數(shù)據(jù)結(jié)構(gòu)附部分答案_第1頁
數(shù)據(jù)結(jié)構(gòu)附部分答案_第2頁
數(shù)據(jù)結(jié)構(gòu)附部分答案_第3頁
數(shù)據(jù)結(jié)構(gòu)附部分答案_第4頁
數(shù)據(jù)結(jié)構(gòu)附部分答案_第5頁
已閱讀5頁,還剩6頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

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 *

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論