計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)構(gòu)-棧、隊(duì)列和數(shù)組(二)

計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)構(gòu)-棧、隊(duì)列和數(shù)組(二)(總分：53.00，做題時(shí)間：90分鐘)一、{{B}}單項(xiàng)選擇題{{/B}}(總題數(shù)：37，分?jǐn)?shù)：37.00)1.對(duì)一個(gè)初始為空的棧s執(zhí)行操作Push(s，5)，Push(s，2)，Push(s，4)，Pop(s，x)，getTop(s，x)后，x的值應(yīng)是______。A.5B.2C.4D.0

（分?jǐn)?shù)：1.00）

A.

B.

√

C.

D.解析：[解析]連續(xù)執(zhí)行3次元素進(jìn)棧操作后，棧內(nèi)的數(shù)據(jù)為5，2，4，此時(shí)執(zhí)行退棧操作1次，棧內(nèi)元素為5和2，棧頂讀到x中應(yīng)為2。2.用S表示進(jìn)棧操作，用X表示出棧操作，若元素的進(jìn)棧順序是1，2，3，4，為了得到出棧順序1，3，4，2，相應(yīng)的S和X的操作序列為______。A.SXSXSSXXB.SSSXXSXXC.SXSSXXSXD.SXSSXSXX

（分?jǐn)?shù)：1.00）

A.

B.

C.

D.

√解析：[解析]此題可以用排除法來解決。由選項(xiàng)A、B、C所得出的棧序列分別為(1，2，4，3)、(3，2，4，1)、(1，3，2，4)，可以看出都是錯(cuò)誤的。選項(xiàng)D得到的出棧序列為1，3，4，2。3.已知一個(gè)棧的進(jìn)棧序列為1，2，3，…，n，其輸出序列的第一個(gè)元素是i，則第j個(gè)出棧元素是______。A.j-iB.n-iC.j-i+1D.不確定

（分?jǐn)?shù)：1.00）

A.

B.

C.

D.

√解析：[解析]i出棧時(shí)，1，2，…，i-l都在棧內(nèi)，之后的過程中還可能有i之后的元素進(jìn)棧，但究竟第j個(gè)出棧元素是哪個(gè)，不能確定。4.已知一個(gè)棧的進(jìn)棧序列為1，2，3，…，n，其輸出序列是p1，p2，p3，…，pn。若p1=3，則p2的值______。A.一定是2B.一定是1C.可能是1D.可能是2

（分?jǐn)?shù)：1.00）

A.

B.

C.

D.

√解析：[解析]元素3第一個(gè)出棧時(shí)，元素1，2一定在棧內(nèi)，下一個(gè)出棧的元素是2，不可能是1。當(dāng)然還可以是元素2暫時(shí)不出棧，元素4，5，…進(jìn)棧。5.已知一個(gè)棧的進(jìn)棧序列為p1，p2，p3，…，pn，其輸出序列是1，2，3，…，n。若p3=1，則p1的值______。A.一定是2B.可能是2C.不可能是2D.一定是3

（分?jǐn)?shù)：1.00）

A.

B.

C.

√

D.解析：[解析]p3=1，輸入序列為p1，p2，1，p4，…，因?yàn)閜3=1，所以p3出棧前，p1，p2必在棧中。若p1出棧，則p2必先于p1出棧，因此p1不可能為2。6.以下有關(guān)順序棧的操作中，正確的是______。A.n個(gè)元素進(jìn)入一個(gè)棧后，它們的出棧順序一定與進(jìn)棧順序相反(一次性進(jìn)棧完畢后再出棧)B.若一個(gè)棧的存儲(chǔ)空間為S[n]，則對(duì)棧的進(jìn)棧和出棧操作最多只能執(zhí)行n次C.棧是一種對(duì)進(jìn)棧和出棧操作的次序做了限制的線性表D.空棧沒有棧頂指針

（分?jǐn)?shù)：1.00）

A.

√

B.

C.

