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

1、班級： 學(xué)號： 姓名： 裝 訂 線哈爾濱工程大學(xué)試卷考試科目: 數(shù)據(jù)結(jié)構(gòu) A卷 題號一二三四五總分分?jǐn)?shù)評卷人一、單項選擇題（每空1分，共15分）1算法的時間復(fù)雜度取決于 。A問題的規(guī)模 B. 待處理數(shù)據(jù)的初態(tài) C. A和B2鏈表不具有的特點(diǎn)是 。A插入、刪除不需要移動元素 B可隨機(jī)訪問任一元素 C不必事先估計存儲空間 D所需空間與線性長度成正比3在雙向鏈表存儲結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時須修改指針 。A p-prior-next=p-next；p-next-prior=p-prior；B p-prior= p-prior-prior；p-prior-next=p；C p-next-prior=p

2、；p-next=p-next-next；D p-next = p-prior-next； p-prior= p-next-next； 4輸入序列為ABC，可以變?yōu)镃BA時，經(jīng)過的棧操作為 。A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,popC. push,push,pop,pop,push,popD. push,pop,push,push,pop,pop5設(shè)棧S和隊列Q的初始狀態(tài)為空，元素e1，e2，e3，e4，e5和e6依次通過棧S，一個元素出棧后即進(jìn)隊列Q，若6個元素出隊的序列是e2，e4，e3，e6，e5，e1，則棧S的

3、容量至少應(yīng)該是 。A 6 B. 4 C. 3 D. 26設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主序存儲，a11為第一元素，其存儲地址為1，每個元素占一個地址空間，則a85的地址為 。A. 13B. 33C. 18D. 407廣義表運(yùn)算式GetTail(a,b),(c,d)的操作結(jié)果是 。A. (c,d) B. c,d C. (c,d) D. d8對n個元素的表做順序查找時，若查找每個元素的概率相同，則查找成功的平均查找長度為 。A(n+1)/2 B. n/2 C. n D. (1+n)n)/29設(shè)有一表示算術(shù)表達(dá)式的二叉樹，它所表示的算術(shù)表達(dá)式是 。A. A*B+C/(D*E)

4、+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+(F-G) D. A*B+C/D*E+F-G10一棵樹高為K的完全二叉樹至少有 個結(jié)點(diǎn)。A2k1B. 2k-11C. 2k-1D. 2k11若二叉樹采用二叉鏈表存儲結(jié)構(gòu)，要交換其所有分支結(jié)點(diǎn)左、右子樹的位置，利用 遍歷方法最合適。A先序 B中序 C后序 D按層次12下面結(jié)構(gòu)中最適于表示稀疏無向圖的是 。A鄰接矩陣 B逆鄰接表 C鄰接多重表 D十字鏈表13在平衡二叉樹中插入一個結(jié)點(diǎn)后造成了不平衡，設(shè)最低的不平衡結(jié)點(diǎn)為A,并已知A的左孩子的平衡因子為0，右孩子的平衡因子為1，則應(yīng)作 型調(diào)整以使其平衡。A.

5、LLB. LRC. RLD. RR14數(shù)據(jù)序列（2，1，4，9，8，10，6，20）只能是下列排序算法中的 的兩趟排序后的結(jié)果。A. 快速排序 B. 冒泡排序 C. 選擇排序 D. 插入排序15對下列關(guān)鍵字序列用快速排序法進(jìn)行排序時，速度最快的情形是 。A21,25,5,17,9,23,30 B25,23,30,17,21,5,9C21,9,17,30,25,23,5 D5,9,17,21,23,25,30 二、填空題（每空1分，共10分）1線性表L=（a1,a2,an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動元素的個數(shù)是 。2設(shè)有二維數(shù)組A0.9,0.19，其每

