計算機(jī)軟件技術(shù)基礎(chǔ)(第三版)沈被娜 課后習(xí)題答案較全

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

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

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

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

5、是信息存儲的實(shí)體，其二是表現(xiàn)信息形式的載體；2. 多媒體計算機(jī)是以計算機(jī)為核心，可以綜合處理數(shù)值計算、文本文件、圖形圖像、聲音視頻等多種信息的計算機(jī)系統(tǒng)。3. 多媒體是20世紀(jì)90年代計算機(jī)發(fā)展的新領(lǐng)域，它是計算機(jī)技術(shù)與圖形圖像、動畫、聲音和視頻等領(lǐng)域頂尖技術(shù)結(jié)合的產(chǎn)物，它將人機(jī)交互的信息從單純的視覺（文字、圖形）擴(kuò)大到兩個以上的媒體信息B： 多媒體的基本要素： 文本，圖形，圖像，動畫，音頻，視頻， 可以看出，它是電腦，電視機(jī)，游戲機(jī)，錄放機(jī)，傳真機(jī)和電話機(jī)的綜合體第二章 常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算2.1 什么是數(shù)據(jù)結(jié)構(gòu)？它對算法有什么影響？ 數(shù)據(jù)結(jié)構(gòu)是指同一數(shù)據(jù)對象中各數(shù)據(jù)元素間存在的關(guān)系。 數(shù)據(jù)

6、結(jié)構(gòu)對算法的影響：算法的實(shí)現(xiàn)必須借助程序設(shè)計語言中提供的數(shù)據(jù)類型及其運(yùn)算。一個算法的效率往往與數(shù)據(jù)的表達(dá)形式有關(guān)，因此數(shù)據(jù)結(jié)構(gòu)的選擇對數(shù)據(jù)處理的效率起著至關(guān)重要的作用。它是算法和程序設(shè)計的基本部分，它對程序的質(zhì)量影響很大。2.2 何謂算法？它與程序有何區(qū)別？廣義地說，為解決一個問題而采取的方法和步驟，就稱為“算法”。計算機(jī)算法是通過計算機(jī)能執(zhí)行的算法語言來表達(dá)的。和程序的區(qū)別：一個程序包括兩個方面的內(nèi)容：（1）對數(shù)據(jù)的描述，即數(shù)據(jù)結(jié)構(gòu)。（2）對操作的描述，即算法。所以算法是程序的一個要素。2.3 何謂頻度，時間復(fù)雜度，空間復(fù)雜度？說明其含義。頻度：在某個算法中某個語句被重復(fù)執(zhí)行的次數(shù)就是此語句

7、的頻度。時間復(fù)雜度：是用來估算一個算法的執(zhí)行時間的量，以算法中頻度最大的語句來度量?？臻g復(fù)雜度：指在算法中所需的輔助空間的單元，而不包括問題的原始數(shù)據(jù)占用的空間。2.4試編寫一個求多項(xiàng)式Pn =anxn +an-1 xn-1+a1x+a0的值Pn(x0)的算法，要求用乘法次數(shù)最少，并說明算法中主要語句的執(zhí)行次數(shù)及整個算法的時間復(fù)雜度。A=(a0, a1 an)mul 1 / sum=a0for i=1 to nmul mul * x / xsum = Ai*mul + sum /求和end(i)進(jìn)行了n次時間復(fù)雜度為：2n2.5計算下列各片段程序中XX+1執(zhí)行次數(shù)(1)for i=1 to n

