2013中國(guó)科學(xué)院大學(xué)考研真題之程序設(shè)計(jì)

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

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

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

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

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