杭州电子科技大学大二计算机专业数据结构试卷测试题及答案.docxVIP

杭州电子科技大学大二计算机专业数据结构试卷测试题及答案

一、选择题（每题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}\)成正比。所以