數(shù)據(jù)結構第9章例題與答案
第九章 集合一、 選擇題
1.若查找每個記錄的概率均等，則在具有n個記錄的連續(xù)順序文件中采用順序查找法查找一個記錄，其平均查找長度asl為( )�！颈本┖娇蘸教齑髮W 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．順序查找法適用于查找順序存儲或鏈式存儲的線性表，平均比較次數(shù)為（（1））,二分法查找只適用于查找順序存儲的有序表，平均比較次數(shù)為（（2））。 在此假定n為線性表中結點數(shù)，且每次查找都是成功的�！鹃L沙鐵道學院 1997 四、3 (4分)】
a.n+1 b.2log2n c.logn d.n/2 e.nlog2n f.n2
4. 下面關于二分查找的敘述正確的是 ( ) 【南京理工大學 1996 一、3 （2分）】
a. 表必須有序，表可以順序方式存儲，也可以鏈表方式存儲 c. 表必須有序，而且只能從小到大排列
b. 表必須有序且表中數(shù)據(jù)必須是整型，實型或字符型 d. 表必須有序，且表只能以順序方式存儲
5. 對線性表進行二分查找時，要求線性表必須（ ）【燕山大學 2001 一、5 （2分）】
a.以順序方式存儲 b.以順序方式存儲,且數(shù)據(jù)元素有序 c.以鏈接方式存儲 d.以鏈接方式存儲,且數(shù)據(jù)元素有序
6．適用于折半查找的表的存儲方式及元素排列要求為( ) 【南京理工大學 1997 一、6 （2分）】
a．鏈接方式存儲，元素無序 b．鏈接方式存儲，元素有序
c．順序方式存儲，元素無序 d．順序方式存儲，元素有序
7. 用二分（對半）查找表的元素的速度比用順序法( ) 【南京理工大學 1998 一、11 （2分）】
a． 必然快 b. 必然慢 c. 相等 d. 不能確定
8．當在一個有序的順序存儲表上查找一個數(shù)據(jù)時，即可用折半查找，也可用順序查找，但前者比后者的查找速度( )
a．必定快 b.不一定 c. 在大部分情況下要快 d. 取決于表遞增還是遞減
【南京理工大學 1997 一、7 （2分）】
9. 具有12個關鍵字的有序表，折半查找的平均查找長度（ ）【中山大學 1998 二、10 （2分）】
a. 3.1 b. 4 c. 2.5 d. 5
10. 折半查找的`時間復雜性為（ ）【中山大學 1999 一、15】
a. o（n2） b. o（n） c. o（nlogn） d. o（logn）
11．當采用分快查找時，數(shù)據(jù)的組織方式為 ( ) 【南京理工大學 1996 一、7 （2分）】
a．數(shù)據(jù)分成若干塊，每塊內數(shù)據(jù)有序
b．數(shù)據(jù)分成若干塊，每塊內數(shù)據(jù)不必有序，但塊間必須有序，每塊內最大（或最小）的數(shù)據(jù)組成索引塊
c. 數(shù)據(jù)分成若干塊，每塊內數(shù)據(jù)有序，每塊內最大（或最�。┑臄�(shù)據(jù)組成索引塊
d. 數(shù)據(jù)分成若干塊，每塊（除最后一塊外）中數(shù)據(jù)個數(shù)需相同
12. 二叉查找樹的查找效率與二叉樹的( （1）)有關, 在 (（2）)時其查找效率最低【武漢交通科技大學1996 一、2(4分)】
(1): a. 高度 b. 結點的多少 c. 樹型 d. 結點的位置
(2): a. 結點太多 b. 完全二叉樹 c. 呈單枝樹 d. 結點太復雜。
13. 要進行順序查找，則線性表（1）；要進行折半查詢，則線性表（2）；若表中元素個數(shù)為n,則順序查找的平均比較次數(shù)為（3）；折半查找的平均比較次數(shù)為（4）�！颈狈浇煌ù髮W 1999 一、2 （4分）】
（1）（2）：a. 必須以順序方式存儲； b. 必須以鏈式方式存儲；c. 既可以以順序方式存儲，也可以鏈式方式存儲；
d. 必須以順序方式存儲，且數(shù)據(jù)已按遞增或遞減順序排好；
e. 必須以鏈式方式存儲，且數(shù)據(jù)已按遞增或遞減的次序排好。
（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) http://www.dgxbdz.com/
【數(shù)據(jù)結構第9章例題與答案】相關文章：