2018年延边大学工学院853数据结构与C程序设计[专业硕士]之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 写出一趟快速排序算法。
【答案】算法如下:
一趟快速排序算法，枢轴记录到位，并返回其所在位置
2． 按图的宽度优先搜索法写一算法判别以邻接矩阵存储的有向图中是否存在由顶点到顶点的路径
。
设有向图有n 个顶点
判断以邻接矩阵方式存储的有向图中是否存在由顶点到顶点的路径
是队列，容量足够大，元素是顶点编号
人队
到顶点
不存在路径
【答案】算法如下:
3． 编写算法，将自然数1〜n 2按“蛇形”填nxn 矩阵中。例(1〜42) 如图所示(用程序实现) 。
图
【答案】算法如下:
//将自然数
，按" 蛇形M 填入n 阶方阵A 中
//i，j 是矩阵元素的下标，k 是要填入的自然数
//从右上向左下填数
//副对角线及以上部分的新i ，j 坐标
//副对角线以下的新的i ，j 坐标
//从左下向右上
//最外层
while
4． 假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT 中，写出计算该算术表达式值的算法。
【答案】算法如下:
以后序遍历算法求以二叉树表示的算术表达式的
值
.
求左子树表示的子表达式的值
求右子树表示的子表达式的值
5． 设从键盘输入一整数的序列:a 1，a 2，a 3，... ，a n ，试编写算法实现:用栈结构存储输入的整数，
当
时，将
入栈；当
时，输出栈顶整数并出栈。算法应对异常情况(入栈满等) 给
出相应的信息。
【答案】算法如下
:
栈空间容量
//s是元素为整数的栈，本算法进行入栈和出栈操作
//top为栈顶指针，定义top ＝0时为栈空
//n个整数序列进行处理
//从键盘读入整数序列
//读入的整数不等于﹣1时人栈
//读入的整数等于﹣1时出栈
//算法结束。
二、应用题
6． 设依以下次序给出关键字:34，16，19，21，5，49，24，62，3，17，45，8，构造3阶B-树。要求从空树开始，每插入一个关键字，画出一棵树。
【答案】如图所示: