2018年河南科技大学信息工程学院825数据结构考研仿真模拟五套题
● 摘要
一、单项选择题
1． 给定二叉树如下图所示. 设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.
2． 已知序列25, 13, 10, 12, 9是大根堆, 在序列尾部插入新元素18, 将其再调整为大根堆, 调整过程中元素之间进行的比较次数是（ ）。
A.1
B.2
C.4
D.5
【答案】B
【解析】对堆插入或删除一个元素, 有可能不满足堆的性质, 堆被破坏, 需要调整为新堆。
(1)为原堆,
(2)为插入18后,
(3)比较10与18, 交换后,
(4)比较25与18, 不交换, 即为调整后的新的大根堆。
因此调整过程中元素之间进行的比较次数为2。
3． 执行完下列语句段后，f 值为（ ）。
A.2
B.4
C.8
D. 无限递归
【答案】B
【解析】该程序使用了递归调用，由题知，:f(0)＝2；f(l)＝l*f(0)＝2；f(2)＝2*f(l)＝4；所以结果为4。
4． 连续存储设计时，存储单元的地址（ ）。
A. 一定连续
B. 一定不连续
C. 不一定连续
D. 部分连续，部分不连续
【答案】A
【解析】连续存储是指数据的物理存储相连，即存储单元的地址是连续的。
5． 某机器字长16位，主存按字节编址，转移指令采用相对寻址，由两个字节组成，第1字节为操作码字段，第2字节为相对位移量字段. 假定取指令时，每取一个字节PC 自动加1. 若某转移指令所在主存地址为2000H ，相对位移量字段的内容为06H ，则该转移指令成功转移后的目标地址是（ ）.
A.2006H
B.2007H
C.2008H
D.2009H
【答案】C
【解析】相对寻址方式的有效地址EA ＝(PC)＋D ，其中PC 为程序计数器，D 为相对偏移量. 主存按字节编址，取指令时，每取一个字节PC 值自动加1. 由于转移指令由两个字节组成，取出这条转移指令之后的PC 值自动加2，为2002H ，故转移的目标地址为2002H ＋06H ＝2008H.
6． 设栈S 和队列Q 的初始状态均为空，元素a ，b ，c ，d ，e ，f ，g 依次进入栈S. 若每个元素出
d ，c ，f ，e ，a ，g ，. 栈后立即进入队列Q ，且7个元素出队的顺序是b ，则找S 的容量至少是（ ）
A.1
B.2
C.3
D.4
【答案】C
【解析】由于栈具有先进后出的特性，队列具有先进先出的特性，出队顺序即为人队顺序.. 在本题中，每个元素出栈S 后立即进入队列Q ，出栈顺序即为入队顺序，所以本题中队列的作用形同虚设，根据题意出队顺序即为出栈顺序. 根据出桟顺序可以分析各个元素进出栈的过程：第一个出栈元素为b ，表明栈内还有元素a ，b 出栈前的深度为2；第二个出栈元素为d ，栈内元素为a 和c ，d 出栈前的深度为3；c 出栈后，剩余元素为a ，c 出栈前的深度为2；f 出栈后，剩余元素为a 和e ，f 出栈前的深度为3；e 出栈后，剩余元素为a ，e 出栈前的深度为2；a 出栈后，无剩余元素，a 出栈前的深度为1；g 出栈后，无剩余元素，g 出栈前的深度为1. 所以栈容量至少是3.
7． 在对n 个元素的序列进行排序时，堆排序所需要的附加存储空间是（ ）。 A.
B.O(1)
C.O(n) D.
【答案】B
【解析】堆排序需要一个空间用于交换，因此堆排序所需要的附加存储空间为O(1)。
8． 在用邻接表表示图时，拓扑排序算法时间复杂度为（ ）。
A.0(n)
B.0(n+e) C. D.
相关内容
相关标签