2018年延边大学工学院832数据结构与操作系统之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 已知二叉树丁的结点形式为(llink，data ，count ，riink) ，在树中查找值为X 的结点，若找到， 则记数(count)加1; 否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。
【答案】算法如下:
在二叉排序树t 中査找值为x 的结点，若査到，则其结点的count 域值增1，否则，
将其
插入到二叉排序树中
f 指向当前结点的査找值为x 的结点，
双亲
无值为x 的结点，插入之
査询成功，值域为x 的结点的count 增
1
2． 对给定关键字序号j(1 中找到关键字从小到大排在第j 位上的记 录，写一个算法利用快速排序的划分思想实现上述查找(要求用最少的时间和最少的空间) 。 例如:给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。 【答案】算法如下； 在后半部分继续进行划分 在前半部分继续进行划分 3． 请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink —rlink 法存储。 【答案】算法如下: 判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag 得出结论 中序遍历左子树 中序遍历的第一个结点不必判断 前驱指针指向当前结点 不是完全二叉树 中序遍历右子树 算法结束 判断二叉树t 是否是二叉排序树，若是，返回true ，否则，返回 false 若左右子树均为二叉 排序树 左子树中的最大值和右子树中 的最小值 不是二叉排序树 结束 求二叉树左子树的最大值 返回机器最小整数 求二叉树右子树的最小值 返回机器最大整数 4． 给定nxm 矩阵 并设 设计一算法判定x 的值是否在A 中，要求时间复杂度 为O(m＋n) 。 【答案】算法如下: //n*m矩阵A ，行下标从a 到b ，列下标从c 到d ，本算法査找x 是否在矩阵A 中 //flag是成功査到x 的标志 //假定x 为整型 (“矩阵A 中无 算法search 结束。 5． 对于任意的无符号的十进制整数m ，写出将其转换为十六进制整数的算法(转换仅要求能够输出正确的十六进制的整数即可) 。 【答案】算法如下: //本算法将无符号十进制整数m 转换为十六进制整数 本算法的递归描述如下: //本算法将无符号十进制整数m 转换为十六进制整数 元素\n"，x) ；
相关内容
相关标签