2018年西安工程大学计算机科学学院408计算机学科专业基础综合之数据结构考研强化五套模拟题
● 摘要
一、算法设计题
1． 令G=(V, E) 为一个有向无环图，编写一个给图G 中每一个顶点赋以一个整数序号的算法，并满足以下条件:若从顶点i 至顶点j 有一条弧，则应使i 【答案】算法如下: 对以邻接表存储的DAG 图g 重新编号, 使若有 记录结点的逆序序号 2． 已知二叉树丁的结点形式为(llink，data ，count ，riink) ，在树中查找值为X 的结点，若找到， 则记数(count)加1; 否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。 【答案】算法如下: 在二叉排序树t 中査找值为x 的结点，若査到，则其结点的count 域值增1，否则， 将其 插入到二叉排序树中 f 指向当前结点的査找值为x 的结点， 第 2 页，共 38 页 ，则编号 求各顶点的入度 双亲 无值为x 的结点，插入之 査询成功，值域为x 的结点的count 增 1 3． 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。 【答案】算法如下: //la，lb 分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列 //本算法将两链表合并成一个按元素值递减次序排列的单链表 //pa, pb 分别是链表la 和lb 的工作指针 //la作为结果链表的头指针，先将结果链表初始化为空 //当两链表均不为空时 //将pa 的后继结点暂存于 r //将pa 结点链于结果表中，同时逆置 //恢复pa 为当前待比较结点 //将pb 的后继结点暂存于 r //将pb 结点链于结果表中，同时逆置 //恢复pb 为当前待比较结点 //避免再对pa 写下面的While 语句 //算法Union 结束 第 3 页，共 38 页 4． 对于任意的无符号的十进制整数m ，写出将其转换为十六进制整数的算法(转换仅要求能够输出正确的十六进制的整数即可) 。 【答案】算法如下: //本算法将无符号十进制整数m 转换为十六进制整数 本算法的递归描述如下: //本算法将无符号十进制整数m 转换为十六进制整数 5． 设记录 的关键字为 。 ，树结点 的败者树，要求除 指向败者记录， 和1 为全胜以外，只 记录下标。写一算法产生对应上述用O(1)辅助空间。 【答案】算法如下: 选得最小关键字记录后，沿从叶结点R[s]到根结点T[0]的路径调整败者树 是 指示新的胜者 第 4 页，共 38 页 的双亲结点
相关内容
相关标签