当前位置：问答库＞考研试题

一、应用题

1． 在二叉树的Llink-Rlink 存储表示中，引入“线索”的好处是什么？

【答案】在二叉链表表示的二叉树中，引入线索的目的主要是便于査找结点的前驱和后继，因为若知道各结点的后继，二叉树的遍历就非常简单。利用二叉链表结构查结点的左右子女非常方便. 但其前驱和后继是在遍历中形成的。为了将非线性结构二叉树的结点排成线性序列，利用结点的空链域，左链为空时作为前驱指针，右链为空时作为后继指针。再引入左右标记ltag 和rtag ，规定：当ltag=0时，lchild 指向左子树，当ltag=1时，lchild 指向前驱：当rtag=0时，rchild 指向右子树，当rtag=l时，rctiild 指向后继。这样，在线索二叉树（特别是中序线索二叉树）上遍历就消除了递归，也不使用栈（利用后序线索二叉树査后扔继续要栈）。

2． 某计算机字长16位，主存地址空间大小为128KB , 按字编址，采用单字长指令格式，指令各字段定义如下：

源操作数目的操作数

转移指令采用相对寻址方式，相对偏移量用补码表示，寻址方式定义如下：

注：（X ）表示存储器地址X 或寄存器X 的内容。请回答下列问题：

（1）该指令系统最多可有多少条指令? 该计算机最多有多少个通用寄存器? 存储器地址寄存器（MAR ）和存储器数据寄存器（MDR ）至少各需要多少位？

（2）转移指令的目标地址范围是多少？

（3）若操作码0010B 表示加法操作（助记符为add ）, 寄存器R4和R5的编号分别为100B 和101B ，R4的内容为1234H ，R5的内容为5678H , 地址1234H 的内容为5678H ，地址5678H 中的内容为1234H ，则汇编语句

改变后的内容是什么？

【答案】（1）指令操作码占4位，则指令系统最多可有

第 2 页，共 38 页 （逗号前为源操作数，逗号后为目的操作数）对应的机器码是什么（十六进制表示）？该指令执行后，哪些寄存器和存储单元的内容会改变? 条不同的指令；指令操作上占6

位，寻址方式占3位，于是寄存器编号占3位，该计算机最多可以有

量为128KB ，计算机字长为16位，故主存有

需16位。 个通用寄存器；主存容个存储单元，故MDR 和MAR 至少各

（2）由于寄存器字长为16位，所以转移指令的目标地址范围为0000H 〜FFFFH 。。 （3）汇编语句

寄存器

R5和地址为5678H 的存储单元的内容会改变，改变后的内容分别为

：

3． 下图是5阶B 树，画出删去P 后的B 树，再画出删去D 后的B 树。

+对应的机器码为该指令执行后，

【答案】删除P 后

删除D 后

4． 下面程序段的时间复杂度是什么？

【答案】赋值语句一共被执行了m*n次，所以该程序段的时间复杂度是O （m*n）。

5． 证明若二叉排序树中的一个结点存在两个孩子，则它的中序后继结点没有左孩子，则它的中序前驱结点没有右孩子。

【答案】根据中序遍历的定义，该结点的中序后继是其右子树上按中序遍历的第一个结点：叶结点或仅有右子树的结点；而其中序前驱是其左子树上按中序遍历的最后个结点：叶结点或仅

第 3 页，共 38 页

有左子树的结点。命题得证。

6． （1）如果G1是一个具有n 个顶点的连通无向图，那么G1最多有多少条边?G1最少有多少条边？

（2）如果G2是一个具有n 个顶点的强连通有向图，那么G2最多有多少条边?G2最少有多少条边？

（3）如果G3是一个具有n 个顶点的弱连通有向图，那么G3最多有多少条边?G3最少有多少条边？

1）G1最多n （n-l ）/2条边，最少n-1条边。 【答案】（

（2）G2最多n （n-l ）条边，最少n 条边。

（3）G3最多n （n-l ）条边，最少n-1条边。

7． 设度为m 的树采用多重链表存储，毎个结点有m+1个域，其中有1个数据域，m 个指向孩子的指针。 则空指针的数目是多少？说明这种存储方式的利弊。

【答案】（1）空指针数目：n （n>0）个结点的m 度树共有nm 个链域，除根结点外，每个结点均有一个指针所指，故该树的空链域有nm-（n-1）=n（m-l ）+1个。

（2）利弊：这种存储结构统一，便于处理但空链域造成存储效率低。

8． 对下面的关键字集若查找表的装填因子为0.8，采用线性探测再哈希方法解决冲突，做：（1）设计哈希函数；（2）画出哈希表；（3）计算查找成功和查找失败的平均查找长度；（4）写出将哈希表中某个数据元素删除的算法。

【答案】（1）由于装填因子为0.8，关键字有8个，所以表长为

哈希函数，哈希函数为

（2）哈希表如表所示：

表 哈希表

（3）计算查找失败时的平均查找长度，必须计算不在表中的关键字，

当其哈希地址为时的查找次数。本例中

（4）算法如下：

第 4 页，共 38 页 用除留余数法设计 故查找失败和查找成功时的平均查找长度分别为：