杭州电子科技大学数据结构学生复习卷及部分答案.docx

杭州电子科技大学数据结构学生复习卷及部分答案

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

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

A.操作对象

B.计算方法

C.逻辑存储

D.数据映像

答案：A。数据结构研究的是数据的逻辑结构、存储结构以及对数据的操作，这里的操作对象就是数据，所以选A。计算方法侧重于算法的设计和分析；逻辑存储是存储结构方面的内容；数据映像是数据库中的概念，均不符合题意。

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

A.树

B.图

C.栈

D.二叉树

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

3.一个栈的入栈序列是1,2,3,4,5，则不可能的出栈序列是（）。

A.5,4,3,2,1

B.4,5,3,2,1

C.4,3,5,1,2

D.1,2,3,4,5

答案：C。栈遵循后进先出原则。对于选项A，入栈1,2,3,4,5，然后依次出栈5,4,3,2,1是可行的；选项B，入栈1,2,3,4，出栈4，再入栈5，出栈5,3,2,1也可行；选项D，入栈一个元素就出栈一个元素，即1入栈出栈，2入栈出栈，以此类推，也是合理的；而选项C，出栈4,3后，栈内剩下1,2，此时5入栈出栈，栈顶元素是2，应该先出栈2再出栈1，所以该序列不可能。

4.设循环队列的存储空间为Q(1:m)，初始状态为front=rear=m。现经过一系列入队与退队运算后，front=15，rear=20，则该循环队列中的元素个数为（）。

A.5

B.6

C.m5

D.m6

答案：A。循环队列中元素个数的计算公式为：(rearfront+m)%m。这里front=15，rear=20，m为队列长度，代入公式可得(2015+m)%m=5%m=5（因为5m），所以元素个数为5。

5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）。

A.9

B.11

C.15

D.不确定

答案：B。根据二叉树的性质：n0=n2+1，其中n0表示度为0的结点个数，n2表示度为2的结点个数。已知n2=10，所以n0=10+1=11，与度为1的结点个数无关。

6.对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为（）。

A.log?n

B.n/2

C.n

D.n+1

答案：C。顺序查找是从线性表的一端开始，依次将每个元素与给定值进行比较。在最坏情况下，要查找的元素是线性表的最后一个元素或者不存在，此时需要比较n次，所以选C。

7.以下排序算法中，不稳定的排序算法是（）。

A.冒泡排序

B.插入排序

C.选择排序

D.归并排序

答案：C。稳定的排序算法是指在排序过程中，相等元素的相对顺序不会改变。冒泡排序、插入排序和归并排序都是稳定的排序算法。而选择排序在每一轮选择最小（或最大）元素时，可能会改变相等元素的相对顺序，是不稳定的排序算法。

8.对于有n个顶点的无向图，采用邻接矩阵表示，该矩阵的大小为（）。

A.n

B.n2

C.(n1)2

D.n(n1)

答案：B。无向图的邻接矩阵是一个n×n的矩阵，矩阵的行和列分别对应图的顶点。矩阵中第i行第j列的元素表示顶点i和顶点j之间是否有边相连，所以矩阵大小为n2。

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

A.1

B.2

C.3

D.4

答案：C。二分查找的基本思想是每次将查找区间缩小一半。首先，取中间元素，(1+11)/2=6，对应元素50，9050，在右半区间查找；右半区间的中间元素，(7+11)/2=9，对应元素90，找到目标元素，共比较了3次。

10.以下哪种存储结构最适合用于实现图的广度优先搜索（BFS）（）。

A.邻接矩阵

B.邻接表

C.栈

D.队列

答案：B。广度优先搜索需要借助队列来实现，而在存储图时，邻接表相比邻接矩阵更适合用于BFS。邻接表可以方便地找到一个顶点的所有邻接顶点，在进行BFS时能够高效地访问