杭州电子科技大学数据结构试题.docx

杭州电子科技大学数据结构试题

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

1.算法分析的目的是（）。

A.找出数据结构的合理性

B.研究算法中的输入和输出的关系

C.分析算法的效率以求改进

D.分析算法的易懂性和文档性

答案：C。算法分析主要是对算法的时间复杂度和空间复杂度等效率指标进行分析，目的是为了改进算法，提高其执行效率。选项A数据结构的合理性是设计数据结构时考虑的；选项B输入输出关系不是算法分析的主要目的；选项D易懂性和文档性不是算法分析核心目的。

2.线性表采用链式存储时，其地址（）。

A.必须是连续的

B.部分地址必须是连续的

C.一定是不连续的

D.连续与否均可以

答案：D。链式存储是通过指针来连接各个节点，节点在内存中的存储位置可以是任意的，不要求连续，也可以有部分连续情况，所以连续与否均可以。

3.栈和队列的共同点是（）。

A.都是先进先出

B.都是先进后出

C.只允许在端点处插入和删除元素

D.没有共同点

答案：C。栈是先进后出，队列是先进先出，A、B错误。栈只允许在栈顶插入和删除元素，队列只允许在队尾插入，队头删除，都是在端点处进行操作，所以C正确。

4.已知一棵二叉树的前序遍历序列为ABCDEFG，中序遍历序列为CBDAEGF，则该二叉树的后序遍历序列为（）。

A.CDBGFEA

B.CDBFGEA

C.CDBAGFE

D.BCDAGFE

答案：A。前序遍历的顺序是根节点左子树右子树，中序遍历是左子树根节点右子树。由前序遍历可知A是根节点，在中序遍历中找到A，A左边的CBD是左子树节点，右边的EGF是右子树节点。再对左子树和右子树分别重复上述步骤构建二叉树，最后得出后序遍历（左子树右子树根节点）为CDBGFEA。

5.对于哈希表，如果将装填因子α定义为表中装入的记录数与表的长度之比，那么向表中加入新记录时，（）。

A.α的值随冲突次数的增加而递减

B.α越大发生冲突的可能性就越大

C.α越大处理冲突的时间就越短

D.α的值随冲突次数的增加而递增

答案：B。装填因子α越大，说明表中装入的记录数相对表的长度越多，发生冲突的可能性就越大。α与冲突次数没有直接的增减关系，且α越大处理冲突的时间通常会越长。

6.对n个不同的关键字进行冒泡排序，在元素无序的情况下比较的次数为（）。

A.n+1

B.n

C.n1

D.n(n1)/2

答案：D。冒泡排序在最坏情况下（元素无序），比较次数为\(n(n1)/2\)。第一次比较\(n1\)次，第二次比较\(n2\)次，以此类推，总的比较次数为\(1+2+\cdots+(n1)=\frac{n(n1)}{2}\)。

7.具有10个叶子节点的二叉树中有（）个度为2的节点。

A.8

B.9

C.10

D.11

答案：B。根据二叉树的性质：\(n_0=n_2+1\)（\(n_0\)表示叶子节点数，\(n_2\)表示度为2的节点数），已知\(n_0=10\)，则\(n_2=n_01=9\)。

8.若一个有向图的邻接矩阵中，主对角线以下元素均为零，则该图的拓扑排序（）。

A.一定存在

B.一定不存在

C.不一定存在

D.无法确定

答案：A。主对角线以下元素均为零的有向图是一个有向无环图（DAG），有向无环图一定存在拓扑排序。

9.顺序查找法适合于存储结构为（）的线性表。

A.散列存储

B.顺序存储或链式存储

C.压缩存储

D.索引存储

答案：B。顺序查找是从线性表的一端开始，依次将每个元素与给定值进行比较，它适用于顺序存储和链式存储的线性表。

10.下面关于图的存储的叙述中，正确的是（）。

A.用邻接矩阵法存储图，占用的存储空间数只与图中顶点数有关，而与边数无关

B.用邻接矩阵法存储图，占用的存储空间数只与图中边数有关，而与顶点数无关

C.用邻接表法存储图，占用的存储空间数只与图中顶点数有关，而与边数无关

D.用邻接表法存储图，占用的存储空间数只与图中边数有关，而与顶点数无关

答案：A。邻接矩阵是一个\(n\timesn\)的矩阵（\(n\)为顶点数），其存储空间只与顶点数\(n\)有关，与边数无关。邻接表的存储空间与顶点数和边数都有关。

二、填空题（每题3分，共15分）

1.数据结构按逻辑结构可分为两大类，分别是______和______。

答案：线性结构；非线性结构。数据的逻辑结构分为线性结构（如线性表、栈、队列等）和非线性结构（如树、图等）。

2.设栈S和队列Q的初始状态