D.解析：[解析]對(duì)于選項(xiàng)A，n個(gè)元素進(jìn)棧后，出棧順序必然與進(jìn)棧的順序相反，因此選項(xiàng)A正確；對(duì)于選項(xiàng)B，如果某元素進(jìn)棧后很快又出棧，則進(jìn)棧和出棧操作可以多于n次；對(duì)于選項(xiàng)C，棧并未對(duì)進(jìn)棧和出棧次序做限制，而僅僅對(duì)進(jìn)棧和出棧的位置做了限制；對(duì)于選項(xiàng)D，棧頂指針屬于棧結(jié)構(gòu)的一個(gè)分量，不會(huì)由于棧的狀態(tài)變化而消失。7.在實(shí)現(xiàn)順序棧的操作時(shí)，在進(jìn)棧之前應(yīng)先判斷棧是否______，在出棧之前應(yīng)先判斷是否空。A.空B.滿C.上溢D.下溢

（分?jǐn)?shù)：1.00）

A.

B.

√

C.

D.解析：[解析]在元素進(jìn)棧之前先判斷棧是否已滿，棧滿再進(jìn)棧就會(huì)發(fā)生上溢。出棧之前先判斷棧是否為空，如果棧已空再出棧就會(huì)發(fā)生下溢。8.設(shè)鏈?zhǔn)綏Ｖ薪Y(jié)點(diǎn)的結(jié)構(gòu)為(data，link)，且top是指向棧頂?shù)闹羔?。若想在鏈?zhǔn)綏５臈ｍ敳迦胍粋€(gè)由指針s所指的結(jié)點(diǎn)，則應(yīng)執(zhí)行的操作是______。A.top→link=S;B.S→link=top→+link;top→link=s;C.s→link=top;top=s;D.s→link=top;top=top→link;

（分?jǐn)?shù)：1.00）

A.

B.

C.

√

D.解析：[解析]在棧頂插入元素即在鏈表首元結(jié)點(diǎn)前插入，必須首先讓s后面鏈接上原棧頂top，再讓棧頂指針指向新棧頂s，所以有s→link=top;top=s;。9.設(shè)一個(gè)循環(huán)隊(duì)列Q[maxSize]的隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列最大容量為maxSize。除此之外，該隊(duì)列再?zèng)]有其他數(shù)據(jù)成員，則該隊(duì)列的隊(duì)滿條件是______。A.Q.front==Q.rearB.front+Q.rear＞=maxSizeC.Q.fron==(Q.rear+1)%maxSizeD.Q.rear==(Q.front+1)%maxSize

（分?jǐn)?shù)：1.00）

A.

B.

C.

√

D.解析：[解析]在不能附加其他任何數(shù)據(jù)成員的前提下，只能用犧牲一個(gè)隊(duì)列元素的整除取余的方式來區(qū)分隊(duì)空和隊(duì)滿的條件。因此，選項(xiàng)C正確。選項(xiàng)A是判斷隊(duì)列是否為空的條件，選項(xiàng)B和D則是干擾項(xiàng)。10.一個(gè)隊(duì)列的進(jìn)隊(duì)順序是1，2，3，4，則該隊(duì)列可能的輸出序列是______。A.1，2，3，4B.1，3，2，4C.1，4，2，3D.4，3，2，1

（分?jǐn)?shù)：1.00）

A.

√

B.

C.

D.解析：[解析]由隊(duì)列的FIFO性質(zhì)可知，出隊(duì)序列為1，2，3，4。11.對(duì)于鏈?zhǔn)疥?duì)列，在執(zhí)行插入操作時(shí)______。A.僅修改頭指針B.僅修改尾指針C.頭、尾指針都要修改D.頭、尾指針可能都要修改

（分?jǐn)?shù)：1.00）

A.

B.

C.

D.

√解析：[解析]對(duì)于鏈?zhǔn)疥?duì)列，一般插入元素僅僅需要修改尾指針，但向空隊(duì)列插入新元素時(shí)，需要同時(shí)修改隊(duì)頭指針和隊(duì)尾指針。所以本題選D。12.最適合用做鏈?zhǔn)疥?duì)列的鏈表是______。A.帶有隊(duì)頭指針和隊(duì)尾指針的循環(huán)單鏈表B.帶有隊(duì)頭指針和隊(duì)尾指針的非循環(huán)單鏈表C.只帶隊(duì)頭指針的循環(huán)單鏈表D.只帶隊(duì)頭指針的非循環(huán)單鏈表

（分?jǐn)?shù)：1.00）

A.

B.

√

C.

