數(shù)據(jù)結(jié)構(gòu)附部分答案資料

1、選擇題1、下面關(guān)于線性表的敘述錯(cuò)誤的是（C ）。A. 線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間B. 線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間C. 線性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn)D. 線性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn)答案解析:根據(jù)順序存儲(chǔ)和旌接存儲(chǔ)的線性表優(yōu)缺點(diǎn)的分析，可以發(fā)現(xiàn)選項(xiàng)G中順序徉儲(chǔ)的線性表便于進(jìn)行 増刪操作是不正確的，而本題恰好讓我們選擇錯(cuò)i吳的說(shuō)法，則必是選項(xiàng)G無(wú)疑。2、棧是一種特殊的線性表，具有（ B ）性質(zhì)A .先進(jìn)先出 B.先進(jìn)后出 C.后進(jìn)后出 D.順序進(jìn)出3、 順序循環(huán)隊(duì)列中（數(shù)組大小為n）,隊(duì)頭指示front指向隊(duì)列的第一個(gè)元素，隊(duì)尾指示r

2、ear指向隊(duì)列最后一個(gè)元素的后一個(gè)位置，則循環(huán)隊(duì)列中存放了n-1個(gè)元素，即循環(huán)隊(duì)列滿的條件是（ B ）。A . （rear+1）%n=front-1B.（rear+1）%n=frontC. （rear）% n=frontD.rear+1=fr ont4、 在一個(gè)單鏈表中，若刪除p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行（A ）。A . p-next=p-next-nextB. p=p-n ext;p-n ext- n extC. p-n ext=p-nextD. p=p-n ext- next答案耀折：解析：在一個(gè)單誰(shuí)表中.若要?jiǎng)h除唏點(diǎn)的后續(xù)結(jié)點(diǎn)，只要將P的扌潤(rùn)域指向P的后繼的后繼即可， 冃卩pT-門巳.

3、next-j. nexto5、 設(shè)某二叉樹中度數(shù)為 0的結(jié)點(diǎn)數(shù)為Nb,度數(shù)為1的結(jié)點(diǎn)數(shù)為N ,度數(shù)為2的結(jié)點(diǎn)數(shù)為Nk,則下列等式成立的是（ A ）。A. N0=N2+1 B.N0=Nl+N2 C. N0=N1 + 1D.N0=2N1+l6、 設(shè)有6個(gè)結(jié)點(diǎn)的無(wú)向圖，該圖至少應(yīng)有（D）條邊才能確保是一個(gè)連通圖。A. 8B.6C.7D.57、 設(shè)有向無(wú)環(huán)圖 G中的有向邊集合 E=, , , ，則下列屬于該 有向圖G的一種拓?fù)渑判蛐蛄械氖牵ˋ ）。A.1 , 2, 3, 4B. 2, 3, 4, 1C.1, 4, 2, 3 D. 1, 2 , 4 , 38、已知一個(gè)有向圖如下所示，則從頂點(diǎn) a出發(fā)進(jìn)行

4、深度優(yōu)先遍歷，不可能得到的DFS序列為（A ）。A.a d b e f cB. a d c e f bC.a d c e b fD.a d e f b cd第 14 頁(yè) 共 11 頁(yè)9、 適用于折半查找的表的存儲(chǔ)方式及元素排列要求是（D ）A. 鏈?zhǔn)椒绞酱鎯?chǔ)，元素?zé)o序B. 鏈?zhǔn)酱鎯?chǔ)方式，元素有序C. 順序存儲(chǔ)方式，元素?zé)o序D. 順序存儲(chǔ)方式，元素有序10、 設(shè)一組初始記錄關(guān)鍵字序列為（345，253, 674, 924, 627），則用基數(shù)排序需要進(jìn)行（C）趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。A. 5B. 4C. 3D. 811 、棧和隊(duì)列的共同特點(diǎn)是 （A ）。A. 只允許在端

5、點(diǎn)處插入和刪除元素B. 都是先進(jìn)后出C. 都是先進(jìn)先出D. 沒(méi)有共同點(diǎn)答案解析：詹析棧和隊(duì)列都是一種特殊的操作竟限的線性表，只允許在嘉點(diǎn)處逬行插入和刪除.二者的區(qū) 別矗棧只允許在豪的一蒯進(jìn)行插入或刪除操作，是一種后進(jìn)先出媲戔性表:而隊(duì)列只允許在験的一端進(jìn)行插入操作，在另一端進(jìn)行鵬操柞，是一種咲進(jìn)先出”的線性表。12、用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)（D ）.A.僅修改頭指針B.頭、尾指針都要修改C.僅修改尾指針D.頭、尾指針可能都要修改13、以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)？（ D ）A.隊(duì)列B.棧C.線性表D.二叉樹答案解折：暉析二叉軻屬于非線性結(jié)構(gòu)。棧是一種特殊的線性表*這戔性表只能

