2017年曲阜师范大学信息科学与工程学院858数据结构与操作系统之数据结构考研仿真模拟题
● 摘要
一、算法设计题
1． 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。
【答案】算法如下：
2． 试为二叉树写出一个建立三叉链表的算法，并在此三叉链表中删去每一个元素值为x 的结点，以及以它为根的子树，且释放相应存储空间。二叉树的三叉链表的描述为：
V ARbt : bitreptr; {二叉树根结点的指针} 【答案】算法如下：
生成三叉链表的二叉树（题目给出PASCAL 定义，下面用类C 语言书
写）
/ /Q是二叉树结点指针的一维数组，容量足够大
//一维数组最后元素的下标
//元素或虚结点
_ //根结点
//双亲结点和子女结点用指针链上
}//结束creat
3． 已知P 是指向单向循环链表最后一个结点的指针，试编写只包含一个循环的算法，
将线性表
改造为
【答案】算法如下：
4． 编写算法打印出由指针Hm 指向总表头的以十字链表形式存储的稀疏矩阵中每一行的非零元的个数。注意：行、列及总表头结点的形式为：
它们已用
域链接成循环链表。非零元的结点形式也同上，每一行（列）的非零元由
域把它们链接成循环链表，该行（列）的表头结点即为该行（列）循环链表的表头。
【答案】算法如下：
5． 假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法（注： 己知树中的结点数）。
【答案】算法如下：
int Depth （PTree t） //求以双亲表示法作为存储结构的树的深度
{int maxdepth=O; For （i=l; i<=t.n; i++）
{temp=0; f=i;
while （f>0） {temp++; f=t.nodes[f].parent; }
// 深度加1，并取新的双亲
if （temp>maxdepth） maxdepth=temp; //最大深度更新 }
return （maxdepth}; //返问树的深度） //结束Depth
6． 假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT 中，写出计算该算术表达式值得算法。
【答案】算法如下： typedef struct node {ElemType data;
char optr; //只取‘+’, ‘_’, ‘*’，‘/’ struct node *lchild, *rchild }BiNode, *BiTree;
float PostEval（BiTree bt） //以后序遍历算法求以二叉树表示的算术表达式的值 {float lv, rv ； i £（btJ=null）
{iv=PostEval（bt->lchild>; //求左子树表示的子表达式的值 rv=PostEval{bt->rchild）; //求右子树表示的子表达式的值 switch （bt->optr）