數(shù)據(jù)結(jié)構(gòu)c語言版期末考試復習試題

1、數(shù) 據(jù) 結(jié) 構(gòu) 與 算 法 復 習一、選擇題。1在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為_C。A. 動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)D .內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)2. 數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)存中的表示是指_A。A. 數(shù)據(jù)的存儲結(jié)構(gòu)B .數(shù)據(jù)結(jié)構(gòu) C .數(shù)據(jù)的邏輯結(jié)構(gòu) D .數(shù)據(jù)元素之間的關(guān)系3. 在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的_A結(jié)構(gòu)。A. 邏輯 B 存儲 C 邏輯和存儲D 物理（數(shù)據(jù)結(jié)構(gòu)在計算機中的表示（映像）稱為數(shù)據(jù)的物理（存儲）結(jié)構(gòu)）4在存儲數(shù)據(jù)時，通常不僅要存儲各數(shù)據(jù)元素的值，而且還要存儲C。A. 數(shù)據(jù)的處理方法B數(shù)據(jù)元素的類型C.數(shù)據(jù)元素之間的關(guān)

2、系D .數(shù)據(jù)的存儲方法5. 在決定選取何種存儲結(jié)構(gòu)時，一般不考慮A。A. 各結(jié)點的值如何B .結(jié)點個數(shù)的多少C.對數(shù)據(jù)有哪些運算D .所用的編程語言實現(xiàn)這種結(jié)構(gòu)是否方便。6. 以下說法正確的是 _D。A. 數(shù)據(jù)項是數(shù)據(jù)的基本單位B. 數(shù)據(jù)元素是數(shù)據(jù)的最小單位C. 數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)項的集合D. 些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)7.算法分析的目的是C，算法分析的兩個主要方面是A(1)A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中的輸入和輸出的關(guān)系C.分析算法的效率以求改進C.分析算法的易讀性和文檔性(2)A.空間復雜度和時間復雜度B.正確性和簡明性C可讀性和文檔性D.數(shù)據(jù)復雜性和程序復雜性

