【数据结构与算法】试卷 1（含答案）

一、选择题

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. 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序不稳定的有希尔排序、快速排序、堆排序。