數(shù)據(jù)結構附部分答案資料

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

2、ear指向隊列最后一個元素的后一個位置，則循環(huán)隊列中存放了n-1個元素，即循環(huán)隊列滿的條件是（ B ）。A . （rear+1）%n=front-1B.（rear+1）%n=frontC. （rear）% n=frontD.rear+1=fr ont4、 在一個單鏈表中，若刪除p所指結點的后續(xù)結點，則執(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答案耀折：解析：在一個單誰表中.若要刪除唏點的后續(xù)結點，只要將P的扌潤域指向P的后繼的后繼即可， 冃卩pT-門巳.

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

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 頁 共 11 頁9、 適用于折半查找的表的存儲方式及元素排列要求是（D ）A. 鏈式方式存儲，元素無序B. 鏈式存儲方式，元素有序C. 順序存儲方式，元素無序D. 順序存儲方式，元素有序10、 設一組初始記錄關鍵字序列為（345，253, 674, 924, 627），則用基數(shù)排序需要進行（C）趟的分配和回收才能使得初始關鍵字序列變成有序序列。A. 5B. 4C. 3D. 811 、棧和隊列的共同特點是 （A ）。A. 只允許在端

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

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

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

8、個連通圖。A.5B.6C.720、設哈夫曼樹中的葉子結點總數(shù)為D. 8m若用二叉鏈表作為存儲結構，則該哈夫曼樹中總共有（B ）個空指針域。（D） 4m）方面的內(nèi)容。（A） 2m-1（B） 2m（C） 2m+121. 對一個算法的評價，不包括如下（ BA .健壯性和可讀性B.并行性 C.正確性D .時空復雜度22. 在帶有頭結點的單鏈表HL中，要向表頭插入一個由指針 p指向的結點, 則執(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. 對線性表

9、，在下列哪種情況下應當采用鏈表表示？（ B ）A.經(jīng)常需要隨機地存取元素B.經(jīng)常需要進行插入和刪除操作C.表中元素需要占據(jù)一片連續(xù)的存儲空間D.表中元素的個數(shù)不變24.(一個棧的輸入序列為 1 2 3,則下列序列中不可能是棧的C ）輸出序列的是A. 2 3 1C. 3 1 2B. 3 2 1D. 1 2 325.AOV網(wǎng)是一種（D ）。A .有向圖B.無向圖C.無向無環(huán)圖D .有向無環(huán)圖26.下面程序的時間復雜為（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.設某有向圖的鄰接表中有n個頭結點和m個表結點，則該圖中有(C )條有向邊。C(A) n(B) n-1(C) m(D) m-1有向圖m個表結點對應 m條邊，每條邊都是有向的28設連通圖 G 中的邊集 E=(a , b), (a, e), (a, c), (b, e), (e, d), (d, f), (f, c)，則從頂點a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點序列為( B )。(A) abedfc(B) acfebd(C) aebdfc(D) aedfcb29快速排序在最壞情況下的時間復雜度為(D )。A O(log2n)B O(nlog2n)C. 0(n)

11、D 0(n2)解析:各種排序算法性能比較如下:排序方法平均時間最好情況最壞情況輔助存儲穩(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)定快遠掃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.從二叉搜索樹中查找一個元素時，其時間復雜度大致為(C

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

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細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隼合黑合中田可兩個歆搗元

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

15、高度，即為n。9. 在一棵二叉排序樹上按 中序遍歷得到的結點序列是一個有序序列。10. 對于一棵具有n個結點的完全二叉樹，若一個結點的編號為 i(1 i 0,H(3H(6)=H(92,H(83JK2H(76h下圖所示的森林:(1) 求樹(a)的先根序列和后根序列;(2) 求森林先序序列和中序庫列； 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個帶權值3,2,4,5,1構造的哈夫曼樹的帶權路徑長度是（）解答；用5個帶釈值

16、3, 2# 4,5,1構造的哈夫曼樹帶權路徑長度=（丄+2）*計（3+4+5）*2=33廠EDE1A08880810B20050888C880830100D89080408E888808I81588808、設有一個輸入數(shù)據(jù)的序列是 46, 25, 78, 62, 12, 80 ，試畫出從空樹起，逐個輸 入各個數(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;/查找成功，返回元素的下標else if (Kdata=x) i+; p=p-next;/while, 出循環(huán)時 i 中的值即為 x 結點個數(shù) return i;/CountX5、設計判斷兩個二叉樹是否相同的算法。 typedef struct node datatype data; struct node *lchild,*rchild; bitree;int judge