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

一、算法设计题

1． 设单链表的表头指针为h ，结点结构由data 和next 两个域构成，其中data 域为字符型。写出算法dc(h，n) ，判断该链表的前n 个字符是否中心对称。例如xyx ，xyyx 都是中心对称。

【答案】算法如下:

//h是带头结点的n 个字符元素的单链表，本算法判断链表是否中心对称

//i记下结点个数，s 是字符栈

//P是链表的工作指针，指向待处理的当前元素

//链表前一半元素入栈

//恢复最后的i 值

//若n 是奇数，后移过中心结点

//测试

是否中心对称

//链表中心对称

//链表不中心对称

//算法结束

2． 已知二叉树T ，试写出复制该二叉树的算法(t→T) 。

【答案】算法如下:

复制二叉树t 的非递归算法

是二叉树的结点指针的队列，容量足够大

结束本题

3． 有二叉排序树采用二叉链表方式存放，树中结点值各不相同，欲得到一个由大到小的结点值递减序列，简述处理方法思路，用非递归形式写出算法。

【答案】算法如下:

按递减次序输出二叉排序树结点的值

是元素为二叉树结点指针的栈，容量足够大

沿右子树向下

结束

4． 请运用快速排序思想，设计递归算法实现求n(n>1)个不同元素集合中的第f(

【答案】算法如下:

在后半部分继续进行划分

在前半部分继续进行划分

5． 已知顺序表中有m 个记录，表中记录不依关键字有序排列，编写算法为该顺序表建立一个有序的索引表，索引表中的每一项含记录的关键字和该记录在顺序表中的序号，要求算法的时间复杂度在最好的情况下能达到O(m)。

【答案】算法如下:

顺序表中记录个数

关键字

该关键字在顺序表中的下标

索引表的一项

) 小元素。

关键字

记录中的其他数据

给有m 个记录的顺序表seq 建立索引表

index

监视哨

关键字放入正确位置

第i 个记录的下标

二、应用题

6． 假定在一个8位字长的计算机中运行下列C 程序段:

若编译器编译时将8个8位寄存器R1〜R8分别分配给变量x 、y 、m 、n 、z1、Z2、k1和k2。请回答下列问题。(提示:带符号整数用补码表示)

(1)执行上述程序段后, 寄存器R1、R5和R6的内容分别是什么？(用十六进制表示) (2)执行上述程序段后, 变量m 和k1的值分别是多少？(用十进制表示)

(3)上述程序段涉及带符号整数加/减、无符号整数加/减运算, 这四种运算能否利用同一个加法器及辅助电路实现? 简述理由。

(4)计算机内部如何判断带符号整数加/减运算的结果是否发生溢出? 上述程序段中, 哪些带符号整数运算语句的执行结果会发生溢出？

【答案】(1)无符号整数运算,

(R1)=x=134=10000110B=86H、(R5)=x-y=246=10010000B=90H、(R6)=x+y=01111100B=7CH。 (2)m的机器数与x 的机器数相同为86H=10000110B, 解释为带符号整数(用补码表示) 时, 其值为-1111010B=-112;

同理kl=(m-n)=(x-y)=90H=10010000B, 解释为带符号整数(用补码表示) 时, 其值为-1111010B=-112;

(3)四种运算可以利用同一个加法器及辅助电路实现, n

位加法器实现的是模无符号整数加法运算。对于无符号整数a 和b , a+b可以直接用加法器实现, 而

实现; 对于带