【正文】 55． 高度為 h(h0) 的二叉樹最少有 ________ 個結(jié)點(diǎn) 。 ( ) 5有 31個結(jié)點(diǎn)的二叉樹 15 個結(jié)點(diǎn)的完全二叉樹 (Huffman)樹 答案： 59. 深度為 k的滿二叉樹有 ____個分枝結(jié)點(diǎn)。 ( ) A. 31 B. 32 C. 33 D. 16 答案： 63. 一個二叉樹按順序方式存儲在一個維數(shù)組中，如圖 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B C D E F G H I J 則結(jié)點(diǎn) E 在二叉樹的第 層。 ( ) *(n1) *(n+1) *n 答案： 67. n 個頂點(diǎn)的連通圖至少有 條邊。 ( ) ,15,37 ,30,37 ,15,30 ,15,30,37 答案： 71． 對有 3600 個記錄的索引順序表 (分塊表 )進(jìn)行查找 ,最理想的塊長為 ___。 ( ) ，而其他屬性相同 答案： 75． 用線形探測法查找散列表，可能要探測多個散列地址，這些位置上的鍵值 ____。（設(shè)搜索成功的平均搜索長度為 Snl=(1+1/(1a))/2,其中 a 為裝填因子） ( ) 答案： 78． 對長度為 10 的表作選擇 (簡單選擇 )排序 ,共需比較 ____次關(guān)鍵字。 ( ) A. 選擇排序 B. 直接插入排序 《軟件技術(shù)基礎(chǔ)》試題庫 C. 快速排序 D. 起泡排序 答案： C 81. 對 5 個不同的數(shù)據(jù)元素進(jìn)行直接插入排序，最多需要進(jìn)行 次比較。 ( ) 折半 哈西 分塊 分塊 折半 哈西 折半 哈西 順序 哈西 分塊 折半 答案： B 85. 在下列算法中， 算法可能出現(xiàn)下列情況：在最后一趟開始之前，所有的元素都不在其最終的位置上。 ( ) 答案： 89．下列關(guān)鍵字序列中 是堆。 ( ) A. 集合 B. 線形結(jié)構(gòu) C. 樹型結(jié)構(gòu) D. 圖型結(jié)構(gòu) 答案： ABCD 2． 數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中有 兩種不同的表示方法。 ( ) 《軟件技術(shù)基礎(chǔ)》試題庫 答案： T 3． 非空線性表中任意一個數(shù)據(jù)元素都有且僅有一個直接后繼元素。 ( ) 答案： F 儲結(jié)構(gòu)，每個數(shù)據(jù)元素占用 4 個存儲單元，第 12 個數(shù)據(jù)元素的存儲地址為 144，則第 1 個數(shù)據(jù)元素的存儲地址是 101。 ( ) 答案： T p 所指的結(jié)點(diǎn)后面插入一個由 q 所指的結(jié)點(diǎn)的過程是依次執(zhí) 行語句：link(q)←link(p)。 ( ) 答案： T 14. 刪除非空鏈?zhǔn)酱鎯Y(jié)構(gòu)的堆棧 ( 設(shè)棧頂指針為 top) 的一個元素的過程是依次執(zhí)行 :p←top,top ←link(p),call RET(p) 。 ( ) 答案： F 18． 在順序表中取出第 i 個元素所花費(fèi)的時間與 i 成正比。 ( ) 答案： T 22．帶權(quán)連通圖的最小生成樹的權(quán)值之和一定小于它的其它生成樹的權(quán)值之和。 ( ) 答案： T 26．哈希表的查找效率主要取決于所選擇的哈希函數(shù)與處理沖突的方法。 答案： 4． n(n0) 個結(jié)點(diǎn)二叉樹對應(yīng)的森林最多包含 _______________ 棵非空樹。 答案： 8． 圖的深度優(yōu)先搜索方法類似于二叉樹的 _________遍歷。這種排序法稱為 _________排序法。 答案： 14． 一個數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示 (映象 )稱為 ________________ 。 答案： 18．線性表中 ____________________________ 稱為表的長度。 答案： 從任何一個結(jié)點(diǎn)出發(fā)可以遍歷所有結(jié)點(diǎn) 22．在一個單鏈表中刪除 p 所指結(jié)點(diǎn)的下一個結(jié)點(diǎn)時，應(yīng)執(zhí)行以下操作： q=plink。該緩沖區(qū)應(yīng)該是一個 結(jié)構(gòu)，其主要特點(diǎn)是 。 答案： 29． n(n0) 個結(jié)點(diǎn)、 (n1) 條邊的連通無向圖中，頂點(diǎn)度數(shù)最大值為 _______________ 。 答案： 33．一棵深度為 4 的二叉樹最多有 _______ 個結(jié)點(diǎn)。 答案： 37．若已知一棵二叉樹的先序序列為 – + a * b – c d / e f，中序序列為 a + b * c – d – e / f，則其后序序列為 ___________。 答案： 41．在有 n 個頂點(diǎn)的有向圖中，每個頂點(diǎn)的度最大可達(dá) 。 答案： 45． 順序查找 n 個元素的順序表 ,當(dāng)使用監(jiān)視哨時 ,若查找成功 ,比較關(guān)鍵字的次數(shù)至少為 ___次 , 最多為 ____次；若查找失敗 ,比較關(guān)鍵字的次數(shù)為 ____次。 2．什么樣的圖是連通圖？ 答案： 在無向圖 G 中，如果從一個頂點(diǎn) vi 到另一個頂點(diǎn) vj(i≠j)有路徑，則稱頂點(diǎn) vi 和頂點(diǎn)vj 是連通的，若圖中任意兩頂點(diǎn)間都是相通的，則稱此圖是 連通圖 。 答案 ： 6． 二叉樹的順序存儲結(jié)構(gòu) : 答案： 7． 給定 30 個字符組成的電文 : D D D D D A A A B E E A A F C D A A C A B B C C C B A A D D 試為字符 A、 B、 C、 D、 E、 F 設(shè)計(jì)哈夫曼 (Huffman)編碼。 《軟件技術(shù)基礎(chǔ)》試題庫 二叉樹 答案： 10． 試用孩子兄弟 (左孩子右兄弟 )表示法畫出下列樹的存儲結(jié)構(gòu)圖。 答案： 14．有 9 個帶權(quán)結(jié)點(diǎn) a、 b、 c、 d、 e、 f、 g、 h、 I，分別帶權(quán) 4， 2， 7， 12， 6， 10， 5， 9，3，試以他們?yōu)槿~子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹（請按照左子樹根結(jié)點(diǎn)的權(quán)小于等于右子樹根結(jié)點(diǎn)的權(quán)的次序構(gòu)造）。 答案： 16．圖的鄰接矩陣 : 答案： 17． 有向圖的逆鄰接表 : 答案： 18．找出下面網(wǎng)絡(luò)的最小生成樹。 答案： 23． 已某個不帶權(quán)的無向圖采用鄰接矩陣存儲方法依次將頂點(diǎn)的數(shù)據(jù)信息存放于一維數(shù)組ABCDEFGH 中，邊的信息存放于鄰接矩陣中，鄰接矩陣為 5 4 6 2 3 1 10 15 4 10 30 4 10 15 2 20 《軟件技術(shù)基礎(chǔ)》試題庫 請寫出從頂點(diǎn) A 出發(fā)對該圖進(jìn)行深度有限搜索后得到的頂點(diǎn)序列。 答案： 25．已知一關(guān)鍵字序列為（ 40， 11， 16， 31， 23， 55， 13， 45， 50），試生成一棵平衡的二叉排序樹 ,再從生成的平衡的二叉排序樹中刪除關(guān)鍵字 45。 答案： 27．設(shè)待排序序列為 {10, 18, 4, 3, 6, 12, 1, 9, 15, 8}，請給出用希爾排序每一趟的結(jié)果。 答案： 0 1 1 0 0 0 0 0 1 0 0 0 1 0 1 1 1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 《軟件技術(shù)基礎(chǔ)》試題庫 第三章 操作系統(tǒng) 一、單項(xiàng)選擇題 1. 操作系統(tǒng)的功能是進(jìn)行處理機(jī)管理、（ ）管理、設(shè)備管理和文件管理?，F(xiàn)有三個同時到達(dá)的作業(yè) J1，J2 和 J3， 它們的執(zhí)行時間分別是 T1， T2 和 T3，且 T1T2T3。 A．加 1 B．減 1 C．等于 0 D．小于 0 答案： B 1通常，用戶編寫的程序中所使用的地址是（ ）。 A．設(shè)備獨(dú)立性 B．設(shè)備分配 C．緩沖管理 D．虛擬設(shè)備 答案： A 1引入緩沖技術(shù)的主要目的是（ ）。 ，后者是由系統(tǒng)自動生成 ，后者是操作系統(tǒng)控制的單位 ，后者是分時的 ，前者則不行 答案： AC 三、判斷題 1．批處理系統(tǒng)的主要優(yōu)點(diǎn)是系統(tǒng)的吞吐量大、資源利用率高、 系統(tǒng)的開銷較小。（ ）答案： F 5．原語是一種不可分割的操作。 （）答案： T 9．并發(fā)性是指若干個事件在不同時刻間隔發(fā)生。答案： T 12．操作系統(tǒng)“生成”是指能產(chǎn)生最適合用戶自己工作環(huán)境的操作系統(tǒng)內(nèi)核。答案： F 16．引導(dǎo)操作系統(tǒng)進(jìn)入內(nèi)存的程序一般 放在計(jì)算機(jī)的固件中。答案： T 20．一個物理硬盤可以分成多個邏輯硬盤分區(qū)進(jìn)行面向用戶文件系統(tǒng)的管理。 3．臨界資源與臨界區(qū) 答案：一次僅允許一個進(jìn)程使用的資源稱為臨界資源 (Critical Resource)。 五、簡單題 /計(jì)算題 1．單道環(huán)境下四個作業(yè)，它們進(jìn)入系統(tǒng)的時間如下： 作業(yè) 進(jìn)入時 間 估計(jì)完成時間（分鐘） 1 8： 00 120 2 8： 50 50 3 9： 00 10 4 9： 50 20 (1)給出 FCFS , SJF 下的作業(yè)執(zhí)行次序 (2)給出 FCFS , SJF 下的作業(yè)平均周轉(zhuǎn)時間和帶權(quán)平均周轉(zhuǎn)時間 答案： 作業(yè) 進(jìn)入時間 估計(jì)運(yùn)行時間 SJF 完成時間 FCFS 完成時間 1 8： 00 120 10： 00 10： 00 2 8： 50 50 11： 20 10： 50 3 9： 00 10 10： 10 11： 00 4 9： 50 20 10： 30 11： 20 FCFS : T= ( 120+120+120+90 ) / 4 = SJF: T=（ 120+150+70+40） /4=95 FCFS： W=（ 120/120 + 120/50 +120/10+90/20） /4= SJF: W=（ 120/120 + 150/50 + 70/10+40/20） /4= 2．假定系統(tǒng)中有五個進(jìn)程 {P P P P P5}和三種類型資源 {A、 B、 C}，每一種資源的數(shù)量分別為 1 20。 所以 T0 時刻系統(tǒng)是安全的。 3） P4 請求資源 Request4(3,3,0)是否允許？ Request4(3,3,0)≤ Need4(4,3,1)， P4 請求在最大需求范圍內(nèi)。① 互斥條件。 《軟件技術(shù)基礎(chǔ)》試題庫 (1) 當(dāng)某一進(jìn)程要求設(shè)備輸入數(shù)據(jù)時， CPU 把準(zhǔn)備存放輸入數(shù)據(jù)的內(nèi)存始址及要傳送的字節(jié)數(shù)據(jù)分別送入 DMA 控制器中的內(nèi)存地址寄存器和傳送字節(jié)計(jì)數(shù)器。 (5) 輸入完成時， DMA 控制器通過中斷請求線發(fā)出中斷信號， CPU 接收到后轉(zhuǎn)中斷處理程序進(jìn)行善后處理。 （ 2）按 LRU 調(diào)度算法將產(chǎn)生 次缺頁中斷，依次淘汰的頁號為 ，缺頁中斷率為 。 7. OSI 模型中，物理層規(guī)定了物理接口的 _________、 ___________、 ___________和 _________特性。 10. MAC 地址中 _____________部分被稱為機(jī)構(gòu)惟一標(biāo)識符。 答案： 1. 總線型、星型、環(huán)型、星型、星型 2. 終結(jié)器、發(fā)送方 3. 185 米、 500 米、 10Base 10Base5 4. 地面微波接力、衛(wèi)星通信 5. 數(shù)據(jù)鏈路層 6. 開放系統(tǒng)互聯(lián) /參考模型 7. 機(jī)械特性、電氣特性、功能特性、過程特性、路由選擇 8. 過濾、復(fù)制、泛洪 9. 對信號進(jìn)行整形、再生和放大 10. 前三個字節(jié) 11. 網(wǎng)絡(luò)號、主機(jī)號、在進(jìn)行尋址時先按網(wǎng)絡(luò)號找到網(wǎng)絡(luò)，再從該網(wǎng)絡(luò)中找到主機(jī) 12. 點(diǎn)分的十進(jìn)制表示形式 13. B、 直接廣播地址 本地廣播地址 二、選擇題 ，屬于 ______。 A. 局域網(wǎng) /廣域網(wǎng) B. 對等網(wǎng) /城域網(wǎng) C. 環(huán)型網(wǎng) /星型網(wǎng) D. 有線網(wǎng) /無線網(wǎng) 5. 如果某種局域網(wǎng)的拓?fù)浣Y(jié)構(gòu)是 _______的，則局域網(wǎng)中任何一個節(jié)點(diǎn)出現(xiàn)故障都不會影響整個網(wǎng)絡(luò)的工作 A. 總線型結(jié)構(gòu) B. 環(huán)型結(jié)構(gòu) C. 樹型結(jié)構(gòu) D. 星型結(jié)構(gòu) 6. 雙絞線的特點(diǎn)是 ________。 A. B. C. D. 22. 下列協(xié)議中不能用于獲取 IP 地址的是 ________。 A. 集線器 B. 網(wǎng)橋 C. 交換機(jī) D. 路由器 答案： 1 2 3 4 5 6 7 8 9 0 B A D B A ABCD B C B