2018年北京市培养单位计算机与控制学院408计算机学科专业基础综合之数据结构考研强化五套模拟题
● 摘要
一、算法设计题
1． 对给定关键字序号j(1 中找到关键字从小到大排在第j 位上的记 录，写一个算法利用快速排序的划分思想实现上述查找(要求用最少的时间和最少的空间) 。 例如:给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。 【答案】算法如下； 在后半部分继续进行划分 在前半部分继续进行划分 2． —个有向图G=(V，E) 的平方图 ，使得表示。 【答案】算法如下: 第 2 页，共 35 页 满足下述性质 : 当且仅当存在某个顶点 且 22 。写一个算法从给定的G 求出G , G 和G 可分别用两个邻接表 3． (1)试分别找出满足下列条件的所有二叉树:(a)前序序列和中序序列相同:(b)前序序列和后序序列相同；(c)中序序列和后序序列相同。 (2)已知非空二叉树的结点结构为(lchild，data , rchild) ，设计算法:从右向左依次将所有叶子的数据值放到向量(假定向量的空间大于叶子的总个数) 中。 【答案】(1)满足条件的二叉树如下: (a)若前序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。 (b)若前序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。 (c)若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树。 (2)算法如下: 全局变量 从右向左依次将二叉树bt 的所有叶子的数据值放到a 向量中 . 中序遍历右子树 叶结点 中序遍历左子树 4． 以顺序存储结构表示串，设计算法。求串S 中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。 【答案】算法如下: //串用一维数组s 存储，本算法求最长重复子串，返回其长度 //index记最长的串在s 串中的开始位置，max 记其长度 //length记局部重复子串长度，i 为字符数组下标 //上一个重复子串结束 //当前重复子串长 度大，则更新 max //初始化下一重复子串的起始位置和长度 (”最长重复子串的长度为 .//算法结束 ，在串中的位置 ，max ，index) ； 时间复杂度:算法的时间复杂度为O(n)，每个字符与其后继比较一次。 第 3 页，共 35 页 5． 编写算法打印出由指针Hm 指向总表头的以十字链表形式存储的稀疏矩阵中每一行的非零元的个数。注意:行、列及总表头结点的形式为: 它们已用val 域链接成循环链表。非零元的结点形式也同上，每一行(列) 的非零元由right(down)域把它们链接成循环链表，该行(列) 的表头结点即为该行(列) 循环链表的表头。 【答案】算法如下: //输出由Hm 指向的十字链表中每一行的非零元素个数 //数组A 记各行非零元个数，i 记行号 //循环完各行列表头 //P是稀疏矩阵行内工作指针，num 记该行非零个 数 //完成行内非零元的查找 //指针后移 //存该行非零元个数 //移到下一行列表头 //输出各行非零元个数 第 }算法结束 行非零元个数为 } //稀疏矩阵非零元个数 二、应用题 6． 对一个有 t 个非零元素的矩阵，用的数组来表示， 其中第0行的三个元素分别为m ，n ，t ，从第一行开始到最后一行，每行表示一个非零元素；第一列为矩阵元素的行号，第二列为其列号，第三列为其值。对这样的表示法，如果需要经常进行该操作-确定任意一个元素A[i][j]在B 中的位置并修改其值， 第 4 页，共 35 页