數(shù)據(jù)結構三套試卷詳細分析

數(shù)據(jù)結構試卷〔一〕一、單項選擇題〔每題2分，共20分〕棧和隊列的共同特點是(A)。A.只允許在端點處插入和刪除元素B.都是先進后出C.都是先進先出D.沒有共同點Ps:棧：先進后出；隊列：先進先出用鏈接方式存儲的隊列，在進行插入運算時(D).A.僅修改頭指針B.頭、尾指針都要修改C.僅修改尾指針D.頭、尾指針可能都要修改ps:新結點的插入和棧頂結點的刪除都在鏈表的表頭，即棧頂進行。如果隊列為空，即第一個結點為null，那么插入時改變了頭指針。以下數(shù)據(jù)結構中哪一個是非線性結構？(D)A.隊列B.棧C.線性表D.二叉樹Ps：數(shù)據(jù)結構=邏輯結構+存儲結構。二叉樹屬于層次關系——樹結構。設有一個二維數(shù)組A[m][n]，假設A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每個元素占一個空間，問A[3][3](10)存放在什么位置？腳注(10)表示用10進制表示。CA．688B．678C．692D．696Ps：此題畫個圖即知?？芍狝[0][2]的存放位置是646，A[2][1]的存放位置是661，因為A[2][2]的存放位置在676，可知兩層之差為15，然后即可知道A[3][3]的存放位置在676+15+1=692.樹最適合用來表示(C)。A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.元素之間具有分支層次關系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)Ps：樹屬于層次關系，所以可表示元素之間具有分支層次關系的數(shù)據(jù)。二叉樹的第k層的結點數(shù)最多為(D).A．2k-1B.2K+1C.2K-1D.2k-1Ps:二叉樹的性質一：在二叉樹的第k〔k>=1〕層最多有2k-1個結點。假設有18個元素的有序表存放在一維數(shù)組A[19]中，第一個元素放A[1]中，現(xiàn)進行二分查找，那么查找A［3］的比擬序列的下標依次為(D)A.1，2，3 B.9，5，2，3C.9，5，3 D.9，4，2，3Ps：二分查找又稱折半查找，優(yōu)點是比擬次數(shù)少，查找速度快，平均性能好；其缺點是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經(jīng)常變動而查找頻繁的有序列表。首先，假設表中元素是按升序排列，將表中間位置記錄的關鍵字與查找關鍵字比擬，如果兩者相等，那么查找成功；否那么利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關鍵字大于查找關鍵字，那么進一步查找前一子表，否那么進一步查找后一子表。重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。此題分析思路：首先18個元素是在有序表中的，即將它放入一維數(shù)組中的時候是有順序的。那么，第一個比擬應該是〔1+18〕/2=9；第二次比擬應該是(1+9)/2=4；第三次比擬應該是(1+4)/2=2，接下來就是3了。對n個記錄的文件進行快速排序，所需要的輔助存儲空間大致為CA.O〔1〕B.O〔n〕C.O〔1og2n〕D.O〔n2〕Ps:快速排序是需要一個輔助空間的，該空間的大小最好為c選項，最差情況為B選項，此題選C對于線性表〔7，34，55，25，64，46，20，10〕進行散列存儲時，假設選用H〔K〕=K%9作為散列函數(shù)，那么散列地址為1的元素有〔D〕個，A．1B．2C．3D．4Ps：散列函數(shù)即為將要進行散列存儲的數(shù)進行一系列的運算，然后將它們確定在散列表中，此題只需將線性表中的數(shù)都用H(K)進行計算，然后結果為1的數(shù)有幾個即為答案。%是取余。設有6個結點的無向圖，該圖至少應有(A)條邊才能確保是一個連通圖。A.5B.6C.7D.8Ps：連通圖是每兩個結點都有一條邊相連，沒有任何孤立結點。所以6個結點的無向圖至少應該有5條邊。二、填空題〔每空1分，共26分〕通常從四個方面評價算法的質量：__正確性__、___易讀性_、__強壯性_和__高效率__。一個算法的時間復雜度為(n3+n2log2n+14n)/n2，其數(shù)量級表示為___O(n)_____。Ps：將該式化簡開，可發(fā)現(xiàn)為n+log2n+14/n,里面計算最復雜的就是n，所以該算法的時間復雜度為n，用數(shù)量級表示就是O(n).假定一棵樹的廣義表表示為A〔C，D〔E，F(xiàn)，G〕，H〔I，J〕〕，那么樹中所含的結點數(shù)為_9________個，樹的深度為___3____，樹的度為__3____。Ps:根據(jù)廣義表的表示可知該樹的根結點為A，它有三個分支：C、D、H；D下面有EFG三個結點，H下面有IJ兩個結點。由此可知結點總數(shù)為9，樹的深度是層數(shù)，即為3；樹的度即為結點度的最大值，為3.后綴算式923+-102/-的值為___-1____。中綴算式〔3+4X〕-2Y/3對應的后綴算式為_34X*+2Y*3/-_。Ps:后綴計算分層次一步一步計算。中綴變后綴可將每次計算加個括號，然后將操作符提到括號后面，全部弄完之后將括號去除，這樣后綴表達式就全部出來了。假設用鏈表存儲一棵二叉樹時，每個結點除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個指針。在這種存儲結構中，n個結點的二叉樹共有__2n___個指針域，其中有__n-1___個指針域是存放了地址，有_____n+1____個指針是空指針。Ps：有左孩子和右孩子，每個孩子有一個指針，即共有2n個指針域。根據(jù)性質三可證的二叉鏈表中有n+1個，這也是因為在2n個指針域中只有n-1個存有邊信息〔即存放了地址〕。對于一個具有n個頂點和e條邊的有向圖和無向圖，在其對應的鄰接表中，所含邊結點分別有___e__個和____2e__個。Ps：根據(jù)鄰接表的定義可知，一個頂點到另一個結點有邊即鏈接。有向圖只有一次，而無向圖有兩次。AOV網(wǎng)是一種___有向無回路_____的圖。在一個具有n個頂點的無向完全圖中，包含有__n(n-1)/2__條邊，在一個具有n個頂點的有向完全圖中，包含有__n(n-1)__條邊。Ps：首先看題目中的要求是完全圖，即每個頂點要和其他n-1個頂點有邊相連，那么無向完全圖有n(n-1)/2。有向完全圖即為它的兩倍。假定一個線性表為(12,23,74,55,63,40)，假設按Key%4條件進行劃分，使得同一余數(shù)的元素成為一個子表，那么得到的四個子表分別為___〔12，40〕________、_〔23,55,63〕_______、____〔74〕_________和_______〔〕________。Ps：原因和選擇題第9題一樣。向一棵B_樹插入元素的過程中，假設最終引起樹根結點的分裂，那么新樹比原樹的高度____增加1____。在堆排序的過程中，對任一分支結點進行篩運算的時間復雜度為___O(log2n)___，整個堆排序過程的時間復雜度為__O(nlog2n)___。在快速排序、堆排序、歸并排序中，___歸并__排序是穩(wěn)定的。Ps：歸并排序是最穩(wěn)定的排序三、計算題〔每題6分，共24分〕在如下數(shù)組A中鏈接存儲了一個線性表，表頭指針為A[0].next，試寫出該線性表。A01234567data605078903440next3572041〔78,50,40,60,34,90〕請畫出以下圖的鄰接矩陣和鄰接表。鄰接矩陣：鄰接表：一個圖的頂點集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};用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。Ps：克魯斯卡爾算法：設有一個有n個頂點的連通網(wǎng)N={V,E},最初先構造一個只有n個頂點，沒有邊的非連通圖T={V,E},圖中每個頂點自成一個連通分量。當在E中選到一條具有最小權值的邊時,假設該邊的兩個頂點落在不同的連通分量上，那么將此邊參加到T中；否那么將此邊舍去，重新選擇一條權值最小的邊。如此重復下去，直到所有頂點在同一個連通分量上為止。答案：用克魯斯卡爾算法得到的最小生成樹為：(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)20畫出向小根堆中參加數(shù)據(jù)4,2,5,8,3時，每參加一個數(shù)據(jù)后堆的變化。4444422255285283452843答案如下：4444422255285283452843四、閱讀算法〔每題7分，共14分〕LinkListmynote(LinkListL){//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；}returnL；}請答復以下問題：〔1〕說明語句S1的功能；答案：查詢鏈表的尾結點〔2〕說明語句組S2的功能答案：將第一個結點鏈接到鏈表的尾部，作為新的尾結點〔3〕設鏈表表示的線性表為〔a1,a2,…,an〕,寫出算法執(zhí)行后的返回值所表示的線性表。答案：返回的線性表為〔a2,a3,…,an,a1〕voidABC(BTNode*BT){ifBT{ABC(BT->left);ABC(BT->right);cout<<BT->data<<'';}}該算法的功能是：遞歸地后序遍歷鏈式存儲的二叉樹。五、算法填空〔共8分〕二叉搜索樹的查找——遞歸算法:boolFind(BTreeNode*BST,ElemType&item)//ElemType代表所有數(shù)據(jù)類型{if(BST==NULL)returnfalse;//查找失敗else{if(item==BST->data){item=BST->data;//查找成功returntrue;}elseif(item<BST->data)returnFind(BST->left,item);elsereturnFind(BST->right,item);//BST->right和BST->left順序可交換。}//if}六、編寫算法〔共8分〕統(tǒng)計出單鏈表HL中結點的值等于給定值X的結點數(shù)。intCountX(LNode*HL,ElemTypex)答案如下：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ù)結構試卷〔二〕一、選擇題(24分)1．下面關于線性表的表達錯誤的選項是〔D〕。 (A)線性表采用順序存儲必須占用一片連續(xù)的存儲空間 (B)線性表采用鏈式存儲不必占用一片連續(xù)的存儲空間(C)線性表采用鏈式存儲便于插入和刪除操作的實現(xiàn)(D)線性表采用順序存儲便于插入和刪除操作的實現(xiàn)Ps:順序表具有的缺點之一就是不利于插入和刪除操作，所以將存儲方式改良為鏈式存儲。2．設哈夫曼樹中的葉子結點總數(shù)為m，假設用二叉鏈表作為存儲結構，那么該哈夫曼樹中總共有〔B〕個空指針域。 (A)2m-1 (B)2m (C)2m+1 (D)4mPs：哈夫曼樹只有葉子和度為2的結點，用二叉鏈表存儲時每個結點都會有一個左孩子，一個右孩子,所以空指針域為2m。3．設順序循環(huán)隊列Q[0：M-1]的頭指針和尾指針分別為F和R，頭指針F總是指向隊頭元素的前一位置，尾指針R總是指向隊尾元素的當前位置，那么該循環(huán)隊列中的元素個數(shù)為〔C〕。 (A)R-F (B)F-R (C)(R-F+M)％M (D)(F-R+M)％MPs：根據(jù)循環(huán)隊列的定義可知C是正確的。4．設某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，那么后序遍歷該二叉樹得到序列為〔A〕。 (A)BADC (B)BCDA (C)CDAB (D)CBDAPs：根據(jù)前序和中序遍歷可知，C為根結點，A為左子樹，D為右子樹，B為A的右子樹。5．設某完全無向圖中有n個頂點，那么該完全無向圖中有〔A〕條邊。 (A)n(n-1)/2 (B)n(n-1) (C)n2 (D)n2-1Ps：該題和試卷一的一道填空題一樣。6．設某棵二叉樹中有2000個結點，那么該二叉樹的最小高度為〔C〕。 (A)9 (B)10 (C)11 (D)12Ps：根據(jù)二叉樹的性質2可知，該二叉樹的最小高度應該是結點數(shù)最多的時候，這樣列出一個表達式即可知道該二叉樹的最小高度。7．設某有向圖中有n個頂點，那么該有向圖對應的鄰接表中有〔B〕個表頭結點。 (A)n-1 (B)n (C)n+1 (D)2n-1Ps：根據(jù)鄰接表的定義可知，表頭結點數(shù)目與頂點數(shù)目相同。8．設一組初始記錄關鍵字序列(5，2，6，3，8)，以第一個記錄關鍵字5為基準進行一趟快速排序的結果為〔C〕。 (A)2，3，5，8，6 (B)3，2，5，8，6 (C)3，2，5，6，8 (D)2，3，6，5，8Ps：快速排序是將一個數(shù)為基準，然后分為左右兩個序列，左邊的數(shù)都比基準小，右邊的數(shù)都比基準大。二、填空題(24分)為了能有效地應用HASH查找技術，必須解決的兩個問題是_構造一個好的HASH函數(shù)_和__確定解決沖突的方法__。下面程序段的功能實現(xiàn)數(shù)據(jù)x進棧，要求在下劃線處填上正確的語句。typedefstruct{ints[100];inttop;}sqstack;voidpush(sqstack&stack,intx){if(stack.top==m-1)printf(“overflow”);else{_stack.top++__;___stack.s[stack.top]=x__;}}中序遍歷二叉排序樹所得到的序列是__有序____序列〔填有序或無序〕?？焖倥判虻淖顗臅r間復雜度為__O(n2)__，平均時間復雜度為__O(nlog2n)__。設某棵二叉樹中度數(shù)為0的結點數(shù)為N0，度數(shù)為1的結點數(shù)為N1，那么該二叉樹中度數(shù)為2的結點數(shù)為__N0-1_；假設采用二叉鏈表作為該二叉樹的存儲結構，那么該二叉樹中共有__2N0+N1__個空指針域。設某無向圖中頂點數(shù)和邊數(shù)分別為n和e，所有頂點的度數(shù)之和為d，那么e=d/2__。設一組初始記錄關鍵字序列為(55，63，44，38，75，80，31，56)，那么利用篩選法建立的初始堆為_(31，38，54，56，75，80，55，63)_。8．一有向圖的鄰接表存儲結構如下：從頂點1出發(fā)，DFS遍歷的輸出序列是(1，3，4，5，2)，BFS遍歷的輸出序列是(1，3，2，4，5)Ps:DFS:深度優(yōu)先遍歷，BFS：廣度優(yōu)先遍歷。三、應用題(36分)設一組初始記錄關鍵字序列為(45，80，48，40，22，78)，那么分別給出第4趟簡單項選擇擇排序和第4趟直接插入排序后的結果。簡單項選擇擇排序：(22，40，45，48，80，78)；直接插入排序：(40，45，48，80，22，78)設指針變量p指向雙向鏈表中結點A，指針變量q指向被插入結點B，要求給出在結點A的后面插入結點B的操作序列〔設雙向鏈表中結點的兩個指針域分別為llink和rlink〕。q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;設一組有序的記錄關鍵字序列為(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求計算出查找關鍵字62時的比擬次數(shù)并計算出查找成功時的平均查找長度。2,ASL=91*1+2*2+3*4+4*2)=25/9設一棵樹T中邊的集合為{(A，B)，(A，C)，(A，D)，(B，E)，(C，F(xiàn))，(C，G)}，要求用孩子兄弟表示法〔二叉鏈表〕表示出該樹的存儲結構并將該樹轉化成對應的二叉樹。設有無向圖G，要求給出用普里姆算法構造最小生成樹所走過的邊的集合。E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}設有一組初始記錄關鍵字為(45，80，48，40，22，78)，要求構造一棵二叉排序樹并給出構造過程。四、算法設計題(16分)設有一組初始記錄關鍵字序列〔K1，K2，…，Kn〕，要求設計一個算法能夠在O(n)的時間復雜度內將線性表劃分成兩局部，其中左半局部的每個關鍵字均小于Ki，右半局部的每個關鍵字均大于等于Ki。Ps：該算法即為快速排序算法voidquickpass(intr[],ints,intt){inti=s,j=t,x=r[s];while(i<j){while(i<j&&r[j]>x)j=j-1;if(i<j){r[i]=r[j];i=i+1;}while(i<j&&r[i]<x)i=i+1;if(i<j){r[j]=r[i];j=j-1;}}r[i]=x;}設有兩個集合A和集合B，要求設計生成集合C=A∩B的算法，其中集合A、B和C用鏈式存儲結構表示。typedefstructnode{intdata;structnode*next;}lklist;voidintersection(lklist*ha,lklist*hb,lklist*&hc){lklist*p,*q,*t;for(p=ha,hc=0;p!=0;p=p->next){for(q=hb;q!=0;q=q->next)if(q->data==p->data)break;if(q!=0){t=(lklist*)malloc(sizeof(lklist));t->data=p->data;t->next=hc;hc=t;}}}數(shù)據(jù)結構試卷〔三〕一、選擇題(每題1分，共20分)1．設某數(shù)據(jù)結構的二元組形式表示為A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，那么數(shù)據(jù)結構A是〔B〕。 (A)線性結構 (B)樹型結構 (C)物理結構 (D)圖型結構Ps：將該題的結構圖畫出即可看出是什么結構。2．下面程序的時間復雜為〔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)Ps：這里面有雙層循環(huán)嵌套在一起，每層都有運行n次，兩次即為n*n。3．設指針變量p指向單鏈表中結點A，假設刪除單鏈表中結點A，那么需要修改指針的操作序列為〔A〕。 (A)q=p->next；p->data=q->data；p->next=q->next；free(q)；(B)q=p->next；q->data=p->data；p->next=q->next；free(q)； (C)q=p->next；p->next=q->next；free(q)； (D)q=p->next；p->data=q->data；free(q)；Ps：首先用指針變量q指向結點A的后繼結點B，然后將結點B的值復制到結點A中，最后刪除結點B。4．設有n個待排序的記錄關鍵字，那么在堆排序中需要〔A〕個輔助記錄單元。 (A)1 (B)n (C)nlog2n (D)n25．設一組初始關鍵字記錄關鍵字為(20，15，14，18，21，36，40，10)，那么以20為基準記錄的一趟快速排序結束后的結果為(A)。(A)10，15，14，18，20，36，40，21 (B)10，15，14，18，20，40，36，21 (C)10，15，14，20，18，40，36，2l (D)15，10，14，18，20，36，40，216．設二叉排序樹中有n個結點，那么在二叉排序樹的平均平均查找長度為〔B〕。 (A)O(1) (B)O(log2n) (C) (D)O(n2)7．設無向圖G中有n個頂點e條邊，那么其對應的鄰接表中的表頭結點和表結點的個數(shù)分別為〔D〕。 (A)n，e (B)e，n (C)2n，e (D)n，2e8.設某強連通圖中有n個頂點，那么該強連通圖中至少有〔C〕條邊。 (A)n(n-1) (B)n+1 (C)n (D)n(n+1)9．設有5000個待排序的記錄關鍵字，如果需要用最快的方法選出其中最小的10個記錄關鍵字，那么用以下〔D〕方法可以到達此目的。 (A)快速排序 (B)堆排序 (C)歸并排序 (D)插入排序Ps：快速排序、歸并排序和插入排序必須等到整個排序結束后才能夠求出最小的10個數(shù)，而堆排序只需要在初始堆的根底上再進行10次篩選即可，每次篩選的時間復雜度為O(log2n)。10.以下四種排序中〔D〕的空間復雜度最大。 (A)插入排序 (B)冒泡排序 (C)堆排序 (D)歸并排序二、填空殖(每空1分共20分)數(shù)據(jù)的物理結構主要包括_順序存儲結構__和__鏈式存儲結構__兩種情況。設一棵完全二叉樹中有500個結點，那么該二叉樹的深度為__9____；假設用二叉鏈表作為該完全二叉樹的存儲結構，那么共有___501___個空指針域。設輸入序列為1、2、3，那么經(jīng)過棧的作用后可以得到__5_____種不同的輸出序列。Ps：共5種：123,213,321,231,132.設有向圖G用鄰接矩陣A[n][n]作為存儲結構，那么該鄰接矩陣中第i行上所有元素之和等于頂點i的__出度__，第i列上所有元素之和等于頂點i的__入度__。設哈夫曼樹中共有n個結點，那么該哈夫曼樹中有__0___個度數(shù)為1的結點。設有向圖G中有n個頂點e條有向邊，所有的頂點入度數(shù)之和為d，那么e和d的關系為__e=d__。__中序__遍歷二叉排序樹中的結點可以得到一個遞增的關鍵字序列〔填先序、中序或后序〕。設查找表中有100個元素，如果用二分法查找方法查找數(shù)據(jù)元素X，那么最多需要比擬__7___次就可以斷定數(shù)據(jù)元素X是否在查找表中。不管是順序存儲結構的棧還是鏈式存儲結構的棧，其入棧和出棧操作的時間復雜度均為___O(1)___。設有n個結點的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，那么第i個結點的雙親結點編號為___i/2____，右孩子結點的編號為____2i+1___。設一組初始記錄關鍵字為(72，73，71，23，94，16，5)，那么以記錄關鍵字72為基準的一趟快速排序結果為___〔5,71,23,16,72,73,94〕____。設有向圖G中有向邊的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，那么該圖的一種拓撲序列為_(1，4，3，2)__。以下算法實現(xiàn)在順序散列表中查找值為x的關鍵字，請在下劃線處填上正確的語句。structrecord{intkey;intothers;};inthashsqsearch(structrecordhashtable[],intk){inti,j;j=i=k%p;while(hashtable[j].key!=k&&hashtable[j].flag!=0){j=(j+1)%m;if(i==j)return(-1);}if(hashtable[j].key==k)return(j);elsereturn(-1);}以下算法實現(xiàn)在二叉排序樹上查找關鍵值k，請在下劃線處填上正確的語句。typedefstructnode{intkey;structnode*lchild;structnode*rchild;}bitree;bitree*bstsearch(bitree*t,intk){ if(t==0)return(0);elsewhile(t!=0)if(t->key==k)return(t);elseif(t->key>k)t=t->lchild;elset=t->rchild;}三、計算題(每題10分，共30分)1.二叉樹的前序遍歷序列是AEFBGCDHIKJ，中序遍歷序列是EFAGBCHKIJD，畫出此二叉樹，并畫出它的后序線索二叉樹。2．待散列的線性表為〔36，15，40，63，22〕，散列用的一維地址空間為[0..6]，假定選用的散列函數(shù)是H〔K〕=Kmod7，假設發(fā)生沖突采用線性探查法處理，試：〔1〕計算出每一個元素的散列地址并在以下圖中填寫出散列表：`0123456求出在查找每一個元素概率相等情況下的平均查找長度。H(36)=36mod7=1;H１(22)=(1+1)mod7=2;….沖突H(15)=15mod7=1;