信息學(xué)奧賽：數(shù)據(jù)結(jié)構(gòu)初步綜合測(cè)試

1、信息學(xué)奧賽：數(shù)據(jù)結(jié)構(gòu)初步綜合測(cè)試一、單選題（75分，30題每題2.5分）1、下列不屬于線性結(jié)構(gòu)的是（）。 A. 棧B. 隊(duì)列C. 字符串D. 二叉樹(shù)(正確答案)2、一個(gè)棧的入棧序列為ABCDE，則出棧序列不可能為（） A. E D C B AB. D E C B AC. D C E A B(正確答案)D. A B C D E3、以下（）是棧和隊(duì)列的共同特點(diǎn)。 A. 在C+中可以用數(shù)組來(lái)實(shí)現(xiàn)(正確答案)B. 只允許在一端插入和刪除元素C. 都是先進(jìn)后出D. 沒(méi)有共同點(diǎn)4、設(shè)有一個(gè)空棧，現(xiàn)有序列1、2、3、4依次進(jìn)棧，若依次經(jīng)過(guò)“進(jìn)棧、進(jìn)棧、出棧、進(jìn)棧、出棧、進(jìn)棧、出棧、出棧”操作后，出棧序列為(

2、 )。 A. 1 2 3 4B. 2 1 3 4C. 4 3 2 1D. 2 3 4 1(正確答案)5、設(shè)有一棧初始為空。已知進(jìn)棧序列為A、B、C、D、E、F，出棧序列為B、D、C、F、E、A，則該棧的容量至少為（）。 A. 5B. 4C. 3(正確答案)D. 26、若a，b，c依次進(jìn)棧，則可能得到的不同出棧序列的種數(shù)是（）。 A. 3B. 4C. 5(正確答案)D. 67、有6個(gè)元素6、5、4、3、2、1依次按順序進(jìn)棧，（）是不可能得到的出棧序列。 A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 2 3 4 1 5 6D. 3 4 6 5 1 2(正確答案)8、某個(gè)車(chē)站呈狹長(zhǎng)形

3、，寬度只能容下一臺(tái)車(chē)，并且只有一個(gè)出入口。已知某時(shí)刻該車(chē)站狀態(tài)為空，從這一時(shí)刻開(kāi)始的出入記錄為：“進(jìn)，出，進(jìn)，進(jìn)，進(jìn)，出，出，進(jìn)，進(jìn)，進(jìn)，出，出”。假設(shè)車(chē)輛入站的順序?yàn)?，2，3，則車(chē)輛出站的順序?yàn)椋ǎ?A. 1 2 3 4 5B. 1 4 3 7 6(正確答案)C. 1 4 3 7 2D. 1 4 3 7 59、設(shè)棧S的初始狀態(tài)為空，元素a，b，c，d，e依次入棧，以下出棧序列不可能出現(xiàn)的有（）。 A. a b c e dB. b c a e dC. a e c b d(正確答案)D. d c e b a10、地面上有標(biāo)號(hào)為A、B、C的3根細(xì)柱，在A柱上放有10個(gè)直徑相同中間有孔的圓盤(pán)，從

4、上到下依次編號(hào)為1，2，3，將A柱上的部分盤(pán)子經(jīng)過(guò)B柱移入C柱，也可以在B柱上暫存。如果B柱上的操作記錄為：“進(jìn)，進(jìn)，出，進(jìn)，進(jìn)，出，出，進(jìn)，進(jìn)，出，進(jìn)，出，出”。那么，在C柱上，從下到上的盤(pán)子的編號(hào)為（）。 A. 2 4 3 6 5 7B. 2 4 1 2 5 7C. 2 4 3 1 7 6D. 2 4 3 6 7 5(正確答案)11、字符串是特殊的線性表，特殊在（）。 A. 字符串可以用數(shù)組進(jìn)行存儲(chǔ)B. 字符串中的每一個(gè)元素都是字符(正確答案)C. 除了第一個(gè)元素以外，字符串中每一個(gè)元素都有一個(gè)前驅(qū)D. 除了最后一個(gè)元素以外，字符串中每一個(gè)元素都有一個(gè)后繼12、下列關(guān)于空串和空格串的說(shuō)法中

