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

一、算法设计题

1． 辅助地址表的排序是不改变结点物理位置的排序。辅助地址表实际上是一组指针，用它来指出结点排序后的逻辑顺序地址。设

用

表示辅助地址表。初始时

减序) 算法的语句序列。

【答案】算法如下:

一趟排序无交换发生，结束

表示n 个结点的值，用

，在排序中，凡需对结点交换就用它的地址

来进行。例如当n=3时，对K(31，11，19) 则有T(2，3，1) 。试编写实现辅助地址表排序(按非递

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

【答案】算法如下:

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

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

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

//链表前一半元素入栈

//恢复最后的i 值

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

//测试

是否中心对称

//链表中心对称

//链表不中心对称

//算法结束

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

【答案】算法如下:

二路插入排序的算法

辅助存储

插人后部

折半査找插入位置

移动元素

插入有序位置

插入前部

移动元素

将序列复制回去

4． 从键盘上输入一串正整数，最后输入-1作为结束标志。如:8，7，1，22，98，46，... ，75，-1。请设计一个非递归程序，创建一棵二叉排序树，并且该二叉排序树也必须是中序线索二叉树。设ltag ，data ，rta9，right) 。该二叉排序树上的结点结构为(teft，其中:data 域为结点的数据场。那么left 域中存在的是该结点的左儿子结点的地址。序遍历次序的前驱结点的地址。

【答案】算法如下:

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

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

，

，那么left 域中存放的是该结点的按中

，那么right

域中存放的是该结点的右儿子结点的地址。

，那么right 域中存放的是该结点的按中序遍历次序的后继结点地址。

从键盘上输入一串正整数，建立一棵初始为空的二叉排序树，同时也是线索二叉树

申请结点空间

结点赋值，其线

索初始化

查找结点的插入位置

f 是P 的双亲

根结点

左子女

修改线索

右子树根结点的值大于等于根结点的值

修改线索

读入下个数

算法结束

5． 己知字符串S1中存放一段英文，写出算法format(s1，s2，s3，n) ，将其按给定的长度n 格式化成两端对齐的字符串S2，其多余的字符送S3。

【答案】算法如下:

//将字符串si 拆分成字符串S2和字符串S3，要求字符串S2长度为n 且两端对齐

//滤掉s1左端空格

("字符串s1为空串或空格串\n")；exit(0)；

}

//字符串S1向字符串S2中

复制

(”字符串s1没有

个有效字符\n"，n) ；exit(0)；

}

//若最后一个字符为空格，则需向后找到第一个非空格字符