8、 for j=1 to ifor k=1 to j xx+1end(k) end(j)end(i)執(zhí)行次數(shù)：n*n*n (2)i1while i<n doxx+1ii+1end(while)執(zhí)行次數(shù)：n-1(3)for i=1 to nj1for k=j+1 to nx x+1end(k)end(i)執(zhí)行次數(shù)：n*（n-1）2.6 數(shù)據(jù)的存儲結(jié)構(gòu)主要有哪兩種?它們之間的本質(zhì)區(qū)別是什么？數(shù)據(jù)的存儲結(jié)構(gòu)：向量和鏈表。本質(zhì)區(qū)別：向量是連續(xù)存放的，其存儲空間是靜態(tài)分配的，以存放順序來表達(dá)元素的前后件的關(guān)系。鏈?zhǔn)酱鎯Y(jié)果不需要一組連續(xù)的存儲單元，其數(shù)據(jù)元素可以分散存放在存儲空間中，其元素關(guān)系由指針

9、來指向。2.8已知線性表L(a1, a2, , an ) 元素按遞增有序排列。用向量作為存儲結(jié)構(gòu)，試編寫算法：刪除表中值在c與d之間(c<=d)的元素大于等于c序號4大于d序號11a1a2a3a4a5a6a7a8a9a10a11a12a130a14a15找到第1個大于等于c的元素，序號為s找到第一個大于d的元素，序號為tLs LtLs+1 Lt+1Ls+m Lt+m / s+m = t -1 m = t s - 1 Ls + i Lt + i / i = 0 to t-s-1 i=1; / i 從1 循環(huán)到ns = -1; / 第1個大于等于c的元素序號t = -1; / 第1個大于d的

10、元素序號for i = 1 to n step -1if s =-1 and Li>=c / 找到第1個大于等于c的元素 s = i if t = -1 and Li >d / 找到第1個大于d的元素 t = i ; end (i)if s != -1 and t !=-1 i = s while i < t and i + t s <=n Li = L i + t s i+end(while)else return(錯誤 沒有找到 元素在c和d之間)end(if) for j=c to n-d+cLj<-Lj+d-c/把j+d-c項(xiàng)給jEnd(j)N<-n

11、-d+c/所有項(xiàng)數(shù)減少Return2.9 線性表A，B中的元素為字符串類型，用向量結(jié)構(gòu)存儲，試編寫算法，判斷B是否為A的子序列（例如A=ENGLISH ，B=LIS ，則B為A的子序列）Am Bna1a2a3a4a5a6a7a8a9a10a11a12a130a14a15A：b1b2b3b4b5b6B：i=1 檢查A中第1個元素開始的字符串是否與B匹配i=2 檢查A中第2個元素開始的字符串是否與B匹配 i= m n + 1 檢查 A中 第(m-n+1)個元素開始的字符串是否與B匹配AmBnif ( m<n ) then return errorfor ( i =1; i<= m-n+

12、1; i+) for (j = 1; j<= n ; j+) if (Ai+j-1 != Bj ) break; end(j) if j>n then return( A字符串中第i個字符開始的子串與B匹配 ) end(i)renturn (找不到匹配的子串)設(shè)A，B兩個線性表的元素個數(shù)為m，nIf (m<=n)thenreturnFor i=0 to n-1a=Aifor j=0 to m-1if(a=Bj)thenb+end(j)end(i)if(b=m)thenB 為A的子集return2.11寫一個將向量L（a1 ，a2， an）倒置的算法。a1a2a3a4a5a6a

13、7a8a9a10a11a12a130a14a15對L(a1，a2, . ., an )如果是奇數(shù)個元素，則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 交換？ 停止！a1a2a3a4a5a6a7a8a9a10a11a12a130a14a15如果是偶數(shù)個元素，則1，14 交換 1, n 交換2，13 交換 2, n-1 交換3，12 交換 3，n-2 交換4，11

14、 交換 4，n-3 交換5，10 交換 5，n-4 交換6，9 交換 6，n-5 交換7，8 交換 7，n-6 交換8，7 交換？ 8，n-7 交換？ 停止！小結(jié)：n個元素倒置的算法是，i = 1while ( i<n-i+1)ai 與 an-i+1 交換i+end(while) 2.12試編寫算法求已知單鏈表長度，并考慮表空的情況。p = headi = 0While(p!=nil) /表不為空P<- next(p)/移動到下一個元素i+End(while)Return i /返回數(shù)據(jù)的個數(shù)2.13試編寫算法刪除單鏈表中第k個結(jié)點(diǎn)。GETNODE(q)GETNODE(p)q<