D.解析：[解析]在鏈頭刪除元素，在鏈尾插入元素，因此需要隊(duì)頭指針和隊(duì)尾指針。這種情況下使用非循環(huán)單鏈表比較方便。13.最不適合用做鏈?zhǔn)疥?duì)列的鏈表是______。A.帶有隊(duì)頭指針的雙向非循環(huán)鏈表B.帶有隊(duì)頭指針的雙向循環(huán)鏈表C.只帶隊(duì)尾指針的雙向循環(huán)鏈表D.只帶隊(duì)尾指針的循環(huán)單鏈表

（分?jǐn)?shù)：1.00）

A.

√

B.

C.

D.解析：[解析]即使是雙向鏈表，如果是非循環(huán)鏈表，只有隊(duì)頭指針也是不夠的。14.為解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配的問題，通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)。主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)應(yīng)該是______。A.棧B.隊(duì)列C.樹D.圖

（分?jǐn)?shù)：1.00）

A.

B.

√

C.

D.解析：[解析]通常用于輸入或輸出的緩沖區(qū)都是采用先進(jìn)先出的隊(duì)列。15.在將遞歸算法轉(zhuǎn)換成對(duì)應(yīng)的非遞歸算法時(shí)，通常需要使用______保存中間結(jié)果。A.鏈表B.棧C.隊(duì)列D.順序表

（分?jǐn)?shù)：1.00）

A.

B.

√

C.

D.解析：[解析]在遞歸程序時(shí)作為遞歸工作棧是棧的一個(gè)典型應(yīng)用，用于開辟每一層遞歸程序調(diào)用時(shí)需要的局部變量空間、實(shí)際參數(shù)的拷貝空間和記錄返回上一層調(diào)用的返回地址等。16.一個(gè)遞歸算法必須包括______。A.遞歸部分B.結(jié)束條件和遞歸部分C.迭代部分D.結(jié)束條件和迭代部分

（分?jǐn)?shù)：1.00）

A.

B.

√

C.

D.解析：[解析]遞歸算法必須包括遞歸體和結(jié)束條件。結(jié)束條件是可以直接求解的，無需再遞歸處理；遞歸體在不能直接求解的情況下把問題通過遞歸調(diào)用化為更簡(jiǎn)單的子問題求解，每遞歸一層就向問題的最終解決推進(jìn)一步。17.在二維數(shù)組中，每個(gè)數(shù)組元素同時(shí)處于______個(gè)向量中。A.0個(gè)B.1個(gè)C.2個(gè)D.n個(gè)

（分?jǐn)?shù)：1.00）

A.

B.

C.

√

D.解析：[解析]可以將二維數(shù)組視為一組行向量和列向量的縱橫交織，每個(gè)元素既處于一個(gè)行向量中，又處于一個(gè)列向量中。因此，需要用兩個(gè)下標(biāo)i和j以確定該數(shù)組元素在數(shù)組中的位置。18.多維數(shù)組實(shí)際上是由______實(shí)現(xiàn)的。A.一維數(shù)組B.多項(xiàng)式C.三元組表D.簡(jiǎn)單變量

（分?jǐn)?shù)：1.00）

A.

√

B.

C.

D.解析：[解析]多維數(shù)組本質(zhì)上是一維數(shù)組，是由一維數(shù)組實(shí)現(xiàn)的，是數(shù)組元素為一維數(shù)組的一維數(shù)組。19.在二維數(shù)組A[9][10]中，每個(gè)數(shù)組元素占用3個(gè)存儲(chǔ)單元，從首地址SA開始按行連續(xù)存放。在這種情況下，元素A[8][5]的起始地址為______。A.SA+141B.SA+144C.SA+222D.SA+255

（分?jǐn)?shù)：1.00）

A.

B.

C.

D.

√解析：[解析]本題屬于計(jì)算存儲(chǔ)地址的典型題目，假設(shè)求元素a的地址，首先按行存儲(chǔ)，求a所在行之前的所有行中元素的總和sum1，然后求a所在行a之前所有元素的總和sum2，最后用首地址加上(sum1+sum2)×每個(gè)元素所占存儲(chǔ)空間的大小即可。由以上分析可知：A[8][5]的地址=SA+(8×10+5)×3=SA+255。20.假設(shè)某棧的輸入序列是1，2，3，4，則不可能得到的輸出序列是______。A.1，2，3，4B.4，1，2，3C.4，3，2，1D.1，3，4，2

（分?jǐn)?shù)：1.00）

A.

B.

√

C.

