【笔试题】【day22】

第一题（循环队列的元素个数）

循环队列的存储空间为 Q(1:200) ，初始状态为 front=rear=200 。经过一系列正常的入队与退队操作后，front=rear=1 ，则循环队列中的元素个数为（ ）
A 0或200
B 1
C 2
D 199

当front=rear的时候，我们的队列可能是满的，也可能是空的，我们无法判断是空的还是满的。如果想要区分的话，我们最好预留出一个位置，如果我们队尾指针的下一个位置就是队头指针，那么我们的队列就是满了，如果我们的队尾指针和队头指针处于同一个位置，那么就是对空。（队尾指针代表下一个元素要存放的位置）

A

第二题（二叉排序树插入规则）

已知数据元素为(34,76,45,18,26,54,92,65),按照依次插入节点的方法生成一棵二叉排序树，则该树的深度为()
A 7
B 6
C 4
D 5

D

第三题（线性探测的平均查找长度）

已知一个线性表（38，25，74，63，52，48），假定采用散列函数h（key) = key%7 计算散列地址，并散列存储在散列表A[0…6]中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为（）
A 1.5
B 1.7
C 2.0
D 2.3

查找38:1次
查找25:1次
查找74:2次
查找63:1次
查找52:4次
查找48:3次
一共是查找12次，12/6=2，也就是平均查找两次

C

第四题（关键字比较次数与初始序列无关的）

下面的排序方法中，关键字比较次数与记录的初始排列无关的是______。
A 希尔排序
B 冒泡排序
C 直接插入排序
D 直接选择排序

希尔排序是一种缩小增量的插入排序，插入排序与你选择的插入的数据是有关系的
冒泡排序也与初始的序列有关。
直接插入排序，同希尔排序
直接选择排序需要从我们的数据中找出最小的，然后再找出次小的，然后再找出第三小的，每一次寻找最小的话，我们都需要遍历一遍数组，所以关键字比较的次数与我们初始的排列是无关的。

D