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

1、科目名稱：程序設(shè)計(jì)第1頁共4頁中國科學(xué)院研究生院中國科學(xué)院研究生院20201212年招收攻讀碩士學(xué)位研究生入學(xué)統(tǒng)一考試試題年招收攻讀碩士學(xué)位研究生入學(xué)統(tǒng)一考試試題科目名稱：科目名稱：程序設(shè)計(jì)程序設(shè)計(jì)考生須知：考生須知：1本試卷滿分為150分，全部考試時(shí)間總計(jì)180分鐘。2所有答案必須寫在答題紙上，寫在試題紙上或草稿紙上一律無效。一、判斷題（共一、判斷題（共10分，每小題分，每小題2分）分）(1)Floyd算法求兩個(gè)頂點(diǎn)的最短路徑時(shí)，pa

2、thk1一定是pathk的子集?！尽?2)在快速排序、堆排序、歸并排序和插入排序中，堆排序所需要的附加存儲(chǔ)開銷最大?！尽?3)用Prim算法和Kruskal算法分別構(gòu)造的圖的最小生成樹不一定相同?！尽?4)在結(jié)點(diǎn)數(shù)多于1的哈夫曼樹中不存在度為1的結(jié)點(diǎn)?！尽?5)在長度都為n的有序單鏈表和順序表上分別做順序查找，若查找每個(gè)元素的概率相等，則順序查找表中任一元素的查找成功的平均查找長度相同?！尽慷?、選擇題（共二、選擇題（共20分，每題分，每

3、題2分）分）1、在存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，而且還要存儲(chǔ)【】。A數(shù)據(jù)的操作方法B數(shù)據(jù)的存取方法C數(shù)據(jù)元素之間的關(guān)系D數(shù)據(jù)元素的類型2、程序段f(i=n1i1i)f(j=1jA[j1])A[j]與A[j1]對換其中n為正整數(shù)，則最后一行的語句頻度在最壞情況下是【】。AO(n)BO(n2)CO(nlog2n)D不直接依賴于n3、在順序表的動(dòng)態(tài)存儲(chǔ)定義中需要包含的數(shù)據(jù)成員是【】I數(shù)組基址baseII表中元素個(gè)數(shù)nIII數(shù)組指針

4、dataIV表的大小maxSizeAII、IIIBI、II、IIICII、III、IVD全部需要科目名稱：程序設(shè)計(jì)第3頁共4頁5、已知一個(gè)長度為16的順序表，其元素按關(guān)鍵字有序排列，若采用折半查找一個(gè)不存在的元素，則比較的次數(shù)至少是【】，至多是【】。6、一棵赫夫曼樹共有215個(gè)結(jié)點(diǎn)，對其進(jìn)行赫夫曼編碼，共能得到【】個(gè)不同的碼字。7、一個(gè)有n個(gè)頂點(diǎn)和n條邊的無向圖一定是【】。8、在含有n個(gè)頂點(diǎn)和e條邊的無向圖的鄰接矩陣中，零元素的個(gè)數(shù)為【

5、】。四、問答題（共四、問答題（共50分，分，每題每題10分）分）1、一個(gè)算法所需時(shí)間由下述遞歸方程表示，試求出該算法的時(shí)間復(fù)雜度級別。T(n)=?1若n=12T?n2?n若n1式中，n是問題規(guī)模，設(shè)n是2的整數(shù)冪。2、依次把結(jié)點(diǎn)（34，23，15，98，115，28，107）插入到初始狀態(tài)為空的平衡二叉排序樹中，使得每次插入后保持該樹仍然是平衡二叉樹。請依次畫出每次插入后所形成的平衡二叉排序樹。3、試為下列每種情況選擇合適的排序方法：（

6、1）n=30，要求最壞情況下速度最快；（2）n=30，要求既快又要排序穩(wěn)定；（3）n=1000，要求平均情況下速度最快；（4）n=1000，要求最壞情況下速度最快且穩(wěn)定；（5）n=1000，要求既快又最省內(nèi)存。4、將下列遞推過程改寫為遞歸過程。voidditui(intn)intii=nwhile(i1)printf(i)5、設(shè)有序順序表的元素依次為017、094、154、170、275、503、509、512、553、612、677、