6、在固定的一端朋亍插入和刪除操作，臥列可看作是插入在一端進(jìn)行，硼除在另一端進(jìn)行的線性表。14、樹最適合用來(lái)表示（C ）。A.有序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)15、二叉樹的第k層的結(jié)點(diǎn)數(shù)最多為（D ）.kA. 2 -1B.2K+1C.2K-1B.無(wú)序數(shù)據(jù)元素D.元素之間無(wú)聯(lián)系的數(shù)據(jù)D. 2k-116、設(shè)某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為 CABD，則后序遍歷該二叉樹得到序列為（A ）。(A) BADC (B) BCDA(C) CDAB(D) CBDA前序遍歷先訪問(wèn)根，所以 C為根，在中序遍歷中先訪問(wèn)左子樹，再訪問(wèn)根，最后訪問(wèn)右子樹， 所以在中序序列中，C前面的為左子樹

7、，第二個(gè)訪問(wèn)的是左子樹的根A以此類推可得這樣的一棵二叉樹：17、下列四種排序中（D ）的空間復(fù)雜度最大。（A）插入排序（B）冒泡排序 （C）堆排序（D）歸并排序18、對(duì)于線性表（7，34, 55, 25, 64, 46, 20，10）進(jìn)行散列存儲(chǔ)時(shí)，若選用H（ K） =K %9作為散列函數(shù)，則散列地址為1的元素有（D ）個(gè)，A.1 B . 2 C . 3 D . 4分別是：55 , 64 , 46 , 10.H （K） = K%9，表示除以9的余數(shù)。由于地址重疊造成沖突，所以散列存儲(chǔ)時(shí)，通常還要有解決沖突的辦法，如線性探查法等等。19、設(shè)有6個(gè)結(jié)點(diǎn)的無(wú)向圖，該圖至少應(yīng)有 （A）條邊才能確保是一

8、個(gè)連通圖。A.5B.6C.720、設(shè)哈夫曼樹中的葉子結(jié)點(diǎn)總數(shù)為D. 8m若用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該哈夫曼樹中總共有（B ）個(gè)空指針域。（D） 4m）方面的內(nèi)容。（A） 2m-1（B） 2m（C） 2m+121. 對(duì)一個(gè)算法的評(píng)價(jià)，不包括如下（ BA .健壯性和可讀性B.并行性 C.正確性D .時(shí)空復(fù)雜度22. 在帶有頭結(jié)點(diǎn)的單鏈表HL中，要向表頭插入一個(gè)由指針 p指向的結(jié)點(diǎn), 則執(zhí)行（A ）。A. p-n ext=HL-n ext; HL-n ext=p;B. p-n ext=HL; HL=p;C. p- next=HL; p=HL;D. HL=p; p- next=HL;23. 對(duì)線性表

9、，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？（ B ）A.經(jīng)常需要隨機(jī)地存取元素B.經(jīng)常需要進(jìn)行插入和刪除操作C.表中元素需要占據(jù)一片連續(xù)的存儲(chǔ)空間D.表中元素的個(gè)數(shù)不變24.(一個(gè)棧的輸入序列為 1 2 3,則下列序列中不可能是棧的C ）輸出序列的是A. 2 3 1C. 3 1 2B. 3 2 1D. 1 2 325.AOV網(wǎng)是一種（D ）。A .有向圖B.無(wú)向圖C.無(wú)向無(wú)環(huán)圖D .有向無(wú)環(huán)圖26.下面程序的時(shí)間復(fù)雜為（B)for (i=1 , s=0;i=n ; i+ ) t=1 ; for(j=1 ; j=i ; j+) t=t*j ; s=s+t; (A) O( n)(B) O(n 2)(C)

10、 O(n 3)(D) O(n 4)27.設(shè)某有向圖的鄰接表中有n個(gè)頭結(jié)點(diǎn)和m個(gè)表結(jié)點(diǎn)，則該圖中有(C )條有向邊。C(A) n(B) n-1(C) m(D) m-1有向圖m個(gè)表結(jié)點(diǎn)對(duì)應(yīng) m條邊，每條邊都是有向的28設(shè)連通圖 G 中的邊集 E=(a , b), (a, e), (a, c), (b, e), (e, d), (d, f), (f, c)，則從頂點(diǎn)a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點(diǎn)序列為( B )。(A) abedfc(B) acfebd(C) aebdfc(D) aedfcb29快速排序在最壞情況下的時(shí)間復(fù)雜度為(D )。A O(log2n)B O(nlog2n)C. 0(n)