3、&下面程序段的時間復雜度是 s =0;for( I =0; in; i+) for(j=0;j n;j+) s +=Bij； sum = s ;0(n 2)9.下面程序段的時間復雜度是0( n*m)for( i =0; in; i+)for(j=0;jm;j+)Aij= 0;10. 下面程序段的時間復雜度是O(log 3n)。i = 0 ;while (inext =head15. 帶頭結(jié)點的單鏈表A. head = NULLC. head-next =headA 。B插入刪除不需要移動元素D 所需空間與其長度成正比head為空的判定條件是_AB head- next =NULLD head!

4、=NULLhead為空的判定條件是_B。B head- next =NULLD head!=NULL 16若某表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點或刪除最后一個結(jié)點，則采用D_ 存儲方式最節(jié)省運算時間。A.單鏈表 B 給出表頭指針的單循環(huán)鏈表C 雙鏈表 D 帶頭結(jié)點的雙循環(huán)鏈表C 線性鏈表D 順序存儲結(jié)構(gòu)17.需要分配較大空間，插入和刪除不需要移動元素的線性表，其存儲結(jié)構(gòu)是 A.單鏈表 B .靜態(tài)鏈表18.非空的循環(huán)單鏈表A. p-next = NULLheadB的尾結(jié)點(由p所指向)滿足_C。.p = NULLC.p-n ext =headD.p = head19.在循環(huán)雙鏈表的1

5、 p所指的結(jié)點之前插入s所指結(jié)點的操作是D。A.p-prior =s ；s-next=p ; p-prior-next = s;s-prior=p-priorB.p-prior =s ；p-prior- n ext = s;s_next = p ;s-prior=p-priorC.s-next =:p ；s-prior =p-prior;p-prior = s;p-prior-next = sD.s-next =:p ；s-prior =p-prior;p-prior- next :=s；p-prior = s20.如果最常用的操作是取第 i個結(jié)點及其前驅(qū)，則采用 D 存儲方式最節(jié)省時間。A.

6、單鏈表 B 雙鏈表 C 單循環(huán)鏈表D .順序表21 在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然保持有序的時間復雜度是A. 0( 1) B . 0(n) C . 0(n2)D . 0 (nlog2n )22在一個長度為n (n1)的單鏈表上，設(shè)有頭和尾兩個指針，執(zhí)行B操作與鏈表的長度有關(guān)。A. 刪除單鏈表中的第一個元素B. 刪除單鏈表中的最后一個元素C. 在單鏈表第一個元素前插入一個新元素D. 在單鏈表最后一個元素后插入一個新元素23 與單鏈表相比，雙鏈表的優(yōu)點之一是DA. 插入、刪除操作更簡單B. 可以進行隨機訪問C. 可以省略表頭指針或表尾指針D. 順序訪問相鄰結(jié)點更靈活24 如果

7、對線性表的操作只有兩種，即刪除第一個元素，在最后一個元素的后面插入新元素，則最好使用B_。A. 只有表頭指針沒有表尾指針的循環(huán)單鏈表B. 只有表尾指針沒有表頭指針的循環(huán)單鏈表C. 非循環(huán)雙鏈表D. 循環(huán)雙鏈表25.在長度為n的順序表的第i個位置上插入一個元素(K i n+1)，元素的移動次數(shù)為：AA. n- i + 1 B. n - i C. iD. i - 126 .對于只在表的首、尾兩端進行插入操作的線性表，宜采用的存儲結(jié)構(gòu)為C 。A.順序表B.用頭指針表示的循環(huán)單鏈表C.用尾指針表示的循環(huán)單鏈表D .單鏈表27 .下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點？_C。A插入運算方便B可方便地用于各種邏輯

8、結(jié)構(gòu)的存儲表示C存儲密度大D 刪除運算方便28 .下面關(guān)于 線性表的敘述中，錯誤的是哪一個？_B。A線性表采用順序存儲，必須占用一片連續(xù)的存儲單元B線性表采用順序存儲，便于進行插入和刪除操作。C線性表采用鏈式存儲，不必占用一片連續(xù)的存儲單元D線性表采用鏈式存儲，便于進行插入和刪除操作。29 .線性表是具有n個_B的有限序列。A .字符 B .數(shù)據(jù)元素C .數(shù)據(jù)項 D .表元素30 .在n個結(jié)點的線性表的數(shù)組實現(xiàn)中，算法的時間復雜度是O( 1)的操作是 A。A .訪問第i (1=i=n )個結(jié)點和求第i個結(jié)點的直接前驅(qū)(1i=n )B. 在第i (1=i=n )個結(jié)點后插入一個新結(jié)點C. 刪除第

9、i (1=inext=s ; s-next=p-nextB . s-next=p-next; p-next=s;C . p-next=s ; p-next=s-nextD . p-next=s-next; p-next=s36 .線性表的順序存儲結(jié)構(gòu)是一種AoA .隨機存取的存儲結(jié)構(gòu)B.順序存取的存儲結(jié)構(gòu)C.索引存取的存儲結(jié)構(gòu)D.Hash存取的存儲結(jié)構(gòu)37 .棧的特點是 B，隊列的特點是AoA.先進先出B.先進后出38 .棧和隊列的共同點是CoA.都是先進后出B.都是先進先出C.只允許在端點處插入和刪除兀素D .沒有共冋點39 .一個棧的進棧序列是a, b,c, d,e,則棧的不可能的輸出序列

10、是CA.edcba B . decba C .dceabD . abcde40 .設(shè)有一個棧，元素依次進棧的順序為A B、C D E。下列 C 是不可能的出棧序列。A . A,B,C,D,E B . B,C,D,E,A C . E,A,B,C,D D . E,D,C,B,A41.以下_B不是隊列的基本運算？A.從隊尾插入一個新元素B.從隊列中刪除第i個元素C.判斷一個隊列是否為空D.讀取隊頭元素的值42 .若已知一個棧的進棧序列是1, 2,3, n,其輸出序列為p1, p2 , p3，pn,若 p1 = n,則 pi 為 CA. i B . n iC. n i + 1 D .不確定43.判定一

11、個順序棧st（最多元糸為MaxSize)為空的條件是 BA. st-top != -1Bst-top =-1C. st-top != MaxSizeD.st-top =MaxSize44.判定一個順序棧st（最多兀素為MaxSize)為滿的條件是 DA. st-top != -1Bst-top =-1C. st-top != MaxSizeD.st-top =MaxSize45.個隊列的入隊序列是1, 2, 3, 4,則隊列的輸出序列是 _BA. 4, 3,2,1B.1,2,3,4C. 1 , 4,3,2D.3,2,4,146.判定一個循環(huán)隊列qu-rear - qu-front -1=Max

