重慶小碼王C++期末測試題三附答案

重慶小碼王C++期末測試題三[復(fù)制]基本信息：[矩陣文本題]*姓名：________________________班級編號：________________________所屬校區(qū):________________________注意：考試時間90分鐘一選擇題（共40分，每題2分）1.以下關(guān)于棧的特性描述正確的是（）[單選題]*A.遵循先進(jìn)先出的原則B.可以讓數(shù)據(jù)進(jìn)行插入操作C.可以從棧尾訪問數(shù)據(jù)D.遵循先進(jìn)后出的原則(正確答案)2.以下關(guān)于棧的關(guān)鍵字正確的是（）[單選題]*A.queueB.frontC.stack(正確答案)D.array3.以下鏈表和數(shù)組的區(qū)別錯誤的是（）[單選題]*A.鏈表是鏈?zhǔn)降拇鎯Y(jié)構(gòu)B.數(shù)組是順序的存儲結(jié)構(gòu)C.數(shù)組插入數(shù)據(jù)會比鏈表更加簡單，不需要移動元素(正確答案)D.兩種結(jié)構(gòu)均可實(shí)現(xiàn)數(shù)據(jù)的順序存儲，構(gòu)造出來的模型呈線性結(jié)構(gòu)。4.下面的故事與以下哪種算法有著異曲同工之妙（）

從前有座山，山里有座廟，廟里有個老和尚在給小和尚講故事：“從前有座山，山里有座廟，廟里有個老和尚在給小和尚講故事：‘從前有座山，山里有座廟，廟里有個老和尚在給小和尚講故事’”[單選題]*A.枚舉B.遞歸(正確答案)C.貪心D.分治5.下圖中所使用的數(shù)據(jù)結(jié)構(gòu)是()

[單選題]*A.隊(duì)列B.棧(正確答案)C.鏈表D.二叉樹6.同時查找2n個數(shù)中的最大值和最小值，最少比較次數(shù)為（）。[單選題]*A.3(n-2)/2B.4n-2C.3n-2(正確答案)D.2n-27.在下列關(guān)于算法復(fù)雜性的說法中，正確的是（）[單選題]*A.算法的時間復(fù)雜度，是指它在某臺計(jì)算機(jī)上具體實(shí)現(xiàn)時的運(yùn)行時間B.算法的時間復(fù)雜度，是指對于該算法的一種或幾種主要的運(yùn)算，運(yùn)算的次數(shù)與問題的規(guī)模之間的函數(shù)關(guān)系(正確答案)C.空間復(fù)雜度，是指它在某臺計(jì)算機(jī)上具體實(shí)現(xiàn)時的內(nèi)存占用空間D.一個算法的優(yōu)劣主要從算法的執(zhí)行時間衡量。8.排序算法是穩(wěn)定的意思是：關(guān)鍵碼相同的記錄排序前后相對位置不發(fā)生改變，下列哪種排序算法是不穩(wěn)定的（）[單選題]*A.冒泡排序B.插入排序C.歸并排序D.快速排序(正確答案)9.以下時間復(fù)雜度不是O(n2)的排序方法是（）。[單選題]*A.插入排序B.歸并排序(正確答案)C.冒泡排序D.選擇排序10.對于入棧順序?yàn)閍,b,c,d,e,f,g的序列，下列不合法出棧序列是()[單選題]*A.a,b,c,d,e,f,gB.a,d,c,b,e,g,fC.a,d,b,c,g,f,e(正確答案)D.g,f,e,d,c,b,a11.鏈表不具有的特點(diǎn)是（）[單選題]*A.插入刪除不需要和移動元素B.不必事先估計(jì)存儲空間C.所需空間與線性表成正比D.可隨機(jī)訪問任一元素(正確答案)12.319和377的最大公約數(shù)是（）[單選題]*A.27B.33C.29(正確答案)D.3113.甲、乙、丙三位同學(xué)選修課程，從4門課中，甲選修2門，乙、丙各選修3門，則不同的選修方案共有多少種()[單選題]*A.36B.48C.96(正確答案)D.19214.向一個棧頂指針為hs的鏈?zhǔn)綏Ｖ胁迦胍粋€指針s指向的結(jié)點(diǎn)時，應(yīng)執(zhí)行()[單選題]*A.hs->next=s;B.s->next=hs;hs=s;(正確答案)C.s->next=hs->next;hs->next=s;D.s->next=hs;hs=hs->next;15.有以下程序：

程序運(yùn)行后的輸出結(jié)果是()[單選題]*A.2,2B.2,3C.3,2D.3,3(正確答案)16.線性表若采用鏈表存儲結(jié)構(gòu)，要求內(nèi)存中可用存儲單元地址()[單選題]*A.必須連續(xù)B.部分地址必須連續(xù)C.一定不連續(xù)D.連續(xù)不連續(xù)均可(正確答案)17.有以下程序：

