計算機軟件技術基礎課程練習題

word文檔可自由復制編輯計算機軟件技術基礎課程學習練習題趙俊生編內(nèi)蒙古工業(yè)大學信息工程學院2011-3-1word文檔可自由復制編輯

目錄《計算機軟件技術基礎》練習題（一） 1《計算機軟件技術基礎》練習題（二） 7《計算機軟件技術基礎》練習題（三） 14《計算機軟件技術基礎》練習題（四） 18《計算機軟件技術基礎》練習題（一）參考答案 21《計算機軟件技術基礎》練習題（二）參考答案 24《計算機軟件技術基礎》練習題（三）參考答案 27《計算機軟件技術基礎》練習題（四）參考答案 31word文檔可自由復制編輯《計算機軟件技術基礎》練習題（一）一、填空題（請在每個題目中的橫線上填上準確的內(nèi)容。）1．衡量算法的優(yōu)劣，通常用計算機執(zhí)行時的時間和空間資源的消耗多少作為評價標準?？臻g復雜度是以在算法中所需的輔助空間單元的多少來衡量的。3．線性表有兩種存儲結構，分別是向量和鏈表。4．線性表的結構特點是：數(shù)據(jù)元素之間是線性關系，在表中除第一個元素外，每個元素有且只有一個前趨元素；除最后一個元素外，每個元素有且只有一個后繼元素。用一組地址連續(xù)的存儲單元存放線性表的數(shù)據(jù)元素，稱為線性表的順序存儲結構。在線性表的鏈式存儲結構中，每一個數(shù)據(jù)元素由兩個域組成，一個是存放元素值的數(shù)據(jù)域，另一個是存放后繼元素存儲地址的指針域。7．在棧中，允許插入或刪除的一端稱為棧頂，另一端稱為棧底(bottom)。8．在樹結構中，度為零的結點稱為葉子結點，又稱端結點。9．二叉樹的第i層上至多有2i-1個結點。10．哈夫曼樹又稱最優(yōu)樹，是一類帶權路徑最短的樹。11．計算機硬件部分包括處理機、存儲器、輸入輸出設備和各種通信設備。12．“批處理”是指用戶與作業(yè)之間沒有交互作用，用戶不能直接控制作業(yè)的運行。13．分時系統(tǒng)是指多個用戶共享同一臺計算機，系統(tǒng)將CPU的時間片輪流分配給多個用戶。14．處理機管理主要解決CPU的分配策略、實施方法以及資源的分配和回收問題。15．文件管理的基本功能是實現(xiàn)對文件的存取和檢索，為用戶提供方便靈活的操作命令以及實現(xiàn)文件共享、安全、保密等措施。16．虛擬是指通過某種技術把一個物理實體變?yōu)槿舾蓚€邏輯上的對應物。17．當目標程序裝入主存后占用的一系列物理單元的集合，稱為存儲空間。18．可重定位分區(qū)分配是在可變分區(qū)分配基礎上增加內(nèi)存緊縮功能形成的。19．常用的兩種頁面置換算法為先進先出法和最近最少使用法。20．進程的三種基本狀態(tài)有就緒狀態(tài)、執(zhí)行狀態(tài)和阻塞狀態(tài)。21．順序程序執(zhí)行的特點有順序性、封閉性和可再現(xiàn)性。22．設備分配算法有先請求先服務和優(yōu)先數(shù)兩種。23．常見的文件物理結構有順序結構、鏈接結構和索引結構三種。24．可行性研究主要集中在經(jīng)濟可行性和技術可行性兩個方面。25．軟件工程的基本原則包括劃分軟件生命期、進行計劃評審和編制軟件文檔。26．軟件維護主要包括改正性維護、適應性維護和完善性維護三個方面。27．軟件測試有黑盒測試和白盒測試兩類方法。28．數(shù)據(jù)處理問題的兩種類型有變換型和事務處理型。29．軟件開發(fā)人員的組織原則有盡早落實責任和減少接口。30．軟件開發(fā)小組內(nèi)部人員的組織形式主要有民主制和主程序員制兩種。二、單項選擇題（請在每個小題的四個備選答案中選擇一個正確答案的序號填入題干的括弧中，多填不得分。）以下程序段的時間復雜度為（C）。fori=1tonforj=1tonfork=1tonx←x+1end(k)end(j)end(i)（A）O(n)（B）O(n2)（C）O(n3)（D）O(3n)2．在數(shù)據(jù)結構中，從邏輯上可以把數(shù)據(jù)結構分成（C）。（A）動態(tài)結構和靜態(tài)結構（B）內(nèi)部結構和外部結構（C）線性結構和非線性結構（D）緊湊結構和非緊湊結構3．時間復雜度可以評估一個算法的（A）。（A）時間增長趨勢（B）具體執(zhí)行時間（C）復雜程度（D）正確性4．以下對線性表的描述，正確的是（B）。向量的存儲空間是動態(tài)分配的線性鏈表只能順序存取棧是先進先出的線性表隊是先進后出的線性表5．在單鏈表中，在p指針之后插入一個s指針所指的結點，則需執(zhí)行（A）。next(s)←next(p);next(p)←snext(p)←s;next(s)←next(p)next(p)←next(s);next(p)←snext(s)←next(p);s←next(p)6．有一顆具有n個結點的k叉樹，則有nk個指針域，其中有用的指針域為（C）個。（A）n（B）nk-1（C）n-1（D）nk7．以下二叉樹的帶權路徑長度為（A）。（A）44（B）48（C）40（D）56aabcd86358．下圖的深度優(yōu)先遍歷序列正確的是（A）。（A）V2→V1→V3→V5→V4→V6（B）V2→V1→V3→V5→V6→V4（C）V2→V5→V1→V3→V4→V6（D）V2→V5→V1→V3→V6→V411253469．表長為n的線性表，在等概率情況下，線性查找的平均查找長度為（C）。（A）n/2（B）(n-1)/2（C）(n+1)/2（D）n10．對有序表(18,20,25,34,48,62,74,85)用對分查找法查找74，查找成功時所需的比較次數(shù)為（B）次。（A）2（B）3（C）4（D）511．一組記錄的關鍵字為{3,8,5,9,7,6,2}，則利用冒泡排序的方法，經(jīng)過第一次掃描得到的排序結果為（A）。（A）3,5,8,7,6,2,9（B）3,8,5,7,6,2,9（C）3,5,6,7,8,2,9（D）2,3,5,8,7,6,912．操作系統(tǒng)的主要功能是管理計算機系統(tǒng)中的（C）。（A）程序和數(shù)據(jù)（B）作業(yè)（C）資源（D）進程13．允許多個用戶以交互方式使用計算機的操作系統(tǒng)稱為（A）。（A）分時操作系統(tǒng)（B）實時操作系統(tǒng)（C）批處理操作系統(tǒng)（D）多處理機操作系統(tǒng)14．批處理系統(tǒng)的主要缺點是（C）。（A）CPU利用率低（B）不能并發(fā)執(zhí)行（C）缺少交互性（D）以上都不是15．下列哪個選項不是操作系統(tǒng)關心的問題（D）。（A）管理計算機裸機（B）設計、提供用戶程序與計算機硬件系統(tǒng)的界面（C）管理計算機系統(tǒng)資源（D）高級程序設計語言的編譯器16．最佳適應算法的空閑塊是（C）。（A）按大小遞減順序連在一起（B）按地址由小到大排列（C）按大小遞增順序連在一起（D）按地址由大到小排列17．軟件測試的目標是（A）。（A）找出錯誤（B）驗證計劃（C）得出結果（D）提高效率18．以下哪項不是軟件測試的步驟（B）。（A）單元測試（B）流程測試（C）組裝測試（D）確認測試19．為保證軟件開發(fā)的質(zhì)量，一般不采取的措施是（D）。（A）技術審查（B）管理復審（C）測試（D）監(jiān)督20．結構化分析方法不包括（C）。（A）數(shù)據(jù)流圖（B）數(shù)據(jù)詞典（C）編寫代碼（D）結構化語言三、判斷題（請判斷每個題干是否正確，正確在括弧中打√，錯誤在括弧中打×。）1．（×）線性表的長度是指線性表所占的存儲空間的大小。2．（×）線性表就是順序表。3．（√）棧和隊是運算受限制的線性表。4．（√）若一棵樹中某結點的度為1，則該結點僅有一棵子樹。5．（×）在執(zhí)行排序算法中，出現(xiàn)了排序的關鍵字朝著和最終排序序列位置相反的方向移動，則該算法是不穩(wěn)定的。6．（√）快速排序中，以待排序的n個記錄中的第1個記錄的關鍵字值為基準，將所有記錄分為兩組，該記錄就在這兩組中間，這也是該記錄的最終位置。7．（√）原語在執(zhí)行時是不能中斷的。8．（×）程序并發(fā)執(zhí)行是指同一時刻有兩個以上的程序指令在同一處理器上執(zhí)行。9．（×）緩沖技術是借用一部分外存儲器區(qū)域作為緩沖池。ABCDABCDEFGH四、問答題（請按照題目要求回答問題。）1．一棵二叉樹其中序和后序遍歷為：中序：BDCEAFHG后序：DECBHGFA畫出這棵二叉樹的邏輯結構，并寫出先序遍歷結果。答：邏輯結構為：先序遍歷為：ABCDEFGH設一棵完全二叉樹有20個結點，試問：有多少個葉子結點；有多少個度為2的結點；有多少個結點只有非空左子樹。答：（1）有10個葉子結點（2）有9個度為2的結點（3）有1個結點只有非空左子樹17151715212728303694834054給定一組權值W={8,2,5,3,2,17,4}，畫出由此生成的哈夫曼樹1717582234412491547請說明分頁管理的優(yōu)缺點是什么？答：優(yōu)點是：①不要求作業(yè)在內(nèi)存中連續(xù)存放，較好的解決了碎片問題。②作業(yè)地址空間不受內(nèi)存的限制，為用戶提供足夠大的存儲空間，更有利于多道程序作業(yè)。缺點是：①要求一定的硬件支持，增加了成本。②系統(tǒng)要增加頁表及其管理程序，因而增加了內(nèi)存的開銷。引入緩沖區(qū)的主要原因是什么？答：①緩解了CPU的高速與I/O設備低速之間速度不匹配的矛盾。②減少了CPU的中斷頻率，降低了CPU中斷訪問時間的限制。③提高了CPU與I/O設備之間的并行性。④提高了資源利用率和系統(tǒng)吞吐量。操作系統(tǒng)的基本功能是什么？答：①處理器管理；②存儲管理；③設備管理；④文件管理；⑤用戶接口。五、算法填空題（根據(jù)算法內(nèi)容，在橫線上填入合適的內(nèi)容，使算法完整。）1．單鏈表的結點類型node定義如下：typedefstructlinknode{intdata;structlinknode*next;}node;輸入一系列整數(shù)，以0標志結束，將這些整數(shù)作為data域建立一個單鏈表的函數(shù)如下：voidcreat(){node*head,*p,*s;intx,cycle=1;head=(node*)malloc(sizeof(node));p=head;while(cycle){scanf("%d",&x);if(x!=0){s=(node*)malloc(sizeof(node));s->data=x;p->next=S;p=s;}elsecycle=0;}head=head->next;p->next=NULL;}《計算機軟件技術基礎》練習題（二）一、填空題（請在每個題目中的橫線上填上準確的內(nèi)容。）時間復雜度是以算法中最大的語句來衡量的。2．線性表的主要運算有、刪除、查找和排序。3．在線性表的順序存儲結構中，插入或刪除一個數(shù)據(jù)元素時，平均需要移動表中元素。4．向量的存儲空間是分配的，而線性鏈表的存儲空間是在執(zhí)行過程中動態(tài)分配的。5．在隊中，允許插入的一端稱為隊尾，允許刪除的一端稱為。6．樹中結點的最大層次數(shù)稱為樹的。7．深度為h的二叉樹中至多含有個結點。8．圖的常用存儲結構有鄰接矩陣和。9．實現(xiàn)圖的遍歷有和廣度優(yōu)先搜索兩種方法。10．二叉排序樹中，其左子樹上所有結點的數(shù)據(jù)值均根結點的數(shù)據(jù)值。11．通道是一種特殊的，它使外部設備和內(nèi)存之間能直接進行數(shù)據(jù)傳輸，而與中央處理機無關。12．“多道”是指在計算機同時可以存放多道作業(yè)。13．并發(fā)是指兩個或多個事件在同一內(nèi)發(fā)生。14．一個目標程序所占有的地址范圍稱為。15．在實存儲管理中，分區(qū)分配有固定分區(qū)分配和兩種形式。16．主存中空閑區(qū)分配算法有算法、最佳適應算法和最差適應算法三種分配策略。17．分段管理中的地址結構包括段號和兩項。18．局部性概念包括時間局部性和。19．進程調(diào)度又稱或微觀調(diào)度。20．按設備的使用性質(zhì)分類，設備可分為、共享設備和虛擬設備。21．設備分配算法有和優(yōu)先數(shù)法兩種。22．文件的邏輯結構是從的角度看到的文件組織形式。23．文件的物理結構是指一個邏輯文件在上的存放形式。24．常見的文件物理結構有、鏈接結構和索引結構三種。25．軟件開發(fā)過程模型主要有瀑布模型和模型兩類。26．軟件測試的步驟一般分為、組裝測試和確認測試三步。27．設備處理程序的最基本任務是使與處理機之間進行通信。28．測試方案包括預定測試的功能、應該輸入的測試數(shù)據(jù)和。29．為保證軟件的質(zhì)量，主要采取的措施有、管理復審和測試。30．軟件開發(fā)人員的組織結構模式通常有、按職能劃分和矩陣模式三種。二、單項選擇題（請在每個小題的四個備選答案中選擇一個正確答案的序號填入題干的括弧中，多填不得分。）以下程序段的空間復雜度為（）。fori=1tonforj=1tonfork=1tonx←x+1end(k)end(j)end(i)（A）O(n)（B）O(1)（C）O(n2)（D）O(n3)2．空間復雜度可以衡量算法中（）的多少。（A）輔助空間單元（B）原始數(shù)據(jù)占用空間（C）程序占用空間（D）使用變量3．以下對線性表的描述，正確的是（）。棧是先進先出的線性表隊是先進后出的線性表線性鏈表可以隨機存取向量的存儲空間是靜態(tài)分配的4．在單鏈表中，若p指針所指結點不是最后結點，刪除p之后所指的結點，則需執(zhí)行（）。q←next(p);next(p)←next(q);RET(q)q←next(p);RET(q);next(p)←next(q)next(p)←next(q);q←next(p);RET(q)next(p)←next(q);RET(q);q←next(p)5．深度為h且含有（）個結點的二叉樹為滿二叉樹。（A）2h（B）2h-1（C）2h+1（D）2h-16．以下二叉樹的帶權路徑長度為（）。（A）35（B）31（C）42（D）46bbacd75427．下圖的廣度優(yōu)先遍歷序列正確的是（）。（A）V2→V1→V5→V3→V4→V6（B）V2→V1→V5→V3→V6→V4（C）V2→V1→V3→V5→V4→V6（D）V2→V1→V3→V5→V6→V411253468．在一個長度為n的順序表中刪除第i個數(shù)據(jù)元素（0≤i≤n-1）時，需向前移動（）個元素。（A）n-i（B）n-i+1（C）n-i-1（D）i9．一組記錄的關鍵字為{46,79,56,38,40,84}，則利用快速排序的方法，以第一個記錄為基準得到的一趟排序結果為（）。（A）38,40,46,56,79,84（B）40,38,46,79,56,84（C）40,38,46,84,56,79（D）40,38,46,56,79,8410．操作系統(tǒng)是一種（）。（A）應用軟件（B）系統(tǒng)軟件（C）軟件包（D）通用軟件11．下面對臨界區(qū)的論述中，正確的是（）。（A）臨界區(qū)是指進程中用于實現(xiàn)進程互斥的那段代碼（B）臨界區(qū)是指進程中用于實現(xiàn)進程同步的那段代碼（C）臨界區(qū)是指進程中用于訪問共享資源的那段代碼（D）臨界區(qū)是指進程中訪問臨界資源的那段代碼12．允許多個用戶將多個作業(yè)交給計算機集中處理的操作系統(tǒng)稱為（）。（A）批處理操作系統(tǒng)（B）分時操作系統(tǒng)（C）實時操作系統(tǒng)（D）網(wǎng)絡操作系統(tǒng)13．引入多道程序設計的主要目的為（）。（A）提高實時響應速度（B）充分利用處理機（C）有利于代碼共享（D）減少存儲碎片14．以下哪項是一級目錄的優(yōu)點（）。（A）實現(xiàn)簡單（B）訪問速度慢（C）文件名不能相重（D）主要用于單用戶系統(tǒng)中15．以下哪一項不是軟件開發(fā)中的系統(tǒng)分析與設計方法（）。（A）結構化系統(tǒng)方法（B）理論化系統(tǒng)方法（C）快速原型方法（D）面向?qū)ο蠓椒?6．以下哪一項不是面向?qū)ο蠓椒ǖ膬?yōu)點（）。（A）可重用性（B）可維護性（C）可虛擬性（D）表示方法的一致性17．高質(zhì)量的軟件文檔不應該取決于（）。（A）精確性（B）概括性（C）清晰性（D）完整性18．軟件維護不包括（）。（A）改正性維護（B）適應性維護（C）完善性維護（D）運行平臺維護19．需求分析階段確定系統(tǒng)的要求時不包括（）。（A）系統(tǒng)模糊要求（B）系統(tǒng)功能要求（C）系統(tǒng)性能要求（D）系統(tǒng)運行要求20．軟件危機出現(xiàn)在（）。（A）20世紀50年代末（B）20世紀60年代末（C）20世紀70年代末（D）20世紀80年代末三、判斷題（請判斷每個題干是否正確，正確在括弧中打√，錯誤在括弧中打×。）1．（）線性表惟一的存儲形式是鏈表。2．（）線性表只能借助于指針和動態(tài)變量來實現(xiàn)。3．（）棧為空的情況下，不能作出棧的操作，否則產(chǎn)生下溢出。4．（）在循環(huán)隊列中，若尾指針r大于頭指針f，則其元素數(shù)為r-f。5．（）二叉樹只能采用二叉鏈表來存儲。6．（）理想情況下，在散列表中查找一個元素的時間復雜度為O(1)。7．（）文件目錄是由文件控制塊組成的。8．（）請求分頁存儲管理系統(tǒng)若把頁面的大小增加一倍，則缺頁中斷次數(shù)會減少一半。9．（）如果信號量當前值是－4，表示系統(tǒng)中在該信號量上有4個等待進程。10．（）銀行家算法是用于防止進程死鎖的。四、問答題（請按照題目要求回答問題。）1．將下列的一般樹化為二叉樹。AABCDEFGIJLMK2．有一組關鍵字序列為{38,19,65,13,97,49,41,95,1,73}，采用冒泡排序方法由小到大排序，請寫出每趟結果。3．如下所示有向圖：（1）寫出每一結點的入度和出度各為多少；（2）寫出上圖的鄰接矩陣。11235644．請說明分段管理的優(yōu)缺點是什么？5．什么是死鎖？產(chǎn)生死鎖的原因和必要條件是什么？6．請說明SPOOLing系統(tǒng)的組成？五、算法填空題（根據(jù)算法內(nèi)容，在橫線上填入合適的內(nèi)容，使算法完整。）1．按先序遍歷序列建立二叉樹的二叉鏈表，已知先序序列為：FCA▲▲DB▲▲▲E▲GH▲▲P▲▲其中▲表示結束符。二叉鏈表的生成：輸入：二叉鏈表的頭指針BT為空；根結點標志k＝0。輸出：二叉鏈表的頭指針BT。#include"stdio.h”#include"stdlib.h”structbtnode{intd；structbtnode*lchild；structbtnode*rchild；}；structbtnode*creatbt(bt，k)structbtnode*bt；intk；{intb；structbtnode*p，*t；printf("inputb：")；scanf(“%d”，&b)；if(b!＝0){p＝；p－>d＝b；p－>lchild＝NULL；p－>rchild＝NULL；if(k＝＝0)t＝p；if(k＝＝1)bt－>lchild＝p；if(k＝＝2)bt－>rchild＝p；；；}return(t)}《計算機軟件技術基礎》練習題（三）一、填空題（請在每個題目中的橫線上填上準確的內(nèi)容。）線性表的結構特點是數(shù)據(jù)元素之間是關系。在線性表的順序存儲結構中，插入或刪除一個數(shù)據(jù)元素時，平均需要移動表中數(shù)據(jù)元素。3．在隊中，允許插入的一端稱為，允許刪除的一端稱為隊頭。4．C語言中數(shù)組是按優(yōu)先順序存放的。5．二叉樹的深度為樹中結點的最大。6．圖的常用存儲結構有和鄰接表。7．多道系統(tǒng)是指在計算機同時可以容納多道作業(yè)，并且可以并發(fā)的運行這些作業(yè)。8．虛擬存儲技術有、分段存儲管理和段頁存儲管理。9．實存儲管理中，分區(qū)分配有和可變分區(qū)分配兩種形式。10．常見的文件物理結構有順序結構、和索引結構三種。11．網(wǎng)絡層數(shù)據(jù)的傳輸單位是或包。12．路由器除了提供橋接功能外，還提供復雜的和管理。13．Internet的C類地址用于大量的小型網(wǎng)，地址的最高3位為。14．軟件開發(fā)過程模型主要有模型和漸增模型兩類。15．軟件測試的步驟一般分為單元測試、和確認測試三步。二、單項選擇題（請在每個小題的四個備選答案中選擇一個正確答案的序號填入題干的括弧中，多填不得分。）1．以下程序段的時間復雜度為（）。fori=1tonforj=1tonx←x+1end(j)end(i)（A）O(n)（B）O(1)（C）O(n2)（D）O(n3)2．以下對線性表的描述，正確的是（）。棧是先進先出的線性表隊是先進后出的線性表向量的存儲空間是靜態(tài)分配的線性鏈表可以隨機存取3．在單鏈表中，若p指針所指結點不是最后結點，刪除p之后所指的結點，則需執(zhí)行（）。（A） q←next(p);RET(q);next(p)←next(q)（B） q←next(p);next(p)←next(q);RET(q)（C） next(p)←next(q);q←next(p);RET(q)（D） next(p)←next(q);RET(q);q←next(p)4．一個長度為n的順序表中在第i（0≤i≤n）個數(shù)據(jù)元素前插入一個數(shù)據(jù)時，需向后移動（）個元素。（A）n-i（B）n-i+1（C）i（D）n-i-15．一組記錄的關鍵字為{46,79,56,38,40,84}，則利用快速排序的方法，以第一個記錄為基準得到的一趟排序結果為（）。（A）40,38,46,56,79,84（B）40,38,46,79,56,84（C）40,38,46,84,56,79（D）38,40,46,56,79,846．操作系統(tǒng)是一種（）。（A）應用軟件（B）工具軟件（C）系統(tǒng)軟件（D）通用軟件7．允許多個用戶以交互方式使用計算機的操作系統(tǒng)稱為（）。（A）批處理操作系統(tǒng)（B）分時操作系統(tǒng)（C）實時操作系統(tǒng)（D）網(wǎng)絡操作系統(tǒng)8．廣域網(wǎng)與廣域網(wǎng)之間連接時需用（）。（A）轉(zhuǎn)發(fā)器（B）網(wǎng)橋（C）路由器（D）網(wǎng)關9．TCP/IP協(xié)議的最低層是（）。（A）應用層（B）傳輸層（C）網(wǎng)間網(wǎng)層（D）網(wǎng)絡接口層10．高質(zhì)量的軟件文檔不應該取決于（）。（A）精確性（B）清晰性（C）概括性（D）完整性三、判斷題（請判斷每個題干是否正確，正確在括弧中打√，錯誤在括弧中打×。）1．（）線性表只能借助于指針和動態(tài)變量來實現(xiàn)。2．（）向量是線性表唯一的一種存儲形式。3．（）在循環(huán)隊列中，若尾指針r大于頭指針f，則其元素數(shù)為r-f。4．（）棧為空的情況下，不能作出棧的操作，否則產(chǎn)生下溢出。5．（）二叉樹只能采用二叉鏈表來存儲。6．（）單級文件目錄也可以允許文件重名。7．（）計算機系統(tǒng)發(fā)生死鎖純粹是由于系統(tǒng)資源不足造成的。8．（）如果信號量當前值是－4，表示系統(tǒng)中在該信號量上有5個等待進程。9．（）在域名系統(tǒng)中，樹根是唯一的中央管理機構。10．（）大型軟件的開發(fā)由于軟件計劃不周可能造成一半以上的項目失敗。四、算法分析應用題1．一棵二叉樹其中序和后序遍歷為：中序：DGBAHECF后序：GDBHEFCA畫出這棵二叉樹的邏輯結構，并寫出先序遍歷結果。2．給定一組元素{35,25,10,58,90,15,21,77,50}，畫出由此生成的二叉排序樹。3．有一組關鍵字序列為{9,15,1,10,8,6}，采用簡單選擇排序方法由小到大排序，請寫出每趟排序結果。（6分）4．如下所示有向圖：（6分）（1）寫出每一結點的入度和出度各為多少；（2）寫出下圖的鄰接表。1124536五、簡答題1．請說明分段管理的優(yōu)缺點各是什么？2．請說明什么是進程的三種基本狀態(tài)？并畫圖說明進程各狀態(tài)之間的轉(zhuǎn)換過程？3．請說明引入緩沖技術的根本原因是什么？4．簡述計算機網(wǎng)絡協(xié)議采取層次結構的好處？5．如果詳細劃分軟件生命期的話，具體來說有哪七個階段？《計算機軟件技術基礎》練習題（四）一、填空題（請在每個題目中的橫線上填上準確的內(nèi)容。）向量的結構特點是數(shù)據(jù)元素之間是關系。在單向線性鏈表存儲結構中，查找一個數(shù)據(jù)元素時，只能從開始。3．在棧中，只能從進行插入或刪除操作。4．數(shù)組可以按或按列優(yōu)先順序存放。5．在樹結構中，沒有前趨的結點稱為結點。6．用矩陣表示的圖的存儲結構稱為。7．計算機硬件部分包括、存儲器、輸入輸出設備和各種通信設備。8．分時系統(tǒng)是指多個用戶共享同一臺計算機，系統(tǒng)將CPU的輪流分配給多個用戶。9．虛存儲管理中，主要有和分段及段頁式存儲形式。10．進程的三種基本狀態(tài)有就緒狀態(tài)、和阻塞狀態(tài)。11．物理層數(shù)據(jù)的傳輸單位是。12．因特網(wǎng)的網(wǎng)絡協(xié)議主要有協(xié)議。13．頂層域名如果是EDU的話，則為機構。14．為了保證軟件的質(zhì)量，主要通過、管理復審和測試來實施。15．軟件測試有和白盒測試兩類方法。二、單項選擇題（請在每個小題的四個備選答案中選擇一個正確答案的序號填入題干的括弧中，多填不得分。）1．在數(shù)據(jù)結構中，從邏輯上可以把數(shù)據(jù)結構分成（）。（A）動態(tài)結構和靜態(tài)結構（B）內(nèi)部結構和外部結構（C）線性結構和非線性結構（D）緊湊結構和非緊湊結構2．有一顆具有n個結點的k叉樹，則有nk個指針域，其中有用的指針域為（）個。（A）n（B）nk-1（C）n-1（D）nk3．對有序表(18,20,25,34,48,62,74,85)用對分查找法查找74，查找成功時所需的比較次數(shù)為（）次。（A）2（B）3（C）4（D）54．一組記錄的關鍵字為{3,8,5,9,7,6,2}，則利用冒泡排序的方法，經(jīng)過第一次掃描得到的排序結果為（）。（A）3,5,8,7,6,2,9（B）3,8,5,7,6,2,9（C）3,5,6,7,8,2,9（D）2,3,5,8,7,6,95．操作系統(tǒng)的主要功能是管理計算機系統(tǒng)中的（）。（A）程序和數(shù)據(jù)（B）作業(yè)（C）硬件和軟件資源（D）進程6．批處理系統(tǒng)的主要缺點是（）。（A）CPU利用率低（B）不能并發(fā)執(zhí)行（C）缺少交互性（D）以上都不是7．TCP/IP協(xié)議的最高層是（）。（A）應用層（B）傳輸層（C）網(wǎng)間網(wǎng)層（D）網(wǎng)絡接口層8．路由器是（）。（A）物理層中繼系統(tǒng)（B）數(shù)據(jù)鏈路層中繼系統(tǒng)（C）網(wǎng)絡層中繼系統(tǒng)（D）網(wǎng)絡層以上中繼系統(tǒng)9．軟件測試的目標是（）。（A）找出錯誤（B）驗證計劃（C）得出結果（D）提高效率10．軟件需求分析應包括（）。（A）用戶需求（B）硬件需求（C）軟件需求（D）以上全是三、判斷題（請判斷每個題干是否正確，正確在括弧中打√，錯誤在括弧中打×。）1．（）線性表的長度是指線性表所占的存儲空間的大小。2．（）棧和隊是運算受限制的線性表。3．（）若一棵樹中某結點的度為1，則該結點僅有一棵子樹。4．（）棧為滿的情況下，不能作入棧的操作，否則產(chǎn)生下溢出。5．（）原語在執(zhí)行時是不能中斷的。6．（）緩沖技術是借用一部分外存儲器區(qū)域作為緩沖池。7．（）兩級以上文件目錄就可以允許文件重名。8．（）網(wǎng)絡操作系統(tǒng)是將連入網(wǎng)絡的所有計算機和各種軟硬件資源當成一個整體。9．（）遠程登錄Telnet無法實現(xiàn)與另外的計算機進行交互式會話。10．（）軟件工程是一門集程序設計方法、工具和管理的科學。四、算法分析應用題1．設一棵完全二叉樹有50個結點，試問：有多少個葉子結點；有多少個度為2的結點；有多少個結點只有非空左子樹。2．給定一組元素{10,6,15,20,18,30}，畫出由此生成的二叉排序樹。（6分）3．給定一組權值W={8,15,3,2,20,4}，畫出由此生成的哈夫曼樹（左分支結點值小于右分支結點值）。（6分）4．CQ[0:9]為一循環(huán)隊列，初態(tài)front=rear=0，畫出下列操作后隊的頭、尾指示器狀態(tài)（5分）(1)a,b,c,d,e入隊(2)a,b出隊(3)f,g,h,i,j入隊(4)c出隊(5)k,l,m,n,o入隊五、簡答題1．簡述虛擬地址空間受哪些條件制約？實現(xiàn)虛擬存儲技術需要解決哪些問題？2．簡述操作系統(tǒng)的基本功能是什么？3．簡述開放系統(tǒng)互聯(lián)參考模型OSI共分為哪七個層次？4．軟件工程按軟件開發(fā)活動步驟應該制定哪些計劃？《計算機軟件技術基礎》練習題（二）參考答案一、填空題1.頻度2.插入3.一半4.靜態(tài)5.隊頭6.深度7.2h-18.鄰接表9.深度優(yōu)先搜索10.小于11.處理機12.內(nèi)存中13.時間間隔14.地址空間15.可變分區(qū)分配16.首次適應17.段內(nèi)地址18.空間局部性19.低級調(diào)度20.獨享設備21.先請求先服務22.用戶23.外存儲器24.順序結構25.漸增26.單元測試27.外部設備28.預期結果29.技術審查30.按課題劃分二、單項選擇題1.B2.A3.D4.A5.D6.A7.A8.C9.D10.B11.D12.A13.B14.A15.B16.C17.B18.D19.A20.B三、判斷題1.×2.×3.√4.√5.×6.√7.√8.×9.√10.×四、問答題ABABCDEFGIJLMK2.答：38,19,65,13,97,49,41,95,1,7319,38,13,65,49,41,95,1,73,9719,13,38,49,41,65,1,73,95,9713,19,38,41,49,1,65,73,95,9713,19,38,41,1,49,65,73,95,9713,19,38,1,41,49,65,73,95,9713,19,1,38,41,49,65,73,95,9713,1,19,38,41,49,65,73,95,971,13,19,38,41,49,65,73,95,973.答：入度出度①30②22③12④22⑤21⑥14鄰接矩陣如下：0000001001000100010010101000001101104.答：分段管理的優(yōu)點是：①便于程序模塊化處理。②便于處理變化的數(shù)據(jù)。③便于共享分段。分段管理的缺點是：增加了硬件成本，地址變換花費了CPU時間，增加了附加的存儲空間。②分段尺寸的大小受主存限制，會出現(xiàn)碎片問題。5.答：死鎖是指多個并發(fā)執(zhí)行的進程由于競爭資源不當所產(chǎn)生的一種僵持狀態(tài)，處于這種僵持狀態(tài)時，如無外力作用，所有進程都將無法再向前推進。產(chǎn)生死鎖的原因是：①系統(tǒng)資源不足。②進程推進的順序不當。產(chǎn)生死鎖的必要條件是：所用資源是非共享的。進程請求新資源時，繼續(xù)占用已分配到的資源。一個進程占有的資源不能被其他進程強行搶占。④一個進程獲得的資源同時被另一個進程所請求，從而形成一個進程資源的循環(huán)鏈。6.答：①輸入井和輸出井②輸入緩沖區(qū)和輸出緩沖區(qū)③輸入進程和輸出進程五、算法填空題1.答：第一空：(structbtnode*)malloc(sizeof(structbtnode))第二空：creatbt(p，1)第三空：creatbt(p，2)《計算機軟件技術基礎》練習題（三）參考答案一、填空題1.線性2.一半3.隊尾4.行5.層次數(shù)6.鄰接矩陣7.內(nèi)存