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

第第3頁共30頁2017《數(shù)據(jù)結構》期末考試試題及答案《數(shù)據(jù)結構》期末考試試題及答案1 2試題1答案 7《數(shù)據(jù)結構》期末考試試題及答案2 9試題2答案 14《數(shù)據(jù)結構》期末考試試題及答案3 16試題3答案 21《數(shù)據(jù)結構》期末考試試題及答案1一、 單選題（每題2分，共20分） A.只允許在端點處插入和刪除元素B.都是先進后出C.都是先進先出D.沒有共同點用鏈接方式存儲的隊列，在進行插入運算( ).僅修改頭指針 B.頭、尾指針都要修改C.僅修改尾指針 頭、尾指針可能都要修改以下數(shù)據(jù)結構中哪一個是非線性結構)隊列 B.棧 C.線性表 D.二叉樹設有一個二維數(shù)組假設存放位置在644 存放位

，每個元素占一個空間，問A[3][3]

存放在什么位置？腳注

表示用(10)10進制表示。

(10)

(10)A．688 B．678 C．692 D．696樹最適合用來表( )。有序數(shù)據(jù)元素 B.無序數(shù)據(jù)元素C.元素之間具有分支層次關系的數(shù)據(jù) 元素之間無聯(lián)系的數(shù)據(jù)二叉樹的第k層的結點數(shù)最多( ).A．2k-1 B.2K+1 C.2K-1 D.若有18個元素的有序表存放在一維數(shù)組A[19]中，第一個元素放A[1]中，現(xiàn)進行二分查找，則查找A［3］的比較序列的下標依次( )A.1，2，3 B.9，5，2，3C.9，5，3 D.對nA.O（1） B.O（n） C.O（1og2n） D.9. 對于線性表（7，34，55，25，64，46，20，10）進行散列存儲時，若選用H（K）=K%9作為散列函數(shù)，則散列地址為1的元素有（ ）個，A．1 B．2 C．3 D．410.設有6個結點的無向圖，該圖至少應( )條邊才能確保是一個連通圖。A.5 B.6 C.7 D.8二、 填空題（每空1分，共26分）通常從四個方面評價算法的質量、 、 和 。一個算法的時間復雜度其數(shù)量級表示。假定一棵樹的廣義表表示為A（C，，F(xiàn)，（，則樹中所含的結點數(shù)為 個，樹的深度，樹的度。4.后綴算式923+-102/的值為 。中綴算式（3+4X）-2Y/3對應的綴算式為 。若用鏈表存儲一棵二叉樹時每個結點除數(shù)據(jù)域外還有指向左孩子和右孩子的兩個指針。在這種存儲結構中個結點的二叉樹共個指針域，其中個指針域是存放了地址，個指針是空指針。對于一個具有n個頂點和e條邊的有向圖和無向圖，在其對應的鄰接表中，所邊結點分別個個。AOV網是一的圖。在一個具有n個頂點的無向完全圖中包含有 條邊在一個具有n個頂?shù)挠邢蛲耆珗D中，包含條邊。假定一個線性表(12,23,74,55,63,40)，若按Key%4條件進行劃分，使得同一余數(shù)的元素成為一個子表，則得到的四個子表分別為 、 、 和 。向一棵B_樹插入元素的過程中，若最終引起樹根結點的分裂，則新樹比原樹的度 。在堆排序的過程中，對任一分支結點進行篩運算的時間復雜度，整個排序過程的時間復雜度。在快速排序、堆排序、歸并排序中排序是穩(wěn)定的。三、 運算題（每題6分，共24分）在如下數(shù)組A中鏈接存儲了一個線性表表頭指針為A試寫出該線性表。A 0 1 2 3 4 5 6 7data

60 50