12、Size qu-rear =qu_front -1qu （最多元素為 MaxSize）為空的條件是 CA. qu-rear - qu-front =MaxSize BC. qu-rear =qu_frontD47.在循環(huán)隊列中，若C。A. front=rear+1 Bfront與rear分別表示對頭兀素和隊尾兀素的位置，則判斷循環(huán)隊列空的條件是.rear=front+1C. front=rearD. front=048.向一個棧頂指針為h的帶頭結(jié)點的鏈棧中插入指針s所指的結(jié)點時，應(yīng)執(zhí)行 D 操作。A. h-next=s; B . s-next=hC. s-next=h;h =s;D . s-n

13、 ext=h-n ext;h-n ext=s;? 49.輸入序列為 ABC可以變?yōu)镃BA時，經(jīng)過的棧操作為B 。A. push, pop, push, pop, push, pop B . push, push, push, pop, pop , popC. push , push, pop, pop , push, pop D . push, pop, push, push , pop, pop50.若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間V1 m , top1、top2分別代表第1和第2個棧的棧頂，棧1的底在V1,棧2的底在Vm,則棧滿的條件是B 。A. |top2-top1|=0 B.

14、top1+1=top2 C . top1+top2=m D . top1=top251. 設(shè)計一個判別表達式中左、右括號是否配對出現(xiàn)的算法，采用D數(shù)據(jù)結(jié)構(gòu)最佳。A. 線性表的順序存儲結(jié)構(gòu)B .隊列 C .線性表的鏈式存儲結(jié)構(gòu)D .棧52. 允許對隊列進行的操作有DA.對隊列中的元素排序C.在隊頭元素之前插入元素B.取出最近進隊的元素D .刪除隊頭元素53. 對于循環(huán)隊列 D。A.無法判斷隊列是否為空C.隊列不可能滿DB .無法判斷隊列是否為滿.以上說法都不對54. 若用一個大小為6的數(shù)值來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為0和3,當從隊列中刪除一個元素，再加入兩個元素后，rea

15、r和front的值分別為 B 。A. 1 和 5 B . 2 和 4 C . 4 和 2 D . 5 和 155 隊列的“先進先出”特性是指D 。A. 最早插入隊列中的元素總是最后被刪除B. 當同時進行插入、刪除操作時，總是插入操作優(yōu)先C. 每當有刪除操作時，總是要先做一次插入操作D. 每次從隊列中刪除的總是最早插入的元素56 和順序棧相比，鏈棧有一個比較明顯的優(yōu)勢是_A_。A.通常不會出現(xiàn)棧滿的情況B 通常不會出現(xiàn)?？盏那闆rC.插入操作更容易實現(xiàn)D刪除操作更容易實現(xiàn)57.用不帶頭結(jié)點的單鏈表存儲隊列，其頭指針指向隊頭結(jié)點，尾指針指向隊尾結(jié)點，則在進行出隊操作 時 _c。A.僅修改隊頭指針B僅

