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

一、算法设计题

1． 二路插入排序是将待排关键字序列二路插入。编写实现2-路插入排序算法。

【答案】算法如下:

二路插入排序的算法

辅助存储

插人后部

折半査找插入位置

移动元素

插入有序位置

插入前部

移动元素

将序列复制回去

中关键字分二路分别按序插入到辅助向量

前半部和后半部(注.. 向量d 可视为循环表) ，其原则为，先将r[1]赋给d[1]，再从r[2]记录开始分

2． 写算法将单链表11拆成二个链表，其中以11为头的链表保持原来向后的链接，另一个链表的头为12，其链接方向与11相反，11包含原链表的奇数序号的结点，12包含原链表的偶数序号的结点。

【答案】算法如下:

//本算法将链表L1拆成L1和L2两个链表，L2链接方向与L1相反

//空链表

//奇数序号结点在L1中

//偶数序号

结点逆置插入到L2中

//置L1

表尾

为了尽量利用

3． 设有两个栈S 1，S 2都采用顺序栈方式，并且共享一个存储区的操作算法。

【答案】找的定乂:

两栈共享顺序存储空间所能达到的最多元素数

//假设元素类型为整型

； //栈空间

//top为两个栈顶指针

//S是如上定义的结构类型变量，为全局变量

(1)入栈操作:

//入栈操作。i 为栈号，i ＝〇表示左栈Sl ，i ＝l 表示右栈s2，x 是入栈元素。入栈成功返回1，否则返回

空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S 1，S 2有关入栈和出找

(2)出栈操作

//出栈算法。i 代表栈号，i ＝0时为s1栈，i ＝l 时为s2栈。出栈成功返回出栈元素，否则返﹣

1

//算法结束

4． 对于任意的无符号的十进制整数m ，写出将其转换为十六进制整数的算法(转换仅要求能够输出正确的十六进制的整数即可) 。

【答案】算法如下:

//本算法将无符号十进制整数m 转换为十六进制整数

本算法的递归描述如下:

//本算法将无符号十进制整数m 转换为十六进制整数