D.解析：[解析]用S表示進(jìn)棧操作，用X表示出棧操作，選項(xiàng)A、C和D的輸出序列可以用操作序列SXSXSXSX、SSSSXXXX和SXSSXSXX來導(dǎo)出，且都是合法操作序列。只有選項(xiàng)B的輸出序列找不到合法的操作序列。21.已知一個(gè)棧的進(jìn)棧序列為1，2，3，…，n，其輸出序列是p1，p2，p3，…，pn。若p1=n，則pi的值是______。A.iB.n-iC.n-i+1D.不確定

（分?jǐn)?shù)：1.00）

A.

B.

C.

√

D.解析：[解析]一個(gè)出棧元素是n，則1，2，3，…，n-1都在棧內(nèi)，可知后續(xù)出棧的元素依次為n-1，n-2，…，則第i個(gè)出棧元素應(yīng)為n-i+1。22.已知一個(gè)棧的進(jìn)棧序列為p1，p2，p3，…，pn，其輸出序列是1，2，3，…，n。若p3=3，則p1的值是______。A.一定是2B.可能是2C.不可能是1D.一定是1

（分?jǐn)?shù)：1.00）

A.

B.

√

C.

D.解析：[解析]當(dāng)p3=3時(shí)，輸入序列為p1，p2，3，p4，…因?yàn)檩敵龅牡谌齻€(gè)元素是3，所以有多種可能：當(dāng)p1=1，p2=2時(shí)，允許的進(jìn)棧或出棧順序是p1進(jìn)棧，p1出棧，p2進(jìn)棧，p2出棧；當(dāng)p1=2，p2=1時(shí)，允許的進(jìn)?；虺鰲ｍ樞蚴莗1進(jìn)棧，p2進(jìn)棧，p2出棧，p1出棧；當(dāng)p1，p2，3進(jìn)棧不出，p4=2，p5=1時(shí)，允許的進(jìn)棧或出棧順序可以是p4進(jìn)棧，p5進(jìn)棧，p5出棧，p4出棧。因此可以斷定p1=1或p1=2是可能的，但不是一定的。23.已知一個(gè)棧的進(jìn)棧序列為p1，p2，p3，…，pn，其輸出序列是1，2，3，…，n。若pn=1，則pi的值是______。A.n-i+1B.n-iC.iD.不確定

（分?jǐn)?shù)：1.00）

A.

√

B.

C.

D.解析：[解析]當(dāng)pn=1時(shí)，輸入序列為p1，p2，p3，p4，…，pn-1，1，因?yàn)檩敵鲂蛄袨?，2，3，…，n，所以第一次輸出l時(shí)p1，p2，p3，p4，…，pn-1都應(yīng)在棧內(nèi)，這樣可得pn-1=2，pn-2=3，…，pn-i=i+1，…，pi=n-i+1。24.當(dāng)利用大小為n的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，元素存儲(chǔ)在[0…n-1]位置上，假定用top==n表示棧空，則向這個(gè)棧插入一個(gè)元素時(shí)，首先應(yīng)執(zhí)行______語句修改top指針。A.top++;B.top--;C.top=0;D.top=n;

（分?jǐn)?shù)：1.00）

A.

B.

√

C.

D.解析：[解析]根據(jù)題意，棧底應(yīng)在下標(biāo)n-1的位置上，因此進(jìn)棧時(shí)棧頂指針應(yīng)該先減1，向?？臻g的底端延伸。25.為了增加內(nèi)存空間的利用率和減少溢出的可能，在兩個(gè)棧共享一片連續(xù)的存儲(chǔ)空間時(shí)，應(yīng)將兩個(gè)棧的棧頂(初始的時(shí)候棧底和棧頂重合；元素進(jìn)棧時(shí)，兩棧頂相向運(yùn)動(dòng))分設(shè)在這片存儲(chǔ)空間的兩端，當(dāng)______時(shí)才產(chǎn)生上溢。A.兩個(gè)棧的棧頂同時(shí)到達(dá)?？臻g的中心點(diǎn)B.其中一個(gè)棧的棧頂?shù)竭_(dá)棧空間的中心點(diǎn)C.兩個(gè)棧的棧頂在棧空間的某一位置相遇D.兩個(gè)棧的棧頂相加超過了?？臻g的最大容量

（分?jǐn)?shù)：1.00）

A.

B.

C.

√

