2018年北京科技大学冶金工程研究院408计算机学科专业基础综合之数据结构考研核心题库
● 摘要
一、填空题
1． 执行顺序查找时，存储方式可以是_____，折半查找时，要求线性表_____，分块查找时要求线性表_____，而哈希表的查找，要求线性表的存储方式是_____。
【答案】顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储
2． N 个顶点的连通图用邻接矩阵表示时，该矩阵至少有_____个非零元素。 【答案】
【解析】所谓连通图一定指的是无向图，有向图会称作强连通图。连接N 个顶点，至少需要N －1条边就可以了。由于无向图的每一条边同时关联了两个顶点。因此用邻接矩阵表示时，该矩阵至少有2(N－1) 个非零元素。
3． 已知链队列的头尾指针分别是f 和r ，则将值x 入队的操作序列是_____。
【答案】S ＝(LinkedList*)malloc(sizeof (LNode))；s ﹣＞data ＝x ；s ﹣＞next ＝r ﹣＞next ；r ﹣＞next ＝s ；r ＝s ；
【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。
4． 顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。
【答案】物理上相邻；指针
【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。
5． 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空:
(_____i)；
＝
_____.
_____
【答案】a ＋l ；n%10
【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。
二、单项选择题
6． 分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（ ）。
A.(100, 80, 90, 60, 120, 110, 130)
B.(100, 120, 110, 130, 80, 60，90)
C.(100, 60, 80, 90, 20, 110, 130)
D.(100, 80, 60, 90, 120, 130, 110)
【答案】C
【解析】二叉排序树:左右子树都是二叉排序树，且保证右子树都比根结点大，左子树都比根结点小。据以上两点建立二叉排序树。
7． 在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（ ）。
A. 直接插入排序
B. 起泡排序
C. 简单选择排序
D. 快速排序
【答案】A
【解析】当待排序列基本有序时，对冒泡排序来说，若最大关键字位于序列首部，则每趟排序仅能使其“下沉”一个位置，要使其下沉到底部仍需n －1趟排序，也即时间复杂度仍为0(n2)。而对简单选择排序来说，其比较次数与待排序列的初始状态无关；归并排序要求待排序列已经部分有序，而部分有序的含义是待排序列由若干有序的子序列组成，即每个子序列必须有序，并且其时间复杂度为；直接插入排序在待排序列基本有序时，每趟的比较次数大为降低，也
2即n －1趟，比较的时间复杂度由O(n) 降至O(n)。
8． 假定有k 个关键字互为同义词，若用线性探测法把这k 个关键字存入哈希表中，至少要进行多少次探测？（ ）
A.k －1次
B.k 次
C.k+1次 D.
【答案】D
次
【解析】至少探测次数。
9． 用海明码对长度为8位的数据进行检/纠错时, 若能纠正一位错, 则校验位数至少为（ ）
A.2
B.3
C.4
D.5
【答案】C
【解析】设校验位的位数为k , 数据位的位数为n , 根据海明码编码k 和n 应满足下述关系。
。
n=8, 当k=4时, , 符合要求, 校验位至少是4位, 故答案为C 。
10．下列关于中断方式和DMA 方式比较的叙述中, 错误的是（ ）
A. 中断方式请求的是方式请求的是CPU 处理时间, DMA 方式请求的是总线使用权
B. 中断响应发生在一条指令执行结束后, 中断响应发生在一条指令执行结束后, DMA 响应发生在一个总线事务完成后
C. 中断
送由硬件完成
D. 中断
设备
【答案】D
【解析】中断处理方式:在
与设备输入每个数据的过程中, 由于无需CPU 干预, 因而可使CPU
设备并行工作。仅当输完一个数据时, 才需CPU 花费极短的时间去做些中断处理。因此中断
设备方式适用于所有外部设备, 方式适用于所有外部设备, DMA 方式仅适用于快速外部方式下数据传送通过软件完成, 方式下数据传送通过软件完成, DMA 方式下数据传申请使用的是CPU 处理时间, 发生的时间是在一条指令执行结束之后, 数据是在软件的控制下完成传送。而DMA 方式与之不同。DMA 方式:数据传输的基本单位是数据块, 即在CPU 与
之间, 每次传送至少一个数据块, DMA 方式每次申请的是总线的使用权, 所传送的数据是从设备直接送入内存的或者相反; 仅在传送一个或多个数据块的开始和结束时, 才需CPU 干预, 整块数据的传送是在控制器的控制下完成的。答案D 的说法不正确。
11．设有数组A[i，j]，数组的每个元素长度为3字节，i 的值为1到8，j 的值为1到10，数组从内存首地址BA 开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为（ ）。
A.BA+141
B.BA+180
C.BA+222
D.BA+225
【答案】B
【解析】在计算中，可以考虑按照列存放时，A[5，8]在内存的位置，比较容易计算元素的首地址。比如A[5，8]顺序存放时，它是第7*8＋5＝61个元素，由于首地址为BA ，所以它的存储首地址为BA ＋(61﹣1)*3＝180+BA。