2017年合肥工业大学科研机构和宣城校区850计算机科学与技术学科专业基础综合之数据结构考研仿真模拟题
● 摘要
目录
2017年合肥工业大学科研机构（智能制造技术研究院、科学技术研究院、工业与装备技术研究
院）和宣城校区850计算机科学与技术学科专业基础综合之数据结构考研仿真模拟题（一） .. 2 2017年合肥工业大学科研机构（智能制造技术研究院、科学技术研究院、工业与装备技术研究院）和宣城校区850计算机科学与技术学科专业基础综合之数据结构考研仿真模拟题（二） 10 2017年合肥工业大学科研机构（智能制造技术研究院、科学技术研究院、工业与装备技术研究院）和宣城校区850计算机科学与技术学科专业基础综合之数据结构考研仿真模拟题（三） 17 2017年合肥工业大学科研机构（智能制造技术研究院、科学技术研究院、工业与装备技术研究院）和宣城校区850计算机科学与技术学科专业基础综合之数据结构考研仿真模拟题（四） 26 2017年合肥工业大学科研机构（智能制造技术研究院、科学技术研究院、工业与装备技术研究院）和宣城校区850计算机科学与技术学科专业基础综合之数据结构考研仿真模拟题（五） 33
一、填空题
1． 在一个具有n 个单元的顺序栈中，假定以地址高端（即下标为n 的单元）作为栈底，以top 作为栈顶指针，则当向栈中压入一个元素时，top 的变化是top=_____。 【答案】
【解析】由于栈底在地址高端，栈中压入一个元素时，栈顶向地址底端移动一个单位，
所以
2． 顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。 【答案】
【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监视哨。
3． 在下面的程序段中，对X 的赋值语句的时间复杂度为_____（表示为n 的函数）。
【答案】1＋（1＋2）＋（1＋2＋3）＋"•＋（l ＋2＋... ＋n ）=n（n ＋1）（n ＋2）/6，即
【解析】当i=l时，赋值语句就被执行了一次。当i=2时，赋值语句被执行了1＋2次。当i=3时，赋值语句被执行了1＋2＋3次。可以推出赋值语句总共被执行了1＋（1＋2）＋（1＋2＋3）＋…＋（l ＋2＋... ＋n ）=n（n ＋1）（n ＋2）/6次。
4． 遍历图的过程实质上是_____，广度优先遍历图的时间复杂度_____; 深度优先遍历图的时间复杂度_____, 两者不同之处在于_____, 反映在数据结构上的差别是_____。
【答案】查找顶点的邻接点的过程；0（n+e）; 0（n+e）; 访问顶点的顺序不同；队列和栈
【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。
5． 执行顺序查找时，存储方式可以是_____，折半查找时，要求线性表_____，分块查找时要求线性表_____，而哈希表的查找，要求线性表的存储方式是_____。
【答案】顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储
6． 设有个结点的完全二叉树顺序存放在向量
【答案】 中，其下标值最大的分支结点为_____。 【解析】最大的分支结点是最后一个叶子结点的父结点。
7． 顺序栈用存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。 【答案】
【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。
8． 模式串的next 函数值序列为_____。
【答案】01122312
9． 用循环链表表示的队列长度为n ，若只设头指针，则出队和入队的时间复杂度分别是_____和_____；若只设尾指针，则出队和入队的时间复杂度分别是_____和_____。 【答案】
【解析】队列的出队操作即删除队头的元素，队列的入队操作即在队尾添加元素，循环链表只设头指针，出队时，只要把头结点的下一个结点删除就好了，入队时，要把新的结点插入队尾，必须把队列遍历，找到队尾指针，才能插入。循环队列只设尾指针，出队时只要把为指针的下一个结点或者下下个结点删除即可，入队时，只要在尾指针的后面插入新的结点，并更新尾结点即可。
10．VSAM （虚拟存储存取方法）文件的优点是：动态地_____，不需要文件进行_____，并能较快地_____进行查找。
【答案】分配和释放存储空间；重组；对插入的记录
二、判断题
11．在任何情况下，归并排序都比简单插入排序快。（ ）
【答案】×
【解析】错误。待排序序列为正序时，简单插入排序比归并排序快。
12．对两棵具有相同关键字集合的而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序却是一致的。（ ）
【答案】√
，【解析】形状不同的两个二叉排序树（关键字集合相同）在中序遍历下是输出排好序的序列，
所以顺序是一致的。
13．—个稀疏矩阵
【答案】× 采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m 的转置运算。（ ） 和n 的值互换，则就完成了
【解析】稀疏矩阵转置后，除行列下标及行列数互换外，还必须确定该元素转置后在新三元组中的位置。
14．深度为k 的二叉树中结点总数小于等于
【答案】√
【解析】深度为K 的二叉树，当结点数最多时为满二叉树，此时结点数为
15．循环队列也存在空间溢出问题。（ ） 【答案】 （ ）
【解析】循环队列的存储空间也是有限的，因此也存在空间溢出问题。
16．由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间更多。（ ）
【答案】×
【解析】希尔排序把序列分成很多小序列，对于直接插入排序，记录少时的效率会大大提高。并且序列在基本有序的情况下，直接插入排序也会提高。
17．哈希表的结点中只包含数据元素自身的信息，不包含任何指针。（ ）
【答案】×
【解析】哈希表的结点中可以包括指针，指向其元素。如哈希链表。
18．堆肯定是一棵平衡二叉树。（ ）
【答案】×
【解析】堆是n 个元素的序列，可以看成是完全二叉树，但相对于根并无左小右大的要求，故其既不是二叉排序树，更不会是平衡二叉树。
19．m 阶B 树的任何一个结点的左右子树的高度都相等。（ ）
【答案】√
【解析】由B 树的性质得知，叶子结点都处于同一层。因此，m 阶B 树的任何一个结点的左右子树的高度都相等。
20．哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。（ ）
【答案】×
【解析】哈希文件是使用一个函数（算法）来完成一种将关键字映射到存储器地址的映射，根据用户给出的关键字，经函数计算得到目标地址，再进行目标的检索。哈希表是根据关键码值
相关内容
相关标签