2013中國科學(xué)院大學(xué)考研真題之計算機(jī)軟件基礎(chǔ)

1、中國科學(xué)院中國科學(xué)院大學(xué)大學(xué)20132013年招收攻讀碩士學(xué)位研究生入學(xué)統(tǒng)一考試試題年招收攻讀碩士學(xué)位研究生入學(xué)統(tǒng)一考試試題科目名稱：計算機(jī)軟件基礎(chǔ)科目名稱：計算機(jī)軟件基礎(chǔ)考生須知：考生須知：1本試卷滿分為150分，全部考試時間總計180分鐘。2所有答案必須寫在答題紙上，寫在試題紙上或草稿紙上一律無效。第一部分：第一部分：數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（共70分）一、一、單選單選題（每題題（每題2分，共，共20分）分）1.下列關(guān)于數(shù)據(jù)的邏輯結(jié)構(gòu)的敘

2、述中，不正確的是【】。(A)數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)間關(guān)系的描述(B)線性表是典型的線性結(jié)構(gòu)(C)數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)(D)數(shù)據(jù)的邏輯結(jié)構(gòu)不僅反映數(shù)據(jù)間的邏輯關(guān)系，而且包含其在計算機(jī)中的存儲方式2.下列關(guān)于數(shù)據(jù)運算的敘述中，不正確的是【】。(A)數(shù)據(jù)運算是數(shù)據(jù)結(jié)構(gòu)的一個重要方面(B)數(shù)據(jù)運算的具體實現(xiàn)是在數(shù)據(jù)的邏輯結(jié)構(gòu)上進(jìn)行(C)檢索是一種常用的運算(D)插入是一種常用的運算3.在包含1000個元素的線性表中實現(xiàn)如下各運算

3、，所需執(zhí)行時間最長的是【】。(A)線性表按順序方式存儲，刪除線性表的第900個結(jié)點(B)線性表按鏈?zhǔn)椒绞酱鎯?，刪除指針P所指向的結(jié)點(C)線性表按順序方式存儲，在線性表的第100個結(jié)點后面插入一個新結(jié)點(D)線性表按鏈?zhǔn)椒绞酱鎯?，在線性表的第100個結(jié)點后面插入一個新結(jié)點科目名稱：計算機(jī)軟件基礎(chǔ)第1頁共7頁5.如果在排序前，關(guān)鍵字序列已接近正序或逆序，則在堆排序和快速排序兩者之中，選用______較為適當(dāng)。6空串的長度是______；空

4、格串的長度是______的數(shù)目。7.已知指針p指向單鏈表中某個結(jié)點，則語句pnext=pnextnext的作用是______。8.產(chǎn)生沖突現(xiàn)象的兩個關(guān)鍵字稱為該散列函數(shù)的______。9.有29條邊的無向連通圖，至少有______個頂點，至多有______個頂點。10設(shè)有100個元素的排序順序文件中，采用折半查找，最大比較次數(shù)為______，最小為______。三、問答題（每題三、問答題（每題5分，分，30分）分）1.評價一個好的算法，

5、您是從哪幾方面來考慮的？2.試說明一棵二叉樹無論進(jìn)行前序、中序或后序遍歷，其葉結(jié)點的相對次序不發(fā)生改變。3.畫出向小根堆中加入數(shù)據(jù)42583時，每加入一個數(shù)據(jù)后堆的變化（每加入一個數(shù)據(jù)后，都需要進(jìn)行調(diào)整成為小根堆）。4.設(shè)有以下三個函數(shù)：()10002124=nnnf，()3450015nnng=，()nnnnhlog5005.3=請判斷以下斷言正確與否：(1)f(n)是O(g(n))(2)h(n)是O(f(n))(3)g(n)是O(h