5、，表述正確的說(shuō)法有（）個(gè)。 空格串表示只含空格的串。 空串表示所含字符數(shù)為0的串。 空格串指由空格組成的非空串，其長(zhǎng)度為串中空格字符的個(gè)數(shù)。 空串指長(zhǎng)度為零的串。 A. 4(正確答案)B. 3C. 2D. 113、定義字符數(shù)組ch101和sring類(lèi)型的字符串st。要輸入這樣一行字符“123 abcd”，則下列輸入方式中可以正確執(zhí)行讀入并進(jìn)行存儲(chǔ)的是（）。 A. cin>>ch;B. cin>>st;C. getline(cin,ch);D. getline(cin,st);(正確答案)14、設(shè)字符串S=“Olympic”，S的非空子串的數(shù)目是（）。 A. 28(正確答

6、案)B. 29C. 16D. 1715、若串S="zuoceshi"，其子串的個(gè)數(shù)是（）。 A. 36B. 37(正確答案)C. 38D. 3916、若串S="xinxixue"，其子串的個(gè)數(shù)是（）。 A. 35B. 34C. 33(正確答案)D. 3217、設(shè)根結(jié)點(diǎn)的深度為1，則深度為6的滿二叉樹(shù)有（）個(gè)分支結(jié)點(diǎn)。 A. 31(正確答案)B. 32C. 63D. 6418、有一個(gè)深度為3的滿二叉樹(shù)(根結(jié)點(diǎn)深度為0)。若將結(jié)點(diǎn)按層次從上到下從左到右從1開(kāi)始逐一編號(hào)，則6號(hào)結(jié)點(diǎn)的左兒子是（）號(hào)結(jié)點(diǎn)。 A. 3B. 12(正確答案)C. 13D. 不存在19

7、、已知6個(gè)結(jié)點(diǎn)的二叉樹(shù)的先根遍歷是1 2 3 4 5 6(數(shù)字為結(jié)點(diǎn)的編號(hào)，以下同)，后根遍歷是3 2 5 6 4 1，則該二叉樹(shù)的可能的中根遍歷是（）。 A. 3 2 1 4 6 5B. 3 2 1 5 4 6(正確答案)C. 2 1 3 5 4 6D. 2 3 1 4 6 520、已知7個(gè)節(jié)點(diǎn)的二叉樹(shù)的先根遍歷是1 2 4 5 6 3 7(數(shù)字為節(jié)點(diǎn)的編號(hào)，以下同)，中根遍歷是4 2 6 5 1 7 3，則該二叉樹(shù)的后根遍歷是（）。 A. 4 6 5 2 7 3 1(正確答案)B4 6 5 2 1 3 7C4 2 3 1 5 4 7D4 6 5 3 1 7 221、完全二叉樹(shù)共有2N-1個(gè)

8、結(jié)點(diǎn)，則它的葉結(jié)點(diǎn)數(shù)是（）。 A. N-1B. N(正確答案)C. 2ND. 2N-122、二叉樹(shù)的先序遍歷是1 2 4 3 5 7 6(數(shù)字為結(jié)點(diǎn)的編號(hào)，以下同)，中序遍歷是2 4 1 5 7 3 6，則該二叉樹(shù)的后根遍歷是（）。 A. 4 2 5 7 6 3 1B. 4 2 7 5 6 3 1(正確答案)C. 7 4 2 5 6 3 1D. 4 2 7 6 5 3 123、設(shè)T是一棵有n個(gè)頂點(diǎn)的樹(shù)，下列說(shuō)法不正確的是（）。 A. T有n條邊(正確答案)B. T是連通的C. T是無(wú)環(huán)的D. T有n-1條邊24、表達(dá)式a(b+c)-d的后綴表達(dá)式是（）。 A a b c d + -B. a b

9、 c + d (正確答案)C. a b c + d D. - + a b c d25、前綴表達(dá)式 + 2 + 3 4 5的值為（）。 A. 11B. 17C. 27D. 37(正確答案)26、一個(gè)包含n個(gè)分支結(jié)點(diǎn)(非葉結(jié)點(diǎn))的非空滿k叉樹(shù)，k>=1，它的葉結(jié)點(diǎn)數(shù)目為（）。 A. nk+1B. nk-1C. (k+1)n-1D. (k-1)n+1(正確答案)27、已知n個(gè)頂點(diǎn)的有向圖，若該圖是強(qiáng)連通的(從所有頂點(diǎn)都存在路徑到達(dá)其他頂點(diǎn))，則該圖中最少有（）條有向邊。 A. n(正確答案)B. n+1C. n-1D. n(n-1)28、下列能夠一筆寫(xiě)出的漢字有（）個(gè)。 日 甲 田 中 A. 0B. 1C. 2(正確答案)D. 329、一個(gè)具有n個(gè)頂點(diǎn)的有向圖G，最多有（）條弧。 A. n(n-1)/2B. n(n+1)C. 2nD. n(n-1)(正確答案)30、圖G是一個(gè)有4個(gè)頂點(diǎn)的無(wú)向完全圖，若要使它不再是連通圖，至少要?jiǎng)h去其中的（）條邊。 A. 1B. 2C. 3(正確答案)D. 4二、填空題（3題，共15分，遍歷每空3分，后三空每空2分）1、寫(xiě)出以下二叉樹(shù)的三序遍歷（先中后序遍歷）。（1）先序遍歷 _(答案：ABDECF)（2）中序遍歷 _(答案：DBEACF)（3）后序遍歷 _(答案：DEBFCA)2、二叉樹(shù)T有2021個(gè)結(jié)點(diǎn)，若