16、修改隊尾指針C.隊頭、隊尾指針都可能要修改D隊頭、隊尾指針都要修改58.若串S= software 其子串的數(shù)目是BA 8 B . 37 C . 36 D . 959.串的長度是指_B。A.串中所含不同字母的個數(shù)C.串中所含不同字符的個數(shù)B.串中所含字符的個數(shù)D.串中所含非空格字符的個數(shù)60.串是一種特殊的線性表，其特殊性體現(xiàn)在BA.可以順序存儲C.可以鏈式存儲B .數(shù)據(jù)兀素是一個字符D .數(shù)據(jù)元素可以是多個字符61 .設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱為BA.連接 B .模式匹配 C .求子串 D .求串長62. 數(shù)組A中，每個元素的長度為3個字節(jié)，行下標i從1到8，列下標j

17、從1到10,從首地址SA開始連續(xù)存放的存儲器內(nèi)，該數(shù)組按行存放，元素A85的起始地址為 C 。A. SA+ 141 B . SA + 144 C . SA+ 222 D . SA+ 22563. 數(shù)組A中，每個元素的長度為3個字節(jié)，行下標i從1到8，列下標j從1到10,從首地址SA開始連續(xù)存放的存儲器內(nèi)，該數(shù)組按行存放，元素A58的起始地址為_C。A. SA+ 141 B . SA + 180 C . SA+ 222 D . SA+ 22564. 若聲明一個浮點數(shù)數(shù)組如下：froat average=new float30;假設(shè)該數(shù)組的內(nèi)存起始位置為200, average15的內(nèi)存地址是 C

18、 。A. 214 B . 215 C . 260 D . 25665 .設(shè)二維數(shù)組 A1m,1n按行存儲在數(shù)組 B中，則二維數(shù)組元素Ai,j 在一維數(shù)組B中的下標為A_。i*(j-1) D . j*m+i-1A. n*(i-1)+j B . n*(i-1)+j-1 C66.有一個100X 90的稀疏矩陣，非 0元素有10,設(shè)每個整型數(shù)占2個字節(jié)，則用三元組表示該矩陣時, 所需的字節(jié)數(shù)是 B 。A. 20 B . 66 C . 18 000 D . 3367 .數(shù)組 A0 4 , -1 -3 , 5A. 55 B . 45 C367中含有的元素個數(shù)是D . 1668對矩陣進行壓縮存儲是為了A.方

19、便運算 B .方便存儲C .提高運算速度D 減少存儲空間69.設(shè)有一個10階的對稱矩陣 A,米用壓縮存儲方式，以行序為主存儲， 為1，每個元素占1個地址空間，則 a8,5的地址為_B_。A. 13 B . 33 C . 18 D . 40a1, 1為第一個元素，其存儲地址70.稀疏矩陣一般的壓縮存儲方式有兩種，即CA.二維數(shù)組和三維數(shù)組B三元組和散列C.三元組和十字鏈表D散列和十字鏈表71.樹最適合用來表示 _C_。A.有序數(shù)據(jù)元素BC.元素之間具有分支層次關(guān)系的數(shù)據(jù).無序數(shù)據(jù)元素D.元素之間無聯(lián)系的數(shù)據(jù)72 .深度為5的二叉樹至多有_C個結(jié)點。A. 16 B .32 C .31 C .107

