軟件技術(shù)基礎(chǔ)試題庫

1、軟件技術(shù)基礎(chǔ)試題庫軟件技術(shù)基礎(chǔ)（21次）一、是非判斷題（10分）1應(yīng)用程序在執(zhí)行過程中，需要通過打印機(jī)輸出數(shù)據(jù)時，一般先形成一個打印作業(yè)，將其存放在硬盤中的一個指定隊列中。當(dāng)打印機(jī)空閑時，就會按先來后服務(wù)的方式從中取出待打印的作業(yè)進(jìn)行打印。（F）2若無進(jìn)程處于運(yùn)行狀態(tài)，則就緒隊列和等待隊列均為空。（F）3多道程序設(shè)計是指在一臺處理機(jī)上并發(fā)運(yùn)行多個程序。(T)4黑盒法是軟件測試方法中的靜態(tài)測試方法之一。(T)5軟件的詳細(xì)設(shè)計就是要編寫出具體的程序。(F)6軟件生命周期中花費(fèi)最多的階段是軟件維護(hù)。(T)7WINDOWS是單用戶多任務(wù)操作系統(tǒng)，UNIX是多用戶多任務(wù)操作系統(tǒng)。(T)8進(jìn)程把程序作為它

2、的運(yùn)行實體，沒有程序也就沒有進(jìn)程。(T)9在結(jié)構(gòu)化分析中，用于是描述加工邏輯的主要工具有三程，即：結(jié)構(gòu)化語言、判斷表和判定樹。(T)10作業(yè)調(diào)度程序從后備隊列中選一個作業(yè)裝入主存后，決定能否占用處理機(jī)的是設(shè)備調(diào)度程序。(F)二單項選擇題（5分）1交換技術(shù)是在（）之間交換程序和數(shù)據(jù)。A主內(nèi)存與CPUBCPU與外設(shè)C主內(nèi)存與外存D外存與CPU2以下的工具中哪個不是軟件詳細(xì)設(shè)計中使用的工具（）A數(shù)據(jù)流圖BN-S圖CPDA圖DPDL語言注：軟件開發(fā)階段包括需求分析、總體設(shè)計、詳細(xì)設(shè)計、編碼和測試五個階段。其中需求分析階段常用的工具是數(shù)據(jù)流程圖和數(shù)據(jù)字典。3任何兩個并發(fā)進(jìn)程之間（）A一定存在互斥關(guān)系B一

3、定存在同步關(guān)系C一定彼此獨(dú)立無關(guān)D可能存在同步或互斥關(guān)系4進(jìn)程從運(yùn)行狀態(tài)進(jìn)入就緒狀態(tài)的原因可能是（）A被選中占有處理機(jī)B等待某一事件C等待的事件已發(fā)生D時間片用完5算法指的是（）A計算機(jī)程序B解決問題的有限運(yùn)算序列C排序算法D解決問題的計算方法軟件技術(shù)基礎(chǔ)模擬試題（第二十次省統(tǒng)考）一、 是非判斷題（正確選填A(yù)，錯誤選填B）（每小題1分，共10分）1、數(shù)據(jù)元素是數(shù)據(jù)的基本單位，數(shù)據(jù)項是數(shù)據(jù)的最小單位。（）2、棧是特殊的線性表，須用一組地址連續(xù)的存儲單元來存儲其元素。（）3、引入虛擬存儲技術(shù)后，邏輯內(nèi)存總?cè)萘渴怯傻刂房偩€的位置確定的。（）4、編譯程序是一種常用應(yīng)用軟件。（）5、順序文件和鏈接文件的

4、長度都可以動態(tài)變化。（）6、在文件系統(tǒng)中采用目錄管理文件。（）7、允許多用戶在其終端上同時交互地使用計算機(jī)的操作系統(tǒng)稱為實時系統(tǒng)。（）8、程序、數(shù)據(jù)、和進(jìn)程控制塊是構(gòu)成一個進(jìn)程的三要素。（）9、黑盒測試時，既要考慮程序的內(nèi)部邏輯結(jié)構(gòu)又要考慮其外部特性。（）10、軟件的總體設(shè)計和詳細(xì)設(shè)計都要用PAD圖形工具。（）(參考答案：110：ABABBABABB)二、 單項選擇題：（每小題1分，共5分）1、允許用戶把若干作業(yè)提交計算機(jī)系統(tǒng)集中處理的操作系統(tǒng)稱為（）。A分時操作系統(tǒng)B實時操作系統(tǒng)C網(wǎng)絡(luò)操作系統(tǒng)D批處理操作系統(tǒng)2、分配到必要資源并獲得了處理機(jī)時的進(jìn)程的狀態(tài)稱為（）。A就緒狀態(tài)B執(zhí)行狀態(tài)C等待狀

