計(jì)算機(jī)習(xí)題答案20140621VIP

1、2.1 什么是數(shù)據(jù)結(jié)構(gòu)？它對(duì)算法有什么影響？ 答：數(shù)據(jù)結(jié)構(gòu)是指同一數(shù)據(jù)對(duì)象中各數(shù)據(jù)元素間存在的關(guān)系，可以看作是相互之間存在著某種特定關(guān)系的數(shù)據(jù)元素的集合。對(duì)算法是影響：算法的效率與數(shù)據(jù)結(jié)構(gòu)有關(guān)，數(shù)據(jù)結(jié)構(gòu)的選擇對(duì)算法實(shí)現(xiàn)的效率起至關(guān)重要的作用。2.2何謂算法？它與程序有何區(qū)別？算法是解決某一特定類(lèi)型問(wèn)題的有限運(yùn)算序列。和程序的區(qū)別：一個(gè)程序包括數(shù)據(jù)結(jié)構(gòu)和算法兩個(gè)方面的內(nèi)容，算法是程序的一個(gè)要素。2.6 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)主要有哪兩種?它們之間的本質(zhì)區(qū)別是什么？數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)主要有順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。本質(zhì)區(qū)別：順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)空間是連續(xù)的，數(shù)據(jù)元素間的邏輯關(guān)系借助存儲(chǔ)的相對(duì)位置來(lái)表示；鏈?zhǔn)酱?/p>

2、儲(chǔ)結(jié)構(gòu)不需要一組連續(xù)的存儲(chǔ)單元，其數(shù)據(jù)元素可以分散存放在存儲(chǔ)空間中，其數(shù)據(jù)元素之間的邏輯關(guān)系借助指針來(lái)表示。2.12 試編寫(xiě)算法求已知單鏈表的長(zhǎng)度，并考慮表空的情況int GetListLength(Node* pHead)int i = 0;Node* pCur = pHead;while (pCur != NULL) i+; pCur = pCur->next;return i;2.13 試編寫(xiě)算法刪除單鏈表中的第K個(gè)節(jié)點(diǎn)/ 2.13 刪除單鏈表中的第k個(gè)節(jié)點(diǎn)。注： 節(jié)點(diǎn)序號(hào)從1開(kāi)始void RemoveNode(Node*& pHead, int k)Node* pPre

3、= NULL;Node* pCur = NULL;pCur = pHead;int i = 1;while (pCur != NULL) / 不是要?jiǎng)h的節(jié)點(diǎn)序號(hào)，則繼續(xù)下一個(gè)節(jié)點(diǎn)if (k != i) pPre = pCur;pCur = pCur->next;i+;continue;/ 要?jiǎng)h除的就是第一個(gè)節(jié)點(diǎn)if (k = 1)pHead = pCur->next;else / 要?jiǎng)h除的是中間某個(gè)節(jié)點(diǎn)pPre->next = pCur->next;delete pCur;2.14 已知一單向鏈表中數(shù)值已按遞增有序排列，先要插入一個(gè)新節(jié)點(diǎn)，并使插入后鏈表仍為有序序列/可

4、參考膠片19頁(yè)Typedef struct tagNodeInt data;Node* next;Node;void InsertNode(Node*& pHead, Node* pNewNode)/ 鏈表為空時(shí)，將該節(jié)點(diǎn)作為鏈表的第一個(gè)節(jié)點(diǎn)if (pHead = NULL) pHead = pNewNode;return;Node* pPre = NULL;Node* pCur = pHead;while(pCur != NULL)/ 新節(jié)點(diǎn)的數(shù)據(jù)比單鏈表的頭節(jié)點(diǎn)的數(shù)據(jù)小，則將新節(jié)點(diǎn)插入到最開(kāi)頭if (pCur->data > pNewNode->data) pNe

5、wNode->next = pCur;pHead = pNewNode;break;Node* pNext = pCur->next;/ 將新節(jié)點(diǎn)插入到單鏈表的表尾if (pNext = NULL)pCur->next = pNewNode;break;/ 將新節(jié)點(diǎn)插入到單鏈表的中間if (pNext->data > pNewNode->data)pNewNode->next = pNext;pCur->next = pNewNode;break;pPre = pCur;pCur = pNext;return;2.28 將下列的一般樹(shù)化為二叉樹(shù)轉(zhuǎn)

