杭州电子科技大学数据结构期末复习卷.docxVIP

杭州电子科技大学数据结构期末复习卷

一、选择题（每题3分，共30分）

1.数据结构是一门研究非数值计算的程序设计问题中计算机的（）以及它们之间的关系和运算等的学科。

A.数据元素

B.计算方法

C.逻辑存储

D.数据映像

答案：A。数据结构研究数据元素、数据元素之间的关系以及对数据元素的运算等内容。计算方法侧重于数值计算的算法；逻辑存储是数据存储的一种方式；数据映像是数据库中的概念，所以选A。

2.以下属于线性结构的是（）。

A.树

B.图

C.栈

D.二叉树

答案：C。线性结构的特点是数据元素之间存在一对一的线性关系。栈是一种特殊的线性表，遵循后进先出原则。树和二叉树是树形结构，数据元素之间是一对多的关系；图是一种复杂的非线性结构，数据元素之间是多对多的关系，所以选C。

3.若进栈序列为1，2，3，4，进栈过程中可以出栈，则不可能的出栈序列是（）。

A.1，4，3，2

B.2，3，4，1

C.3，1，4，2

D.3，4，2，1

答案：C。对于选项A，进1出1，进2进3进4出4出3出2，可以得到1，4，3，2；对于选项B，进1进2出2，进3出3，进4出4，出1，可以得到2，3，4，1；对于选项C，进1进2进3出3后，栈顶元素是2，此时不可能出1，所以该序列不可能；对于选项D，进1进2进3出3，进4出4，出2出1，可以得到3，4，2，1，所以选C。

4.设某无向图有n个顶点，则该无向图的邻接表中有（）个表头结点。

A.2n

B.n

C.n/2

D.n(n1)

答案：B。邻接表中每个顶点对应一个表头结点，所以有n个顶点就有n个表头结点，选B。

5.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为（）。

A.n

B.n+1

C.n1

D.n+e

答案：A。表头向量是用来存储每个顶点的信息，其大小取决于顶点的个数，有n个顶点，表头向量大小就是n，选A。

6.已知一棵二叉树的先序遍历序列为ABCDEF，中序遍历序列为CBAEDF，则该二叉树的后序遍历序列为（）。

A.CBEFDA

B.FEDCBA

C.CBEDFA

D.不确定

答案：A。先序遍历的顺序是根左右，中序遍历的顺序是左根右。根据先序遍历序列ABCDEF可知A是根节点，再结合中序遍历序列CBAEDF，可知C、B是左子树的节点，E、D、F是右子树的节点。然后对左子树和右子树分别进行同样的分析，构建出二叉树，最后得到后序遍历序列为CBEFDA，选A。

7.用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：

（1）25，84，21，47，15，27，68，35，20

（2）20，15，21，25，47，27，68，35，84

（3）15，20，21，25，35，27，47，68，84

（4）15，20，21，25，27，35，47，68，84

则所采用的排序方法是（）。

A.选择排序

B.希尔排序

C.归并排序

D.快速排序

答案：D。快速排序的基本思想是通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小。从给出的序列变化可以看出，每次排序都将一个元素放到了其最终的位置上，符合快速排序的特点。选择排序是每次选择最小（大）的元素放到已排序序列的末尾；希尔排序是按照不同的增量进行分组插入排序；归并排序是将序列分成子序列，分别排序后再合并，所以选D。

8.顺序查找法适合于存储结构为（）的线性表。

A.散列存储

B.顺序存储或链式存储

C.压缩存储

D.索引存储

答案：B。顺序查找是从线性表的一端开始，依次将每个元素与给定值进行比较。顺序存储和链式存储的线性表都可以使用顺序查找法，散列存储主要用于快速查找，压缩存储是为了节省存储空间，索引存储通过索引表来加快查找速度，所以选B。

9.已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当用二分查找法查找值为90的元素时，查找成功的比较次数为（）。

A.1

B.2

C.3

D.4

答案：C。二分查找的基本思想是每次将待查找区间缩小一半。第一次比较中间元素50，90大于50，在右半区间查找；第二次比较右半区间的中间元素83，90大于83，继续在右半区间查找；第三次比较找到90，所以比较次数为3次，选C。

10.若一个