【正文】 答案： B 2. 在計(jì)算機(jī)系統(tǒng)中，操作系統(tǒng)是 （ ） 答案： B 3. 如果分時(shí)系統(tǒng)的時(shí)間片一定，那么（ ），則響應(yīng)時(shí)間越長。增量序列取為 5, 3, 2, 1。 3．設(shè)散列 表的長度為 13，散列函數(shù)為 H(k) = k % 13，給頂?shù)年P(guān)鍵碼序列為 19, 14, 23, 01, 68, 20, 84, 27。 答案： 24．試按表 ( 10,8,9,12,20,5,6,15,19,25 )中元素的排列次序 , 將所有元素插入一棵初始為空的二叉排序樹中 , 使之仍是一棵二叉排序樹。 答案： 19． 找出下面網(wǎng)絡(luò)的最小生成樹 : 答案： 20． 試畫出下列圖的鄰接表。 答案： 《軟件技術(shù)基礎(chǔ)》試題庫 15．某二叉樹的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲表示如下： (1) 試畫出此二叉樹的圖形表示。 樹 答案： 11． 已知二叉樹的前序遍歷序列和中序遍歷序列分別是： B,A,C,D,F,E,G 和 D,C,A,F,G,E,B, 試畫出該二叉樹。 (1)畫出相應(yīng)的哈夫曼樹； (2)分別列出 A、 B、 C、 D、 E、 F 的哈夫曼碼； (3)計(jì)算該樹的帶權(quán)路徑長度 WPL。 3． 二叉樹有哪幾種基本形態(tài) ? 畫圖說明之。 答案： 46． 在單鏈表上難以實(shí)現(xiàn)的排序方法有 、 和 。 答案： 42．有向圖 g 用 鄰接矩陣 a［１ …m,1…m ］來存儲，其第 i 行的所有元素之和等于頂點(diǎn) i的 。 答案： 38．已知一棵完全二叉樹中共有 768 結(jié)點(diǎn)，則該樹中共有 _____個(gè)葉子結(jié)點(diǎn)。 答案： 34．將 轉(zhuǎn)化為二叉樹時(shí)，其根結(jié)點(diǎn)的右子樹總是空的。 答案： 30．一棵深度為 6 的滿二叉樹有 ______個(gè)非終端結(jié)點(diǎn)。 答案： 26．對于一個(gè)以順序?qū)崿F(xiàn)的循環(huán)隊(duì)列 Q[0…m 1]，隊(duì)頭、隊(duì)尾指針分別為 f、 r，其判空的條件是 ，判滿的條件是 。 plink=____ __ Delete q 答案： 23．設(shè) SQ 為循環(huán)隊(duì)列，存儲在數(shù)組 d[m] 中，則 SQ 出隊(duì)操作對其隊(duì)頭指針 front 的修改是 _______________ 。 答案： 19．設(shè)長度為 n 的線性表順序存貯 ,若在它的第 i1 和第 i 個(gè)元素之間插入一個(gè)元素 , 共需移動(dòng) _________ 個(gè)元素 (1i≤n)。 答案： 15． 數(shù)據(jù)結(jié)構(gòu)被形式地定義為（ D, R ），其中 D 是 的有限集合， R 是 D 上 的 有限集合。 答案： ，該元素將當(dāng)前參加排序的那些元素分成前后兩個(gè)部分，前一部分中所有元素都小于等于所選元素，后一部分中所有元素都大于或等于所選元素，而此時(shí)所選元素處在排序的最終位置。 答案： 9． 帶權(quán)連通圖 G, 其中 V={v1,v2,v3,v4,v5}， E={(v1,v2)7,V1,V3)6,(V1,V4)9,(V2,V3)8,(V2,V3)8,(V2,V4)4,(V2,V5)4,(V3,V4)6,(V4,V5)2}（注：頂點(diǎn)偶對右下角的數(shù)據(jù)為邊上的權(quán)值）， G 的最小生成樹的權(quán)值之和為 ____________。 答案： 5． 深度為 n(n0) 的二叉樹最多有 _______________ 個(gè)結(jié)點(diǎn)。 ( ) 答案： T 四、填空題 1．已知具有 n 個(gè)元素的一維數(shù)組采用順序存儲結(jié)構(gòu)，每個(gè)元素占 k 個(gè)存儲單元，第一個(gè)元素的地址為 LOC(a1)，那么， LOC(ai)=___________________。 ( ) 答案： T 23． 對二叉排序樹遍歷的結(jié)果是一個(gè)有序序列。（ ） 答案： F 19．完全二叉樹就是滿二叉樹。 ( ) 答案： T ，隊(duì)頭指針與指針分別為 front 和 rear，向隊(duì)列中插入一個(gè)數(shù)據(jù)信息為 item 的新元素的過程是依次執(zhí)行 :call GETNODE(p),data(P)←item,rear←p,front←p 。link(p)←q 。 ( ) 答案： F n 的線性表采用順序存儲結(jié)構(gòu)，刪除表的第 i 個(gè)元素之前需要移動(dòng)表中 ni+1 個(gè)元素。 ( ) 答案： F 4． 數(shù)據(jù)的存儲結(jié)構(gòu)不僅有順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，還有索引結(jié)構(gòu)與散列結(jié)構(gòu)。 ( ) A. 順序存儲結(jié)構(gòu) B. 二叉樹存儲結(jié)構(gòu) C. 鏈?zhǔn)酱鎯Y(jié)構(gòu) D. 網(wǎng)絡(luò)結(jié)構(gòu) 答案： AC 3．查找哈希 (Hash)表 ,解決沖突的的方法有 ___。 ( ) A． 16， 72， 31， 23， 94， 53 B． 94， 23， 31， 72， 16， 53 C． 16， 53， 23， 94， 31， 72 D． 16， 23， 53， 31， 94， 72 答案： 90．目前以比較為基礎(chǔ)的內(nèi)部排序方法中，其比較次數(shù)與待排序的記錄的初始排列狀態(tài)無關(guān)的是 。 ( ) 《軟件技術(shù)基礎(chǔ)》試題庫 答案： C 86．堆是一個(gè)鍵值序列 ( K1, K2, …, K n )，對 I = 1,2…[n/2], 滿足 。 ( ) A. 8 B. 10 C. 15 D. 25 答案： 82. 采用折半查找方法進(jìn)行查找，數(shù)據(jù)文件應(yīng)為 ，且 限于 。 ( ) 答案： 79. 設(shè)有 100 個(gè)數(shù)據(jù)元素，采用折半搜索時(shí)，最大比較次數(shù)為 ( )。 ( ) 答案： 《軟件技術(shù)基礎(chǔ)》試題庫 76．在初始為空的雜湊表中依次插入關(guān)鍵字序列 (MON， TUE， WED， THU， FRI， SAT，SUN), 雜湊函數(shù)為 H(k)=i MOD 7，其中， i 為關(guān)鍵字 k 的第一個(gè)字母在英文字母表中的序號，地址值域?yàn)?[0:6] ，采用線性再散列法處理沖突。 ( ) D.?log2 3600? 答案： B 72. 折半查找 20個(gè)記錄的有序表 ,若查找失敗 ,比較關(guān)鍵字的次數(shù) ____。 ( ) +1 答案： 68．在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的 倍。 ( ) 答案： 64．在一棵度為 3 的樹中 ,度為 3 的結(jié)點(diǎn)個(gè)數(shù)為 2,度為 2 的結(jié)點(diǎn)個(gè)數(shù)為 1,則度為 0 的結(jié)點(diǎn)個(gè)數(shù)為 ____。 ( ) +1 +1 答案： 《軟件技術(shù)基礎(chǔ)》試題庫 60. 若已知一棵二叉樹先序序列為 ABCDEFG，中序序列為 CBDAEGF，則其后序序列為____。 ( ) +1 答案： 56．樹型結(jié)構(gòu)最適合用來描述 ____。 ( ) ←link(rear) ←link(p) ←link(front) ←link(p) 答案： 52．由兩個(gè)棧共享一個(gè)向量空間的好處是 _____。 ( ) +1 答案： 48. 棧的數(shù)組表示中， top 為棧頂指針，棧空的條件是 _____。 ( ) 《軟件技術(shù)基礎(chǔ)》試題庫 答案： 44． 設(shè)依次進(jìn)入一個(gè)棧的元素序列為 c,a,b,d,不可得到出棧的元素序列有 _____。 ( ) 答案： 40. 設(shè)單鏈表中指針 p 指著結(jié)點(diǎn) a，若要?jiǎng)h除 a 之后的結(jié)點(diǎn)（若存在），則需要修改指針的操作為 ____。 ( ) B. n/2 C.(n1)/2 D.(n+1)/2 答案： 36. 用鏈表表示線性表的優(yōu)點(diǎn)是 ____。 link=s。 B. slink=plink。 ( ) 答案： D 32. 將線性表的數(shù)據(jù)元素以 ____結(jié)構(gòu)存放 , 查找一個(gè)數(shù)據(jù)元素所需時(shí)間不依賴于表長。 ( ) 答案： B 28．在長度為 n 的順序表的第 i (1≤i≤n+1) 個(gè)位置上插入一個(gè)元素，元素的移動(dòng)次數(shù)為 。（ ） B. 108 答案： B 24．已知一個(gè)順序存儲的線性表，設(shè)每個(gè)結(jié)點(diǎn)需要占 m 個(gè)存儲單元，若第一個(gè)結(jié)點(diǎn)的地址為 da，則第 i 個(gè)結(jié)點(diǎn)的地址為 。（ ） 答案： C 20． 算法指的是 。 ( ) 答案： D 16． 是具有相同特性數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。 ( ) 《軟件技術(shù)基礎(chǔ)》試題庫 +1 答案： C 10． 在非空二叉樹的中序遍歷序列中，二叉樹的根結(jié)點(diǎn)的左邊應(yīng)該 ( ) 答案： A 11． 下面關(guān)于哈夫曼樹的說法， 不正確 的是 ( ) 1 的結(jié)點(diǎn) 1 的結(jié)點(diǎn)外，還有度為 2 的結(jié)點(diǎn)和葉結(jié)點(diǎn) 答案： D 12．?dāng)?shù)據(jù)結(jié)構(gòu)是一門研究計(jì)算機(jī)中 對象及其關(guān)系的學(xué)科。（ ） +1 答案： B 5． 采用拉鏈法解決沖突的散 列表中，查找的平均查找長度 ( )。《軟件技術(shù)基礎(chǔ)》試題庫 《 軟件技術(shù)基礎(chǔ) 》 試題庫 課程名稱： 軟件技術(shù)基礎(chǔ) 適用專業(yè)：軟件技術(shù) 、計(jì)算機(jī)應(yīng)用、網(wǎng)絡(luò)、信息等計(jì)算機(jī)相關(guān) 專業(yè) 第一章 概述 第二章 數(shù)據(jù)結(jié)構(gòu) 一、單項(xiàng)選擇題 1．若長度為 n 的線性表采用順序存儲結(jié)構(gòu)，刪除它的第 i 數(shù)據(jù)元素之前，需要先依次向前移動(dòng) _______個(gè)數(shù)據(jù)元素。（ ） A. h B. h1 C. h+1 D. 2h 《軟件技術(shù)基礎(chǔ)》試題庫 答案： A 4． n 個(gè)頂點(diǎn)的帶權(quán)無向連通圖的最小生成樹包含 ________ 個(gè)頂點(diǎn) 。 ( ) B. 33 答案： C 9． 若某完全二叉樹的深度為 h，則該完全二叉樹中至少有 ______個(gè)結(jié)點(diǎn)。 ( ) 答案： C 《軟件技術(shù)基礎(chǔ)》試題庫 15． 數(shù)據(jù)的不可分割的基本單位是 。 （ ） 答案： C 19．?dāng)?shù)據(jù)在計(jì)算機(jī)存儲器內(nèi)表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱為 。 ( ) i 個(gè)節(jié)點(diǎn)的位置 、刪除操作不方便 答案： B 23．一個(gè)向量第一個(gè)元素的存儲地址是 100 ，每個(gè)元素的長度為 2 ，則第 5 個(gè)元素的地址是 。（ ） 《軟件技術(shù)基礎(chǔ)》試題庫 的 答案： D 27．線性表Ｌ在 情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。 ( ) A.(孔子 ,諸葛亮 ,曹雪芹 ) B.{A,B,C,D} C.{10,11,12,13,14} D.(1,2,3,...) 答案： A 31. ____ 是表示線性數(shù)據(jù)結(jié)構(gòu)的。plink=s。p=s。 ( ) link=NULL B. firstlink=current =current link=first 答案： 35. 從一個(gè)具有 n 個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于 x 結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較 ____個(gè)結(jié)點(diǎn)。 ( ) 《軟件技術(shù)基礎(chǔ)》試題庫 答案： 39. 線性表采用鏈?zhǔn)酱鎯r(shí)，其地址 ____。 ( ) 答案： C 43． ____又稱為 FIFO 表。 ( ) A. 前一個(gè)位置 B. 后一個(gè)位置 C. 隊(duì)頭元素位置 D. 隊(duì)尾元素的前一位置 答案： 47. 若一個(gè)棧的輸入序列是 1， 2， 3……n ，則輸出序列的第一個(gè)元素是 n，則第 i 個(gè)輸出元素是 _____。 ( ) 答案： 51．若非空隊(duì)列采用鏈?zhǔn)酱鎯Y(jié)構(gòu)， front 和 rear 分別為隊(duì)頭元素與隊(duì)列尾元素的指針，刪除此時(shí)隊(duì)列的一個(gè)元素的操作時(shí)依次執(zhí)行 p←front ， ______ ， call RET(P)。 ( ) 《軟件技術(shù)基礎(chǔ)》試題庫 答案：