20、3. 對一個滿二叉樹，m個葉子，n個結(jié)點，深度為h,則DA. n = h+m B h+m = 2n C m = h-1 D n = 2h-174. 任何一棵二叉樹的葉子結(jié)點在前序、中序和后序遍歷序列中的相對次序AA.不發(fā)生改變B.發(fā)生改變C.不能確定D.以上都不對75. 在線索化樹中，每個結(jié)點必須設(shè)置一個標志來說明它的左、右鏈指向的是樹結(jié)構(gòu)信息，還是線索化信息，若0標識樹結(jié)構(gòu)信息,1標識線索，對應(yīng)葉結(jié)點的左右鏈域，應(yīng)標識為A. 00B. 01C . 101176 .在下述論述中，正確的是 _D。只有一個結(jié)點的二叉樹的度為0 :二叉樹的度為2;二叉樹的左右子樹可任意交換;深度為K的順序二叉樹的結(jié)

21、點個數(shù)小于或等于深度相同的滿二叉樹。A. B . C . D .77 .設(shè)森林F對應(yīng)的二叉樹為 B,它有m個結(jié)點，B的根為p，p的右子樹的結(jié)點個數(shù)為n，森林F中第棵樹的結(jié)點的個數(shù)是_A。A. m-n B . m-n-1 C . n+1 D .不能確定78 .若一棵二叉樹具有 10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點的個數(shù)是 BA. 9 B . 11 C . 15 D .不能確定N0=N2+179.具有10個葉子結(jié)點的二叉樹中有 _B個度為2的結(jié)點。A. 8 B . 9 C . 10 D . 1180.在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的C 倍。A. 1/2 B 1 C

22、2 D 481.在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的B 倍。A. 1/2 B 1 C 2 D 482.某二叉樹結(jié)點的中序序列為A. 3B . 2ABCDEFG后序序列為 BDCAFG,則其左子樹中結(jié)點數(shù)目為:C. 4D. 583 .已知一算術(shù)表達式的中綴形式為A. A+B*C/DEBA+ B *C- D/E,后綴形式為ABC*+DE/ -,其前綴形式為DA+B*CD/EC +*ABC/DED. +A*BC/DE84 .已知一個圖，如圖所示，若從頂點 a出發(fā)按深度搜索法 可能得到的一種頂點序列為_D_ ;按廣度搜索法進行遍到的一種頂點序列為A ;A.a,b, e,c,d,

23、fB.a,c,f, e,b,dC .a,e, b,c,f, d,D.a,e,d, f,c,bA.a,b, c,e,d, fB.a,b,c, e,f,dC .a,e, b,c,f, d,D.a,c,f, d,e,b進行遍歷，則 歷，則可能得85 .采用鄰接表存儲的圖的 深度優(yōu)先遍 歷算法類似于二叉樹的_A_A.先序遍歷B .中序遍歷 C .后序遍歷 D .按層遍歷86 .采用鄰接表存儲的圖的 廣度優(yōu)先遍 歷算法類似于二叉樹的D next-next=L。18. 是限定僅在表尾進行插入或刪除操作的線性表，其運算遵循后進先出的原則。19. 空串是 零個字符的串，其長度等于 零。空白串是由一個或多個空格

24、字符組成的串，其長度等于其 _ 包含的空格個數(shù)。20. 組成串的數(shù)據(jù)元素只能是單個字符。21. 一個字符串中 任意個連續(xù)字符構(gòu)成的部分稱為該串的子串。22. 子串” str ” 在主串” datastructure ” 中的位置是 5。23. 二維數(shù)組 M的每個元素是6個字符組成的串，行下標 i的范圍從0到8,列下標j的范圍從1到10, 則存放M至少需要54L個字節(jié)；M的第8列和第5行共占108個字節(jié)。24. 稀疏矩陣一般的壓縮存儲方法有兩種，即三元組表和 十字鏈表。25. 廣義表(a), ( b), c), (d)的長度是衛(wèi)_，深度是_4_。26. 在一棵二叉樹中，度為零的結(jié)點的個數(shù)為n0,

