2013中國科學院大學考研真題之程序設計

1、科目名稱：程序設計第1頁共4頁中國科學院中國科學院大學大學202013年招收攻讀碩士學位研究生入學統(tǒng)一考試試題年招收攻讀碩士學位研究生入學統(tǒng)一考試試題科目名稱：科目名稱：程序設計程序設計考生須知：考生須知：1本試卷滿分為150分，全部考試時間總計180分鐘。2所有答案必須寫在答題紙上，寫在試題紙上或草稿紙上一律無效。一、判斷題（共一、判斷題（共10分，每小題分，每小題2分）分）(1)在快速排序、堆排序、歸并排序和插入排序中，堆排序所需要

2、的附加存儲開銷最大?！尽?2)圖的深度遍歷不適用于有向圖?！尽?3)用Prim算法和Kruskal算法分別構(gòu)造的圖的最小生成樹不一定相同?！尽?4)對一個具有n個元素的線性表，建立其有序單鏈表的時間復雜度為O(n)?！尽?5)在長度都為n的有序單鏈表和順序表上分別做順序查找，若查找每個元素的概率相等，則順序查找表中任一元素的查找成功的平均查找長度相同?！尽慷⑦x擇題（共二、選擇題（共20分，每題分，每題2分）分）1、若想把數(shù)組中的100

3、個元素調(diào)整為小根堆（或大根堆），需做【】次關鍵字值比較。A164B195C220D2572、執(zhí)行下面的程序段，語句3的執(zhí)行次數(shù)為【】。f(i=0iij)(2)state(3)A(2)2nnB(1)(2)2nn?C(1)2nnD(1)(2)nn?3、如果具有n個頂點的圖是一個環(huán)，則它有【】棵生成樹。AnB2nCn1Dn14、下面關于B樹和B樹的敘述中，不正確的是【】A.B樹和B樹都是平衡的多分樹B.B樹和B樹都是可用于文件的索引結(jié)構(gòu)C.B

4、樹和B樹都能有效地支持順序檢索科目名稱：程序設計第3頁共4頁4、設關鍵字序列為｛3，7，6，9，7，1，4，5，20｝，對其進行排序的最小交換次數(shù)是【】。5、將一個的對稱矩陣A的下三角部分按行存放在一個一維數(shù)組B中，A[0][0]存放于B[0]中，那么第i行的對角元素A[i][i]在B中的存放位置是【】。6、在一棵度為4的樹中，有20個度為4的結(jié)點，10個度為3的結(jié)點，1個度為2的結(jié)點，10個度為1的結(jié)點，則樹中度為0的結(jié)點個數(shù)為【】。

5、7、在n個結(jié)點的線索二叉樹中，線索的數(shù)目是【】。8、由權值為8，4，5，7的4個葉結(jié)點構(gòu)造一棵Huffman樹，該樹的帶權路徑長度為【】。9、中綴表達式A(BCD)E的后綴形式是【】。四、問答題（共四、問答題（共50分，分，每題每題10分）分）1、試利用Dijkstra算法求下圖中從頂點a到其它各頂點間的最短路徑，寫出執(zhí)行算法過程中各步的狀態(tài)。2、在地址空間為0~16的散列區(qū)中，對以下關鍵字序列構(gòu)造兩個哈希表：（JanFebMarApr