2017年宁夏医科大学数据结构复试实战预测五套卷
● 摘要
一、应用题
1． 画出对算术表达式表所示。
表 操作数栈和运算符找的变化过程
求值时操作数栈和运算符栈的变化过程。
求值，过程如
【答案】设操作数栈是opnd ，运算符栈是optr ，对算术表达式
2． 从概念上讲，树、森林和二叉树是三种不同的数据结构，将树、森林转化为二叉树的基本目的是什么？ 并指出树和二叉树的主要区別。
【答案】（1）基本目的
树的孩子兄弟链表表示法和二叉树的二叉链表表示法本质是一样的，只是解释不同，也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林中的问题。
（2）主要区别
一是二叉树的度至多为2，树无此限制；二是二叉树有左右子树之分，即使在只有一个分支的情况下，也必须指出是左子树还是右子树，树无此限制：三是二叉树允许为空，树一般不允许
为空（有些书上考虑到与二叉树的转换，允许树为空）。
3． 写出下面算法中带标号语句的频度。
设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。
4． 请回答下列关于图（Graph ）的一些问题：
（1）有n 个顶点的有向强连通图最多有多少条边? 最少有多少条边？
（2）表示一个有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素? 是否稀疏矩阵？
（3）对于一个有向图，不用拓扑排序，如何判断图中是否存在环？ 【答案】⑴最多有n （n-l ）条边；最少有n 条边。 （2） 有有
个矩阵元素；不一定是稀疏矩阵（稀疏矩阵的定义是非零元素个数远小于该矩
阵元素个数，且分 布无规律）。
（3）使用深度优先遍历，按退出DFS 过程的先后顺序记录下的顶点是逆向拓扑有序序列。如果在执行DFS （V ） 未退出前，出现顶点u 到v 的回边，则说明存在包含顶点v 和顶点u 的环。
5． 某计算机字长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位，则指令系统最多可有量为128KB ，计算机字长为16位，故主存有需16位。
（2）由于寄存器字长为16位，所以转移指令的目标地址范围为0000H 〜FFFFH 。。 （3）汇编语句寄存器
R5和地址为5678H 的存储单元的内容会改变，改变后的内容分别为
：
+对应的机器码为
该指令执行后，
条不同的指令；指令操作上占6
个通用寄存器；主存容
个存储单元，故MDR 和MAR 至少各
位，寻址方式占3位，于是寄存器编号占3位，该计算机最多可以有
（逗号前为源操作数，逗号后为目的操作数）
对应的机器码是什么（十六进制表示）？该指令执行后，哪些寄存器和存储单元的内容会改变?
相关内容
相关标签