2017年湘潭大学信息工程学院848数据结构(一)考研冲刺密押题
● 摘要
一、填空题
1． 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。 【答案】
【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测 的次数最小。总次数为
2． 抽象数据类型的定义仅取决于它的一组_____，而与_____无关, 即不论其内部结构如何变化，只要它的_____不变，都不影响其外部使用。
【答案】逻辑特性；在计算机内部如何表示和实现；数学特性
3． 中缀式
运算结果为_____。 【答案】
【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。
4． 设有一个10阶对称矩阵A 采用压缩存储方式， （以行为主序存储：）则的地址为_____。
【答案】33
【解析】设存储的元素的行标为i ，列标为j 。若则则的地址为若
的地址为将代入得33。
5． 执行顺序查找时，存储方式可以是_____，折半查找时，要求线性表_____，分块查找时要求线性表_____，而哈希表的查找，要求线性表的存储方式是_____。
【答案】顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储
6． 二叉树的前序序列和中序序列相同的条件是_____。
【答案】空树或任何结点至多只有右子树的二叉树
【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。
第 2 页，共 50 页 对应的前缀式为_____，若则后缀式的
7． 当广义表中的每个元素都是原子时，广义表便成了_____。
【答案】线性表
【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。
8． 已知二叉排序树的左右子树均不为空，则_____上所有结点的值均小于它的根结点值，_____上所有结点的值均大于它的根结点的值。
【答案】左子树；右子树
【解析】二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：①若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；③它的左、右子树也分别为二叉排序树。
9．
=_____
【答案】5
10．设单链表的结点结构为为指针域，已知指针px 指向单链表中data 为x 的结
_____；点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，贝懦要执行以下语句：
_____; 【答案】
二、选择题
11．已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是（ ）。
A.39
B.52
C.111
D.119
【答案】C
【解析】完全二叉树的一个特点是：叶子结点只能出现在最下层和次下层。题目中没有说明完全二叉树的高度，首先由完全二叉树的特点确定题目中树的高度。根据题意，一棵完全二叉树的第6层（设根为第1层）有8个叶结点，可知此二叉树的高度是6或7。题目中求二叉树的结点数最多的情况，因此此完全二叉树的高度为7。由于高度为7的完全二叉树的前6层是一棵满二叉树，根据二叉树的性质2可知，高度为6的满二叉树的结点数是-1=63。又根据二叉树的性质1可知，题目中二叉树的第6层结点数是
结点数最多可达-1+（-8）×2=lll。
=32个结点，已知有8个叶子结点，那么其余32-8=24个结点均为分支结点，这些结点在第7层上最多有48个子结点（即叶子结点）。所以此二叉树的第 3 页，共 50 页
12．某计算机的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直接编码法，共有33个微命令，构成5个互斥类，分别包含7、3、12、5和6个微命令，则操作控制字段至少有（ ）。
A.5位
B.6位
C.15 位
D.33 位
【答案】C 。
，根据每个类中微命令的多少可以分别【解析】33个微命令分成5个互斥类（即5个字段）
确定字段的长度 为3、2、4、3、3位，又因为采用直接编码方式，所以它们之和
就是操作控制字段的位数。
13．5个字符有如下4种编码方案，不是前缀编码的是（ ）
A.
B.
C.
D.
【答案】D
【解析】在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀。约定左分支
表示字符
右分支表示字符则可以用从根结点到叶子结点的路径上的分支字符串作为该叶子结点字符的编码。如此得到的编码必是前缀编码。D 选项中，编码110是编码1100的前缀，故不符合前缀编码的定义。
14．在系统总线的数据线上，不可能传输的是（ ）。
A. 指令
B. 操作数
C. 握手（应答）信号
D. 中断类型号型号
【答案】C
【解析】握手（应答）信号属于通信联络控制信号应该在通信总线上传输，不可能在数据总线上传输。而指令、操作数和中断类型码都可以在数据线上传输。
15．某计算机有16个通用寄存器，采用32位定长指令字操作码字段（含寻址方式位）为8位，Store 指令的源操作数和目的操作数分别采用寄存器直接寻址和基址寻址方式，若基址寄存器可使用任一通用寄存器，且偏移量用补码表示，则Store 指令中偏移量的取值范围是（ ）
A.-32768〜+32767
B.-32767〜+32768
C.-65536〜+65535
第 4 页，共 50 页 也
相关内容
相关标签