6、個元素占兩個字節(jié)，第一個元素的存儲地址為100，若按列優(yōu)先順序存儲，則元素A6,6存儲地址為_。3當(dāng)廣義表中的每個元素都是原子時，廣義表便成了_。4在完全二叉樹中，編號為i和j的兩個結(jié)點(diǎn)處于同一層的條件是_。5一棵樹T中，包括一個度為1的結(jié)點(diǎn)，兩個度為2的結(jié)點(diǎn)，三個度為3的結(jié)點(diǎn)，四個度為4的結(jié)點(diǎn)和若干葉子結(jié)點(diǎn)，則T的葉結(jié)點(diǎn)數(shù)為_。6已知一無向圖G=（V，E），其中V=a，b，c，d，e ，E=(a,b)，(a,d)，(a,c)，(d,c)，(b,e)，現(xiàn)用某一種圖遍歷方法從頂點(diǎn)a開始遍歷圖，得到的序列為abecd，則采用的是_遍歷方法。7. 己知有序表為(12，18，24，35，47，50，6

7、2，83，90，115，134)，當(dāng)用折半查找法查找100時，需_次才能確定不成功。8在一棵m階B-樹中，若在某結(jié)點(diǎn)中插入一個新關(guān)鍵字而引起該結(jié)點(diǎn)分裂，則此結(jié)點(diǎn)中原有的關(guān)鍵字的個數(shù)是_。9分別采用堆排序、快速排序、冒泡排序和歸并排序，對初態(tài)為有序的表，則最省時間的是_算法。10不受待排序初始序列的影響，時間復(fù)雜度為O(n2)的排序算法是_。三、判斷題（每空1分，共10分）1順序存儲方式的優(yōu)點(diǎn)是存儲密度大，且插入、刪除運(yùn)算效率高。 ( )2線性表的特點(diǎn)是每個元素都有一個前驅(qū)和一個后繼。( )3循環(huán)隊列也存在空間溢出問題。( )4一個稀疏矩陣Am*n采用三元組形式表示，若把三元組中有關(guān)行下標(biāo)與列下

8、標(biāo)的值互換，并把m和n的值互換，則就完成了Am*n的轉(zhuǎn)置運(yùn)算。 ( )5一棵樹中的葉子數(shù)一定等于與其對應(yīng)的二叉樹的葉子數(shù)。( )6用鄰接矩陣存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小與圖中結(jié)點(diǎn)個數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。( )7在任意一棵非空二叉排序樹中，刪除某結(jié)點(diǎn)后又將其插入，則所得二排序叉樹與原二排序叉樹相同。( )8在初始數(shù)據(jù)表已經(jīng)有序時，快速排序算法的時間復(fù)雜度為O(nlog2n )。( )9堆排序是穩(wěn)定的排序方法。( )10在任何情況下，歸并排序都比直接插入排序快。 ( )四、應(yīng)用題（每題7分，共35分）1采用哈希函數(shù)H(k)=3*k MOD 13，并用線性探測開放

9、地址法處理沖突，在數(shù)列地址空間0.12中對關(guān)鍵字序列22、41、53、46、30、13、1、67、51，（1）構(gòu)造哈希表（畫示意圖）；（2）求等概率下成功的平均查找長度。2一棵二叉樹的先序、中序序列如下，請構(gòu)造出該二叉樹，并進(jìn)行后序線索化。先序序列 ：A B D H I M E J C F K L G中序序列 ：H D I M B J E A K F L C G3給出一組關(guān)鍵字29，18，25，47，58，12，51，10，寫出堆排序的過程（包括初始建大頂堆、堆頂每取下一個元素后堆調(diào)整）。4給定一組權(quán)值2、3、5、7、11、13、17、19、23、29、31、37、41，試畫出哈夫曼樹。5用克魯斯卡爾算法構(gòu)造下圖的一棵最小生成樹，并給出選邊順序。五、算法設(shè)計題（每題15分，共30分）1有一個帶頭結(jié)點(diǎn)的單鏈表，頭指針為head，它的數(shù)據(jù)域的類型為整型，而且按自小到大的順序排列，編寫一個算法insertx_lis