5、態(tài)D阻塞狀態(tài)3、利用通道技術(shù)可以在（）之間直接交換數(shù)據(jù)。A內(nèi)存與CPUBCPU與外設(shè)C內(nèi)存與外設(shè)D內(nèi)存、CPU和外設(shè)三者4、以下的準(zhǔn)則中哪個不是軟件設(shè)計的準(zhǔn)則（）。A編程語言選擇準(zhǔn)則B信息屏蔽準(zhǔn)則C結(jié)構(gòu)化和模塊化準(zhǔn)則D抽象準(zhǔn)則5、有一數(shù)列：97657613294958經(jīng)過一趟排序后得到：65971376294958請問使用的是何種排序方法？（）A簡單插入排序B冒泡排序C2路歸并排序D快速排序(參考答案：DBCAC)軟件技術(shù)基礎(chǔ)模擬試題（第十九次省統(tǒng)考）一、 是非判斷題（正確選填A(yù)，錯誤選填B）（每小題1分，共10分）1、在目前，用于保證軟件質(zhì)量的主要手段是進(jìn)行軟件測試。（）注：軟件測試的目的：

6、發(fā)現(xiàn)錯誤而執(zhí)行程序的過程2、使用DMA方式傳送數(shù)據(jù)期間不需要CPU干預(yù)。（）注：DMA直接存儲器訪問，直接依靠硬件實現(xiàn)主存與外設(shè)之間的數(shù)據(jù)直接傳輸，傳輸過程 本身不需CPU程序干預(yù)3、線性順序隊列會產(chǎn)生“假溢出”，而線性循環(huán)隊列則不會。（）4、對同一種算法，用高級語言編寫的程序比用低級語言編寫的程序運(yùn)行速度快。（）5、在線性表中，數(shù)據(jù)的存儲方式有順序和鏈接兩種。（）6、進(jìn)程由程序塊、文件控件塊和數(shù)據(jù)塊三部分組成。（）7、在面向?qū)ο蟮某绦蛟O(shè)計中，派生類只能從一個基類產(chǎn)生。（）8、操作系統(tǒng)是用戶和硬件的接口。（）9、個人計算機(jī)中可配置的最大內(nèi)存容量受地址總線位數(shù)的限制。（）10、軟件維護(hù)中最困難的

7、問題是軟件配置不全。（）(參考答案：110：A、A、A、B、B B、A、A、A、B)二、 單項選擇題：（每小題1分，共5分）1、在排序法中，從未排序序列中依次取出元素，與已排序序列中的元素作比較，將其放入已排序序列的正確位置稱為（）。A選擇排序B快速排序C插入排序D冒泡排序2、有X、Y、Z三個元素依次入棧，不可能的出棧順序是（）。AZ，Y，XBZ，X，YCY，X，ZDX，Y，Z3、進(jìn)程的狀態(tài)是可以轉(zhuǎn)換的，而以下哪個狀態(tài)轉(zhuǎn)換是不可能的（）。A就緒狀態(tài)執(zhí)行狀態(tài)B執(zhí)行狀態(tài)就緒狀態(tài)C阻塞狀態(tài)就緒狀態(tài)D等待狀態(tài)執(zhí)行狀態(tài)4、線性鏈表的地址（）。A必須連續(xù)B部分地址必須連續(xù)C一定不連續(xù)D連續(xù)與否均可以5、在

8、軟件測試中，（）主要分析程序的內(nèi)部結(jié)構(gòu)。A白盒法B黑盒法C因果圖法D錯誤推測法(參考答案：15：C、B、D、D、A)軟件技術(shù)基礎(chǔ)模擬試題（第十六次省統(tǒng)考）一、是非判斷題（正確選填A(yù)，錯誤選填B）（每小題1分，共10分）1、軟件測試的目的是為了發(fā)現(xiàn)軟件中的全部錯誤。（）2、在樹形結(jié)構(gòu)中，每一層的數(shù)據(jù)元素只和上一層中的一個元素相關(guān)。（）3、所謂共享設(shè)備是指可以分時地為多個作業(yè)服務(wù)的設(shè)備，打印機(jī)屬于共享設(shè)備。（）4、面向?qū)ο蟮某绦蛟O(shè)計的基本做法是將數(shù)據(jù)及對數(shù)據(jù)的操作放在一起，作為一個相互依存、不可分割的整體來處理。（）5、高級程序設(shè)計語言C+是C語言的發(fā)展和擴(kuò)充，它們都是結(jié)構(gòu)化程序設(shè)計語言。（）6、