6、換后的二叉樹(shù)如右圖所示 轉(zhuǎn)換后 2.30 設(shè)一棵二叉樹(shù)其中序和后序遍歷為，中序：BDCEAFHG 后序：DECBHGFA畫(huà)出這棵二叉樹(shù)的邏輯結(jié)構(gòu)，并寫(xiě)出先序遍歷結(jié)果。先序遍歷：ABCDEFGH。其邏輯結(jié)構(gòu)如下：ABFCDEGH2.32 給定一組元素17，28,36,54,30,27,94,15,21,83,40，畫(huà)出由此生成的二叉排序樹(shù)。2.33 定一組權(quán)值W=8，2，5，3，2，17，4，畫(huà)出由此生成的哈夫曼樹(shù)。 生成的哈夫曼樹(shù)為： 或者 2.34 有一圖如下圖所示：由節(jié)點(diǎn)V1 作深度優(yōu)先搜索和廣度優(yōu)先搜索。深度： 1 5 4 3 2 10 11 12 13 14 15 6 7 8 9 18

7、 19 20 16 17廣度： 1 8 7 6 5 17 18 9 16 15 10 2 14 13 20 19 11 4 3 12 3 2.42 對(duì)于給定的一組關(guān)鍵字：41，62，13，84，35，96，57，39，79，61，15，83。分別寫(xiě)出：插入排序，簡(jiǎn)單選擇排序、堆排序、冒泡排序、快速排序、二叉樹(shù)排序的排序過(guò)程，并對(duì)排序方法進(jìn)行分析。插入13 41 62 84 35, 96,57,39, 79,61,15,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

8、 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 對(duì)于具有n個(gè)記錄的文件，要進(jìn)行n-1趟排序就地排序穩(wěn)定的排序方法簡(jiǎn)單選擇排序41 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

9、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 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冒泡排

10、序 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, 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,

11、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, 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快速排序 13, 35, 39, 15, 41, 96, 57, 83

12、, 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, 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 1

13、3, 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, 39, 41, 57, 61, 62, 79, 83, 84, 96 二叉樹(shù)排序 二叉樹(shù)建立過(guò)程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

14、, 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, 84, 96 13, 15, 35, 39, 41, 57, 61, 62, 79, 84, 96 13, 15, 35, 39, 41, 57, 61, 62, 79, 83, 84, 963.1 操作系統(tǒng)的基本功能是什么？它包括哪些部分？操作系統(tǒng)具有處理機(jī)管理、存儲(chǔ)管理、設(shè)備管理和文件管理，同時(shí)，為了使用戶(hù)能方便地使用機(jī)器，操作系統(tǒng)還應(yīng)提供用戶(hù)接口功能。 處理機(jī)管理：負(fù)責(zé)處理及資源的管理

15、，包括進(jìn)程控制、進(jìn)程同步、進(jìn)程通信及調(diào)度。內(nèi)存管理：負(fù)責(zé)內(nèi)存資源管理，包括內(nèi)存分配及回收、信息保護(hù)、地址映射及內(nèi)存擴(kuò)充。設(shè)備管理：負(fù)責(zé)設(shè)備資源的管理，包括設(shè)備分配回收、緩沖管理、設(shè)備處理、設(shè)備獨(dú)立性。文件管理：負(fù)責(zé)信息資源管理，包括文件存儲(chǔ)空間管理、目錄管理、文件操作、文件共享保護(hù)。用戶(hù)接口：命令接口及程序接口。3，3通常操作系統(tǒng)有哪幾種基本類(lèi)型？各有什么特點(diǎn)及適用于何種場(chǎng)合？課本P109（1） 多道批處理系統(tǒng)：計(jì)算機(jī)內(nèi)存中同時(shí)可以存放多道作業(yè)，用戶(hù)與作業(yè)之間沒(méi)有交互作用，用戶(hù)不能直接控制作業(yè)的運(yùn)行。此類(lèi)系統(tǒng)一般用于計(jì)算中心等較大型的計(jì)算機(jī)系統(tǒng)中。（2） 分時(shí)系統(tǒng)：多個(gè)用戶(hù)分享同一臺(tái)計(jì)算機(jī)，它

