計算機軟件技術基礎(第三版)課后習題答案較全

1、第一章 信息與計算機1.1 什么是信息？信息與數據的區(qū)別和聯系在何處？ 信息定義之一：信息是現實世界中存在的客觀實體、現象、關系 進行描述的數據。 信息定義之二： 信息是經過加工后并對實體的行 為產生影響的數據。與數據的區(qū)別和聯系： 數據定義：數據是現實世界客觀存在的 實體或事物的屬性值， 即指人們聽到的事實和看到的景象。 我們把 這些數據收集起來，經過處理后，即得到人們需要的信息。信息和數 據的關系可以歸結為： 1. 信息是有一定含義的數據。 2. 信息是 經過加工（處理）后的數據。 3. 信息是對決策有價值的數據。1.2 信息有哪些基本屬性？信息的基本屬性有： 1. 事實性。 2. 等級性

2、。 3. 可壓縮性。4. 可擴散性。 5. 可傳輸性。 6. 共享性。 7. 增值性和再生性。 8. 轉換性。1.3 計算機的主要特點是什么？計算機最主要的特點是： 1. 高速自動的操作功能。 2. 具有記 憶的能力。 3. 可以進行各種邏輯判斷。 4. 精確高速的計算能力。 1.5 完整的計算機系統應該包括哪幾部分？目前最完整的計算機系統學說認為由五部分組成： 1. 人員 2. 數據 3. 設備 4. 程序 5. 規(guī)程1.6 什么是計算機硬件？什么是計算機軟件？硬件：泛指實際存在的物理設備， 包括計算機本身及其外圍設備。微型計算機的硬件系統：主機、外存儲器、輸入設備、輸出設備、微 機的系統總

3、線。軟件：是指計算機程序、方法、規(guī)則的文檔以及在計算機上運 行它時所必須的數據。 計算機軟件一般分為系統軟件和應用軟件。 1.8 軟件技術發(fā)展的幾個階段各有什么特點？它與硬件的關系如 何？第一階段：高級語言階段 特點：這一時期，編譯技術代 表了整個軟件技術，軟件工作者追求的主要 目的是設計和實現在控 制結構和數據結構方面表現能力強的高級語言。 但在這一時期內， 編 譯系統主要是靠手工編制，自動化程度很低。 硬件關系：此時 期計算機的硬件要求僅能用機器指令來編制可運行的程序。第二階段：結構程序設計階段 特點：在程序的正確性方 面，提 出了 結構 化程序設 計思想使 程序 的可靠 性 提 高了 。

4、 程序設計方法論方面，提出由頂向下法和自底向上法。使程序模塊 化，使問題的復雜性和人的思維統一起來了。 出現了 軟件生產管理。 硬件關系：磁盤問世，操作系統發(fā)展，非數 值計算應用發(fā)展，通信設備完 善，網絡發(fā)展，集成電路發(fā)展等使軟 件復雜性增加產生軟件危機，在此背景下發(fā)展了軟件技術。第三階段：自動程序設計階段 特點：向集成化、一體化 發(fā)展。出現了軟件開發(fā)環(huán)境。程序設計基本方法 進一步改進。 硬件關系： 集成電路迅速發(fā)展以及高分辨率終端的出現， 為個人計算 機發(fā) 展提供了條件，再加上人工智能、專家系統研究的發(fā)展，使程序設計進入成熟期。1.9 什么是多媒體計算機？ 多媒體計算機包含那幾項？ 什么是多

5、媒體計算機？1. “媒體”的概念分為兩部分，其一是信息存儲的實體，其二是 表現信息形式的載體；2. 多媒體計算機是以計算機為核心， 可以綜合處理數值計算、 文 本文件、圖形圖像、聲音視頻等多種信息的計算機系統。3. 多媒體是 20 世紀 90 年代計算機發(fā)展的新領域， 它是計算機技 術與圖形圖像、動畫、聲音和視頻等領域頂尖技術結合的產物， 它將人機交互的信息從單純的視覺（文字、圖形）擴大到兩個 以上的媒體信息B： 多媒體的基本要素：文本，圖形，圖像，動畫，音頻，視頻， 可以看出，它是電腦， 電視機，游戲機，錄放機，傳真機和電話機的綜合體第二章 常用數據結構及其運算2.1 什么是數據結構？它對算

6、法有什么影響？ 數據結構是指同一數據對象中各數據元素間存在的關系。 數據結構對算法的影響：算法的實現必須借助程序設計語言中 提供的數據類型及其運算。一個算法的效率往往與數據的表達 形式有關，因此數據結構的選擇對數據處理的效率起著至關重 要的作用。它是算法和程序設計的基本部分，它對程序的質量 影響很大。2.2 何謂算法？它與程序有何區(qū)別？ 廣義地說，為解決一個問題而采取的方法和步驟，就稱為“算 法”。計算機算法是通過計算機能執(zhí)行的算法語言來表達的。 和程序的區(qū)別：一個程序包括兩個方面的內容： (1)對數據的描述，即數據結構。(2)對操作的描述，即算法。 所以算法是程序的一個要素。2.3 何謂頻度

7、，時間復雜度，空間復雜度？說明其含義。 頻度：在某個算法中某個語句被重復執(zhí)行的次數就是此語句的頻 度。時間復雜度： 是用來估算一個算法的執(zhí)行時間的量，以算法中頻 度最大的語句來度量。 空間復雜度： 指在算法中所需的輔助空間的單 元，而不包括問題的原始數據占用的空間。2.4 試編寫一個求多項式 Pn =anxn +a n-1 x n-1 + +a1x+a0的值 Pn(x 0) 的算法，要求用乘法次數最少， 并說明算法中主要語句的執(zhí)行次數及 整個算法的時間復雜度。A=(a0, a 1 an)mul 1 /sum=a0for i=1 to nmul mul * x / xsum = Ai*mul +

8、 sum /求和end(i)進行了 n 次時間復雜度為： 2n2.5 計算下列各片段程序中 XX+1 執(zhí)行次數(1)for i=1 to nfor j=1 to ifor k=1 to jx x+1end(k)end(j)end(i)執(zhí)行次數： n*n*n(2)i 1while in doxx+1i i+1end(while) 執(zhí)行次數： n-1for i=1 to nj 1for k=j+1 to nx x+1end(k)end(i)執(zhí)行次數： n* (n-1)2.6 數據的存儲結構主要有哪兩種 ?它們之間的本質區(qū)別是什么？ 數據的存儲結構：向量和鏈表。本質區(qū)別：向量是連續(xù)存放的， 其存儲空

