數(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)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ì)尾指示rear指向隊(duì)列最后一個(gè)元素的后一個(gè)位置，則循環(huán)隊(duì)列中存放了n-1 個(gè)元素，即循環(huán)隊(duì)列滿的條件是（B）。A(rear+1)%n=front-1B.(rear+1)%n=f

2、rontC. (rear)%n=frontD.rear+1=front4、在一個(gè)單鏈表中，若刪除p 所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行（A）。A p->next=p->next->next B. p=p->next;p->next->next C.p->next=p->next D.p=p->next->next5、設(shè)某二叉樹中度數(shù)為0 的結(jié)點(diǎn)數(shù)為N0，度數(shù)為 1 的結(jié)點(diǎn)數(shù)為Nl ，度數(shù)為 2 的結(jié)點(diǎn)數(shù)為N2，則下列等式成立的是（A）。A. N0=N2+1B.N0=Nl+N2C. N0=N1+1D.N0=2N1+l6、設(shè)有 6 個(gè)結(jié)點(diǎn)的無向圖

3、，該圖至少應(yīng)有（D）條邊才能確保是一個(gè)連通圖。A.8B.6C.7D.57、設(shè)有向無環(huán)圖G中的有向邊集合E=<1， 2>，<2，3>，<3，4>，<1，4> ，則下列屬于該有向圖 G的一種拓?fù)渑判蛐蛄械氖牵ˋ）。A.1 ，2，3，4B. 2，3，4，1C.1，4，2，3D. 1，2，4，38、已知一個(gè)有向圖如下所示，則從頂點(diǎn)a 出發(fā)進(jìn)行深度優(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 cb.專業(yè) .整理 .acefd下載可編輯9、適用于折半查找的表的

4、存儲(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. 只允許在端點(diǎn)處插入和刪除元素B. 都是先進(jìn)后出C. 都是先進(jìn)先出D. 沒有共同點(diǎn)12、用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)(D ).A.僅修改頭指針B.頭、尾指針都要修改C.僅修改尾指針D.頭、尾指針可能都要修改13、以下數(shù)據(jù)

5、結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)？(D )A.隊(duì)列B.棧C.線性表D.二叉樹14、樹最適合用來表示( C)。A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)15、二叉樹的第k 層的結(jié)點(diǎn)數(shù)最多為 (D ).A 2k-1B.2K+1C.2K-1D. 2 k-116、設(shè)某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（A ）。(A) BADC(B) BCDA(C) CDAB(D) CBDA前序遍歷先訪問根，所以C 為根，在中序遍歷中先訪問左子樹，再訪問根，最后訪問右子樹，所以在中序序列中，C 前面的為左子樹，第二個(gè)訪問的是左子

6、樹的根A 以此類推可得這樣的一棵二叉樹：.專業(yè) .整理 .下載可編輯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è)，A1B2C3D4分別是： 55， 64， 46， 10.H（ K）= K%9，表示除以9 的余數(shù)。由于地址重疊造成沖突，所以散列存儲(chǔ) 時(shí)，通常還要有解決沖突的辦法，如線性探查法等等。19、設(shè)有 6 個(gè)結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有(A)條邊才能確保是一個(gè)連通圖

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

8、L;23. 對(duì)線性表，在下列哪種情況下應(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.231B.321C.312D.12325. AOV網(wǎng)是一種（ D ）。A有向圖B無向圖C無向無環(huán)圖D有向無環(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)

9、 O(n 2)(C) 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條邊，每條邊都是有向的.專業(yè) .整理 .下載可編輯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

10、 ）。AO(log 2 n)BO(nlog 2n)C0(n)D 0(n 2 )30. 從二叉搜索樹中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為 ( C ) 。A. O(n)B. O(1)C. O(log2n)D. O(n2 )解析：如果二叉搜索樹為平衡二叉樹，查找一個(gè)元素的最壞時(shí)間復(fù)雜度為O(log 2 n) 。二、 填空題1、數(shù)據(jù)的物理結(jié)構(gòu)主要包括順序存儲(chǔ)和鏈?zhǔn)酱鎯?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)序列

11、為（）。4、設(shè)待排序的7 記錄的排序碼為312 ， 126，272，226，28，165， 123 ，從小到大直接插入排序，一趟排序的結(jié)果是：（）。.專業(yè) .整理 .下載可編輯5.數(shù)據(jù)的邏輯結(jié)構(gòu)有四種基本形態(tài)，分別是_、_、 _和 _。6 一個(gè)算法的效率可分為 _時(shí)間 _效率和 _空間 _效率。7. 在樹型結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有 _前趨 _結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的有且只有_一_個(gè)前趨驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有 _后繼 _結(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)它為一棵單支樹具有

