安工大數(shù)據(jù)結構試卷(帶完整答案)

………………裝………………訂…………………線………………課程________________________班級________________________姓名__________________________學號________________________………………密………………封…………………線………………安徽工業(yè)大學試題紙（一）題號一二三四五六七八九十十一十二十三十四十五十六十七十八十九二十總分得分安徽工業(yè)大學2012~2013學年第二學期期末考試《數(shù)據(jù)結構》試卷(A)一、單項選擇題（110=10分）1、在數(shù)據(jù)結構中，從邏輯上可以把數(shù)據(jù)結構分為（C）。(A)動態(tài)結構和靜態(tài)結構(B)緊湊結構和非緊湊結構(C)線性結構和非線性結構(D)內部結構和外部結構2.設某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（A）。 (A)BADC (B)BCDA (C)CDAB (D)CBDA3.將10階對稱矩陣壓縮存儲到一維數(shù)組A中，則數(shù)組A的長度最少為（C）。 (A)100 (B)40 (C)55 (D)804.設順序循環(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)％M5.設某棵三叉樹中有40個結點，則該三叉樹的最小高度為（B）。 (A)3 (B)4 (C)5 (D)66.設某強連通圖中有n個頂點，則該強連通圖中至少有（C）條邊。 (A)n(n-1) (B)n+1 (C)n (D)n(n+1)7.設有5000個待排序的記錄關鍵字，如果需要用最快的方法選出其中最小的10個記錄關鍵字，則用下列（B）方法可以達到此目的。 (A)快速排序 (B)堆排序 (C)歸并排序 (D)插入排序8.若某線性表中最常用的操作是取第I個元素和找第I個元素的前趨元素，則采用（D）存儲方式最節(jié)省時間。（A）單鏈表(B)雙鏈表（C）單向循環(huán)(D)順序表9.設某無向圖中有n個頂點e條邊，則該無向圖中所有頂點的入度之和為（D）。 (A)n (B)e (C)2n (D)2e10.設有序表中有1000個元素，則用二分查找查找元素X最多需要比較（B）次。 (A)25 (B)10 (C)7 (D)1二、填空題（每空格1分，共17分）數(shù)據(jù)的物理結構主要包括__連續(xù)存儲結構____和___非連續(xù)存儲結構____兩種情況。設一棵完全二叉樹中有500個結點，則該二叉樹的深度為_____9_____；若用二叉鏈表作為該完全二叉樹的存儲結構，則共有______501_____個空指針域。設輸入序列為1、2、3，則經過棧的作用后可以得到____5_______種不同的輸出序列。設哈夫曼樹中共有99個結點，則該樹中有____50_____個葉子結點；若采用二叉鏈表作為存儲結構，則該樹中有__100___個空指針域。設一棵完全二叉樹的順序存儲結構中存儲數(shù)據(jù)元素為ABCDEF，則該二叉樹的中序遍歷序列為_____DBEAFC______?！b………………訂…………………線………………課程________________________班級________________________姓名__________________________學號________________________………………密………………封…………………線………………安徽工業(yè)大學試題紙（二）6．設F和R分別表示順序循環(huán)隊列的頭指針和尾指針，則判斷該循環(huán)隊列為空的條件為_______F==R______________。7．設二叉樹中結點的兩個指針域分別為lchild和rchild，則判斷指針變量p所指向的結點為葉子結點的條件是_______p->lchild==NULL&&p->rchild==NULL______________________________________。8．簡單選擇排序和直接插入排序算法的平均時間復雜度為_____O(n^2)______。9．快速排序算法的空間復雜度平均情況下為____O(log2n)______，最壞的情況下為____O(n^2)______。10.散列表中解決沖突的兩種方法是______開放地址法_______和___鏈地址法__________。11．平衡因子是指____左子樹的深度減去右子樹的深度____________________________________。12．數(shù)組A[0..6,0..8]的每個元素占4個字節(jié)，將其按行優(yōu)先次序存儲在起始地址為2000的內存單元中，元素A[5,6]的地址是_____2204________。三、應用題。（共35分）已知8個待排序的記錄，其關鍵碼分別為53，36，30，91，47，12，24，85，用希爾排序、快速排序和堆排序對其進行排序，寫出第一趟排序后結果。(9分)答：希爾排序：1224309147533685(步長為5)快速排序：2436301247539185小堆排序：1236538547302491假定有字符a1，a2，a3，a4，a5在一篇文章中出現(xiàn)的次數(shù)分別為{{3,2,4,5,1}}試以它們?yōu)槿~子結點構造哈夫曼樹，并計算WPL(8分)答：見三、2圖WPL=（3+4+5）*2+（1+2）*3=33已知廣義表L=(a,(b,c),(d,e)),試畫出其存儲結構圖并利用取頭函數(shù)head和取尾函數(shù)tail求出原子e。((6分)答：見三、3圖e=head(tail(head(tail(tail(L))))4．（共6分）設有下列帶權無向圖：請用PRIM求該圖的一棵最小生成樹。答：見三、4圖5.設一棵二叉樹的先序序列為ABDGECFH，中序序列為：DGBAECHF。試畫出該二叉樹。(6分)答：見三、5圖四、判斷題（1*10`=10分）1、順序表結構適宜于進行順序存取，而鏈表適宜于進行隨機存取。（錯）2、兩個棧共享一片連續(xù)內存空間時，為提高內存利用率，減少溢出機會，應把兩個棧的棧底分別設在這片內存空間的兩端。。（對）3、一個棧的輸入序列是12345，則棧的輸出序列不可能是12345。（錯）4、串是一種數(shù)據(jù)對象和操作都特殊的線性表。（對）5、數(shù)組可看成線性結構的一種推廣，因此與線性表一樣，可以對它進行插入，刪除等操作。（錯）6、對于一棵非空二叉樹，它的根結點作為第一層，則它的第i層上最多能有2i-1個結點。（錯）7、最小代價生成樹是唯一的。（錯）8、歸并排序的空間復雜度為O(n)（對）9、為了方便操作，一般在二叉樹排序樹中插入一個新結點，總是作為葉結點。（對）10、在初始數(shù)據(jù)表已經有序時，快速排序算法的時間復雜度為O(nlog2n)。（錯）五、編寫算法（28分）試編寫算法將兩個有序的單鏈表歸并成一個新的有序單鏈表。（10分）linklistMerge(linklistA,linklistB)/*將有序單鏈表合并后由函數(shù)帶回*/答：LinkListMerge(LinkListA,LinkListB){ LinkListp,q,r; p=A; q=B->next;while(p){ if(q->next->dtat<p->data) { r=q; r->next=p->next; p->next=r; q=q->next; } else { p=p->next; q=q->next; } if(!p&&q) p=q; returnA;}試編寫算法計算二叉樹中度為1的結點數(shù)。（9分）intcount(bintreet)/*求二叉鏈表結構二叉樹t度為1的結點數(shù)*/答:intcount(bintreet){ intcount=0; PSeqStackS; bintreep=t; S=Init_SeqStack(); while(p||Empty_SeqStack(S)) { if(p) { Push_SeqStack(S,p); p=p->lichild; } else { Pop_SeqStack(S,&p); if(((p->lchild!=NULL)&&(p->rchild==NULL))||((p->lchild==NULL)&&(p->rchild!=NULL))) count++; p=p->rchild; } } returncount;}試編寫算法在二叉排序樹T中查找值為X的算法。（9分）BinSTreeBS