(完整word版)2017《數(shù)據(jù)結構》期末考試試題及答案(2)

1、2017數(shù)據(jù)結構期末考試試題及答案數(shù)據(jù)結構期末考試試題及答案12.試題 1 答案 7.數(shù)據(jù)結構期末考試試題及答案29.試題 2 答案 1.4.數(shù)據(jù)結構期末考試試題及答案31.6試題 3 答案 2.1.第 3 頁 共 23 頁數(shù)據(jù)結構期末考試試題及答案 1單選題（每題 2 分，共 20 分）1. 棧和隊列的共同特點是 （）。A. 只允許在端點處插入和刪除元素B. 都是先進后出C. 都是先進先出D. 沒有共同點2. 用鏈接方式存儲的隊列，在進行插入運算時 （）.A. 僅修改頭指針B. 頭、尾指針都要修改C. 僅修改尾指針D .頭、尾指針可能都要修改3. 以下數(shù)據(jù)結構中哪一個是非線性結構？ （）A.

2、 隊列B. 棧C. 線性表D. 二叉樹4. 設有一個二維數(shù)組Amn，假設A00存放位置在644（io）, A22存放位置在 676（10），每個元素占一個空間，表示用 10 進制表示。問 A33 （10）存放在什么位置？腳注 （10）5.A688B678C692D 696樹最適合用來表示 （）。A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素6.C.元素之間具有分支層次關系的數(shù)據(jù)D .元素之間無聯(lián)系的數(shù)據(jù)二叉樹的第 k 層的結點數(shù)最多為 （ ）.A2k-1B.2K+1C.2K-1D. 2k-17.若有18個元素的有序表存放在一維數(shù)組 A19中，第一個元素放A1中,現(xiàn)進行二分查找，則查找 A 3的比較序列的下標

3、依次為（A. 1 ，2，3B. 9，5，2， 3C. 9，5，3D. 9，4，2， 38. 對n個記錄的文件進行快速排序，所需要的輔助存儲空間大致為A. O（1）B. O（n）C. O（ 1 og2n）D. O（n2）9. 對于線性表（ 7， 34， 55， 25， 64， 46， 20， 10）進行散列存儲時，若選 用 H（K）=K %9 作為散列函數(shù)，則散列地址為 1 的元素有（ ）個，A1B2C3D410. 設有6個結點的無向圖，該圖至少應有 ()條邊才能確保是一個連通圖。A.5 B.6 C.7 D.8二、填空題(每空 1 分，共 26 分)1. 通常從四個方面評價算法的質量： 、 、

