2017年湖北师范大学数据结构(同等学力加试)复试仿真模拟三套题
● 摘要
一、应用题
1． 假定在一个8位字长的计算机中运行下列C 程序段：
若编译器编译时将8个8位寄存器R1〜R8分别分配给变量回答下列问题。（提示：带符号整数用补码表示）
（1）执行上述程序段后，寄存器Rl 、R5和R6的内容分别是什么？（用十六进制表示） （2）执行上述程序段后，变量m 和kl 的值分别是多少？（用十进制表示）
（3）上述程序段涉及带符号整数加/减、无符号整数加/减运算，这四种运算能否利用同一个加法器及辅助电路实现? 简述理由。
（4）计算机内部如何判断带符号整数加/减运算的结果是否发生溢出? 上述程序段中，哪些带符号整数运算语句的执行结果会发生溢出？
【答案】（1）无符号整数运算，（Rl ） =x=134=10000110B=86H、（R5）=x-y=246=10010000B=90H、（R6）=x+y=01111100B=7CH。
（2） m 的机器数与x 的机器数相同为86H=1000 0110B，解释为带符号整数（用补码表示）时，其值为-111 1010B= -112; 同理kl=（m-n ）=（x-y ）=90H=1001 0000B，解释为带符号整数（用补码表示）时，其值为-111 1010B=-112；
（3）四种运算可以利用同一个加法器及辅助电路实现，n 位加法器实现的是模2n 无符号整数加法运算。对于无符号整数a 和b , a+b可以直接用加法器实现，而
实现；
对于带符号整数用补码表示，补码加减运算公式为
：
，所以四种运算都可在n 位加法器
中实现。
（4）判断溢出的方法有3种：一位符号位、进位位和双符号位。上述程序段中只有
语句会发 生溢出，因为2个带符号整数均为负数，它们相加之后，结果小于8位二进制所能表示的最小负数。
2． 证明任一结点个数为n 的二叉树的高度至少为0 （logn ）。
【答案】最低高度二叉树的特点是，除最下层结点个数不满外，其余各层的结点数都应达到
请
各层的最大值。设n 个结点的二叉树的最低高度是h ，则n 应满足。解此不等式，并考
虑h 是整数. 则有即任一结点个数为n 的二叉树的高度至少为
3． 设内存中可利用空间已连成一个单链表，对用户的存储空间需求，一般有哪三种分配策略？
【答案】（1）首次适配法
从链表头指针开始查找，找到第一个大于等于所需空间的结点即分配。首次适配法适合事先不知道请求分配和释放信息的情况，分配时需查询，释放时插在表头。
（2）最佳适配法
链表结点大小增序排列，找到第一个大于等于所需空间的结点即分配。最佳适配法适用于请求分配内存大小范围较宽的系统，释放时容易产生存储量很小难以利用的内存碎片，同时保留那些很大的内存块以备将来可能发生的大内存量的需求，分配与回收均需查询。
（3）最差适配法
链表结点大小逆序排列，总从第一个结点开始分配，将分配后结点所剩空间插入到链表适当位置。最差适配法适合请求分配内存大小范围较窄的系统，分配时不查询，回收时查询，以便插入适当位置。
4． 已知n 阶下三角矩阵A （即当
时，有，按照压缩存储的思想，可以将其主对角线以）
下所有元素（包括主对角线上元素）依次存放于一维数组B 中，请写出从第一列开始采用列序为主序分配方式时在B 中确定元素的存放位置的公式。
【答案】2
阶下三角矩阵元素第1列到第
列是梯形，元素数为
第1列有n 个元素，第j 列有而在第j 列上的位置是为
5．
设与记录
对应的关键字分别是
进行交换。
之前全部记录
（其
的关键字一定
如果存在
和
使得
且个元素，所以n
阶下三角矩阵A 按列存储，其元素在一维数组B 中的存储位置k 与i 和j 的关系为：
成立，试证明经过一趟起泡后，一定有记录与值。由题假设知中包括为
又因
在
之前且
则
故
即说明
和
【答案】起泡排序思想是相邻两个记录的关键字比较，若反序则交换，一趟排序完成得到极
是反序；设对于
和
）中关键字最大为
，故经过起泡排序前i-2次比较后，
必定交换，证毕。
和Rf 为反序，由此可知
6． 已知世界六大城市为：北京（Pe ）、纽约（N ）、巴黎（Pa ）、伦敦（L ）、东京（T ）、墨西哥，下表给定了这六 大城市之间的交通里程：
（M ）
（1）画出这六大城市的交通网络图； （2）画出该图的邻接表表示法；
（3）画出该图按权值递增的顺序来构造的最小（代价）生成树。 【答案】（1）这六大城市的交通网络图如图1所示：
图1
（2）该图的邻接表表示法如图2所示：
图2
（3）最小生成树有6个顶点与条边：V （G ）={Pe，N ，Pa ，L , T，M}
E （G ）=（ {（L , Pa, 3）, （Pe , T, 21）, （M , N, 32）, （L , N, 55）, （L , Pe, 81）}
7． 某计算机的CPU 主频为500MHz ，CPI 为5（即执行每条指令平均需要5个时钟周期）。假定某外设的数据传输率为0.5MB/S，采用中断方式与主机进行数据传送，以32位为传输单位，对应的中断服务程序包含18条指令，中断服务的其他开销相当于2条指令的执行时间。请回答下列问题，要求给出计算过程。
（1）在中断方式下，CPU 用于该外设I/O的时间占整个CPU 时间的百分比是多少？