若要使程序輸出的值為2，則應(yīng)該從鍵盤給n輸入的值為()[單選題]*A.-1B.-3(正確答案)C.-5D.018.把一個復(fù)雜的問題分成兩個或更多的相同類似的子問題，再把子問題分解成更小的子問題......知道最后的子問題可以簡單地直接求解。而原問題的解就是子問題解的合并（）[單選題]*A.動態(tài)規(guī)劃B.貪心C.分治(正確答案)D.搜索19.程序運(yùn)行過程中，如果遞歸調(diào)用的層數(shù)過多，會因?yàn)椋ǎ┮l(fā)錯誤。[單選題]*A.系統(tǒng)分配的?？臻g溢出(正確答案)B.系統(tǒng)分配的堆空間溢出C.系統(tǒng)分配的隊(duì)列空間溢出D.系統(tǒng)分配的鏈表空間溢出20.設(shè)X、Y、Z分別代表三進(jìn)制下的一位數(shù)字，若等式XY+ZX=XYX在三進(jìn)制下成立，那么同樣在三進(jìn)制下，等式XY*ZX=(

)也成立。[單選題]*A．YXZB．ZXY(正確答案)C．XYZD．XZY二程序閱讀題（共10分，每題2分）1.

輸入：110015

輸出：____________[填空題]*_________________________________(答案：6)2.

輸入：234

輸出：______[填空題]*_________________________________(答案：Ans=9)3.

輸入：7

輸出：________[填空題]*_________________________________(答案：-11)4．

#include<iostream>

usingnamespacestd;

voidswap(int&a,int&b)

{

intt;

t=a;

a=b;

b=t;

}

intmain()

{

inta1,a2,a3,x;

cin>>a1>>a2>>a3;

if(a1>a2)

swap(a1,a2);

if(a2>a3)

swap(a2,a3);

if(a1>a2)

swap(a1,a2);

cin>>x;

if(x<a2)

if(x<a1)

cout<<x<<''<<a1<<''<<a2<<''<<a3<<endl;

else

cout<<a1<<''<<x<<''<<a2<<''<<a3<<endl;

else

if(x<a3)

cout<<a1<<''<<a2<<''<<x<<''<<a3<<endl;

else

cout<<a1<<''<<a2<<''<<a3<<''<<x<<endl;

return0;

}

輸入：

91220

77

輸出：[填空題]*_________________________________(答案：2207791)5.

#include<iostream>

#include<string>

usingnamespacestd;

intmain()

{

strings;

charm1,m2;

inti;

getline(cin,s);

m1='';

m2='';

for(i=0;i<s.length();i++)

if(s[i]>m1)

{

m2=m1;

m1=s[i];

}

elseif(s[i]>m2)

m2=s[i];

cout<<int(m1)<<''<<int(m2)<<endl;

return0;

}

輸入：Expo2010ShanghaiChina

輸出:_________________

[填空題]*_________________________________(答案：120112)三判斷題（共20分，每題2分）1.鏈表和數(shù)組之間沒有任何區(qū)別()[判斷題]*對錯(正確答案)2.分治法解決問題的特征包含：問題的規(guī)?？s小到一定規(guī)模就可以較容易的解決()[判斷題]*對(正確答案)錯3.遞歸的優(yōu)點(diǎn)是解法比普通循環(huán)運(yùn)行效率更高()[判斷題]*對錯(正確答案)4.遞歸次數(shù)過多容易造成隊(duì)列溢出()[判斷題]*對錯(正確答案)5.遞推和遞歸的性質(zhì)是一致的，只是叫法不同()[判斷題]*對錯(正確答案)6.從一個棧刪除元素又稱作出棧或退棧，它是把棧頂元素刪除掉()[判斷題]*對(正確答案)錯7.隊(duì)列是一種操作不受限制的線性表()[判斷題]*對錯(正確答案)8.鏈表的存儲單元是可以連續(xù)的，也可以是不連續(xù)的()[判斷題]*對(正確答案)錯9.遞推思想是把一個龐大的計(jì)算過程轉(zhuǎn)化為簡單過程的多次重復(fù)()[判斷題]*對(正確答案)錯10.運(yùn)用遞歸解決問題時，子問題可以和原問題不是同一件事()[判斷題]*對錯(正確答案)四編程題（共30分，每題15分）1.數(shù)樓梯

樓梯有N階，上樓可以一步上一階，也可以一步上二階。

編一個程序，計(jì)算共有多少種不同的走法。

輸入格式

一個數(shù)字，樓梯數(shù)。

輸出格式

輸出走的方式總數(shù)。

輸入輸出樣例

輸入

4

輸出

5[填空題]*_________________________________2.排隊(duì)接水

有nn個人在一個水龍頭前排隊(duì)接水，假如每個人接水的時間為T_iTi，請編程找出這nn個人排隊(duì)的一種順序，使得nn個人的平均等待時間最小。

輸入格式

第一行為一個整數(shù)nn。

第二行nn個整數(shù)，第ii個整數(shù)T_iT