【正文】 A. 172, B. C. D. 24. 下面選項(xiàng)中不屬于組織機(jī)構(gòu)域名的是 _______。 A. 第一層 B. 第二層 C. 第三層 D. 第四層 18. 下列選項(xiàng)中，能夠指定給某個(gè)具體主機(jī)的 IP 地址是 _____ A. B. C. D. 19. 以下哪幾個(gè)是正確的子網(wǎng)號(hào)表示方法 ______ A. 255. 255. 0. 0 B. 187. 230. 34. 0 C. D. 132. 43. 66. 22 20. 下列地址中 _______是 B 類地址。 A. 硬件、軟件、數(shù)據(jù)、通信信道 B. 主機(jī)、外設(shè)、軟件、通信信道 《軟件技術(shù)基礎(chǔ)》試題庫 C. 硬件、程序、數(shù)據(jù)、通信信道 D. 主機(jī)、程序、數(shù)據(jù)、通信信道 3. 計(jì)算機(jī)互聯(lián)的主要目的是 ______。 13. 主機(jī) 屬于 ___類網(wǎng)絡(luò)，其網(wǎng)絡(luò)號(hào)是 ______。 8. 網(wǎng)橋?qū)λ邮盏降臄?shù)據(jù)幀的處理方式有 __________、 ___________和 ____________三種。 2. 在總線結(jié)構(gòu)中，數(shù)據(jù)在傳輸完畢后，由 ______負(fù)責(zé)吸收掉總線上的信息流。 (7) 當(dāng)操作系統(tǒng)進(jìn)程調(diào)度程序調(diào)度到該進(jìn)程時(shí)，該進(jìn)程按指定的內(nèi)存始址和實(shí)際傳送的數(shù)據(jù)對(duì)輸入數(shù)據(jù)進(jìn)行加工處理。 (3) 該進(jìn)程進(jìn)入等待狀態(tài)，等待數(shù)據(jù)輸入的完成，操作系統(tǒng)進(jìn)程調(diào)度程序調(diào)度其他進(jìn)程占用CPU。③不剝奪條件。 3．什么是死鎖？產(chǎn)生死鎖的四個(gè)必要條件是什么？ 答案：所謂死鎖 (Deadlock)，是指多個(gè)進(jìn)程因競(jìng)爭(zhēng)資源而造成的彼此無休止地互相等待，在無外力作用下永遠(yuǎn)不能擺脫的僵局，這種僵局使參與的進(jìn)程永遠(yuǎn)不能向前推進(jìn)。 Request1(1,0,2)≤ Available(3,3,2)，可用資源可滿足 P1 請(qǐng)求需要。 《軟件技術(shù)基礎(chǔ)》試題庫 Max Allocation Need Available A B C A B C A B C A B C P1 5 5 9 2 1 2 3 4 7 2 3 3 P2 5 3 6 4 0 2 1 3 4 P3 4 0 11 4 0 5 0 0 6 P4 4 2 5 2 0 4 2 2 1 P5 4 2 4 3 1 4 1 1 0 試問：① T0 時(shí)刻是否安全？若是請(qǐng)給出安全序列。我們把這種互斥執(zhí)行的程序段稱為臨界區(qū) (Critical Section)或互斥段。 2．地址重定位。答案： T 18．具有多道功能的操作系統(tǒng)一定是多用戶操作系統(tǒng)。答案： F 14．實(shí)時(shí)操作系統(tǒng)的響應(yīng)系數(shù)最大，設(shè)備利用率最高。它由專門負(fù)責(zé) I/O 的常駐內(nèi)存的進(jìn)程以及輸入、輸出井組成。（ ）答案： F 7．對(duì)臨界資源應(yīng)采取互斥訪問方式來實(shí)現(xiàn)共享。（ ）答案： T 3．單級(jí)目錄結(jié)構(gòu)能夠解決文件重名問題。 A．預(yù)防 B．避免 C．檢測(cè) D．恢復(fù) 答案： B 二、多項(xiàng)選擇題 1．引入多道程序設(shè)計(jì)的主要目的在于（ ） A、提高實(shí)時(shí)響應(yīng)速度 B、充分利用處理機(jī)，減少處理機(jī)空閑時(shí)間 C、有利于代碼共享 D、充分利用外圍設(shè)備 E、減少存儲(chǔ)器碎片 答案： BD 2．段式和頁式存儲(chǔ)管理的地址結(jié)構(gòu)很類似，但是它們之間有實(shí)質(zhì)上的不同，表現(xiàn)為 （ ） A、頁式的邏輯地址是連續(xù)的，段式的邏輯地址可以不連續(xù) B、頁式的地址是一維的，段式的地址是二維的 C、分頁是操作系統(tǒng)進(jìn)行的，分段是用戶確定 的 D、各頁可以分散存放在主存，每段必須占用連續(xù)的主存空間 E、頁式采用靜態(tài)重定位方式，段式采用動(dòng)態(tài)重定位方式 答案： ABCD 3．利用記錄的成組與分解操作能（ ） A、有效地實(shí)現(xiàn)信息轉(zhuǎn)儲(chǔ) B、提高存儲(chǔ)介質(zhì)的利用率 C、減少操作系統(tǒng)的程序量 D、增加啟動(dòng)外設(shè)的次數(shù) E、提高文件的存取速度 答案： ABE 4．線程是操作系統(tǒng)的概念，已具有線程管理的操作系統(tǒng)有（ ） A、 Windows 《軟件技術(shù)基礎(chǔ)》試題庫 B、 OS/2 C、 Windows NT D、 DOS E、 Mach 答案： BCE ( )和 ( )組成。 A．?dāng)U大物理內(nèi)存容量 B．?dāng)U大物理外存容量 C．?dāng)U大邏輯內(nèi)存容量 D．?dāng)U大邏輯外存容量 答案： C 1在以下的文件物理存儲(chǔ)組織形式中，（ ）常用于存放大型的系統(tǒng)文件。 A． 9 B． 10 C． 11 D． 12 答案： B 1操作系統(tǒng)的基本職能是（ ）。 答案： B 4. 操作系統(tǒng)中采用多道程序設(shè)計(jì)技術(shù)提高 CPU 和外部設(shè)備的（ ）。 答案： 28．對(duì)于給定鍵值： 83， 40， 63， 12， 35， 90， 65, 畫出堆排序各趟排序的結(jié)果。試畫出用線性探查法解決沖突時(shí)所構(gòu)成的散列表。 (1)試畫出插入完成之后的二叉排序樹； (2)若查找元素 17,它將依次與二叉排序樹中哪些元素比較大小 ? (3)假設(shè)每個(gè)元素的查找概率相等 ,試計(jì)算該樹的平均查找長(zhǎng)度 ASL。 《軟件技術(shù)基礎(chǔ)》試題庫 圖 答案： 21．對(duì)下面的帶權(quán)無向圖采用 prim 算法從頂 點(diǎn) ① 開始構(gòu)造最小生成樹。 (2) 寫出結(jié)點(diǎn) D 的雙親結(jié)點(diǎn)及左、右子女。 答案： 12． 試用雙親表示法畫出下列樹 T 的存儲(chǔ)結(jié)構(gòu)圖。 答案： 8． 試將森林 F={ T1,T2,T3,T4 }轉(zhuǎn)換為一棵二叉樹。 答案： 六、操作題 /綜合能力題 1．若對(duì)序列 (76， 38， 65， 13， 97， 27， 50， 49)采用 冒泡 排序法 (按照值的大小從小到大 )進(jìn)行排序， 共需幾趟排序？ 請(qǐng)分別 在下表中寫出每一趟的結(jié)果： 原始序列 76 38 65 13 97 27 50 49 答案： 共需 5 趟 第 1 趟結(jié)果 38 65 13 76 27 50 49 97 第 2 趟結(jié)果 38 13 65 27 50 49 76 97 第 3 趟結(jié)果 13 38 27 50 49 65 76 97 第 4 趟結(jié)果 13 27 38 49 50 65 76 97 第 5 趟結(jié)果 13 27 38 49 50 65 76 97 2． 若對(duì)序列 (76， 38， 65， 13， 97， 27， 50， 49)采用 選擇 排 序法 (按照值的大小從小到大 )進(jìn)行排序，請(qǐng)分別在下表中寫出每一趟的結(jié)果： 原始序列 76 38 65 13 97 27 50 49 答案： 第 1 趟結(jié)果 76 38 65 13 49 27 50 97 第 2 趟結(jié)果 50 38 65 13 49 27 76 97 第 3 趟結(jié)果 50 38 27 13 49 65 76 97 第 4 趟結(jié)果 49 38 27 13 50 65 76 97 第 5 趟結(jié)果 13 38 27 49 50 65 76 97 第 6 趟結(jié)果 13 27 38 49 50 65 76 97 第 7 趟結(jié)果 13 27 38 49 50 65 76 97 3． 把 1 、 2 、 3 、 4 依次進(jìn)棧（棧初始為空），任何時(shí)刻（只要棧不空），都可以出（退）《軟件技術(shù)基礎(chǔ)》試題庫 棧，試寫出所有可能的出棧序列（如 1234 ）。 答案： 快速排序、堆排序 、 希爾排序 《軟件技術(shù)基礎(chǔ)》試題庫 五、簡(jiǎn)答題 /問答題 /綜述題 1．什么是 順序表 ？ 順序表的 特點(diǎn) 是什么 ？ 答案： 線性表的順序存儲(chǔ)是指在內(nèi)存中用一塊地址連續(xù)的存儲(chǔ)空間順序存放線性表的各元素，用這種形式存儲(chǔ)的線性表稱為順序 表。 答案： 43． 有 n 個(gè)球隊(duì)參加的足球聯(lián)賽按主客場(chǎng)制進(jìn)行比賽，共需進(jìn)行 場(chǎng)比賽。 答案： 39．已知二叉樹有 50 個(gè)葉子結(jié)點(diǎn)，且僅有一個(gè)孩子的結(jié)點(diǎn)數(shù)為 30，則總結(jié)點(diǎn)數(shù)為 。 答案： 35．哈夫曼樹是帶權(quán)路徑長(zhǎng)度 的樹，通常權(quán)值較大的結(jié)點(diǎn)離根結(jié)點(diǎn) 。 答案： 31．若一棵二叉樹中有 8 個(gè)度為 2 的結(jié)點(diǎn) ,則它有 _____個(gè)葉子。 答案： r=f、 (r+1)%m=f 27．在具有 n 個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有 _______個(gè)元素。 答案： 《軟件技術(shù)基礎(chǔ)》試題庫 24．棧中元素的進(jìn)出原則為 _____________________ 。 答案： 20．在單鏈表中要在已知結(jié)點(diǎn) *p 之前插入一新結(jié)點(diǎn)，需找到 。 答案： 16．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的 _____無關(guān)，是獨(dú)立 于計(jì)算機(jī)的。這種排序法稱為 _________排序法。 答案： 2,4,6,8,10,12,14,16,18,20 依次存放于一個(gè)一維 數(shù)組中，然后采用折半查找方法查找元素 12，被比較過的數(shù)組元素的下標(biāo)依次為 _________。 答案： 6． n(n0) 個(gè)結(jié)點(diǎn)、 (n1) 條邊的連通無向圖中，頂點(diǎn)度數(shù)最大值為 _______________ 。 答案： LOC(a1)+(n1)k 2．若一棵二叉樹有 10 個(gè)葉結(jié)點(diǎn)，則該二叉樹中度為 2 的結(jié)的點(diǎn)個(gè)數(shù)為 ______________。（ ） 答案： T 24．折半查找方法適用于按值有序的線性鏈表的查找。 ( ) 答案： F 20．已知一棵二叉樹的前序序列和中序序列可以唯一地構(gòu)造出該二叉樹。( ) 《軟件技術(shù)基礎(chǔ)》試題庫 答案： F 16．?dāng)?shù)據(jù)結(jié)構(gòu)概念包括數(shù)據(jù)之間的邏輯結(jié)構(gòu)，數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式和數(shù)據(jù)的運(yùn)算三個(gè)方面 。 ( ) 答案： T q 所指的結(jié)點(diǎn)后面插入一個(gè)由 p 指的結(jié)點(diǎn)的動(dòng)作依次為：llink(p)←q,rlink(p)←rlink(q),rlink(q)←p,llink(rlink(q))←p 。 ( ) 答案： F link(p)出現(xiàn)在表達(dá)式中表示 p 所指的那個(gè)結(jié)點(diǎn)的內(nèi)容。 ( ) 答案： F 5． 線性鏈表中各個(gè)鏈結(jié)點(diǎn)之間的地址不一定要連續(xù)。 ( ) 答案： BD 三、判斷題 1．非空線 性表中任意一個(gè)數(shù)據(jù)元素都有且僅有一個(gè)直接前驅(qū)元素。 ( ) A．插入排序 《軟件技術(shù)基礎(chǔ)》試題庫 B．直接選擇排序 C．快速排序 D．冒泡排序 答案： B 91．對(duì) n 個(gè)不同的排序碼進(jìn)行冒泡排序，在元素?zé)o序的情況下比較的次數(shù)為 。 ( ) = K2i = K2i+1 K2i+1 K2i = K2i 且 Ki =K2i+1 D. Ki = K2i 或 Ki = K2i+1 答案： 87．對(duì)于關(guān)鍵字序列 {46 ， 58 ， 15 ， 45 ， 90 ， 18 ， 10 ， 62} ，其快速排序第一趟的結(jié)果是 。 ( ) 順序存儲(chǔ)結(jié)構(gòu) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 順序存儲(chǔ)結(jié)構(gòu) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 答案： 83. 從未排序序列中依次取出一個(gè)元素與已排序序列中的元素依次進(jìn)行比較，然后將其存放在已排序序列的合適位置，該排序方法稱為 排序法。 A. 6 B. 7 C. 8 D. 10 答案： 80. 對(duì)待排序的元素序列進(jìn)行劃分，將其分為左、右兩個(gè)子序列，再對(duì)兩個(gè)子序列施加同樣的排序操作，直到子序列為空或只剩一個(gè)元素為止。插入后的雜湊表應(yīng)該如________________所示。 ( ) 6 5 4 3 答案： B 73. 中序遍歷一棵二叉排序樹所得到的結(jié)點(diǎn)序列是鍵值的 序列。 ( ) A． 1/2 B． 1 C． 2 D． 4 答案： 69．在含 n 個(gè)頂點(diǎn)和 e 條邊的無向圖的鄰接矩陣中 ,零元素的個(gè)數(shù)為 ____。 ( ) A． 4 B． 5 C． 6 《軟件技術(shù)基礎(chǔ)》試題庫 D． 7 答案： 65． n 個(gè)頂點(diǎn)的帶權(quán)無向連通圖的最小生成樹包含 ________ 個(gè)頂點(diǎn) 。 ( ) 答案： A 61. 二叉樹第 i(i=1)層上至多有