9、間是靜態(tài)分配的， 以存放順序來表達 元素的前后件的關系。鏈式存儲結果不需要一組連續(xù)的存儲單元， 其數據元素可以分散存 放在存儲空間中，其元素關系由指針來指向2.8 已知線性表 L(a 1, a2, , an ) 元素按遞增有序排列。用向量作為存儲結構，試編寫算法： 刪除表中值在 c與 d 之間 (c=c / 找到第 1 個大于等于 c 的元素s = iift = -1 andLi d/ 找到第 1 個大于 d的元素end (i)t = i ;ifs != -1 and t !=-1i = swhilei t andi + t s =nLi = L i + t s i+ end(while) e

10、lsereturn( 錯誤 沒有找到 元素在 c 和 d 之間 ) end(if) for j=c to n-d+cLj-Lj+d-c/ 把 j+d-c 項給 j End(j)N-n-d+c/ 所有項數減少ReturnB 是否為 A2.9 線性表 A ，B 中的元素為字符串類型，用向量結構存儲，試編寫算法，判斷 的子序列(例如 A=ENGLISH ， B=LIS ，則 B 為 A 的子序列)Am Bna1a2a3a4a5a6a7a8a9a10a11a12a13a14a15b1b2b3b4b5b6A：B：i=1 檢查 A 中第 1 個元素開始的字符串是否與 B 匹配 i=2 檢查 A 中第 2

11、個元素開始的字符串是否與 B 匹配i= m n + 1 檢查 A 中 第 (m-n+1) 個元素開始的字符串是否與 B 匹配AmBn if ( mn ) then return error for ( i =1; i= m-n+1; i+)for (j = 1; jn then return( A 字符串中第 i 個字符開始的子串與 B 匹配 ) end(i) renturn ( 找不到匹配的子串 )設 A ，B 兩個線性表的元素個數為 m， n If (m=n)thenreturn For i=0 to n-1a=Aifor j=0 to m-1if(a=Bj)thenb+end(j)end

12、(i)if(b=m)thenB 為 A 的子集 returna1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14 a152.11 寫一個將向量 L (a1 ， a2， an)倒置的算法。a1a2a3a4a5a6a7a8a9a10a11a12a13a14a15對 L(a 1， a2, . ., an ) 如果是奇數個元素，則1,15交換1,n 交換2，14交換2,n-1交換3，13交換3，n-2交換4，12交換4，n-3交換5，11交換5，n-4交換6，10交換6，n-5交換7，9交換7，n-6交換8，8交換8，n-7交換9，7交換9，n-8交換？ 停止！

13、a1a2a3a4a5a6a7a8a9a10a11a12a13a14a15如果是偶數個元素，則1，14交換1,n 交換2，13交換2,n-1交換3，12交換3，n-2交換4，11交換4，n-3交換5，10交換5，n-4交換6，9交換6，n-5交換7，8交換7，n-6交換8，7交換？8，n-7交換？ 停止！小結： n 個元素倒置的算法是，i = 1while ( in-i+1)ai 與 an-i+1 交換 i+ end(while)2.12 試編寫算法求已知單鏈表長度，并考慮表空的情況。p = headi = 0While(p!=nil) / 表不為空P- next(p)/ 移動到下一個元素+En

14、d(while)Return i / 返回數據的個數2.13 試編寫算法刪除單鏈表中第 k 個結點。 GETNODE(q) GETNODE(p) q-headFor i=1 to k-1q-next(q)End(i)P-next(q);next(q)-next(p)Ret(p)Return2.14 已知一循環(huán)鏈表中數值已按遞增有序排列現要插入一個新結點，并使插入一個新節(jié) 點，并使插入后鏈表仍為有序序列GETNODE(p)Data(p)=aWhile(data(p)data(n) n-next(n)End(while)p 為指向鏈表中每個節(jié)點q -n next(p) -next(q)-p ret

15、urn 2.18 設在長度大于 1 的循環(huán)鏈表中，即無頭結點，也無頭指正， 的指針，試編寫算法刪除該節(jié)點的前趨結點。 q-Next(p)/ 找到該節(jié)點的前趨結點p-next(q);next(q)-next(p)RET(p)Return 2.20 試用單鏈表表示兩個多項式； A=4x 12+5x 8+6x 3+4 ，B=3x 12+6x 7+2x 4+5(1) 設計此兩個多項式的數據結構。(2) 寫出兩個多項式相加的算法。(3) 分析算法的時間、空間復雜度。ADD-POLY(h a ,h b )1. p next(h a); q next(h b)2. p re h a;h ch a/p re

16、指向 p 的前趨，為 c(x) 頭指針 /3. while (pnil) AND (qnil) do4. case5. EXP(p)EXP(q):6. p re p;p next(p)7. EXP(p)=EXP(q):8. x COEF(p)+COEF(q);9.if (x0) then COEF(p)x;p re p10. else next(pre ) next(p); RET(p)11. p next(p re);u q;q next(q);RET(u)12. EXP(p)EXP(q):13. u next(q);next(q) p;next(pre ) q;p re q;q u14.

17、end(case)15. end(while)16.if(qnil) then next(pre ) q17.RET(h b)/ 釋放多項式 B(x) 的頭結點 /18.return 2.22 CQ0:10 為一循環(huán)隊列，初態(tài) front=rear=1 ，畫出下列操作后隊的頭，尾指示器狀態(tài)：(1) d,e,b,g,h 入隊； rear=6 front=1(2) d ， e 出隊 rear=6 front=3(3)I,j,k,l,m 入隊 rear=0 front=3(4)b 出隊 rear=0 front=4 (5)n,o,p,q,r 入隊 rear=5 front=42.22 CQ0 器狀態(tài)

18、： 10 為一循環(huán)隊列，初態(tài) front=rear=1 ，畫出下列操作后隊的頭、尾指示(1) d,e,b,g,h 入隊； (2) d,e 出隊； (3) i,j,k,l,m, 入隊； (4) b 出隊；(5) n,o,p,q,r 入隊。2.23 試畫出表達式 A*(B-D)/C*(E*F) 執(zhí)行過程中 NS ， OS 棧的變化情況。2.24 用一長度為 m 的數組存放一雙向棧，兩個棧頂分別為top1 和 top2, 如圖所示。上溢條件為 top1=top2, 從鍵盤輸入一串整數，奇數入stack1 ，偶數如 stack2 ，直到上溢時停止輸入。試編寫一算法實現此過程。O_E(R,m,top1,

19、top2,x)1. top1 m;top2 1 /top1,top2置初值2. if (top1=top2) then 溢 ,return3. while (top1top2) do4. if (x mod 2=0) thenRtop2 x;top2 top2+15. else x;top1top1+1 Rtop16. end(while)7. retun2.25 有一個二維數組 A1:m ;1:n, 假設 A3,2 地址為 1110，A2 ，3地址為 1115， 若每個單元占一個空間，問 A1,4 的地址是多少答案： 11202.26 用三元組和帶行輔助向量形式表示下列的稀疏矩陣：2.28

20、將題圖 2.3 的一般樹化為二叉樹。 答案：2.29 設一顆完全二叉數有 1000 個結點，試問：(1) 有多少個葉子結點 500(2) 有多少個度為 2 的結點 499(3) 有多少個結點只有非空左子樹 12.30 設一顆二叉樹其中序和后序遍歷為中序： BDCEAFHG后序： DECBHGFA答案： ABCDEFHG231.對二叉樹寫出如下算法：(1) 復制一棵二叉樹；(2) 判斷兩棵二叉樹是否相等；(3) 計算二叉樹的樹葉；(4) 計算二叉樹的深度； 解：1) /復制一棵二叉樹 /*算法思想采用遞規(guī)函數來實現(1)如果樹為空，則復制一棵空樹；(2)如果樹不為空，則依次遞規(guī)復制已知二叉樹的左

21、子樹和有子樹；(3) 生成一個新的根結點，使復制得到的左子樹和右子樹的根指針分別成為這個新生 成結點的左指針域和右指針域的值。算法編寫：*/BiTree *CopyTree(BiTree *T)/if(!T) return NULL;if(T-lchild)newlchild=CopyTree(T-lchild);/else newlchild=NULL;/if(T-rchild)newrchild=CopyTree(T-rchild);/else newrchild=NULL;/newnode=GetTreeNode(T-data,newlchild,newrchild); /return

22、newnode;/CopyTreeBiTNode *GetTreeNode(TelemType item,BiTNode *lptr,BiTNode *rptr)/T=new BiTNode;T-data=item;T-lchild=lptr;T-rchild=rptr;return T;/GetTreeNode(2)在這里要對一種情況進行說明這兩顆這兩顆當 root1 的左子樹與 root2 的左子樹相同， root1 的右子樹與 root2 的右子樹相同時， 二叉樹相同。當 root1 的左子樹與 root2 的右子樹相同， root1 的右子樹與 root2 的左子樹相同時， 二叉樹同樣

23、相同。以下是實現代碼bool IsBSTEqual(BNode* root1,BNode* root2)if (root1=NULL & root2=NULL)return true;else if (root1=NULL | root2=NULL)return false;elseif (root1-data != root2-data)return false;bool is_left = IsBSTEqual(root1-left,root2-left);bool is_right = IsBSTEqual(root1-right,root2-right);if (is_left&is_

24、right)return true;elseis_right = IsBSTEqual(root1-right,root2-left); is_left = IsBSTEqual(root1-left,root2-right);if (is_left&is_right) return true;elsereturn false;3)4) 計算葉子數和樹的深度。計算葉子：遞歸每個節(jié)點，當沒有左孩子和右孩子時即為葉子。 計算深度：對每個節(jié)點計算左右子樹的深度，節(jié)點的最終深度是其子樹深度的最大值加1，空樹返回 -1.struct TreeElementType Element;Tree *left;

