數據結構附部分答案

1、一、 選擇題1、下面關于線性表的敘述錯誤的是（ C ）。 A.線性表采用順序存儲必須占用一片連續(xù)的存儲空間B.線性表采用鏈式存儲不必占用一片連續(xù)的存儲空間C.線性表采用鏈式存儲便于插入和刪除操作的實現D.線性表采用順序存儲便于插入和刪除操作的實現2、棧是一種特殊的線性表，具有（ B ）性質 A先進先出 B.先進后出 C.后進后出 D.順序進出3、順序循環(huán)隊列中（數組大小為n），隊頭指示front指向隊列的第一個元素，隊尾指示rear指向隊列最后一個元素的后一個位置，則循環(huán)隊列中存放了n-1個元素，即循環(huán)隊列滿的條件是 （ B ）。 A(rear+1)%n=front-1 B.(rear+1)%

2、n=front C. (rear)%n=front D.rear+1=front 4、在一個單鏈表中，若刪除p所指結點的后續(xù)結點，則執(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、設某二叉樹中度數為0的結點數為N0，度數為1的結點數為Nl，度數為2的結點數為N2，則下列等式成立的是（ A ）。 A. N0=N2+1 B.N0=Nl+N2 C. N0=N1+1 D.N0=2N1+l6、設有6個

3、結點的無向圖，該圖至少應有（ D ）條邊才能確保是一個連通圖。A.8 B.6 C.7 D.57、設有向無環(huán)圖G中的有向邊集合E=<1，2>，<2，3>，<3，4>，<1，4>，則下列屬于該有向圖G的一種拓撲排序序列的是（ A ）。A.1，2，3，4 B. 2，3，4，1 C.1，4，2，3 D. 1，2，4，3 8、已知一個有向圖如下所示，則從頂點a出發(fā)進行深度優(yōu)先遍歷，不可能得到的DFS序列為（ A ）。A.a d b e f c B. a d c e f b C.a d c e b f D.a d e f b cbecfad 9、適用于折半查

4、找的表的存儲方式及元素排列要求是（ D ）A.鏈式方式存儲，元素無序 B.鏈式存儲方式，元素有序C.順序存儲方式，元素無序D.順序存儲方式，元素有序10、設一組初始記錄關鍵字序列為(345，253，674，924，627)，則用基數排序需要進行（ C ）趟的分配和回收才能使得初始關鍵字序列變成有序序列。 A. 5 B. 4 C. 3 D. 8 11、棧和隊列的共同特點是( A )。 A.只允許在端點處插入和刪除元素B.都是先進后出 C.都是先進先出D.沒有共同點12、用鏈接方式存儲的隊列，在進行插入運算時( D ). A. 僅修改頭指針 B. 頭、尾指針都要修改 C. 僅修改尾指針 D.頭、尾

5、指針可能都要修改13、以下數據結構中哪一個是非線性結構？( D ) A. 隊列 B. 棧 C. 線性表 D. 二叉樹14、樹最適合用來表示( C )。 A.有序數據元素 B.無序數據元素 C.元素之間具有分支層次關系的數據 D.元素之間無聯系的數據15、二叉樹的第k層的結點數最多為( D ). A 2k-1 B.2K+1 C.2K-1 D. 2k-116、設某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（ A ）。 (A) BADC(B) BCDA(C) CDAB(D) CBDA前序遍歷先訪問根，所以C為根，在中序遍歷中先訪問左子樹，再訪問根，最后訪問

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

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

8、 p->next=HL; HL=p;C. p->next=HL; p=HL; D. HL=p; p->next=HL;23.     對線性表，在下列哪種情況下應當采用鏈表表示？( B )A.經常需要隨機地存取元素 B.經常需要進行插入和刪除操作C.表中元素需要占據一片連續(xù)的存儲空間 D.表中元素的個數不變24.     一個棧的輸入序列為1 2 3，則下列序列中不可能是棧的輸出序列的是( C )A. 2 3 1B. 3 2 1C. 3 1 2 D. 1 2 325.  

9、60;  AOV網是一種（ 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(n2)(C) O(n3)(D) O(n4)27設某有向圖的鄰接表中有n個頭結點和m個表結點，則該圖中有（C ）條有向邊。 C(A) n(B) n-1(C) m(D) m-1有向圖 m個表結點對應m條邊，每條邊都是有向的28設連通圖G中的邊集E=(a，b)，(a，e)，(

10、a，c)，(b，e)，(e，d)，(d，f)，(f，c)，則從頂點a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點序列為（B ）。(A) abedfc(B) acfebd(C) aebdfc(D) aedfcb29.     快速排序在最壞情況下的時間復雜度為（D ）。AO(log2n) BO(nlog2n) C0(n) D0(n2)30. 從二叉搜索樹中查找一個元素時，其時間復雜度大致為( C )。A. O(n) B. O(1) C. O(log2n) D. O(n2)解析：如果二叉搜索樹為平衡二叉樹，查找一個元素的最壞時間復雜度為O(log2n)。二、 填空題

11、1、數據的物理結構主要包括 順序存儲 和 鏈式存儲 兩種情況。2、設順序線性表中有n個數據元素，刪除第i個位置上的數據元素需要移動表中 n-1 個元素。則第i個位置上插入一個數據元素需要移動表中 n+1-i 個元素3、用一維數組存放完全二叉樹：ABCDEFGHI，則中序遍歷該二叉樹的結點序列為（ ）。4、設待排序的7記錄的排序碼為312，126，272，226，28，165，123，從小到大直接插入排序，一趟排序的結果是：（ ）。5. 數據的邏輯結構有四種基本形態(tài)，分別是_、_、_和_。6 一個算法的效率可分為_時間_效率和_空間_效率。7. 在樹型結構中，樹根結點沒有_前趨_結點，其余每個結

12、點的有且只有_一_個前趨驅結點；葉子結點沒有_后繼_結點；其余每個結點的后續(xù)結點可以_多個_。 8. 對于一個有n個結點的二叉樹，當它為一棵_滿/完全_二叉樹時具有最小高度，即為_log2(N+1)_，當它為一棵單支樹具有_最大_高度，即為_n_。9. 在一棵二叉排序樹上按_中序_遍歷得到的結點序列是一個有序序列。 10. 對于一棵具有n個結點的完全二叉樹，若一個結點的編號為i(1in)，則它的左孩子結點的編號為_2i_，右孩子結點的編號為_2i+1_，雙親結點的編號為_i/2_。 11.    在線性表的散列存儲中，處理沖突的常用方法有_線性探測再散列_和_ 二

13、次探測再散列_兩種。12、若用鏈表存儲一棵二叉樹時，每個結點除數據域外，還有指向左孩子和右孩子的兩個指針。在這種存儲結構中，n個結點的二叉樹共有_2n_個指針域，其中有_n-1_個指針域是存放了地址，有_n+1_個指針是空指針。13.    在堆排序的過程中，對任一分支結點進行篩運算的時間復雜度為_O(log2n)_，整個堆排序過程的時間復雜度為_O(nlog2n)_。14.    在快速排序、堆排序、歸并排序中，_歸并_排序是穩(wěn)定的。15.        設無向圖

14、G中有n個頂點e條邊，所有頂點的度數之和為m，則e和m有_e=2m_關系。一個點的度數就等于該點連接的邊數,一條邊連接2個點,這兩個點的度數都要加1,也就是說,有一條邊總的度數就要加2,所以總度數是邊數的2倍16 已知一有向圖的鄰接表存儲結構如下：從頂點1出發(fā)，DFS遍歷的輸出序列是 (1，3，4，5，2) ，BFS遍歷的輸出序列是 (1，3，2，4，5)  三、應用題 1、假定有四個元素A, B, C, D依次進棧，進棧過程中允許出棧，請寫出所有可能的出棧序列。 進一個出一個，ABCD先進兩個，AB進，進C出C,進D出D，出B出A，CDBA進A進B，進C進D，出D出C出B出A，DC

15、BA下面的不解釋了，不明白你再問BCDA,BDCA,BCAD,BADC,BACD,前三個一起進CBAD,CBDA,CDBA第一個進去就出來ADCB,ACDB,ACBD一共14種例題圖3.2 有向圖用5個帶權值3,2,4,5,1構造的哈夫曼樹的帶權路徑長度是 （ ） 8、 設有一個輸入數據的序列是 46, 25, 78, 62, 12, 80 , 試畫出從空樹起，逐個輸入各個數據而生成的二叉排序樹。四、程序填空1、如下為二分查找的非遞歸算法，試將其填寫完整。Int Binsch(ElemType A ,int n,KeyType K)int low=0;int high=n-1;while (l

16、ow<=high)int mid=_；if (K=Amid.key) return mid; /查找成功，返回元素的下標 else if (K<mid.key) _; /在左子表上繼續(xù)查找 else _; /在右子表上繼續(xù)查找return -1; /查找失敗，返回-1答案： (low+high)/2           high=mid-1          

17、60;  low=mid+1 2循環(huán)隊列的插入。循環(huán)隊列數據結構定義如下：四、算法設計題 1、設計算法，在順序表test中插入元素a到第i個位置。要求考慮表滿情況。 2、設計算法，實現二叉樹的遞歸先序遍歷。 3、設計算法，實現n個整數的快速排序。 4、統計出單鏈表HL中結點的值等于給定值X的結點數。 int CountX(LNode* HL,ElemType x) int i=0; LNode* p=HL;/i為計數器 while(p!=NULL) if (P->data=x) i+; p=p->next; /while, 出循環(huán)時i中的值即為x結點個數 return i; /CountX5、   設計判斷兩個二叉樹是否相同的算法。 typedef struct node datatype data; struct node *lchild,*rchild; bitree;int judgebitree(bitree *bt1,bitree *