9、文件管理系統(tǒng)只負(fù)責(zé)對系統(tǒng)文件和用戶文件的組織和管理，它不負(fù)責(zé)對文件進(jìn)行保護(hù)和故障恢復(fù)。（）7、樹形結(jié)構(gòu)是用于描述數(shù)據(jù)元素之間的層次關(guān)系的一種線性數(shù)據(jù)結(jié)構(gòu)。（）8、進(jìn)程的建立可以通過作業(yè)調(diào)度來實現(xiàn)。（）9、進(jìn)程間由于共享資源而產(chǎn)生的制約關(guān)系稱為進(jìn)程同步。（）10、緩沖池是由多個緩沖區(qū)組成，一個系統(tǒng)可有一個或幾個緩沖池，一個緩沖池可有多個緩沖區(qū)。（）(參考答案：110：BABABBBABA)二、單項選擇題：（每小題1分，共5分）1、不屬于面向?qū)ο蟪绦蛟O(shè)計的主要特性的是（）。A封裝性B重載與多態(tài)性C數(shù)據(jù)的完整性D繼承性2、引入緩沖區(qū)的主要目的是（）。A節(jié)省內(nèi)存B提高CPU的利用率C提高I/O設(shè)備的效

10、率D改善CPU和I/O設(shè)備間速度不匹配的情況3、要進(jìn)行二分查找，則線性表（）。A必須以順序方式存儲B必須以鏈接方式存儲C必須以隊列方式存儲D必須以順序方式存儲，且數(shù)據(jù)元素有序。4、在結(jié)構(gòu)化程序設(shè)計中，應(yīng)盡量避免使用（）。A條件語句B循環(huán)語句C轉(zhuǎn)向語句D輸出語句5、在以下所列中不是虛擬設(shè)備技術(shù)的是（）。A多窗口技術(shù)B脫機(jī)輸出C虛擬內(nèi)存D中斷處理(參考答案：CDDCD)軟件技術(shù)基礎(chǔ)試題庫課程名稱：軟件技術(shù)基礎(chǔ) 適用專業(yè)：軟件技術(shù)、計算機(jī)應(yīng)用、網(wǎng)絡(luò)、信息等計算機(jī)相關(guān)專業(yè)第一章 概述第二章 數(shù)據(jù)結(jié)構(gòu)一、單項選擇題1若長度為n的線性表采用順序存儲結(jié)構(gòu)，刪除它的第i數(shù)據(jù)元素之前，需要先依次向前移動_個數(shù)據(jù)

11、元素。( )A. n-iB. n+iC. n-i-1D. n-i+1答案：A2在單鏈表中，已知q指的結(jié)點(diǎn)是p指的結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，若在q和p指的結(jié)點(diǎn)之間插入一個由s指的結(jié)點(diǎn)，則需執(zhí)行_。( )A. link(s)link(p)，link(p)sB. link(q)s，link(s)pC. link(p)link(s)，link(s)pD. link(p)s，link(s)q答案：B3高度為h(h0) 的二叉樹最少有_個結(jié)點(diǎn)。（ ）A. hB. h-1 C. h+1D. 2h答案：A4n個頂點(diǎn)的帶權(quán)無向連通圖的最小生成樹包含 _ 個頂點(diǎn)。（）A.n-1 B.n C.n/2 D.n+1答案：B5

12、采用拉鏈法解決沖突的散列表中，查找的平均查找長度( )。A. 直接與關(guān)鍵字個數(shù)有關(guān) B. 直接與裝填因子 a 有關(guān) C. 直接與表的容量有關(guān) D. 直接與散列函數(shù)有關(guān)答案：D6樹型結(jié)構(gòu)最適合用來描述( )A.有序的數(shù)據(jù)元素 B.無序的數(shù)據(jù)元素C.數(shù)據(jù)元素之間的具有層次關(guān)系的數(shù)據(jù)D.數(shù)據(jù)元素之間沒有關(guān)系的數(shù)據(jù)答案：C7若二叉樹中度為2的結(jié)點(diǎn)有15個，度為1的結(jié)點(diǎn)有10個_個葉結(jié)點(diǎn)。( )A.25 B.10C.16 D.41答案：C8若深度為6的完全二叉樹的第6層有3個葉結(jié)點(diǎn)，則該二叉樹一共有_個結(jié)點(diǎn)。( )A.32 B.33C.34 D.25答案：C9若某完全二叉樹的深度為h，則該完全二叉樹中至

13、少有_個結(jié)點(diǎn)。( )A.2h B.2h-1C.2h-2D.2h-1+1答案：C10在非空二叉樹的中序遍歷序列中，二叉樹的根結(jié)點(diǎn)的左邊應(yīng)該( )A.只有左子樹上的所有結(jié)點(diǎn)B.只有左子樹上的部分結(jié)點(diǎn)C.只有右子樹上的所有結(jié)點(diǎn) D.只有右子樹上的部分結(jié)點(diǎn)答案：A11下面關(guān)于哈夫曼樹的說法，不正確的是( )A.對應(yīng)于一組權(quán)值構(gòu)造出的哈夫曼樹一般不是唯一的B.哈夫曼樹具有最小帶權(quán)路徑長度C.哈夫曼樹中沒有度為1的結(jié)點(diǎn)D.哈夫曼樹中除了度為1的結(jié)點(diǎn)外，還有度為2的結(jié)點(diǎn)和葉結(jié)點(diǎn)答案：D12數(shù)據(jù)結(jié)構(gòu)是一門研究計算機(jī)中 對象及其關(guān)系的學(xué)科。( )A. 數(shù)值運(yùn)算B.非數(shù)值運(yùn)算C.集合D.非集合答案：B13數(shù)據(jù)結(jié)構(gòu)