25、Tree *right;int CountLeaf(Tree *T)static int count = 0;if (T != NULL)CountLeaf(T-left);CountLeaf(T-right);if (T-left = NULL & T-right = NULL)count+;return count;int Depth(Tree *T)int depthLeft, depthRight, depth;if (T = NULL)return -1;elsedepthLeft = Depth(T-left);depthRight = Depth(T-right);depth =

26、 1 + (depthLeft depthRight ? depthLeft:depthRight);return depth;2.32.給定一組元素 17,28,36,54,30,27,94,15,21,83,40, 畫出由此生成的二叉排序樹。 解：1）寫出此圖的鄰接表與鄰接矩陣；2）由給點 V1 作深度優(yōu)先搜索和廣度優(yōu)先搜索；3）試說明上述搜索的用途。210122016141513解：（1）12582131034212435145146657157681781171598101810291111101219123111313121420144131515614161615172017716

27、18189171919111820201316192)V1 作深度優(yōu)先搜索 :V1 作廣度優(yōu)先搜索（3）為了避免同一頂點被多次訪問。2.35.有一又向圖如題圖 2.5 所示：564（ 1）寫出每一結點的入度和出度各為多少；（2）寫出上圖的鄰接矩陣和鄰接表。 解：V1:入度 =3出度=0V2:入度 =2出度=2V3:入度 =1出度=2V4:入度 =2出度=2V5:入度 =2出度=1V6:入度 =0出度=43.36 求題圖 2.6 中結點 a 到各結點之間最短路徑。2.37 求題圖 2.7 中所示 AOV 網所有可能的拓撲順序結果。 解:25拓撲排序： V7-V5-V2-V4-V6-V3-V1-V