16、把處理機(jī)的時(shí)間分成很短的時(shí)間片，按時(shí)間片輪流把處理機(jī)分配給各聯(lián)機(jī)作業(yè)使用。用戶(hù)感覺(jué)好像只有自己獨(dú)占計(jì)算機(jī)一樣。此類(lèi)系統(tǒng)適用于程序的開(kāi)發(fā)。（3） 實(shí)時(shí)系統(tǒng)：實(shí)時(shí)系統(tǒng)是指系統(tǒng)能及時(shí)響應(yīng)外部事件的請(qǐng)求，在規(guī)定的時(shí)間范圍內(nèi)完成對(duì)該事件的處理，并控制實(shí)時(shí)任務(wù)協(xié)調(diào)一致地運(yùn)行。此類(lèi)系統(tǒng)一般用于工業(yè)控制系統(tǒng)或事物處理系統(tǒng)。3.6 什么是重定位？靜態(tài)重定位和動(dòng)態(tài)重定位的區(qū)別是什么？各舉一例說(shuō)明。當(dāng)用戶(hù)程序要調(diào)入內(nèi)存時(shí)，必須把程序的邏輯地址轉(zhuǎn)換為絕對(duì)地址，同時(shí)要包括對(duì)程序中與地址有關(guān)的指令進(jìn)行修改，這一過(guò)程稱(chēng)為重定位。靜態(tài)重定位：地址變換在程序裝入時(shí)由重定位裝入程序一次完成，以后不再改變；不需硬件支持，但程序運(yùn)行

17、時(shí)不能在內(nèi)存移動(dòng)，程序需要連續(xù)存儲(chǔ)空間，難以共享。動(dòng)態(tài)重定位：在程序執(zhí)行過(guò)程中，每次訪(fǎng)問(wèn)內(nèi)存之前將要訪(fǎng)問(wèn)程序地址轉(zhuǎn)換成內(nèi)存地址；需要硬件支持，不需連續(xù)空間，可以實(shí)現(xiàn)虛擬存儲(chǔ)。3.7 存儲(chǔ)管理器的功能是什么？為什么要引入虛擬存儲(chǔ)器的概念？虛存的容量由什么決定？存儲(chǔ)管理的功能主要分為：內(nèi)存分配、地址轉(zhuǎn)換、存儲(chǔ)保護(hù)和內(nèi)存擴(kuò)充。虛擬存儲(chǔ)器可以在不擴(kuò)充物理內(nèi)存的情況下，能提供給用戶(hù)一個(gè)比實(shí)際內(nèi)存大得多的存儲(chǔ)空間，使用戶(hù)在編制程序時(shí)可以不必考慮存儲(chǔ)空間的限制，達(dá)到即擴(kuò)充內(nèi)存又不增加成本的目的。虛存的容量受兩個(gè)條件約束：指令中地址場(chǎng)長(zhǎng)度的限制、外存儲(chǔ)器容量的限制。3.11 處理器管理主要解決什么問(wèn)題？解決用

18、戶(hù)提交的作業(yè)何時(shí)調(diào)入內(nèi)存，在調(diào)入內(nèi)存的各作業(yè)之間如何分配處理機(jī)。3.12 什么是進(jìn)程的同步和互斥？什么是臨界區(qū)？同步：多個(gè)相關(guān)合作的進(jìn)程，在一些關(guān)鍵點(diǎn)上可能需要互相等待或互相交換信息。這種相互制約關(guān)系稱(chēng)為進(jìn)程同步。互斥：當(dāng)一個(gè)進(jìn)程正在訪(fǎng)問(wèn)某共享資源時(shí)，就不允許其他進(jìn)程對(duì)其訪(fǎng)問(wèn)，這種相互制約關(guān)系稱(chēng)為互斥。臨界區(qū)：進(jìn)程中訪(fǎng)問(wèn)臨界資源的那段代碼稱(chēng)為臨界區(qū)，又稱(chēng)臨界段。3.16 死鎖產(chǎn)生的必要條件是什么？死鎖的預(yù)防、避免和檢測(cè)各有什么不同？各舉一種相應(yīng)的方法。死鎖產(chǎn)生的必要條件：互斥條件：在一段時(shí)間內(nèi)某資源僅為一個(gè)進(jìn)程所占有。不剝奪條件：進(jìn)程所獲得的資源在未使用完畢之前，不能被其他進(jìn)程強(qiáng)行奪走。請(qǐng)求和