15、;-headFor i=1 to k-1q<-next(q)End(i)P<-next(q);next(q)<-next(p)Ret(p)Return2.14 已知一循環(huán)鏈表中數(shù)值已按遞增有序排列現(xiàn)要插入一個新結(jié)點(diǎn)，并使插入一個新節(jié)點(diǎn)，并使插入后鏈表仍為有序序列GETNODE(p)Data(p)=aWhile(data(p)<data(n)n<-next(n)End(while) q <-nnext(p) <-next(q)<-preturn2.18 設(shè)在長度大于1 的循環(huán)鏈表中，即無頭結(jié)點(diǎn)，也無頭指正，p為指向鏈表中每個節(jié)點(diǎn)的指針，試編寫算法刪

16、除該節(jié)點(diǎn)的前趨結(jié)點(diǎn)。q<-Next(p)/找到該節(jié)點(diǎn)的前趨結(jié)點(diǎn)p<-next(q);next(q)<-next(p)RET(p)Return2.20試用單鏈表表示兩個多項(xiàng)式；A=4x12+5x8+6x3+4，B=3x12+6x7+2x4+5(1) 設(shè)計此兩個多項(xiàng)式的數(shù)據(jù)結(jié)構(gòu)。(2) 寫出兩個多項(xiàng)式相加的算法。(3) 分析算法的時間、空間復(fù)雜度。ADD-POLY(ha ,hb )1. pnext(ha); qnext(hb)2. preha;hcha /pre指向p的前趨，為c(x)頭指針/3.while (p<>nil) AND (q<>nil) do

17、4.case5.EXP(p)<EXP(q):6.prep;pnext(p)7.EXP(p)=EXP(q):8.xCOEF(p)+COEF(q);9.if (x<>0) then COEF(p)x;prep10.else next(pre)next(p); RET(p)11.pnext(pre);uq;qnext(q);RET(u)12.EXP(p)>EXP(q):13.unext(q);next(q)p; next(pre)q;preq;qu14.end(case)15.end(while)16.if(q<>nil) then next(pre)q17.RE

18、T(hb)/釋放多項(xiàng)式B(x)的頭結(jié)點(diǎn)/18.return2.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：10為一循環(huán)隊列，初態(tài)front=rear=1，畫出下列操作后隊的頭、尾指示器狀態(tài)：(1) d,e,b,g,h入隊；(2) d,e出隊；(3) i,j,k,l

19、,m,入隊；(4) b出隊；(5) n,o,p,q,r入隊。2.23試畫出表達(dá)式A*(B-D)/C*(E*F)執(zhí)行過程中NS，OS棧的變化情況。2.24用一長度為m的數(shù)組存放一雙向棧，兩個棧頂分別為top1和top2,如圖所示。上溢條件為top1=top2,從鍵盤輸入一串整數(shù)，奇數(shù)入stack1，偶數(shù)如stack2，直到上溢時停止輸入。試編寫一算法實(shí)現(xiàn)此過程。 O_E(R,m,top1,top2,x)1. top1m;top21 /top1,top2置初值2. if (top1=top2) then 上溢,return 3. while (top1<>top2) do 4. if

20、(x mod 2=0) thenRtop2x;top2top2+15. else Rtop1x;top1top1+16.end(while)7.retun2.25 有一個二維數(shù)組A1:m ;1:n,假設(shè)A3,2地址為1110，A2，3地址為1115，若每個單元占一個空間，問A1,4的地址是多少答案：11202.26用三元組和帶行輔助向量形式表示下列的稀疏矩陣：2.28將題圖2.3的一般樹化為二叉樹。答案：2.29 設(shè)一顆完全二叉數(shù)有1000個結(jié)點(diǎn)，試問：(1)有多少個葉子結(jié)點(diǎn) 500(2)有多少個度為2的結(jié)點(diǎn) 499(3) 有多少個結(jié)點(diǎn)只有非空左子樹 12.30 設(shè)一顆二叉樹其中序和后序遍歷為

21、中序：BDCEAFHG后序：DECBHGFA答案：ABCDEFHG231.對二叉樹寫出如下算法：(1)復(fù)制一棵二叉樹；(2)判斷兩棵二叉樹是否相等；(3)計算二叉樹的樹葉；(4)計算二叉樹的深度；解：1）/復(fù)制一棵二叉樹/*算法思想 采用遞規(guī)函數(shù)來實(shí)現(xiàn) （1）如果樹為空，則復(fù)制一棵空樹； （2）如果樹不為空，則依次遞規(guī)復(fù)制已知二叉樹的左子樹和有子樹； （3）生成一個新的根結(jié)點(diǎn)，使復(fù)制得到的左子樹和右子樹的根指針分別成為這個新生成結(jié)點(diǎn)的左指針域和右指針域的值。 算法編寫：*/BiTree *CopyTree(BiTree *T)/if(!T) return NULL;if(T->lchil

22、d)newlchild=CopyTree(T->lchild);/else newlchild=NULL;/if(T->rchild)newrchild=CopyTree(T->rchild);/else newrchild=NULL;/newnode=GetTreeNode(T->data,newlchild,newrchild); /return newnode;/CopyTreeBiTNode *GetTreeNode(TelemType item,BiTNode *lptr,BiTNode *rptr)/T=new BiTNode;T->data=item

23、;T->lchild=lptr;T->rchild=rptr;return T;/GetTreeNode(2)在這里要對一種情況進(jìn)行說明當(dāng)root1的左子樹與root2的左子樹相同，root1的右子樹與root2的右子樹相同時，這兩顆二叉樹相同。當(dāng)root1的左子樹與root2的右子樹相同，root1的右子樹與root2的左子樹相同時，這兩顆二叉樹同樣相同。以下是實(shí)現(xiàn)代碼bool IsBSTEqual(BNode* root1,BNode* root2)        &#

24、160; if (root1=NULL && root2=NULL)                     return true;                

25、;else if (root1=NULL | root2=NULL)                     return false;                else&#

26、160;                     if (root1->data != root2->data)                   

27、0;              return false;                              bool is_lef

28、t = IsBSTEqual(root1->left,root2->left);              bool is_right = IsBSTEqual(root1->right,root2->right);              &

29、#160; if (is_left&&is_right)                   return true;                else    

30、;                              is_right = IsBSTEqual(root1->right,root2->left);         &

31、#160;          is_left = IsBSTEqual(root1->left,root2->right);                      if (is_left&&is_right) 

32、;                        return true;                    else  &#

33、160;                      return false;                        &#

34、160;   3）4）計算葉子數(shù)和樹的深度。計算葉子：遞歸每個節(jié)點(diǎn)，當(dāng)沒有左孩子和右孩子時即為葉子。計算深度：對每個節(jié)點(diǎn)計算左右子樹的深度，節(jié)點(diǎn)的最終深度是其子樹深度的最大值加1，空樹返回-1.struct Tree ElementType Element; Tree *left; Tree *right;int CountLeaf(Tree *T) static int count = 0; if (T != NULL)   CountLeaf(T->left); &

35、#160;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; else   depthLeft = Depth(T->le

36、ft);  depthRight = Depth(T->right);  depth = 1 + (depthLeft > depthRight ? depthLeft:depthRight);  return depth;2.32.給定一組元素17,28,36,54,30,27,94,15,21,83,40,畫出由此生成的二叉排序樹。83283040219454361517解：272.33給定一組權(quán)值W=8,2,5,3,2,17,4,畫出由此生成的哈夫曼樹。2.34.有一圖如題圖2.4所示：（1）寫出此圖的鄰接表與鄰接矩

