2018年贵州师范大学数学与计算机科学学院408计算机学科专业基础综合之数据结构考研强化五套模拟题
● 摘要
一、算法设计题
1． 编写对有序表进行顺序查找的算法，并画出对有序表进行顺序查找的判定树。假设每次查找时的给定值为随机值，又查找成功和不成功的概率也相等，试求进行每一次查找时和给定值进行比较的关键字个数的期望值。
【答案】算法如下:
在具有个元素的有序表R 中，顺序査找值为K 的结点，査找成功返回其位置
否则返回-1表示失败
元素序号
结束
，查找失败的平均查找
期望值分析:在等概率情况下，则查找成功的平均查找长度为
长度为(n+2)/2(失败位置除小于每一个，还存在大于最后一个) 。若查找成功和不成功的概率也相等，则查找成功时和关键字比较的个数的期望值约为。
2． 编写算法打印出由指针Hm 指向总表头的以十字链表形式存储的稀疏矩阵中每一行的非零元的个数。注意:行、列及总表头结点的形式为:
它们已用val 域链接成循环链表。非零元的结点形式也同上，每一行(列) 的非零元由right(down)域把它们链接成循环链表，该行(列) 的表头结点即为该行(列) 循环链表的表头。
【答案】算法如下:
//输出由Hm 指向的十字链表中每一行的非零元素个数
//数组A 记各行非零元个数，i 记行号
//循环完各行列表头
//P是稀疏矩阵行内工作指针，num 记该行非零个
数
//完成行内非零元的查找
//指针后移
//存该行非零元个数
//移到下一行列表头
//输出各行非零元个数
第
}算法结束
3． (1)试分别找出满足下列条件的所有二叉树:(a)前序序列和中序序列相同:(b)前序序列和后序序列相同；(c)中序序列和后序序列相同。
(2)已知非空二叉树的结点结构为(lchild，data , rchild) ，设计算法:从右向左依次将所有叶子的数据值放到向量(假定向量的空间大于叶子的总个数) 中。
【答案】(1)满足条件的二叉树如下:
(a)若前序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。 (b)若前序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。
(c)若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树。 (2)算法如下:
全局变量
从右向左依次将二叉树bt 的所有叶子的数据值放到a 向量中 .
中序遍历右子树
叶结点
中序遍历左子树
4． —个有向图G=(V，E) 的平方图
，使得表示。
【答案】算法如下:
行非零元个数为
}
//稀疏矩阵非零元个数
满足下述性质
:
2
当且仅当存在某个顶点
2
且
。写一个算法从给定的G 求出G , G 和G 可分别用两个邻接表
5． 试将下列递归过程改写为非递归过程。
【答案】算法如下:
二、应用题
6．
设与记录
对应的关键字分别是
。如果存在
和
使得j 且 成立，试证明经过一趟起泡后，一定有记录与进行交换。 【答案】起泡排序思想是相邻两个记录的关键字比较，若反序则交换，一趟排序完成得到极值。由题假设知在 ，又因 之前且 ，则 ，故 ，即说明和 是反序；设对于 和 之前全部记录: (其 中包括) 中关键字最大为 ，故经过起泡排序前i-2次比较后， 必定交换。 的关键字一定为 和Rf 为反序，由此可知 7． 证明:置换选择排序法产生的初始归并段的长度至少为m(m是所用缓冲区的长度) 。 【答案】由置换选择排序思想，第一个归并段中第一个元素是缓冲区中最小的元素，以后每选一个元素都不应小于前一个选出的元素，故当产生第一个归并段时(即初始归并段) ，缓冲区中m 个元素中除最小元素之外，其他m －1个元素均大于第一个选出的元素，即当以后读入元素均小
相关内容
相关标签