2016青島科技大學(xué)碩士研究生考研真題-數(shù)據(jù)結(jié)構(gòu)

1、第頁(yè)（共3頁(yè)）1青島科技大學(xué)二○一六一六年碩士研究生士研究生入學(xué)考入學(xué)考試試試試題考試科目：數(shù)據(jù)結(jié)構(gòu)考試科目：數(shù)據(jù)結(jié)構(gòu)注意事項(xiàng)：1本試卷共三道大題（共計(jì)23個(gè)小題），滿分150分；2本卷屬試題卷，答題另有答題卷，答案一律寫(xiě)在答題卷上，寫(xiě)在該試題卷上或草紙上均無(wú)效。要注意試卷清潔，不要在試卷上涂劃；3必須用藍(lán)、黑鋼筆或簽字筆答題，其它均無(wú)效。﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡一、選擇題一、選

2、擇題(每個(gè)每個(gè)2分，共分，共3030分)1、在長(zhǎng)度為n的順序表的第i(1≤i≤n1)個(gè)位置上刪除一個(gè)元素，移動(dòng)元素的個(gè)數(shù)為()。A.i1B.ni1C.iD.ni2、以下哪一個(gè)術(shù)語(yǔ)與數(shù)據(jù)的邏輯結(jié)構(gòu)無(wú)關(guān)？（）A哈希表B.棧C.二叉樹(shù)D.線性表3、下面程序段的時(shí)間復(fù)雜度為_(kāi)___________。f(inti=0i=1）的滿三叉樹(shù)中，結(jié)點(diǎn)總數(shù)為（）。A.3kB.3k1C.（3k1）3D.（3k1）28、AVL樹(shù)是一種平衡的二叉排序樹(shù)，樹(shù)中任一

3、結(jié)點(diǎn)的()。A.左、右子樹(shù)高度差的絕對(duì)值不超過(guò)1B.左、右子樹(shù)的高度均相同C.左子樹(shù)的高度均大于右子樹(shù)的高度D.左子樹(shù)的高度均小于右子樹(shù)的高度第頁(yè)（共3頁(yè)）3if(L.r[i].keyL.r[i1].key)L.r[0]=L.r[i]復(fù)制為監(jiān)視哨f(j=i1L.r[0].keyL.r[j].keyj)L.r[j1]=L.r[j]記錄后移L.r[j1]=L.r[0]①這是什么類(lèi)型的排序算法？；②該排序算法穩(wěn)定嗎？③該排序算法的時(shí)間復(fù)雜度與

4、關(guān)鍵字的初始排列順序有沒(méi)有關(guān)系？④假定設(shè)待排序的關(guān)鍵字序列為12，2，16，30，28，10，16，20，6，18，請(qǐng)寫(xiě)出使用該排序方法，每趟排序結(jié)束后關(guān)鍵字序列的狀態(tài)。5.（12分）假定對(duì)有序表：（3，4，5，7，24，30，42，54，63，72，87，95）進(jìn)行折半查找，試回答下列問(wèn)題：①畫(huà)出描述折半查找過(guò)程的判定樹(shù)；②若查找元素54，需依次與哪些元素比較？③若查找元素90，需依次與哪些元素比較？④假定每個(gè)元素的查找概率相等，求查

5、找成功時(shí)的平均查找長(zhǎng)度。三、算法設(shè)計(jì)題（三、算法設(shè)計(jì)題（60分）分）1.（20分）將兩個(gè)遞增的有序鏈表合并為一個(gè)遞增的有序鏈表。要求結(jié)果鏈表仍使用原來(lái)兩個(gè)鏈表的存儲(chǔ)空間不另外占用其它的存儲(chǔ)空間。表中不允許有重復(fù)的數(shù)據(jù)。（1）描述算法的基本設(shè)計(jì)思想；（2）用類(lèi)C的語(yǔ)言描述該算法，關(guān)鍵之處給出簡(jiǎn)要注釋。2.（20分）以二叉鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，編寫(xiě)以下算法：（1）判別兩棵樹(shù)是否相等；（2）交換二叉樹(shù)每個(gè)結(jié)點(diǎn)的左孩子和右孩子。3.（20分