《数据结构与算法》期末考试试卷(A卷)

数据结构与算法

清远职业技术学院2015-2016学年度第二学期

《数据结构与算法(java版)》期末考试试题（A卷） （系.部级年制业班 学号姓名分数

一、 选择题（每题4分，共40分）

B．并行性

D．时空复杂度 1. 对一个算法的评价，不包括如下（ ）方面的内容。 A．健壮性和可读性 C．正确性

2. 在一个单链表中的p和q两个结点之间插入一个新结点，假设新结点为s,则修改链的java语句序列是（ ）。

A.s.setNext(p); q.setNext(s);

C.p.setNext(s); s.setNext(q);

3. 若将整数1、2、3、4依次进栈，则不可能得到的出栈序列是（ ）。

A．1234 B. 1324 C. 4321 D. 1423

4. 设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）

A．求子串 B．联接 C．模式匹配 D．求串长

5. 对一棵树进行后根遍历操作与对这棵树所对应的二叉树进行（ ）遍历操作相同。

A． 先根 B. 中根 C. 后根 D. 层次

6. 在哈夫曼树中，任何一个结点它的度都是（ ）。

A． 0或1 B. 1或2 C. 0或2 D. 0或1或2

7. 若某棵二叉树的先根遍历序列为ABCDEF，中根遍历序列为CBDAEF，则这棵二叉树的后根遍历序列为（ ）。

A．FEDCBA B. CDBFEA C. CDBEFA D. DCBEFA

8. 具有6个顶点的无向图至少应有（ ）条边才能确保是一个连通图。

A.5 B.6 C.7 D.8 B. p.setNext(s.getNext()); s.setNext(p); D. q.setNext(s.getNext()); s.setNext(p);

数据结构与算法

9. 当待排序序列基本有序时，以下排序方法中，( )最不利于其优势的发挥。

A. 直接选择排序 B. 快速排序 C.冒泡排序 D.直接插入排序

10. 若有一个长度为64的有序表，现用二分查找方法查找某一记录，则查找不成功，最多需要

比较( )次。

A.9 B.7 C.5 D.3

二、 填空题（每空1分，共20分）

1. 线性表是由n（n≥0）个数据元素所构成的有限序列，其中n为数据元素的个数，称为线性表的 ，n=0的线性表称为 。

2. 顺序表中逻辑上相邻的数据元素，其物理位置 相邻，而在单链表中逻辑上相邻的数据元素，其物理位置 相邻。

3. 队列也是一种操作受限的线性表，它与栈不同的是，队列中所有的插入操作均限制在表的一端进行，而所有的删除操作都限制在表的另一端进行，允许插入的一端称为 ，允许删除的一端称为 。

4. 一个串的任意连续字符组成的子序列称为串的 ，该串称为 。

5. 深度为4的平衡二叉树中至少有 个结点，至多有 个结点。

三、 上机实践题（每题20分，共40分）

答题要求提交如下资料：

1) 将代码复制到答卷中“【代码】：”处。

2) 运行结果中必须显示个人的名字，并截图复制到答卷中的“【运行效果图】：”处。如：

3) 提交完整的程序文件，并按题号分目录（如3.1、3.2）存放。

1. 编写一个顺序表类，实现对顺序表（顺序表长度为10，节点值为随机数字）就地逆置的操作。所谓逆置，就是把（a1,a2, ,an）变成（an,an-1, ,a1）；所谓就地，就是指逆置后的数据元素仍存储在原来顺序表的存储空间中，即不为逆置后的顺序表另外分配存储空间。

2. 编写一个排序方法类，实现用插入排序方法对单链表（链表长度为5，节点值为随机数字）

数据结构与算法

进行排序。