2018年齐齐哈尔大学计算机与控制工程学院823数据结构考研核心题库
● 摘要
一、单项选择题
1． 若串S ＝'software'%其子串的数目是（ ）。
A.8
B.37
C.36
D.9
【答案】B
【解析】子串的定义是:串中任意个连续的字符组成的子序列，并规定空串是任意串的子串，任意串是其自身的子串。若字符串长度为n(n＞0) ，长为n 的子串有1个，长为n ﹣1的子串有2个，长为n ﹣2的子串有3个，...... ，长为1的子串有n 个。由于空串是任何串的子串，所以本题的答案为:8*(8＋1)/2十1＝37。故选B 。
2． 在OSI 参考模型中, 直接为会话层提供服务的是（ ）
A. 应用层
B. 表示层
C. 传输层
D. 网络层
【答案】C
【解析】OSI 参考模型中, 下层直接为上层提供服务, 而会话层的下层为传输层。
3． 在下列表述中，正确的是（ ）
A. 含有一个或多个空格字符的串称为空格串
B. 对n(n＞0) 个顶点的网，求出权最小的n ﹣1条边便可构成其最小生成树
C. 选择排序算法是不稳定的
D. 平衡二叉树的左右子树的结点数之差的绝对值不超过1
【答案】C
【解析】平衡二叉树的左右子树的深度之差的绝对值不超过1。求最小生成树时，每次挑最小权值边，是要求该边的两点都在不同的连通分量上的。
4． 若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（ ）.
A.. 起泡排序
B. 插入排序
C. 选择排序
D. 二路归并排序
【答案】B
【解析】经过两趟排序后，A 项起泡排序的结果是两个最小或最大的元素放到了序列的最终位置；B 项插入排序的结果是前三个数有序即可；C 项选择排序结果是两个最小的元素在最前面按顺序排好；D 项二路归并排序的结果是长度为4的子序列有序，即前4个数排好序，接下来的4个数排好序. 显然题目中的元素序列只能是插入排序第二趟排序后的结果，因此，B 项正确.
5． 下列排序算法中元素的移动次数和关键字的初始排列次序无关的是（ ）。
A. 直接插入排序
B. 起泡排序
C. 基数排序
D. 快速排序
【答案】C
【解析】C 项, 基数排序是采用分配和收集实现的, 不需要进行关键字的比较。ABD 三项都依赖关键字的比较, 不同的初始排列次序下元素移动的次数有很大变化, 最好情况元素正序, 则不用移动, 最坏情况元素反序, 则需要移动次(n为元素个数) 。
6． 有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（ ）。
A.60
B.66
C.18000
D.33
【答案】B
【解析】如果是全部，则是需要100*90*2个字节；但是用三元组表示的话，只需要记录非零数据的X 坐标，Y 坐标，数值即可，就是每个非零数字需要占用三个整数的空间，即2*3＝6字节，10个非零整数则是2*3*10＝60字节；如果问有效元素占的空间大小，则选A 项，但是如果从整体来看，应该多一个用来记录矩阵宽(100)、高(90)、默认值(0)的元素，所以还应该多算6个字节。所以全部为66字节，选B 项。
7． 循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。
A.rear ＝rear ＋l
B.rear ＝(rear＋1)mod(m﹣1)
C.rear ＝(rear＋1)modm
D.rear ＝(rear＋1)mod(m＋1)
【答案】D
8． 某计算机有16个通用寄存器, 采用32位定长指令字操作码字段(含寻址方式位) 为8位, Store 指令的源操作数和目的操作数分别采用寄存器直接寻址和基址寻址方式, 若基址寄存器可使用任一通用寄存器, 且偏移量用补码表示, 则Store 指令中偏移量的取值范围是（ ） A. B. C. D.
【答案】A
【解析】寄存器个数
指令编址方式如下所示:
16位补码取值范围为, 所以偏移量取值范围为
9． 5个字符有如下4种编码方案, 不是前缀编码的是（ ）
A.01, 0000, 0001, 001, 1
B.011, 000, 001, 010, 1
C.000, 001, 010, 011, 100
D.0, 100, 110, 1110, 1100
【答案】D
【解析】在一个字符集中, 任何一个字符的编码都不是另一个字符编码的前缀。约定左分支表示字符„0‟, 右分支表示字符„1‟, 则可以用从根结点到叶子结点的路径上的分支字符串作为该叶子结点字符的编码。如此得到的编码必是前缀编码。D 选项中, 编码110是编码1100的前缀, 故不符合前缀编码的定义
10．下列选项中，能引起外部中断的事件是（ ）.
A. 键盘输入
B. 除数为0
C. 浮点运算下溢
D. 访存缺页
【答案】A
【解析】所谓外部中断是指由外部事件引起的中断，在这4个选项中，只有键盘输入是真正由外部事件引起的中断.
11．为支持 中视频文件的快速随机播放, 播放性能最好的文件数据块组织方式是（ ）
A. 连续结构
B. 链式结构
C. 直接索引结构
偏移量有32-8-4-4=16位