14、的定義為(K，R)，其中K是 的集合。( )A.算法B.數(shù)據(jù)元素C.數(shù)據(jù)操作D.邏輯結(jié)構(gòu)答案：B14算法分析的目的是_。( )A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中輸入和輸出的關(guān)系C.分析算法的效率以求改進(jìn)D.分析算法的易懂性和文檔性答案：C15數(shù)據(jù)的不可分割的基本單位是 。( )A.元素B.結(jié)點(diǎn)C.數(shù)據(jù)類型D.數(shù)據(jù)項答案：D16 是具有相同特性數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。( )A.數(shù)據(jù)符號B.數(shù)據(jù)對象C.數(shù)據(jù)D.數(shù)據(jù)結(jié)構(gòu)答案：B17數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的 及它們之間的相互聯(lián)系。（ ）A.理想結(jié)構(gòu)、物理結(jié)構(gòu)B.理想結(jié)構(gòu)、邏輯結(jié)構(gòu)C.物理結(jié)構(gòu)、邏輯結(jié)構(gòu)D.抽象結(jié)構(gòu)、邏輯結(jié)構(gòu)答案：C18組成數(shù)據(jù)的

15、基本單位是 。（ ）A.數(shù)據(jù)項B.數(shù)據(jù)類型C.數(shù)據(jù)元素D.數(shù)據(jù)變量答案：C19數(shù)據(jù)在計算機(jī)存儲器內(nèi)表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱為 。（ ）A.存儲結(jié)構(gòu)B.邏輯結(jié)構(gòu)C.順序存儲結(jié)構(gòu)D.鏈?zhǔn)酱鎯Y(jié)構(gòu)答案：C20算法指的是 。（ ）A計算機(jī)程序B解決問題的計算方法C排序算法D解決問題的有限運(yùn)算序列答案：D21. 由_組成的集合是一個數(shù)據(jù)對象。( )A.不同類型的數(shù)據(jù)項B.不同類型的數(shù)據(jù)元素C.相同類型的數(shù)據(jù)項D.相同類型的數(shù)據(jù)元素答案：D22關(guān)于順序存儲的敘述中,哪一條是不正確的。( )A.存儲密度大B.邏輯上相鄰的節(jié)點(diǎn)物理上不必鄰接C.可以通過計算直接確定第i個節(jié)點(diǎn)的位置D.插入

16、、刪除操作不方便答案：B23一個向量第一個元素的存儲地址是 100 ，每個元素的長度為 2 ，則第 5 個元素的地址是 。（ ）A.110B.108C.100D.120 答案：B24已知一個順序存儲的線性表，設(shè)每個結(jié)點(diǎn)需要占m個存儲單元，若第一個結(jié)點(diǎn)的地址為da，則第i個結(jié)點(diǎn)的地址為 。（ ）A.da+(i-1)*mB.da+i*mC.da-i*mD.da+(i+1)*m答案：A25鏈表是一種采用 存儲結(jié)構(gòu)存儲的線性表。（ ） A.順序B.鏈?zhǔn)紺.星式D.網(wǎng)狀答案：B26線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址 。（ ）A.必須是連續(xù)的B.部分地址必須是連續(xù)的C.一定是不連續(xù)的

17、D.連續(xù)或不連續(xù)都可以答案：D27線性表在 情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實現(xiàn)。 ( )A.需經(jīng)常修改中的結(jié)點(diǎn)值B.需不斷對進(jìn)行刪除插入C.中含有大量的結(jié)點(diǎn)D.中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜答案：B28在長度為 n 的順序表的第 i (1in+1) 個位置上插入一個元素，元素的移動次數(shù)為 。（ ）A.n-i+1B.n-iC.iD.i-1答案：A29線性表是 。（ ）A.一個有限系列，可以為空B.一個有限系列，不能為空C.一個無限系列，可以為空D.一個無限系列，不能為空答案：A30. _是線性表。( )A.(孔子,諸葛亮,曹雪芹)B.A,B,C,DC.10,11,12,13,14D.(1,2,3,.)答案：A31.

18、_ 是表示線性數(shù)據(jù)結(jié)構(gòu)的。( )A.循環(huán)鏈表B.鄰接多重表C.孩子鏈表D.單鏈表答案：D32. 將線性表的數(shù)據(jù)元素以_結(jié)構(gòu)存放, 查找一個數(shù)據(jù)元素所需時間不依賴于表長。( )A.循環(huán)雙鏈表B.哈希(Hash)表C.一維數(shù)組D.單鏈表答案：C33. 在一個單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行_。( )A.s-link=p;p-link=s;B.s-link=p-link;p-link=s;C.s-link=p-link;p=s;D.p-link=s;s-link=p;答案：34. 在循環(huán)鏈表中first為指向鏈表表頭的指針，current為鏈表當(dāng)前指針，在循環(huán)鏈表中