11、D 0(n2)解析:各種排序算法性能比較如下:排序方法平均時(shí)間最好情況最壞情況輔助存儲(chǔ)穩(wěn)定性選擇誹序0代0(n2)0(1)不穩(wěn)定插人排序Otn2)0(n)0(n2)0(1)穩(wěn)定冒泡排序価)0(n2)0(n2)0(1)穩(wěn)定希爾排序0鄉(xiāng)-0(1)不穩(wěn)定快遠(yuǎn)掃E序0 (nlogn)0 (nlogrj0(n2)0(nlogn)不穩(wěn)定堆拄序0 (nlognjO(nlogn)0(nlogn)0(1)穩(wěn)定歸并排序0 (nlognj0 (nlogn)0(nlogn)0W穩(wěn)宦基數(shù)排序0(d(nhii)0(d(n+xd)0(d(n-hrd)O(rd)穩(wěn)定30.從二叉搜索樹中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為(C

12、)。2A. 0( n)B. 0(1) C. O(log2 n)D. O( n2)解析：如果二叉搜索樹為平衡二叉樹，查找一個(gè)元素的最壞時(shí)間復(fù)雜度為O(log 2n)。、填空題1、 數(shù)據(jù)的物理結(jié)構(gòu)主要包括順序存儲(chǔ) 和兩種情況。2、設(shè)順序線性表中有 n個(gè)數(shù)據(jù)元素，刪除第i個(gè)位置上的數(shù)據(jù)元素需要移動(dòng)表中n-1 個(gè)元素。則第i個(gè)位置上插入一個(gè)數(shù)據(jù)元素需要移動(dòng)表中n+1-i個(gè)元素3、 用一維數(shù)組存放完全二叉樹：ABCDEFGHI則中序遍歷該二叉樹的結(jié)點(diǎn)序列為()。4、設(shè)待排序的7記錄的排序碼為312 , 126, 272 , 226, 28, 165, 123，從小到大直接插入排序，一趟排序的結(jié)果是：()

13、。哨位排序碼312, 126. 272, 226 r 28, 165,123初始（）312, 126, 272,226,28*165.1231-2：（126）126. 312. 272,226,28,165,123i=3：（272）126, 272. 312，226.28,165,123i=4：（226）126, 226, 272.312p細(xì)165.123l=5i（20）2. 126. 226, 272, 312：165,123i=6：（165）28. 126.226. 272t312,123i=7：（123）28, 123. 126. 165. 226,272,312隼合黑合中田可兩個(gè)歆搗元

14、黑之間都沒(méi)有邏矩關(guān)蒸,絹奴形式唏訝. 踐性結(jié)構(gòu)裟性結(jié)構(gòu)中的結(jié)點(diǎn)按邏:ii關(guān)索依次排列形成一個(gè) 卷踞T 桶形第構(gòu)輔詐構(gòu)目育分支.層決特性r具形態(tài)有鬆勰目愍界中的梆. 圖杭結(jié)構(gòu)圖伏結(jié)構(gòu)沖的結(jié)點(diǎn)按邏輯關(guān)系互弔纏進(jìn).任何兩個(gè)結(jié)點(diǎn)都可収鄰按5.數(shù)據(jù)的邏輯結(jié)構(gòu)有四種基本形態(tài)，分別是 、和。6 一個(gè)算法的效率可分為 時(shí)間 率和空間 率。7. 在樹型結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒(méi)有 前趨結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的有且只有 _一 個(gè)前趨驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒(méi)有 后繼結(jié)點(diǎn)；其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn) 可以多個(gè)_。8. 對(duì)于一個(gè)有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)它為一棵 滿/完全二叉樹時(shí)具有最小高度，即為log2(N+1) ，當(dāng)它為一棵單支樹具有最大_

15、高度，即為n。9. 在一棵二叉排序樹上按 中序遍歷得到的結(jié)點(diǎn)序列是一個(gè)有序序列。10. 對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹，若一個(gè)結(jié)點(diǎn)的編號(hào)為 i(1 i 0,H(3H(6)=H(92,H(83JK2H(76h下圖所示的森林:(1) 求樹(a)的先根序列和后根序列;(2) 求森林先序序列和中序庫(kù)列； D 1-D 8Jb D, P Ar-F 10仏 Lb F, E 1-D-B 2&D, F, B, G A-G 28U，D, Ff Bf Gf E A-D-E 32仏 D, Ft B G, Er C A-D-B-C SR用5個(gè)帶權(quán)值3,2,4,5,1構(gòu)造的哈夫曼樹的帶權(quán)路徑長(zhǎng)度是（）解答；用5個(gè)帶釈值

16、3, 2# 4,5,1構(gòu)造的哈夫曼樹帶權(quán)路徑長(zhǎng)度=（丄+2）*計(jì)（3+4+5）*2=33廠EDE1A08880810B20050888C880830100D89080408E888808I81588808、設(shè)有一個(gè)輸入數(shù)據(jù)的序列是 46, 25, 78, 62, 12, 80 ，試畫出從空樹起，逐個(gè)輸 入各個(gè)數(shù)據(jù)而生成的二叉排序樹。四、程序填空1如下為二分查找的非遞歸算法，試將其填寫完整。Int Binsch(ElemType A ,int n,KeyType K)in t low=0;int high=n-1;while (low=high)int mid=；if (K=Amid.key) return mid;/查找成功，返回元素的下標(biāo)else if (Kdata=x) i+; p=p-next;/while, 出循環(huán)時(shí) i 中的值即為 x 結(jié)點(diǎn)個(gè)數(shù) return i;/CountX5、設(shè)計(jì)判斷兩個(gè)二叉樹是否相同的算法。 typedef struct node datatype data; struct node *lchild,*rchild; bitree;int judge