愛考：2013年計(jì)算機(jī)專業(yè)數(shù)據(jù)結(jié)構(gòu)考研模擬題及答案

1、計(jì)算機(jī)專業(yè)考研數(shù)據(jù)結(jié)構(gòu)模擬練習(xí)題來源：愛考機(jī)構(gòu)1.下面算法的吋間復(fù)朵度為。0(n) B. 0(2)C. 0(log2) D . 0(喬)2若耍在0(1)的吋間復(fù)朵度實(shí)現(xiàn)兩個(gè)循環(huán)鏈衣頭尾相接，則對(duì)應(yīng)兩個(gè)循環(huán)鏈衣各設(shè)置一個(gè)指針，分別指向各口的頭節(jié)點(diǎn)C.各口的笫一個(gè)元索節(jié)點(diǎn)各口的尾節(jié)點(diǎn)D. 一個(gè)衣的頭節(jié)點(diǎn)，一個(gè)衣的尾節(jié)點(diǎn)pn,設(shè)n個(gè)元索進(jìn)棧序列足1, 2, 3,若Pl=3,則p2的值為。定是2 B.定是1，n,其輸出序列足pl, p2, p3, 不可能足1 D.以匕都不止確設(shè)離度為h的二叉樹只冇度為0和度為2的節(jié)點(diǎn)，則此類二叉樹中所包含的節(jié)點(diǎn)數(shù)至 少為。A. 2hB. 2h+lC. 2hTD. h-

2、1對(duì)丁二叉排序樹，下面的說法是止確的。二叉排序樹是動(dòng)態(tài)樹表，查找不成功吋插入新結(jié)點(diǎn)吋，會(huì)引起樹的重新分裂和組合對(duì)二叉排序樹進(jìn)行蜃序遍歷可得到冇序序列用逐點(diǎn)插入法構(gòu)造二叉排序樹吋，若先后插入的關(guān)鍵字冇序，二叉排序樹深度最人在二叉排序樹中進(jìn)行查找，關(guān)鍵字的比較次數(shù)不會(huì)超過結(jié)點(diǎn)數(shù)的1/2設(shè)X足樹T中的個(gè)非根節(jié)點(diǎn)，B足T所對(duì)應(yīng)的二叉樹。在B中，X足其雙親的右孩了，下列結(jié)論止確的是。在樹T中，X是其雙親的第個(gè)孩了在樹T中，X M 定無右邊兄弟在樹T中，X 定是葉了結(jié)點(diǎn)在樹T種，X 定冇左邊兄弟若一個(gè)冇向圖具冇拓?fù)渑判蛐蛄?，那么它的鄰接矩陣必定為。A.對(duì)稱矩陣B.稀疏矩陣C.二角矩陣D. 般矩陣判斷個(gè)冇向

3、圖是否存在回路的方法除了可以利用拓?fù)渑判虻姆椒ㄍ?，還可以使用A.求關(guān)鍵路徑的方法B.求最短路徑的Dijikstra方法C.廣度優(yōu)先遍歷算法D.深度優(yōu)先遍歷算法下列數(shù)據(jù)結(jié)構(gòu)，查找效率最低的是。A.冇序順序衣B.二叉排序樹C.堆D . B-樹10在基丁關(guān)鍵字比較的算法中,算法在最壞的情況下的吋間復(fù)朵度不高丁O(nlog2 n )。A.冒泡排序B.川并排序C.希爾排序D.快速排序11用肓接插入排序方法對(duì)下面四個(gè)序列進(jìn)行排序(由小到人)，元索的比較次數(shù)戢少A. 94, 32, 40, 90,80, 46,21,69B. 32, 40, 21, 46,69, 94,90,80C. 21, 32, 46,

4、 40,80, 69,90,94D. 90, 69, 80, 46,2L 32,94,4012.已知加權(quán)冇向圖G的鄰接矩陣如下: 15 4 TOC o 1-5 h z 21268439510 畫出該冇向圖G,設(shè)頂點(diǎn)分別為a, b, c, d, e, f, g.。試用Dijkstra算法求G屮從頂點(diǎn)a到其他各頂點(diǎn)間的戢短路徑，并給出求解過程13.設(shè)計(jì)一個(gè)算法，判斷一個(gè)帶頭結(jié)點(diǎn)的雙向循環(huán)鏈衣DL是否對(duì)稱相等。(比如衣(25, 34, 34, 25)和農(nóng)(25, 3, 25)為對(duì)稱的)其中結(jié)點(diǎn)結(jié)構(gòu)為：struct NodeElemType data; / ElemType代農(nóng)某種數(shù)據(jù)類型Node *

5、Llink, Rlink;給出算法的基本設(shè)計(jì)思想。根據(jù)設(shè)計(jì)思想，采用C或C+或JAVA語言描述算法，關(guān)鍵之處給出注釋。計(jì)算機(jī)專業(yè)考研數(shù)據(jù)結(jié)構(gòu)模擬練習(xí)題答案111： DBCCC DCDCB C(2)sd0 path0dl pat hld2 path2d3 path3d4 path4d5 pat h5d6 patha0,-115,02,012,0 , _1 , _1 ,c0,-115,02,012,010,26,2 ,f0,-115,02,012,010,26,216, 5e0,-115,02,012,010,26,216,5d0,-115,02,012,010,26,215,3b0,-115,02,012,010,26,215,3f0,-115,02,012,010,26,215,313. (1)算法的基本思想如下：分別設(shè)置左右指針，從兩邊向中間移動(dòng)，同時(shí)判斷是否 對(duì)稱，當(dāng)左右兩個(gè)指針碰頭或者交叉時(shí)終止。(2)算法描述如下：bool isSym(Node *h)Node *l=h-Llink;Node fr=h-Rlink ;if (1=NULL | | r=NULL) return true; /鏈表為空while(l!