2018年天津职业技术师范大学信息技术工程学院811数据结构考研基础五套测试题
● 摘要
目录
2018年天津职业技术师范大学信息技术工程学院811数据结构考研基础五套测试题（一） ... 2 2018年天津职业技术师范大学信息技术工程学院811数据结构考研基础五套测试题（二） . 15 2018年天津职业技术师范大学信息技术工程学院811数据结构考研基础五套测试题（三） . 27 2018年天津职业技术师范大学信息技术工程学院811数据结构考研基础五套测试题（四） . 39 2018年天津职业技术师范大学信息技术工程学院811数据结构考研基础五套测试题（五） . 52
第 1 页，共 64 页
一、填空题
1． 如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。
【答案】
【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺序查找效率一样为。
2． 已知一循环队列的存储空间为则此循环队列判满的条件是_____
【答案】
3． 二叉树的前序序列和中序序列相同的条件是_____。
【答案】空树或任何结点至多只有右子树的二叉树
【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。
4． 在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_____、_____、_____、_____。
【答案】f ﹣＞next ＝p ﹣＞next ；f ﹣＞prior ＝p ；p ﹣＞next ﹣＞prior ＝f ；p ﹣＞next ＝f ；
5． 从平均时间性能而言，_____排序最佳。
【答案】快速
【解析】快速算法的平均时间复杂度为nlogn 。
6． 顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。
【答案】物理上相邻；指针
【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。
7． 下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。
第 2 页，共 64 页
，其中n ＞m ，队头和队尾指针分别为front 和rear ，
a 中存放待排序的关键字
【答案】
【解析】快速排序(quick sort)的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
8． 模式串
【答案】01122312
9． 克鲁斯卡尔算法的时间复杂度为_____，它对_____图较为适合。
【答案】
；边稀疏
10．阅读下列程序，指出其功能，并写出空格处应填上的语句。
第 3 页，共 64 页
的next 函数值序列为_____。
【答案】
【解析】本题是在哈希表
中插入值为item 的元素，如该元素已在哈希表中，报告出错。
二、单项选择题
11．下列有关RAM 和ROM 的叙述中, 正确的是（ ）。
Ⅰ.RAM 是易失性存储器, ROM 是非易失性存储器 Ⅱ.RAM 和ROM 都采用随机存取方式进行信息访问 Ⅲ.RAM 和ROM 都可用作Cache Ⅳ.RAM 和ROM 都需要进行刷新 A. 仅Ⅰ和Ⅱ B. 仅Ⅱ和Ⅲ C. 仅Ⅰ、Ⅱ和Ⅳ D. 仅Ⅱ、Ⅲ和Ⅳ 【答案】A
【解析】RAM 中的内容断电后即丢失(易失性) , ROM 中的内容断电后不会丢失(非易失性) , 同时RAM 和ROM 都采用随机存取方式(即CPU 对任何一个存储单元的存取时间相同) , 区别在于RAM 可读可写, ROM 只读不写。而ROM 显然不可用作Cache , 也不需要刷新, 所以Ⅲ和Ⅳ的叙述都是错误的。
12．下列二叉排序树中查找效率最高的是（ ）。
A. 平衡二叉树 B. 二叉查找树
C. 没有左子树的二叉排序树 D. 没有右子树的二叉排序树 【答案】A
【解析】平衡二叉树的左子树和右子树的深度之差的绝对值不超过1。这就保证了二叉树的深度是
级别的。二叉查找树或者是一颗空数；或者是具有下列性质的二叉树:①若左子树不空，
则左子树上所有结点的值均小于它的根结点的值；②若右子树不空，则右子树上所有结点的值均大于它的根结点的值；③左、右子树也分别为二叉排序树。B 、C 、D 三项均不能保证左子树和右子树的深度之差的绝对值不超过1, 甚至很大，因此查找效率低。
13．若某单处理器多进程系统中有多个就绪态进程, 则下列关于处理机调度的叙述中, 错误的是（ ）。
A. 在进程结束时能进行处理机调度
第 4 页，共 64 页
相关内容
相关标签