D.解析：[解析]初始時(shí)，兩個(gè)棧的棧頂設(shè)置在?？臻g的兩端，元素進(jìn)棧時(shí)，棧頂指針相向而行，當(dāng)兩個(gè)棧的棧頂在?？臻g的某一位置相遇時(shí)，為棧滿狀態(tài)。26.設(shè)鏈?zhǔn)綏Ｖ薪Y(jié)點(diǎn)的結(jié)構(gòu)為(data，link)，且top是指向棧頂?shù)闹羔槨Ｈ粝胝骆準(zhǔn)綏５臈ｍ斀Y(jié)點(diǎn)，并將被摘除結(jié)點(diǎn)的值保存到x中，則應(yīng)執(zhí)行的操作是______。A.x=top→data;top=top→link;B.top=top→link;x=top→data;C.x=top;top=top→link;D.x=top→data;

（分?jǐn)?shù)：1.00）

A.

√

B.

C.

D.解析：[解析]出棧操作由兩部分組成：取元素存儲(chǔ)在其他空間和調(diào)整棧頂指針位置。為完成這兩部分可以執(zhí)行以下語句：x=top→data;//取元素存儲(chǔ)在其他空間top=top→link;//調(diào)整棧頂指針位置27.設(shè)循環(huán)隊(duì)列的存儲(chǔ)容量為maxSize，隊(duì)頭和隊(duì)尾指針分別為front和rear。若有一個(gè)循環(huán)隊(duì)列Q，則可應(yīng)用下列______算式計(jì)算隊(duì)列元素個(gè)數(shù)。A.Q.rear-Q.frontB.Q.rear-Q.front+1C.(Q.rear-Q.front)%maxSize+1D.(Q.rear-Q.front+maxSize)%maxSize

（分?jǐn)?shù)：1.00）

A.

B.

C.

D.

√解析：[解析]隨著隊(duì)列中元素的進(jìn)隊(duì)出隊(duì)的交替進(jìn)行，對(duì)于rear與front兩指針，其相對(duì)位置不定。當(dāng)rear＜front時(shí)，Q.reai-Q.front+maxSize正好是隊(duì)列元素個(gè)數(shù)；當(dāng)rear＞front時(shí)，可以用(Q.rear-Q.front+maxSize)%maxSize得到隊(duì)列元素個(gè)數(shù)。28.設(shè)一個(gè)鏈?zhǔn)疥?duì)列q的隊(duì)頭指針和隊(duì)尾指針分別為front和rear，則判斷隊(duì)列為空的條件是______。A.q.front==q.rearB.q.front==NULL||q.rear==NULLC.q.rear==NULLD.q.front!=NULL

（分?jǐn)?shù)：1.00）

A.

B.

√

C.

D.解析：[解析]當(dāng)front==NULL或者rear==NULL時(shí)，鏈為空，則對(duì)應(yīng)的鏈隊(duì)也為空。29.對(duì)一個(gè)初始為空的隊(duì)列Q執(zhí)行操作enQueue(Q,a)，enQueue(Q,b)，deQueue(Q,x)，deQueue(Q,Y)之后，再執(zhí)行isEmpty(Q)，返回的值是______。A.aB.bC.1D.0

（分?jǐn)?shù)：1.00）

A.

B.

C.

√

D.解析：[解析]對(duì)一個(gè)空隊(duì)列，執(zhí)行兩次進(jìn)隊(duì)操作和兩次出隊(duì)操作后，顯然棧變?yōu)榭諣顟B(tài)，此時(shí)執(zhí)行判斷隊(duì)列是否為空的操作Q.isEmpty()，函數(shù)返回true。30.設(shè)棧S和隊(duì)列Q的初始狀態(tài)均為空，元素a，b，c，d，e，f，g依次進(jìn)入棧S。如果每個(gè)元素出棧后立即進(jìn)入隊(duì)列Q，且7個(gè)元素出隊(duì)的順序?yàn)閎，d，c，f，e，a，g，則棧S的容量至少是______。A.1B.2C.3D.4

（分?jǐn)?shù)：1.00）

A.

B.

C.

√

