2018年武汉理工大学计算机科学与技术学院852数据结构(C语言版)考研基础五套测试题
● 摘要
一、单项选择题
1． 将线性表的数据元素进行扩充，允许带结构的线性表是（ ）。
A. 串
B. 树
C. 广义表
D. 栈
【答案】C
【解析】串、树、桟中的数据元素都是属于非结构的原子类型，元素的值是不可分解的。数组和广义表都是允许带结构的线性表。
2． 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（ ）排序法。
A. 插入
B. 选择
C. 希尔
D. 二路归并
【答案】A
【解析】解此题需要熟知各种排序方法的基本思想。插入排序的基本思想是:假设待排序的记
录存放在数组中，排序过程的某一中间时刻，R
被划分成两个子区间
插入到有序区中适当的位置上。使和，其中:前一个子区间是已排好序的有序区，后一个子区间则是当前未排序的部分，不妨称其为无序区。将当前无序区的第1个记录变为新的有序区。这种方法通常称为增量法，因为它每次使有序区增加1个记录。
3． 在物理层接口特性中, 用于描述完成每种功能的事件发生顺序的是（ ）。
A. 机械特性
B. 功能特性
C. 过程特性
D. 电气特性
【答案】C 。
【解析】物理层的主要任务描述为确定与传输媒体接口的一些特性; 机械特性:主要定义物理
连接的边界点, 即接插装置; 电气特性:规定传输二进制位时, 线路上信号的电压高低、阻抗匹配、传输速率和距离限制; 功能特性:主要定义各条物理线路的功能; 规程特性:主要定义各条物理线路的工作规程和时序关系。而从题干可以分析描述事件先后顺序的就是规程, 也就是过程特性, 答案是C 。
4． 先序序列为a , b , c , d 的不同二叉树的个数是（ ）。
A.13
B.14
C.15
D.16
【答案】B
【解析】二叉树的先序遍历定义为:若二叉树为空, 则空操作; 否则, 访问根节点, 然后先序遍历左子树, 最后先序遍历右子树。本题中, 结点a 为二叉树的根节点, 左右子树的先序遍历可能存在下面四种情况:
①左子树为空, bcd 为右子树; ②b 为左子树, cd 为右子树; ③bc 为左子树, d 为右子树; ④bcd 为左子树, 右子树为空。
然后将左右子树继续分解, 如第①种情况的右子树先序遍历(bcd)可能有:
A. 左子树为空, 右子树为cd ;
b. 左子树为c , 右子树为d ;
c. 左子树为cd , 右子树为空。
按照这种方法继续分解左右子树, 直到不能再分解为止, 可得第①和④种情况各包含5种不同情况, 第②和③种情况各包含2种情况, 因此总共有14种不同的二叉树。
5． 执行（ ）操作时，需要使用队列做辅助存储空间。
A. 查找哈希(Hash)表
B. 广度优先搜索网
C. 前序(根) 遍历二叉树
D. 深度优先搜索网
【答案】B
【解析】查找哈希表不需要辅助存储空间，前序遍历二叉树和深度优先搜索网需要使用栈做辅助存储空间，广度优先搜索树需要队列做辅助存储空间。
6． 在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（ ）。
A. 直接插入排序
B. 起泡排序
C. 简单选择排序
D. 快速排序
【答案】A
【解析】当待排序列基本有序时，对冒泡排序来说，若最大关键字位于序列首部，则每趟排序仅能使其“下沉”一个位置，要使其下沉到底部仍需n －1趟排序，也即时间复杂度仍为0(n2)。而对简单选择排序来说，其比较次数与待排序列的初始状态无关；归并排序要求待排序列已经部分有序，而部分有序的含义是待排序列由若干有序的子序列组成，即每个子序列必须有序，并且其时间复杂度为；直接插入排序在待排序列基本有序时，每趟的比较次数大为降低，也
2即n －1趟，比较的时间复杂度由O(n) 降至O(n)。
7． 假设变址寄存器R 的内容为1000H , 指令中的形式地址为2000H ; 地址1000H 中的内容为2000H , 地址2000H 中的内容为3000H , 地址3000H 中的内容为4000H , 则变址寻方式下访问到的操作数是（ ）
A.1000H
B.2000H
C.3000H
D.4000H
【答案】D
【解析】
根据变址寻址的
操作数的实际地址,
由题可知, 变址寄存器的内容与形式地址的内容相加之后得到, 根据实际地址访问内存, 获取操作数4000H 。
8． 在下面的程序段中，对x 的赋值语句的时间复杂度为（ ）
A.O(2n)
B.O(n)
C.O(n2)
D.O(log2n )
【答案】C
2【解析】两个循环嵌套，那么语句x :＝x+l:则被执行了n 次。
9． n 个结点的线索二叉树上含有的线索数为（ ）。
A.2n
B.n ﹣1
C.n ＋1
D.n
【答案】C
【解析】线索二叉树是利用二叉树的空链域加上线索，n 个结点的二叉树有n ＋1个空链域。