杭州电子科技大学数据结构期末复习卷.docx
杭州电子科技大学数据结构期末复习卷
一、选择题（每题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