數(shù)據(jù)結(jié)構(gòu)練習(xí)附答案

1、、單項(xiàng)選擇題1. 邏輯關(guān)系是指數(shù)據(jù)元素間的( )A 類型 B 存儲(chǔ)方式C 結(jié)構(gòu) D 數(shù)據(jù)項(xiàng)2. 對(duì)于只在表的首、尾兩端進(jìn)行插入操作的線性表，宜采用的存儲(chǔ)結(jié)構(gòu)為 ( )A.順序表B.用頭指針表示的單循環(huán)鏈表C. 用尾指針表示的單循環(huán)鏈表D. 單鏈表3. 設(shè)數(shù)組datam作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行出隊(duì)操作后其頭指針front 值為( )B front=A front=front+1 (front+1)%(m-1)C front=(front-1)%mD front=(front+1)%m4. 在具有 n 個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front

2、 和 rear 分別為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)滿的條件為 ( )。A rear n=front B (front+l) n=rearC rear n-1=front D (rear+l) n=front5. 在具有 n 個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front 和 rear 分別為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)空的條件為 ( )。A rear n=front B front+l=rearC rear=front D (rear+l) n=front6. 已知一顆二叉樹(shù)上有92 個(gè)葉子結(jié)點(diǎn)，則它有個(gè)度為 2 的結(jié)點(diǎn)。( )A. 90B. 91 C. 92 D. 937. 在一棵非空二叉樹(shù)的

3、中序遍歷序列中，根結(jié)點(diǎn)的右邊只有右子樹(shù)上的部分結(jié)點(diǎn)只有左子樹(shù)上的部分結(jié)點(diǎn)鏈表中結(jié)點(diǎn)的個(gè)數(shù)是( ) 個(gè)。n*nA. 只有右子樹(shù)上的所有結(jié)點(diǎn)B.C. 只有左子樹(shù)上的所有結(jié)點(diǎn)D.8. 有 n 條邊的無(wú)向圖的鄰接表存儲(chǔ)法中，A. n B. 2n C. n/2 D.9. 判斷有向圖是否存在回路，除了可利用拓?fù)渑判蚍椒ㄍ猓€可以利用( ) 。A. 求關(guān)鍵路徑的方法B.求最短路徑的方法C. 深度優(yōu)先遍歷算法D.廣度優(yōu)先遍歷算法10. 對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須()A.鍵值有序的順序表B.鍵值有序的鏈接表C.鏈接表但鍵值不一定有序D.順序表但鍵值不一定有序11. 下列時(shí)間復(fù)雜度中最好的是()。A.

4、 O(1) B . O(n) C . O(log2n) D . O(n2)12. 若某線性表的常用操作是取第i個(gè)元素及其前趨元素，則采用() 存儲(chǔ)方式最節(jié)省時(shí)間？A.順序表 B.單鏈表C雙鏈表 D.單向循環(huán)13. 在一個(gè)單鏈表HL中，若要向q所指結(jié)點(diǎn)之后插入一個(gè)由指針p指向 的結(jié)點(diǎn)，則執(zhí)行()A. HL=p;p->next=HL B , p->next=HL;HL=pC. p->next=q->next;q->next=p D . p->next=q->next;q=p>next14 .棧和隊(duì)列是兩種特殊的線性表，只能在它們的()處添加或刪除結(jié)點(diǎn)

5、。A.中間點(diǎn) B .端點(diǎn)C隨機(jī)存取點(diǎn)D .結(jié)點(diǎn)15 . 一個(gè)棧的輸入序列為1, 2, 3, 4, 5,則下列序列中不可能是站的輸 出序列的是A. 2,3,4,1,5B.5,4,1,3,2C. 2,3,1,4,5D.1,5,4,3,216 .廣義表(a),a)的表尾是。()A. a B .A C . (a) D . (a)17 .將含100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根這一層開(kāi)始，每層從左至右依次 對(duì)結(jié)點(diǎn)編號(hào)，根結(jié)點(diǎn)的編號(hào)為1。編號(hào)為47的結(jié)點(diǎn)X的雙親的編號(hào) 為()A. 24 B . 25C. 23 D.無(wú)法確定18 .有n個(gè)頂點(diǎn)的無(wú)向圖的鄰接矩陣是用 數(shù)組存儲(chǔ)。A. n行n列 B. 一維 C. 任意行

