【文章內(nèi)容簡(jiǎn)介】 )n1 　C)ni+1 　D)不確定( B )　A)算法必須有輸出 　B)算法必須在計(jì)算機(jī)上用某種語(yǔ)言實(shí)現(xiàn)　C)算法不一定有輸入 D)算法必須在有限步執(zhí)行后能結(jié)束( B)　A)刪除棧頂元素 　B)刪除棧底的元素 　　C)判斷棧是否為空 D)將棧置為空棧(2，5，7，10，14，15，18，23，35，41，52)中，用二分法查找12，所需的關(guān)鍵碼比較的次數(shù)為( C)　A)2 　B)3 　C)4 　D)5，所有結(jié)點(diǎn)的度為0，或?yàn)?，則此樹最少有( B)個(gè)結(jié)點(diǎn)　A)2h1 　B)2h1 　C)2h+1 　D)h+1=(V，E)，其中V={a,b,c,d,e,f} E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)} 對(duì)該圖進(jìn)行深度優(yōu)先遍歷,得到的頂點(diǎn)序列正確的是(D) A)a,b,e,c,d,f　B)a,c,f,e,b,d　C)a,e,b,c,f,d　D)a,b,e,d,f,cNOIP2002：17．按照二叉數(shù)的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹有（ C ）種。 A）3 B）4 C）5 D）618．在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（ B ）倍。A） 1/2 B）1 C）2 D）4解析: 在有向圖的鄰接表中，從一頂點(diǎn)出發(fā)的弧鏈接在同一鏈表中，鄰接表中結(jié)點(diǎn)的個(gè)數(shù)恰為圖中弧的數(shù)目，所以頂點(diǎn)入度之和為弧數(shù)和的一倍，若為無(wú)向圖，同一條邊有兩個(gè)結(jié)點(diǎn)，分別出現(xiàn)在和它相關(guān)的兩個(gè)頂點(diǎn)的鏈表中，因此無(wú)向圖的鄰接表中結(jié)點(diǎn)個(gè)數(shù)的邊數(shù)的2倍19．要使1 ．．．8號(hào)格字的訪問(wèn)順序?yàn)椋?，則下圖中的空格中應(yīng)填入（ C ）。1 2 3 4 5 6 7 84 6 1 1 7 3 2A）6 B）0 C）5 D）3NOIP2003：5. 一個(gè)高度為h 的二叉樹最小元素?cái)?shù)目是（ B ）。 A） 2h+1 B） h C） 2h1 D） 2h E） 2h16. 已知隊(duì)列（13，2，11，34，41，77，5，7，18，26，15），第一個(gè)進(jìn)入隊(duì)列的元素是13，則第五個(gè)出隊(duì)列的元素是（ B ）。 A） 5 B） 41 C） 77 D） 13 E） 1819. 已知元素（8，25，14，87，51，90，6，19，20），問(wèn)這些元素以怎樣的順序進(jìn)入棧，才能使出棧的順序滿足：8在51前面；90在87的后面；20在14的后面；25在6的前面；19在90的后面。（ D ）。 A）20，6，8，51，90，25，14，19，87 B）51，6，19，20，14，8，87，90，25 C）19，20，90，8，6，25，51，14，87 D）6，25，51，8，20，19，90，87，14 E）25，6，8，51，87，90，19，14，2020. 假設(shè)我們用d=(a1,a2,…,a5),表示無(wú)向圖G的5個(gè)頂點(diǎn)的度數(shù)，下面給出的哪（些）組d 值合理（ BE ）。 A）{5，4，4，3，1} B）{4，2，2，1，1} C）{3，3，3，2，2} D）{5，4，3，2，1} E）{2，2，2，2，2}NOIP2004：3. 某個(gè)車站呈狹長(zhǎng)形，寬度只能容下一臺(tái)車，并且只有一個(gè)出入口。已知某時(shí)刻該車站狀態(tài)為空，從這一時(shí)刻開始的出入記錄為：“進(jìn)，出，進(jìn)，進(jìn)，出，進(jìn)，進(jìn)，進(jìn)，出，出，進(jìn)，出”。假設(shè)車輛入站的順序?yàn)?，2，3，……，則車輛出站的順序?yàn)椋?E ）。A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 3, 5, 4, 6 D. 1, 3, 5, 6, 7 E. 1, 3, 6, 5, 74. 滿二叉樹的葉結(jié)點(diǎn)個(gè)數(shù)為N，則它的結(jié)點(diǎn)總數(shù)為（ C ）。A. N B. 2 * N C. 2 * N – 1 D. 2 * N + 1 E. 2N – 15. 二叉樹T，已知其前序遍歷序列為1 2 4 3 5 7 6，中序遍歷序列為4 2 1 5 7 3 6，則其后序遍歷序列為（ B ）。A. 4 2 5 7 6 3 1 B. 4 2 7 5 6 3 1 C. 4 2 7 5 3 6 1 D. 4 7 2 3 5 6 1 E. 4 5 2 6 3 7 120. 某大學(xué)計(jì)算機(jī)專業(yè)的必修課及其先修課程如下表所示：課程代號(hào)C0C1C2C3C4C5C6C7課程名稱高等數(shù)學(xué)程序設(shè)計(jì)語(yǔ)言離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)編譯技術(shù)操作系統(tǒng)普通物理計(jì)算機(jī)原理先修課程C0, C1C1, C2C3C3, C7C0C6請(qǐng)你判斷下列課程安排方案哪個(gè)（些）是合理的（ BCE ）。A. C0, C1, C2, C3, C4, C5, C6, C7 B. C0, C1, C2, C3, C4, C6, C7, C5C. C0, C1, C6, C7, C2, C3, C4, C5 D. C0, C1, C6, C7, C5, C2, C3, C4E. C0, C1, C2, C3, C6, C7, C5, C4NOIP2005：4. 完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)為4 * N + 3，則它的葉結(jié)點(diǎn)個(gè)數(shù)為（ E ）。A. 2 * N B. 2 * N 1 C. 2 * N + 1 D. 2 * N 2 E. 2 * N + 25. 平面上有五個(gè)點(diǎn)A(5, 3), B(3, 5), C(2, 1), D(3, 3), E(5, 1)。以這五點(diǎn)作為完全圖G 的頂點(diǎn)，每?jī)牲c(diǎn)之間的直線距離是圖G 中對(duì)應(yīng)邊的權(quán)值。圖G 的最小生成樹中的所有邊的權(quán)值綜合為（ D ）。A. 8 B. 7+ 5 C. 9 D. 6+ 5 E. 4+2 2 + 513. 二叉樹T的寬度優(yōu)先遍歷序列為A B C D E F G H I，已知A是C的父結(jié)點(diǎn)，D 是G 的父結(jié)點(diǎn)，F(xiàn) 是I 的父結(jié)點(diǎn)，樹中所有結(jié)點(diǎn)的最大深度為3（根結(jié)點(diǎn)深度設(shè)為0），可知E的父結(jié)點(diǎn)可能是（ BC ）。A. A B. B C. C D. D E. F14. 設(shè)棧S的初始狀態(tài)為空，元素a, b, c, d, e, f, g依次入棧，以下出棧序列不可能出現(xiàn)的有（ CE ）。A. a, b, c, e, d, f, g B. b, c, a, f, e, g, d C. a, e, c, b, d, f, gD. d, c, f, e, b, a, g E. g, e, f, d, c, b, aNOIP2006：4．在編程時(shí)（使用任一種高級(jí)語(yǔ)言，不一定是 Pascal），如果需要從磁盤文件中輸入一個(gè)很大的二維數(shù)組（例如 1000*1000 的 double 型數(shù)組），按行讀（即外層循環(huán)是關(guān)于行的）與按列讀（即外層循 環(huán)是關(guān)于列的）相比，在輸入效率上（ E ）。A. 沒(méi)有區(qū)別 B. 有一些區(qū)別，但機(jī)器處理速度很快，可忽略不計(jì)C. 按行讀的方式要高一些 D. 按列讀的方式要高一些 E. 取決于數(shù)組的存儲(chǔ)方式。7．某個(gè)車站呈狹長(zhǎng)形，寬度只能容下一臺(tái)車，并且只有一個(gè)出入口。已知某時(shí)刻該車站狀態(tài)為空，從 這一時(shí)刻開始的出入記錄為：“進(jìn)，出，進(jìn)，進(jìn)，進(jìn)，出，出，進(jìn)，進(jìn)，進(jìn)，出,出”。假設(shè)車輛入站的 順序?yàn)?1，2，3，……，則車輛出站的順序?yàn)椋? C ）。A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 4, 3, 7, 6D. 1, 4, 3, 7, 2 E. 1, 4, 3, 7, 58．高度為 n 的均衡的二叉樹是指：如果去掉葉結(jié)點(diǎn)及相應(yīng)的樹枝，它應(yīng)該是高度為 n1 的滿二叉樹。在這里，樹高等于葉結(jié)點(diǎn)的最大深度，根結(jié)點(diǎn)的深度為 0，如果某個(gè)均衡的二叉樹共有 2381 個(gè)結(jié)點(diǎn)， 則該樹的樹高為（ B ）。A. 10 B. 11 C. 12 D. 13 E. 210 – 1解析: 均衡二叉樹就是：任意兩個(gè)度不為2的節(jié)點(diǎn)的深度之差不大于1例如： 1 / \ 2 3 \ / 4 5是均衡二叉樹而 1 / \ 2 3 \ / \ 4 5 6 / 7就不是，2和7的深度差2.因?yàn)?^11 = 2048；所以一顆滿二叉樹從深度為0（根節(jié)點(diǎn)）到深度10的總節(jié)點(diǎn)數(shù)是2047，剩下23812047 = 334個(gè)節(jié)點(diǎn)，這剩下的節(jié)點(diǎn)的深度都是11。所以答案為B10．將 5 個(gè)數(shù)的序列排序，不論原先的順序如何，最少都可以通過(guò)（ B ）次比較，完成從小到大的排序。A. 6 B. 7 C. 8 D. 9 E. 1013. 設(shè)棧S的初始狀態(tài)為空，元素a, b, c, d, e 依次入棧，以下出棧序列不可能出現(xiàn)的有（ C ）。A. a, b, c, e, d B. b, c, a, e, dC. a, e, c, b, d D. d, c, e, b, a14. 已知 6 個(gè)結(jié)點(diǎn)的二叉樹的先根遍歷是 1 2 3 4 5 6（數(shù)字為結(jié)點(diǎn)的編號(hào)，以下同），后根遍歷是3 2 5 6 4 1，則該二叉樹的可能的中根遍歷是（ BC ）A. 3 2 1 4 6 5 B. 3 2 1 5 4 6C. 2 3 1 5 4 6 D. 2 3 1 4 6 5NOIP2007：2. 在關(guān)系數(shù)據(jù)庫(kù)中, 存放在數(shù)據(jù)庫(kù)中的數(shù)據(jù)的邏輯結(jié)構(gòu)以( E )為主。 A. 二叉樹 B. 多叉樹 C. 哈希表 D. B+樹 E. 二維表 9. 歐拉圖G是指可以構(gòu)成一個(gè)閉回路的圖，且圖G的每一條邊恰好在這個(gè)閉回路上出現(xiàn)一次（即一筆畫成）。在以下各個(gè)描述中, 不一定是歐拉圖的是：（ D ）。 A. 圖G中沒(méi)有度為奇數(shù)的頂點(diǎn) B. 包括歐拉環(huán)游的圖(歐拉環(huán)游是指通過(guò)圖中每邊恰好一次的閉路徑) C. 包括歐拉閉跡的圖(歐拉跡是指通過(guò)途中每邊恰好一次的路徑) D. 存在一條回路, 通過(guò)每個(gè)頂點(diǎn)恰好一次 E. 本身為閉跡的圖 14. 已知7個(gè)節(jié)點(diǎn)的二叉樹的先根遍歷是1 2 4 5 6 3 7(數(shù)字為結(jié)點(diǎn)的編號(hào)，以下同)， 后根遍歷是4 6 5 2 7 3 1， 則該二叉樹的可能的中根遍歷是（ ABD ） A. 4 2 6 5 1 7 3 B. 4 2 5 6 1 3 7 C. 4 2 3 1 5 4 7 D. 4 2 5 6 1 7 3 19. 在下列關(guān)于算法復(fù)雜性的說(shuō)法中， 正確的有（ BC ）。 A. 算法的時(shí)間復(fù)雜度，是指它在某臺(tái)計(jì)算機(jī)上具體實(shí)現(xiàn)時(shí)的運(yùn)行時(shí)間 B. 算法的時(shí)間復(fù)雜度，是指對(duì)于該算法的一種或幾種主要的運(yùn)算， 運(yùn)算的次數(shù)與問(wèn)題的規(guī)模之間的函數(shù)關(guān)系 C. 一個(gè)問(wèn)題如果是NPC類的， 就意味著在解決該問(wèn)題時(shí)， 不存在一個(gè)具有多項(xiàng)式時(shí)間復(fù)雜度的算法. 但這一點(diǎn)還沒(méi)有得到理論上證實(shí)，也沒(méi)有被否定 D. 一個(gè)問(wèn)題如果是NP類的，與C有相同的結(jié)論 5．將數(shù)組{8, 23, 4, 16, 77, 5, 53, 100}中的元素按從大到小的順序排列，每次可以交換任意兩個(gè)元素，最少需要交換（ B ）次。A. 4 B. 5 C. 6 D. 7 E. 86．設(shè)棧S的初始狀態(tài)為空，元素a，b，c，d，e，f依次入棧S，出棧的序列為b，d，c，f，e，a，則棧S的容量至少應(yīng)該是（ D ）。A. 6 B. 5 C. 4 D. 3 E. 218. 設(shè)T是一棵有n個(gè)頂點(diǎn)的樹，下列說(shuō)法正確的是（ ABC ）。A. T是連通的、無(wú)環(huán)的 B. T是連通的，有n1條邊C. T是無(wú)環(huán)的，有n1條邊 D. 以上都不對(duì)NOIP2009：一個(gè)包含n個(gè)分支結(jié)點(diǎn)（非葉結(jié)點(diǎn)）的非空滿k叉樹，k=1，它的葉結(jié)點(diǎn)數(shù)目為：DA) nk + 1 B) nk1 C) (k+1)n1 D. (k1)n+1 最優(yōu)前綴編碼，也稱Huffman編碼。這種編碼組合的特點(diǎn)是對(duì)于較頻繁使用的元素給與較短的唯一編碼，以提高通訊的效率。下面編碼組合哪一組不是合法的前綴編碼。BA)（00，01，10，11） B)（0，1，00，11） C)（0，10，110，111） D)（1，01，000，001）快速排序平均情況和最壞情況下的算法時(shí)間復(fù)雜度分別為：AA) 平均情況 O(nlog2n)，最壞情況O(n2)B) 平均情況 O(n)， 最壞情況O(n2)C) 平均情況 O(n)， 最壞情況O(nlog2n) D) 平均情況 O(log2n)， 最壞情況O(n2)左圖給出了一個(gè)加權(quán)無(wú)向圖，從頂點(diǎn)V0開始用prim算法求最小生成樹。則依次加入最小生成樹的頂點(diǎn)集合的頂點(diǎn)序列為：AA) V0, V1, V2, V3, V5, V4 B) V0, V1, V5, V4, V3, V3 C) V1, V2, V3, V0, V5, V4 D) V1, V2, V3, V0,