2018年闽南师范大学计算机学院916计算机专业基础之数据结构考研仿真模拟五套题
● 摘要
一、填空题
1．
【答案】5
2． 每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH ，中序序列是FEBGCHD ，则它的后序序列是_____。设上述二叉树是由某棵树转换而成，则该树的前序序列是_____
【答案】FEGHDCB ；BEF
【解析】树的前序序列对应二叉树的前序序列，该二叉树转换成森林时含三棵树，其第一棵树的前序是BEF 。
3． 对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度, 当它为一棵_____时，具有最大高度。
【答案】完全；只有一个叶结点的二叉树
4． 起始地址为480，大小为8的块，其伙伴块的起始地址是_____；若块大小为32, 则其伙伴块的起始地址为_____; 。
【答案】480+8=488，480－32=448
【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下:
根据上述公式起始地址就为488。
5． 以下是用类C 语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild 域作为前链域，指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack , 栈顶指针为top ，P ，t 为辅助指针，head 为双向循环链表的头指针。试填充算法中的空格，使算法完整。
第 2 页，共 58 页
＝_____
【答案】
6． 在n 个顶点的非空无向图中，最多有_____个连通分量。
【答案】n
【解析】当n 个顶点之间没有边，都是孤立的顶点时，有n 个连通分量。
二、单项选择题
7． 将一棵树t 转换为孩子兄弟链表表示的二叉树h ，则t 的后序遍历是h 的（ ）。
A. 前序遍历 B. 中序遍历 C. 后序遍历 【答案】B
【解析】树的后序遍历恰好对应于二叉树的中序遍历。
8． 某计算机主频为1.2GHz , 其指令分为4类, 它们在基准程序中所占比例及CPI 如下表所示。
该机的MIPS 数是（ ） A.100 B.200 C.400 D.600
【答案】C
【解析】基准程序的
。
计算机的主频为
, 为1200MHz , 该机器的MIPS 为
第 3 页，共 58 页
。
9． 给定二叉树如下图所示. 设N 代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子树. 若遍历后的结点序列为3，1，7，5，6，2，4，则其遍历方式是（ ）.
A.LRN B.NRL C.RLN
D.RNL
图
【答案】D
【解析】对“二叉树”而言，一般有三条搜索路径： ①先上后下的按层次遍历； ②先左(子树) 后右(子树) 的遍历； ③先右(子树) 后左(子树) 的遍历.
其中第1种搜索路径方式就是常见的层次遍历，第2种搜索路径方式包括常见的先序遍历NLR 、中序遍历LNR 、后序遍历LRN ，第3种搜索路径方式则是不常使用的NRL 、RNL 、RLN. 本题考查的是第3种搜索路径方式的一种情况. 根据遍历的序列以及树的结构图，可以分析出该遍历的顺序是先右子树再跟结点最后左子树，故答案为D.
10．响应外部中断的过程中, 中断隐指令完成的操作, 除保护断点外, 还包括（ ）。
Ⅰ. 开关中断
Ⅱ. 保存通用寄存器的内容
Ⅲ. 形成中断服务程序入口地址并送PC A. 仅Ⅰ、Ⅱ B. 仅Ⅰ、Ⅲ C. 仅Ⅱ、Ⅲ D. Ⅰ、Ⅱ、Ⅲ 【答案】B 。
【解析】中断隐指令完成的操作有3个:
①保存断点; ②关中断; ③引出中断服务程序(形成中断服务程序入口地址并送PC) 。 而保存通用寄存器内容的操作是由软件来实现, 不是由中断隐指令实现的。
第 4 页，共 58 页
相关内容
相关标签