6、n列 D.n行任意19 .如圖所示有向圖的一個(gè)拓?fù)湫蛄惺?)A. ABCDEF B. FCBEAD C. FEDCBA D. DAEBCF20 .有一個(gè)有序表1 , 4, 6, 10, 18, 35, 42, 53, 67, 71, 78, 84,92, 99,當(dāng)用二分查找法查找鍵值為84的結(jié)點(diǎn)時(shí)，經(jīng) 比較后查找成功。A.2B.3C.4D.1221.在一個(gè)帶有附加表頭結(jié)點(diǎn)的單鏈表HL中，若要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行（）A. HL=p; p->next=HL;B. p->next=HL->next;HL->next=p;C. p->next=HL;

7、p=HL; D. p->next=HL; HL=p;22 .若采用單鏈表表示循環(huán)隊(duì)列，則應(yīng)該選用（）A.帶尾指針的非循環(huán)鏈表B.帶尾指針的循環(huán)鏈表C.帶頭指針的非循環(huán)鏈表D.帶頭指針的循環(huán)鏈表23 .棧和隊(duì)列是兩種特殊的線性表，只能在它們的 處添加或刪 除結(jié)點(diǎn)。（）A.中間點(diǎn) B.端點(diǎn)C.隨機(jī)存取點(diǎn)D.結(jié)點(diǎn)24 .首先訪問(wèn)結(jié)點(diǎn)的左子樹(shù)，然后訪問(wèn)該結(jié)點(diǎn)，最后訪問(wèn)結(jié)點(diǎn)的右子樹(shù)， 這種遍歷稱為（）A.前序遍歷B.后序遍歷C.中序遍歷D.層次遍歷25 .樹(shù)最適合用來(lái)表示（）A.有序數(shù)據(jù)元素B.無(wú)序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無(wú)聯(lián)系的數(shù)據(jù)26 .已知一顆二叉樹(shù)上有92個(gè)葉

8、子結(jié)點(diǎn)，則它有 個(gè)度為2的結(jié)點(diǎn)。（ ）A. 90B. 91C. 92D. 9327 .對(duì)一棵查找樹(shù)根結(jié)點(diǎn)而言，左子樹(shù)中所有結(jié)點(diǎn)與右子樹(shù)中所有結(jié)點(diǎn) 的關(guān)鍵字大小關(guān)系是（）A 小于R 大于G 等于D 不小于28 .對(duì)關(guān)鍵字序列19, 11, 27, 18, 33進(jìn)行快速排序，則要進(jìn)行多少次 關(guān)鍵字比較？（）A. 5次B. 6次C. 7次D. 8次1 .設(shè)有一個(gè)二維數(shù)組Amn，假設(shè)A00存放位置在644到，A22 存放位置在676（io）,每個(gè)元素占一個(gè)空間，問(wèn)A33 （10）存放在什么 位置？腳注（10）表示用10進(jìn)制表示。（C ）A.688B.678 C.692D.6962 .設(shè)有6個(gè)結(jié)點(diǎn)的無(wú)向

