【正文】 63. 一個二叉樹按順序方式存儲在一個維數(shù)組中，如圖 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B C D E F G H I J 則結(jié)點(diǎn) E 在二叉樹的第 層。 ( ) 答案： 64．在一棵度為 3 的樹中 ,度為 3 的結(jié)點(diǎn)個數(shù)為 2,度為 2 的結(jié)點(diǎn)個數(shù)為 1,則度為 0 的結(jié)點(diǎn)個數(shù)為 ____。 ( ) A． 4 B． 5 C． 6 《軟件技術(shù)基礎(chǔ)》試題庫 D． 7 答案： 65． n 個頂點(diǎn)的帶權(quán)無向連通圖的最小生成樹包含 ________ 個頂點(diǎn) 。 ( ) +1 答案： 66． 具有 n 個頂點(diǎn)的有向完全圖有 條弧。 ( ) *(n1) *(n+1) *n 答案： 67. n 個頂點(diǎn)的連通圖至少有 條邊。 ( ) +1 答案： 68．在一個有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的 倍。 ( ) A． 1/2 B． 1 C． 2 D． 4 答案： 69．在含 n 個頂點(diǎn)和 e 條邊的無向圖的鄰接矩陣中 ,零元素的個數(shù)為 ____。 ( ) A． e B． 2e C． n2－ e D． n2－ 2e 答案： D 70． 折半查找有序表 (6,15,30,37,65,68,70,72,89,99),若查找元素 37,需依次與表中元素 ____進(jìn)《軟件技術(shù)基礎(chǔ)》試題庫 行比較。 ( ) ,15,37 ,30,37 ,15,30 ,15,30,37 答案： 71． 對有 3600 個記錄的索引順序表 (分塊表 )進(jìn)行查找 ,最理想的塊長為 ___。 ( ) D.?log2 3600? 答案： B 72. 折半查找 20個記錄的有序表 ,若查找失敗 ,比較關(guān)鍵字的次數(shù) ____。 ( ) 6 5 4 3 答案： B 73. 中序遍歷一棵二叉排序樹所得到的結(jié)點(diǎn)序列是鍵值的 序列。 ( ) 答案： 74．散列表中的沖突是指 ____。 ( ) ，而其他屬性相同 答案： 75． 用線形探測法查找散列表，可能要探測多個散列地址，這些位置上的鍵值 ____。 ( ) 答案： 《軟件技術(shù)基礎(chǔ)》試題庫 76．在初始為空的雜湊表中依次插入關(guān)鍵字序列 (MON， TUE， WED， THU， FRI， SAT，SUN), 雜湊函數(shù)為 H(k)=i MOD 7，其中， i 為關(guān)鍵字 k 的第一個字母在英文字母表中的序號，地址值域?yàn)?[0:6] ，采用線性再散列法處理沖突。插入后的雜湊表應(yīng)該如________________所示。 ( ) A. 0 1 2 3 4 5 6 THU TUE WED FRI SUN SAT MON B. 0 1 2 3 4 5 6 TUE THU WED FRI SUN SAT MON C. 0 1 2 3 4 5 6 TUE THU WED FRI SAT SUN MON D. 0 1 2 3 4 5 6 TUE THU WED SUN SAT FRI MON 答案： 77． 設(shè)有一個含 200 個表項(xiàng)的散列表，用線性探查法解決沖突，按關(guān)鍵碼查詢時找到一個表項(xiàng)的平均探查次數(shù)不超過 ，則散列存儲空間應(yīng)能夠至少容納 個表項(xiàng)。（設(shè)搜索成功的平均搜索長度為 Snl=(1+1/(1a))/2,其中 a 為裝填因子） ( ) 答案： 78． 對長度為 10 的表作選擇 (簡單選擇 )排序 ,共需比較 ____次關(guān)鍵字。 ( ) 答案： 79. 設(shè)有 100 個數(shù)據(jù)元素，采用折半搜索時，最大比較次數(shù)為 ( )。 A. 6 B. 7 C. 8 D. 10 答案： 80. 對待排序的元素序列進(jìn)行劃分，將其分為左、右兩個子序列，再對兩個子序列施加同樣的排序操作，直到子序列為空或只剩一個元素為止。這樣的排序方法是 ____。 ( ) A. 選擇排序 B. 直接插入排序 《軟件技術(shù)基礎(chǔ)》試題庫 C. 快速排序 D. 起泡排序 答案： C 81. 對 5 個不同的數(shù)據(jù)元素進(jìn)行直接插入排序，最多需要進(jìn)行 次比較。 ( ) A. 8 B. 10 C. 15 D. 25 答案： 82. 采用折半查找方法進(jìn)行查找，數(shù)據(jù)文件應(yīng)為 ，且 限于 。 ( ) 順序存儲結(jié)構(gòu) 鏈?zhǔn)酱鎯Y(jié)構(gòu) 順序存儲結(jié)構(gòu) 鏈?zhǔn)酱鎯Y(jié)構(gòu) 答案： 83. 從未排序序列中依次取出一個元素與已排序序列中的元素依次進(jìn)行比較，然后將其存放在已排序序列的合適位置，該排序方法稱為 排序法。 ( ) 答案： 84. 就平均查找速度而言，下列幾種查找速度從慢至快的關(guān)系是 。 ( ) 折半 哈西 分塊 分塊 折半 哈西 折半 哈西 順序 哈西 分塊 折半 答案： B 85. 在下列算法中， 算法可能出現(xiàn)下列情況：在最后一趟開始之前，所有的元素都不在其最終的位置上。 ( ) 《軟件技術(shù)基礎(chǔ)》試題庫 答案： C 86．堆是一個鍵值序列 ( K1, K2, …, K n )，對 I = 1,2…[n/2], 滿足 。 ( ) = K2i = K2i+1 K2i+1 K2i = K2i 且 Ki =K2i+1 D. Ki = K2i 或 Ki = K2i+1 答案： 87．對于關(guān)鍵字序列 {46 ， 58 ， 15 ， 45 ， 90 ， 18 ， 10 ， 62} ，其快速排序第一趟的結(jié)果是 。 ( ) 45 18 46 10 62 58 90 15 18 45 46 58 62 90 18 15 45 46 90 58 62 10 18 45 46 62 58 90 答案： 88．用某種排序方法對關(guān)鍵字序列（ 25， 84， 21， 47， 15， 27， 68， 35， 20）進(jìn)行排序時，序列的變化情況如下： 20， 15， 21， 25， 47， 27， 68， 35， 84 15， 20， 21， 25， 35， 27， 47， 68， 84 15， 20， 21， 25， 27， 35， 47， 68， 84 則所采用的排序方法是 。 ( ) 答案： 89．下列關(guān)鍵字序列中 是堆。 ( ) 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)的是 。 ( ) A．插入排序 《軟件技術(shù)基礎(chǔ)》試題庫 B．直接選擇排序 C．快速排序 D．冒泡排序 答案： B 91．對 n 個不同的排序碼進(jìn)行冒泡排序，在元素?zé)o序的情況下比較的次數(shù)為 。 ( ) A． n+1 B． n C． n1 D． n(n1)/2 答案： 二、多項(xiàng)選擇題 1．根據(jù)數(shù)據(jù)元素之間的不同特性，通常具有 這幾種基本數(shù)據(jù)結(jié)構(gòu)。 ( ) A. 集合 B. 線形結(jié)構(gòu) C. 樹型結(jié)構(gòu) D. 圖型結(jié)構(gòu) 答案： ABCD 2． 數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中有 兩種不同的表示方法。 ( ) 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)表 ,解決沖突的的方法有 ___。 ( ) 答案： BD 三、判斷題 1．非空線 性表中任意一個數(shù)據(jù)元素都有且僅有一個直接前驅(qū)元素。 ( ) 答案： F 2．?dāng)?shù)組是一種沒有插入與刪除操作的線性結(jié)構(gòu)。 ( ) 《軟件技術(shù)基礎(chǔ)》試題庫 答案： T 3． 非空線性表中任意一個數(shù)據(jù)元素都有且僅有一個直接后繼元素。 ( ) 答案： F 4． 數(shù)據(jù)的存儲結(jié)構(gòu)不僅有順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，還有索引結(jié)構(gòu)與散列結(jié)構(gòu)。 ( ) 答案： F 5． 線性鏈表中各個鏈結(jié)點(diǎn)之間的地址不一定要連續(xù)。 ( ) 答案： T 6． 若頻繁地對線性表進(jìn)行插入和刪除操作，該線性表采用順序存儲結(jié)構(gòu)更合適。 ( ) 答案： F 儲結(jié)構(gòu)，每個數(shù)據(jù)元素占用 4 個存儲單元，第 12 個數(shù)據(jù)元素的存儲地址為 144，則第 1 個數(shù)據(jù)元素的存儲地址是 101。 ( ) 答案： F n 的線性表采用順序存儲結(jié)構(gòu)，刪除表的第 i 個元素之前需要移動表中 ni+1 個元素。 ( ) 答案： F link(p)出現(xiàn)在表達(dá)式中表示 p 所指的那個結(jié)點(diǎn)的內(nèi)容。 ( ) 答案： F p 移到它所指的結(jié)點(diǎn)的下一個結(jié)點(diǎn)是執(zhí)行語句 p←link(p) 。 ( ) 答案： T p 所指的結(jié)點(diǎn)后面插入一個由 q 所指的結(jié)點(diǎn)的過程是依次執(zhí) 行語句：link(q)←link(p)。link(p)←q 。 ( ) 答案： T q 所指的結(jié)點(diǎn)后面插入一個由 p 指的結(jié)點(diǎn)的動作依次為：llink(p)←q,rlink(p)←rlink(q),rlink(q)←p,llink(rlink(q))←p 。 ( ) 答案： F 1,2,3,4，則 4,3,1,2 不可能是堆棧的輸出序列之一。 ( ) 答案： T 14. 刪除非空鏈?zhǔn)酱鎯Y(jié)構(gòu)的堆棧 ( 設(shè)棧頂指針為 top) 的一個元素的過程是依次執(zhí)行 :p←top,top ←link(p),call RET(p) 。 ( ) 答案： T ，隊(duì)頭指針與指針分別為 front 和 rear，向隊(duì)列中插入一個數(shù)據(jù)信息為 item 的新元素的過程是依次執(zhí)行 :call GETNODE(p),data(P)←item,rear←p,front←p 。( ) 《軟件技術(shù)基礎(chǔ)》試題庫 答案： F 16．?dāng)?shù)據(jù)結(jié)構(gòu)概念包括數(shù)據(jù)之間的邏輯結(jié)構(gòu)，數(shù)據(jù)在計(jì)算機(jī)中的存儲方式和數(shù)據(jù)的運(yùn)算三個方面 。 ( ) 答案： T 17．非空線性表中任意一個數(shù)據(jù)元素都有且僅有一個直接前驅(qū)元素。 ( ) 答案： F 18． 在順序表中取出第 i 個元素所花費(fèi)的時間與 i 成正比。（ ） 答案： F 19．完全二叉樹就是滿二叉樹。 ( ) 答案： F 20．已知一棵二叉樹的前序序列和中序序列可以唯一地構(gòu)造出該二叉樹。 ( ) 答案： T 21．有向圖是一種非線性結(jié)構(gòu)。 ( ) 答案： T 22．帶權(quán)連通圖的最小生成樹的權(quán)值之和一定小于它的其它生成樹的權(quán)值之和。 ( ) 答案： T 23． 對二叉排序樹遍歷的結(jié)果是一個有序序列。（ ） 答案： T 24．折半查找方法適用于按值有序的線性鏈表的查找。 ( ) 答案： F 25．非空 二叉排序樹的任意一棵子樹也是二叉排序樹。 ( ) 答案： T 26．哈希表的查找效率主要取決于所選擇的哈希函數(shù)與處理沖突的方法。 ( ) 答案： T 四、填空題 1．已知具有 n 個元素的一維數(shù)組采用順序存儲結(jié)構(gòu)，每個元素占 k 個存儲單元，第一個元素的地址為 LOC(a1)，那么， LOC(ai)=___________________。 答案： LOC(a1)+(n1)k 2．若一棵二叉樹有 10 個葉結(jié)點(diǎn)，則該二叉樹中度為 2 的結(jié)的點(diǎn)個數(shù)為 ______________。 答案： 4 《軟件技術(shù)基礎(chǔ)》試題庫 3． 設(shè) SQ 為循環(huán)隊(duì)列，存儲在數(shù) 組 d[m] 中，則 SQ 出隊(duì)操作對其隊(duì)頭指針 front 的修改是 _______________ 。 答案： 4． n(n0) 個結(jié)點(diǎn)