一、选择题

1. 计算机算法指的是（）

A. 计算方法

B. 排序方法

C. 解决问题的有限运算序列

D. 调度方法

2. 表达式 a*(b+c)-d 的后缀表达式是（）

A. abcd+-

B. abc+*d-

C. abc*+d-

D. -+*abcd

3. 一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（）

A. edcba

B. decba

C. dceab

D. abcde

4. 非空的循环单链表head的尾结点（由p指向）满足（）

A. p->next==NULL

B. p==NULL

C. p->next=head

D. p==head

5. 有一个序列{4,10,6,……}，当生成平衡二叉树时，插入值为6的结点时应做（）类平衡

A. LL

B. LR

C. RL

D. RR

6. 设串s1='ABCDEFG'，s2=‘PQRST’，函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2))，sub(s1,len(s2),2))的结果串是（）

A. BCDEF

B. BCDEFG

C. BCPQRST

D. BCDEFEF

7. 数据结构的二元组定义DS={D,S}中，D是数据元素的有限集合，而S是D上（）的有限集合

A. 数组

B. 数据项

C. 关系

D. 操作

8. 矩阵的压缩存储是为多个相同的元素只分配（）个存储空间，对零元素不分配空间

A. 1

B. 2

C. 3

D. 4

9. 首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为（）

A. 先序遍历

B. 中序遍历

C. 后序遍历

D. 层次遍历

10. 一个具有8个顶点的有向图中，所有顶点的入度之和与所有顶点的出度之和的差等于（）

A.16

B. 4

C. 0

D. 2

11. 若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为（）

A. 顺序结构

B. 链式结构

C. 索引结构

D. 散列结构

12. 在单链表中，指针p指向元素为x的结点，实现删除x的后继的语句是（）

A. p=p->next

B. p->next=p->next->next

C. p->next=p

D. p=p->next->next

13. 在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next==head，则（）

A. p指向头结点

B. p指向尾结点

C. p的直接后继是头结点

D. p的直接后继是尾结点

14. 广义表A=(a,(b),(),(c,d,e))的长度为（）

A. 4

B. 5

C. 6

D. 7

15. 无向图中一个顶点的度是指图中（）

A. 通过该顶点的简单路径数

B. 与该顶点相邻接的顶点数

C. 与该顶点连通的顶点数

D. 通过该顶点的回路数

16. 下列排序方法中，平均时间性能为O(nlogn)且空间性能最好的是（）

A. 快速排序

B. 堆排序

C. 归并排序

D. 基数排序

17. 队和栈的主要区别是（）不同

A. 逻辑结构

B. 存储结构

C. 所包含的运算个数

D. 限定插入和删除的位置

18. 对于哈希函数H(key)=key%13，被称为同义词的关键字是（）

A. 35和41

B. 23和39

C. 15和44

D. 25和51

19. 多维数组之所以有行优先顺序和列优先顺序两种存储方式，原因是（）

A. 数组的元素处在的行和列两个关系中

B. 数组的元素必须从左到右顺序排序

C. 数组的元素之间存在次序关系

D. 数组是多维结构，内存是唯一的

20. 希尔排序的增量必须是（）

A. 递增的

B. 递减的

C. 随机的

D. 非递减的

答案：1~5：C B C C D      6~10：D C A B C       11~15：D B D A B       16~20：B D D D B

二、填空题

1. 若一个算法的语句频度之和为T(N)=3720N+4NlogN，则算法的时间复杂度为  NlogN  。

2. 若以邻接矩阵表示有向图，则邻接矩阵上第i行中非零元素的个数即为顶点vi的  出度  。

3. 已知循环队列的存储空间大小为20，且当队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为   5   。

4. 在散列函数H(key)=key%p中，p应该取  不大于表长的质数  。

5. 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序不稳定的有  希尔排序、快速排序、堆排序  。

三、判断题

1. 在二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树

2. 链式存储的线性表可以随机存取

3.所谓平衡二叉树是指左右子树的高度差的绝对值不大于1的二叉树

4. 理想情况下，在散列表中查找一个元素的时间复杂度为O(1)

5. 满二叉树一定是完全二叉树

答案：√ × × √ √