90 34 40next 3 5 7 2 0 4 110圖10第4頁共30頁第第8頁共30頁 已知一個圖的頂點集V和邊集E分別為：V={1,2,3,4,5,6,7};(6,7)25};用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。4,2,5,8,3四、 閱讀算法（每題7分，共14分）LinkListmynote(LinkListL){//L是不帶頭結點的單鏈表的頭指針if(L&&L->next){q=L；L=L－>next；p=L；S1： while(p－>next)p=p－>next；S2： }return L；}請回答下列問題：S1S2設鏈表表示的線性表為（a1,a2,…,an）性表。voidABC(BTNode*BT){if BT{ABC(BT->left);ABC(BT->right);cout<<BT->data<<'';}}該算法的功能是：五、 算法填空（共8分）boolFind(BTreeNode*BST,ElemType&item){if(BST==NULL)returnfalse;//查找失敗else{if(item==BST->data){return ;}elseif(item<BST->data)return Find( ,item);else returnFind( ,item);}//if}六、 編寫算法（共8分）統(tǒng)計出單鏈表HL中結點的值等于給定值X的結點數(shù)。intCountX(LNode*HL,ElemTypex)試題1答案一、 單選題（每題2分，共20分）1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A二、 填空題（每空1分，共26分）1. 正確性易讀性強壯性 高效率2. O(n)3. 9 334. -1 34X*+2Y*3/-5. 2nn-1n+16. e2e7. 有向無回路8. n(n-1)/2 n(n-1)9. （12，40） （ ） （74） （23,55，63）1O(log2n) O(nlog2n)歸并三、 運算題（每題6分，共24分）. （，，0，，，）01111鄰接矩陣：

1 1 1 00 1 0 11 0 1 10 1 0 11 1 1 鄰接表如圖11所示：圖11用克魯斯卡爾算法得到的最小生成樹為：(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20124 4 2 42

2 2 24 5 4 5 4 58 8 33 58 4圖12四、 閱讀算法（每題7分，共14分）（1）查詢鏈表的尾結點將第一個結點鏈接到鏈表的尾部，作為新的尾結點返回的線性表為（a2,a3,…,an,a1）遞歸地后序遍歷鏈式存儲的二叉樹。五、 算法填空（每空2分，共8分）true BST->left 六、 編寫算法（8分）第9頁共30頁PAGE2230頁intCountX(LNode*HL,ElemTypex){ inti=0;LNode*p=HL;//i為計數(shù)器while(p!=NULL){if(P->data==x)i++;p=p->next;}//while,出循環(huán)時i中的值即為x結點個數(shù)returni;}//CountX《數(shù)據(jù)結構》期末考試試題及答案2一、 單選題（每小題2分，共8分）1、在一個長度為n的順序線性表中順序查找值為x的元素時，查找成功時的平均查長度（即x與元素的平均比較次數(shù)，假定查找每個元素的概率都相等）為 ( )。A n B n/2 C (n+1)/2 D (n-1)/22、在一個單鏈表,若q所指結點是p所指結點的前驅結,若在q與p之間插入一個s所指的結則執(zhí)( )。A s→link=p→link; p→link=s; B p→link=s; s→link=q;C p→link=s→link; s→link=p; D q→link=s; s→link3、 棧的插入和刪除操作在（）進行。A 棧頂 B 棧底 C 任意位置 D 指定位置4、 由權值分別為11，8，6，2，5的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為（）A24B71C 48D53二、 填空題（每空1分，共32分）1、數(shù)據(jù)的邏輯結構被分、 、 和 四種。2、一種抽象數(shù)據(jù)類型包和 兩個部分。3、在下面的數(shù)組a中鏈接存儲著一個線性表，表頭指針為a[o].next，則該線性表為 。012301234567860564238742543762014、在以HL為表頭指針的帶表頭附加結點的單鏈表和循環(huán)單鏈表中，判斷鏈表為空的條件分別和 。5、用具有n個元素的一維數(shù)組存儲一個循環(huán)隊列，則其隊首指針總是指向隊首素的 ，該循環(huán)隊列的最大長度。6、當堆棧采用順序存儲結構時，棧頂元素的值可用———————表示；當堆采用鏈接存儲結構時，棧頂元素的值可表示。7、一棵高度為5的二叉樹中最少含個結點，最多含個結點一棵高度為5的理想平衡樹中，最少含個結點，最多含個結點。8、在圖的鄰接表中，每個結點被稱為 ，通常它包含三個域：一是 ；二是 ；三是 。9在一個索引文件的索引表中每個索引項包含對應記錄和 兩項數(shù)據(jù)。0、假定一棵樹的廣義表表示為A（B（C，（E，F(xiàn)，，（，），則樹中所含的結點數(shù)個，樹的深度樹的度為 ,結點H的親結點為 孩子結點。11、在堆排序的過程中，對任一分支結點進行篩運算的時間復雜度為 個堆排序過程的時間復雜度。12、在對m階的B_樹插入元素的過程中，每向一個結點插入一個索引項（葉子點中的索引項為關鍵字和空指針）后，若該結點的索引項數(shù)等于個，則必須把它分裂個結點。三、 運算題（每小題6分，共24分）1、已知一組記錄的排序碼為（6，9，68，0，,5，4，寫出對其進行快速排序的每一次劃分結果。圖圖深度優(yōu)先序列廣度優(yōu)先序列2、一個線性表為=（23，5，7，03815，6，設散列HT[0..12H（key）=key%13并用線性探查法解決沖突，請畫出散列表，并計算等概率情況下查找成功的平均查找長度。3、已知一棵二叉樹的前序遍歷的結果序列是ABECKFGHIJ，中序遍歷的結果是EBCDAFHIGJ，試寫出這棵二叉樹的后序遍歷結果。4、已知一個圖的頂點集VG{0，1，2，3，4，5，6，7，8，9}；E=0104（121728（（38（565，8596，77，8，）}當它用鄰接矩陣表示和鄰接表表示時，分別寫出從頂點V0出發(fā)按深度優(yōu)先搜索遍歷得到的頂點序列和按廣度優(yōu)先搜索遍歷等到的頂點序列。假定每個頂點鄰接表中的結點是按頂點序號從大到小的次序鏈接的。鄰接矩陣表示時鄰接矩陣表示時鄰接表表示時四、 閱讀算法，回答問題（每小題8分，共16分）1、假定從鍵盤上輸入一批整數(shù)，依次為63 45 30 91 34 –1，請寫出輸出結果。#include<iostream.h>#include<stdlib.h>constintstackmaxsize=30;typedefintelemtype;structstack{elemtypestack[stackmaxsize];inttop;};#include“stack.h”void main(){stacka;initstack(a);intx;cin>>x;while(x!=-1){push(a,x);cin>>x;}while(!stackempty(a))tp)”;cout<<end1;}該算法的輸出結果為：2、閱讀以下二叉樹操作算法，指出該算法的功能。es e>d e>：unknown(BinTreeNode<Type>*t) {BinTreeNode<Type> *p=t,if(p!=NULL){temp=p→leftchild;p→leftchild=p→rightchild;p→rightchild=temp;unknown(p→leftchild);undnown(p→rightchild);}}該算法的功能是 五、 算法填空，在畫有橫線的地方填寫合適的內容分）對順序存儲的有序表進行二分查找的遞歸算法。intBinsch(ElemTypeA[],intlow,inthigh,KeyTypeK){if(low<=high){intmid= 1if(K==A[mid].key)returnmid;elseif(K<A[mid].key)return 2else}

return 3elsereturn 4六、 編寫算法分）編寫算法，將一個結點類型為Lnode的單鏈表按逆序鏈接，即若原單鏈表中存儲元素的次序為a1，……an-1，an，則逆序鏈接后變?yōu)?an，an-1，……a1。Void contrary(Lnode*&HL)試題2答案一、單選題（每小題2分，共8分）題號 1234答案 CDAB二、填空題（每空1分，共32分1：集合、線性、樹、圖；2：數(shù)據(jù)描述、操作聲名；：（，，，，2，4；4：HL→next=NULL； HL=HL→next；5：前一個位置； n-1；6：S.stack[S.top]; 7：5 318：邊結點、鄰接點域、權域、鏈域；9：索引值域、開始位置域；10：10、3、3、B、I和J；：（gn、g12：m、 m-1劃分次序劃分結果劃分次序劃分結果第一次[382440]46[56809579]第二次24[3840]46[56809579]第三次243840 46[56809579]第四次243840 4656[809579]第五次第五次24 38 40 46 56 79 [80 95]第六次24 38 40 46 56 79 80 952、0 1 2 3 4 5 6 7 8 9 10 11 127878150357452031233612查找成功的平均查找長度：ASLSUCC=14/10=1.43、此二叉樹的后序遍歷結果是：EDCBIHJGFA4、圖深度優(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分）1、該算法的輸入結果是：34 91 30 45 63 782、該算法的功能是：交換二叉樹的左右子樹的遞歸算法。五、算法填空，在畫有橫線的地方填寫合適的內容（10分1（w+h）Binsch(A,low,mid–1,K);Binsch(A,mid+1,high,K);4是：-1；六、編寫算法（10分）根據(jù)編程情況，酌情給分。{Lnode*P=HL;HL=NULL;While(p!=null){Lnode*q=p;P=p→next;q→next=HL;HL=q;}}《數(shù)據(jù)結構》期末考試試題及答案3一、單項選擇題對于一個算法，當輸入非法數(shù)據(jù)時，也要能作出相應的處理，這種要求稱為（ (A)、正確性 (B).可行性 (C).健壯性 (D). 輸入性設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)折半查找法適用于（ 。（A、有序順序表 （B、有序單鏈表（C、有序順序表和有序單鏈表都可以 （、無限4．順序存儲結構的優(yōu)勢是（ 。A、利于插入操作（B、利于刪除操作C、利于順序訪問（D、利于隨機訪問深度為k的完全二叉樹，其葉子結點必在第（ ）層上。（A、1 （B、k C、1和k （D、1至k具有60個結點的二叉樹，其葉子結點有12個，則度過1的結點數(shù)為（ ）（A、1 （B、3 （C8 （D、圖的Depth-FirstSearch(DFS)遍歷思想實際上是二叉樹（ ）遍歷方法的推廣。、先序 （B、中序 （C、后序 D、層序8．在下列鏈隊列Q中，元素a出隊的操作序列為（ frontfrontabcd∧Q、p=Q.front->next;p->next=Q.front->next;、p=Q.front->next;Q.front->next=p->next;、p=Q.rear->next;p->next=Q.rear->next;、p=Q->next;Q->next=p->next;9．Huffman樹的帶權路徑長度WPL等于（ ）（A、除根結點之外的所有結點權值之和 （B、所有結點權值之和（C、各葉子結點的帶權路徑長度之和 （、根結點的10．線索二叉鏈表是利用（ ）域存儲后繼結點的地址。（A、d （B、a （C、d （D、二、填空題邏輯結構決定了算法的 ，而存儲結構決定了算法的 。棧和隊列都是一種 的線性表，棧的插入和刪除只能在 進行。線性表（a1,a2,…,an）的順序存儲結構中，設每個單元的長度為L，元素ai的存儲地址xyqpexyqpe現(xiàn)將p所指的結點插入到x和y結點之間，其操作步驟為： ；； ； ；5．n個結點無向完全圖的的邊數(shù)為 n個結點的生成樹的邊數(shù)為 。已知一有向無環(huán)圖如下：BBFADGCE任意寫出二種拓撲排序序列： 、 。已知二叉樹的中序遍歷序列為 BCA，后序遍歷序列為 CBA，則該二叉樹的先序遍歷序為 ，層序遍歷序列為 。三、應用題1．設散列函數(shù)H(k)=k%13,設關鍵字系列為{22,12,24,6,45,7,8,13,21},要求用線性探測法處理沖突。(6分)HASH分別求查找成功和不成功時的平均查找長度。2．給定表（19,14,22,15,20,21,56,10）.（8分）按元素在表中的次序，建立一棵二叉排序樹對(1)中所建立的二叉排序樹進行中序遍歷，寫出遍歷序列。畫出對(2)中的遍歷序列進行折半查找過程的判定樹。ABABijVijV13-525224633725241342-152-9529558寫出A-B壓縮存儲的三元組表。（5分）已知一維數(shù)組中的數(shù)據(jù)為（18,12,25,53,18）,試寫出插入排序（升序）過程。并指出具有n個元素的插入排序的時間復雜度是多少？(5已知一網絡的鄰接矩陣如下，求從頂點A開始的最小生成樹。(8分，要有過程A B C D E FA 6 5 1 B6 5 3 C5 7 2D1 5 7 6 4 3636246F AADFSBFSA0.15A0.15B0.15C0.1D0.1E0.2F0.3把這些字母和頻率作為葉子結點及權值，完成如下工作(7分，要有過程)。HuffmanWPL。A、B、C、D、E、FHuffmanA2A25B3E641061 22第2330頁PAGE3030頁CCDA（Dijkstra（6）四、 設計題 （30分，每題10分,用C語言寫出算法，做在答題紙上）已知線性表（a1,a2,…,an）以順序存儲結構為存儲結構，其類型定義如下#define LIST_INIT_SIZE 100 //順序表初始分配容量typedef struct {Elemtype *elem; //順序存儲空間基址int length; //當前長度（存儲元素個數(shù)）}SqList;設計一個算法，刪除其元素值為x的結點（假若x是唯一的算法函數(shù)頭部如下：StatusListDelete(Sqlist&L,Elemtypex){……}anan…aa12其中結點定義如下： toptypedef struct{Elemtype *base; //棧底指Elemtype *top; //棧頂指針}Stack;設計算法，將棧頂元素出棧并存入e中． base設二叉鏈樹的類型定義如下：typedef int typedef struct node{Elemtype data;struct node *lchild,*rchild;}BinNode,*BinTree;試寫出求該二叉樹葉子結點數(shù)的算法:StatusCountLeaves(BinTree&root,int&n){//nisthenumberofleaves……}試題3答案一、選擇題（每題1分）1、C2、D3、A4、D5、C6、D7、A8、B9、C10、C二、填空題設計、實現(xiàn)特殊、棧頂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-1ADCBFEG、ABCDEFFGABC、ABC三