19、保持條件：又稱(chēng)部分分配條件。當(dāng)進(jìn)程因請(qǐng)求資源被阻塞時(shí)，已分配資源保持不放。循環(huán)等待條件：死鎖發(fā)生時(shí)，存在一個(gè)進(jìn)程資源的循環(huán)。不同點(diǎn)： 死鎖的預(yù)防：設(shè)置某些限制條件，通過(guò)破壞死鎖產(chǎn)生的四個(gè)必要條件之一來(lái)預(yù)防死鎖。 死鎖的避免：在資源的動(dòng)態(tài)分配過(guò)程中，用某種方法來(lái)防止系統(tǒng)進(jìn)入不安全狀態(tài)。 死鎖的檢測(cè)及解除：系統(tǒng)定期檢測(cè)是否出現(xiàn)死鎖，若出現(xiàn)則解除死鎖。舉例：死鎖預(yù)防：靜態(tài)資源分配法、有序資源分配法死鎖避免：銀行家算法死鎖檢測(cè)：資源剝奪法、撤銷(xiāo)進(jìn)程法3.19 設(shè)備管理的功能是什么？怎樣把一臺(tái)物理設(shè)備虛擬為多臺(tái)設(shè)備？設(shè)備管理的功能： 設(shè)備分配：根據(jù)用戶(hù)的I/O請(qǐng)求，為之分配設(shè)備。包含控制器和通道。 設(shè)備

20、處理：負(fù)責(zé)啟動(dòng)設(shè)備及I/O操作完成時(shí)的中斷處理。 緩沖管理：為緩和CPU與I/O速度不匹配的矛盾常設(shè)置緩沖區(qū)。緩沖管理負(fù)責(zé)緩沖區(qū)的分配和釋放及有關(guān)管理工作。 設(shè)備獨(dú)立性：又稱(chēng)設(shè)備無(wú)關(guān)性，是指用戶(hù)編制程序時(shí)所使用的設(shè)備與物理設(shè)備無(wú)關(guān)。假脫機(jī)系統(tǒng)利用高速的直接存儲(chǔ)設(shè)備來(lái)模擬低速的獨(dú)占設(shè)備，并使其轉(zhuǎn)換成共享設(shè)備，這種技術(shù)被稱(chēng)為虛擬設(shè)備技術(shù)，其基本實(shí)現(xiàn)思想是：輸入Spooling：系統(tǒng)把原來(lái)使用獨(dú)占設(shè)備的輸入過(guò)程分成兩步：首先將用戶(hù)的作業(yè)由輸入設(shè)備以文件形式保存在磁盤(pán)的專(zhuān)門(mén)區(qū)域（輸入井）中，這由Spooling系統(tǒng)的輸入收存程序來(lái)完成；當(dāng)運(yùn)行的進(jìn)程需要輸入信息時(shí)，由Spooling系統(tǒng)中的輸入發(fā)送程序

21、負(fù)責(zé)從輸入井中將有關(guān)文件讀入內(nèi)存。在這里輸入井起到了虛擬輸入機(jī)的作用。輸出Spooling：當(dāng)作業(yè)執(zhí)行過(guò)程中需要輸出時(shí)，由Spooling系統(tǒng)中的輸出收存程序負(fù)責(zé)將要求輸出的信息以文件形式暫存到磁盤(pán)的專(zhuān)門(mén)區(qū)域（輸出井）中，等待該作業(yè)運(yùn)行完畢，Spooling系統(tǒng)的輸出發(fā)送程序?qū)?duì)應(yīng)該作業(yè)的輸出文件通過(guò)輸出設(shè)備輸出。因此輸出井起到了虛擬輸出機(jī)的作用。補(bǔ)充題目：什么是設(shè)備獨(dú)立性，有何好處？又稱(chēng)設(shè)備無(wú)關(guān)性，是指用戶(hù)編制程序時(shí)使用的設(shè)備與實(shí)際使用的物理設(shè)備無(wú)關(guān)。使用設(shè)備獨(dú)立性的優(yōu)點(diǎn)：設(shè)備分配的靈活性。進(jìn)程在執(zhí)行時(shí)可利用該類(lèi)設(shè)備中任一物理設(shè)備，而不必僅限于使用具體的某一設(shè)備，可提高設(shè)備的利用率。易于實(shí)現(xiàn)