37、陣；（2）由給點(diǎn)V1作深度優(yōu)先搜索和廣度優(yōu)先搜索；（3）試說明上述搜索的用途。2101820191716151314121197846531解：（1）0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 01 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 00 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 00 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 01 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 1 0 1 0 0 0 0 0 0 0 1

38、0 0 0 0 00 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 01 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 00 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 00 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 10 0 0 1 0 0 0 0 0

39、0 0 0 1 0 1 0 0 0 0 00 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 10 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 00 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 00 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 10 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 85211031212243145346415157561718671571181810

40、89119210191210111311312201412131513414161461520171516181671719179182018111919161320（2）V1作深度優(yōu)先搜索:V1V2V3V4V5V6V7V8V9V10V11V12V13V14V15V16V17V18V19V20 V1作廣度優(yōu)先搜索:V1V2V5V8V3V10V4V6V7V9V12V11V14V15V17V18V13V19V16V20(3)為了避免同一頂點(diǎn)被多次訪問。2.35.有一又向圖如題圖2.5所示：5643（1）寫出每一結(jié)點(diǎn)的入度和出度各為多少；（2）寫出上圖的鄰接矩陣和鄰接表。解：V1:入度=3 出度=0

41、V2:入度=2 出度=2V3:入度=1 出度=2V4:入度=2 出度=2V5:入度=2 出度=1V6:入度=0 出度=40 0 0 0 0 01 0 0 1 0 00 1 0 0 0 10 0 1 0 1 01 0 0 0 0 01 1 0 1 1 0153123456142 45 21 63.36 求題圖2.6中結(jié)點(diǎn)a到各結(jié)點(diǎn)之間最短路徑。hfgedcba 2 2 2 2 1 2 3 3 1 4 1解：ab:2ac:3abd:4abde:6abdef:7abdeg:8abdefh:82.37 求題圖2.7中所示AOV網(wǎng)所有可能的拓?fù)漤樞蚪Y(jié)果。 解: 21738546V1V2V3V4V5V6

