一、數(shù)據(jù)結(jié)構(gòu)大綱解讀二、題型和分?jǐn)?shù)分配20xx年：分?jǐn)?shù)-資料下載頁
2024-10-17 21:10本頁面
【導(dǎo)讀】單項(xiàng)選擇題10道,每題2分,共20分。1）算法理解10分。2）編算法(鏈表)15分。描述設(shè)計(jì)思想、算法效率。；掌握數(shù)據(jù)的邏輯結(jié)、存儲(chǔ)結(jié)。構(gòu)及其差異，以及各種基本操作的實(shí)現(xiàn)。進(jìn)行設(shè)計(jì)與分析。、基本原理和基本方法。求解，具備采用C或C++或JAVA語言設(shè)計(jì)與實(shí)現(xiàn)算法的能力。數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算程序設(shè)。關(guān)系，如線性表、棧、隊(duì)列。包括數(shù)據(jù)元素的表示和關(guān)系的表示。數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中的兩種表示。非順序表示--------鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。抽象數(shù)據(jù)類型定義格式：。ADT抽象數(shù)據(jù)類型名{. }抽象數(shù)據(jù)類型名。具體步驟的描述，是指令的有限序列。1）有窮性-必須在執(zhí)行有窮步之后結(jié)束。2）確定性-每條指令有確切含義，不產(chǎn)生二義性。3）可行性-所有操作都是可以實(shí)現(xiàn)的。常見函數(shù)的增長(zhǎng)率。在等概率情況下討論算法的復(fù)雜度。說明兩個(gè)數(shù)據(jù)結(jié)構(gòu)的邏輯
【正文】 下面程序段中帶有下劃線的語句的執(zhí)行次數(shù)的數(shù)量級(jí)是 ( ) i： =n*n ； WHILE i1 DO i:=i div 2。 18. 計(jì)算機(jī)執(zhí)行下面的語句時(shí)，語句 s的執(zhí)行次數(shù)為 _______ 。 FOR(i=l； inl； i++) FOR(j=n。j=i。j) s。 19．解釋概念 （ 1）數(shù)據(jù)類型 （ 2）數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu) （ 3）抽象數(shù)據(jù)類型 （ 4）算法的時(shí)間復(fù)雜性 20. 運(yùn)算是數(shù)據(jù)結(jié)構(gòu)的一個(gè)重要方面。試舉一例，說明兩個(gè)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲(chǔ)方式完全相同，只是對(duì)于運(yùn)算的定義不同。因而兩個(gè)結(jié)構(gòu)具有顯著不同的特性，是兩個(gè)不同的結(jié)構(gòu)。 21. 試舉一例，說明對(duì)相同的邏輯結(jié)構(gòu) ,同一種運(yùn)算在不同的存儲(chǔ)方式下實(shí)現(xiàn)，其運(yùn)算效率不同。 22．設(shè) n是偶數(shù)，試計(jì)算運(yùn)行下列程序段后 m的值并給出該程序段的時(shí)間復(fù)雜度。 m:=0。 FOR i:=1 TO n DO FOR j:=2*i TO n DO m:=m+1。 23．將下列函數(shù)，按它們?cè)?n→ ∝ 時(shí)的無窮大階數(shù)，從小到大排序。 n, nn3+7n5, nlogn, 2n/2, n3, logn, n1/2+logn, (3/2)n, n!, n2+logn C B 2 B 3D 5C 6C 7D 8A 9C 10A 11C 12．集合 線性結(jié)構(gòu) 樹形結(jié)構(gòu) 圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。 13. 1） n+1 （ 2） n （ 3） n(n+3)/2 （ 4） n(n+1)/2。 14. O(n3) 15. log2n 16. nlog2n 17. log2n2 18. (n+3)(n2)/2 20. 棧和隊(duì)列的邏輯結(jié)構(gòu)相同，其存儲(chǔ)表示也可相同（順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)），但由于其運(yùn)算集合不同而成為不同的數(shù)據(jù)結(jié)構(gòu)。 22. O(n2) 頻度： n2/4 23. logn, n1/2+logn, n, nlogn, n2+logn， n3, nn3+7n5, 2n/2, (3/2)n, n!
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1