第九章集合
一、 選擇題
1.若查詢每個記錄的概率均等，則在具有n個記錄的連續順序檔案中採用順序查詢法查詢乙個記錄，其平均查詢長度asl為( )。【北京航空航天大學 2000
一、8 （2分
a． (n-1)/2 b. n/2 c. (n+1)/2 d. n
2. 對n個元素的表做順序查詢時，若查詢每個元素的概率相同，則平均查詢長度為( ) 【南京理工大學1998
一、7（2分）】
a．（n+1）/2 b. n/2 c. n d. [（1+n）*n ]/2
3．順序查詢法適用於查詢順序儲存或鏈式儲存的線性表，平均比較次數為（（1））,二分法查詢只適用於查詢順序儲存的有序表，平均比較次數為（（2））。 在此假定n為線性表中結點數，且每次查詢都是成功的。【長沙鐵道學院 1997
四、3 (4分)】
a.n+1 b.2log2n c.logn d.n/2 e.nlog2n f.n2
4. 下面關於二分查詢的敘述正確的是南京理工大學 1996
一、3 （2分）】
a. 表必須有序，表可以順序方式儲存，也可以鍊錶方式儲存 c. 表必須有序，而且只能從小到大排列
b. 表必須有序且表中資料必須是整型，實型或字元型 d. 表必須有序，且表只能以順序方式儲存
5. 對線性表進行二分查詢時，要求線性表必須（ ）【燕山大學 2001
一、5 （2分）】
a.以順序方式儲存 b.以順序方式儲存,且資料元素有序 c.以鏈結方式儲存 d.以鏈結方式儲存,且資料元素有序
6．適用於折半查詢的表的儲存方式及元素排列要求為( ) 【南京理工大學 1997
一、6 （2分）】
a．鏈結方式儲存，元素無序 b．鏈結方式儲存，元素有序
c．順序方式儲存，元素無序 d．順序方式儲存，元素有序
7. 用二分（對半）查詢表的元素的速度比用順序法( ) 【南京理工大學 1998
一、11 （2分）】
a． 必然快 b. 必然慢 c. 相等 d. 不能確定
8．當在乙個有序的順序儲存表上查詢乙個資料時，即可用折半查詢，也可用順序查詢，但前者比後者的查詢速度
a．必定快 b.不一定 c. 在大部分情況下要快 d. 取決於表遞增還是遞減
【南京理工大學 1997
一、7 （2分）】
9. 具有12個關鍵字的有序表，折半查詢的平均查詢長度（ ）【中山大學 1998
二、10 （2分）】
a. 3.1b. 4c. 2.5d. 5
10. 折半查詢的時間複雜性為（ ）【中山大學 1999
一、15】
a. o（n2） b. o（n） c. o（nlogn） d. o（logn）
11．當採用分快查詢時，資料的組織方式為南京理工大學 1996
一、7 （2分）】
a．資料分成若干塊，每塊內資料有序
b．資料分成若干塊，每塊內資料不必有序，但塊間必須有序，每塊內最大（或最小）的資料組成索引塊
c. 資料分成若干塊，每塊內資料有序，每塊內最大（或最小）的資料組成索引塊
d. 資料分成若干塊，每塊（除最後一塊外）中資料個數需相同
12. 二叉查詢樹的查詢效率與二叉樹的( （1）)有關, 在 (（2）)時其查詢效率最低【武漢交通科技大學1996
一、2(4分)】
(1): a. 高度 b. 結點的多少 c. 樹型 d. 結點的位置
(2): a. 結點太多 b. 完全二叉樹 c. 呈單枝樹 d. 結點太複雜。
13. 要進行順序查詢，則線性表（1）；要進行折半查詢，則線性表（2）；若表中元素個數為n,則順序查詢的平均比較次數為（3）；折半查詢的平均比較次數為（4）。【北方交通大學 1999
一、2 （4分）】
（1）（2）：a. 必須以順序方式儲存； b. 必須以鏈式方式儲存；c. 既可以以順序方式儲存，也可以鏈式方式儲存；
d. 必須以順序方式儲存，且資料已按遞增或遞減順序排好；
e. 必須以鏈式方式儲存，且資料已按遞增或遞減的次序排好。
（3）（4）：a.n b.
n/2 c.n*n d.n*n/2 e.
log2n f.nlog2n g.(n+1)/2 h.
log2(n+1)
14．在等概率情況下,線性表的順序查詢的平均查詢長度asl為( （1） ),有序表的折半查詢的asl為( （2） ),對靜態樹表,在最壞情況下,asl為( （3） ),而當它是一棵平衡樹時,asl為 ( （4） ),在平衡樹上刪除乙個結點後可以通過旋轉使其平衡,在最壞情況下需( （5） )次旋轉。供選擇的答案：【上海海運學院 1999
二、3 （5分）】
（1）（2）（3）（4）（5）: a. o(1) b.
o( log2n ) c. o((log2n)2) d.o(nlog2n) e.
o(n)
15. 對大小均為n的有序表和無序表分別進行順序查詢,在等概率查詢的情況下,對於查詢失敗,它們的平均查詢長度是((1)) ,對於查詢成功,他們的平均查詢長度是((2))供選擇的答案: 【上海海運學院 1997
二、4 （3分）】
a. 相同的b.不同的
16．如果要求乙個線性表既能較快的查詢，又能適應動態變化的要求，則可採用( )查詢法。
a. 分快查詢 b. 順序查詢 c. 折半查詢 d. 基於屬性
【西安電子科技大學 2001應用
一、8 （2分）】
17. 既希望較快的查詢又便於線性表動態變化的查詢方法是北方交通大學 2000
二、4 （2分）】
a．順序查詢 b. 折半查詢 c. 索引順序查詢 d. 雜湊法查詢
18．分別以下列序列構造二叉排序樹，與用其它三個序列所構造的結果不同的是( ) 【合肥工業大學2000
一、4（2分）】
a．（100，80， 90， 60， 120，110，130） b.（100，120，110，130，80， 60， 90）
c.（100，60， 80， 90， 120，110，130） d. (100，80， 60， 90， 120，130，110)
19. 在平衡二叉樹中插入乙個結點後造成了不平衡，設最低的不平衡結點為a,並已知a的左孩子的平衡因子為0右孩子的平衡因子為1,則應作( ) 型調整以使其平衡。【合肥工業大學 2001
一、4 （2分）】
a. llb. lrc. rld. rr
20．下列關於m階b-樹的說法錯誤的是( ) 【南京理工大學 1997
一、9 （2分）】
a．根結點至多有m棵子樹 b．所有葉子都在同一層次上
c. 非葉結點至少有m/2 (m為偶數)或m/2+1（m為奇數）棵子樹 d. 根結點中的資料是有序的
21. 下面關於m階b樹說法正確的是( ) 【南京理工大學 1999
一、5 （2分）】
①每個結點至少有兩棵非空子樹； ②樹中每個結點至多有m一1個關鍵字;
③所有葉子在同一層上當插入乙個資料項引起b樹結點**後，樹長高一層。
abcd. ③
22. 下面關於b和b+樹的敘述中，不正確的是( ) 【北方交通大學 2001
一、17 （2分）】
a. b樹和b+樹都是平衡的多叉樹。 b. b樹和b+樹都可用於檔案的索引結構。
c. b樹和b+樹都能有效地支援順序檢索。 d. b樹和b+樹都能有效地支援隨機檢索。
23. m階b-樹是一棵( ) 【北京郵電大學 2000
二、2 （20/8分）】
a. m叉排序樹 b. m叉平衡排序樹 c. m-1叉平衡排序樹 d. m+1叉平衡排序樹
24. 在一棵含有n個關鍵字的m階b-樹中進行查詢，至多讀盤( )次。【中科院計算所 2000
一、6 （2分）】
a. log2n b. 1+log2n c. 1+log d. 1+log
25. m路b+樹是一棵(（1）) ，其結點中關鍵字最多為(（2）)個，最少(（3）)個。【中科院計算機 1999
一、5】
a. m路平衡查詢樹 b. m路平衡索引樹 c. m路ptrie樹 d. m路鍵樹 e. m-1f. m g. m+1
h. -1ij. +1
26在一棵m階的b+樹中, 每個非葉結點的兒子數s 應滿足武漢交通科技大學 1996
一、3 (4分) 】
a.≤s≤m b. ≤s≤m c. 1≤s≤ d. 1≤s≤
27. 設有一組記錄的關鍵字為，用鏈位址法構造雜湊表，雜湊函式為h（key）=key mod 13,雜湊位址為1的鏈中有（ ）個記錄。【南京理工大學 1997
一、4 （2分）】
資料結構課後習題答案第九章
第九章查詢 參 9.1 int seqsearch rectype r,keytype k 監視哨設在n個元素的公升序順序表低下標端，順序查詢關鍵字為k的資料 元素。若存在，則返回其在順序表中的位置，否則，返回0 r 0 key k i n while r i key k i if i 0 r i ...
資料結構作業系統第九章答案
判別給定二叉樹t是否為二叉排序樹。若是，則返回true，否則false 二叉樹的型別bitree定義如下 typedef struct elemtype typedef struct bitnode bitnode,bitree status isbstree bitree t 判別給定二叉樹t是否...
第九章梁板結構
專案一任務一 簡述鋼筋混凝土樓蓋按施工方法可分為哪幾類？各有何優缺點。任務二 簡述鋪板式混凝土樓蓋有哪幾種形式？其常用與何建築中及常用尺寸。任務三 簡述裝配式樓蓋的連線構造。任務四 簡述何為單向板，何為雙向板?專案二任務一 單向板樓蓋計算簡圖的內容包括哪些？以下圖為例確定板計算簡圖？任務二 單向板肋...