2017年西北师范大学955数据结构复试仿真模拟三套题
● 摘要
一、应用题
1． 二叉树的带权路径长度（WPL ）是二叉树中所有叶结点的带权路径长度之和，给定一棵二叉树T ，采用二叉链表存储，节点结构为：
其中叶节点的weight 域保存该结点的非负权值。设root 为指向T 的根节点的指针，设计求T 的WPL 的算法。要求：
（1）给出算法的基本设计思想；
（2）使用C 或C++语言，给出二叉树结点的数据类型定义；
（3）根据设计思想，采用C 或C++语言描述算法，关键之处给出注释。
【答案】（1）算法的基本思路是利用利用递归的思想来求解二叉树的带权路径长度，如果当前节点不是叶子节点，那么当前节点为根的树的带权路径长度便等于它的子树的带权路径长度之和，对于此函数要传入一个当前节点的树高的形参，那么递归调用孩子节点时只需要将这个形参加一即可。
（2）
typedef struct BiNode
（3）具体算法实现如下：
如果当前节点为空节点
//如果当前节点的左右孩子节点都为空，即当前节点为叶子节点，直接返回当前节点的
WPL
//如果当前节点不是叶子节点，则对当前节点的左右子树进行递归，返回左右子树WPL 之和
2． 某程序中有如下循环代码段p :
P 起始地址 为0804 8100H，对应的汇编代码和机器代码如下表所示
假设编译时变量sum 和i 分
别分配在寄存器R1和R2中。常量N 在寄存器R6中，数组A 的首地址在寄存器R3中，程序段
执行上述代码的计算机M 采用32位定长指令字，其中分支指令Bne 采用如下格式，
Op 为操作码：Rs 和Rd 为寄存器编号：OFFSET 为偏移量，用补码表示。请回答下列问题，并说明理由。
（1）M 的存储器编址单位是什么？
（2）已知sll 指令实现左移功能，数组A 中每个元素占多少位？
（3）表中bne 指令的OFFSET 字段的值是多少？已知bne 指令采用相对寻址方式，当前PC 内容为bne 指令地址，通过分析表中指令地址和bne 指令内容，推断出bne 指令的转移目标地址计算公式。
（4）若M 采用如下“按序发射、按序完成”的5级指令流水线：IF （取指）、ID （译码及，且硬件不采取任何转发措施，分取数）、EXE （执 行）、MEM （访存）、WB （写回寄存器）支指令的执行均引起3个时钟周期阻塞，则P 中哪些指令的执行会由于数据相关而发生流水线阻塞？哪条指令的执行会发生控制冒险？为什么指令1 的执行不会因为与指令5的数据相关而发生阻塞？
【答案】（1）由题可知，指令为32为即4个字节，而程序执行时是以4为间隔逐条取指令的，故可知M 的存储器是采用字节编址。
（2）32位，因为sll 中实现左移，而（R2） <<2 R4即左移两位就是乘以4，所以是位
（3）由Bne 的指令格式可知其OFFSET 为指令的后16位，而Bne 的机器码码为1446 FFFAH，所以Bne 的OFFSET 为FFFAH 即-6。
由题可知Bne 采用相对寻址方式，故有效地址为当前
Bne
指令的地址
即
而取完
Bne
而PC 的值指令后
，
而要跳转到指令1的地址08048100H ，两者相差了18H 也
就是24个字节，而OFFSET 是-6, 故转移目标地址计算公式为（PC
）
（4）由指令序列可知，指令1需写R4而指令2需读R4, 故指令2会因为数据相关而发生阻
塞，同理指令3、指令4也会因为数据相关而发生阻塞；而指令6为分支指令，故其存在控制冒险。因为分支指令会有3个时钟周期的阻塞，故指令1的执行不会因为指令5的数据相关而发生阻塞。
3． 设目标为
模式为
（1）计算模式p 的nextval 函数值；
（2）不写出算法，只画出利用KMP 算法进行模式匹配时每一趟的匹配过程。 【答案】（1）P 的nextval 函数值为0110132（P 的next 函数值为0111232）。 （2）利用KMP （改进的nextval ）算法，每趟匹配过程如下： 第一趟匹配：abcab （i=5, j=5） 第二趟匹配：abc （i=7，j=3） 第三趟匹配：a （i=7，j=l） 第四趟匹配：
（成功）abcabaa （i=15，j=8）
4． 在采用线性探测法处理冲突的哈希表中，所有同义词在表中是否一定相邻？
【答案】不一定相邻。哈希地址为
的关键字，和为解决冲突形成的探测序列f 的
同义词，都争夺哈希地址i 。
5． 设哈希（Hash ）表的地址范围为0～17，哈希函数为：造出哈希表，试回答下列问题：
（1）画出哈希表示意图；
（2）若查找关键字63，需要依次与哪些关键字比较？ （3）若查找关键字60，需要依次与哪些关键字比较？
（4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 【答案】（1）哈希表示意图如表所示：
表 哈希示意图
（2）查找关键字63时，由于63比较。
为关键字，用
线性探测再散列法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49）
所以需要依次与31，46，47，32，17，