2017年合肥工业大学科研机构和宣城校区850计算机科学与技术学科专业基础综合之数据结构考研题库
● 摘要
一、填空题
1． 下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n
个顶点
用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。
（1）若是边，则的值等于_____，若不是边，则的值是一个比任何边的权，矩阵的对角线元素全为0。
（2）构造最小生成树过程中，若顶点Vi 已包括进生成树，就把相邻矩阵的对角线元素A （i , i ）置成若
【答案】（1） 已包括进生成树，就把矩阵元素A （i ，j ）置成。 边上的权值；都大的数；（2）1; 负值；（3）为负；边 （3）算法结束时，相邻矩阵中的元素指出最小生成树的
2． 检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_____检索。也可以按_____检索；按_____检索又可以有_____检索和_____检索。
【答案】关键字；记录号；记录号；顺序；直接
3． 在一个无向图的的邻接表中，若表结点的个数是m , 则图中边的条数是_____条。
【答案】m/2
【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。
4． 设有一个空找，栈顶指针为1000H （十六进制），现有输入序列为1，2，3, 4, 5，经过PUSH ，PUSH , POP , PUSH , POP ，PUSH ，PUSH 之后，输出序列是_____，而栈顶指针值是_____。设栈为顺序栈，每个元素占4个字节。
【答案】23; 100CH
5． 遍历图的过程实质上是_____，广度优先遍历图的时间复杂度_____; 深度优先遍历图的时间复杂度_____, 两者不同之处在于_____, 反映在数据结构上的差别是_____。
【答案】查找顶点的邻接点的过程；0（n+e）; 0（n+e）; 访问顶点的顺序不同；队列和栈
【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。
6． 表达式的后缀表达式是_____。 【答案】
7． 在单链表L 中，指针P 所指结点有后继结点的条件是_____ 【答案】
【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。
8． 高度为h 的堆中，最多有_____元素，最少有_____个元素。 【答案】
当最后一层只有【解析】当这个堆构成的是满二叉树时，元素的个数最多，元素个数为
一个元素时，此时堆的元素个数最少，元素个数为
9． 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。
【答案】（1）
（2）链表未到尾就一直进行 将当前结点作为头结点后的第一元素结点插入
10．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_____存储结构。
【答案】顺序
【解析】顺序存储结构的存取操作比较方便，但插入和删除操作不如链式存储结构方便，而且需要连续的存储空间，由于该线性表的元素总数基本稳定，而且很少进行插入删除操作，为了更快的存取元素，顺序表更合适。
二、判断题
11．对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。（ ）
【答案】√
【解析】可以有长度无穷大的广义表，只是在计算机中不能实现。
12．在一个设有头指针和尾指针的单链表中，执行删除该单链表中最后一个元素的操作与链表的长度无关。（ ） 【答案】
【解析】必须从头指针开始，查找到尾指针所指结点的前驱结点的指针。
13．为了很方便的插入和删除数据，可以使用双向链表存放数据。（ ） 【答案】
【解析】链式存储结构便于数据的插入和删除，但只能顺序访问表中的元素。
14．即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作，所得的输出序列也一定相同。（ ） 【答案】
【解析】栈只是一种先入后出的存储结构。对于出栈、入栈的元素不进行修改，因此，输入序列的元素不相同，不可能得到相同的输出序列。
15．由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间更多。（ ）
【答案】×
【解析】希尔排序把序列分成很多小序列，对于直接插入排序，记录少时的效率会大大提高。并且序列在基本有序的情况下，直接插入排序也会提高。
16．数据结构的抽象操作的定义与具体实现有关。（ ） 【答案】
【解析】数据结构的抽象操作定义取决于客观存在的一组逻辑特性，与其在计算机内具体表示和实现无关。
17．完全二叉树肯定是平衡二叉树。（ ）
【答案】×
【解析】从平衡因子定义看，完全二叉树任一结点的平衡因子的绝对值确实是小于等于1。但是，平衡二叉树本质上是二叉排序树，完全二叉树不一定是排序树。故不能说完全二叉树是平衡二叉树。
18．用希尔（Shell ）方法排序时，若关键字的初始排序杂乱无序，则排序效率就低。（ ）
【答案】×
【解析】希尔排序的基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
19．数组不适合作为任何二叉树的存储结构。（ ）
【答案】×
【解析】对于完全二叉树，因为其n 个结点的位置已经固定，所以用一维数组作为存储结构是高效率的（存储密度大）。
20．有n 个数顺序（依次）入栈，出栈序列有Cn 种
，
（ ） 【答案】
相关内容
相关标签