19、檢測current是否達(dá)到鏈表表尾的語句是_。( )A.current-link=NULLB.first-link=currentC.first=currentD.current-link=first答案：35. 從一個具有n個結(jié)點(diǎn)的單鏈表中查找其值等于x結(jié)點(diǎn)時，在查找成功的情況下，需平均比較_個結(jié)點(diǎn)。( )A.NB.n/2C.(n-1)/2D.(n+1)/2答案：36. 用鏈表表示線性表的優(yōu)點(diǎn)是_。 ( ) A. 便于隨機(jī)存取B. 花費(fèi)的存儲空間比順序表少C. 便于插入與刪除D. 數(shù)據(jù)元素的物理順序與邏輯順序相同答案：37. 當(dāng)需要隨機(jī)查找線性表的元素時,宜采用_作存儲結(jié)構(gòu)。( )A.雙向鏈

20、表B.循環(huán)鏈表C.順序表D.單鏈表答案：38. 線性表的鏈接實現(xiàn)有利于 運(yùn)算。( )A.插入B.讀表元C.查找D.定位答案：39. 線性表采用鏈?zhǔn)酱鎯r，其地址_。 ( ) A.必須是連續(xù)的B.部分地址是連續(xù)的C.一定是不連續(xù)的D.連續(xù)與否均可以答案：40. 設(shè)單鏈表中指針p指著結(jié)點(diǎn)a，若要刪除a之后的結(jié)點(diǎn)（若存在），則需要修改指針的操作為_。 ( ) A.p-next=p-next-nextB.p=p-nextC.p= p-next-nextD.p-next=p答案：A41. 向一個有127個元素順序表中插入一個新元素并保存原來順序不變，平均要移動 個元素。( )A.64B.63.5C.63

21、D.64.5答案：A42. 向一個有 127 個元素的順序表中刪除一個元素，平均要移動 個元素。( )A.8B.63.5C.63D.7答案：C43_又稱為FIFO表。( )A.隊列B.散列表C.棧D.哈希表答案：44設(shè)依次進(jìn)入一個棧的元素序列為c,a,b,d,不可得到出棧的元素序列有_。( )A.a.b,c,dB.a,d,c,bC.b,a,d,cD.c,d,a,b答案：45. 鏈?zhǔn)綏Ｅc順序棧相比，一個比較明顯的優(yōu)點(diǎn)是_。( )A. 插入操作更加方便B. 通常不會出現(xiàn)棧滿的情況C. 不會出現(xiàn)?？盏那闆rD. 刪除操作更加方便答案：46. 在一個順序存儲的循環(huán)隊列中，隊頭指針指向隊頭元素的_。( )

22、A. 前一個位置B. 后一個位置C. 隊頭元素位置D. 隊尾元素的前一位置答案：47. 若一個棧的輸入序列是1，2，3n，則輸出序列的第一個元素是n，則第i個輸出元素是_。( )A.n-iB.iC.n-i+1D.n-i-1答案：48. 棧的數(shù)組表示中，top為棧頂指針，?？盏臈l件是_。( )A.top=0B.top=maxSizeC.top=maxSizeD.top=-1答案：49. 在數(shù)組表示的循環(huán)隊列中，front、rear分別為隊列的頭、尾指針，maxSize為數(shù)組的最大長度，隊滿的條件是_。( )A.front=maxSizeB.(rear+1)%maxSize=frontC.rear

23、=maxSizeD.rear=front答案：50. 棧和隊列的共同特點(diǎn)是_。( )A.都是先進(jìn)后出B.都是先進(jìn)先出C.只允許在端點(diǎn)處插入和刪除D.沒有共同點(diǎn)答案：51若非空隊列采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，front和rear分別為隊頭元素與隊列尾元素的指針，刪除此時隊列的一個元素的操作時依次執(zhí)行pfront，_ ，call RET(P)。( )A.frontlink(rear)B.rearlink(p)C.rearlink(front)D.frontlink(p)答案：52由兩個棧共享一個向量空間的好處是_。( )A減少存取時間，降低下溢發(fā)生的機(jī)率B節(jié)省存儲空間，降低上溢發(fā)生的機(jī)率C減少存取時間，降低

24、上溢發(fā)生的機(jī)率D節(jié)省存儲空間，降低下溢發(fā)生的機(jī)率答案：53數(shù)組datam為循環(huán)隊列的存儲空間, front為隊頭指針, rare為隊尾指針,則執(zhí)行入隊的操作為_。( )A.rare=rare+1B.rare=(rare+1)%(m-1)C.rare=(rare-1)%mD.rare=(rare+1)%m答案：54. 將遞歸算法轉(zhuǎn)換成對應(yīng)的非遞歸算法時，通常需要使用_。( )A.棧B.隊列C.鏈表D.數(shù)組答案：55高度為 h(h0) 的二叉樹最少有 _ 個結(jié)點(diǎn)。( )A.hB.h-1C.h+1D.2h答案：56樹型結(jié)構(gòu)最適合用來描述_。( )A.有序的數(shù)據(jù)元素B.無序的數(shù)據(jù)元素C.數(shù)據(jù)元素之間的