9、圖，該圖至少應(yīng)該有（A ）條邊才能確保是一 個(gè)連通圖。A.5 B. 6 C. 7 D. 83 .根據(jù)二叉樹(shù)的定義可知二叉樹(shù)共有（B ）種不同的形態(tài)。A.4B.5C.6D.74 .假設(shè)在一棵二叉樹(shù)中，雙分支結(jié)點(diǎn)數(shù)為15,單分支結(jié)點(diǎn)數(shù)為30個(gè)，則葉子結(jié)點(diǎn)數(shù)為 ( B ) 個(gè)。A 15 B 16 C 17 D 475 . 任何一棵二叉樹(shù)的葉子結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序 ( A )。A.不發(fā)生改變 B .發(fā)生改變C.不能確定D .以上都不對(duì)6 . 在一個(gè)具有n 個(gè)頂點(diǎn)的無(wú)向完全圖中，所含的邊數(shù)為 ( C ) 。A n B n(n-1) C n(n-1)/2 D n(n+1)/27 .

10、若一個(gè)圖的邊集為 (A,B),(A,C),(B,D),(C,F),(D,E),(D,F) ，則從頂點(diǎn) A 開(kāi)始對(duì)該圖進(jìn)行深度優(yōu)先搜索，得到的頂點(diǎn)序列可能為( B ) 。A A,B,C,F,D,EB A,C,F,D,E,BC A,B,D,C,F,ED A,B,D,F,E,C8 . 假定對(duì)元素序列 (7,3,5,9,1,12) 進(jìn)行堆排序，采用小頂堆，則初始數(shù)據(jù)構(gòu)成的初始堆為 ( B )。A 1,3,5,7,9,12 B 1,3,5,9,7,12C 1,7,3,5,9,12 D 1,3,5,7,9,12二、填空題1. 根據(jù)值的不同特性，高級(jí)程序語(yǔ)言中的數(shù)據(jù)類型可分為兩類： 和2. 線性表有兩種存儲(chǔ)

11、結(jié)構(gòu)： 和。3. 在以HL為表頭指針的循環(huán)單鏈表中，鏈表為空的條件為 。4. 設(shè)棧S和隊(duì)列Q的初始狀態(tài)皆為空，元素 a1,a2,a3,a4,a5 和a6一次通過(guò)一個(gè) 棧后即進(jìn)入隊(duì)列Q若6個(gè)元素出對(duì)的順序是 a3,a5,a4,a6,a2,a1 ，則棧S至少可以容納 個(gè)元素。5. 對(duì)于一棵具有30 個(gè)結(jié)點(diǎn)的二叉樹(shù)， 若一個(gè)結(jié)點(diǎn)的編號(hào)為 5 ， 則它的左孩子結(jié)點(diǎn)的編號(hào)為 ， 右孩子結(jié)點(diǎn)的編號(hào)為， 雙親結(jié)點(diǎn)的編號(hào)為 。6. 對(duì)于一個(gè)具有n 個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)它存儲(chǔ)在二叉鏈表中時(shí)，其指針字段的總數(shù)為 個(gè)，其中 個(gè)用于鏈接孩子結(jié)點(diǎn)， 個(gè)空閑。7. 設(shè)圖中有 n 個(gè)頂點(diǎn)， e 條邊， 則含有 e= 條邊的無(wú)

12、向圖稱作完全圖，含有 e=條弧的有向圖稱作有向完全圖。8. 對(duì)于線性表( 78， 4 ， 56， 30 ， 65)進(jìn)行哈希存儲(chǔ)時(shí)，若選用H( K) =K %5 作為哈希函數(shù)，則哈希地址為 0 的元素有 個(gè)。9. 在單鏈表上難以實(shí)現(xiàn)的排序方法有和 。10. 根據(jù)值的不同特性，高級(jí)程序語(yǔ)言中的數(shù)據(jù)類型可分為兩類： 和11. 在單鏈表中，刪除指針 P 所指節(jié)點(diǎn)的后繼結(jié)點(diǎn)的語(yǔ)句是 。12. 棧又稱為 的線性表，隊(duì)列又稱為 的線性表。13. N 個(gè)結(jié)點(diǎn)的二叉樹(shù)采用二叉鏈表存放，共有空鏈域個(gè)數(shù)為 。14. 一棵深度為 k 的滿二叉樹(shù)的結(jié)點(diǎn)總數(shù)為 ，一棵深度為 k 的完全二叉樹(shù)的結(jié)點(diǎn)總數(shù)的最小值為 ，最大值