42、0000013 8 68 4 8 V7 0V8 0 0 8 4 拓?fù)渑判颍篤7->V5->V2->V4->V6->V3->V1->V82.38 題圖2.8所示AOE網(wǎng)，求:(1).每一事件最早開始時間和最晚開始時間;(2).該計劃最早完成時間為多少。解: 活動最早最遲開始時間a1a2a3a4a5a6a7a8a9a10a11a12a13a14E00566121212191916202325L409616121916191923202325L-E404010074007000事件最早最遲開始時間V1V2V3V4V5V6V7V8V9V10VE05612191

43、620232527VL096121923202325272.39某校97級同學(xué)舉辦運(yùn)動會，報名同學(xué)學(xué)號為97438，97102，97528，97136，97338，97250，97407，97239，97227，97517，97321，97421，97451，97241，97118，97543，97309畫出進(jìn)行分塊查找的數(shù)據(jù)組織形式。2.40 畫一棵對20個記錄進(jìn)行對分查找的判定樹,并求等概率情況下的平均查找長度。ASL=(1+2*2+3*4+4*8+5*5)/20=3.72.41設(shè)有10個記錄的關(guān)鍵字為ICKES，BARBER，ELYOT，KERN，F(xiàn)RENCE，LOWES，BENSDN，

44、FONK，ERVIN，KNOX。構(gòu)造=10/13的哈希表，取關(guān)鍵字首字母表中的序號為哈希函數(shù)值，用隨機(jī)探測解決沖突，di=(d1+Rj) mod 13，Rj取自偽隨機(jī)數(shù)列：3，7，1，12，10，。統(tǒng)計該表的平均查找長度ASL。2.42對于給定的一組關(guān)鍵字：41,62,13,84,35,96,57,39,79,61,15,83。分別寫出：插入排序、簡單選擇排序、堆排序、冒泡排序、快速排序、二叉樹排序的排序過程，并對各排序方法進(jìn)行分析。排序，簡單選擇排序、堆排序、冒泡排序、快速排序、二叉樹排序的排序過程，并對排序方法進(jìn)行分析。插入13 41 62 84 35, 96,57,39, 79,61,1

