第九章 集合
一、 选择题
$ r5 Y0 G! k# g) E3 f0 G0 e+ ~太原理工大学|太原理工大学论坛|太原理工大学BBS 1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。【北京航空航天大学 2000 一、8 (2分)】
6 `' Z$ V" f* \' Y- A% x' x( r太原理工大学,太原理工大学论坛 A. (n-1)/2 B. n/2 C. (n+1)/2 D. n
* C: l, `% T3 X8 _! E太原理工大学|太原理工大学论坛|太原理工大学BBS 2. 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( ) 【南京理工大学1998一、7(2分)】2 N$ y( U! g9 S
A.(N+1)/2 B. N/2 C. N D. [(1+N)*N ]/2
: I! J* A& p2 `/ |9 G. @) p太原理工大学|太原理工大学论坛|太原理工大学BBS 3.顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为((1)),二分法查找只适用于查找顺序存储的有序表，平均比较次数为((2))。 在此假定N为线性表中结点数，且每次查找都是成功的。【长沙铁道学院 1997 四、3 (4分)】www.tyutbbs.com; M( ~5 {; M# v. i8 Q* _
A.N+1 B.2log2N C.logN D.N/2 E.Nlog2N F.N2清泽论坛-太原理工大学网络家园+ r! J I8 m3 b( D" T' @% `3 s
4. 下面关于二分查找的叙述正确的是 ( ) 【南京理工大学 1996 一、3 (2分)】www.tyutbbs.com( d x8 [3 z: n- ?/ n* ^1 \
A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列
, m% n% C9 y! D/ J& l; y( ^ B. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储太原理工大学,太原理工大学论坛' b, C$ R2 k7 l/ Y
5. 对线性表进行二分查找时，要求线性表必须( )【燕山大学 2001 一、5 (2分)】太原理工大学,太原理工大学论坛$ B; W" v2 g. d7 c5 a' Z
A.以顺序方式存储 B.以顺序方式存储,且数据元素有序 C.以链接方式存储 D.以链接方式存储,且数据元素有序
5 d: E* m0 p6 u z' Z9 C3 J太原理工大学论坛[龙城水秀] 6.适用于折半查找的表的存储方式及元素排列要求为( ) 【南京理工大学 1997 一、6 (2分)】
* m0 { ~& _' V, p* a$ W6 y太原理工大学|太原理工大学论坛|太原理工大学BBS A.链接方式存储，元素无序 B.链接方式存储，元素有序太原理工大学,太原理工大学论坛9 H) G! w7 D4 x
C.顺序方式存储，元素无序 D.顺序方式存储，元素有序太原理工大学,太原理工大学论坛2 r- ]. H: [7 ?: C8 _# v
7. 用二分(对半)查找表的元素的速度比用顺序法( ) 【南京理工大学 1998 一、11 (2分)】
* I/ M4 e: B* n0 M9 c: d清泽论坛-太原理工大学网络家园 A. A. 必然快 B. 必然慢 C. 相等 D. 不能确定
$ Z; ]' p1 ~: K" S' n: e' r太原理工大学|太原理工大学论坛|太原理工大学BBS 8.当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( )* o0 a4 H. G0 U5 k
A.必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减
5 Q2 o; x/ \( r1 T; [* {/ m/ I" {: F 【南京理工大学 1997 一、7 (2分)】太原理工大学,太原理工大学论坛9 ?0 N# f* J, x! A% x
9. 具有12个关键字的有序表，折半查找的平均查找长度( )【中山大学 1998 二、10 (2分)】9 j. B& k6 j9 P; D9 Q# y: m8 p. ?
A. 3.1 B. 4 C. 2.5 D. 5
1 v M# R" Q5 L% W6 |" k6 O1 f* \太原理工大学,太原理工大学论坛 10. 折半查找的时间复杂性为( )【中山大学 1999 一、15】清泽论坛-太原理工大学网络家园& n$ d' @: h2 V- X; \. A
A. O(n2) B. O(n) C. O(nlogn) D. O(logn)
