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

1、課程班級姓名學號密封線安 徽 工 業(yè) 大 學 試 題 紙(一)題號一二三四五六七八九十十一十二十三十四十五十六十七十八十九二十總分得分安徽工業(yè)大學20122013學年第二學期期末考試數(shù)據(jù)結構試卷(A)一、單項選擇題(1M10=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ù)

2、組 A中，則數(shù)組A的長度最少為(C)。(A) 100(B) 40(C) 55(D) 804 .設順序循環(huán)隊列Q0: 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

3、個待排序的記錄關鍵字，如果需要用最快的方法選出其中最小的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分，共

4、17分)1 .數(shù)據(jù)的物理結構主要包括 連續(xù)存儲結構 和非連續(xù)存儲結構兩種情況。2 .設一棵完全二叉樹中有500個結點，則該二叉樹的深度為 9；若用二叉鏈表作為該完全二叉樹的存儲結構，則共有 501 個空指針域。3 .設輸入序列為1、2、3,則經過棧的作用后可以得到 5 種不同的輸出序列。4 .設哈夫曼樹中共有99個結點，則該樹中有50 個葉子結點；若采用二叉鏈表彳為存儲結構，則該樹中有_100一個空指針域。5 .設一棵完全二叉樹的順序存儲結構中存儲數(shù)據(jù)元素為ABODEF則該二叉樹的中序遍歷序列為 DBEAFC。課程班級姓名學號密封線安 徽 工 業(yè) 大 學 試 題 紙（二）6 .設F和R分別表示

5、順序循環(huán)隊列的頭指針和尾指針，則判斷該循環(huán)隊列為空的條件為 F=R7 .設二叉樹中結點的兩個指針域分別為Ichild 和rchild，則判斷指針變量p所指向的結點為葉子結點的條件是 p->lchild=NULL&&p->rchild=NULL_ 8 .簡單選擇排序和直接插入排序算法的平均時間復雜度為 0mA2）。9 .快速排序算法的空間復雜度平均情況下為 O（log2n）,最壞的#況下為 0（nA2）。10 .散列表中解決沖突的兩種方法是 開放地址圣?口鏈地址法11 .平衡因子是指 左子樹的深度減去右子樹的深度 12 .數(shù)組A0.6,0.8 的每個元素占4個字節(jié)，將

6、其按行優(yōu)先次序存儲在起始地址為2000的內存單元中，元素A5,6的地址是 22040三、應用題。（共35分）1 .已知8個待排序的記錄，其關鍵碼分別為 53, 36, 30, 91, 47, 12, 24, 85,用希爾排序、快速排序和堆排序對其進行排序，寫出第一趟排 序后結果。（9分）答：希爾排序：1224309147533685（步長為5）快速排序：2436301247539185小堆排序：12365385473024912 .假定有字符a1, a2, a3, a4, a5在一篇文章中出現(xiàn)的次數(shù)分別為3, 2, 4, 5, 1 試以它們?yōu)槿~子結點構造哈夫曼樹，并計算WPL（8分）答：見三、

7、2圖WPL= （3+4+5） *2+ （1+2） *3=333,已知廣義表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.設一棵二叉樹的先序序列為 ABDGECF片序序列為：DGBAECH就畫出該二叉樹。（6分）答：見三、5圖四、判斷題（1*10'=10分）1、順序表結構適宜于進行順序存取，而鏈表適宜于進行隨機存取。（錯）2、兩個棧共享一片連續(xù)內存空間時，為提高內

8、存利用率，減少溢出機會，應把兩個棧的棧底分別設在這片內存空間的兩端3、一個棧的輸入序列是12345,則棧的輸出序列不可能是12345。（錯）4、用是一種數(shù)據(jù)對象和操作都特殊的線性表。（對）5、數(shù)組可看成線性結構的一種推廣，因此與線性表一樣，可以對它進行插入，刪除等操作。（錯）6、對于一棵非空二叉樹，它的根結點作為第一層，則它的第 i層上最多能有2i-1個結點。（錯）7、最小代價生成樹是唯一的。（錯）8、歸并排序的空間復雜度為O（n） （對）9、為了方便操作，一般在二叉樹排序樹中插入一個新結點，總是作為葉結點。（對 ）10、在初始數(shù)據(jù)表已經有序時，快速排序算法的時間復雜度為O（nlog2n ）。

9、（錯）五、編寫算法（28分）1、試編寫算法將兩個有序的單鏈表歸并成一個新的有序單鏈表。（10分）linklist Merge(linklist A, linklist B) /* 將有序單鏈表合并后由函數(shù)帶回*/答：LinkList Merge(LinkList A,LinkList B)LinkList p,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; elsep=p->next;q=q->

10、;next;if(!p&&q)p=q； return A;2、試編寫算法計算二叉樹中度為1的結點數(shù)。(9分)int count(bintree t) /*求二叉鏈表結構二叉樹t度為1的結點數(shù)*/答：int count(bintree t)int count=0;PSeqStack S;bintree p=t;S=Init_SeqStack();while(p|Empty_SeqStack(S)if(p)Push_SeqStack(S,p);p=p->lichild;elsePop_SeqStack(S,&p);if(p->lchild!=NULL)&&(p->rchild=NULL)|(p->lchild=NULL)&&(p->rchild!=NULL) count+;p=p->rchild;return count;3、試編寫算法在二叉排序樹T中查找值為X的算法。(9分)BinSTree BSTSearch (BinSTree t , KeyType X ,) /* 二