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

1、一、 選擇題1、下面關(guān)于線性表的敘述錯誤的是（ C ）。 A.線性表采用順序存儲必須占用一片連續(xù)的存儲空間B.線性表采用鏈式存儲不必占用一片連續(xù)的存儲空間C.線性表采用鏈式存儲便于插入和刪除操作的實現(xiàn)D.線性表采用順序存儲便于插入和刪除操作的實現(xiàn)2、棧是一種特殊的線性表，具有（ B ）性質(zhì) A先進先出 B.先進后出 C.后進后出 D.順序進出3、順序循環(huán)隊列中（數(shù)組大小為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所指結(jié)點的后續(xù)結(jié)點，則執(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é)點數(shù)為N0，度數(shù)為1的結(jié)點數(shù)為Nl，度數(shù)為2的結(jié)點數(shù)為N2，則下列等式成立的是（ A ）。 A. N0=N2+1 B.N0=Nl+N2 C. N0=N1+1 D.N0=2N1+l6、設(shè)有6個

3、結(jié)點的無向圖，該圖至少應(yīng)有（ D ）條邊才能確保是一個連通圖。A.8 B.6 C.7 D.57、設(shè)有向無環(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.鏈式方式存儲，元素?zé)o序 B.鏈式存儲方式，元素有序C.順序存儲方式，元素?zé)o序D.順序存儲方式，元素有序10、設(shè)一組初始記錄關(guān)鍵字序列為(345，253，674，924，627)，則用基數(shù)排序需要進行（ C ）趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。 A. 5 B. 4 C. 3 D. 8 11、棧和隊列的共同特點是( A )。 A.只允許在端點處插入和刪除元素B.都是先進后出 C.都是先進先出D.沒有共同點12、用鏈接方式存儲的隊列，在進行插入運算時( D ). A. 僅修改頭指針 B. 頭、尾指針都要修改 C. 僅修改尾指針 D.頭、尾

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

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

7、能確保是一個連通圖。 A.5 B.6 C.7 D.820、設(shè)哈夫曼樹中的葉子結(jié)點總數(shù)為m，若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中總共有（ B ）個空指針域。 (A) 2m-1(B) 2m(C) 2m+1(D) 4m21.     對一個算法的評價，不包括如下（ B ）方面的內(nèi)容。 A健壯性和可讀性 B并行性 C正確性 D時空復(fù)雜度22.     在帶有頭結(jié)點的單鏈表HL中，要向表頭插入一個由指針p指向的結(jié)點，則執(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.     對線性表，在下列哪種情況下應(yīng)當采用鏈表表示？( B )A.經(jīng)常需要隨機地存取元素 B.經(jīng)常需要進行插入和刪除操作C.表中元素需要占據(jù)一片連續(xù)的存儲空間 D.表中元素的個數(shù)不變24.     一個棧的輸入序列為1 2 3，則下列序列中不可能是棧的輸出序列的是( C )A. 2 3 1B. 3 2 1C. 3 1 2 D. 1 2 325.  

9、60;  AOV網(wǎng)是一種（ D ）。A有向圖 B無向圖 C無向無環(huán)圖 D有向無環(huán)圖26.     下面程序的時間復(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(n2)(C) O(n3)(D) O(n4)27設(shè)某有向圖的鄰接表中有n個頭結(jié)點和m個表結(jié)點，則該圖中有（C ）條有向邊。 C(A) n(B) n-1(C) m(D) m-1有向圖 m個表結(jié)點對應(yīng)m條邊，每條邊都是有向的28設(shè)連通圖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.     快速排序在最壞情況下的時間復(fù)雜度為（D ）。AO(log2n) BO(nlog2n) C0(n) D0(n2)30. 從二叉搜索樹中查找一個元素時，其時間復(fù)雜度大致為( C )。A. O(n) B. O(1) C. O(log2n) D. O(n2)解析：如果二叉搜索樹為平衡二叉樹，查找一個元素的最壞時間復(fù)雜度為O(log2n)。二、 填空題

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

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

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

14、G中有n個頂點e條邊，所有頂點的度數(shù)之和為m，則e和m有_e=2m_關(guān)系。一個點的度數(shù)就等于該點連接的邊數(shù),一條邊連接2個點,這兩個點的度數(shù)都要加1,也就是說,有一條邊總的度數(shù)就要加2,所以總度數(shù)是邊數(shù)的2倍16 已知一有向圖的鄰接表存儲結(jié)構(gòu)如下：從頂點1出發(fā)，DFS遍歷的輸出序列是 (1，3，4，5，2) ，BFS遍歷的輸出序列是 (1，3，2，4，5)  三、應(yīng)用題 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個帶權(quán)值3,2,4,5,1構(gòu)造的哈夫曼樹的帶權(quán)路徑長度是 （ ） 8、 設(shè)有一個輸入數(shù)據(jù)的序列是 46, 25, 78, 62, 12, 80 , 試畫出從空樹起，逐個輸入各個數(shù)據(jù)而生成的二叉排序樹。四、程序填空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)隊列數(shù)據(jù)結(jié)構(gòu)定義如下：四、算法設(shè)計題 1、設(shè)計算法，在順序表test中插入元素a到第i個位置。要求考慮表滿情況。 2、設(shè)計算法，實現(xiàn)二叉樹的遞歸先序遍歷。 3、設(shè)計算法，實現(xiàn)n個整數(shù)的快速排序。 4、統(tǒng)計出單鏈表HL中結(jié)點的值等于給定值X的結(jié)點數(shù)。 int CountX(LNode* HL,ElemType x) int i=0; LNode* p=HL;/i為計數(shù)器 while(p!=NULL) if (P->data=x) i+; p=p->next; /while, 出循環(huán)時i中的值即為x結(jié)點個數(shù) return i; /CountX5、   設(shè)計判斷兩個二叉樹是否相同的算法。 typedef struct node datatype data; struct node *lchild,*rchild; bitree;int judgebitree(bitree *bt1,bitree *