2018年青岛理工大学计算机工程学院818数据结构考研核心题库
● 摘要
一、单项选择题
1． —个栈的入栈序列为1, 2, 3, ……, n , 其出栈序列是
取值的个数是（ ） A. B. C.
D. 无法确定
【答案】C
【解析】除了3本身以外, 其他的值均可以取到, 因此可能取值的个数为n-1。
2． 假设变址寄存器R 的内容为1000H , 指令中的形式地址为2000H ; 地址1000H 中的内容为2000H , 地址2000H 中的内容为3000H , 地址3000H 中的内容为4000H , 则变址寻方式下访问到的操作数是（ ）
A.1000H
B.2000H
C.3000H
D.4000H
【答案】D
【解析】
根据变址寻址的
操作数的实际地址,
由题可知, 变址寄存器的内容与形式地址的内容相加之后得到, 根据实际地址访问内存, 获取操作数。若, 则, 则可能4000H 。
3． 已知两个长度分别为m 和n 的升序链表, 若将它们合并为一个长度为m+n的降序链表, 则最坏情况下的时间复杂度是（ ） A. B. C. D.
【答案】D
m 和n 是两个升序链表长度分别为m 和n , 在合并过程中最坏的情况是两个链表中的【解析】
元素依次进行比较, 比较的次数是m 和n 中的最大值。
4． 二叉树在线索化后，仍不能有效求解的问题是（ ）。
A. 前序线索二叉树中求前序后继
B. 中序线索二叉树中求中序后继
C. 中序线索二叉树中求中序前驱
D. 后序线索二叉树中求后序后继
【答案】D
【解析】后序线索二叉树求后序后继要分3种情况，比较复杂，不是仅仅线索化后就能求解的，算法上还要要分情况讨论。
5． 下列选项中, 会导致用户进程从态切换到内核的操作是（ ）
Ⅰ. 整数除以零
Ⅱ.sin （ ）函数调用
Ⅲ.read 系统调用
A. 仅Ⅰ、Ⅱ
B. 仅Ⅰ、Ⅲ
C. 仅Ⅱ、Ⅲ
D. Ⅰ、Ⅱ和Ⅲ
【答案】B
【解析】对于Ⅰ, 系统发生异常, 需要进入内核态由操作系统进行处理, 而read 系统调用函数也是在内核态执行, sin （ ）就是普通的用户函数, 在用户态执行, 故答案为C 。
6． 以太网交换机进行转发决策时使用的PDU 地址是（ ）.
A. 目的物理地址
B. 目的IP 地址
C. 源物理地址
D. 源IP 地址
【答案】A
【解析】交换机会监测发送到每个端口的数据帧，通过数据帧中的有关信息(源结点的MAC 地址、目的结点的MAC 地址) ，就会得到与每个端口所连接结点的MAC 地址，并在交换机的内部建立一个“
端口地址”映射表. 建立映射表后，当某个端口接收到数据帧后，交换机会读取出该帧中的目的结点的MAC 地址，并通过“端口-MAC 地址”的对应关系，迅速将数据帧转发到相应的端口，注意这里的交换机工作在数据链路层，因此关于IP 地址的选项是不对的，因此答案为
A.
7． 下列四个序列中，哪一个是堆（ ）?
A.75，65，30，15，25，45，20，10
B.75，65，45，10，30，25，20，15
C.75，45，65，30，15，25，20，10
D.75，45，65，10，25，30，20，15
【答案】C
【解析】堆的定义:
n 个关键字序列
①②且且 称为堆，当且仅当该序列满足如下性质(简称为堆性质) : 小根堆:满足第①种情况的堆；
大根堆:满足第②种情况的堆。
根据堆定义即可得出答案。
8． 已知待排序的n 个元素可分为n/k个组，每个组包含k 个元素，且任一组内的各元素均分别大干前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为（ ）。 A.
B.
C.
D.
【答案】B
【解析】因组与组之间己有序，故将n/k个组分别排序即可，基于比较的排序方法每组的时
，全部时间下界为间下界为
9． 用有向无环图描述表达式
A.5
B.6
C.8
D.9
【答案】A 。 ，至少需要顶点的数目为（ ）。
，6条边【解析】一共5个结点
10．有n(n＞0) 个分支结点的满二叉树的深度是（ ）。
A.n 2﹣l
B.log 2(n＋1) ＋1
C.log 2(n＋1)
D.log 2(n—1)
【答案】C 。
【解析】满二叉树的结点总数＝分支的结点总数＋非分支的结点总数。由于此树为满二叉树，
所以非分支的结点总数为1，所以满二叉树共有n ＋1个结点，所以满二叉树的深度为log 2 (n＋1) 。
11．已知一棵二叉树的前序遍历结果为ABCDEF ，中序遍历结果为CBAEDF ，则后序遍历结果为（ ）。
A.CBEFDA
B.FEDCBA
相关内容
相关标签