数据结构模拟试题及答案.pdf

如有帮助欢迎下载支持

数据结构模拟试题一

一、判断题（每小题1分，共15分）

1.计算机程序处理的对象可分为数据和非数据两大类。

2.全体自然数按大小关系排成的序列是一个线性表。

3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。

4.顺序栈是一种规定了存储方法的栈。

5.树形结构中的每个结点都有一个前驱。

6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。

7.若某顶点是有向图的根，则该顶点的入度一定是零。

8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。

9.用一维数组表示矩阵可以节省存储空间。

10.广义表的长度与广义表中含有多少个原子元素有关。

11.分块查找的效率与线性表被分成多少块有关。

12.散列表的负载因子等于存入散列表中的结点个数。

13.在起泡排序过程中，某些元素可能会向相反的方向移动。

14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。

15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。

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

1.顺序表是一种_____________线性表。

2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。

3.栈和队列的区别在于________的不同。

4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。

5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域

为空的结点。

6.n个顶点的有根有向图中至少有___条边，至多有___条边。

7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。

8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是

_____。

9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。

10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。

三、选择题（每题2分，共30分）

1.计算机所处理的数据一般具有某种内在联系性，这是指________。

A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系

C．元素内部具有某种结构D．数据项和数据项之间存在某种关系

2.假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4。若把新插入元素存入R[6]，则________。

A．会产生运行错误B．R[1]~R[6]不构成一个顺序表

C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率

D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦

3.设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后一个结点时，_________。

A．P所指结点指针字段的值为空B．P的值与H的值相等

C．P所指结点的地址与H的值相等D．P所指结点指针字段的值与H的值相等

4.栈的定义不涉及数据的__________。

A．逻辑结构B．存储结构C．运算D．逻辑结构和存储结构

5.设5个元素进栈的顺序是1,2,3,4,5，则出栈的顺序有可能是___________。

A．2,4,1,3,5B．3,4,1,5,2C．3,2,4,1,5D．4,1,3,2,5

6.若某棵二叉树结点的前序序列和中序序列相同，则该二叉树_________。

A．只有一个结点B．每个结点都没有左孩子C．每个结点都没有右孩子D．不存在

7.对于一棵具有n个结点，度为3的树来说，____________。

A．树的高度至多是n-3B．树的高度至多是n-2C．树的最低高度是┏log(n+1)┓

3

D．至少在某一层上正好有3个结点

8．n个顶