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

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

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

3、，樹中任一結(jié)點(diǎn)的()。A.左、右子樹高度差的絕對值不超過1B.左、右子樹的高度均相同C.左子樹的高度均大于右子樹的高度D.左子樹的高度均小于右子樹的高度第頁（共3頁）34（12分）請閱讀下列算法，回答問題。f(i=2i=L.lengthi)if(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.

4、r[0]①這是什么類型的排序算法？；②該排序算法穩(wěn)定嗎？③該排序算法的時間復(fù)雜度與關(guān)鍵字的初始排列順序有沒有關(guān)系？④假定設(shè)待排序的關(guān)鍵字序列為12，2，16，30，28，10，16，20，6，18，請寫出使用該排序方法，每趟排序結(jié)束后關(guān)鍵字序列的狀態(tài)。5.（12分）假定對有序表：（3，4，5，7，24，30，42，54，63，72，87，95）進(jìn)行折半查找，試回答下列問題：①畫出描述折半查找過程的判定樹；②若查找元素54，需依次與哪些元

5、素比較？③若查找元素90，需依次與哪些元素比較？④假定每個元素的查找概率相等，求查找成功時的平均查找長度。三、算法設(shè)計題（三、算法設(shè)計題（60分）分）1.（20分）將兩個遞增的有序鏈表合并為一個遞增的有序鏈表。要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間不另外占用其它的存儲空間。表中不允許有重復(fù)的數(shù)據(jù)。（1）描述算法的基本設(shè)計思想；（2）用類C的語言描述該算法，關(guān)鍵之處給出簡要注釋。2.（20分）以二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，編寫以下算法