杭州电子科技大学数据结构期末复习卷.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

解析：栈的特点是后进先出。对于选项C，若3先出栈，说明1、2、3已进栈，此时出栈顺序应为3、2、1，不可能3出栈后接着1出栈，所以C选项不可能，A、B、D选项都可以通过合理的进栈出栈操作得到。

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

A.m1

B.m

C.1

D.0

答案：A

解析：循环队列元素个数的计算公式为：(rearfront+m)%m。将front=1，rear=m代入公式，可得(m1+m)%m=m1，所以选A。

5.一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为（）。

A.219

B.221

C.229

D.231

答案：A

解析：在二叉树中，度为0的节点（叶子节点）个数比度为2的节点个数多1，已知叶子节点有70个，所以度为2的节点个数为69个。总结点数=度为0的节点数+度为1的节点数+度为2的节点数=70+80+69=219，所以选A。

6.对长度为n的线性表排序，在最坏情况下，比较次数不是n(n1)/2的排序方法是（）。

A.快速排序

B.冒泡排序

C.直接插入排序

D.堆排序

答案：D

解析：快速排序、冒泡排序和直接插入排序在最坏情况下的比较次数都是n(n1)/2。而堆排序在最坏情况下的时间复杂度是$O(nlog_2n)$，所以选D。

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

A.1

B.2

C.3

D.4

答案：B

解析：二分查找每次将查找区间缩小一半。第一次查找，中间元素是50，90大于50，所以在右半区间查找；第二次查找，右半区间中间元素是90，查找成功，所以比较次数为2次，选B。

8.有向图的邻接矩阵中，第i行上非零元素的个数等于（）。

A.顶点$v_i$的度

B.顶点$v_i$的出度

C.顶点$v_i$的入度

D.依附于顶点$v_i$的边数

答案：B

解析：在有向图的邻接矩阵中，第i行上非零元素表示从顶点$v_i$出发的边，所以第i行上非零元素的个数等于顶点$v_i$的出度，选B。

9.哈希表的平均查找长度（）。

A.与处理冲突方法有关而与表的长度无关

B.与处理冲突方法无关而与表的长度有关

C.与处理冲突方法和表的长度都有关

D.与处理冲突方法和表的长度都无关

答案：C

解析：哈希表的平均查找长度既与处理冲突的方法（如开放定址法、链地址法等）有关，不同的处理冲突方法会导致不同的查找效率；也与表的长度有关，表的长度不同，装填因子不同，平均查找长度也会不同，所以选C。

10.若一个算法的时间复杂度为$O(n^2)$，表明该算法的（）。

A.问题规模是$n^2$

B.执行时间等于$n^2$

C.执行时间与$n^2$成正比

D.问题规模与$n^2$成正比

答案：C

解析：时间复杂度$O(n^2)$表示算法的执行时间的增长趋势与$n^2$成正比，而不是问题规模是$n^2$或执行时间等于$n^2$，也不是问题规模与$n^2$成正比，所以选C。

二、填空题（每题3分，共1