2017年武汉科技大学信息科学与工程学院856数据结构(C语言版)考研题库
● 摘要
一、选择题
1． 某计算机存储器按字节编址，采用小端方式存放数据。假定编译器规定int 和short 型长度分别为32位和16位，并且数据按边界对齐存储。某C 语言程序段如下：
若record
变量的首地址为则地址中内容及record.c 的地址分别为（ ）。
A.
B.
C.
D. 【答案】D 。
【解析】32位整数a 需要占4个字节，16位整数c 需要占2个字节，而字符数据b 占一个字节。a=273, 转换成十六进制是111H , 采用小端方式存放数据，地址0xC008中的内容为11H 。由于数据按边界对齐存储，地址
地址
2． 下列排序算法中，其中（ ）是稳定的。
A. 堆排序，起泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，起泡排序 【答案】D
3． 已知一棵有2011个结点的树，其叶结点个数为116, 该树对应的二叉树中无右孩子的结点个数是（ ）。
A.115 B.116 C.1895 D.1896 【答案】D
【解析】每个非终端结点转换成二叉树后都对应一个无右孩子的结点（因为一个非终端结点，另外，树根结点转至少有一个孩子结点，其最右边的孩子结点转换成二叉树后一定没有右孩子）
换成二叉树后也没有右孩子。题目中树的总结点数是2011，叶结点个数是116, 则非终端结点个数
第 2 页，共 66 页
中存放a , 地址中存放b , 地址中空闲，
中存放c 。
是2011-116=1895, 则该树对应的二叉树中 无右孩子的结点个数是1895+1=1896。
4． 连续存储设计时，存储单元的地址（ ）。
A. 一定连续 B. 一定不连续 C. 不一定连续
D. 部分连续，部分不连续 【答案】A
【解析】连续存储是指数据的物理存储相连，即存储单元的地址是连续的。
5． 某计算机有16个通用寄存器，采用32位定长指令字操作码字段（含寻址方式位）为8位，Store 指令的源操作数和目的操作数分别采用寄存器直接寻址和基址寻址方式，若基址寄存器可使用任一通用寄存器，且偏移量用补码表示，则Store 指令中偏移量的取值范围是（ ）
A.-32768〜+32767 B.-32767〜+32768 C.-65536〜+65535 D.-65535〜+65536 【答案】A
【解析】寄存器个数指令编址方式如下所示：
16位补码取值范围为-32768〜+32767，所以偏移量取值范围为-32768〜+32767
6． 若平衡二叉树的高度为6, 且所有非叶结点的平衡因子均为1，则该平衡二叉树的结点总数为（ ）。
A.12 B.20 C.32 D.33
【答案】B 。
【解析】本题题目的实际问题是，具有6层结点的平衡二叉树含有最少的结点数是多少。表示深度为h 的平衡二叉树中含有的最少结点数，有
由此可得
对应的平衡二叉树如下图所示。
偏移量有32-8-4-4=16位
第 3 页，共 66 页
7． 知一棵二叉树的前序遍历结果为ABCDEF ，中序遍历结果为CBAEDF ，则后序遍历结果为（ ）。
A.CBEFDA B.FEDCBA C.CBEDFA D. 不定
【答案】A
【解析】由前序结果可知A 为根节点，再由中序遍历结果知BC 为A 的左孩子，且C 为B 的左孩子结点，到此可排除B 项，按照这种逻辑依次推理，便可得出结果对于该类型题目，可以先根据前序遍历结果和中序遍历结果画出二叉树，然后后序遍历二叉树得到后序遍历序列。
8． 若一个有向图具有拓扑排序序列，那么它的邻接矩阵必定为（ ）。
A. 对称矩阵 B. 稀疏矩阵 C. 三角矩阵 D. —般矩阵 【答案】C
【解析】在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为改图的一个拓扑排序：①每个顶点出现且出现一次；②若顶点在序列中排在顶点B 的前面，则在 图中不存在从顶点B 到顶点A 的路径。由拓扑排序的性质知，有向图的邻接矩阵必定为三角矩阵。
9． 某计算机使用4体交叉存储器，假定在存储器总线上出现的主存地址（十进制）序列为8005, 8006，8007，8008, 8001，8002，8003，8004，8000， 则可能发生发生缓存冲突的地址对是（ ）。
A.8004、8008 B.8002、8007 C.8001、8008 D.8000、8004 【答案】D
【解析】交叉存储器，又称低位交叉编址，即低位地址为体号，高位地址为体内地址。本题中，主存地址对应的体号分别是：1，2，3，4，1，2，3，4，4。地址为8004和8000都是存取的四号储存器，可能导致8004存储还未完成而又存取8000地址，因此可能发生缓存冲突。
10．要连通具有n 个顶点的有向图，至少需要（ ）条边。
A.n-1 B.n C.n+1
第 4 页，共 66 页