28、82.38 題圖 2.8 所示 AOE 網，求 :(1). 每一事件最早開始時間和最晚開始時間;(2).該計劃最早完成時間為多少。解:活動最早最遲開始時間a1a2a3a4a5a6a7a8a9a10a11a12a13a14E00566121212191916202325L409616121916191923202325L-E 404010074007000事件最早最遲開始時間V1V2V3V4V5V6V7V8V9V10VE05612191620232527VL096121923202325272.39 某校 97 級同學舉辦運動會，報名同學學號為97438 ，97102 ，97528 ，97136

29、 ，97338 ，97250 ，97407 ，97239 ，9722797517 ， 97321 ，97421 ，97451 ， 97241 ， 97118 ， 97543 ，97309 畫出進行分塊查找的數據組織形式。2.40 畫一棵對 20 個記錄進行對分查找的判定樹,并求等概率情況下的平均查找長度。ASL=(1+2*2+3*4+4*8+5*5)/20=3.7 2.41 設有 10 個記錄的關鍵字為ICKES ， BARBER ， ELYOT ，KERN ，FRENCE ， LOWES ， BENSDN ，FONK ， ERVIN ， KNOX 。構造 =10/13 的哈希表，取關鍵字首字

30、母表中的序號為哈希函數值， 用隨機探測解決沖突， di=(d 1+Rj) mod 13 ，R j取自偽隨機數列： 3 ，7 ，1 ，12 ，10 ，。 統計該表的平均查找長度 ASL 。2.42 對于給定的一組關鍵字： 41,62,13,84,35,96,57,39,79,61,15,83 。分別寫出： 插入排序、簡單選擇排序、堆排序、冒泡排序、快速排序、二叉樹排序的排序過程，并對 各排序方法進行分析。排序，簡單選擇排序、堆排序、冒泡排序、快速排序、二叉樹排序的排序過程，并對排序方 法進行分析。插入13 41 62 84 35, 96,57,39, 79,61,15,8313 35 41 62

31、 84 96 57 39 79 61 15 8313 35 41 57 62 84 96 39 79 61 15 8313 35 39 41 57 62 84 96 79 61 15 8313 35 39 41 57 62 79 84 96 61 15 8313 35 39 41 57 61 62 79 84 96 15 8313 15 35 39 41 57 61 62 79 84 96 8313 15 35 39 41 57 61 62 79 83 84 96對于具有 n 個記錄的文件，要進行 n-1 趟排序 就地排序穩(wěn)定的排序方法 簡單選擇排序 41，62，13，84，35，96 ，57

32、，39，79，61，15，8341 62 13 84 35 96 57 39 79 61 15 8313 41 62 84 35 96 57 39 79 61 15 8313 15 41 62 84 35 96 57 39 79 61 8313 15 35 41 62 84 96 57 39 79 61 8313 15 35 39 41 62 84 96 57 79 61 8313 15 35 39 41 57 62 84 96 79 61 8313 15 35 39 41 57 61 62 84 96 79 8313 15 35 39 41 57 61 62 79 84 96 8313 15

33、 35 39 41 57 61 62 79 83 84 96堆排序41 62 13 84 35 96 57 39 79 61 15 8396, 84, 83, 79, 62, 61, 57, 41, 39, 35, 15, 13冒泡排序 41，62，13，84，35 ，96，57，39，79，61，15，8341, 13, 62, 35, 84, 57, 39, 79, 61, 15, 83, 9613, 41, 35, 62, 57, 39, 79, 61, 15, 83, 84, 9613, 35, 41, 57, 39, 62, 61, 15, 79, 83, 84, 9613, 35,

