2018年常州大学商学院858数据结构考研核心题库
● 摘要
一、单项选择题
1． 下列选项中，不属于网络体系结构中所描述的内容是（ ）.
A. 网络的层次
B. 每一层使用的协议
C. 协议的内部实现细节
D. 每一层必须完成的功能
【答案】C
【解析】体系结构仅规定协议的功能和消息格式，但对具体的实现细节由具体设备厂商来确定，对于网络的层次，以及每一个层次的协议及其功能都是网络体系结构所要描述的内容，因此答案为选项C.
2． 一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（ ）个不同的码字。
A.107
B.108
C.214
D.215
【答案】B
【解析】此题可转化为一棵哈夫曼树共有215个结点，共有多少叶子结点。又有n0＝n2＋+l，所以215＝n0＋n2＝2*n2＋l ，n2＝107，n0＝108。也就是说若对其进行哈夫曼编码，共能得到108个码字。
3． 在子网
A.0
B.1
C.2
D.4
【答案】C 中, 能接收目的地址为的IP 分组的最大主机数是（ ）。
【解析】每个子网中忽略子网内全为0和全为1的地址剩下的就是有效主机地址, 本题中由于子网的比特数是30, 因此用于主机的只有2位, 即00, 01, 10, 11, 有效主机地址是2个,
这里
显然是其广播地址, 因此答案是C 。
4． 当字符序列
A.4个
B.5个
作为图输入时，输出长度为3的且可用作C 语言标识符的序列的有（ ）。
C.3个
D.6个
图
【答案】C
【解析】首先需要明白C 语言标识符的命名规则。数字不能作为标识符的开头，因此第一个字符只能为t 或者下划线。若首字符为t ，有两种结果
和，若首字符为，
则只有一种结果
因此总共有3种结果。
5． 有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（ ）。
A.543612
B.453126
C.346521
D.234156
【答案】C
【解析】根据栈的后进先出的特点，对于C 选项中前两个元素得出栈顺序可以看出，4在5和6前先出栈，又根据入栈顺序，4在5和6后入栈，因此4出栈时，5和6必定在栈内，且5在6之上，所以出栈时5要比6先出枝。
6． 数据序列(8，9，10，4，5，6，20，1，2) 只能是下列排序算法中的（ ）的两趟排序后的结果。
A. 选择排序
B. 起泡排序
C. 插入排序
D. 堆排序
【答案】C
【解析】选择排序、起泡排序和堆排序两趟排序后，在序列的某一端应该有序列的两个最大值或者最小值。
7． 下列有关浮点数加减运算的叙述中, 正确的是（ ）。
Ⅰ. 对阶操作不会引起阶码上溢或下溢
Ⅱ. 右规和尾数舍入都可能引起阶码上溢
Ⅲ. 左规时可能引起阶码下溢
Ⅳ. 尾数溢出时结果不一定溢出
A. 仅Ⅱ Ⅲ
B. 仅Ⅰ Ⅱ Ⅳ
C. 仅Ⅰ Ⅲ Ⅳ
D. Ⅰ Ⅱ ⅢⅣ
【答案】D
【解析】浮点数的加减运算步骤包括:①对阶, 使两个操作数的小数点位置对齐, 阶码小的尾数右移, 可能产生溢出, 但是阶码不会溢出; ②尾数求和, 将对阶后的尾数按定点数加(减) 运算规则运算; ③规格化, 包括左规和右规, 左规时阶码减少, 可能出现阶码下溢, 而右规时, 阶码增加可能出现阶码上溢; ④舍入, 该过程可能需要右规调整, 因此可能出现阶码上溢; ⑤溢出判断, 浮点数的溢出与否是由阶码的符号决定的, 而不是由尾数溢出判断的, 因此尾数溢出时结果不一定溢出。因此Ⅰ Ⅱ Ⅲ Ⅳ均正确。
8． 对下图进行拓扑排序, 可以得到不同的拓扑序列的个数是（ ）。
图
A.4
B.3
C.2
D.1
【答案】B
【解析】拓扑排序的步骤为:
(1)在有向图中选一个没有前驱的顶点并且输出它;
(2)从图中删除该顶点和以它为尾的弧。重复上述两步, 直至全部顶点均已输出。由于没有前驱的顶点可能不唯一, 所以拓扑排序的结果也不唯一。题中所给图有三个不同的拓扑排序序列, 分别为abced , abecd , aebcd 。
9． 某计算机采用微程序控制器, 共有32条指令, 公共的取指令微程序包含2条微程序, 各指令对应的微程序平均由4条微指令组成, 采用断定法(下址字段法) 确定下条微指令的地址, 则微指令中下址字段的位数至少是:（ ）
A.5
B.6
C.8
D.9
【答案】C 【解析】, ,
所以至少需要8位才能表示完130个地址。