《2017年厦门大学能源学院845数据结构考研仿真模拟题.doc》由会员分享，可在线阅读，更多相关《2017年厦门大学能源学院845数据结构考研仿真模拟题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年厦门大学能源学院845数据结构考研仿真模拟题一、填空题1 栈是_的线性表，其运算遵循_的原则。；后进先出 【答案】操作受限（或限定仅在表尾进行插入和删除操作） 2 设用希尔排序对数组98，36，-9，0，47，23，1，8，10，7进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需_趟，写出第一趟结束后，数组中数据的排列次序_。【答案】3; （10，7，-9，0，47，23，1，8，98，36） 3 个字符串中_称为该串的子串。【答案】任意个连续的字符组成的子序列 4 根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_和_; 而又根据指针的连接方式，链表又
2、可分成_和_。【答案】单链表；双链表；（动态）链表；静态链表【解析】线性表的链式存储结构根据每个结点包含的指针个数分为单链表和双链表，单链表只包含一个指针，指向后续元素，双链表包括两个指针，指向前一个元素和后续元素。根据指针的连接方式，链表可分为动态链表和静态链表。静态链表的指针指向下一个元素的编号，动态链表的指针指向下一个元素的物理位置。 5 在拓扑分类中，拓扑序列的最后一个顶点必定是_的顶点。【答案】出度为0【解析】如果最后一个顶点的出度不为0, 则必定还有顶点存在，与题目所说的最后一个顶点矛盾，所有最 后一个顶点的出度必定为零。 6 用循环链表表示的队列长度为n ，若只设头指针，则出队和
3、入队的时间复杂度分别是_和_；若只设尾指针，则出队和入队的时间复杂度分别是_和_。 【答案】【解析】队列的出队操作即删除队头的元素，队列的入队操作即在队尾添加元素，循环链表只设头指针，出队时，只要把头结点的下一个结点删除就好了，入队时，要把新的结点插入队尾，必须把队列遍历，找到队尾指针，才能插入。循环队列只设尾指针，出队时只要把为指针的下一个结点或者下下个结点删除即可，入队时，只要在尾指针的后面插入新的结点，并更新尾结点即可。 7 对于一个具有n 个结点的二叉树，当它为一棵_二叉树时具有最小高度，当它为一棵_ 时. 具有最大高度【答案】完全；只有一个叶结点的二叉树 8 中缀式运算结果为_。 【
4、答案】【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。9 无用单元是指_，例_【答案】用户不再使用而系统没有回收的结构和变量；10VSAM （虚拟存储存取方法）文件的优点是：动态地_，不需要文件进行_，并能较快地_进行查找。【答案】分配和释放存储空间；重组；对插入的记录 11二叉树的前序序列和中序序列相同的条件是_。【答案】空树或任何结点至多只有右子树的二叉树【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。 12如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，请在算法，其空
5、格处填上正确的语句。设线索二叉树的结点数据结构为（lflag ，lcft ，data ，right ，rflag ）中：lflag=0，lcft 指向其左孩子，lflag=1，left 指向其前驱：rflag=0，right 指向其右孩子，rflag=1，right 指向其后继。Prior （node , x ） if（node !=null）If （ （1） ） *x=node-right；else * x-node-left;next （bt , node, x ）/*bt是二叉树的树根*/ （2） ; if （node-rflag）（3）;else do t=*x；;while （*x=
6、node ）;*x=t;【答案】nodc-rflag=O; *x=ht; *x=nodc-right; prior （t , X ）对应的前缀式为_，若则后缀式的 二、选择题13引入二叉线索树的目的是（ ）。A. 加快查找结点的前驱或后继的速度B. 为了能在二叉树中方便地进行插入与删除C. 为了能方便地找到双亲D. 使二叉树的遍历结果唯一【答案】A【解析】二叉线索树有指向前驱和后继的指针，因此加快了查找前驱和后继结点的速度。14求整数阶乘的算法如下，其时间复杂度是（ ）。 A.B.C.D. 【答案】B 。【解析】设fact （n ）的运行时间函数是T （n ）。 该函数中语句的运行时间是0（1）, 语句的运行时间是法运算的时间。因此，当时， 当时，则，其中O （1）为乘即fact （n ）的时间复杂度为 15在参考摸型中，下列功能需由应用层的相邻层实现的是（ ）A. 对话管理B. 数据格式转换C. 路由选择D. 可靠数据传输【答案】B【解析】应用层的相邻层即为表示层，表示层负责管理数据的压缩、加密与解密、格式装换等，故答案为B 。一、填空题考研试题