34、 41, 39, 57, 61, 15, 62, 79, 83, 84, 9613, 35, 39, 41, 57, 15, 61, 62, 79, 83, 84, 9613, 35, 39, 41, 15, 57, 61, 62, 79, 83, 84, 9613, 35, 39, 15, 41, 57, 61, 62, 79, 83, 84, 9613, 35, 15, 39, 41, 57, 61, 62, 79, 83, 13, 15, 35, 39, 41, 57, 61, 62, 79, 83, 13, 15, 35, 39, 41, 57, 61, 62, 79, 83, 13,

35、 15, 35, 39, 41, 57, 61, 62, 79, 83, 13, 15, 35, 39, 41, 57, 61, 62, 79, 83,快速排序 41，62，13，84，35 ，13, 35, 39, 15, 41, 96, 57, 83, 79, 61, 13, 35, 39, 15, 41, 96, 57, 83, 79, 61, 13, 15, 35, 39, 41, 96, 57, 83, 79, 61, 13, 15, 35, 39, 41, 96, 57, 83, 79, 61, 13, 15, 35, 39, 41, 96, 57, 83, 79, 61, 13,

36、 15, 35, 39, 41, 62, 57, 83, 79, 61, 13, 15, 35, 39, 41, 57, 61, 62, 79, 84, 13, 15, 35, 39, 41, 57, 61, 62, 79, 84, 13, 15, 35, 39, 41, 57, 61, 62, 79, 84, 13, 15, 35, 39, 41, 57, 61, 62, 79, 84, 13, 15, 35, 39, 41, 57, 61, 62, 79, 83,二叉樹排序 二叉樹建立過程 41 41, 62 13, 41, 6213, 41, 62, 8413, 35, 41, 62,

37、8413, 35, 41, 62, 84, 9613, 35, 41, 57, 62, 84, 9613, 35, 39, 41, 57, 62, 84, 9613, 35, 39, 41, 57, 62, 79, 84, 9613, 35, 39, 41, 57, 61, 62, 79, 84, 9613, 15, 35, 39, 41, 57, 61, 62, 79, 84, 13, 15, 35, 39, 41, 57, 61, 62, 79, 83,84, 9684, 9684, 9684, 9684, 9696，57，39，79，61 ，15，8384, 6284, 6284, 62

38、84, 6284, 6284, 9683, 9683, 9683, 9683, 9684, 969684, 96第三章 操作系統3.1 操作系統的基本功能是什么？它包括哪些部分？基本功能： 操作系統應該具有處理器管理， 存儲管理， 設備管理和文件管理功能，同 時，為了使用戶能方便地使用機器，操作系統還應提供用戶接口功能。構成部分： （1） . 對 CPU 的使用進行管理的進程調度程序。（2）. 對內存分配進行管理的內存管理程序。（ 3）. 對輸入輸出設備進行管理的設備驅動程序。（ 4） . 對外存中信息進行管理的文件系統。3.2 試說明虛擬機的概念以及實現的方法。 在裸機外面每增加一個軟件層后

39、就會變成一臺功能更強的機器，我們通常把 這種計算機系統稱為虛擬機。虛擬機的實現方法：在裸機上裝上操作系統對機器進行首次擴展，再在操作 系統的基礎上增加其他軟件，這樣就可以實現 “虛擬機 ”。3.3 通常操作系統有哪幾種基本類型？各有什么特點及適用于何種場合？ 三大類：（1）多道批處理系統：計算機內存中同時可以存放多道作業(yè)，用戶與作 業(yè)之間沒有交互作用，用戶不能直接控制作業(yè)的運行。此類系統一般用于計算中 心等較大型的計算機系統中。 （ 2）分時系統：多個用戶通過終端分享同一臺計算 機，并通過終端直接控制程序運行，進行人與機器之間的交互。此類系統適用于 程序的開發(fā)。 （ 3）實時系統：對外部發(fā)生的

40、隨機事件作出及時的響應，并對它進 行處理。此類系統一般用于工業(yè)控制系統或事物處理系統。3.4 試說明你所使用過的操作系統的類型和特點。Windows 系統：多用戶多任務操作系統。 特點：全新的、友善的用戶界面。提供了功能強大的應用程序。 具有多任務并行處理能力，各種應用程序之間可以方便地進行切換和交換信息。具有強大的內存管理能力，支持擴展內存功能，提高系統運行效率。3.5 解釋名空間、作業(yè)地址空間和存儲空間的關系以及邏輯地址和物理地址的區(qū)別。 存放源程序的空間稱為名空間。當匯編或編譯程序將源程序轉換成目標程序后， 一個目標程序所占有的地址范圍稱為地址空間，這些地址的編號是相對于起始地 址而定的

