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

1、選擇題1、下面關(guān)于線性表的敘述錯(cuò)誤的是（D ）。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ì)列的第rear 指向隊(duì)列最后一個(gè)元素的后一個(gè)位置，則循環(huán)隊(duì)列中存放了個(gè)元素，隊(duì)尾指示n-1 個(gè)元素，即循環(huán)隊(duì)列滿的條件是 （）。A . (rear+1)%n=front-1B.(rear+1)%n=

2、frontC. (rear)%n=frontD.rear+1=front4、在一個(gè)單鏈表中，若刪除所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行（A )。A . p->next=p->next->nextB. p=p->next;p->next->nextC.p->next=p->nextD.p=p->next->next5、設(shè)某二叉樹中度數(shù)為 0 的結(jié)點(diǎn)數(shù)為 N 0，度數(shù)為 1 的結(jié)點(diǎn)數(shù)為Nl，度數(shù)為 2 的結(jié)點(diǎn)數(shù)為N2，則下列等式成立的是（A ）。A. N0=N2+1B.N0=NI+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 ）。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)行深度優(yōu)先遍歷，不可能得到的DFS序列為（A ）。A.a d b e f cB. a d c e f b C.a d c e b fD.a d e f b c9、 適用于折半查找的表的存儲(chǔ)方式及元素排列要求是（D）A. 鏈?zhǔn)椒绞酱鎯?chǔ)，元素?zé)o序B. 鏈?zhǔn)酱鎯?chǔ)方式，元素有

4、序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ù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)？（ D ）A.隊(duì)列B.棧C.線性表D.二叉樹14、樹

5、最適合用來表示（ 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-lB.2K+116、設(shè)某棵二叉樹的中序遍歷序列為樹得到序列為（A ）o(A) BADC (B) BCDAC.2K-1D. 2k-1ABCD，前序遍歷序列為 CABD，則后序遍歷該二叉（C） CDAB（D） CBDA17、下列四種排序中（C ）的空間復(fù)雜度最大。（A）插入排序（B）冒泡排序 （C）堆排序（D）歸并排序18、對(duì)于線性表7，34，55，25，64，46，20，10 ）進(jìn)行散列存儲(chǔ)時(shí)，若選用=K %9作為散列函數(shù)，則散

6、列地址為1的元素有（D ）個(gè),A.1B. 2C. 319、設(shè)有6個(gè)結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有 （ AA.5B.6C.7D.8）條邊才能確保是一個(gè)連通圖。20、設(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 ） oA. p->next=HL->next;HL->next=p;

7、B. p->next=HL;HL=p;C. p-> next=HL; p=HL;D. HL=p; p-> next=HL;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，貝U下列序列中不可能是棧的輸出序列的是（C ）A. 2 3 1B. 3 2 1D. 1 2 3C. 3 1 225. AOV 網(wǎng)是一種（D ）A 有向圖B.無向圖26.下面程序的時(shí)間復(fù)雜為（B ）C.無向無環(huán)圖D .有向無環(huán)圖for (i=1 ,

8、 s=0 ; i<=n ;i+ )t=1 ; for(j=1 ; j<=i ; j+) t=t*j ; s=s+t ; (A) 0(n)(B) O(n 2)(C) O(n 3)(D) 0(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-128 .設(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

9、) aebdfc(D) aedfcb29. 快速排序在最壞情況下的時(shí)間復(fù)雜度為( D )。A. O(log 2n)B. O(nlog 2n)C. 0(n)D . 0(n2)30. 從二叉搜索樹中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為 (C )。A. O(n)B. O(1)C. O(log 2n)D. O(n 2)、填空題1、 數(shù)據(jù)的物理結(jié)構(gòu)主要包括順序儲(chǔ)存結(jié)構(gòu)和 鏈?zhǔn)絻?chǔ)存結(jié)構(gòu)兩種情況。2、 設(shè)順序線性表中有 n個(gè)數(shù)據(jù)元素，刪除第i個(gè)位置上的數(shù)據(jù)元素需要移動(dòng)表中n-i個(gè)元素。3、 用一維數(shù)組存放完全二叉樹：ABCDEFGHI，則中序遍歷該二叉樹的結(jié)點(diǎn)序列為HDIBEAFCG）。4、設(shè)待排序的 7 記

