數(shù)據(jù)結(jié)構(gòu)第九章《集合》選擇題及參考答案_跨考網(wǎng)

?? 1．若查找每個(gè)記錄的概率均等，則在具有n個(gè)記錄的連續(xù)順序文件中采用順序查找法查找一個(gè)記錄，其平均查找長度ASL為( )?！?a target="_blank">北京航空航天大學(xué) 2000 一、8 （2分）】

　　A．(n-1)/2 B．n/2 C．(n+1)/2 D．n

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

　　A．(N+1)/2??? B．N/2??? C．N??? D．[(1+N)*N ]/2

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

　　A．N+1??? B．2log2N??? C．logN??? D．N/2??? E．Nlog2N??? F．N2

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

　　A．表必須有序，表可以順序方式存儲(chǔ)，也可以鏈表方式存儲(chǔ)

　　C．表必須有序，而且只能從小到大排列

　　B．表必須有序且表中數(shù)據(jù)必須是整型，實(shí)型或字符型

　　D．表必須有序，且表只能以順序方式存儲(chǔ)

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

　　A．以順序方式存儲(chǔ)

　　B．以順序方式存儲(chǔ),且數(shù)據(jù)元素有序

　　C．以鏈接方式存儲(chǔ)

　　D．以鏈接方式存儲(chǔ),且數(shù)據(jù)元素有序

　　【參考答案】B

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

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

　　B．鏈接方式存儲(chǔ)，元素有序

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

　　D．順序方式存儲(chǔ)，元素有序

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

??? A．必然快??????? B．必然慢

??? C．相等????????? D．不能確定

??? 【參考答案】D

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

　　A．必定快????????????? B．不一定

　　C．在大部分情況下要快?? D．取決于表遞增還是遞減

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

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

　　A．3.1??????? B．4??????? C．2.5??????? D．5

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

　　A．O（n2）??? B．O（n）??? C．O（nlogn）??? D．O（logn）

　　【參考答案】D