《數(shù)據(jù)結(jié)構(gòu)與算法》試卷與答案5

1、 PAGE PAGE 9廣州大學(xué)學(xué)年第學(xué)期考試卷課程 數(shù)據(jù)結(jié)構(gòu)與算法考試形式（閉卷，考試）信息學(xué)院 系 專業(yè) 級 班 學(xué)號： 姓名：題次一二三四五六總分評卷人分數(shù)評分201010302010100（2 20 分）具有10 個頂點的無向圖，邊的總數(shù)最多為。n0 為哈夫曼樹的葉子結(jié)點數(shù)目，則該哈夫曼樹共有 個結(jié)點。設(shè)有一個10 階的對稱矩陣A，采用壓縮存儲方式以行序為主序存儲 為第一個元素，其存儲地址為0，每個元素占有1個存儲地址空間，則a85 的址為。A3BAB的度是一個無序序列可以通過構(gòu)造一棵樹而變成一個有序序列，造樹的過程即為對無序序列進行排序的過程。法構(gòu)造的哈希函數(shù)肯定不會發(fā)生沖突。求從某

2、源點到其余各頂點的Dijkstra算法，當圖的頂點數(shù)為10，用鄰接矩表示圖時計算時間約為10ms則當圖的頂點數(shù)為40時計算時間為ms設(shè)一棵后序線索樹的高度是結(jié)點x 是樹中的一個結(jié)點其雙親是結(jié)點 y 的右子樹高度是31x是y的左孩子則確定x的后繼最多需經(jīng)過個中間結(jié)點（不含后繼及x 本身）對于單向鏈表，在兩個結(jié)點之間插入一個新結(jié)點時需修改的指共有個。10 .有一個有序表為1,3,9,12,32,41,45,62,75,77,82,95,10082 的結(jié)點時，經(jīng)過次比較查找成功。二、單項選擇題（每題 1 分，共 10 分）()在一個長度為n 的順序表中向第i 個元素（0i=n+1）之前插入一新元素時

3、，需向后移動（）個元素n-in-i+1n-i-1i() 設(shè)有一個棧，元素的進棧次序為下()是不能的出棧序列A，B，C，D，EB，C，D，E，AE，A，B，C，DE，D，C，B，A() 具有842 個結(jié)點的完全三叉樹，其葉子結(jié)點共有（）個A.421B. 422C.420D.423E.以上都不是4.（）順序查找方法適用于存儲結(jié)構(gòu)為（）的線性表A.壓縮存儲B. 散列存儲C. 順序存儲D. 鏈式存儲E以上都不是5.（）以下序列不是堆的是（） 100，85，98，77，80，60，82，40，20，10，66） B. （100，98，85，82，80，77，66，60，40，20，10） C10，20，

4、40，60，66，77，80，82，85，98，100） 100，85，40，77，80，60，66，98，82，10，20）6（）可采用的查找方法是（）分塊查找 B. 順序查找 C. 折半查找 D. 基于屬性（ ）n A1.ni 個結(jié)點（i 1 開始用上述方法編號）A中的位置是（ ）A. A2i (2i=n) B.A2i+1 (2i+1=n) C. Ai/2 D.條件不充分，無法確定8（ ）53303712452496）A.45，24，53，12，37，96，30B. 37，24，12，30，53，45，96C. 12，24，30，37，45，53，96D. 30，24，12，37，45，9

5、6，539()在有向圖G 的拓撲序列中，若頂點Vi 在頂點Vj 之前，則下列情形可能出現(xiàn)的是()A.G中有弧B.G中有一條從Vi 到Vj 的路徑C.G 中沒有弧D. G 中有一條從Vj 到Vi 的路徑( )FBm 個結(jié)點，Bp，p nF中第一棵樹的結(jié)點個數(shù)是( )A.m-nB. m-n-1C. n+1D. 條件不足，無法確定判斷題（在括號內(nèi)填上“”或“1 10 分，做錯不倒扣）（）在?？盏那闆r下，不能做退棧運算，否則產(chǎn)生下溢。() 任何一棵前序線索二叉樹，都可以不用棧實現(xiàn)前序遍歷。（）就平均查找長度而言，分塊查找最小，折半查找次之，順序查找最大（）Shell 方法排序時，若關(guān)鍵字的排列雜亂無序

