数据结构练习第八章 查找

数据结构练习第八章查找

1.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )

A. 1，2，3

B. 9，5，2，3

C. 9，5，3

D. 9，4，2，3

2．设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（）。

A. O(1)

B. O(log

2

n) C. O(n) D. O(n2) 3．在二叉排序树中插入一个结点的时间复杂度为（）。

A. O(1)

B. O(n)

C. O(log

2

n) D. O(n2) 4．设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（）。

A. log

2n+1 B. log

2

n-1 C. log

2

n D. log

2

(n+1)

5．设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。

A. 25

B. 10

C. 7

D. 1

6．顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（）。A. O(n) B. O(n2) C. O(n1/2) D. O(1og

2

n) 7．设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为（）。

A. O(n)

B. O(n2)

C. O(nlog

2n) D. O(1og

2

n)

8．（）二叉排序树可以得到一个从小到大的有序序列。

A. 先序遍历

B.中序遍历

C. 后序遍历

D. 层次遍历9．设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（）。

A. 1

B. 2

C. 3

D. 4

10．设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选择（）。

A. 99

B. 97

C. 91

D. 93

11．在二叉排序树中插入一个关键字值的平均时间复杂度为（）。

A. O(n)

B. O(1og

2n) C. O(nlog

2

n) D. O(n2)

12．设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为( )。

A. A[1]，A[2]，A[3]，A[4]

B.A[1]，A[14]，A[7]，A[4]

C.A[7]，A[3]，A[5]，A[4]

D. A[7]，A[5] ，A[3]，A[4]

13．设散列表中有m个存储单元，散列函数H(key)= key % p，则p最好选择（）。

A. 小于等于m的最大奇数

B.小于等于m的最大素数

C. 小于等于m的最大偶数

D. 小于等于m的最大合数

14．设顺序表的长度为n，则顺序查找的平均比较次数为（）。

A. n

B. n/2

C. (n+1)/2

D. (n-1)/2

15．设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过（）次比较。

A. 1

B. 2

C. 3

D. 4

16．设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为（ ）。

A. 6

B. 11

C. 5 D . 6.5

17．设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为（ ）。

A . 4 B. 5 C. 6 D. 7

18．二叉排序树中左子树上所有结点的值均（ ）根结点的值。

A . < B. > C. = D. !=

19．设有n 个关键字具有相同的Hash 函数值，则用线性探测法把这n 个关键字映射到HASH 表中需要做（ ）次线性探测。

A. n 2

B. n(n+1)

C. n(n+1)/2 D . n(n-1)/2

20．用散列函数求元素在散列表中的存储位置时，可能会出现不同的关键字得到相同散列函数值的冲突现象。可用于解决上述问题的是( )

A.线性探测法

B.除留余数法

C.平方取中法

D.折叠法

21．

22．在线性表的散列存储中，若用m 表示散列表的长度，n 表示待散列存储的元

素的个数，则装填因子α等于（ ）。

A ．n/m

B ．m/n

C ．n/(n+m)

D ．m/(n+m)

23．从一棵B_树删除元素的过程中，若最终引起树根结点的合并，则新树高度

是（ ）。

A ．原树高度加1

B ．原树高度减1

C ．原树高度

D ．不确定

24．向二叉搜索树中插入一个元素时，其时间复杂度大致为（ ）。

Ａ.O （log 2n ） B. O(n) C. O(1) D. 0(nlog 2n) 25．5阶B 树中，每个结点最多有（）个关键码。

A ．2

B ．3

C ．4

D ．5

26．对一棵二叉排序树采用中根遍历进行输出的数据一定是（ ）

A.递增或递减序列

B.递减序列

C.无序序列

D.递增

序列

27．一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，查找成功时的比较次数为（ ）

A.1

B.2

C.4

D.8

28．若构造一棵具有n 个结点的二叉排序树，最坏的情况下其深度不超过( ) A. 2n B. n C. 2

1n + D. n+1 29．闭散列表中由于散列到同一个地址而引起的“堆积”现象，是( )

A.由同义词之间发生冲突引起的

B.由非同义词之间发生冲突引起的

C.由同义词之间或非同义词之间发生冲突引起的

D.由散列表“溢出”引起的

30．在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于( )

A.静态查找表

B.动态查找表

C.静态查找表与动态查找表

D.静态查找表或动态查找表

31．设一组记录的关键字key值为{62，50，14，28，19，35，47，56，83}，散列函数为H(key)=key mod 13，则它的开散列表中散列地址为1的链中的结点个数是（）

A．1 B.2 C．3 D.4

32．已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分检索值为90的元素时，检索成功需比较的次数是（）

A.1

B.2

C.3

D.4

33．闭散列表中由于散列到同一个地址而引起的“堆积”现象，是由（）

A.同义词之间发生冲突引起的

B.非同义词之间发生冲突引起的

C.同义词与非同义词之间发生冲突引起的

D.散列地址“溢出”引起的

34．在最坏的情况下，查找成功时二叉排序树的平均查找长度（）

A．小于顺序表的平均查找长度B．大于顺序表的平均查找长度

C．与顺序表的平均查找长度相同D．无法与顺序表的平均查找长度比较35．闭散列表中由于散列到同一个地址而引起的“堆积”现象，是由（）A．同义词之间发生冲突引起的

B．非同义词之间发生冲突引起的

C．同义词之间或非同义词之间发生冲突引起的

D．散列表“溢出”引起的

36．设有100个元素，用二分法查找时，最大比较次数是（）。

A．25 B．7 C．10 D．1 37．设有1000个元素，用二分法查找时，最小比较次数为（）

A．0 B．1 C．10 D．500

38．在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为( )。

A. n

B. n/2

C. (n+1)/2

D. (n-1)/2

39．对有14个数据元素的有序表R[14]进行折半搜索，搜索到R[3]的关键码等于给定值，此时元素比较顺序依次为（）。

A．R[0]，R[1]，R[2]，R[3] B．R[0]，R[13]，R[2]，R[3] C．R[6]，R[2]，R[4]，R[3] D．R[6]，R[4]，R[2]，R[3] 40．在一个有N个元素的有序单链表中查找具有给定关键字的结点，平均情况下的时间复杂性为( B )

A.O(1)

B.O(N)

C.0（N2）

D.O(NlogN)

41．对线性表进行二分查找时，要求线性表必须（B）

A.以顺序方式存储

B.以顺序方式存储,且数据元素有序

C.以链接方式存储

D.以链接方式存储,且数据元素有序

42．下列二叉排序树中查找效率最高的是( A )

A.平衡二叉树

B.二叉查找树

C.没有左子树的二叉排序树

D.没有右子树的二叉排序树

43．如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用

下列哪一种查找方法。A

A. 分块

B. 顺序

C. 折半

D. 哈希

44．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( C )

A.(100,80,90,60,120,110,130)

B.(100,120,110,130,80,60,90)

C.(100,60,80,90, 20,110,130)

D.(100,80,60,90,120,130,110)

45．下面关于B和B+树的叙述中，不正确的是(C )

A. B树和B+树都是平衡的多叉树。

B. B树和B+树都可用于文件的索引结构。

C. B树和B+树都能有效地支持顺序检索。

D. B树和B+树都能有效地支持随机检索。

46．m阶B-树是一棵( B )

A. m叉排序树

B. m叉平衡排序树

C. m-1叉平衡排序树

D.m+1叉平衡排序树

47．在一棵含有n个关键字的m阶B-树中进行查找，至多读盘( C )次。

48．一棵3阶B-树中含有2047个关键字，包括叶子结点层，该树的最大深度为( B )。

A, 11 B. 12 C. 13 D. 14

49．关于杂凑查找说法不正确的有几个( B ) （1）采用链地址法解决冲突时，查找一个元素的时间是相同的

（2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的

（3）用链地址法解决冲突易引起聚集现象

（4）再哈希法不易产生聚集

A. 1

B. 2

C. 3

D. 4 50．设哈希表长M=14，哈希函数H(KEY)=KEY MOD 11。表中已有4个结点：ADDR(15)=4， ADDR(38)=5，ADDR(61)=6，ADDR(84)=7，其余地址为空，如用二次探测再散列处理冲突，关键字为49的结点的地址是( D )。

A. 8

B. 3

C. 5

D. 9

51．散列函数有一个共同的性质，即函数值应当以( D )取其值域的每个值。

A. 最大概率

B. 最小概率

C. 平均概率

D. 同等概率52．将10个元素散列到100000个单元的哈希表中，则（C）产生冲突。A. 一定会 B. 一定不会 C. 仍可能会

53．长度为10的按关键字有序的查找表采用顺序组织方式。若采用折半查找方法，则在等概率情况下，查找失败时的ASL值是（D）

A.24/10

B.24/11

C.39/10

D.39/11

54．在采用拉链法处理冲突所构成的开散列表上查找某一关键字，在查找成功的情况下，所探测的这些位置上的键值（A）

A.一定都是同义词

B.不一定都是同义词

C.都相同

D.一定都不是同义词

55．二叉查找树的查找效率与二叉树的树型有关, 在 (C )时其查找效率最

低。

A. 结点太多

B. 完全二叉树

C. 呈单枝树

D. 结点太复杂。

56．具有12个关键字的有序表，折半查找的平均查找长度（A）

A. 3.1

B. 4

C. 2.5

D. 5

57．哈希查找中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存入哈希表中，至少要进行( C )次探测。

A． k B. k+1 C. k(k+1)/2 D.1+k(k+1)/2

58．对线性表进行二分查找时，要求线性表必须（B）

A.以顺序方式存储

B.以顺序方式存储,且数据元素有序

C.以链接方式存储

D.以链接方式存储,且数据元素有序

59.若查找每个元素的概率相等，则在长度为n 的顺序表上查找任一元素的平均查找长度为( D) 。

A. n

B. n+1

C. (n-1)/2

D. (n+1)/2

60.对长度为10 的顺序表进行查找，若查找前面 5 个元素的概率相同，均为1/8 ，查找后面5 个元素的概率相同，均为3/40 ，则查找任一元素的平均查找长度为( C) 。