D.解析：[解析]根據(jù)隊(duì)列的FIFO性質(zhì)，出隊(duì)順序與入隊(duì)順序一致，也就是說，與出棧順序一致。如果用S表示進(jìn)棧，用X表示出棧，按照題意，進(jìn)棧和出棧序列見下表。{{B}}進(jìn)棧與出棧情況{{/B}}進(jìn)棧序列ab進(jìn)出操作SSXSSXXSSXXXSX棧的內(nèi)容aabaacacdacaaeaefaeag出棧序列bdcfeag由表可知，棧中最多時(shí)有3個(gè)元素，所以棧的容量最少為3。31.已知輸入序列是1234，則輸入受限(僅允許由一端輸入)但輸出不受限(兩端均可輸出)的雙端隊(duì)列不可能得到的輸出序列是______。A.4231B.1324C.3214D.2341

（分?jǐn)?shù)：1.00）

A.

√

B.

C.

D.解析：[解析]設(shè)雙端隊(duì)列的兩端為e1和e2，e1端允許輸入，e1和e2端都允許輸出。若在e1端輸出，相當(dāng)于棧；若在e2端輸出，相當(dāng)于隊(duì)列。

對(duì)于選項(xiàng)A(4231)，要求先輸出4，有一種進(jìn)隊(duì)方案：1e12e13e14e1，然后從e1端輸出4，但由于2夾在1和3之間，下一個(gè)輸出的不可能是2，所以選項(xiàng)A是不可能的輸出序列。

對(duì)于選項(xiàng)B(1324)，一種操作順序是1e1進(jìn)1e1出2e1進(jìn)3e1進(jìn)3e1出2e1出4e1進(jìn)4e1出。

對(duì)于選項(xiàng)C(3214)，一種操作順序是1e1進(jìn)2e1進(jìn)3e1進(jìn)3e1出2e1出1e1出4e1進(jìn)4e1出。

對(duì)于選項(xiàng)D(2341)，一種操作順序是1e1進(jìn)2e1進(jìn)2e1出3e1進(jìn)3e1出4e1進(jìn)4e1出1e1出。32.已知輸入序列是abcd，則經(jīng)過輸出受限的雙端隊(duì)列后能得到的輸出序列是______。A.dacbB.cadbC.dbcaD.dbac

（分?jǐn)?shù)：1.00）

A.

B.

√

C.

D.解析：[解析]設(shè)雙端隊(duì)列的兩端為e1和e2，e2端允許輸出，e1和e2兩端都允許輸入。若在e1端輸入，相當(dāng)于隊(duì)列；若在e2端輸入，相當(dāng)于棧。

對(duì)于選項(xiàng)A(dacb)，要求先輸出d，必須abc都輸入后再執(zhí)行操作de2進(jìn)de2出(相當(dāng)于進(jìn)棧出棧)，但下一個(gè)要輸出a，就必須執(zhí)行操作ae1進(jìn)be1進(jìn)ce1進(jìn)，隊(duì)列中是cba，再執(zhí)行ae2出，然而下一個(gè)不可能輸出c，所以選項(xiàng)A是不可能的輸出序列。

對(duì)于選項(xiàng)B(cadb)，一種操作順序是ae1進(jìn)be1進(jìn)ce2進(jìn)ce2出ae2出de2進(jìn)de2出be2出，是可能的輸出序列。

對(duì)于選項(xiàng)C(dbca)，相當(dāng)于上一題中的A項(xiàng)(4231)，是不可能的輸出序列。

對(duì)于選項(xiàng)D(dbac)，與選項(xiàng)A類似，要求先輸出d，必須先輸入abc后再執(zhí)行操作de2進(jìn)de2出；若要求下一個(gè)輸出b，應(yīng)執(zhí)行操作ae1進(jìn)be2進(jìn)ce1進(jìn)，隊(duì)列中是cab，輸出b后，下一個(gè)輸出的不可能是c，選項(xiàng)D是不可能的輸出序列。33.設(shè)求解某問題的遞歸算法如下：

voidF(intn)

{

if(n==1)Move(1);

else

{

F(n-1);

Move(n);

F(n-1);

}

}

在求解該算法的計(jì)算時(shí)間時(shí)，僅考慮算法Move所做的計(jì)算，且Move為常數(shù)級(jí)算法。算法F的計(jì)算時(shí)間T(n)的遞推關(guān)系式為______。A.T(n)=T(n-1)+1B.T(n)=2T(n-1)C.T(n)=2T(n-1)+1D.T(n)=2T(n+1)+1

（分?jǐn)?shù)：1.00）

A.

B.

C.

√

