數(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-1 B.(rear+1)%

2、n=front C. (rear)%n=front D.rear+1=front 4、在一個(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ù)中度數(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+1 B.N0=Nl+N2 C. N0=N1+1 D.N0=2N1+l6、設(shè)有6個(gè)

3、結(jié)點(diǎn)的無(wú)向圖，該圖至少應(yīng)有（ D ）條邊才能確保是一個(gè)連通圖。A.8 B.6 C.7 D.57、設(shè)有向無(wú)環(huán)圖G中的有向邊集合E=<1，2>，<2，3>，<3，4>，<1，4>，則下列屬于該有向圖G的一種拓?fù)渑判蛐蛄械氖牵?A ）。A.1，2，3，4 B. 2，3，4，1 C.1，4，2，3 D. 1，2，4，3 8、已知一個(gè)有向圖如下所示，則從頂點(diǎn)a出發(fā)進(jìn)行深度優(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、找的表的存儲(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. 5 B. 4 C. 3 D. 8 11、棧和隊(duì)列的共同特點(diǎn)是( A )。 A.只允許在端點(diǎn)處插入和刪除元素B.都是先進(jìn)后出 C.都是先進(jìn)先出D.沒(méi)有共同點(diǎn)12、用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)( D ). A. 僅修改頭指針 B. 頭、尾指針都要修改 C. 僅修改尾指針 D.頭、尾

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

6、右子樹(shù)，所以在中序序列中，C前面的為左子樹(shù)，第二個(gè)訪問(wèn)的是左子樹(shù)的根A以此類推可得這樣的一棵二叉樹(shù)：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è)， A 1 B2 C3 D4分別是：55，64，46，10.H（K）= K%9，表示除以9的余數(shù)。由于地址重疊造成沖突，所以散列存儲(chǔ)時(shí)，通常還要有解決沖突的辦法，如線性探查法等等。19、設(shè)有6個(gè)結(jié)點(diǎn)的無(wú)向圖，該圖至少應(yīng)有( A )條邊才

7、能確保是一個(gè)連通圖。 A.5 B.6 C.7 D.820、設(shè)哈夫曼樹(shù)中的葉子結(jié)點(diǎn)總數(shù)為m，若用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該哈夫曼樹(shù)中總共有（ 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.

8、 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，則下列序列中不可能是棧的輸出序列的是( C )A. 2 3 1B. 3 2 1C. 3 1 2 D. 1 2 325.  

9、60;  AOV網(wǎng)是一種（ D ）。A有向圖 B無(wú)向圖 C無(wú)向無(wú)環(huán)圖 D有向無(wú)環(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) O(n2)(C) O(n3)(D) O(n4)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條邊，每條邊都是有向的28設(shè)連通圖G中的邊集E=(a，b)，(a，e)，(

10、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 ）。AO(log2n) BO(nlog2n) C0(n) D0(n2)30. 從二叉搜索樹(shù)中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為( C )。A. O(n) B. O(1) C. O(log2n) D. O(n2)解析：如果二叉搜索樹(shù)為平衡二叉樹(shù)，查找一個(gè)元素的最壞時(shí)間復(fù)雜度為O(log2n)。二、 填空題

11、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ù)組存放完全二叉樹(shù)：ABCDEFGHI，則中序遍歷該二叉樹(shù)的結(jié)點(diǎn)序列為（ ）。4、設(shè)待排序的7記錄的排序碼為312，126，272，226，28，165，123，從小到大直接插入排序，一趟排序的結(jié)果是：（ ）。5. 數(shù)據(jù)的邏輯結(jié)構(gòu)有四種基本形態(tài)，分別是_、_、_和_。6 一個(gè)算法的效率可分為_(kāi)時(shí)間_效率和_空間_效率。7. 在樹(shù)型結(jié)構(gòu)中，樹(shù)根結(jié)點(diǎn)沒(méi)有_前趨_結(jié)點(diǎn)，其余每個(gè)結(jié)

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

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

14、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,也就是說(shuō),有一條邊總的度數(shù)就要加2,所以總度數(shù)是邊數(shù)的2倍16 已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下：從頂點(diǎn)1出發(fā)，DFS遍歷的輸出序列是 (1，3，4，5，2) ，BFS遍歷的輸出序列是 (1，3，2，4，5)  三、應(yīng)用題 1、假定有四個(gè)元素A, B, C, D依次進(jìn)棧，進(jìn)棧過(guò)程中允許出棧，請(qǐng)寫(xiě)出所有可能的出棧序列。 進(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，DC

15、BA下面的不解釋了，不明白你再問(wèn)BCDA,BDCA,BCAD,BADC,BACD,前三個(gè)一起進(jìn)CBAD,CBDA,CDBA第一個(gè)進(jìn)去就出來(lái)ADCB,ACDB,ACBD一共14種例題圖3.2 有向圖用5個(gè)帶權(quán)值3,2,4,5,1構(gòu)造的哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度是 （ ） 8、 設(shè)有一個(gè)輸入數(shù)據(jù)的序列是 46, 25, 78, 62, 12, 80 , 試畫(huà)出從空樹(shù)起，逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉排序樹(shù)。四、程序填空1、如下為二分查找的非遞歸算法，試將其填寫(xiě)完整。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; /查找成功，返回元素的下標(biāo) 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)隊(duì)列的插入。循環(huán)隊(duì)列數(shù)據(jù)結(jié)構(gòu)定義如下：四、算法設(shè)計(jì)題 1、設(shè)計(jì)算法，在順序表test中插入元素a到第i個(gè)位置。要求考慮表滿情況。 2、設(shè)計(jì)算法，實(shí)現(xiàn)二叉樹(shù)的遞歸先序遍歷。 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è)二叉樹(shù)是否相同的算法。 typedef struct node datatype data; struct node *lchild,*rchild; bitree;int judgebitree(bitree *bt1,bitree *bt2) if (bt1=