A. 5.5

B. 5

C.39/8

D. 19/4

61.对长度为 3 的顺序表进行查找，若查找第一个元素的概率为1/2 ，查找第二个元素的概率为1/3 ，查找第三个元素的概率为1/6 ，则查找任一元素的平均查找长度为( A) 。

A .5/3

B .2 C. 7/3 D. 4/3

62.对长度为n 的单链有序表，若查找每个元素的概率相等，则查找任一元素的平均查找长度为( B) 。

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

63.对于长度为9 的顺序存储的有序表，若采用二分查找，在等概率情况下的平均查找长度为( A) 的9 分之一。

A .20 B. 18 C. 25 D. 22

64.对于长度为18 的顺序存储的有序表，若采用二分查找，则查找第15 个元素的查找长度为( B) 。

A. 3

B. 4

C. 5

D. 6

65.对于顺序存储的有序表(5,12,20,26,37,42,46,50,64) ，若采用二分查找，则查找元素26 的查找长度为( C) 。

A .2 B. 3 C. 4 D. 5

66.对具有n 个元素的有序表采用二分查找，则算法的时间复杂性为( D) 。

A. O (n)

B. O (n 2 )

C. O (1)

D. O (log 2 n)

67.在索引查找中，若用于保存数据元素的主表的长度为n ，它被均分为k 个子表，每个子表的长度均为n/k ，则索引查找的平均查找长度为( D) 。

A. n+k

B. k+n/k

C. (k+n/k)/2

D. (k+n/k)/2+1

68.在索引查找中，若用于保存数据元素的主表的长度为n ，它被均分为若干个子表，每个子表的长度均为s ，则索引查找的平均查找长度为( B ) 。

A. (n+s)/2

B. (n/s+s)/2+1

C. (n+s)/2+1 D . (n/s+s)/2

69.在索引查找中，若用于保存数据元素的主表的长度为144 ，它被均分为12 子表，每个子表的长度均为12 ，则索引查找的平均查找长度为( A) 。

A .13 B. 24 C. 12 D. 79

70.在索引查找中，若用于保存数据元素的主表的长度为117 ，它被均分为9 子表，则索引查找的平均查找长度为( B) 。

A. 11

B. 12 C .13 D. 9

71.在一棵深度为h 的具有n 个元素的二叉排序树中，查找所有元素的最长查找长度为( D) 。

A. n

B. log 2 n

C. (h+1)/2

D. h

72.从具有n 个结点的二叉搜索树中查找一个元素时，在平均情况下的时间复杂性大致为( C) 。

A. O (n)

B. O (1)

C. O (log 2 n)

D. O (n 2 )

73.从具有n 个结点的二叉搜索树中查找一个元素时，在最坏情况下的时间复杂性为( A) 。

A. O (n)

B. O (1)

C. O (log 2 n)

D. O (n 2 )

74.向具有n 个结点的二叉搜索树中插入一个元素时，其时间复杂性大致为( B ) 。

A. O (1) B .O (log 2 n ) C. O (n) D. O ( n log 2n )

75.根据n 个元素建立一棵二叉搜索树时，其时间复杂性大致为( D) 。

A. O (n) B .O (log 2 n ) C. O (n 2 ) D .O ( n log 2n )

76.在一棵平衡二叉排序树中，每个结点的平衡因子的取值范围是( A ) 。

A .-1 ~ 1 B. -2 ~ 2 C. 1 ~ 2 D. 0 ~ 1

77.若根据查找表(23,44,36,48,52,73,64,58) 建立开散列表，采用h(K)=K%13 计算散列地址，则元素64 的散列地址为( C) 。

A. 4

B. 8

C. 12

D. 13

78.若根据查找表(23,44,36,48,52,73,64,58) 建立开散列表，采用h(K)=K%7 计算散列地址，则散列地址等于 3 的元素个数( B) 。

A.1 B .2 C. 3 D. 4

79.若根据查找表(23,44,36,48,52,73,64,58) 建立开散列表，采用h(K)=K%7 计算散列地址，则同义词元素个数最多为( C) 。

A. 1

B. 2

C. 3

D. 4

80.若根据查找表建立长度为m 的闭散列表，采用线性探测法处理冲突，假定对一个元素第一次计算的散列地址为 d ，则下一次的散列地址为(D) 。

A. d

B. d+1

C. (d+1)/m

D. (d+1)%m

81.若根据查找表建立长度为m 的闭散列表，采用二次探测法处理冲突，假定对一个元素第一次计算的散列地址为 d ，则第四次计算的散列地址为( C) 。

A. (d+1)%m

B. (d-1)%m C . (d+4)%m D. (d-4)%m

82.在采用线性探测法处理冲突的闭散列表上，假定装填因子 a 的值为0.5 ，则查找任一元素的平均查找长度为(B) 。

A. 1

B. 1.5

C. 2 D .2.5

83.在采用链接法处理冲突的开散列表上，假定装填因子 a 的值为 4 ，则查找任一元素的平均查找长度为( A) 。

A. 3

B. 3.5

C. 4

D. 2.5

84.在散列查找中，平均查找长度主要与( C) 有关。

A.散列表长度

B.散列元素的个数

C.装填因子

D.处理冲突方法

85.对顺序表进行二分查找时，要求顺序表必须：

A.以顺序方式存储

B.以顺序方式存储，且数据元素有序

C.以链接方式存储

D.以链接方式存储，且数据元素有序

【解答】B

86.下列二叉排序树中查找效率最高的是：

A.平衡二叉树

B.二叉查找树

C.没有左子树的二叉排序树

D.没有右子树的二叉排序树

【解答】A

二、填空题

1．假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为_____________、___________、________和___________。（12，40），（），（74），（23,55，63）2．向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度___________。增加1

3. 为了能有效地应用HASH查找技术，必须解决的两个问题是________________和_____________________。构造一个好的HASH函数，确定解决冲突的方法4．设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较________次就可以断定数据元素X是否在查找表中。7

5．下列算法实现在顺序散列表中查找值为x的关键字，请在下划线处填上正确的语句。

struct record{int key; int others;};

int hashsqsearch(struct record hashtable[ ],int k)

{

int i,j; j=i=k % p;

while (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; if (i==j) return(-1);}

if (_______________________ ) return(j); else return(-1);

} j+1，hashtable[j].key==k

6．下列算法实现在二叉排序树上查找关键值k，请在下划线处填上正确的语句。

typedef struct node{int key; struct node *lchild; struct node *rchild;}bitree;

bitree *bstsearch(bitree *t, int k)

{

if (t==0 ) return(0);else while (t!=0)

if (t->key==k)_____________; else if (t->key>k) t=t->lchild;

else_____________;

} return(t)，t=t->rchild

7．根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为____________。3

8．设散列函数H(k)=k mod p，解决冲突的方法为链地址法。要求在下列算法划线处填上正确的语句完成在散列表hashtalbe中查找关键字值等于k的结点，成功时返回指向关键字的指针，不成功时返回标志0。

typedef struct node {int key; struct node *next;} lklist;

void createlkhash(lklist *hashtable[ ])