45、5,8313 35 41 62 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個記錄的文件，要進(jìn)行n-1趟排序就地排序穩(wěn)定的排序方法簡單選擇排序41，62，13，84，

46、35，96，57，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

47、 8313 15 35 39 41 57 61 62 79 83 84 96堆排序41 62 13 84 35 96 57 39 79 61 15 83 96, 84, 83, 79, 62, 61, 57, 41, 39, 35, 15, 13冒泡排序41，62，13，84，35，96，57，39，79，61，15，83 41, 13, 62, 35, 84, 57, 39, 79, 61, 15, 83, 96 13, 41, 35, 62, 57, 39, 79, 61, 15, 83, 84, 96 13, 35, 41, 57, 39, 62, 61, 15, 79, 83, 84,

48、 96 13, 35, 41, 39, 57, 61, 15, 62, 79, 83, 84, 96 13, 35, 39, 41, 57, 15, 61, 62, 79, 83, 84, 96 13, 35, 39, 41, 15, 57, 61, 62, 79, 83, 84, 96 13, 35, 39, 15, 41, 57, 61, 62, 79, 83, 84, 96 13, 35, 15, 39, 41, 57, 61, 62, 79, 83, 84, 96 13, 15, 35, 39, 41, 57, 61, 62, 79, 83, 84, 96 13, 15, 35, 39

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

50、84, 62 13, 15, 35, 39, 41, 96, 57, 83, 79, 61, 84, 62 13, 15, 35, 39, 41, 96, 57, 83, 79, 61, 84, 62 13, 15, 35, 39, 41, 62, 57, 83, 79, 61, 84, 96 13, 15, 35, 39, 41, 57, 61, 62, 79, 84, 83, 96 13, 15, 35, 39, 41, 57, 61, 62, 79, 84, 83, 96 13, 15, 35, 39, 41, 57, 61, 62, 79, 84, 83, 96 13, 15, 35,

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

52、84, 96 13, 15, 35, 39, 41, 57, 61, 62, 79, 84, 96 13, 15, 35, 39, 41, 57, 61, 62, 79, 83, 84, 96第三章 操作系統(tǒng)3.1 操作系統(tǒng)的基本功能是什么？它包括哪些部分？ 基本功能： 操作系統(tǒng)應(yīng)該具有處理器管理，存儲管理，設(shè)備管理和文件管理功能，同時，為了使用戶能方便地使用機(jī)器，操作系統(tǒng)還應(yīng)提供用戶接口功能。 構(gòu)成部分： （1）. 對CPU的使用進(jìn)行管理的進(jìn)程調(diào)度程序 。 （2）. 對內(nèi)存分配進(jìn)行管理的內(nèi)存管理程序。 （3）. 對輸入輸出設(shè)備進(jìn)行管理的設(shè)備驅(qū)動程序。（4） . 對外存中信息進(jìn)行管理的文件系統(tǒng)