25、具有層次關(guān)系的數(shù)據(jù)D.數(shù)據(jù)元素之間沒有關(guān)系的數(shù)據(jù)答案：57有n(n0)個結(jié)點(diǎn)的完全二叉樹的深度是_。( )A.log2(n)B.log2(n)+1C.log2(n+1)D.log2(n)+1答案：58. _ 又是一棵滿二叉樹。( )A.二叉排序樹B.深度為5有31個結(jié)點(diǎn)的二叉樹C.有15個結(jié)點(diǎn)的完全二叉樹D.哈夫曼(Huffman)樹答案：59. 深度為k的滿二叉樹有_個分枝結(jié)點(diǎn)。( )A.2k-1B.2k-1-1C.2k+1D.2k-1+1答案：60. 若已知一棵二叉樹先序序列為ABCDEFG，中序序列為CBDAEGF，則其后序序列為_。( )A.CDBGFEAB.CDBFGEAC.CDBA

26、GFED.BCDAGFE答案：A61. 二叉樹第i(i=1)層上至多有 結(jié)點(diǎn)。( )A.iB.iC.iD.i答案：62. 在一棵具有5層的滿二叉樹中結(jié)點(diǎn)總數(shù)為_。( )A. 31B. 32C. 33D. 16答案：63. 一個二叉樹按順序方式存儲在一個維數(shù)組中，如圖0 1 2 3 4 5 6 7 8 9 10 11 12 13 14ABCDEFGHIJ則結(jié)點(diǎn)E在二叉樹的第 層。( )A.1B.2C.3D.4答案：64在一棵度為3的樹中,度為3的結(jié)點(diǎn)個數(shù)為2,度為2 的結(jié)點(diǎn)個數(shù)為1,則度為0的結(jié)點(diǎn)個數(shù)為_。( )A4B5C6D7答案：65n 個頂點(diǎn)的帶權(quán)無向連通圖的最小生成樹包含 _ 個頂點(diǎn)。(

27、 )A.n-1B.nC.n/2D.n+1答案：66具有 n 個頂點(diǎn)的有向完全圖有 條弧。( )A.nB.n*(n-1)C.n*(n+1)D.n*n答案：67. n 個頂點(diǎn)的連通圖至少有 條邊。( )A.n-1 B.n C.n+1 D.0答案：68在一個有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的 倍。( )A1/2B1C2D4答案：69在含n個頂點(diǎn)和e條邊的無向圖的鄰接矩陣中,零元素的個數(shù)為_。( )AeB2eCn2eDn22e答案：D70折半查找有序表(6,15,30,37,65,68,70,72,89,99),若查找元素37,需依次與表中元素_進(jìn)行比較。( )A.65,15,37B.

28、68,30,37C.65,15,30D.65,15,30,37答案：71對有3600個記錄的索引順序表(分塊表)進(jìn)行查找,最理想的塊長為_。( )A.1800B.60C.1200D.log2 3600答案：B72. 折半查找20個記錄的有序表,若查找失敗,比較關(guān)鍵字的次數(shù)_。( )A.最多為6B.最多為5C.最多為4D.最多為3答案：B73. 中序遍歷一棵二叉排序樹所得到的結(jié)點(diǎn)序列是鍵值的 序列。( )A.遞增或遞減B.遞減C.遞增D.無序答案：74散列表中的沖突是指_。( )A.兩個元素具有相同的序號B.兩個元素的鍵值相同，而其他屬性相同C.不同的鍵值對應(yīng)相同的存儲地址D.數(shù)據(jù)元素的地址相同

29、答案：75用線形探測法查找散列表，可能要探測多個散列地址，這些位置上的鍵值_。( )A.一定是同義詞B.不一定是同義詞C.一定不是同義詞D.都相同答案：76在初始為空的雜湊表中依次插入關(guān)鍵字序列(MON，TUE，WED，THU，F(xiàn)RI，SAT，SUN), 雜湊函數(shù)為H(k)=i MOD 7，其中，i為關(guān)鍵字k的第一個字母在英文字母表中的序號，地址值域為0:6，采用線性再散列法處理沖突。插入后的雜湊表應(yīng)該如_所示。( )A. 0 1 2 3 4 5 6 THU TUE WED FRI SUN SAT MONB. 0 1 2 3 4 5 6 TUE THU WED FRI SUN SAT MONC

