2017年曲阜师范大学软件学院859数据结构考研强化模拟题
● 摘要
一、算法设计题
1． 设二叉排序树的各元素值均不相同，采用二叉链表作为存储结构，试分别设计递归和非递归算法按递减序打印所有左子树为空，右子树非空的结点的数据域的值。
【答案】（1）递归算法如下：
（2）非递归算法如下：
2． 试将下列递归过程改写为非递归过程。
【答案】算法如下：
3． 给出以十字链表作存储结构，建立图的算法，输入（i ，j ，v ） ，其中I , j 为顶点号，v 为权值。
【答案】算法如下：
//建立有向图的十字链表存储结构
//假定权值为整型
//建立顶点向量
//当输入i , j 、v 之一为0时，结朿算
法运行
//申请结点
//弧结点中杈值域
//算法结束
4． 请运用快速排序思想，设计递归算法实现求n （n>l）个不同元素集合中的第
【答案】算法如下：
5． 已知P 是指向单向循环链表最后一个结点的指针，试编写只包含一个循环的算法，
将线性表
改造为
【答案】算法如下：
小元素。
6． 用邻接多重表存储结构，编写FIRST-ADJ （G ，V ）函数，函数返回值为第一个邻接点，若V 没有邻接点，返回零。
【答案】算法如下：
//在邻接多重表g 中，求v 的第一邻接点, 若存在，返回第一邻接点，否则返回0
（
//确定顶点v 在邻接多重表向量中的下标, 不考虑不存在v 的情况
//取第一个边结点
//返回第一邻接点，ivex 和jvex 中必有一个等干
i
7． 已知深度为h 的二叉树, 以一维数组应的算法。
【答案】算法如下： int Leaves （int BT[]，int n）
//计算深度为h. 以一维数BT 作为其存储结构的二叉树的叶结点数，n 为数组长度{int num=0; //记叶结点数
for （i=0; i 2*i+l BT （2*i+l】<0） num++; }//若结点无孩子，则是叶子else if （BT[i]>0） num++； //存储在数组后一半的元素是叶结点 return num; }//结束Leaves 作为其存储结构，试编写一算法，求该二叉 树中叶结点的个数，为简单起见，设二叉树中元素结点为非负整数，要求写出算法基本思想及相
相关内容
相关标签