考研计算机科学814,2017年西南科技大学计算机科学与技术学院814程序综合设计考研题库...

一、算法设计题

1． 试设计一个C 语言算法(或C 语言程序)：用单链表做存储结构，以回车符为结束标志，输入一个任意长度的字符串，然后判断该字符串是否为“回文”(正向读和反向读时，串值相同的字，输出信息“Y es ”或“NO ”；最后删除字符串并释放全部空间。例如： 符串称为“回文”)

若输入若输入

是回文，则输出“Yes”； 不是回文，则输出“NO”。

要求：定义相关数据类型，不得使用数组(顺序表)做字符串的存储结构和辅助存储空间。假定字符串的长度为n ，试分析上述算法的时间复杂度。

【答案】算法如下：

2． 对给定关键字序号

要求在无序记录

中找到关键字从小到大排在第j 位上的记

录，写一个算法利用快速排序的划分思想实现上述查找(要求用最少的时间和最少的空间)。

例如：给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。 【答案】算法如下：

第 2 页，共 28 页

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

【答案】算法如下：

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

赋给

再从

记录开始分

，其原则为，先将前半部和后半部(注：向量d 可视为循环表)

4． 写出按后序序列遍历中序线索树的算法。

【答案】算法如下：

//求结点

//求结点

//若t 是father 的右孩子，返回1, 否则返回0

第 3 页，共 28 页

t 最左子孙的左线索

//沿左分支向下

t 最右子孙的右线索

//沿右分支向下

//后序遍历中序线索二叉树bt

//沿左分支向下

//左孩子为线索，右孩子为链，相当从左返回

//P为叶子，相当从右返回

//访问结点

//修改P 指向双亲

//P是左子女，用最右子孙的右线索找双亲

//转向当前结点右分支

} }//结束PostOrderInThr

5． 试编写一算法对二叉树按前序线索化。

【答案】算法如下：

//设置前驱

//对以线索链表为存储结构的二叉树BT 进行前序线索化

//

设

置

左

线

索

//设置前驱的右线索

//为建立右链做准备

//前驱后移

.

//左子树前序线索化

//右子树前序线索化

6． 设二叉树用二指针结构存储(可以是动态存储结构)，元素值为整数，且元素值无重复，请编写子程序，求出以元素值等于某个给定的整数的结点为根的子树中的各个叶结点。

【答案】算法如下：

//在二叉树t 中査找结点值等于x 的结点

//结束

第 4 页，共 28 页