30、. 0 1 2 3 4 5 6 TUE THU WED FRI SAT SUN MOND. 0 1 2 3 4 5 6 TUE THU WED SUN SAT FRI MON答案：77設(shè)有一個含200個表項的散列表，用線性探查法解決沖突，按關(guān)鍵碼查詢時找到一個表項的平均探查次數(shù)不超過1.5，則散列存儲空間應(yīng)能夠至少容納 個表項。（設(shè)搜索成功的平均搜索長度為Snl=(1+1/(1-a)/2,其中a 為裝填因子）( )A.400B.526C.624D.676答案：78對長度為10的表作選擇(簡單選擇)排序,共需比較_次關(guān)鍵字。( )A.45B.90C.55D.110答案：79. 設(shè)有100個數(shù)據(jù)元

31、素，采用折半搜索時，最大比較次數(shù)為 ( )。A. 6B. 7C. 8D. 10答案：80. 對待排序的元素序列進(jìn)行劃分，將其分為左、右兩個子序列，再對兩個子序列施加同樣的排序操作，直到子序列為空或只剩一個元素為止。這樣的排序方法是_。( )A. 選擇排序B. 直接插入排序C. 快速排序D. 起泡排序答案：C81. 對5個不同的數(shù)據(jù)元素進(jìn)行直接插入排序，最多需要進(jìn)行 次比較。( )A. 8B. 10C. 15D. 25答案：82. 采用折半查找方法進(jìn)行查找，數(shù)據(jù)文件應(yīng)為 ，且限于 。( )A.有序表 順序存儲結(jié)構(gòu)B.有序表 鏈?zhǔn)酱鎯Y(jié)構(gòu)C.隨機(jī)表 順序存儲結(jié)構(gòu)D.隨機(jī)表 鏈?zhǔn)酱鎯Y(jié)構(gòu)答案：83.

32、 從未排序序列中依次取出一個元素與已排序序列中的元素依次進(jìn)行比較，然后將其存放在已排序序列的合適位置，該排序方法稱為 排序法。( )A.插入B.選擇C.希爾D.二路并歸答案：84. 就平均查找速度而言，下列幾種查找速度從慢至快的關(guān)系是 。( )A.順序 折半 哈西 分塊B.順序 分塊 折半 哈西C.分塊 折半 哈西 順序D.順序 哈西 分塊 折半答案：B85. 在下列算法中， 算法可能出現(xiàn)下列情況：在最后一趟開始之前，所有的元素都不在其最終的位置上。( )A.堆排序B.冒泡排序C.插入排序D.快速排序答案：C86堆是一個鍵值序列( K1, K2, , Kn )，對 I = 1,2n/2, 滿足

33、 。( )A.Ki = K2i = K2i+1B.Ki K2i+1 K2i C.Ki = K2i 且 Ki =K2i+1D. Ki = K2i 或 Ki 0) 個結(jié)點(diǎn)二叉樹對應(yīng)的森林最多包含_ 棵非空樹。答案：5深度為 n(n0) 的二叉樹最多有 _ 個結(jié)點(diǎn)。 答案：6n(n0) 個結(jié)點(diǎn)、 (n-1) 條邊的連通無向圖中，頂點(diǎn)度數(shù)最大值為 _ 。 答案：7在一個圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊的數(shù)目的_2_倍。答案：8圖的深度優(yōu)先搜索方法類似于二叉樹的_遍歷。答案：9帶權(quán)連通圖G,其中V=v1,v2,v3,v4,v5，E=(v1,v2)7,V1,V3)6,(V1,V4)9,(V2,V3)8,

34、(V2,V3)8,(V2,V4)4,(V2,V5)4,(V3,V4)6,(V4,V5)2（注：頂點(diǎn)偶對右下角的數(shù)據(jù)為邊上的權(quán)值），G的最小生成樹的權(quán)值之和為_。答案：10.將數(shù)據(jù)元素2,4,6,8,10,12,14,16,18,20依次存放于一個一維數(shù)組中，然后采用折半查找方法查找元素12，被比較過的數(shù)組元素的下標(biāo)依次為_。答案：11.每趟排序從未排序的子序列中依次取出元素與已經(jīng)排好序的序列中元素進(jìn)行比較，然后將其放在已經(jīng)排好序的序列的合適位置。這種排序法稱為_插入_排序法。答案：12.從未排序序列中選擇一個元素，該元素將當(dāng)前參加排序的那些元素分成前后兩個部分，前一部分中所有元素都小于等于所選

35、元素，后一部分中所有元素都大于或等于所選元素，而此時所選元素處在排序的最終位置。這種排序法稱為_快速_排序法。答案：13.對序列(49,38,65,97,76,27,13,50)采用快速排序法進(jìn)行排序，以序列的第一個元素為基準(zhǔn)元素得到的劃分結(jié)果是_。答案：14一個數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的表示(映象)稱為 _數(shù)據(jù)的存儲結(jié)構(gòu)_。答案：15數(shù)據(jù)結(jié)構(gòu)被形式地定義為（ D, R ），其中 D 是 的有限集合， R 是 D 上的 有限集合。 答案：16數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的_存儲結(jié)構(gòu)_無關(guān)，是獨(dú)立于計算機(jī)的。答案：17一個算法具有5個特性:_、_、_、有零個或多個輸入、有一個或多個輸