13、為 。15. 具有 80 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，若按層次從上到下、從左到右對(duì)其編號(hào) （ 根結(jié)點(diǎn)為 1 號(hào)） ，則編號(hào)最大的分支結(jié)點(diǎn)序號(hào)為 ，編號(hào)最小的分支結(jié)點(diǎn)序號(hào)為 ，編號(hào)最大的葉子結(jié)點(diǎn)序號(hào)為 ，編號(hào)最小的葉子結(jié)點(diǎn)序號(hào)為 。16. 采用二分法進(jìn)行查找的查找表，應(yīng)選擇 的存儲(chǔ)結(jié)構(gòu)。17. 假設(shè)在有序表A 019中進(jìn)行二分查找，比較二次查找成功的結(jié)點(diǎn)數(shù)為 ，比較三次查找成功的結(jié)點(diǎn)數(shù)為 。18. 一個(gè)有向圖G 中若有弧<Vj,Vi> 、 <Vi,Vk> 和 <Vj,Vk> ，則在圖 G 的拓樸序列中，頂點(diǎn) Vi,Vj 和 Vk 的相對(duì)位置為 。19. 對(duì)于一個(gè)長(zhǎng)度為

14、 n 的順序存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為 ，在表尾插入元素的時(shí)間復(fù)雜度為 。20. 棧又稱為 的線性表，隊(duì)列又稱為 的線性表。21. 對(duì)于一棵具有n 個(gè)結(jié)點(diǎn)的二叉樹(shù)， 用二叉鏈表存儲(chǔ)時(shí)， 其指針總數(shù)為 個(gè)，其中 個(gè)指針是空閑的。22. 在稀疏矩陣所對(duì)應(yīng)的三元組線性表中，每個(gè)三元組元素按 為主序、為輔序的次序排列。23. 一顆深度為 K 且有 個(gè)結(jié)點(diǎn)的二叉樹(shù)稱為滿二叉樹(shù)。24. 若對(duì)一棵完全二叉樹(shù)從 0 開(kāi)始進(jìn)行結(jié)點(diǎn)的編號(hào)，并按此編號(hào)把它順序存儲(chǔ)到一維數(shù)組 A 中，即編號(hào)為 0 的結(jié)點(diǎn)存儲(chǔ)到 A0 中。其余類推，則 Ai 元素的左孩子元素為 ，雙親元素為 。25. 對(duì)于線性表（ 7

15、8， 4 ， 56， 30 ， 65）進(jìn)行哈希存儲(chǔ)時(shí)，若選用H（ K） =K %5 作為哈希函數(shù)， 則哈希地址為 0 的元素有 個(gè)， 哈希地址為 4 的有 個(gè)。26. 以折半查找方法從長(zhǎng)度為 8 的有序表中查找一個(gè)元素時(shí)，平均查找長(zhǎng)度為27. 假 定 一 個(gè) 有 向 圖 的 頂 點(diǎn) 集 為 a,b,c,d,e,f， 邊 集<a,c>,<a,e>,<c,f>,<d,c>,<e,b>,<e,d>， 則 出 度 為 0 的 頂 點(diǎn) 個(gè) 數(shù) 為 ，入度為 1 的頂點(diǎn)個(gè)數(shù)為 。28. 設(shè)有向圖 G中有向邊的集合 E=<1, 2

