2017年昆明理工大学J012数据结构与算法分析(同等学力加试)复试实战预测五套卷
● 摘要
目录
2017年昆明理工大学J012数据结构与算法分析(同等学力加试) 复试实战预测五套卷（一）... 2 2017年昆明理工大学J012数据结构与算法分析(同等学力加试) 复试实战预测五套卷（二）... 8 2017年昆明理工大学J012数据结构与算法分析(同等学力加试) 复试实战预测五套卷（三）. 17 2017年昆明理工大学J012数据结构与算法分析(同等学力加试) 复试实战预测五套卷（四）. 22 2017年昆明理工大学J012数据结构与算法分析(同等学力加试) 复试实战预测五套卷（五）. 29
第 1 页，共 35 页
一、应用题
1． 写出下面算法中带标号语句的频度。
设k 的初值等于1。
【答案】（1）这是一个递归调用，因k 初值为1，由语句（6）知，每次调用k 增1，故第（1）语句执行n 次，所以频度是n 。
（2）这是FOR 循环语句，在满足（1）的条件下执行，该语句进入循环体（3）n 次，加上最后一次判断出界，故执彳丁了n ＋1次，所以频度是n ＋1。
（3）这是循环体语句，共执行了n 次，所以频度是n 。
，k=2时判断n 次，最后（4）这是循环语句，当k=l时判断n ＋1次（进入循环体（5）n 次）
一次k=n－l 时判断3次，故执行次数是（n ＋1）＋n ＋... ＋3=（n ＋4）（n －1）/2次，所以频度是（n ＋4）（n －1）/2。
（5）语句（5）是（4）的循环体，每次比（4）少一次判断，故执行次数是n ＋（n －1）＋... ＋2=（n ＋2）（n －1）/2次，所以频度是（n ＋2）（n －1）/2。
（6）这是循环体语句，共执行了n －1次，所以频度是n －1。
2． 设哈希（Hash ）表的地址范围为0～17，哈希函数为：造出哈希表，试回答下列问题：
（1）画出哈希表示意图；
第 2 页，共 35 页
为关键字，用
线性探测再散列法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49）
（2）若查找关键字63，需要依次与哪些关键字比较？ （3）若查找关键字60，需要依次与哪些关键字比较？
（4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 【答案】（1）哈希表示意图如表所示：
表 哈希示意图
（2）查找关键字63时，由于63比较。
（3）查找关键字60时，由于（4）
哈希地址12内为空，查找失败。 所以需要依次与31，46，47，32，17，
3． 某计算机字长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位，则指令系统最多可有
条不同的指令；指令操作上占6
个通用寄存器；主存容
位，寻址方式占3位，于是寄存器编号占3位，该计算机最多可以有
第 3 页，共 35 页
（逗号前为源操作数，逗号后为目的操作数）
对应的机器码是什么（十六进制表示）？该指令执行后，哪些寄存器和存储单元的内容会改变?
量为128KB ，计算机字长为16位，故主存有需16位。
个存储单元，故MDR 和MAR 至少各
（2）由于寄存器字长为16位，所以转移指令的目标地址范围为0000H 〜FFFFH 。。 （3）汇编语句寄存器
R5和地址为5678H 的存储单元的内容会改变，改变后的内容分别为
：
4． 如果两个串含有相等的字符，能否说它们相等？
【答案】仅从两串含有相等的字符，不能判定两串是否相等，两串相等的充分必要条件是两串长度相等且对应位置上的字符相同（即两串串值相等）。
5． 为什么文件的倒排表比多重表组织方式节省空间？
【答案】倒排表有两项，一是次关键字值，二是具有相同次关键字值的物理记录号，这些记录号有序且顺序存储，不使用多重表中的指针链接，因而节省了空间。
6． 二叉树的带权路径长度（WPL ）是二叉树中所有叶结点的带权路径长度之和，给定一棵二叉树T ，采用二叉链表存储，节点结构为：
其中叶节点的weight 域保存该结点的非负权值。设root 为指向T 的根节点的指针，设计求T 的WPL 的算法。要求：
（1）给出算法的基本设计思想；
（2）使用C 或C++语言，给出二叉树结点的数据类型定义；
（3）根据设计思想，采用C 或C++语言描述算法，关键之处给出注释。
【答案】（1）算法的基本思路是利用利用递归的思想来求解二叉树的带权路径长度，如果当前节点不是叶子节点，那么当前节点为根的树的带权路径长度便等于它的子树的带权路径长度之和，对于此函数要传入一个当前节点的树高的形参，那么递归调用孩子节点时只需要将这个形参加一即可。
（2）
typedef struct BiNode
（3）具体算法实现如下：
如果当前节点为空节点
第 4 页，共 35 页
+对应的机器码为该指令执行后，
相关内容
相关标签