41、，一般定起始位零，稱為邏輯地址或相對地址。存儲空間是指當目標程 序裝入主存后占用的一系列物理單元的集合，這些單元編號稱為物理地址或絕對 地址。3.6 什么是重定位？靜態(tài)重定位和動態(tài)重定位的區(qū)別是什么？各舉一例說明。 當用戶程序要調入內存時， 必須把相對地址轉換為絕對地址， 同時要包括對程序 中與地址有關的指令進行修改， 這一過程稱為重定位。 靜態(tài)重定位是在程序裝入 時進行， 一般通過處理機中一對界地址寄存器來實現。 動態(tài)重定位是在程序執(zhí)行 過程中進行的，當處理器訪問主存指令時由動態(tài)變換機構自動進行地址轉換。3.7 存儲管理器的功能是什么？為什么要引入虛擬存儲器的概念？虛存的容量由什 么決定？

42、存儲管理的功能主要分為：內存分配、地址轉換、存儲保護和內存擴充。 虛擬存儲器能提供給用戶一個比實際內存大得多的存儲空間， 使用戶在編制程序 時可以不必考慮存儲空間的限制。 虛存的容量受兩個條件約束：指令中地址場長度的限制、外存儲器容量的限制。3.10 什么是作業(yè)、作業(yè)步和進程？ 作業(yè)是用戶在一次算題過程中或一個事務處理中要求計算機系統所做的集合。 一個作業(yè)是由一系列有序的作業(yè)步所組成。 一個作業(yè)步運行的結果產生下一個作 業(yè)步所需的文件。進程可以看成是程序的一次執(zhí)行， 即是在指定內存區(qū)域的一組指令序列的執(zhí)行過 程。3.11 處理器管理主要解決什么問題？ 在大型通用系統中， 可能數百個批處理作業(yè)存

43、放在磁盤中， 又有數百個終端用戶 與主機聯接， 如何從這些作業(yè)中挑選一些作業(yè)進入主存運行， 又如何在主存各進 程間分配處理器， 是操作系統資源管理的一個重要問題， 處理器管理就是用來解 決此問題的。3.12 什么是進程的同步和互斥？什么是臨界區(qū)？ “同步 ”是指兩個事件的發(fā)生存在某種時序上的關系， 如果系統中有若干個進程要 共同完成某一任務，那么它們相互之間必須協調配合。“互斥 ”是指當多個進程要求共享系統中某些硬件或軟件資源， 而這些資源卻又要 求排它性使用時，這樣往往引起由于多個進程競爭同一資源使運行結果出現問 題。如果在兩個進程 P1、P2 中加入 P、V 操作后，可以實現對公用變量 c

44、ount 的互 斥使用。其中 P（ s）、V（s）之間的程序段稱為臨界區(qū)。3.15 進程間的通信可以由哪些方式進行？ 低級通信方式： P-V 操作。 高級通信方式：直接通信、信箱通信。3.16 死鎖產生的必要條件是什么？死鎖的預防、避免和檢測各有什么不同？各舉一 種相應的方法。死鎖產生的必要條件有： 1.所涉及的資源是非共享的； 2.進程在等待新資源 時，繼續(xù)占用已分配到的資源； 3.一個進程占有的資源不能被別的進程強行搶 占； 4.一個進程獲得的資源同時被另一個進程所請求，從而形成一個進程的循 環(huán)鏈。死鎖的預防是研究如何破壞產生死鎖的必要條件之一， 從而達到不使死鎖發(fā) 生地目的。死鎖的避免與

45、死鎖的預防區(qū)別在于，死鎖的預防是嚴格破壞形成死 鎖的必要條件之一，使得死鎖不在系統中出現。預防方法之一，采用假脫機技 術將非共享設備變成共享設備來實現。而死鎖的避免并不嚴格限制必要條件的存在， 因為必要條件存在并不一定產 生死鎖。而進程推進順序不當，也可以導致系統發(fā)生死鎖，因此死鎖的避免是 考慮萬一當死鎖有可能出現時，就小心地避免這種情況的最終發(fā)生。避免方法 有采用相應的銀行算法和方法。死鎖的檢測和恢復， 這是一種變通的方法， 它允許死鎖的發(fā)生， 但能在適當 時間檢測出來， 并設法進行恢復。 利用化簡進程 -資源有向圖的方法來檢測系統 在某一特定狀態(tài)時是否處于死鎖狀態(tài)。3.17 通道、控制器和

