杭州电子科技大学大二计算机专业数据结构试卷测试题及答案.docx
杭州电子科技大学大二计算机专业数据结构试卷测试题及答案
一、选择题（每题3分，共30分）
1.数据结构是一门研究非数值计算的程序设计问题中计算机的（）以及它们之间的关系和运算等的学科。
A.数据元素
B.计算方法
C.逻辑存储
D.数据映像
答案：A
详细解释：数据结构研究的是数据元素、数据元素之间的关系以及对这些数据元素的运算。计算方法侧重于算法的设计和分析，并非数据结构核心研究内容；逻辑存储是数据存储结构的一部分，不全面；数据映像是关于数据映射方面的概念，也不符合数据结构的定义。所以选A。
2.线性表采用链式存储时，其地址（）。
A.必须是连续的
B.一定是不连续的
C.部分地址必须是连续的
D.连续与否均可以
答案：D
详细解释：链式存储结构是通过指针来表示元素之间的逻辑关系，每个节点可以存储在内存的任意位置，节点之间的地址不一定连续，也不需要部分地址连续，当然也不要求必须连续。所以选D。
3.栈和队列的共同点是（）。
A.都是先进后出
B.都是先进先出
C.只允许在端点处插入和删除元素
D.没有共同点
答案：C
详细解释：栈是先进后出的数据结构，队列是先进先出的数据结构，A和B选项分别只对应栈和队列的特点。它们的共同点是都只允许在端点处进行插入和删除操作，栈在栈顶进行插入和删除，队列在队头删除、队尾插入。所以选C。
4.深度为5的完全二叉树的结点数不可能是（）。
A.15
B.16
C.17
D.18
答案：A
详细解释：深度为h的完全二叉树，其节点数n的范围是\(2^{h1}\leqn2^{h}\)。深度\(h=5\)时，\(2^{4}=16\leqn2^{5}=32\)。15不在这个范围内，所以选A。
5.对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为（）。
A.log?n
B.n/2
C.n
D.n+1
答案：C
详细解释：顺序查找是从线性表的一端开始，逐个元素进行比较。在最坏情况下，要查找的元素是线性表的最后一个元素或者不存在，此时需要比较n次。所以选C。
6.以下排序算法中，稳定的排序算法是（）。
A.快速排序
B.堆排序
C.冒泡排序
D.希尔排序
答案：C
详细解释：稳定排序是指在排序过程中，相等元素的相对顺序不发生改变。快速排序、堆排序、希尔排序都是不稳定的排序算法；冒泡排序在比较相邻元素时，如果顺序不对就交换，相等时不交换，能保证相等元素的相对顺序不变，是稳定排序算法。所以选C。
7.一个具有n个顶点的无向完全图的边数为（）。
A.n(n1)/2
B.n(n1)
C.n(n+1)/2
D.n2
答案：A
详细解释：无向完全图中，每个顶点都要和其他\(n1\)个顶点相连，由于每条边连接两个顶点，所以边数为\(n(n1)/2\)。所以选A。
8.线索二叉树中某结点R没有左孩子的充要条件是（）。
A.R.lchild=NULL
B.R.ltag=0
C.R.ltag=1
D.R.rchild=NULL
答案：C
详细解释：在线索二叉树中，ltag是左线索标志。当ltag=1时，表示lchild指向的是前驱线索，即该节点没有左孩子；当ltag=0时，lchild指向左孩子。所以选C。
9.已知一个栈的进栈序列是1,2,3,4，其出栈序列不可能是（）。
A.4,3,2,1
B.3,4,2,1
C.4,1,2,3
D.2,3,4,1
答案：C
详细解释：栈是先进后出的数据结构。对于A选项，进栈顺序1,2,3,4，然后依次出栈4,3,2,1是可以的；B选项，进栈1,2,3，出栈3，进栈4，出栈4,2,1也可行；D选项，进栈1,2，出栈2，进栈3，出栈3，进栈4，出栈4,1也是合理的。而C选项，4先出栈，说明1,2,3都在栈中，此时栈顶是3，不可能接着出栈1，所以选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}\)成正比。所以