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

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

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

3、，需向后移動(dòng)（）個(gè)元素n-in-i+1n-i-1i() 設(shè)有一個(gè)棧，元素的進(jìn)棧次序?yàn)橄?)是不能的出棧序列A，B，C，D，EB，C，D，E，AE，A，B，C，DE，D，C，B，A() 具有842 個(gè)結(jié)點(diǎn)的完全三叉樹，其葉子結(jié)點(diǎn)共有（）個(gè)A.421B. 422C.420D.423E.以上都不是4.（）順序查找方法適用于存儲(chǔ)結(jié)構(gòu)為（）的線性表A.壓縮存儲(chǔ)B. 散列存儲(chǔ)C. 順序存儲(chǔ)D. 鏈?zhǔn)酱鎯?chǔ)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 個(gè)結(jié)點(diǎn)（i 1 開始用上述方法編號(hào)）A中的位置是（ ）A. A2i (2i=n) B.A2i+1 (2i+1=n) C. Ai/2 D.條件不充分，無(wú)法確定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 的拓?fù)湫蛄兄?，若頂點(diǎn)Vi 在頂點(diǎn)Vj 之前，則下列情形可能出現(xiàn)的是()A.G中有弧B.G中有一條從Vi 到Vj 的路徑C.G 中沒(méi)有弧D. G 中有一條從Vj 到Vi 的路徑( )FBm 個(gè)結(jié)點(diǎn)，Bp，p nF中第一棵樹的結(jié)點(diǎn)個(gè)數(shù)是( )A.m-nB. m-n-1C. n+1D. 條件不足，無(wú)法確定判斷題（在括號(hào)內(nèi)填上“”或“1 10 分，做錯(cuò)不倒扣）（）在?？盏那闆r下，不能做退棧運(yùn)算，否則產(chǎn)生下溢。() 任何一棵前序線索二叉樹，都可以不用棧實(shí)現(xiàn)前序遍歷。（）就平均查找長(zhǎng)度而言，分塊查找最小，折半查找次之，順序查找最大（）Shell 方法排序時(shí)，若關(guān)鍵字的排列雜亂無(wú)序

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

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

8、整。注：圖的頂點(diǎn)號(hào)從0開始計(jì)；indegree是有n個(gè)分量的一維數(shù)組，放頂點(diǎn)的入度；函數(shù)crein用于計(jì)算頂點(diǎn)的入度；有三個(gè)函數(shù)push(data)pop(check(data退棧和測(cè)試棧是否為空（不空返回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ù)元素的算法補(bǔ)充完整。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、 都是中心對(duì)稱的字符串。試卷答案一、填空題（每空1.5 分，共15 分）1456直接定址2.。7.160ms3 418.31個(gè)中間結(jié)點(diǎn)4B的度是 49 2個(gè)二叉排序10.4 次單項(xiàng)選擇題（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 （ ）四、畫圖/計(jì)算/證明/算法分析 (30 分)葉結(jié)點(diǎn)的相對(duì)次序是不會(huì)發(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