數(shù)據(jù)結(jié)構(gòu)第9章例題與答案

一、 選擇題

1.若查找每個(gè)記錄的概率均等，則在具有n個(gè)記錄的連續(xù)順序文件中采用順序查找法查找一個(gè)記錄，其平均查找長(zhǎng)度asl為( )。【北京航空航天大學(xué) 2000 一、8 （2分）】

a． (n-1)/2 b. n/2 c. (n+1)/2 d. n

2. 對(duì)n個(gè)元素的表做順序查找時(shí)，若查找每個(gè)元素的概率相同，則平均查找長(zhǎng)度為( ) 【南京理工大學(xué)1998一、7（2分）】

a．（n+1）/2 b. n/2 c. n d. [（1+n）*n ]/2

3．順序查找法適用于查找順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)的線性表，平均比較次數(shù)為（（1））,二分法查找只適用于查找順序存儲(chǔ)的有序表，平均比較次數(shù)為（（2））。 在此假定n為線性表中結(jié)點(diǎn)數(shù)，且每次查找都是成功的�！鹃L(zhǎng)沙鐵道學(xué)院 1997 四、3 (4分)】

a.n+1 b.2log2n c.logn d.n/2 e.nlog2n f.n2

4. 下面關(guān)于二分查找的敘述正確的是 ( ) 【南京理工大學(xué) 1996 一、3 （2分）】

a. 表必須有序，表可以順序方式存儲(chǔ)，也可以鏈表方式存儲(chǔ) c. 表必須有序，而且只能從小到大排列

b. 表必須有序且表中數(shù)據(jù)必須是整型，實(shí)型或字符型 d. 表必須有序，且表只能以順序方式存儲(chǔ)

5. 對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須（ ）【燕山大學(xué) 2001 一、5 （2分）】

a.以順序方式存儲(chǔ) b.以順序方式存儲(chǔ),且數(shù)據(jù)元素有序 c.以鏈接方式存儲(chǔ) d.以鏈接方式存儲(chǔ),且數(shù)據(jù)元素有序

6．適用于折半查找的表的存儲(chǔ)方式及元素排列要求為( ) 【南京理工大學(xué) 1997 一、6 （2分）】

a．鏈接方式存儲(chǔ)，元素?zé)o序 b．鏈接方式存儲(chǔ)，元素有序

c．順序方式存儲(chǔ)，元素?zé)o序 d．順序方式存儲(chǔ)，元素有序

7. 用二分（對(duì)半）查找表的元素的速度比用順序法( ) 【南京理工大學(xué) 1998 一、11 （2分）】

a． 必然快 b. 必然慢 c. 相等 d. 不能確定

8．當(dāng)在一個(gè)有序的順序存儲(chǔ)表上查找一個(gè)數(shù)據(jù)時(shí)，即可用折半查找，也可用順序查找，但前者比后者的查找速度( )

a．必定快 b.不一定 c. 在大部分情況下要快 d. 取決于表遞增還是遞減

【南京理工大學(xué) 1997 一、7 （2分）】

9. 具有12個(gè)關(guān)鍵字的有序表，折半查找的平均查找長(zhǎng)度（ ）【中山大學(xué) 1998 二、10 （2分）】

a. 3.1 b. 4 c. 2.5 d. 5

10. 折半查找的時(shí)間復(fù)雜性為（ ）【中山大學(xué) 1999 一、15】

a. o（n2） b. o（n） c. o（nlogn） d. o（logn）

11．當(dāng)采用分快查找時(shí)，數(shù)據(jù)的組織方式為 ( ) 【南京理工大學(xué) 1996 一、7 （2分）】

a．?dāng)?shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序

b．?dāng)?shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)不必有序，但塊間必須有序，每塊內(nèi)最大（或最�。┑臄�(shù)據(jù)組成索引塊

c. 數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序，每塊內(nèi)最大（或最�。┑臄�(shù)據(jù)組成索引塊

d. 數(shù)據(jù)分成若干塊，每塊（除最后一塊外）中數(shù)據(jù)個(gè)數(shù)需相同

12. 二叉查找樹的查找效率與二叉樹的( （1）)有關(guān), 在 (（2）)時(shí)其查找效率最低【武漢交通科技大學(xué)1996 一、2(4分)】

(1): a. 高度 b. 結(jié)點(diǎn)的多少 c. 樹型 d. 結(jié)點(diǎn)的位置

(2): a. 結(jié)點(diǎn)太多 b. 完全二叉樹 c. 呈單枝樹 d. 結(jié)點(diǎn)太復(fù)雜。

13. 要進(jìn)行順序查找，則線性表（1）；要進(jìn)行折半查詢，則線性表（2）；若表中元素個(gè)數(shù)為n,則順序查找的平均比較次數(shù)為（3）；折半查找的平均比較次數(shù)為（4）。【北方交通大學(xué) 1999 一、2 （4分）】

（1）（2）：a. 必須以順序方式存儲(chǔ)； b. 必須以鏈?zhǔn)椒绞酱鎯?chǔ)；c. 既可以以順序方式存儲(chǔ)，也可以鏈?zhǔn)椒绞酱鎯?chǔ)；

d. 必須以順序方式存儲(chǔ)，且數(shù)據(jù)已按遞增或遞減順序排好；

e. 必須以鏈?zhǔn)椒绞酱鎯?chǔ)，且數(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.szmdbiao.com/

【數(shù)據(jù)結(jié)構(gòu)第9章例題與答案】相關(guān)文章：

職稱英語(yǔ)綜合類概括大意練習(xí)例題07-08

大學(xué)四級(jí)英語(yǔ)翻譯參考例題及譯文06-24

第100次微笑10-11

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)心得體會(huì)10-01

小學(xué)六年級(jí)上冊(cè)數(shù)學(xué)補(bǔ)充習(xí)題第56-66頁(yè)答案(蘇教版)(2)06-20

第59屆國(guó)際聾人節(jié)06-30

關(guān)于第4號(hào)臺(tái)風(fēng)的通知10-21

環(huán)保法第42條05-13

小學(xué)秋季開學(xué)第廣播稿09-02

今年是第52屆世界電信日10-08