25、度為2的結(jié)點的個數(shù)為n2,則有n0 =n 2+1。27. 在有n個結(jié)點的二叉鏈表中，空鏈域的個數(shù)為n+1 。28. 棵有n個葉子結(jié)點的哈夫曼樹共有 _2n-1_個結(jié)點。29. 深度為5的二叉樹至多有_J1個結(jié)點。30. 若某二叉樹有20個葉子結(jié)點，有30個結(jié)點僅有一個孩子，則該二叉樹的總結(jié)點個數(shù)為69。31 .某二叉樹的前序遍歷序列是abdgcefh，中序序列是dgbaechf,其后序序列為 gdbehfca 。32 .線索二叉樹的左線索指向其遍歷序列中的前驅(qū),右線索指向其遍歷序列中的后繼。33. 在各種查找方法中，平均查找長度與結(jié)點個數(shù)n無關(guān)的查找方法是散列查找法 。34. 在分塊索引查找方

26、法中，首先查找索引表，然后查找相應(yīng)的塊表 。35 .一個無序序列可以通過構(gòu)造一棵二叉排序 樹而變成一個有序序列，構(gòu)造樹的過程即為對無序序列進行排序的過程。36. 具有10個頂點的無向圖，邊的總數(shù)最多為45 。37. 已知圖G的鄰接表如圖所示，其從頂點v1出發(fā)的深度優(yōu)先搜索序列為v1v2v3v6v5v4 ，其從頂點v1出發(fā)的廣度優(yōu)先搜索序列為v1v2v5v4v3v6 。38. 索引是為了加快檢索速度而引進的一種數(shù)據(jù)結(jié)構(gòu)。一個索引隸屬于某個數(shù)據(jù)記錄集，它由若干索引項組成，索引項的結(jié)構(gòu)為關(guān)鍵字 禾口 關(guān)鍵字對應(yīng)記錄的地址。39. Prim算法生成一個最小生成樹每一步選擇都要滿足邊的總數(shù)不超過 n-1

27、，當前選擇的邊的權(quán)值是候選邊中最小的， 選中的邊加入樹中不產(chǎn)生回路三項原則。40. 在一棵m階B樹中，除根結(jié)點外，每個結(jié)點最多有m 棵子樹，最少有 m/2棵子樹。三、判斷題。1在決定選取何種存儲結(jié)構(gòu)時，一般不考慮各結(jié)點的值如何。（V）2. 抽象數(shù)據(jù)類型（ADT包括定義和實現(xiàn)兩方面，其中定義是獨立于實現(xiàn)的，定義僅給出一個ADT的邏輯特性，不必考慮如何在計算機中實現(xiàn)。（V ）3. 抽象數(shù)據(jù)類型與計算機內(nèi)部表示和實現(xiàn)無關(guān)。（V ）4. 順序存儲方式插入和刪除時效率太低，因此它不如鏈式存儲方式好。（X ）5線性表采用鏈式存儲結(jié)構(gòu)時，結(jié)點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的。（X ）6對任何數(shù)據(jù)結(jié)構(gòu)鏈式存

28、儲結(jié)構(gòu)一定優(yōu)于順序存儲結(jié)構(gòu)。（X ）7.順序存儲方式只能用于存儲線性結(jié)構(gòu)。（X ）&集合與線性表的區(qū)別在于是否按關(guān)鍵字排序。（X ）9線性表中每個元素都有一個直接前驅(qū)和一個直接后繼。（X ）10.線性表就是順序存儲的表。（X ）11取線性表的第i個元素的時間同i的大小有關(guān)。（X ）12循環(huán)鏈表不是線性表。（X ）13. 鏈表是采用鏈式存儲結(jié)構(gòu)的線性表，進行插入、刪除操作時，在鏈表中比在順序表中效率高。（V ）14. 雙向鏈表可隨機訪問任一結(jié)點。（X ）15. 在單鏈表中，給定任一結(jié)點的地址p，則可用下述語句將新結(jié)點s插入結(jié)點p的后面：p-next = s;s_next = p_next; （X ）16隊列是一種插入和刪除操作分別在表的兩端進行的線