【正文】 ,2,2)， P1 請求在最大需求范圍內(nèi)。② 保持請求條件。 (6) 中斷處理結束時， CPU 返回被中斷進程處執(zhí)行。網(wǎng)絡層的主要任務是 ____________。 A. MAN B. LAN C. WAN 2. 計算機網(wǎng)絡中可以共享的資源包括 ______。 A. RARP B. DHCP C. ARP D. BOOTP 23. 下列網(wǎng)絡地址中不是私有地址的是 __________。 A. B. C. D. 21. 下列選項中不能夠作為子網(wǎng)掩碼的是 _______。若該主機要給 IP 地址是 的主機所在的網(wǎng)絡廣播一個報文，其目的 IP 地址是 ____________，該地址稱為 _____廣播地址；若該主機要給自己所在網(wǎng)絡的所有主機廣播一個報文，目的 IP 地址是 ____________，該地址稱為 _____廣播地址。而在環(huán)形結構中，由 _____負責吸收掉環(huán)上的信息流 3. 在無中繼設備的情況下，同軸電纜的細纜最遠可傳輸 _______米，粗纜可傳輸 ______米，《軟件技術基礎》試題庫 相應的 以太網(wǎng)標準分別是 ____________和 ____________ 4. 微波通信包含的兩種方式是 ______________________和 ________________________ 5. 負責數(shù)據(jù)在計算機之間進行無差錯傳遞也就是負責完成數(shù)據(jù)校驗過程的是 ______ 6. OSI/RM 的全稱是 _______________________________________。 (4) 在 DMA 控制器的控制下，按內(nèi)存地址寄存器中的內(nèi) 容把數(shù)據(jù)緩沖寄存器的數(shù)據(jù)源源不斷地寫入到相應的主存單元，直至所有的數(shù)據(jù)全部傳送完畢。 產(chǎn)生死鎖的必要條件如下。 ②在 T0 時刻進程 P2 請求資源 Request1(0,3,4)是否允許？為什么？ ③在②的基礎上進程 P4 請求資源 Request4(2,0,1)是否允許？為什么？ 答案：（ 1） T0 時刻是否安全？ 可找出一個序列 (P1 、 P P4 、 P2 、 P0)使各進程順序地一個個地執(zhí)行完成。 答案：這種由于 用戶程序裝入內(nèi)存而引起的地址空間中的相對地址轉(zhuǎn)化為存儲空間中的絕對地址的地址變換過程，稱為地址重定位，也稱地址映射。答案： T 15． UNIX 的最大特點是分時、多用戶、多任務和倒樹型文件結構。（ ）答案： T 8．進程有就緒、運行、阻塞三種基本狀態(tài)。 答案： CD ( )和 ( )。 A．控制和管理系統(tǒng)內(nèi)各種資源，有效地組織多道程序的運行 B．提供用戶界面，方便用戶使用 C．提供方便的可視化編輯程序 D．提供功能強大的網(wǎng)絡管理工具 答案： A 1如果進程 PA 對信號量 S 執(zhí)行 P 操作，則信號量 S 的值應（ ）。 答案： 29．若對序列 (49， 38， 65， 97， 76， 13， 27， 50)采用選擇排序法排序，則各趟結束后序列。 (4)對該樹進行中序遍歷 ,試寫出中序遍歷序列。 (3) 將此二叉樹看作森林的二叉樹表示，試將它還原為森林。 T1 T2 T3 T4 答案： 9． 試畫出下列二叉樹的中序線索二叉樹存儲結構圖。數(shù)據(jù)元素在順序表中物理位置取決于數(shù)據(jù)元素在線性表中的邏輯位置，可得出順序表的特點：邏輯位置相鄰，其物理位置也相鄰。 答案： 40．具有 10 個頂點的無向圖 ,邊的總數(shù)最多為 _____________ 。 答案： 32．樹中結點 A 的 ____________________ 稱為 結點 A 的度。 答案： 25．在解決計算機主機與打印機之間速度不匹配問題時通常設置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則從該緩沖區(qū)中取出數(shù)據(jù)打印。 答案： 17．一個算法具有 5 個特性 :__________、 __________、 ___________、有零個或多個輸入、有一個或多個輸出。 答案： ，然后將其放在已經(jīng)排好序的序列的合適位置。 答案： 4 《軟件技術基礎》試題庫 3． 設 SQ 為循環(huán)隊列，存儲在數(shù) 組 d[m] 中，則 SQ 出隊操作對其隊頭指針 front 的修改是 _______________ 。 ( ) 答案： T 21．有向圖是一種非線性結構。 ( ) 答案： F 1,2,3,4，則 4,3,1,2 不可能是堆棧的輸出序列之一。 ( ) 答案： T 6． 若頻繁地對線性表進行插入和刪除操作，該線性表采用順序存儲結構更合適。 ( ) A． n+1 B． n C． n1 D． n(n1)/2 答案： 二、多項選擇題 1．根據(jù)數(shù)據(jù)元素之間的不同特性，通常具有 這幾種基本數(shù)據(jù)結構。 ( ) 答案： 84. 就平均查找速度而言，下列幾種查找速度從慢至快的關系是 。 ( ) A. 0 1 2 3 4 5 6 THU TUE WED FRI SUN SAT MON B. 0 1 2 3 4 5 6 TUE THU WED FRI SUN SAT MON C. 0 1 2 3 4 5 6 TUE THU WED FRI SAT SUN MON D. 0 1 2 3 4 5 6 TUE THU WED SUN SAT FRI MON 答案： 77． 設有一個含 200 個表項的散列表，用線性探查法解決沖突，按關鍵碼查詢時找到一個表項的平均探查次數(shù)不超過 ，則散列存儲空間應能夠至少容納 個表項。 ( ) A． e B． 2e C． n2－ e D． n2－ 2e 答案： D 70． 折半查找有序表 (6,15,30,37,65,68,70,72,89,99),若查找元素 37,需依次與表中元素 ____進《軟件技術基礎》試題庫 行比較。 ( ) i i i－１ i－１ 答案： 62. 在一棵具有 5 層的滿二叉樹中結點總數(shù)為 ____。 ( ) =rare+1 =(rare+1)%(m1) =(rare1)%m =(rare+1)%m 答案： 54. 將遞歸算法轉(zhuǎn)換成對應的非遞歸算法時，通常需要使用 ____。 ( ) A. 插入操作更加方便 B. 通常不會出現(xiàn)棧滿的情況 C. 不會出現(xiàn)?？盏那闆r D. 刪除操作更加方便 答案： 46. 在一個順序存儲的循環(huán)隊列中，隊頭指針指向隊頭元素的 _____。 ( ) 答案： 38. 線性表的鏈接實現(xiàn)有利于 運算。 link=plink。（ ） ，可以為空 有限系列，不能為空 ，可以為空 ，不能為空 答案： A 30. ____是線性表。 ( ) 答案： D 22．關于順序存儲的敘述中 ,哪一條是不正確的 。 ( ) 答案： B 14． 算法分析的目的是 ____。 ( ) A. link(s)←link(p) ， link(p)←s B. link(q)←s ， link(s)←p C. link(p)←link(s) ， link(s)←p D. link(p)←s ， link(s)←q 答案： B 3． 高度為 h(h0) 的二叉樹最少有 ________個結點 。 A. 直接與關鍵字個數(shù)有關 B. 直接與裝填因子 a 有關 C. 直接與表的容量有關 D. 直接與散列函數(shù)有關 答案： D 6． 樹型結構最適合用來描述 ( ) 答案： C 7． 若二叉樹中度為 2 的結點有 15 個，度為 1 的結點有 10 個 _______個葉結點。 ( ) 答案： B 17．數(shù)據(jù)結構是研究數(shù)據(jù)的 及它們之間的相互聯(lián)系。（ ） +(i1)*m B. da+i*m *m +(i+1)*m 答案： A 25．鏈表是一種采用 存儲結構存儲的線性表 。 ( ) 《軟件技術基礎》試題庫 (Hash)表 答案： C 33. 在一個單鏈表中，若 p 所指結點不是最后結點，在 p 之后插入 s 所指結點，則執(zhí)行 ___。slink=p。 ( ) next=pnextnext B. p=pnext = pnextnext next=p 答案： A 41. 向一個有 127 個元素順序表中插入一個新元素并保存原來順序不變，平均要移動 個元素。 ( ) =0 B. top=maxSize =maxSize =1 答案： 《軟件技術基礎》試題庫 49. 在數(shù)組表示的循環(huán)隊列中， front、 rear 分別為隊列的頭、尾指針 ， maxSize 為數(shù)組的最大長度，隊滿的條件是 _____。 ( ) 答案： 57． 有 n(n0)個結點的完全二叉樹的深度是 ____。 ( ) A． 4 B． 5 C． 6 《軟件技術基礎》試題庫 D． 7 答案： 65． n 個頂點的帶權無向連通圖的最小生成樹包含 ________ 個頂點 。 ( ) 6 5 4 3 答案： B 73. 中序遍歷一棵二叉排序樹所得到的結點序列是鍵值的 序列。 A. 6 B. 7 C. 8 D. 10 答案： 80. 對待排序的元素序列進行劃分，將其分為左、右兩個子序列，再對兩個子序列施加同樣的排序操作，直到子序列為空或只剩一個元素為止。 ( ) = K2i = K2i+1 K2i+1 K2i = K2i 且 Ki =K2i+1 D. Ki = K2i 或 Ki = K2i+1 答案： 87．對于關鍵字序列 {46 ， 58 ， 15 ， 45 ， 90 ， 18 ， 10 ， 62} ，其快速排序第一趟的結果是 。 ( ) 答案： BD 三、判斷題 1．非空線 性表中任意一個數(shù)據(jù)元素都有且僅有一個直接前驅(qū)元素。 ( ) 答案： F link(p)出現(xiàn)在表達式中表示 p 所指的那個結點的內(nèi)容。( ) 《軟件技術基礎》試題庫 答案： F 16．數(shù)據(jù)結構概念包括數(shù)據(jù)之間的邏輯結構，數(shù)據(jù)在計算機中的存儲方式和數(shù)據(jù)的運算三個方面 。（ ） 答案： T 24．折半查找方法適用于按值有序的線性鏈表的查找。 答案： 6． n(n0) 個結點、 (n1) 條邊的連通無向圖中，頂點度數(shù)最大值為 _______________ 。這種排序法稱為 _________排序法。 答案： 20．在單鏈表中要在已知結點 *p 之前插入一新結點，需找到 。 答案： r=f、 (r+1)%m=f 27．在具有 n 個單元的循環(huán)隊列中，隊滿時共有 _______個元素。 答案： 35．哈夫曼樹是帶權路徑長度 的樹，通常權值較大的結點離根結點 。 答案： 43． 有 n 個球隊參加的足球聯(lián)賽按主客場制進行比賽，共需進行 場比賽。 答案： 六、操作題 /綜合能力題 1．若對序列 (76， 38， 65， 13， 97， 27， 50， 49)采用 冒泡 排序法 (按照值的大小從小到大 )進行排序， 共需幾趟排序？ 請分別 在下表中寫出每一趟的結果： 原始序列 76 38 65 13 97 27 50 49 答案： 共需 5 趟 第 1 趟結果 38 65 13 76 27 50 49 97 第 2 趟結果 38 13 65 27 50 49 76 97 第 3 趟結果 13 38 27 50 49 65 76 97 第 4 趟結果 13 27 38 49 50 65 76 97 第 5 趟結果 13 27 38 49 50 65 76 97 2． 若對序列 (76， 38， 65， 13， 97， 27， 50， 49)采用 選擇 排 序法 (按照值的大小從小到大 )進行排序，請分別在下表中寫出每一趟的結果： 原始序列