2018年武汉理工大学计算机科学与技术学院408计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 设有一个数组中存放了一个无序的关键序列
【答案】算法如下:
2． 令G=(V, E) 为一个有向无环图，编写一个给图G 中每一个顶点赋以一个整数序号的算法，并满足以下条件:若从顶点i 至顶点j 有一条弧，则应使i 【答案】算法如下: 对以邻接表存储的DAG 图g 重新编号, 使若有 记录结点的逆序序号 。现要求将K n 放在将元素排序后 的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n(注:用程序实现) 。 ，则编号 求各顶点的入度 3． 叙述基数排序算法，并对下列整数序列图示其基数排序的全过程。(179，208，93，306，55，859，984，9，271，33) 【答案】算法如下: 待排序记录的个数 关键字由d 个分量组成 静态链域 记录的其他数据域 存放n 个记录 . 用队列表示桶，共m 个 进行基数排序，返回收集用的链头指针 将 进行d 趟排序 初始化桶 按关键字的第j 个分量进行分配 k 为桶的序号 将将 链到桶头 链到桶尾 链成一个静态链表 将初始链表的终端结点指针置空，P 指向链表的第一个结点 队列的头、尾指针 对 修改桶的尾指针 扫描下一个记录 找第一个非空的桶 为收集链表的头指针，t 为尾指针 连接非空桶 本趟收集完毕，将链表的终端结点指针置空 4． 假设在二叉链表的结点中增设两个域:parent 域指示其双亲结点:flag 域(取值为历的递推形式的算法。 【答案】算法如下: 在增加双亲指针 和标志域 的二叉树中，不用栈后序遍历二叉树 ) 区分在遍 历过程中到达该结点时应继续向左、向右或访问该结点。试以此存储结构编写不用栈进行后序遍 向左 向右 访问根结点 找被访问结点的双亲 结束 5． 编写程序，统计在输入字符串中各个不同字符出现的频度并将结果存入文件(字符串中的合法字符为A 〜Z 这26个字母和0〜9这10个数字) 。 【答案】算法如下: （ ） //统计输入字符串中数字字符和字母字符的个数 //初始化 //’#’表示输入字符串结束 '//数字字符 //字母字符 //输出数字字符的个数 ("数字％d 的个数＝ //求出字母字符的个数 ("字母字符％c 的个数＝ //算法结束。 ) ； ) ； 二、应用题
相关内容
相关标签