D.解析：[解析]根據(jù)題目中程序代碼的遞歸框架可知，該程序把一個(gè)規(guī)模為n的問題轉(zhuǎn)化為兩個(gè)規(guī)模為n-1的同樣問題外加一個(gè)常量復(fù)雜度的操作來求解，因此其遞推關(guān)系為T(n)=2T(n-1)+O(1)，可近似為T(n)=2T(n-1)+1。34.一個(gè)二維數(shù)組A[10][20]按行存放于一個(gè)連續(xù)的存儲(chǔ)空間中，A[0][0]的存儲(chǔ)地址是200，每個(gè)數(shù)組元素占1個(gè)存儲(chǔ)字，則A[6][2]的地址為______。A.226B.322C.341D.342

（分?jǐn)?shù)：1.00）

A.

B.

√

C.

D.解析：[解析]此類型題目基礎(chǔ)題部分已經(jīng)講過，A[6][2]的地址=200+6×20+2=322。35.一個(gè)二維數(shù)組A[10][20]按列存放于一個(gè)連續(xù)的存儲(chǔ)空間中，A[0][0]的存儲(chǔ)地址是200，每個(gè)數(shù)組元素占1個(gè)存儲(chǔ)字，則A[6][2]的地址為______。A.226B.322C.341D.342

（分?jǐn)?shù)：1.00）

A.

√

B.

C.

D.解析：[解析]此類型題目基礎(chǔ)題部分已經(jīng)講過，A[6][2]的地址=200+2×10+6=226。36.將一個(gè)n×n的對(duì)稱矩陣A的下三角部分按行存放在一個(gè)一維數(shù)組B中，A[0][0]存放于B[0]中，那么第i行的對(duì)角元素A[i][i]在B中的存放位置是______。A.(i+3)×i/2B.(i+1)×i/2C.(2n-i+1)×i/2D.(2n-i-1)×i/2

（分?jǐn)?shù)：1.00）

A.

√

B.

C.

D.解析：[解析]第i行前面存有i行，元素個(gè)數(shù)為1+2+…+i=(i+1)×i/2，第i行中第i列前有i個(gè)元素，則A[i][i]在B中的存放位置為(i+1)×i/2+i=(i+3)×i/2。37.設(shè)有一個(gè)n階的三對(duì)角線矩陣A的對(duì)角元素A[i][j]可存放于一個(gè)一維數(shù)組B中，要求行下標(biāo)必須滿足0≤i≤n-1，而列下標(biāo)必須滿足______。A.0≤j≤n-1B.i-1≤j≤i+1C.0≤j≤iD.i≤j≤n

（分?jǐn)?shù)：1.00）

A.

B.

√

C.

D.解析：[解析]三對(duì)角線矩陣屬于帶狀矩陣，如圖所示。帶狀矩陣下標(biāo)范圍可以表示為i-1≤j≤i+1，因此本題選B。[*]二、{{B}}綜合應(yīng)用題{{/B}}(總題數(shù)：2，分?jǐn)?shù)：16.00)Legendre多項(xiàng)式定義如下：

（分?jǐn)?shù)：8.00）(1).編寫一個(gè)遞歸算法，計(jì)算該多項(xiàng)式的值。（分?jǐn)?shù)：4.00）__________________________________________________________________________________________

正確答案：(遞歸算法可以根據(jù)函數(shù)的定義來編寫。floatLegendre_(floatx,intn){if(n==0)return1;if(n==1)returnx;return((2*n-1)*x*Legendre(x,n-1)-(n-1)*Legendre(x,n-2))/n;})解析：(2).編寫一個(gè)非遞歸算法，計(jì)算該多項(xiàng)式的值。（分?jǐn)?shù)：4.00）__________________________________________________________________________________________

正確答案：(使用迭代法的非遞歸算法：從多項(xiàng)式的定義中可以看出，要求Legendre(x,n)，必須先求Legendre(x,n-1)和Legendre(x,n-2)，遞歸結(jié)束于Legendre(x,0)和Legendre(x,1)。只要用backone保存Legendre(x,n-1)，用backtwo保存Legendre(x,n-2)，即可求Legendre(x,n)。不需要使用棧編寫非遞歸算法。用這種思路編寫的非遞歸算法代碼如下：floatLegendre(floatx,intn){floatcurrent,backone,backtwo;inti;if(n==0)return1;if(n==1)returnx;backone=x;backtwo=1;for(i=2;i＜=n;++i){current=((2*n-1)*x*backone-(n-1)*backtwo)/n;ba