53、。3.2 試說明虛擬機(jī)的概念以及實(shí)現(xiàn)的方法。在裸機(jī)外面每增加一個軟件層后就會變成一臺功能更強(qiáng)的機(jī)器，我們通常把這種計算機(jī)系統(tǒng)稱為虛擬機(jī)。 虛擬機(jī)的實(shí)現(xiàn)方法：在裸機(jī)上裝上操作系統(tǒng)對機(jī)器進(jìn)行首次擴(kuò)展，再在操作系統(tǒng)的基礎(chǔ)上增加其他軟件，這樣就可以實(shí)現(xiàn)“虛擬機(jī)”。3.3通常操作系統(tǒng)有哪幾種基本類型？各有什么特點(diǎn)及適用于何種場合？三大類：（1）多道批處理系統(tǒng)：計算機(jī)內(nèi)存中同時可以存放多道作業(yè)，用戶與作業(yè)之間沒有交互作用，用戶不能直接控制作業(yè)的運(yùn)行。此類系統(tǒng)一般用于計算中心等較大型的計算機(jī)系統(tǒng)中。（2）分時系統(tǒng)：多個用戶通過終端分享同一臺計算機(jī)，并通過終端直接控制程序運(yùn)行，進(jìn)行人與機(jī)器之間的交互。此類系統(tǒng)

54、適用于程序的開發(fā)。（3）實(shí)時系統(tǒng)：對外部發(fā)生的隨機(jī)事件作出及時的響應(yīng)，并對它進(jìn)行處理。此類系統(tǒng)一般用于工業(yè)控制系統(tǒng)或事物處理系統(tǒng)。3.4試說明你所使用過的操作系統(tǒng)的類型和特點(diǎn)。Windows系統(tǒng)：多用戶多任務(wù)操作系統(tǒng)。特點(diǎn)：全新的、友善的用戶界面。 提供了功能強(qiáng)大的應(yīng)用程序。 具有多任務(wù)并行處理能力，各種應(yīng)用程序之間可以方便地進(jìn)行切換和交換信息。 具有強(qiáng)大的內(nèi)存管理能力，支持?jǐn)U展內(nèi)存功能，提高系統(tǒng)運(yùn)行效率。3.5 解釋名空間、作業(yè)地址空間和存儲空間的關(guān)系以及邏輯地址和物理地址的區(qū)別。存放源程序的空間稱為名空間。當(dāng)匯編或編譯程序?qū)⒃闯绦蜣D(zhuǎn)換成目標(biāo)程序后，一個目標(biāo)程序所占有的地址范圍稱為地址空間，

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

56、么決定？存儲管理的功能主要分為：內(nèi)存分配、地址轉(zhuǎn)換、存儲保護(hù)和內(nèi)存擴(kuò)充。虛擬存儲器能提供給用戶一個比實(shí)際內(nèi)存大得多的存儲空間，使用戶在編制程序時可以不必考慮存儲空間的限制。虛存的容量受兩個條件約束：指令中地址場長度的限制、外存儲器容量的限制。3.10 什么是作業(yè)、作業(yè)步和進(jìn)程？作業(yè)是用戶在一次算題過程中或一個事務(wù)處理中要求計算機(jī)系統(tǒng)所做的集合。一個作業(yè)是由一系列有序的作業(yè)步所組成。一個作業(yè)步運(yùn)行的結(jié)果產(chǎn)生下一個作業(yè)步所需的文件。進(jìn)程可以看成是程序的一次執(zhí)行，即是在指定內(nèi)存區(qū)域的一組指令序列的執(zhí)行過程。3.11 處理器管理主要解決什么問題？在大型通用系統(tǒng)中，可能數(shù)百個批處理作業(yè)存放在磁盤中，又有數(shù)百個終端用戶與主機(jī)聯(lián)接，如何從這些作業(yè)中挑選一些作業(yè)進(jìn)入主存運(yùn)行，又如何在主存各進(jìn)程間分配處理器，是操作系統(tǒng)資源管理的一個重要問題，處理器管理就是用來解決此問題的。3.12 什么是進(jìn)程的同步和互斥？什么是臨界區(qū)？ “同步”是指兩個事件的發(fā)生存在某種時序上的關(guān)系，如果系統(tǒng)中有若干個進(jìn)程要共同完成某一任務(wù)，那么它們相互之間必須協(xié)調(diào)配合?！盎コ狻笔侵府?dāng)多個進(jìn)程要求共享系統(tǒng)中某些硬件或軟件資源，而這些資源卻又要