2018年郑州大学软件技术学院408计算机学科专业基础综合之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 设计算法将一个带头结点的单链表A 分解为两个具有相同结构的链表B 、C , 其中B 表的结点为A 表中值小于零的结点，而C 表的结点为A 表中值大于零的结点(链表A 的元素类型为整型，要求B 、C 表利用A 表的结点) 。
【答案】算法如下:
//本算法将带头结点的单链表A 分解成数据域值小于零和大于零的两个单链表B 和
C
//为C 申请结点空间
//C初始化为空表
//P为工作指针
//B表初始化
//暂存P 的后继
//小于0的放入B 表
//将小于0的结点链人B 表
//P指向新的待处理结点
//算法结束
2． 令G=(V, E) 为一个有向无环图，编写一个给图G 中每一个顶点赋以一个整数序号的算法，并满足以下条件:若从顶点i 至顶点j 有一条弧，则应使i 【答案】算法如下: 对以邻接表存储的DAG 图g 重新编号, 使若有 第 2 页，共 34 页 ，则编号 求各顶点的入度 记录结点的逆序序号 3． 在一个循环链队中只有尾指针(记为rear ，结点结构为数据域data ，指针域next) ，请给出这种队列的入队和出队操作的实现过程。 【答案】算法如下: //rear是带头循环链队列的尾指针，本算法将元素X 插入到队尾 //申请结点空间 //将s 结点链入队尾 //rear指向新队尾 //rear是带头结点的循环链队列的尾指针 //本算法执行出队操作，成功输出队头元素；否则给出出错信息 //s指向队头元素 //队头元素出队 //空队列 4． 起泡排序算法是把大的元素向上移(气泡的上浮) ，也可以把小的元素向下移(气泡的下沉；请给出上浮和下沉过程交替的起泡排序算法。 【答案】算法如下: 相邻两趟向相反方向起泡的起泡排序算法， 起泡的上下界 设不发生交换 以上向下起泡 有交换，修改标志 第 3 页，共 34 页 change 修改界 气泡下沉，小元素上浮(向左 ) 修改下界 5． 设二叉树用二指针结构存储(可以是动态存储结构) ，元素值为整数，且元素值无重复，请编写子程序，求出以元素值等于某个给定的整数的结点为根的子树中的各个叶结点。 【答案】算法如下: 在二叉树t 中査找结点值等于x 的结 点 结束 统计以t 为根结点的子树的叶结点数 n0 . 叶结点 输出并计数 结束 : 二、应用题 6． 设mxn 阶稀疏矩阵A 有t 个非零元素，其三元组表示为素的个数t 达到什么程度时用LTMA 表示A 才有意义？ 【答案】稀疏矩阵A 有t 个非零元素，加上行数mu 、列数nu 和非零元素个数tu(也算一个三元组) ，共占用三元组表LTMA 的3(t＋1) 个存储单元，用二维数组存储时占用m*n个单元，只有当3(t＋1) ＜m*n时，用LTMA 表示A 才有意义。解不等式得t ＜m*n/3﹣l 。 试问:非零元 第 4 页，共 34 页