10、錄的排序碼為 312 ，126 ，272 ， 226 ，28 ， 165 ，123 ，從小到大直 接插入排序，一趟排序的結(jié)果是： （ 28 ， 126 ，272 ， 226 ，312 ，165 ，123 ）。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)可以 多_ 。_8. 對(duì)于一個(gè)有 n 個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)它為一棵 _完全 二叉樹時(shí)具有最小高度，即為 _log

11、 2n，當(dāng)它為一棵單支樹具有 _最大高度，即為 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ǔ)中 ， 處 理沖突的 常用 方法 有 開放定 址法和鏈?zhǔn)椒?兩_種_ 。12、若用鏈表存儲(chǔ)一棵二叉樹時(shí)，每個(gè)結(jié)點(diǎn)除數(shù)據(jù)域外，還有指向左孩子和右孩子 的兩個(gè)指針。在這種存儲(chǔ)結(jié)構(gòu)中， n 個(gè)結(jié)點(diǎn)的二叉樹共有 _2n個(gè)指針域，其中有n-1個(gè)指針域是存放了地

12、址，有 n+1個(gè)指針是空指針。13. 在堆排序的過程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為 (log 2n)，整個(gè)堆排序過程的時(shí)間復(fù)雜度為 _O(nlog 2n)。11、14.在快速排序、堆排序、歸并排序中， _3并一排序是穩(wěn)定的。12、15. 設(shè)無向圖G中有n個(gè)頂點(diǎn)e條邊，所有頂點(diǎn)的度數(shù)之和為 m ,則e和m有_m=2e關(guān)系。16. 已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下：從頂點(diǎn) 1出發(fā)，DFS遍歷的輸出序列是, BFS遍歷的輸出序列是圉的鄒接奏存福結(jié)枸三、應(yīng)用題1、假定有四個(gè)元素 A, B, C, D依次進(jìn)棧，進(jìn)棧過程中允許出棧，請(qǐng)寫出所有可能的出棧序 列。2、設(shè)散列表的地址范圍是0.4 。

13、現(xiàn)采用除余法為散列函數(shù)H ( key ) = key MOD 5, 并采用拉鏈法解決地址沖突，請(qǐng)畫出元素1 ,13，20, 5，14，33依次插入散列表的存儲(chǔ)結(jié)構(gòu)。3、下圖所示的森林：(1) 將樹(a)轉(zhuǎn)換為相應(yīng)的二叉樹(2) 將二叉樹(b)轉(zhuǎn)換為森林；4、有向圖如下所示。應(yīng)用Dijkstra算法,求源點(diǎn)1到其它點(diǎn)的最短路徑。圖3.2 有向圖迭代Sudist2dist3dist4dist5初始12345 有5個(gè)權(quán)值5,3,7,11,4，試構(gòu)造一棵有5個(gè)葉子結(jié)點(diǎn)的哈夫曼樹并計(jì)算哈夫曼 樹的帶權(quán)路徑長度 WPL。6、請(qǐng)畫出下圖的鄰接表。（5 分）7、設(shè)有有向圖G，要求給出用普里姆算法構(gòu)造的最小生成

14、樹。8、 設(shè)有一個(gè)輸入數(shù)據(jù)的序列是 46, 25, 78, 62, 12, 80 , 試畫出從空樹起，逐個(gè) 輸入各個(gè)數(shù)據(jù)而生成的二叉排序樹。四、程序填空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;else if (K<mid.key)/ 查找成功，返回元素的下標(biāo)/ 在左子表上繼續(xù)查else/ 在右子表上繼續(xù)查找return -1;/ 查找失敗，返回 -1

15、2循環(huán)隊(duì)列的插入。 循環(huán)隊(duì)列數(shù)據(jù)結(jié)構(gòu)定義如下：typedef int datatype;typedef struct datatype aMAXSIZE; int front;in t rear;seque nce_queue;void in sert_seque nce_cqueue(seque nce_queuesq,datatype x) if(.)");exit(1);pri ntf("n順序循環(huán)隊(duì)列是滿的！無法進(jìn)行插入操作！sq->asq->rear=x;sq->rear= 3、求第n項(xiàng)Fibonacci級(jí)數(shù)的值1 n=1Fib ona(n)=1n=2Fibo na( n-1)+ Fib on a( n-2)n>2int Fib ona ( int n ) int m;if () return (1);else if (n= =2) retur n(1);else m=return (m);4、以下 程 序是后序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分(樹結(jié)構(gòu)中，左、右指針域分別為left和right ,數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn))。void fostorder (struct BTreeNode *BT) if (BT!=NULL