哈爾濱工程大學(xué)考研數(shù)據(jù)結(jié)構(gòu)真題11

1、班級(jí)： 學(xué)號(hào)： 姓名： 裝 訂 線哈爾濱工程大學(xué)試卷考試科目: 數(shù)據(jù)結(jié)構(gòu)a 卷 題號(hào)一二三四五總分分?jǐn)?shù)評(píng)卷人一、 單項(xiàng)選擇題（每空1分，共15分）1、下面說(shuō)法錯(cuò)誤的是（ ）。（1）算法原地工作的含義是指不需要任何額外的輔助空間。（2）在相同的規(guī)模n下，復(fù)雜度o(n)的算法在時(shí)間上總是優(yōu)于復(fù)雜度o(2n)的算法。 （3）所謂時(shí)間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時(shí)間的一個(gè)上界。（4）同一個(gè)算法，實(shí)現(xiàn)語(yǔ)言的級(jí)別越高，執(zhí)行效率就越低。a（1） b（1），（2）c（1），（4） d（3）2、雙向鏈表中有兩個(gè)指針域，llink和rlink，分別指向前驅(qū)及后繼，設(shè)p指向鏈表中的一個(gè)結(jié)點(diǎn)，q指向一待插入結(jié)點(diǎn)

2、，現(xiàn)要求在p前插入q，則正確的插入為（ ）。 ap->llink=q; q->rlink=p; p->llink->rlink=q; q->llink=p->llink;bq->llink=p->llink; p->llink->rlink=q; q->rlink=p; p->llink=q->rlink; cq->rlink=p; p->rlink=q; p->llink->rlink=q; q->rlink=p;dp->llink->rlink=q; q->rlin