12、_最大 _高度，即為 _n_。9. 在一棵二叉排序樹上按 _中序 _遍歷得到的結(jié)點(diǎn)序列是一個(gè)有序序列。10. 對(duì)于一棵具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹，若一個(gè)結(jié)點(diǎn)的編號(hào)為 i(1 i n) ，則它的左孩子結(jié)點(diǎn)的編號(hào)為 _2i _，右孩子結(jié)點(diǎn)的編號(hào)為 _2i+1 _，雙親結(jié)點(diǎn)的編號(hào)為 _i/2 _。11. 在線性表的散列存儲(chǔ)中，處理沖突的常用方法有 _線性探測(cè)再散列 _和_二次探測(cè)再散列 _兩種。12、若用鏈表存儲(chǔ)一棵二叉樹時(shí)，每個(gè)結(jié)點(diǎn)除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個(gè)指針。在這種存儲(chǔ)結(jié)構(gòu)中，n 個(gè)結(jié)點(diǎn)的二叉樹共有 _2n_個(gè)指針域，其中有 _n-1 _個(gè)指針域是存放了地址，有_n+1_個(gè)指針

13、是空指針。13. 在堆排序的過程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為_O(log2n) _，整個(gè)堆排序過程的時(shí)間復(fù)雜度為_O(nlog2n)_ _。14.在快速排序、堆排序、歸并排序中，_歸并 _排序是穩(wěn)定的。.專業(yè) .整理 .下載可編輯15.設(shè)無向圖 G中有 n 個(gè)頂點(diǎn) e 條邊，所有頂點(diǎn)的度數(shù)之和為m，則 e 和 m有_e=2m_關(guān)系。一個(gè)點(diǎn)的度數(shù)就等于該點(diǎn)連接的邊數(shù) , 一條邊連接 2 個(gè)點(diǎn) , 這兩個(gè)點(diǎn)的度數(shù)都要加 1, 也就是說 , 有一條邊總的度數(shù)就要加 2, 所以總度數(shù)是邊數(shù)的 2 倍16 已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下：從頂點(diǎn)1 出發(fā)， DFS遍歷的輸出序列是(1 ，

14、3， 4，5， 2)，BFS遍歷的輸出序列是(1 ， 3， 2， 4， 5)三、應(yīng)用題1、假定有四個(gè)元素A, B, C, D依次進(jìn)棧，進(jìn)棧過程中允許出棧，請(qǐng)寫出所有可能的出棧序列。進(jìn)一個(gè)出一個(gè)，ABCD先進(jìn)兩個(gè)， AB進(jìn)，進(jìn) C出 C, 進(jìn) D 出 D，出 B 出 A，CDBA進(jìn) A進(jìn) B，進(jìn) C進(jìn) D，出 D出 C出 B出 A，DCBA下面的不解釋了，不明白你再問BCDA,BDCA,BCAD,BADC,BACD,前三個(gè)一起進(jìn)CBAD,CBDA,CDBA第一個(gè)進(jìn)去就出來ADCB,ACDB,ACBD一共 14種例題.專業(yè) .整理 .下載可編輯.專業(yè) .整理 .下載可編輯圖3.2 有向圖用 5 個(gè)

15、帶權(quán)值 3,2,4,5,1構(gòu)造的哈夫曼樹的帶權(quán)路徑長(zhǎng)度是（）.專業(yè) .整理 .下載可編輯8、 設(shè)有一個(gè)輸入數(shù)據(jù)的序列是 46, 25, 78, 62, 12, 80 ,試畫出從空樹起，逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉排序樹。.專業(yè) .整理 .下載可編輯四、程序填空1、如下為二分查找的非遞歸算法，試將其填寫完整。 Int Binsch(ElemType A ,int n,KeyType K) int low=0;int high=n-1;while (low<=high)int mid=_ ；if (K=Amid.key) return mid;/查找成功，返回元素的下標(biāo)else if (K&

16、lt;mid.key)_;/在左子表上繼續(xù)查找else _;/在右子表上繼續(xù)查找return -1;/查找失敗，返回 -1答案 ：(low+high)/2high=mid-1low=mid+12循環(huán)隊(duì)列的插入。循環(huán)隊(duì)列數(shù)據(jù)結(jié)構(gòu)定義如下：四、算法設(shè)計(jì)題1、設(shè)計(jì)算法，在順序表test中插入元素a 到第 i 個(gè)位置。要求考慮表滿情況。.專業(yè) .整理 .下載可編輯2、設(shè)計(jì)算法，實(shí)現(xiàn)二叉樹的遞歸先序遍歷。3、設(shè)計(jì)算法，實(shí)現(xiàn)n 個(gè)整數(shù)的快速排序。4、統(tǒng)計(jì)出單鏈表HL中結(jié)點(diǎn)的值等于給定值X 的結(jié)點(diǎn)數(shù)。int CountX(LNode* HL,ElemType x) int i=0; LNode* p=HL;/i為計(jì)數(shù)器while(p!=NULL) if (P->data=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 judgebitree(bitree *bt1,bitree *bt2) if (bt1=0 && b