《数据结构》期末考试试题练习题及答案.docxVIP

《数据结构》期末考试试题练习题及答案

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

1.数据结构是一门研究非数值计算的程序设计问题中计算机的（）以及它们之间的关系和运算等的学科。

A.数据元素

B.计算方法

C.逻辑存储

D.数据映像

答案：A

解析：数据结构研究数据元素以及它们之间的关系和运算等，数据元素是数据的基本单位，所以选A。计算方法主要涉及数值计算的方法，B选项不符合；逻辑存储只是数据结构中存储方面的一部分，C选项不全面；数据映像是指数据在不同表示形式之间的转换，不是数据结构研究的核心内容，D选项错误。

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

A.必须是连续的

B.一定是不连续的

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

D.连续与否均可以

答案：D

解析：链式存储结构中，每个节点包含数据域和指针域，节点可以存放在内存的任意位置，通过指针来表示节点之间的逻辑关系，所以地址连续与否均可，选D。顺序存储才要求地址必须连续，A选项错误；虽然链式存储地址通常不连续，但也不排除连续的可能，B选项过于绝对；链式存储不要求部分地址必须连续，C选项错误。

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，选A。

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

A.n+1

B.n

C.n1

D.n(n1)/2

答案：D

解析：冒泡排序在最坏情况下（元素无序），第1趟比较n1次，第2趟比较n2次，……，第n1趟比较1次。总的比较次数为1+2+…+(n1)=n(n1)/2，选D。

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

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

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

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

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

答案：C

解析：哈希表的平均查找长度受处理冲突的方法（如开放定址法、链地址法等）影响，不同的处理冲突方法会导致不同的查找效率。同时，表的长度也会影响平均查找长度，表越长，发生冲突的概率相对越小，平均查找长度可能越短，所以与处理冲突方法有关且与表的长度有关，选C。

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

A.一定存在

B.一定不存在

C.不一定存在

D.无法确定

答案：A

解析：主对角线以下的元素均为0说明该有向图是一个有向无环图（DAG），有向无环图一定存在拓扑排序，选A。

8.以下哪种排序算法在最坏情况下的时间复杂度最低（）。

A.冒泡排序

B.快速排序

C.堆排序

D.插入排序

答案：C

解析：冒泡排序和插入排序在最坏情况下的时间复杂度都是$O(n^2)$，快速排序在最坏情况下时间复杂度为$O(n^2)$，而堆排序在最坏情况下的时间复杂度是$O(nlogn)$，所以选C。

9.一个满二叉树，其深度为4，则该二叉树的节点个数为（）。

A.15

B.16

C.17

D.18

答案：A

解析：满二叉树的节点个数公式为$2^h1$（h为树的深度），当h=4时，$2^41=15$，选A。

10.线性表若采用顺序存储结构时，要求内存中可用存储单元的地址（）。

A.必须是连续的

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

C.一定是不连续的

D.连续或不连续都可以

答案：A

解析：顺序存储结构是用一组地址连续的存储单元依次存储线性表的数据元素，所以要求内存中可用存储单元的地址必须是连续的，选A。

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

1.数据的逻辑结构分为线性结构和_____