3、k=p; q->llink=p->llink; p->llink=q;3、若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（ ）存儲(chǔ)方式最節(jié)省時(shí)間。a順序表 b雙鏈表 c帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 d單循環(huán)鏈表4、設(shè)abcdef以所給的次序進(jìn)棧，若在進(jìn)棧操作時(shí)，允許退棧操作，則下面得不到的序列為（ ）。afedcba bbcafed cdcefba dcabdef5、下面關(guān)于串的敘述中，（ ）是不正確的。a串是字符的有限序列 b空串是由空格構(gòu)成的串c模式匹配是串的一種重要運(yùn)算d串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)6、廣義表a=(a,b,(c,d)

4、,(e,(f,g)，則head(tail(head(tail(tail(a)的值為（ ）。a(g) b(d) cc dd7、將一個(gè)a1.100，1.100的三對(duì)角矩陣，按行優(yōu)先存入一維數(shù)組b1.298中，a中元素a6665（即該元素下標(biāo)i=66，j=65）在b數(shù)組中的位置k為（ ）。a198 b195 c197 8、下述二叉樹中，（ ）滿足性質(zhì)：從任一結(jié)點(diǎn)出發(fā)到根的路徑上所經(jīng)過(guò)的結(jié)點(diǎn)序列按其關(guān)鍵字有序。a二叉排序樹 b哈夫曼樹 c平衡二叉排序樹 d堆9、一棵樹高為k的完全二叉樹至少有（ ）個(gè)結(jié)點(diǎn)。a2k1 b2k-11 c2k-1 d2k10、設(shè)圖如下所示，在下面的5個(gè)序列中，符合深度優(yōu)先遍歷

5、的序列有（ ）。a e b d f c a c f d e b a e d f c b a e f d c b a e f d b ca5個(gè) b4個(gè) c3個(gè) d2個(gè) 11、具有12個(gè)關(guān)鍵字的有序表，折半查找的平均查找長(zhǎng)度為（ ）。 a3.1b4c2.5d512、對(duì)n個(gè)元素的表做順序查找時(shí)，若查找每個(gè)元素的概率相同，則平均查找長(zhǎng)度為（ ）。a(n+1)/2 bn/2 cn d(1+n)×n /213、在下列排序算法中，（ ）算法的時(shí)間復(fù)雜度與初始排序無(wú)關(guān)。a直接插入排序 b冒泡排序 c快速排序 d直接選擇排序14、對(duì)序列15，9，7，8，20，-1，4進(jìn)行排序，進(jìn)行一趟后數(shù)據(jù)的排列變?yōu)?/p>

6、4，9，-1，8，20，7，15，則采用的是（ ）排序。a選擇b快速c希爾d冒泡15、有一組數(shù)據(jù)（15，9，7，8，20，-1，7，4），用堆排序的篩選方法建立的初始堆為（ ）。a-1，4，8，9，20，7，15，7 b-1，7，15，7，4，8，20，9c-1，4，7，8，20，15，7，9 da，b，c均不對(duì)二、 判斷題（每空1分，共10分）1、健壯的算法不會(huì)因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。（ ）2、線性表的特點(diǎn)是每個(gè)元素都有一個(gè)前驅(qū)和一個(gè)后繼。（ ）3、即使對(duì)不含相同元素的同一輸入序列進(jìn)行兩組不同的合法的入棧和出棧組合操作，所得的輸出序列也一定相同。（ ）4、循環(huán)隊(duì)列也存在空間溢出

7、問題。（ ）5、一個(gè)稀疏矩陣am*n采用三元組形式表示，若把三元組中有關(guān)行下標(biāo)與列下標(biāo)的值互換，并把m和n的值互換，就完成了am*n的轉(zhuǎn)置運(yùn)算。（ ）6、對(duì)一棵二叉樹進(jìn)行層次遍歷時(shí)，應(yīng)借助于一個(gè)棧。（ ）7、在任意一棵非空二叉排序樹，刪除某結(jié)點(diǎn)后又將其插入，則所得二叉排序樹與刪除前原二叉排序樹相同。（ ）8、一個(gè)有向圖的鄰接表和逆鄰接表中結(jié)點(diǎn)的個(gè)數(shù)可能不等。 （ ）9、當(dāng)改變網(wǎng)上某一關(guān)鍵路徑上任一關(guān)鍵活動(dòng)后，必將產(chǎn)生不同的關(guān)鍵路徑。（ ）10、在9階b-樹中，除葉子以外的任意結(jié)點(diǎn)的分支數(shù)介于5和9之間。 （ ）三、 填空題（每空1分，共10分）1、數(shù)據(jù)結(jié)構(gòu)中評(píng)價(jià)算法的兩個(gè)重要指標(biāo)是_。2、當(dāng)線

8、性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素時(shí)，應(yīng)采用_存儲(chǔ)結(jié)構(gòu)。3、兩個(gè)棧共享空間時(shí)棧滿的條件是_。 4、空格串的長(zhǎng)度等于_。5、設(shè)數(shù)組a1.50,1.80的基地址為2000，每個(gè)元素占2個(gè)存儲(chǔ)單元，若以行序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素a45,68的存儲(chǔ)地址為_。6、己知三對(duì)角矩陣a1.9,1.9的每個(gè)元素占2個(gè)單元，現(xiàn)將其三條對(duì)角線上的元素逐行存儲(chǔ)在起始地址為1000的連續(xù)的內(nèi)存單元中，則元素a7,8的地址為_。7、廣義表運(yùn)算式head(tail(a,b,c),(x,y,z)的結(jié)果是_。8、高度為8的完全二叉樹至少有_個(gè)葉子結(jié)點(diǎn)。9、有向圖g=(v,e)

9、，其中v(g)=0,1,2,3,4,5，用<a,b,d>三元組表示弧<a,b>及弧上的權(quán)d，e(g)為<0,5,100>,<0,2,10>,<1,2,5>,<0,4,30>,<4,5,60>,<3,5,10>,<2,3,50>,<4,3,20>，則從源點(diǎn)0到頂點(diǎn)3的最短路徑長(zhǎng)度是_。10、在一棵m階b-樹中，若在某結(jié)點(diǎn)中插入一個(gè)新關(guān)鍵字而引起該結(jié)點(diǎn)分裂，則此結(jié)點(diǎn)中原有的關(guān)鍵字的個(gè)數(shù)是_。四、 應(yīng)用題（每題7分，共35分）1、已知長(zhǎng)度為l2的表jan,feb,mar,apr,m

10、ay,june,july,aug,sep,oct,nov,dec，按表中元素順序構(gòu)造一棵平衡二叉排序樹，并求其在等概率情況下查找成功的平均查找長(zhǎng)度。2、已知一棵二叉樹的中序遍歷序列為dgbaechif，后序遍歷序列為gdbeihfca，（1）試畫出該二叉樹；（2）試畫出該二叉樹的中序線索樹；（3）試畫出該二叉樹對(duì)應(yīng)的森林。3、給定一組權(quán)值2,3,5,7,11,13,17,19,23,29,31,37,41，試為這些字符設(shè)計(jì)哈夫曼編碼。4、根據(jù)普利姆(prim) 算法，求下圖的最小生成樹。eabgcdf5361413255、對(duì)下面的關(guān)鍵字集30,15,21,40,25,26,36,37，若查找表的裝填因子為0.8，采用線性探測(cè)再散列方法解決沖突，（1）設(shè)計(jì)哈希函數(shù)； （2）畫出哈希表；（3）計(jì)算