46、設備的各種不同連接方式各有什么特點？ 第一種連接方式（書中圖 3.41（ a）：控制器與設備是一一對應的，當系統對某 設備提出申請時， CPU 將設備號及有關操作要求傳遞給通道，由通道啟動該設 備，并完成對該設備的操作。第二種連接方式 （書中圖 3.41（ b）：是一個控制器控制若干個設備， 只有當被 申請的設備及相應的控制器均為空閑狀態(tài)時才能啟動。第三種連接方式（書中圖 3.41（ c）：是同道、控制器與設備交叉連接，提高了 控制的靈活性，但必須在相應的設備、控制器、同道均為空閑時才能工作。3.18 什么是 “瓶頸 ”問題？引入緩沖區(qū)為何可以解決這一問題？ 系統中的獨占類型設備，只能由單個作

47、業(yè)獨占，這樣使其他需要改設備的進程 由于等待設備而被阻塞，稱為系統的 “瓶頸 ”。 緩沖技術是指在內存中劃出一個由 n 個單元組成的區(qū)域，稱為緩沖區(qū)，作為外 部設備在進行數據傳輸時的暫存區(qū)。 引入緩沖技術的根本原因是 CPU 數據處理 速度與設備傳輸數據速度不相匹配，利用緩沖區(qū)來緩解其間的速度矛盾，減少 瓶頸現象。3.19 設備管理的功能是什么？怎樣把一臺物理設備虛擬為多臺設備？ 設備管理的功能：設備驅動程序；即插即用；通用即插即用； 集中、同一管理；添加硬件。通過虛擬機軟件， 就可以在一臺物理計算機上模擬出一臺或多臺虛擬的計算機。3.20 什么是記錄、文件、文件系統？ 記錄：文件由若干個記錄

48、組成，每一個記錄是一些相關信息的集合。 文件：在邏輯上具有完整意義的數據或字符序列的集合。 文件系統：負責存取和管理文件的機構，又稱為文件管理系統。3.21 文件的邏輯結構和物理結構有何區(qū)別？文件的存儲方式與文件的存取有何關 系？ 文件的邏輯結構是從用戶的角度看到的文件面貌，也就是它的記錄結構。文件 的物理結構是指一個邏輯文件在外存儲器上的存放形式。 各種文件應用場合不同，對文件的存取要求也就不同，對應不同的存取方式，對文件的物理結構即存儲方式有不同的要求3.22 什么是文件目錄？有幾種目錄結構形式？各有什么特點？ 為了便于對文件進行存取和管理， 所有計算機系統都設置一個文件目錄， 每個文 件

49、目錄中都有一個表目，存放描述該文件的有關信息。 通常有一級目錄、二級目錄和多級目錄結構。一級目錄： 把系統中所有文件都建立在一張目錄表中， 整個目錄結構是一個線性 表， 所以查找的時間會增加， 不允許用戶對不同的文件取相同的名字， 主要用于 單用戶的操作系統中。二級目錄： 在主目錄文件中每一個用戶有一個表目， 指出各用戶文件目錄的所在 位置， 而各用戶文件目錄才指出其所屬各具體文件的描述信息，不同用戶的文件可以起相同的名字。多級目錄：是樹形結構，每一個結點出來的分支可以是文件，也可以是下一級， 在一定時間內以某一級目錄作為當前目錄，用戶只需從 “當前目錄 ”查看即可。3.23 文件的共享與安全

50、保密問題如何解決？ 共享的實現：通過文件路徑實現共享； 通過聯接實現共享。保密問題的解決：采用存取控制矩陣方法； 采用按用戶分類的存取控制的方法； 采用口令設置。3.24 什么是文件操作指令？每個命令的具體功能是什么？ 文件操作指令： 是指文件系統提供給用戶的一系列操作使用命令， 其中最基本的 命令是查詢文件目錄。建立文件： 當用戶需要將其信息作為文件保存時， 向系統提出建立文件指令， 系 統按照用戶提供的參數為該文件建立一個表目， 放入相應的文件目錄 中。打開文件： 當用戶需要訪問文件中某個記錄時， 首先要進行打開文件操作， 此時 系統將欲訪問的文件表目從目錄文件調入活動文件表中。讀文件： 把文件中相關的記錄從外存儲器的文件區(qū)中讀入主存用戶工作區(qū)中。 寫文件：把用戶要求插入、增加或刪除的記錄寫入文件