{

int i,k; lklist *s;

for(i=0;i

for(i=0;i

{

s=(lklist *)malloc(sizeof(lklist)); s->key=a[i];

k=a[i] % p; s->next=hashtable[k];_______________________;

}

}

hashtable[i]=0，hashtable[k]=s

9．下面程序段的功能是实现二分查找算法，请在下划线处填上正确的语句。

struct record{int key; int others;};

int bisearch(struct record r[ ], int k)

{

int low=0,mid,high=n-1;

while(low<=high)

{

________________________________;

if(r[mid].key==k) return(mid+1); else if(____________) high=mid-1;else low=mid+1;

}

return(0);

} mid=(low+high)/2，r[mid].key>k

10．设需要对5个不同的记录关键字进行排序，则至少需要比较_____________次，至多需要比较_____________次。4，10

11．设在长度为20的有序表中进行二分查找，则比较一次查找成功的结点数有_________个，比较两次查找成功有结点数有_________个。1，2

12．设二叉排序树的高度为h，则在该树中查找关键字key最多需要比较_________次。h

13．设散列表的长度为8，散列函数H(k)=k % 7，用线性探测法解决冲突，则根据一组初始关键字序列(8，15，16，22，30，32)构造出的散列表的平均查找长度是________。8/3

14．设一组初始记录关键字序列为(20，12，42，31，18，14，28)，则根据这些记录关键字构造的二叉排序树的平均查找长度是_______________________________。19/7

15．下面程序段的功能是实现在二叉排序树中插入一个新结点，请在下划线处填上正确的内容。

typedef struct node{int data;struct node *lchild;struct node *rchild;}bitree;

void bstinsert(bitree *&t,int k)

{

if(t==0)

{____________________________;t->data=k;t->lchild=t->rchild=0;} else if (t->data>k) bstinsert(t->lchild,k);else__________________________;

} t=(bitree *)malloc(sizeof(bitree))，bstinsert(t->rchild,k)

16．解决散列表冲突的两种方法是________________和__________________。开放定址法，链地址法

17．在一棵m阶B_树上，每个非树根结点的关键字数目最少为_______个，最多为_____个，其子树数目最少为______，最多为____。??1

m、m-1 、

2/-

??2/m、 m

18．从一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明_______，若元素的值小于根结点的值，则继续向________查找，若元素的大于根结点的值，则继续向________查找。查找成功、左子树、右子树

19．对于二分查找所对应的判定树，它既是一棵_ ____，又是一棵_____ __ ___。二叉搜索树、理想平衡树

20．二叉搜索树的中序遍历得到的结点序列为____ ____。有序序列21．从有序表（12，18，30，43，56，78，82，95）中依次二分查找43和56元素时，其查找长度分别为___________和__________。1 ， 3

22．假定对长度n=144的线性表进行索引查找，并假定每个子表的长度均为n,则进行索引查找的平均查找长度为__________，时间复杂度为___________。13，O(n)

23．一棵B-树中的所有叶子结点均处在_____________上。同一层

24．每次从无序表中顺序取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做_______排序；每次从无序表中挑选出一个最大或最小元素，把它交换到有序表中的一端，此种排序方法叫做_________排序。插入选择

25．对于线性表（18，25，63，50，41，32，90，66）进行散列存储时，若选用

H（K）=K%11作为散列函数，则散列地址为0的元素有______个，散列地址为3的元素有______个，散列地址为8的元素有______个。1 1 2

26．在一个具有n个结点的单链表中查找值为m的某结点，若查找成功，则需平均比较的结点数为____(n+1)/2________。

27．在一棵二叉排序树上按_____中序_______遍历得到的结点序列是一个有序序列。

28．实现二分查找的存储结构仅限于顺序存储结构，且其中元素排列必须是____有序的。

29．设顺序表的表长为n，且查找每个元素的概率相等，则采用顺序查找法查找表中任一元素，在查找成功时的平均查找长度为___(n+1)/2_______。

30．在索引顺序表上的查找分两个阶段：一是查找_____索引表_____，二是查找块。

31．一棵平衡二叉树中任一结点的平衡因子只可能是__-1，0，1_____。

n)_____。

32．二分查找的时间复杂度为__O(log

2

33．查找表的数据结构有别于线性表、树型结构等，其逻辑结构为____集合______。

34．长度为L的顺序表，采用设置岗哨方式顺序查找，若查找不成功，其查找长度为__L+1_______。

35．在开散列表上查找某元素时，通常分两步进行，首先必须计算该键值的散列地址，然后在地址指针所指_________同义词子表_______中查找该结点。36．对二叉排序树进行__中序______遍历，可得到排好序的递增结点序列。37．采用折半查找方法进行查找的数据序列应为____顺序存储____且___有序_____。

38．查找表的逻辑组织结构实际上是____集合____________结构。

39．对于具有n个元素的数据序列，采用顺序查找法，其平均查找长度为____(n+1)/2______。

40．快速排序算法在最差的情况下其时间复杂度是。O(n2)

41．在线性表的________存储中，对每一个元素只能采用顺序查找。链式42．采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为________________。（n+1）/2

43．以顺序查找方法从长度为n的线性表中查找一个元素时，平均查找长度为________，时间复杂度为________。(n+1)/2、O(n)

44．以二分查找方法从长度为n的线性有序表中查找一个元素时，平均查找长度小于等于________，时间复杂度为________。O(log

n)

2

45．以二分查找方法从长度为12的有序表中查找一个元素时，平均查找长度为________。37/12

46．以二分查找方法查找一个线性表时，此线性表必须是________存储的________表。顺序、有序

47．从有序表(12,18,30,43,56,78,82,95)中依次二分查找43和56元素时，其查找长度分别为________和________。1、3

48．对于二分查找所对应的判定树，它既是一棵_______，又是一棵________。二叉搜索树、理想平衡树

49．假定对长度n=50的有序表进行二分查找，则对应的判定树高度为________，判定树中前5层的结点数为________，最后一层的结点数为________。6、31、19

50．在索引表中，每个索引项至少包含有________域和________域这两项。索引、开始地址

51．假定一个线性表为(12,23,74,55,63,40,82,36)，若按Key % 3条件进行划分，使得同一余数的元素成为一个子表，则得到的三个子表分别为________、________和________。(12,63,36)、(55,40,82)、(23,74)

52．假定一个线性表为(”abcd”,”baabd”,”bcef”,”cfg”,”ahij”,”bkwte”,”ccdt”,

”aayb”)，若按照字符串的第一个字母进行划分，使得同一个字母被划分在一个子表中，则得到的a,b,c三个子表的长度分别为________、________和

________。3、3、2

53．在线性表的________存储中，无法查找到一个元素的前驱或后继元素。散列54．在线性表的________存储中，对每一个元素只能采用顺序查找。链接55．假定对线性表(38,25,74,52,48)进行散列存储，采用H(K)=K % 7作为散列函数，若分别采用线性探查法和链接法处理冲突，则对各自散列表进行查找的平均查找长度分别为_______和________。2、7/5

56．假定要对长度n=100的线性表进行散列存储，并采用链接法处理冲突，则对于长度m=20的散列表，每个散列地址的单链表的长度平均为________。5 57．在线性表的散列存储中，处理冲突有________和________两种方法。开放定址、链接

58．对于线性表(18,25,63,50,42,32,90)进行散列存储时，若选用H(K)=K % 9作为散列函数，则散列地址为0的元素有________个，散列地址为5的元素有________个。3、2

59．在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_________,

整个堆排序过程的时间复杂度为________________。O（log

2n）、O(nlog

2

n);

60. 顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为__ __次；当使用监视哨时，若查找失败，则比较关键字的次数为__ __。n n+1 61. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是。哈希查找

62. 在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为__________。6,9,11,12

63. 己知有序表为(12,18,24,35,47,50,62,83,90,115，134)当用二分法查找90时，需__________次查找成功，47时__________成功，查100时，需__________次才能确定不成功。2,4,3

64. 平衡二叉树又称_________，其定义是________。AVL树(高度平衡树，高度平衡的二叉排序树)，或为空二叉树，或二叉树中任意结点左子树高度与右子树高度差的绝对值小于等于1。

65. 在哈希函数H（key）=key%p中，p值最好取_________。小于等于表长的最大素数或不包含小于20的质因子的合数

66. 有一个2000项的表，欲采用等分区间顺序查找方法进行查找，则每块的理想长度是__(1)___，分成__(2)___块最为理想，平均查找长度是__(3)___。(1)45 (2)45 (3)46(块内顺序查找)

67. 假定有k个关键字互为同义词，若用线性探测再散列法把这k个关键字存入散列表中，至少要进行__________次探测。k(k+1)/2

68. 查找是非数值程序设计的一个重要技术问题，基本上分成__(1)__查找，__(2)__查找和__(3)__查找。处理哈希冲突的方法有__(4)__、__(5)__、__(6)__和__(7)__。

(1)顺序表 (2)树表 (3)哈希表 (4)开放定址方法

(1)(5)链地址方法 (6)再哈希 (7)建立公共溢出区

69. 在含有n个结点的二叉排序树中查找一个关键字，进行关键字比较次数最大值是。n

70. 一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有个结点。2k-1

71. 假定查找有序表A[1..12]中每个元素的概率相等，则进行二分查找时的平

均查找长度为__________ 37/12

72. 动态查找表和静态查找表的重要区别在于前者包含有__________和__________运算，而后者不包含这两种运算。插入删除

73. 对于具有144 个记录的文件，若采用分块查找法，且每块长度为8，则平均查找长度为__________. 14

74.以顺序查找方法从长度为n 的顺序表或单链表中查找一个元素时，平均查找长度为________ ，时间复杂性为________ 。(n+1)/2 O(n)

75.假定一个顺序表的长度为40 ，并假定查找每个元素的概率都相同，则在查找成功情况下的平均查找长度________ ，在查找不成功情况下的平均查找长度________ 。20.5 41

76.以二分查找方法从长度为50 的有序表中查找一个元素时，其查找长度不超过________ 。6

77.以二分查找方法在一个查找表上进行查找时，该查找表必须组织成________ 存储的________ 表。顺序有序

78.从有序表(12,18,30,43,56,78,82,95) 中分别二分查找43 和56 元素时，其查找长度分别为________ 和________ 。1 3

79.二分查找所对应的判定树，既是一棵_______ ，又是一棵________ 。二叉排序树理想平衡树

80.假定对长度n=50 的有序表进行二分查找，则对应的判定树高度为________ ，最后一层的结点数为________ 。6 19

81.假定在索引查找中，查找表长度为n ，每个子表的长度相等，设为s ，则进行成功查找的平均查找长度为____________ 。(n/s+s)/2+1

82.在索引查找中，假定查找表（即主表）的长度为96 ，被等分为8 个子表，则进行索引查找的平均查找长度为________ 。11

83.在一棵二叉排序树中，每个分支结点的左子树上所有结点的值一定________ 该结点的值，右子树上所有结点的值一定________ 该结点的值。小于大于

84.对一棵二叉排序树进行中序遍历时，得到的结点序列是一个________ 。有序序列

85.从一棵二叉排序树中查找一个元素时，若元素的值等于根结点的值，则表明_______ ，若元素的值小于根结点的值，则继续向________ 查找，若元素的值大于根结点的值，则继续向________ 查找。查找成功左子树右子树

86.向一棵二叉排序树中插入一个元素时，若元素的值小于根结点的值，则接着向根结点的________ 插入，若元素的值大于根结点的值，则接着向根结点的________ 插入。左子树右子树

87.从一棵具有n 个结点的二叉排序树中查找和插入元素的时间复杂性大致分别为________ 和________ 。O (log 2 n) O (log 2 n)

88.根据n 个元素建立一棵二叉排序树的时间复杂性大致为________ 。O ( n log 2n )

89.在一棵平衡二叉排序树中，每个结点的左子树高度与右子树高度之差的绝对值不超过________ 。1

90.假定对线性表(38,25,74,52,48) 进行散列存储，采用H(K)=K % 7 作为散列函数，采用线性探测法处理冲突，则在建立闭散列表的过程中，将会碰到________ 次存储冲突。5

91.假定对线性表(38,25,74,52,48) 进行散列存储，采用H(K)=K % 7 作为散列函数，采用线性探测法处理冲突，则平均查找长度为________ 。2

92.假定要对长度n=100 的线性表进行散列存储，并采用链接法处理冲突，则对于长度m=20 的开散列表，每个散列地址的单链表的长度平均为________ 。5

93.在线性表的散列存储中，装填因子 a 又称为装填系数，若用m 表示散列表的长度，n 表示线性表中的元素的个数，则 a 等于________ 。n/m

94.在开散列表中，处理冲突的方法为________ 法，在闭散列表中，处理冲突的方法为____________ 法。链接开放定址

95.对线性表(18,25,63,50,42,32,90) 进行散列存储时，若选用H(K)=K % 9 作为散列函数，则散列地址为0 的元素有________ 个，散列地址为 5 的元素有________ 个。3 2

96.在开散列表中插入一个元素的时间复杂性为__________ ，查找一个元素的时间复杂性为________ ，假定装填因子为 a 。1 1+ a /2

97.在采用线性探测法处理冲突的闭散列表中，假定装填因子为 a ，则进行成功查找的平均查找长度为___________ 。(1+1/(1- a ))/2

98.在采用二次探测法处理冲突的长度为m 的闭散列表中，假定根据散列函数求出一个元素的散列地址为 d ，则第五个后继散列地址为___________ 。(d+9)%m

99.在各种查找方法中，平均查找长度与结点个数无关的是。哈希查找法

三、判断题

1．（）分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。T

2．（）中序遍历二叉排序树可以得到一个有序的序列。T

3．（）当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。T 4．（）先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。T 5．（）如果两个关键字的值不等但哈希函数值相等，则称这两个关键字为同义词。T

6．（）分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。T

7．（）向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。F

8．（）顺序表查找指的是在顺序存储结构上进行查找。F

9．( )折半查找法的前提之一是线性表有序。√

10．( )一个单链表不能采用折半查找法进行查找。√

11．( )一个有序的单链表不能采用折半查找法进行查找。√

12．（）有序表的折半查找只适用于升序表。×

13．（）装载因子是散列表的一个重要参数，它反映了散列表的装满程度。√14．（）在散列检索中，“比较”操作一般也是不可避免的。√

15．（）哈希函数的选取平方取中法最好。×

16．（）哈希表的结点中只包含数据元素自身的信息，不包含任何指针。×17．（）折半查找与二元查找树的时间性能在最坏的情况下是相同的。×18．（）对于满足折半查找和分块查找条件的文件而言，无论它存放在何种介

质上，均能进行顺序查找、折半查找和分块查找。×

19．（）对无序表用二分法查找比顺序查找快。×

20．（）在二叉排序树中插入一个新结点，总是插入到叶结点下面。×21．（）N个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的。√

22．（）二元查找树的任何结点的左右子树都是二元查找树。√

23．（）B-树中所有结点的平衡因子都为零。√

24．（）B-树的插入算法中，通过结点的向上“分裂”，代替了专门的平衡调整。√

25．（）B+树既能索引查找也能顺序查找。√

26．（）适于对动态查找表进行高效率查找的组织结构是分块有序表。×27．（）如果完全二叉树从根结点开始按层次遍历的输序列为1,2,3,4,5,6,7,则该完全二叉树是二叉排序树。×

28．（）设有关键字n=2h-1，构成二叉排序树，每个关键字查找的概率相等，查找成功的ASL最大是n。√

29．（）若把堆看成是一棵完全二叉树，则该树一定是一棵二叉排序树。×30．（）中根遍历二元查找树所得序列一定是有序序列。√

31．（）m 阶B-树的任何一个结点的左右子树的高度都相等。√

32．（）非空的平衡二叉树中插入一个结点,原有结点中至少一个结点的平衡因子会改变。√

33．（）3阶的B_树是平衡的3路搜索树。反之，一棵平衡的3路搜索树是3阶B_树。×

34．（）若装填因子α为1，则向散列表中散列元素时一定会产生冲突。√35．（）随着装填因子α的增大，用闭散列法解决冲突，其平均搜索长度比用开散列法解决冲突时的平均搜索长度增长得慢。×

36．（）对二棵具有相同关键字集合的而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序却是一致的。√

37．（）采用线性探测再散列法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置为空，因为这会影响以后的查找。√

38．（）对无序表用二分法查找比顺序查找快。×

39．（）在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面。×

四、简答题

1．什么情况下二叉排序树的查找性能较好？什么情况下二叉排序树的查找性能最差？

【解答】当二叉排序树接近平衡二叉树或完全二叉树时查找性能较好，当二叉排序树为单边单枝二叉树时查找性能最差。

2．在哈希查找法中，为什么平均查找长度与关键字个数无关？

3．在哈希表中，发生冲突的可能性与哪些因素有关？为什么？

【解答】主要与哈希函数、装填因子α有关。如果用哈希函数计算的地址分布均匀，则冲突的可能性较小，如果装填因子α较小，则哈希表较稀疏，发生冲突的可能性较小。

4．给定表（39，14，22，8，65，28，88，29，67，13，10），试按元素在表中

的顺序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树。

5．设闭散列表容量为7（散列地址空间0..6），给定表（30，36，47，52，34）,散列函数H （K ）=K mod 6，采用线性探测法解决冲突，要求：

（1）构造散列表；

（2）求查找数34需要比较的次数。

6．对长度为20的有序表进行二分查找，试画出它的一棵判定树

【解答】

7．用二分查找法对一个长度为10的有序表进行查找，填写查找每一元素需要的比较次数。（8分）

元素下标

比较次数【解答】

8．一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设散列表为HT[0..12]，散列函数为H （key ）= key % 13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。

【解答】

查找成功的平均查找长度：ASL SUCC =14/10= 1.4

9. 证明若二叉排序树中的一个结点存在两个孩子，则它的中序后继结点没有左孩子，则它的中序前趋结点没有右孩子。【中国科学技术大学1998四(10分)】

【解答】证明：根据中序遍历的定义，该结点的中序后继是其右子树上按中序遍历的第一个结点：叶子结点或仅有右子树的结点；而其中序前驱是其左子树上按中序遍历的最后个结点：叶子结点或仅有左子树的结点。命题得证。

10. 回答问题并填空

（1）（2分）散列表存储的基本思想是什么？

0 1 2 3 4 5 6 7 8 9 10 11 12

（2）（4分）散列表存储中解决碰撞的基本方法有哪些？其基本思想是什么？（3）（４分）用分离的同义词子表解决碰撞和用结合的同义词表解决碰撞属于哪种基本方法？他们各有何特点？

（4）（３分）用线性探查法解决碰撞时，如何处理被删除的结点？为什么？（5）（２分）散列法的平均检索长度不随( )的增加而增加，而是随( )的增大而增加。

【山东工业大学 1999 四（15分）】

【解答】

(1)散列表存储的基本思想是用关键字的值决定数据元素的存储地址

(2)散列表存储中解决碰撞的基本方法：

①开放定址法形成地址序列的公式是：H

i =(H(key)+d

i

)% m，其中m是

表长，d

i 是增量。根据d

i

取法不同，又分为三种：

a．d

i

=1，2，…，m-1 称为线性探测再散列，其特点是逐个探测表空间，只要散列表中有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一散列地址。

b．d

i

=12，-12，22，-22，…， k2(k≤m/2) 称为二次探测再散列，它减少了聚集，但不容易探测到全部表空间，只有当表长为形如4j+3(j为整数)的素数时才有可能。

c．d

i

=伪随机数序列，称为随机探测再散列。

②再散列法 H

i =RH

i

(key) i=1，2，…，k，是不同的散列函数，即在同

义词产生碰撞时，用另一散列函数计算散列地址，直到解决碰撞。该方法不易产生“聚集”，但增加了计算时间。

③链地址法将关键字为同义词的记录存储在同一链表中，散列表地址区间用H[0..m-1]表示，分量初始值为空指针。凡散列地址为i(0≤i≤m-1)的记录均插在以H[i]为头指针的链表中。这种解决方法中数据元素个数不受表长限制，插入和删除操作方便，但增加了指针的空间开销。这种散列表常称为开散列表，而①中的散列表称闭散列表，含义是元素个数受表长限制。

④建立公共溢出区设H[0..m-1]为基本表，凡关键字为同义词的记录，都填入溢出区O[0..m-1]。

(3)用分离的同义词表和结合的同义词表解决碰撞均属于链地址法。链地址向量空间中的每个元素不是简单的地址，而是关键字和指针两个域，散列地址为i(0≤i≤m-1)的第一个关键字存储在地址空间向量下标为i的“关键字”域。前者的指针域是动态指针，指向同义词的链表，具有上面③的优缺点；后者实际是静态链表，同义词存在同一地址向量空间(从最后向前找空闲单元)，以静态指针(下标)相连。节省了空间，但易产生“堆积”，查找效率低。

(4)要在被删除结点的散列地址处作标记，不能物理的删除。否则，中断了查找通路。

(5)记录负载因子

11. 如何衡量hash函数的优劣？简要叙述hash表技术中的冲突概念，并指出三种解决冲突的方法。

【南京航空航天大学 1996 九.2 （6分）】

【解答】评价哈希函数优劣的因素有：能否将关键字均匀影射到哈希空间上，有无好的解决冲突的方法，计算哈希函数是否简单高效。由于哈希函数是压缩映像，冲突难以避免。解决冲突的方法见上面2题。

12. 在采用线性探测法处理冲突的散列表中，所有同义词在表中是否一定相邻？【西安电子科技大学2000计应用一.8 （5分）】

【解答】不一定相邻。哈希地址为i(0≤i≤m-1)的关键字，和为解决冲突形成的探测序列i的同义词，都争夺哈希地址i。

13. 设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10(di=12,22,32,…,)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。

【东北大学 2002 二 .2 （5分）】

succ

以关键字27为例：H(27)=27%7=6(冲突) H

1

=(6+1)%10=7(冲突)

H 2=(6+22)%10=0(冲突) H

3

=(6+33)%10=5 所以比较了4次。

14. 简要叙述B-树与B+树的区别?

【解答】m阶的B+树和B-树主要区别有三：

(1)有n棵子树的结点中含有n(B-树中n-1)个关键字；

(2)B+树叶子结点包含了全部关键字信息，及指向含关键字记录的指针，且叶子结点本身依关键字大小自小到大顺序链接；

(3)B+树的非终端结点可以看成是索引部分，结点中只含其子树(根结点)中最大(或最小)关键字。B+树的查找既可以顺序查找，也可以随机查找，B-只能随机查找。

15. 设散列表长度为14 ，散列函数h(x)=，其中 i为健值中第一个字母在字母表中的序号，若健值的输入顺序为Jan, Feb,

Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec，用拉链法处理冲突，要求：（1）构造散列表（2）求出在等概率情况下，查找成功的平均查找长度。【厦门大学 2001 二.2 （24%/3分）】

【解答】ASL

succ

=19/12

16. 选取哈希函数Ｈ（key）=key mod 7,用链地址法解决冲突。试在０-６的散列地址空间内对关键字序列｛31,23,17,27,19,11,13,91,61,41｝构造哈希表，并计算在等概率下成功查找的平均查找长度。【大连海事大学2001 八 (10分)】【解答】

17. 对以下关键字序列建立哈希表：(SUN,MON,TUE,WED,THU,FRI,SAT)，哈希函数为H（K）=（关键字中第一个字母在字母表中的序号）MOD 7，用线性探测法处理冲突，求构造一个装填因子为0.7的哈希表;并分别计算出在等概率情况下查找成功与不成功的平均查找长度。

【西北大学 2000 二.3 (5分)】

【解答】

α

ASL

succ unsucc

18. 设散列表为HT [0..12],即表的大小为m=13。现采用双散列法解决冲突。散列函数和再散列函数分别为：

H

(key)=key % 13; 注:%是求余数运算(=mod)

H

i =(H

i-1

+REV(key+1)%11+1) % 13; i=1,2,3,…,m-1

其中，函数REV（x）表示颠倒10进制数x的各位，如REV（37）=73，REV（7）=7等。若插入的关键码序列为(2,8,31,20,19,18,53,27)。

(1)(8分)试画出插入这8个关键码后的散列表；

(2)(5分)计算搜索成功的平均搜索长度ASL。【清华大学2000八(13分）】【解答】

suss

19.在B-树和B+树中查找关键字时，有什么不同？【东北大学 2002 一 .5 (2分)】

【解答】

在B-树中查找关键字从根结点开始，从根往下查找结点，然后在结点内查找关键字，得出查找成功与否的结论。B+树的非终端结点是索引部分，其查找从根开始，从根往下查到关键字后，要继续查到最下层结点，得到查找成功与否的结论。

另外，B+树还可以在最下层从最小关键字开始，从左往右进行顺序查找，B-树则不能作顺序查找。

20. 含9个叶子结点的3阶B-树中至少有多少个非叶子结点？含10个叶子结点的3阶B-树中至多有多少个非叶子结点？

【东南大学2005一.1(5分）】【北京轻工业学院2000八(10分）】

【解答】

含9个叶子结点的3阶B-树至少有4个非叶子结点，当每个非叶子结点均含3棵子树，第三层是叶子结点时就是这种情况。当4层3阶B-树有10个叶子结点时，非叶子结点达到最大值8个：其中第一层1个，第二层2个，第三层5个。

21.一棵二叉排序树结构如下,各结点的值从小到大依次为1-9，请标出各结点的值。

【厦门大学 2002 八.2 （5分）】

【解答】

22. 在查找和排序算法中，监视哨的作用是什么？

【解答】监视哨的作用是免去查找过程中每次都要检测整个表是否查找完毕，提高了查找效率。

23. 输入一个正整数序列（53,17,12,66,58,70,87,25,56,60），试完成下列各题。

（1）按次序构造一棵二叉排序树BS。(2) 依此二叉排序树，如何得到一个从大到小的有序序列？

（2）画出在此二叉排序树中删除“66”后的树结构。【同济大学2001一(10分)】【解答】

24. 设二叉排序树中关键字由1到1000的整数组成，现要查找关键字为363的结点，下述关键字序列哪一个不可能是在二叉排序树中查到的序列？说明原因。（1）51,250,501,390,320,340,382,363

（2）24,877,125,342,501,623,421,363

【东北大学 2002 一 .3 (4分)】

【解答】

25. 用分块查找法，有2000项的表分成多少块最理想？每块的理想长度是多少？若每块长度为25 ，平均查找长度是多少？

【解答】分成45块，每块的理想长度为45(最后一块长20)。若每块长25，则平均查找长度为ASL=(80+1)/2+(25+1)/2=53.5(顺序查找确定块)，或ASL=19(折半查找确定块)。

五、应用题

1. 设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。

【解答】2,ASL=91*1+2*2+3*4+4*2)=25/9

2．设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给出构造过程。略

3．已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为[0..6]，假定选用的散列函数是H（K）= K mod 7，若发生冲突采用线性探查法处理，试：（1）计算出每一个元素的散列地址并在下图中填写出散列表：

（2

(22)=(1+1) mod 7=2; ….冲突【解答】H(36)=36 mod 7=1; H

１

H(15)=15 mod 7=1;….冲突 H

(22)=(2+1) mod 7=3;

2

(15)=(1+1) mod 7=2;

H

１

H(40)=40 mod 7=5;

H(63)=63 mod 7=0;

数据流图试题及答案

【问题1】（1）费用单 （2）待租赁房屋列表 （3）看房请求 （4）变更房屋状态请求 【问题2】（5）房主信息文件 （6）租赁者信息文件 （7）房屋信息文件 （8）看房记录文件 【问题3】（1）起点：房主终点：变更房屋状态数据流名称：变更房屋状态请求 （2）起点：租赁者终点：登记租赁者信息数据流名称：租赁者信息 （3）起点：租赁者终点：安排租赁者看房数据流名称：看房请求试题一（共15分） 阅读以下说明和图，回答问题1至问题4，将解答填入答题纸的对应栏内。 【说明】 某高校欲开发一个成绩管理系统，记录并管理所有选修课程的学生的平时成绩和考试成绩，其主要功能描述如下： 1. 每门课程都有3到6个单元构成，每个单元结束后会进行一次测试，其成绩作为这门课程的平时成绩。课程结束后进行期末考试，其成绩作为这门课程的考试成绩。 2. 学生的平时成绩和考试成绩均由每门课程的主讲教师上传给成绩管理系统。

3. 在记录学生成绩之前，系统需要验证这些成绩是否有效。首先，根据学生信息文件来确认该学生是否选修这门课程，若没有，那么这些成绩是无效的；如果他的确选修了这门课程，再根据课程信息文件和课程单元信息文件来验证平时成绩是否与这门课程所包含的单元相对应，如果是，那么这些成绩是有效的，否则无效。 4. 对于有效成绩，系统将其保存在课程成绩文件中。对于无效成绩，系统会单独将其保存在无效成绩文件中，并将详细情况提交给教务处。在教务处没有给出具体处理意见之前，系统不会处理这些成绩。 5. 若一门课程的所有有效的平时成绩和考试成绩都已经被系统记录，系统会发送课程完成通知给教务处，告知该门课程的成绩已经齐全。教务处根据需要，请求系统生成相应的成绩列表，用来提交考试委员会审查。 6. 在生成成绩列表之前，系统会生成一份成绩报告给主讲教师，以便核对是否存在错误。主讲教师须将核对之后的成绩报告返还系统。 7. 根据主讲教师核对后的成绩报告，系统生成相应的成绩列表，递交考试委员会进行审查。考试委员会在审查之后，上交一份成绩审查结果给系统。对于所有通过审查的成绩，系统将会生成最终的成绩单，并通知每个选课学生。 现采用结构化方法对这个系统进行分析与设计，得到如图1-1所示的顶层数据流图和图1-2所示的0层数据流图。 图1-1 顶层数据流图

《数据结构》习题汇编08_第八章_查找_试题

数据结构课程（本科）第七章试题 一、单项选择题 1.若搜索每一个元素的概率相等，则在长度为n的顺序表上搜索到表中任一元素的平均搜索长度为 （）。 A. n B. n+1 C. (n-1)/2 D. (n+1)/2 2.对长度为10的顺序表进行搜索，若搜索前面5个元素的概率相同，均为1/8，搜索后面5个元素的概 率相同，均为3/40，则搜索到表中任一元素的平均搜索长度为（）。 A. 5.5 B. 5 C. 39/8 D. 19/4 3.对长度为3的顺序表进行搜索，若搜索第一个元素的概率为1/2，搜索第二个元素的概率为1/3，搜索 第三个元素的概率为1/6，则搜索到表中任一元素的平均搜索长度为（）。 A. 5/3 B. 2 C. 7/3 D. 4/3 4.对长度为n的有序单链表，若搜索每个元素的概率相等，则顺序搜索到表中任一元素的平均搜索长度 为（）。 A. n/2 B. (n+1)/2 C. (n-1)/2 D. n/4 5.对于长度为n的有序顺序表，若采用折半搜索，则对所有元素的搜索长度中最大的为（）的值 的向上取整。 A. log2(n+1) B. log2n C. n/2 D. (n+1)/2 6.对于长度为n的有序顺序表，若采用折半搜索，则对所有元素的搜索长度中最大的为（）的值 的向下取整加一。 A. log2(n+1) B. log2n C. n/2 D. (n+1)/2 7.对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（） 的值除以9。 A. 20 B. 18 C. 25 D. 22 8.对于长度为18的有序顺序表，若采用折半搜索，则搜索第15个元素的搜索长度为（）。 A. 3 B. 4 C. 5 D. 6 9.对具有n个元素的有序顺序表进行折半搜索，则搜索任一元素的时间复杂度为（）。 A. O(n) B. O(n2) C. O(1) D. O(log2n) 10.在一棵高度为h的具有n个元素的二叉搜索树中，搜索所有元素的搜索长度中最大的为（）。 A. n B. log2n C. (h+1)/2 D. h+1 11.从具有n个结点的二叉搜索树中搜索一个元素时，在等概率情况下进行成功搜索的时间复杂度大致为 （）。 A. O(n) B. O(1) C. O(log2n) D. O(n2)

数据结构第八章习题及答案

习题八查找 一、单项选择题 1．顺序查找法适合于存储结构为（）的线性表。 A．散列存储 B. 顺序存储或链式存储 C. 压缩存储 D. 索引存储 2.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。 A． (n-1)/2 B. n/2 C. (n+1)/2 D. n 3．适用于折半查找的表的存储方式及元素排列要求为( ) A．链接方式存储，元素无序 B．链接方式存储，元素有序 C．顺序方式存储，元素无序 D．顺序方式存储，元素有序 4．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( ) A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减5．当采用分块查找时，数据的组织方式为 ( ) A．数据分成若干块，每块内数据有序 B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块 C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D. 数据分成若干块，每块（除最后一块外）中数据个数需相同 6．二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法（）。 A．正确 B. 错误 7. 二叉查找树的查找效率与二叉树的(（1） )有关, 在 (（2） )时其查找效率最低。 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。 8．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( )查找法。 A. 分快查找 B. 顺序查找 C. 折半查找 D. 基于属性 9．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( )。 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) 10．下图所示的4棵二叉树,( )是平衡二叉树。 （A）（B）（C）（D） 11．散列表的平均查找长度（）。 A．与处理冲突方法有关而与表的长度无关 B．与处理冲突方法无关而与表的长度有关 C．与处理冲突方法有关且与表的长度有关 D．与处理冲突方法无关且与表的长度无关 12. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（）个

数据结构C语言版第八章 查找

第八章查找 重点难点 要求理解"查找表"的结构特点以及各种表示方法的适用性；熟练掌握顺序查找和折半查找的方法；熟悉描述折半查找过程的判定树的构造方法；熟练掌握二叉排序树的构造和查找方法；理解二叉平衡树的构造过程；理解B-和B+树的特点、基本操作和二者的区别。熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别；掌握各种不同查找方法之间的区别和各自的适用情况，能按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。 典型例题 1.若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试在下述两种情况下分别讨论两者在等概率时的平均查找长度： (1)查找不成功，即表中无关键字等于给定值K的记录； (2)查找成功，即表中有关键字等于给定值K的记录。 【解】查找不成功时，需进行n+1次比较才能确定查找失败。因此平均查找长度为n+1，这时有序表和无序表是一样的。 查找成功时，平均查找长度为(n+1)/2,有序表和无序表也是一样的。因为顺序查找与表的初始序列状态无关。 2.画出对长度为18的有序的顺序表进行二分查找的判定树，并指出在等概率时查找成功的平均查找长度，以及查找失败时所需的最多的关键字比较次数。 【解】 等概率情况下，查找成功的平均查找长度为： ASL=(1+2*2+3*4+4*8+5*3)/18=3.556 查找失败时，最多的关键字比较次树不超过判定树的深度，此处为5. 3.为什么有序的单链表不能进行折半查找?

【解】因为链表无法进行随机访问，如果要访问链表的中间结点，就必须先从头结点开始进行依次访问，这就要浪费很多时间，还不如进行顺序查找，而且，用链存储结构将无法判定二分的过程是否结束，因此无法用链表实现二分查找。 4.设二叉排序树中关键字互不相同，则其中最小元必无左孩子，最大元必无右孩子。此命题是否正确?最小元和最大元一定是叶子吗?一个新结点总是插在二叉排序树的某叶子上吗? 【解】此命题正确。假设最小元有左孩子，则根据二叉排序树性质，此左孩子应比最小元更小，如此一来就产生矛盾了，因此最小元不可能有左孩子，对于最大元也是这个道理。 但最大元和最小元不一定是叶子，它也可以是根、内部结点(分支结点)等，这得根据插入结点时的次序而定。 新结点总是作为叶子插入在二叉排序树中的。 5.在一棵m阶的B-树中，当将一关键字插入某结点而引起该结点的分裂时，此结点原有多少个关键字?若删去某结点中的一个关键字，而导致结点合并时，该结点中原有几个关键字? 【解】在一棵m阶的B-树中，若由于一关键字的插入某结点而引起该结点的分裂时，则该结点原有m-1个关键字。 若删去某结点中一个关键字而导致结点合并时，该结点中原有┌m/2┐-1个关键字。6.设散列表长度为11，散列函数h(x)=x%11,给定的关键字序列为：1，13，13，34，38，33，27，22.试画出分别用拉链法和线性探查法解决冲突时所构造的散列表，并求出在等概率情况下，这两种方法查找成功和失败时的平均查找长度。请问装填因子的值是什么? 答： (1)拉链法如下图： T[0..10] ┌──┐ 0││→ 33 → 22 →∧ ├──┤ 1││→ 1 → 12 →34→ ∧ ├──┤ 2││→ 13 →∧ ├──┤ 3│ ∧ │ ├──┤ 4│ ∧ │ ├──┤ 5││→ 38 → 27 →∧ ├──┤ 6│ ∧ │ ├──┤ 7│∧ │

数据流图画法

数据流图（DFD）画法要求 一、数据流图（DFD） 1.数据流图的基本符号 数据流图由基本符号组成，见图5－4－1所示。 图5－4－1 数据流图的基本符号 例：图5－4－2是一个简单的数据流图，它表示数据X从源S流出，经P加工转换成Y，接着经P加工转换为Z，在加工过程中从F中读取数据。 图5－4－2数据流图举例 下面来详细讨论各基本符号的使用方法。 2.数据流 数据流由一组确定的数据组成。例如“发票”为一个数据流，它由品名、规格、单位、单价、数量等数据组成。数据流用带有名字的具有箭头的线段表示，名字称为数据流名，表示流经的数据，箭头表示流

向。数据流可以从加工流向加工，也可以从加工流进、流出文件，还可以从源点流向加工或从加工流向终点。 对数据流的表示有以下约定： 对流进或流出文件的数据流不需标注名字，因为文件本身就足以说明数据流。而别的数据流则必须标出名字，名字应能反映数据流的含义。 数据流不允许同名。 两个数据流在结构上相同是允许的，但必须体现人们对数据流的不同理解。例如图5－4－3(a)中的合理领料单与领料单两个数据流，它们的结构相同，但前者增加了合理性这一信息。 两个加工之间可以有几股不同的数据流，这是由于它们的用途不同，或它们之间没有联系，或它们的流动时间不同，如图5－4－3(b)所示。 （a）（b）（c） 图5－4－3 简单数据流图举例 数据流图描述的是数据流而不是控制流。如图5-4-3 (c)中，“月末”只是为了激发加工“计算工资”，是一个控制流而不是数据流，所以应从图中删去。 3.加工处理 加工处理是对数据进行的操作，它把流入的数据流转换为流出的数据流。每个加工处理都应取一个名字表示它的含义，并规定一个编号用来标识该加工在层次分解中的位置。名字中必须包含一个动词，例如“计算”、“打印”等。 对数据加工转换的方式有两种： 改变数据的结构，例如将数组中各数据重新排序；

从数据流程图导出初始结构图方法模板

从数据流程图导出初始结构图方法 下面分别讨论经过”变换分析”和”事务分析”技术, 导出”变换型”和”事务型”初始结构图的技术。 1．变换分析 根据系统说明书, 能够决定数据流程图中, 哪些是系统的主处理。主处理一般是几股数据流汇合处的处理, 也就是系统的变换中心, 即逻辑输入和逻辑输出之间的处理。 确定逻辑输入——离物理输入端最远的, 但仍可被看作系统输入的那个数据流即为逻辑输入。确定方法是从物理输入端开始, 一步步向系统的中间移动, 直至达到这样一个数据流: 它已不能再被看作为系统的输入, 则其前一个数据流就是系统的逻辑输入。确定逻辑输出——离物理输出端最远的, 但仍可被看作系统输出的那个数据流即为逻辑输出。方法是从物理输出端开始, 一步步向系统的中间反方向移动, 直至达到这样一个数据流: 它已不能再被看作为系统的输出, 则其后一个数据流就是系统的逻辑输出。对系统的每一股输入和输出, 都用上面的方法找出相应的逻辑输入、输出。逻辑输入和逻辑输出之间的加工, 就是系统的主加工。如图4-24所示。

图4-24(a)初始DFD图 图4-24(b)找系统的主加工 2) 设计模块的顶层和第一层 ”顶层模块”也叫主控模块, 其功能是完成整个程序要做的工作。在与主加工对应的位置上画出主模块。系统结构的”顶层”设计后, 下层的结构就按输入、变换、输出等分支来分解。 设计模块结构的第一层: 为逻辑输入设计一个输入模块, 它的功能是向主模块提供数据; 为逻辑输出设计一个输出模块, 它的功能是输出主模块提供的数据; 为主加工设计一个变换模块, 它的功能是将逻辑输入变换成逻辑输出。 第一层模块同顶层主模块之间传送的数据应与数据流程图相对应。这里主模块控制并协调第一层的输入、变换、输出模块的工作。( 3) 设计中、下层模块 由自顶向下、逐步细化的过程, 为每一个上层模块设计下属模块。输入模块的功能是向它的调用模块提供数据, 由两部分组成: 一部分是接受输入数据; 另一部分是将这些数据变换成其调用模块所

数据结构练习第八章-查找

数据结构练习第八章查找 1.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 2．设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（）。 A. O(1) B. O(log 2 n) C. O(n) D. O(n2) 3．在二叉排序树中插入一个结点的时间复杂度为（）。 A. O(1) B. O(n) C. O(log 2 n) D. O(n2) 4．设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（）。 A. log 2n+1 B. log 2 n-1 C. log 2 n D. log 2 (n+1) 5．设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。 A. 25 B. 10 C. 7 D. 1 6．顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（）。A. O(n) B. O(n2) C. O(n1/2) D. O(1og 2 n) 7．设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为（）。 A. O(n) B. O(n2) C. O(nlog 2n) D. O(1og 2 n) 8．（）二叉排序树可以得到一个从小到大的有序序列。 A. 先序遍历 B.中序遍历 C. 后序遍历 D. 层次遍历9．设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（）。 A. 1 B. 2 C. 3 D. 4 10．设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选择（）。 A. 99 B. 97 C. 91 D. 93 11．在二叉排序树中插入一个关键字值的平均时间复杂度为（）。 A. O(n) B. O(1og 2n) C. O(nlog 2 n) D. O(n2) 12．设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为( )。 A. A[1]，A[2]，A[3]，A[4] B.A[1]，A[14]，A[7]，A[4] C.A[7]，A[3]，A[5]，A[4] D. A[7]，A[5] ，A[3]，A[4] 13．设散列表中有m个存储单元，散列函数H(key)= key % p，则p最好选择（）。 A. 小于等于m的最大奇数 B.小于等于m的最大素数 C. 小于等于m的最大偶数 D. 小于等于m的最大合数 14．设顺序表的长度为n，则顺序查找的平均比较次数为（）。 A. n B. n/2 C. (n+1)/2 D. (n-1)/2 15．设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过（）次比较。 A. 1 B. 2 C. 3 D. 4

数据结构 第八章 查找自测题

第9章查找自测卷姓名班级 一、填空题（每空1分，共10分） 1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是。 2. 线性有序表（a1，a2，a3，…，a256）是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索次。设有100个结点，用二分法查找时，最大比较次数是。 3. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结 点数为；比较四次查找成功的结点数为；平均查找长度为。 4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素比较大小。 5. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是。 6. 散列法存储的基本思想是由决定数据的存储地址。 7. 有一个表长为m的散列表，初始状态为空，现将n（n

数据流图试题及答案

数据流图试题及答案https://www.wendangku.net/doc/3012824795.html,work Information Technology Company.2020YEAR

【问题1】（1）费用单 （2）待租赁房屋列表 （3）看房请求 （4）变更房屋状态请求 【问题2】（5）房主信息文件 （6）租赁者信息文件 （7）房屋信息文件 （8）看房记录文件 【问题3】（1）起点：房主终点：变更房屋状态数据流名称：变更房屋状态请求 （2）起点：租赁者终点：登记租赁者信息数据流名称：租赁者信息 （3）起点：租赁者终点：安排租赁者看房数据流名称：看房请求 试题一（共15分） 阅读以下说明和图，回答问题1至问题4，将解答填入答题纸的对应栏内。【说明】 某高校欲开发一个成绩管理系统，记录并管理所有选修课程的学生的平时成绩和考试成绩，其主要功能描述如下： 1. 每门课程都有3到6个单元构成，每个单元结束后会进行一次测试，其成绩作为这门课程的平时成绩。课程结束后进行期末考试，其成绩作为这门课 程的考试成绩。

2. 学生的平时成绩和考试成绩均由每门课程的主讲教师上传给成绩管理系统。 3. 在记录学生成绩之前，系统需要验证这些成绩是否有效。首先，根据学生信息文件来确认该学生是否选修这门课程，若没有，那么这些成绩是无效的；如果他的确选修了这门课程，再根据课程信息文件和课程单元信息文件来验证平时成绩是否与这门课程所包含的单元相对应，如果是，那么这些成绩是有效的，否则无效。 4. 对于有效成绩，系统将其保存在课程成绩文件中。对于无效成绩，系统会单独将其保存在无效成绩文件中，并将详细情况提交给教务处。在教务处没有给出具体处理意见之前，系统不会处理这些成绩。 5. 若一门课程的所有有效的平时成绩和考试成绩都已经被系统记录，系统会发送课程完成通知给教务处，告知该门课程的成绩已经齐全。教务处根据需要，请求系统生成相应的成绩列表，用来提交考试委员会审查。 6. 在生成成绩列表之前，系统会生成一份成绩报告给主讲教师，以便核对是否存在错误。主讲教师须将核对之后的成绩报告返还系统。 7. 根据主讲教师核对后的成绩报告，系统生成相应的成绩列表，递交考试委员会进行审查。考试委员会在审查之后，上交一份成绩审查结果给系统。对于所有通过审查的成绩，系统将会生成最终的成绩单，并通知每个选课学生。 现采用结构化方法对这个系统进行分析与设计，得到如图1-1所示的顶层数据流图和图1-2所示的0层数据流图。 图1-1 顶层数据流图

数据结构第8章 查找 答案

第8章 查找 测试题 及答案 一、填空题 1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。 2. 线性有序表（a 1，a 2，a 3，…，a 256)是从小到大排列的，对一个给定的值k ，用二分法检索表中与k 相等的元素，在查找不成功的情况下，最多需要检索 8 次。设有100个结点，用二分法查找时，最大比较次数是 7 。 3. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。 解：显然，平均查找长度＝O （log 2n ）<5次（25）。但具体是多少次，则不应当按照公式 )1(log 12++=n n n ASL 来计算（即（21×log 221）/20＝4.6次并不正确！）。因为这是在假设n ＝2m -1的情况下推导出来的公式。应当用穷举法罗列： 全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL ＝74/20=3.7 ！！！ 4．【计研题2000】折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。 5. 在各种查找方法中，平均查找长度与结点个数n 无关的查找方法是 散列查找 。 6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。 7. 有一个表长为m 的散列表，初始状态为空，现将n （n

数据结构练习8

第八章查找 习题 9．1 判断题(在你认为正确的题后的括号中打√，否则打X)。 (1)用来惟一区分文件中不同记录的属性或属性组称为主关键字。( ) (2)查找成功与否的关键在于是否按主关键字查找。( ) (3)顺序文件必须用一片地址连续的存储空间来存放。( ) (4)只有在顺序存储结构上才能采用顺序查找方法。( ) (7)只要按值有序排列的线性表采用顺序存储结构就可以采用折半查找方法。( ) (8)建立稠密索引的优点是节省存储空间。( ) (9)分块查找的效率与文件中的记录被分成多少块有关。( ) (10)分块查找过程是首先查找索引表，然后再到相应的块中具体查找记录。( ) (11)B-树和B十树都是用来实现动态索引的。( ) (12)在B-树上可以进行顺序查找。( 1 (13)在B+树上可以进行顺序查找。／ 1 (14)采用散列方法存储线性表，不能存储数据元素之间的关系。( ) (15)在散列文件中进行查找不涉及关键字的比较。( ) (16)散列冲突是指同一个关键字对应了多个不同的散列地址。( ) (17)散列表的负载因子等于存人散列表中的关键字的个数。( ) (18)在散列表的查找过程中，关键字的比较次数与表中关键字的数目直接相关。( ) (19)在利用线性探测法处理冲突的散列表中，散列函数值相同的关键字总是存放在一片地址连续的存储单元中。 (20)在采用链地址法处理冲突的散列表中，散列函数值相同的关键字是链接在同一个链表中的。( ) 9．2单项选择题。 (1)衡量查找算法性能好坏的主要标准是。 A．参加比较的关键字值的多少 B．被查找的关键字值在关键字序列中的位置 C.关键字序列中是否存在被查找关键字值 D．关键字值的平均比较次数的多少 (2)顺序查找方法的优点之一是—。· A．对于被查找对象几乎没有限制B．适合排序连续顺序文件的查找 C.适合链接顺序文件的查找D．查找时间效率高 (3)对线性表采用折半查找，该线性表必须。 A．元素按值有序排列B．采用顺序结构 C．元素按值有序排列，并且采用顺序存储结构 n元素按值有序排列，并且采用链式存储结构 (4)下面的说法中，不正确的是——。 A．折半查找方法不适用于按值有序链接的链表的查找 B．折半查找方法适用于按值有序的顺序表的查找 C.折半查找方法适用于按关键字值大小有序排列的顺序文件的查找 D．折半查找方法适用于排序连续顺序文件的查找 (5)在有序表(k1，k2，…，k9，)中采用折半查找方法查找99次，其中，至少有一个元素被比较了99次，该元素是——。

数据流图(DFD)专题讲解

数据流图(DFD)专题讲解 ——解题的方法与技巧 1.首先要懂得数据流图设计要略 有时为了增加数据流图的清晰性，防止数据流的箭头线太长，减少交叉绘制数据流条数，一般在一张图上可以重复同名的数据源点、终点与数据存储文件。如某个外部实体既是数据源点又是数据汇点，可以在数据流图的不同的地方重复绘制。在绘制时应该注意以下要点： (1)自外向内，自顶向下，逐层细化，完善求精。 (2)保持父图与子图的平衡。 为了表达较为复杂问题的数据处理过程，用一个数据流图往往不够。一般按问题的层次结构进行逐步分解，并以分层的数据流图反映这种结构关系。根据层次关系一般将数据流图分为顶层数据流图、中间数据流图和底层数据流图，除顶层图外，其余分层数据流图从0开始编号。对任何一层数据流图来说，称它的上层数据流图为父图，在它的下一层的数据流图为子图。 顶层数据流图只含有一个加工，表示整个系统;输入数据流和输出数据流为系统的输入数据和输出数据，表明了系统的范围，以及与外部环境的数据交换关系。 底层数据流图是指其加工不能再分解的数据流图，其加工称为“原子加工”。 中间数据流图是对父层数据流图中某个加工进行细化，而它的某个加工也可以再次细化，形成子图。中间层次的多少，一般视系统的复杂程度而定。 任何一个数据流子图必须与它上一层父图的某个加工对应，二者的输入数据流和输出数据流必须保持一致，此即父图与子图的平衡。父图与子图的平衡是数据流图中的重要性质，保证了数据流图的一致性，便于分析人员阅读和理解。 在父图与子图平衡中，数据流的数目和名称可以完全相同;也可以在数目上不相等，但是可以借助数据字典中数据流描述，确定父图中的数据流是由子图中几个数据流合并而成的，也即子图是对父图中加工和数据流同时进行分解，因此也属于父图与子图的平衡，如图1所示。

数据结构第8章 查找 答案

第8章查找测试题及答案一、填空题 1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是顺序查找（线性查找）。 2. 线性有序表（a，a，a，…，a)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相123256等的元素，在 查找不成功的情况下，最多需要检索8 次。设有100个结点，用二分法查找时，最大比较次 数是7。 3. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1； 比较两次查找成功的结点数为 2；比较四次查找成功的结点数为 8；平均查找长度为 3.7。 5解：显然，平均查找长度＝O（logn）<5次（2）。但具体是多少次，则不应当按照公式2m来计算（即 （21×log21）/20＝4.6次并不正确！）。因为这是在假设n＝2-1的情况下22n推导出来的公式。应当用穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL＝74/20=3.7 ！！！4．【计研 题2000】折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20， 它将依次与表中元素 28，6，12，20比较大小。 5. 在各种查找方法中，平均查找长度与结 点个数n无关的查找方法是散列查找。 6. 散列法存储的基本思想是由关键字的值决定数 据的存储地址。 7. 有一个表长为m的散列表，初始状态为空，现将n（n

数据结构第8章查找练习题

一、单选题 1．下列查找方法中，不属于动态的查找方法是( )。 A ．二叉排序树法 B ．平衡树法 C ．散列法 D ．二分查找法 2．适用于静态的查找方法为( )。 A ．二分查找、二叉排序树查找 B ．二分查找、索引顺序表查找 C ．二叉排序树查找、索引顺序表查找 D ．二叉排序树查找、散列法查找 3．静态查找表与动态查找表二者的根本差别在于( )。 A ．它们的逻辑结构不一样 B ．施加在其上的操作不同 C ．所包含的数据元素的类型不一样 D ．存储实现不一样 4．对长度为10的顺序表进行查找，若查找前面5个元素的概率相同，均为1/8，查找后面5个元素的概率相同，均为3/40，则查找任一元素的平均查找长度为( )。 A ．5.5 B ．5 C ．39/8 D ．19/4 5．( )存储方式适用于折半查找。 A ．键值有序的单链表 B ．键值有序的顺序表 C ．键值有序的双链表 D ．键值无序的顺序表 6．对线性表进行二分查找时，要求线性表必须( )。 A ．以顺序方式存储 B ．以链接方式存储 C ．顺序存储，且结点按关键字有序排序 D ．链式存储，且结点按关键字有序排序 7．在索引顺序表中查找一个元素，可用的且最快的方法是( )。 A ．用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找 B ．用顺序查找法确定元素所在块，再用二分查找法在相应块中查找 C ．用二分查找法确定元素所在块，再用顺序查找法在相应块中查找 D ．用二分查找法确定元素所在块，再用二分查找法在相应块中查找 8．在索引查找中，若主表长度为144，它被均分为12子表，每个子表的长度均为12，则索引查找的平均查找长度为( )。 A ．13 B ．24 C ．12 D ．79 9．由同一关键字集合构造的各棵二叉排序树( )。 A ．形态和平均查找长度都不一定相同 B ．形态不一定相同，但平均查找长度相同 C ．形态和平均查找长度都相同 D ．形态相同，但平均查找长度不一定相同 10．对二叉排序树进行( )，可以得到各结点键值的递增序列。 A ．先根遍历 B ．中根遍历 C ．层次遍历 D ．后根遍历 11．下述序列中，哪个可能是在二叉排序树上查找35时所比较过的关键字序列？ A ．2，25，40，39，53，34，35 B ．25，39，2，40，53，34，35 C ．53，40，2，25，34，39，35 D ．39，25，40，53，34，2，35 12．在A VL 树中，每个结点的平衡因子的取值范围是( )。 A ．-1~1 B ．-2~2 C ．1~2 D ．0~1 13．在AVL 树中，任一结点的( )。 A ．左、右子树的高度均相同 B ．左、右子树高度差的绝对值不超过1 C ．左、右子树的结点数均相同 D ．左、右子树结点数差的绝对值不超过1 14．下面关于B 树和B +树的叙述中，不正确的是 A ．都是平衡的多叉树 B ．都是可用于文件的索引结构 C ．都能有效地支持顺序检索 D ．都能有效地支持随机检索 15．右图是一棵( )。 2822221915100528 2610

数据流图(DFD)专题讲解

数据流图(DFD)专题讲解 一.解题当中考生表现出的特点 由于这是下午考试的第一道题，所以很多考生从考前的紧张氛围当中逐渐平静下来开始答题，头脑还比较清醒，阅读起来比较流畅，速度还可以，自我感觉不错。可偏偏这道题有很多人不能全取15分，纠其原因有以下一些特点： 1.拿卷就做，不全面了解试卷，做到心中有数。这样会导致在解题过程当中缺少一种整体概念，不能明确自己在哪些题上必需拿分(多花时间)，哪些题上自己拿不了分(少花时间)。这样，在解题时目标就会明确很多。 2.速度快，读一遍题就开始动手做。 3.速度慢，用手指逐个字的去看，心想看一遍就能做出题来。 4.在阅读题目时，不打记，不前后联系起来思考。 5.边做边怀疑边修改，浪费时间。 6.缺少的数据流找不准，可去掉的文件找不出来。 7.由于缺少项目开发经验，对一些事务分析不知如何去思考。 8.盲目乐观，却忽略了答题格式，丢了不应该丢的分。 二.解题的方法与技巧 1.首先要懂得数据流图设计要略。 有时为了增加数据流图的清晰性，防止数据流的箭头线太长，减少交叉绘制数据流条数，一般在一张图上可以重复同名的数据源点、终点与数据存储文件。如某个外部实体既是数据源点又是数据汇点，可以在数据流图的不同的地方重复绘制。在绘制时应该注意以下要点：

(1)自外向内，自顶向下，逐层细化，完善求精。 (2)保持父图与子图的平衡。 为了表达较为复杂问题的数据处理过程，用一个数据流图往往不够。一般按问题的层次结构进行逐步分解，并以分层的数据流图反映这种结构关系。根据层次关系一般将数据流图分为顶层数据流图、中间数据流图和底层数据流图，除顶层图外，其余分层数据流图从0 开始编号。对任何一层数据流图来说，称它的上层数据流图为父图，在它的下一层的数据流图为子图。 顶层数据流图只含有一个加工，表示整个系统;输入数据流和输出数据流为系统的输入数据和输出数据，表明了系统的范围，以及与外部环境的数据交换关系。 底层数据流图是指其加工不能再分解的数据流图，其加工称为“原子加工”。 中间数据流图是对父层数据流图中某个加工进行细化，而它的某个加工也可以再次细化，形成子图。中间层次的多少，一般视系统的复杂程度而定。 任何一个数据流子图必须与它上一层父图的某个加工对应，二者的输入数据流和输出数据流必须保持一致，此即父图与子图的平衡。父图与子图的平衡是数据流图中的重要性质，保证了数据流图的一致性，便于分析人员阅读和理解。 在父图与子图平衡中，数据流的数目和名称可以完全相同;也可以在数目上不相等，但是可以借助数据字典中数据流描述，确定父图中的数据流是由子图中几个数据流合并而成的，也即子图是对父图中加工和数据流同时进行分解，因此也属于父图与子图的平衡，如图1所示。

数据流图与功能构图

数据流图与功能构图

————————————————————————————————作者：————————————————————————————————日期：

XXX系统结构化概要设计 （文档封面及目录格式与以前作业相同） 1.文档说明(5分) 1.1文档目的 //说明本文档的目的和作用

1.2文档范围 //说明本文档描述的主要内容 1.3读者对象 //说明可能的读者，比如详细设计、编码人员和测试人员 1.4参考文档 //说明编写该文档需要的参考资料，比如《用户需求说明书》和《需求分析规格说明书》等1.5术语与缩写解释 //说明本文档与具体业务无关的技术术语，比如数据流、模块、关系表等 2.项目背景(2分) //说明项目的需求来源以及用户的基本需求，可以参考《用户需求说明书》。 3.需求分析结果(3分) //此章节描述需求分析的分层数据流图 3.1顶层数据流图 //将基于结构化数据流图的《需求分析规格说明书》中顶层数据流图展示出来，无须进行修改（原样拷贝粘贴）

3.2第一层数据流图

3.3第二层数据流图 1. 处理临过期商品子系统 …… 3.n 第n层数据流图 4.基于功能需求的初始功能结构图(50分) //结合以上分层的数据流图，将整个系统对应的数据流图划分成多个功能相对独立的子系统，每个子系统由一个或多个结合紧密的加工组成。比如教科书第100页，从“医院就诊管理系统”的第一层数据流图可以看出，它由三个相对功能独立的子系统组成，分别是挂号子系统、问诊子系统、交费取药子系统。 4.1子系统1 处理临过期商品子系统 4.1.1数据流图(分数占20%)

数据流图与功能结构图

XXX系统结构化概要设计 （文档封面及目录格式与以前作业相同） 1.文档说明(5分) 1.1文档目的 //说明本文档的目的和作用

1.2文档范围 //说明本文档描述的主要内容 1.3读者对象 //说明可能的读者，比如详细设计、编码人员和测试人员 1.4参考文档 //说明编写该文档需要的参考资料，比如《用户需求说明书》和《需求分析规格说明书》等1.5术语与缩写解释 //说明本文档与具体业务无关的技术术语，比如数据流、模块、关系表等 2.项目背景(2分) //说明项目的需求来源以及用户的基本需求，可以参考《用户需求说明书》。 3.需求分析结果(3分) //此章节描述需求分析的分层数据流图 3.1顶层数据流图 //将基于结构化数据流图的《需求分析规格说明书》中顶层数据流图展示出来，无须进行修改（原样拷贝粘贴）

3.2第一层数据流图

3.3第二层数据流图 1. 处理临过期商品子系统 …… 3.n 第n层数据流图 4.基于功能需求的初始功能结构图(50分) //结合以上分层的数据流图，将整个系统对应的数据流图划分成多个功能相对独立的子系统，每个子系统由一个或多个结合紧密的加工组成。比如教科书第100页，从“医院就诊管理系统”的第一层数据流图可以看出，它由三个相对功能独立的子系统组成，分别是挂号子系统、问诊子系统、交费取药子系统。 4.1子系统1 处理临过期商品子系统 4.1.1数据流图(分数占20%)

4.1.2 功能结构图(分数占50%) // 画出对应的功能结构图，主模块名字和子系统名字一致

4.1.3功能模块说明(分数占30%) // 为功能结构图中每一个模块写一份处理说明和一份接口说明，格式如下： 1.模块名字1（与功能结构图中名字相同） (1)处理说明 // 参见教科书155页7.7.1 (2)接口说明 // 参见教科书155页7.7.2，只需要说明入口参数、返回值、下属模块、上级模块2.模块名字2 (1)处理说明 (2)接口说明 …… 4.2子系统2 定价子系统 4.2.1数据流图