36、出。答案：18線性表中 _數(shù)據(jù)元素的個數(shù)_ 稱為表的長度。答案：19設(shè)長度為n的線性表順序存貯,若在它的第i-1和第i個元素之間插入一個元素, 共需移動 _ 個元素(1link;p-link=_ _Delete q答案：23設(shè) SQ 為循環(huán)隊列，存儲在數(shù)組 dm 中，則 SQ 出隊操作對其隊頭指針 front 的修改是 _ 。答案：24棧中元素的進(jìn)出原則為 _ 。答案：25在解決計算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題時通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則從該緩沖區(qū)中取出數(shù)據(jù)打印。該緩沖區(qū)應(yīng)該是一個 列隊 結(jié)構(gòu)，其主要特點(diǎn)是 先進(jìn)先出 。答案：26對于一個以順

37、序?qū)崿F(xiàn)的循環(huán)隊列Q0m-1，隊頭、隊尾指針分別為f、r，其判空的條件是r=f ，判滿的條件是 (r+1)%m=f 。答案：、27在具有n個單元的循環(huán)隊列中，隊滿時共有_n-1_個元素。答案：28深度為 n(n0) 的二叉樹最多有 _ 個結(jié)點(diǎn)。答案：29n(n0) 個結(jié)點(diǎn)、 (n-1) 條邊的連通無向圖中，頂點(diǎn)度數(shù)最大值為 _ 。答案：30一棵深度為6的滿二叉樹有_個非終端結(jié)點(diǎn)。答案：31若一棵二叉樹中有8個度為2的結(jié)點(diǎn),則它有_9_個葉子。答案：32樹中結(jié)點(diǎn)A的 _子樹數(shù)_ 稱為結(jié)點(diǎn)A的度。答案：33一棵深度為4的二叉樹最多有 _ 個結(jié)點(diǎn)。答案：2*n -134將 轉(zhuǎn)化為二叉樹時，其根結(jié)點(diǎn)的右

38、子樹總是空的。答案：35哈夫曼樹是帶權(quán)路徑長度 的樹，通常權(quán)值較大的結(jié)點(diǎn)離根結(jié)點(diǎn) 。答案：36具有n個葉子的二叉樹，每個葉子的權(quán)值為wi(1in)其中帶權(quán)路徑最小的二叉樹被稱為 。答案：37若已知一棵二叉樹的先序序列為 + a * b c d / e f，中序序列為a + b * c d e / f，則其后序序列為_。答案：38已知一棵完全二叉樹中共有768結(jié)點(diǎn)，則該樹中共有_個葉子結(jié)點(diǎn)。答案：39已知二叉樹有50個葉子結(jié)點(diǎn)，且僅有一個孩子的結(jié)點(diǎn)數(shù)為30，則總結(jié)點(diǎn)數(shù)為 。答案：40具有10個頂點(diǎn)的無向圖,邊的總數(shù)最多為 _ 。答案：41在有n個頂點(diǎn)的有向圖中，每個頂點(diǎn)的度最大可達(dá) 。答案：42

39、有向圖g用鄰接矩陣am,1m來存儲，其第i行的所有元素之和等于頂點(diǎn)i的。答案：43有n個球隊參加的足球聯(lián)賽按主客場制進(jìn)行比賽，共需進(jìn)行 場比賽。答案：44帶權(quán)連通圖G=，其中V=v1,v2,v3,v4,v5,E=(v1,v2)7,(v1,v4)6，(v1,v4)9，(v2,v3)8，(v2,v4)4，(v2,v5)4，(v3,v4)6，(v4,v5)2，(注：頂點(diǎn)偶對右下角的數(shù)據(jù)為邊上的權(quán)值)，G的最小生成樹的權(quán)值之和為_ 。答案：45順序查找n個元素的順序表,當(dāng)使用監(jiān)視哨時,若查找成功,比較關(guān)鍵字的次數(shù)至少為_次, 最多為_次；若查找失敗,比較關(guān)鍵字的次數(shù)為_次。答案：46在單鏈表上難以實現(xiàn)的排序方法有 、 和 。答案：快速排序、堆排序、希爾排序 五、簡答題/問答題/綜述題1什么是順序表？順序表的特點(diǎn)是什么？答案：線性表的順序存儲是指在內(nèi)存中用一塊地址連續(xù)的存儲空間順序存放線性表的各元素，用這種形式存儲的線性表稱為順序表。數(shù)據(jù)元素在順序表中物理位置取決于數(shù)據(jù)元素在線性表中的邏輯位置，可得出順序表的特點(diǎn)：邏輯位置相鄰，其物理位置也相鄰。2什么樣的圖是連通圖？答案