2017年空军工程大学566计算机专业基础综合之数据结构复试仿真模拟三套题
● 摘要
一、应用题
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． 二叉树的带权路径长度（WPL ）是二叉树中所有叶结点的带权路径长度之和，给定一棵二叉树T ，采用二叉链表存储，节点结构为：
其中叶节点的weight 域保存该结点的非负权值。设root 为指向T 的根节点的指针，设计求T 的WPL 的算法。要求：
（1）给出算法的基本设计思想；
（2）使用C 或C++语言，给出二叉树结点的数据类型定义；
（3）根据设计思想，采用C 或C++语言描述算法，关键之处给出注释。
【答案】（1）算法的基本思路是利用利用递归的思想来求解二叉树的带权路径长度，如果当前节点不是叶子节点，那么当前节点为根的树的带权路径长度便等于它的子树的带权路径长度之和，对于此函数要传入一个当前节点的树高的形参，那么递归调用孩子节点时只需要将这个形参加一即可。
（2）
typedef struct BiNode
（3）具体算法实现如下：
如果当前节点为空节点
//如果当前节点的左右孩子节点都为空，即当前节点为叶子节点，直接返回当前节点的
WPL
//如果当前节点不是叶子节点，则对当前节点的左右子树进行递归，返回左右子树WPL 之和
3． 设有正文AADBAACACCDACACAAD ，字符集为A , B , C , D , 设计一套二进制编码，使得上述正文的编码最短。
A :1, B :000，C :01，D :001。 【答案】字符A , B , C , D 出现的次数为9, 1, 5, 3。其哈夫曼编码如下：
4． 设度为m 的树采用多重链表存储，毎个结点有m+1个域，其中有1个数据域，m 个指向孩子的指针。 则空指针的数目是多少？说明这种存储方式的利弊。
【答案】（1）空指针数目：n （n>0）个结点的m 度树共有nm 个链域，除根结点外，每个结点均有一个指针所指，故该树的空链域有nm-（n-1）=n（m-l ）+1个。
（2）利弊：这种存储结构统一，便于处理但空链域造成存储效率低。
5． 如果两个串含有相等的字符，能否说它们相等？
【答案】仅从两串含有相等的字符，不能判定两串是否相等，两串相等的充分必要条件是两串长度相等且对应位置上的字符相同（即两串串值相等）。
6． 请回答下列关于堆（Heap ）的一些问题：
（1）堆的存储表示是顺序的还是链接的？
（2）设有一个最小堆，即堆中任意结点的关键码均不大于它的左子女和右子女的关键码。其具有最大值的元素可能在什么地方？
（3）对n 个元素进行初始建堆的过程中，最多做多少次数据比较（不用大0表示法）？
【答案】（1）堆的存储是顺序的。
（2）最大值元素一定是叶结点，在最下两层上。
（3）在建含有n 个元素、深度为h 的堆时，其比较次数不超过4n ，推导如下：
由于第i 层上的结点数至多是以它为根的二叉树的深度为则调用次筛选算法时总共进行的关键字比较次数不超过下式之值：
7． 如果只要找出一个具有n 个元素的集合的第
种最适合? 给出实现的思想。
【答案】在具有n 个元素的集合中找第个最小元素，应使用快速排序方法。其基本思想如下：设n 个元素的集合用一维数组表示，其第一个元素的下标为1，最后一个元素下标为n 。以第一个元素为“枢轴”，经过快速排序的一次划分，找到“枢轴”的位置i ，若i=k，则该位置的元素即为所求；若则在1至i-1间继续进行快速排序的划分；若则在i+1至n 间继续进
个最小元行快速排序的划分。这种划分一直进行到i=k为止，第i 位置上的元素就是第个最小元素，你所学过的排序方法中哪
素。
8． 试比较顺序文件、索引非顺序文件、索引顺序文件、哈希文件的存储代价，检索、插入、删除记录时的优点和缺点。
【答案】（1）顺序文件只能顺序查找，优点是批量检索速度快，不适于单个记录的检索。顺序文件不能像顺序表那样插入、删除和修改，因文件中的记录不能象向量空间中的元素那样“移动”，只能通过复制整个文件实现上述操作。
（2）索引非顺序文件适合随机存取，不适合顺序存取，因主关键字未排序，若顺序存取会引起磁头频繁移动。索引顺序文件是最常用的文件组织，因主文件有序，既可顺序存取也可随机存取。索引非顺序文件是稠密索引，可以“预查找”，索引顺序文件是稀疏索引，不能“预查找”，但由于索引占空间较少，管理要求低，提高了索引的查找速度。
相关内容
相关标签