当前位置：问答库＞考研试题

一、应用题

1． 证明若二叉排序树中的一个结点存在两个孩子，则它的中序后继结点没有左孩子，则它的中序前驱结点没有右孩子。

【答案】根据中序遍历的定义，该结点的中序后继是其右子树上按中序遍历的第一个结点：叶结点或仅有右子树的结点；而其中序前驱是其左子树上按中序遍历的最后个结点：叶结点或仅有左子树的结点。命题得证。

2． 在采用线性探测法处理冲突的哈希表中，所有同义词在表中是否一定相邻？

【答案】不一定相邻。哈希地址为

的关键字，和为解决冲突形成的探测序列f 的

同义词，都争夺哈希地址i 。

3． 已知一个带有表头结点的单链表，结点结构为datalink , 假设该链表只给出了头指针list 。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k 个位置上的结点（k 为正整数）。若查找成功，算法输出该结点的data 域的值，并返回1; 否则，只返回0。要求：

（1）描述算法的基本设计思想； （2）描述算法的详细实现步骤；

（3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C 或，关键之处请给出简要注释。 现）

【答案】（1）算法的基本设计思想定义两个指针变量p 和q ，初始时均指向头结点的下一个结点。p 指针沿链表移动；当p 指针移动到第k 个结点时，q 指针开始与p 指针同步移动；当p 指针移动到链表最后一个结点时，因为p 和q 相隔k ，故q 指针所指元素为倒数第k 个结点。以上过程对链表仅进行一遍扫描。

（2）算法的详细实现步骤

①count=0, p 和q 指向链表表头结点的下一个结点； ②若p 为空，转⑤; ，

③若count 等于k ，则q 指向下一个结点；否则，count=count+l; ④p 指向下一个结点，转步骤②；

⑤若count 等于k ，则查找成功，输出该结点的data 域的值，返回1; 否则，查找失败，返回0;

⑥算法结束。 （3）算法实现

第 2 页，共 33 页

或JA V A 语言实

4． 假定在一个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种：一位符号位、进位位和双符号位。上述程序段中只有

第 3 页，共 33 页

请

语句会发 生溢出，因为2个带符号整数均为负数，它们相加之后，结果小于8位二进制所能表示的最小负数。

5．

已知一个整数序列

其中

则称x 为A 的主元素。

例如

若存在

且

则称5为主元素；

又如

则A 中没有主元素。假设A 中的n 个元素保存在一个一维数组中，请设计一个

尽可能高效的算法，找出A 的主元素。若存在主元素，则输出该元素；否则输出-1。要求：

（1）给出算法的基本设计思想。 （2）根据设计思想，采用C 或【答案】

（1）算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素Num 。然后重新计数，确认Num 是否是主元素。

算法可分为以下两步：

①选取候选的主元素：依次扫描所给数组中的每个整数，将第一个遇到的整数Num 保存到c 中，记录Num 的出现次数为1; 若遇到的下一个整数仍等于Num ，则计数加1否则计数减1; 当计数减到0时，将遇到的下一个整数保存到c 中，计数重新记为1，开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素。

②判断c 中元素是否是真正的主元素，再次扫描该数组，统计c 中元素出现的次数，若大于则为主元素；否则，序列中不存在主元素。

（2）算法实现如下：

用来保存候选主元素，count 用来计数

设置A [0]为候选主元素

查找候选主元素

为A 中的候选主元素计数

处理不是候选主元素的情况

更换候选主元素

统计候选主元素的实际出现次数

第 4 页，共 33 页

或Java 语言描述算法，关键之处给出注释。

（3）说明你所设计算法的时间复杂度和空间复杂度。