22、I/O重定向。程序的I/O操作不必指出在哪臺(tái)輸入、輸出設(shè)備上進(jìn)行。3.22 什么是文件目錄？有幾種目錄結(jié)構(gòu)形式？各有什么特點(diǎn)？文件目錄是計(jì)算機(jī)對(duì)文件進(jìn)行管理的一種數(shù)據(jù)結(jié)構(gòu)。通常有一級(jí)目錄、二級(jí)目錄和多級(jí)目錄結(jié)構(gòu)。一級(jí)目錄：最簡(jiǎn)單的結(jié)構(gòu)形式，整個(gè)文件系統(tǒng)只建立一張目錄表，每個(gè)文件占據(jù)其中一個(gè)表項(xiàng)，查找時(shí)要掃描這個(gè)歌目錄，增加查找時(shí)間。目錄中的文件符號(hào)名不能重復(fù)二級(jí)目錄：由主目錄文件和用戶(hù)目錄文件組成。主文件目錄記錄用戶(hù)名及相應(yīng)用戶(hù)文件目錄所在的存儲(chǔ)位置；用戶(hù)文件目錄記錄該用戶(hù)文件的有關(guān)信息。多級(jí)目錄：第一級(jí)目錄稱(chēng)為根目錄（樹(shù)根），目錄樹(shù)中的非葉節(jié)點(diǎn)均為目錄文件（又稱(chēng)子目錄），葉結(jié)點(diǎn)為文件。4.1

23、 試比較數(shù)據(jù)庫(kù)系統(tǒng)與文件系統(tǒng)，說(shuō)明兩者的異同。相同點(diǎn)：A、都是以文件為基本單位存儲(chǔ)數(shù)據(jù)B、數(shù)據(jù)都有邏輯結(jié)構(gòu)與物理結(jié)構(gòu)之分C、都有專(zhuān)門(mén)的軟件系統(tǒng)管理數(shù)據(jù)不同點(diǎn)：A、文件系統(tǒng)中的文件是面向應(yīng)用組織的，一個(gè)文件基本對(duì)應(yīng)一個(gè)應(yīng)用程序，數(shù)據(jù)間的聯(lián)系弱；數(shù)據(jù)庫(kù)系統(tǒng)中的文件是面向整個(gè)應(yīng)用系統(tǒng)組織的，減少了數(shù)據(jù)冗余，實(shí)現(xiàn)了數(shù)據(jù)共享。B、數(shù)據(jù)庫(kù)系統(tǒng)中的邏輯結(jié)構(gòu)又分成局部數(shù)據(jù)邏輯結(jié)構(gòu)和全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)兩級(jí)C、DBMS管理數(shù)據(jù)的功能比OS中的文件系統(tǒng)要強(qiáng)得多。4，3數(shù)據(jù)庫(kù)系統(tǒng)的三級(jí)結(jié)構(gòu)模式各起什么作用。外模式（子模式）對(duì)局部數(shù)據(jù)邏輯結(jié)構(gòu)和特征的描述。（多個(gè)） 概念模式（模式）對(duì)全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)和特征的描述。（一個(gè)）。定義模式時(shí)不僅要定義數(shù)據(jù)的邏輯結(jié)構(gòu)，還要定義與數(shù)據(jù)有關(guān)的安全性、完整性要求。 內(nèi)模式（存儲(chǔ)模式、物理模式）對(duì)數(shù)據(jù)物理結(jié)構(gòu)和存儲(chǔ)方式的描述。（一個(gè)）4.4 試說(shuō)明數(shù)據(jù)庫(kù)設(shè)計(jì)的主要步驟，各完成什么工作。主要步驟：A、 需求分析：了解用戶(hù)需求；B、 概念設(shè)計(jì)：對(duì)用戶(hù)需求進(jìn)行綜合抽象，形成獨(dú)立于具體DBMS的概念模型；C、 邏輯設(shè)計(jì)：將概念結(jié)構(gòu)轉(zhuǎn)換為所用DBMS支持的數(shù)據(jù)模型并