16、>, <2, 3>, <1, 4>, <4, 2>, <4, 3>, 則該圖的一種拓?fù)湫蛄袨?。29. 對(duì)于一棵具有n 個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)進(jìn)行鏈接存儲(chǔ)時(shí)，其二叉鏈表中的指針域的總數(shù)為2n個(gè)，其中 個(gè)用于鏈接孩子結(jié)點(diǎn)，個(gè)空閑著。30. 設(shè)有向圖中不存在有向邊，則其對(duì)應(yīng)的鄰接矩陣A中的數(shù)組元素 Aij 的值等于。31. 根據(jù)初始關(guān)鍵字序列(19, 22, 01, 38, 10)建立的二叉排序樹(shù)的高度為 c 32.三.應(yīng)用題1 .順序隊(duì)的“假溢出”是怎樣產(chǎn)生的？如何知道循環(huán)隊(duì)列是空還是滿？2 .回文。假設(shè)一字符序列已存入計(jì)算機(jī)，請(qǐng)分析用線性表、堆

17、棧和隊(duì) 列等方式正確輸出其回文的可能性？假設(shè)正讀和反讀都相同的字符序 列為“回文”，例如，abba'和'abcba'是回文，'abcde'和'ababab' 則不是。3 .設(shè)有編號(hào)為1, 2, 3, 4的四輛列車，順序進(jìn)入一個(gè)棧式結(jié)構(gòu)的車站， 具體寫(xiě)出這四輛列車開(kāi)出車站的所有可能的順序。至少有14種。 全進(jìn)之后再出，f#況，只有 1種：4, 3, 2, 1 進(jìn)3個(gè)之后再出的情況，有 3種，3,4,2,1 3,2,4,1 3,2,1,4 進(jìn)2個(gè)之后再出的情況，有 5種，2,4,3,1 2,3,4,1 2,1,3,4 2,1,4,32,1,3

18、,4 進(jìn)1個(gè)之后再出的，情況，有 5種，1,4,3,2 1,3,2,4 1,3,4,2 1,2,3,41,2,4,34 .對(duì)給定的權(quán)值2,3,4,7,8,9,構(gòu)造出相應(yīng)的赫夫曼樹(shù)，并求出帶權(quán) 路徑的長(zhǎng)度WPL33WPL=2*4+3*4+4*3+9*2+7*2+8*2=805 .對(duì)于下圖的無(wú)向圖，繪出從 a出發(fā)，用普利姆算法構(gòu)造的最小生成樹(shù)的過(guò)程6.請(qǐng)畫(huà)出右圖的鄰接矩陣和鄰接表7 .試比較順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)。在什么情況下用順 序表比鏈表好？在什么情況下用鏈表比順序表好？順序存儲(chǔ)時(shí)，相鄰數(shù)據(jù)元素的存放地址也相鄰（邏輯與物理統(tǒng)一）；要求內(nèi)存中可用存儲(chǔ)單元的地址必須是連續(xù)的。優(yōu)點(diǎn)：存儲(chǔ)

19、密度大（=1?）,存儲(chǔ)空間利用率高。缺點(diǎn)：插入或刪除元素時(shí)不方便。鏈?zhǔn)酱鎯?chǔ)時(shí)，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲(chǔ)空間分兩部分， 一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針優(yōu)點(diǎn)：插入或刪除元素時(shí)很方便，使用靈活。缺點(diǎn)：存儲(chǔ)密度小，存儲(chǔ)空間利用率 低。順序表適宜于做查找這樣的靜態(tài)操作;鏈表宜于做插入、刪除這樣的動(dòng)態(tài)操作。若線性表的長(zhǎng)度變化不大，且其主要操作是查找，則采用順序表； 若線性表的長(zhǎng)度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。8 .按照下列給定二叉樹(shù)的先序遍歷序列、中序遍歷序列和后序遍歷序 歹I，分別構(gòu)造出二叉樹(shù)。先序遍歷序歹h EBADCFHGIKJ中序遍歷序歹h ABCDEFGHIJK 中序遍歷序列：ACBGEDF后序遍歷序列：ABCDEFG（2）9 .如下列所示的連通圖，請(qǐng)畫(huà)出：(1)以頂點(diǎn)a為根的深度優(yōu)先生成樹(shù)；(2)如