2018年青海师范大学计算机学院408计算机学科专业基础综合[专业硕士]之数据结构考研核心题库
● 摘要
一、算法设计题
1． 有二叉排序树采用二叉链表方式存放，树中结点值各不相同，欲得到一个由大到小的结点值递减序列，简述处理方法思路，用非递归形式写出算法。
【答案】算法如下:
按递减次序输出二叉排序树结点的值
是元素为二叉树结点指针的栈，容量足够大
沿右子树向下
结束
2． 令G=(V, E) 为一个有向无环图，编写一个给图G 中每一个顶点赋以一个整数序号的算法，并满足以下条件:若从顶点i 至顶点j 有一条弧，则应使i 【答案】算法如下: 对以邻接表存储的DAG 图g 重新编号, 使若有 记录结点的逆序序号 ，则编号 求各顶点的入度 3． 已知关键字序列( 试写出一算法将( ) 是大根堆。 ) 调整为大根堆； 利用(1)的算法写一个建大根堆的算法。 【答案】(1)算法如下: '' 假设 是大堆，本算法把 (2) 4． 试编写在带头结点的单链表中删除(一个) 最小值结点的(高效) 算法。delete(Linklist&L) 【答案】算法如下: //L是带头结点的单链表，本算法删除其最小值结点 //P为工作指针。指向恃处理的结点。假定链表非空 //pre指向最小值结点的前驱 //q指向最小值结点，初始假定第一元素结点是最小值结点 //查最小值结点 //指针后移 //从链表上刪除最小值结点 //释放最小值结点空间 //结束算法Delete 5． 有n 个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进行排序，请写出这种排序的算法(注:双向起泡排序即相邻两趟排序向相反方向起泡) 。 【答案】算法如下: 对存储在带头结点的双向链表head 中的元素进行双向起泡排序 设标记 双向链表尾，算法过程中是向上起泡的开始结点 是工作指针，指向当前结点 调成大堆 假定本趟无交换 向下(右) 起泡，一趟有一个最大元素沉底 交换两结点指针，涉及6条链 有交换 先将结点从链表上摘下 将temp 插到p 结点前 无交换，指针后移 准备向上起泡 向上(左) 起泡，一趟有一个最小元素冒 出 交换两结点指针，涉及6条链 有交换 先将temp 结点从链表上摘 下 将temp 插到p 结点后(右 ) 无交换，指针前移 准备向下起泡 算法结束 二、应用题 6． (1)如果G1是一个具有n 个顶点的连通无向图，那么G1最多有多少条边?G1最少有多少条边？ (2)如果G2是一个具有n 个顶点的强连通有向图，那么G2最多有多少条边?G2最少有多少条边？ (3)如果G3是一个具有n 个顶点的弱连通有向图，那么G3最多有多少条边?G3最少有多少条边？ 【答案】(1)G1最多n(n－1)/2条边，最少n －1条边。 ⑵G2最多n(n－1) 条边，最少n 条边。 (3)G3最多n(n－1条边，最少n －1条边。