一、单选题（共15道题，共45分）

1、设有98个已排序列元素，采用二分法查找时，最大比较次数是（)。

 A .49

 B .8

 C .20

 D 7

2、用某种排序方法对关键字序列｛25,84,21,47,15,27,68,35,20）进行排序时，序列的变化情况如下：

20,15,21,25,47,27,68,35,84

15,20,21,25,35,27,47,68,84

15,20,21,25,27,35,47,68,84

则采用的方法是（)

 A ．快速排序

 B ．直接选择排序

 C ．希尔排序

 D ．堆排序

3、下列排序算法中，其时间复杂度和记录的初始排列无关的是（)

 A ．插入排序

 B ．堆排序

 C ．快速排序

 D ．冒泡排序

4、如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（）方法最快。

 A ．冒泡排序

 B ．快速排序

 C ．希尔排序

 D ．堆排序

5、设循环队列的结构是

 typedef struct ( DataType data [ MaxSize ]; int front , rear :) Queue ;若有一个 Queue 类型的队列 Q ，试问判断队列满的条件应为（)。

 A . Q . front == Q . rear 

 B . Qufront - Q . rar == MaxSize 

 C . Q front + Q . rear == MaxSize 

 D . O front ==( Q . rear +1)% MaxSize 

6、判断一个表达式中左右括号是否匹配，采用

 A ．线性表的顺序存储

 B ．队列

 C ．线性表的链式存储

 D ．栈

7、若用邻接矩阵 A =(010

                                   101

                                    010)

表示一个联通图，则该图共有(）个顶点

 A .9

 B .3

 C .6

 D .1

8、关于二叉排序树，下面说法正确的是

 A ．二叉排序树是动态数表，查找失败时插入新节点时，会引起树的重新分裂和组合

B ．在二叉排序树中进行查找，关键字的比较次数不超过节点数的1/2

 C ．用逐点插入法构造二叉排序树，若先后插入的关键字有序，二叉排序树的深度最大

对一旦排序树进行尽席偏历可得到有序序列

D.对二叉树排序进行层序遍历得到有序序列

9、给定一个最小堆 H ，使用数组存储它。假定最开始数组中有5个数字，按顺序分别是：2,3,5,8,10。然后依次向该堆插入（两个数字7和1，请问插入数字后该数组的内容变为

 A .1.3.2.8,10.7.5

B.5,8,2.3,1,7.10

 C 3.2.10.1,5.8,7

D.2,8.10.7.5,3.1

10、在一棵四元树中，度为4的结点数为4个，度为3的结点数为3个，度为2的结点数为2个，度为1的结点数为1个，则度为0的结点数为（）个

 A .0

 B.1

 C .10

 D .21

11、进程从运行状态进入就绪状态的原因可能是

 A ．等待某一事件

 B ．被选中占有处理机

 C ．时间片用完

 D ．等待的事件已发生

12、以下哪种存储管理方式不会产生内存碎片。

 A ．固定分区式存储管理

 B ．分页式存储管理

 C ．分段式存储管理

 D ．段页式存储管理

13、 GROUP BY 子句的作用是什么？

 A ．组的筛选条件

 B ．查询结果的分组条件

 C ．限定返回的行的判断条件

 D ．对结果集进行排序

14、在 IP 地址方案中，159.226.181.1是一个（)

 A . A 头地址

 B . B 类地址

 C . C 类地址

 D . D 类地址

15、为实现高效率的数据传输，在传输层采用了 UDP 协议，其传输的可靠性应由（）提供

 A . IP 

 B . DNS 

 C ．网关

 D ．应用进程

二、填空题（共5道题，共20分）

1、已知有一个关键字序列：(27,23,34,14,1,55,20,19,85,83,10,68）散列存储在一个哈希表中，若散列函数为 H ( key )= key %7，并采用链地址法来解决冲突，则在等概率情况下直找成功的平均查找长度为＿（精确到小数点后两位即可)

第一空：_________

2、____是被限定只能在表的一端进行插入运算，在另一端进行删除运算的线性表

(4分）

第一空：________

3、在二叉查找树中

最好情况下复杂度为_____

最差情况下为__________

(4分）

4、某系统有四个并发进程，都需要同类资源5个，当系统中这类资源虽少数是

系统一定不会发生死锁

(4分）

第一空：

5、大端模式，是指数据的高字节保存在内存的＿地址中，而数据的低字节保存在内存的__地址中。

第一空：________

第二空：________

三、问答题

第一题：一段英语翻译

第二题：哈希表的get操作是否一定是O(1)?如果不是请简单说明出现的情况。

第三题：内存碎片产生的原因有哪些？如何减少内存碎片的产生？

第四题：如何在名为user的表中统计姓李(name)的成员数量，请写出sql语句。

四、编程题

一个人爬楼梯，每次可以爬1-4阶，但他对数字很敏感，不喜欢爬在第［ a , b , c , d ..］阶，最多有10个不喜欢爬的阶。现在从第0阶爬到第 N 阶，请问下有多少种方式可以到达。

数据规模（0< a < b < c < d < n <=1000)，其中不会有连续的三阶不可到达。（先写编程思路，再写代码，不写编程思路扣分）（12分）