4、和2. 一個算法的時間復雜度為(n3+n2log2n+14n)/n2,其數(shù)量級表示為。3. 假定一棵樹的廣義表表示為 A (C, D (E, F, G), H (I, J),則樹中所含的結點數(shù)為 個，樹的深度為 樹的度為 。4. 后綴算式9 2 3 +- 10 2 / -的值為 中綴算式(3+4X)-2Y/3對應的后綴算式為 。_5. 若用鏈表存儲一棵二叉樹時， 每個結點除數(shù)據(jù)域外， 還有指向左孩子和右孩子的兩個指針。在這種存儲結構中，n個結點的二叉樹共有 指針域，其中有個指針域是存放了地址，有 個指針是空指針。6. 對于一個具有 n 個頂點和 e 條邊的有向圖和無向圖，在其對應的鄰接表中，所

5、含邊結點分別有 個和 個。7. AOV 網(wǎng)是一種 的圖。8. 在一個具有 n 個頂點的無向完全圖中，包含有 條邊，在一個具有 n個頂點的有向完全圖中，包含有 條邊。9. 假定一個線性表為 (12,23,74,55,63,40)，若按 Key % 4 條件進行劃分， 使得同一 余 數(shù) 的 元 素 成 為 一 個 子 表 ， 則 得 到 的 四 個 子 表 分 別 為和。10. 向一棵B_樹插入元素的過程中，若最終引起樹根結點的分裂，貝慚樹比原樹的高度。11. 在堆排序的過程中，對任一分支結點進行篩運算的時間復雜度為 整個堆排序過程的時間復雜度為 。12. 在快速排序、堆排序、歸并排序中， 卡序是

6、穩(wěn)定的。三、運算題(每題6分，共24分)1. 在如下數(shù)組A中鏈接存儲了一個線性表，表頭指針為A 0.next，試寫出該線性表。605078903440357204101234567Adatan ext2. 請畫出圖10的鄰接矩陣和鄰接表3. 已知一個圖的頂點集 V和邊集E分別為： V=1,2,3,4,5,6,7;E=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25;用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。4. 畫出向小根堆中加入數(shù)據(jù)4,

7、 2, 5, 8, 3時，每加入一個數(shù)據(jù)后堆的變化第4頁共23頁四、閱讀算法(每題 7 分，共 14分)1. LinkList mynote(LinkList L)/L 是不帶頭結點的單鏈表的頭指針if(L&&L->next)q=L ；L=L >next； p=L ；S1：while(p >next) p=p >next；S2：p>next=q； q >next=NULL ；return L ；請回答下列問題：(1) 說明語句 S1 的功能；(2) 說明語句組 S2 的功能；(3) 設鏈表表示的線性表為(ai,a2,an),寫出算法執(zhí)行后的返

8、回值所表 示的線性表。2. void ABC(BTNode * BT) if BT ABC (BT->left);ABC (BT->right); cout<<BT->data<<' ' 該算法的功能是：第 # 頁 共 23 頁五、算法填空（共 8 分）二叉搜索樹的查找 遞歸算法 :bool Find(BTreeNode* BST,ElemType& item)if (BST=NULL)return false; /查找失敗else if (item=BST->data) item=BST->data;/查找成功 r

9、eturn ;else if(item<BST->data)return Find(,item);else return Find(,item);/if六、 編寫算法(共 8 分) 統(tǒng)計出單鏈表 HL 中結點的值等于給定值 X 的結點數(shù)。int CountX(LNode* HL,ElemType x)第 7 頁 共 23 頁試題1答案5.2nn-1n+16.2e7.有向無回路8.n(n-1)/2n(n_1)9.(12, 40)(74)(23,55, 63)10.增加111.O(log2 n)0(nlog 2n)12.歸并1.線性表為:(78,50：,40,60, 34, 90)01

10、1 10101 01110 11101 012.鄰接矩陣:011 10鄰接表如圖11所示：運算題（每題6分，共24分）4A圖11、1.A單選題（每題2分，共20分）2.D3.D4.C5.C6.D7.D8.C、填空題（每空1分，共26分）1.正確性易讀性強壯性咼效率2.O(n)3.933-13 4 X * + 2 Y * 3 / -4.9.D10.A四、3.用克魯斯卡爾算法得到的最小生成樹為:(1,2)3,(4,6)4,(1,3)5,(1,4)8,1.2.(2,5)10,(4,7)20圖12閱讀算法(每題7分，共14分)(1)查詢鏈表的尾結點(2)將第一個結點鏈接到鏈表的尾部，作為新的尾結點(3

11、)返回的線性表為(a2,a3,an,a1)遞歸地后序遍歷鏈式存儲的二叉樹。五、算法填空(每空2分，共8分)true BST->leftBST->right六、編寫算法(8分)int CountX(LNode* HL,ElemType x) int i=0; LNode* p=HL;/i為計數(shù)器while(p!=NULL) if (P->data=x) i+;p=p->n ext;/while,出循環(huán)時i中的值即為x結點個數(shù) return i;/Cou ntX第9頁共23頁數(shù)據(jù)結構期末考試試題及答案2一、 單選題（每小題2分，共8分）1、在一個長度為n的順序線性表中順序查

12、找值為x的元素時，查找成功時的平均查找長度（即x與元素的平均比較次數(shù)，假定查找每個元素的概率都相等）為（）。AnB n/2C（n+1）/2D（n-1）/22、在一個單鏈表中，若q所指結點是p所指結點的前驅結點，若在q與p之間插入 一個s所指的結點，則執(zhí)行（）。As link=p f link;plink=s ；Bp lin k=s;s lin k=q;Cplin k=slink;s lin k=p;Dq lin k=s;s link =p;3、棧的插入和刪除操作在（）進行。A棧頂B棧底C任意位置D指定位置4、由權值分別為11, 8, 6,2, 5的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為（

13、）A 24B 71C 48D53填空題（每空1分，共32分）1、 數(shù)據(jù)的邏輯結構被分為 、和四種。2、 一種抽象數(shù)據(jù)類型包括和個部分。3、 在下面的數(shù)組a中鏈接存儲著一個線性表，表頭指針為ao.next，則該線性表為。605642387425437620廠data n ext0123456784、 在以HL為表頭指針的帶表頭附加結點的單鏈表和循環(huán)單鏈表中，判斷鏈表為空的條件分別為和。5、用具有n個元素的一維數(shù)組存儲一個循環(huán)隊列，則其隊首指針總是指向隊首元素的，該循環(huán)隊列的最大長度為 。6、當堆棧采用順序存儲結構時，棧頂元素的值可用 表示；當堆棧采用鏈接存儲結構時，棧頂元素的值可用 表示。7、一

14、棵高度為 5 的二叉樹中最少含有 個結點，最多含有 個結點；一棵高度為 5 的理想平衡樹中，最少含有 個結點，最多含有個結點。8、在圖的鄰接表中，每個結點被稱為 ，通常它包含三個域：.曰曰-曰一是 ；二是 ；三是 。9、在一個索引文件的索引表中，每個索引項包含對應記錄的 和兩項數(shù)據(jù)。10、假定一棵樹的廣義表表示為 A（B（C，D（ E，F(xiàn)，G），H（I，J）， 則樹 中所 含的結點數(shù)為 個，樹的深度為 ,樹的度為, 結點 H 的雙親結點為 ,孩子結點為 。11、在堆排序的過程中，對任一分支結點進行篩運算的時間復雜度為 ,整個堆排序過程的時間復雜度為 。12、在對m階的B_樹插入元素的過程中，每

15、向一個結點插入一個索引項（葉 子結點中的索引項為關鍵字和空指針）后，若該結點的索引項數(shù)等于 個，則必須把它分裂為 個結點。運算題（每小題 6 分，共 24 分）1、已知一組記錄的排序碼為（ 46， 79， 56， 38， 40， 80, 95， 24），寫出對 其進行快速排序的每一次劃分結果。第13頁共23頁2、一個線性表為 B= （12, 23, 45, 57, 20, 03, 78, 31, 15, 36）,設散列表為HT0.12，散列函數(shù)為H （key） = key % 13并用線性探查法解決沖 突，請畫出散列表，并計算等概率情況下查找成功的平均查找長度。3、已知一棵二叉樹的前序遍歷的結

16、果序列是ABECKFGHIJ，中序遍歷的結果是 EBCDAFHIGJ，試寫出這棵二叉樹的后序遍歷結果。4、已知一個圖的頂點集 V各邊集G如下：V = 0 , 1, 2, 3, 4, 5, 6, 7, 8, 9；E = （0 , 1）,（0 , 4）,（ 1, 2）,（ 1 , 7）,（2 , 8）,（3 , 4）,（3 , 8）,（5 , 6）,（5 , 8）,（5 , 9）,（6 , 7）,（7 , 8）,（8 , 9）當它用鄰接矩陣表示和鄰接表表示時，分別寫出從頂點V。出發(fā)按深度優(yōu)先搜索遍歷得到的頂點序列和按廣度優(yōu)先搜索遍歷等到的頂點序列。假定每個頂點鄰接表中的結點是按頂點序號從大到小的次

17、序鏈接的。圖深度優(yōu)先序列廣度優(yōu)先序列鄰接矩陣表示時鄰接表表示時四、閱讀算法，回答問題（每小題 8分，共16分）1、假定從鍵盤上輸入一批整數(shù),依次為：78 63 45 30 91 34 - 1，請 寫出輸出結果。# in elude < iostream.h># in elude < stdlib.h >const int staekmaxsize = 30;typedef int elemtype;struct stack elemtype stack stackmaxsize;int top;# include void“stack.h”main ( ) stack

18、a; initstack(a); int x; cin >>x; while (x! = -1) push (a, x ); cin >>x;while (!stackempty (a) cout <<pop (a) <<” cout <<end1;該算法的輸出結果為：2、閱讀以下二叉樹操作算法，指出該算法的功能。Template <calss type > void BinTree <Type> ： unknown (BinTreeNode<Type>*t) BinTreeNode< Typ

19、e> *p =t, *temp;if (p!=NULL) temp = p leftchild; pf leftchild = p f rightchild; pfrightchild = temp; unknown(pfleftchild); undnown(pfrightchild); 該算法的功能是： 五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容(10 分)對順序存儲的有序表進行二分查找的遞歸算法 。int Binsch( ElemType A ,int low ,int high,KeyType K )if (low <= high)int mid = 1 if ( K=

20、= A mid .key ) return mid;else if ( K < Amid.key) return 2else return 3elsereturn 4六、編寫算法( 10 分)即若原單鏈表中,a1 o編寫算法， 將一個結點類型為 Lnode 的單鏈表按逆序鏈接， 存儲元素的次序為ai,a-i, an,則逆序鏈接后變?yōu)?an, eVoid contrary (Lnode * & H L)第 i3 頁 共 23 頁試題2答案、單選題（每小題 2分，共8分）題號1234答案CDAB二、填空題（每空1分，共32分）1:集合、線性、樹、圖；2:數(shù)據(jù)描述、操作聲名；3：（38

21、, 56， 25， 60， 42， 74）;4： HLt next =NULL ; HL=HL 宀 next;5: 前一個位置；n-1;6: S.stack S.top;HSt data;7：531& 邊結點、鄰接點域、權域、鏈域；9:索引值域、開始位置域；10:10、3、3、B、I 和 J;11: O （log2n）、0（nlog2n）;12: m、 m - 1三、運算題（每小題 6分，共24分）1、劃分次序劃分結果第一次3824 40 465680 9579第二次243840 4656809579第三次2438 40465680 9579第四次2438 404656809579第五

22、次2438 404656798095第六次2438 40465679 80952、012345678910111278150357452031233612查找成功的平均查找長度：ASL succ=14/10= 1.44、圖深度優(yōu)先序列廣度優(yōu)先序列鄰接矩陣表示時0, 1 , 2, 8, 3, 4, 5, 6, 7, 90, 1 , 4 , 2 , 7 , 3 , 8 , 6 , 5 , 9鄰接表表示時0, 4, 3, 8, 9, 5, 6, 7, 1 , 20 , 4 , 1 , 3 , 7 , 2 , 8 , 6 , 9 , 5四、閱讀算法，回答問題（每小題8分，共16分）3、此二叉樹的后序遍

23、歷結果是:EDCBIHJGFA1、 該算法的輸入結果是：34 91 30 45 63 782、該算法的功能是：交換二叉樹的左右子樹的遞歸算法。10 分)五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容(1 是：(low + high)/2;2 是： Binsch(A,low,mid - 1,K);3 是：Binsch(A,mid+1,high,K);4 是：-1;六、編寫算法(10分)根據(jù)編程情況，酌情給分。Lnode *P=HL;HL=NULL;While (p!=null)Lno de*q=p;P=p t n ext;qf n ext=HL;HL=q;數(shù)據(jù)結構期末考試試題及答案3一、單項選擇題

24、1對于一個算法，當輸入非法數(shù)據(jù)時，也要能作出相應的處理，這種要求稱為()。(A)、正確性 (B).可行性 (C).健壯性 (D).輸入性2. 設S為C語言的語句,計算機執(zhí)行下面算法時，算法的時間復雜度為()。for(i=n-1 ; i>=0 ; i-)for(j=0 ; j<i ; j+) S;(A)、n2(B). O(nlgn)(C). O(n)(D). O(n2)3折半查找法適用于()。(A)、有序順序表 (B)、有序單鏈表(C)、有序順序表和有序單鏈表都可以(D)、無限制4. 順序存儲結構的優(yōu)勢是()。(A)、利于插入操作(B)、利于刪除操作(C)、利于順序訪問(D)、利于隨

25、機訪問5深度為k的完全二叉樹，其葉子結點必在第()層上。(A)、k-1(B)、k (C)、k-1 和 k ( D)、1 至 k6. 具有60個結點的二叉樹，其葉子結點有12個，則度過1的結點數(shù)為()(A )、11(B)、13( C)、48( D)、37、遍歷方法的推廣。7. 圖的 Depth-First Search(DFS)遍歷思想實際上是二叉樹(A)、先序 (B)、中序(C)、后序 (D)、層序&在下列鏈隊列 Q中，元素a出隊的操作序列為()Q(A)、p=Q.front->next; p->next= Q.front->next;第25頁共23頁(B )、p=Q.

26、front->next; Q.front->next=p->next;(C) 、p=Q.rear->next; p->next= Q.rear->next;(D) 、p=Q->next; Q->next=p->next;9. Huffman樹的帶權路徑長度 WPL等于()(A)、除根結點之外的所有結點權值之和(B)、所有結點權值之和(C)、各葉子結點的帶權路徑長度之和(D)、根結點的值10. 線索二叉鏈表是利用()域存儲后繼結點的地址。(A)、Ichild( B)、data(C)、rchild( D)、root二、填空題1. 邏輯結構決定了

27、算法的 ，而存儲結構決定了算法的 。2棧和隊列都是一種 的線性表，棧的插入和刪除只能在 進行。3. 線性表(ai,a 2,an)的順序存儲結構中，設每個單元的長度為 L,元素a的存儲地址LOC(a)為4. 已知一雙向鏈表如下(指針域名為next和prior):p .e現(xiàn)將p所指的結點插入到 x和y結點之間，其操作步驟為： ; ; ;5. n個結點無向完全圖的的邊數(shù)為 ,n 個結點的生成樹的邊數(shù)為 。6. 已知一有向無環(huán)圖如下：7. 已知二叉樹的中序遍歷序列為BCA后序遍歷序列為 CBA則該二叉樹的先序遍歷序列為，層序遍歷序列為。三、應用題1. 設散列函數(shù) H(k)=k % 13,設關鍵字系列為

28、22,12,24,6,45,7,8,13,21, 要求用線性探測 法處理沖突。(6分)(1) 構造HASH表。(2) 分別求查找成功和不成功時的平均查找長度。2. 給定表(19,14,22,15,20,21,56,10) . (8 分)(1) 按元素在表中的次序，建立一棵二叉排序樹(2) 對(1)中所建立的二叉排序樹進行中序遍歷，寫出遍歷序列。(3) 畫出對(2)中的遍歷序列進行折半查找過程的判定樹。3.已知二個稀疏矩陣 A和B的壓縮存儲三元組表如下:ijV13-524625242-1529ABijV25233741352-9558寫出A-B壓縮存儲的三兀組表。(5分)4.已知一維數(shù)組中的數(shù)據(jù)

29、為(18,12,25,53,18_),試寫出插入排序(升序)過程。并指出A開始的最小生成樹。(8分，要有過程)具有n個元素的插入排序的時間復雜度是多少？(5分)ABCDEFA651B653C572D15764E366F246(1 )求從頂點A開始的最小生成樹。5.已知一網(wǎng)絡的鄰接矩陣如下，求從頂點（2）分別畫出以 A為起點的DFS生成樹和BFS生成樹。6.已知數(shù)據(jù)六個字母及在通信中出現(xiàn)頻率如下表:ABCDEF0.150.150.10.10.20.3把這些字母和頻率作為葉子結點及權值，完成如下工作（7分，要有過程）。（1）畫出對應的Huffman樹。（2）計算帶權路徑長度 WPL（3）求 A、B

30、 C、D、E、F 的 Huffman 編碼。7. 已知有如下的有向網(wǎng):求頂點A到其它各頂點的最短路徑（采用 Dijkstra算法，要有過程）。（6分）四、 設計題（30分，每題10分,用C語言寫出算法，做在答題紙上）1. 已知線性表（a1,a 2, - ,a n）以順序存儲結構為存儲結構，其類型定義如下：#define LIST_INIT_SIZEtypedef struct Elemtype *elem;int len gth;SqList;設計一個算法，刪除其元素值為x的結點雜度。其算法函數(shù)頭部如下：100/順序表初始分配容量/順序存儲空間基址/當前長度（存儲元素個數(shù)）（假若x是唯一的）。

31、并求出其算法的平均時間復S tatus ListDelete(Sqlist &L,Elemtype x) base2 設順序棧如左圖所示。 其中結點定義如下：typedef struct Elemtype *base; / 棧底指針Elemtype *top; / 棧頂指針 Stack;設計算法，將棧頂元素出棧并存入e中.3. 設二叉鏈樹的類型定義如下：typedef int Elemtype;typedef struct no deElemtype data; struct node *lchild, *rchild;Bi nN ode, *B in Tree;試寫出求該二叉樹葉子結

32、點數(shù)的算法：S tatus Coun tLeaves(B in Tree &root, int &n)/n is the nu mber of leaves試題3答案一、選擇題(每題 1分)1. C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C二、填空題1 設計、實現(xiàn)2. 特殊、棧頂3. LOC(a1) +(i-1)*L4. p_>next=q_>next;q_>next->prior=p; q_>next=p;p_>prior=q;5. n(n-1)/2、n-16. ADCBFEG 、 ABCDEFFG7. ABC、ABC三、應用題1.(1