6、，則效率最高。（）在任何條件下，快速排序的效率總是最好的。（）兩叉樹是樹的一種特殊情況。（）NN-1條邊（）拓撲排序是判斷一個有向圖是否存在回路的唯一方法。（）T中，先刪除結(jié)點NN，得到新的二叉排序樹 T1，則 T 和 T1 相同。（）棧和隊列都是限制存取點的線性結(jié)構(gòu)。四、畫圖/計算/證明 (30 分)1 試說明一棵二叉樹進行前序、中序、后序遍歷，其葉結(jié)點的相對次序是否會發(fā)生改變？為什么？（5 分）2n m 節(jié)省多少？（設(shè)鏈域占兩個單元，數(shù)據(jù)域占一個單元（5 分）已知一棵二叉樹的中序遍歷序列為 :BAFDJGCKHLEIMBFJGDKLHMIECA.請完成（6分）構(gòu)造出這顆二叉樹；畫出這顆二叉

7、樹中序線索化后的結(jié)構(gòu)8 （5 分）(9分) V=a,b,c,d,e,f; E=,請畫出該圖，并寫出鄰接矩陣a出發(fā)的深度優(yōu)先和廣度優(yōu)先遍歷序列畫出由此得到的深度優(yōu)先和廣度優(yōu)先生成樹（或森林）五. 程序填空題 （20 分，每個函數(shù) 5 分）用鏈表表示數(shù)據(jù)的簡單選擇排序，結(jié)點的域為數(shù)據(jù)域data，指針域nexthead，鏈表無頭結(jié)點。selectsort(head) p=head;while (p) q=p;r=;while ()if ( q-next-data r-data )r=;tmp=q-data;q-data=p-data; p-data=tmp;p=;n個頂點的有向圖用鄰接矩陣array

8、整。注：圖的頂點號從0開始計；indegree是有n個分量的一維數(shù)組，放頂點的入度；函數(shù)crein用于計算頂點的入度；有三個函數(shù)push(data)pop(check(data退棧和測試棧是否為空（不空返回1，否則返回0。# include crein (array, indegree, for (i=0; in; i+)indegreei=;for (i=0; in; i+) for (j=0; jn; indegreei+=array ;topsort( array, indegree, n)count=for (i=0; in; i+)if ()push(i); while (check

9、( )coutvex; count+;for (i=0; in; i+)k=array;if () indegreei-;if ()push(i);latypedef struct Datatype listMaxnum; int num; SeqList;試將下面刪除順序表 la 中所有值為 x 的數(shù)據(jù)元素的算法補充完整。void DeleteSeqList ( SeqList * la, Datatype x)int j, k;for (j=1; jnum; j+) if ()for (k=j; knum; k+);la-num-;j-;四、編寫算法（10 分）n xyzzyx xyzyx

10、 都是中心對稱的字符串。試卷答案一、填空題（每空1.5 分，共15 分）1456直接定址2.。7.160ms3 418.31個中間結(jié)點4B的度是 49 2個二叉排序10.4 次單項選擇題（1.5 15 分1. ( B )2. ( C )ECA5.（D）6.（A）7.（D）8（）9( D)10. ( A)（1.5 15 ）1 （）2( )3 （）4 （）5 （ ）6 （）7 （）8 （ ）9 （ ）10 （ ）四、畫圖/計算/證明/算法分析 (30 分)葉結(jié)點的相對次序是不會發(fā)生改變的。2 節(jié) 省 n(2m+1)-5n=2n(m-2)3.(1)二叉樹為ABCDE(2) (略)4.FGHIMJKLASL=(1+2*2+3*4+4)/8=21/85. (9 分) V=a,b,c,d,e,f; E=,(1) (略)深度優(yōu)先序列：a b d e c f廣度優(yōu)先序列：a b d e c f深度優(yōu)先森林：廣度優(yōu)先遍歷森林為acacbdfbdefe五. 程序填空題 （15 分，每小題 5 分）10while (p!=NULL)r=p; 或 p-next 或 q while (q-next!=NULL) 或 r!=NULLr=q-next; 或 r-next p=p-next