2018年北京市培养单位高能物理研究所408计算机学科专业基础综合之数据结构考研强化五套模拟题
● 摘要
一、算法设计题
1． 令G=(V, E) 为一个有向无环图，编写一个给图G 中每一个顶点赋以一个整数序号的算法，并满足以下条件:若从顶点i 至顶点j 有一条弧，则应使i 【答案】算法如下: 对以邻接表存储的DAG 图g 重新编号, 使若有 记录结点的逆序序号 2． 假设K1，... ，Kn 是n 个关键词，试解答： (1)试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K1，K2，…，Kn 时，用算法建立一棵以llink —rlink 链接表示的二叉查找树。 (2)设计一个算法，打印出该二叉查找树的嵌套括号表示结构。例如，K1=B，K2=A，K3=D，K4=C，K5=E，则用二叉查找树的插入算法建立如图所示的二叉查找树。 ，则编号 求各顶点的入度 图 该二叉查找树的嵌套括号表示结构为:B(A，D(C，E)) 。 【答案】(1)算法如下: 在二叉排序树bst 上査找值为K 的结点，返回其双亲结点指针 f 以存储在数组R 中的n 个关键字，建立一棵初始为空的二叉排序树 不再插入相同值结点 . 申请结点空间 根结点 左子女 右子女 结束算法 (2)算法如下: 以嵌套括号表示结构打印二叉排序树 打印根结点值 左子女和右子女中至少有一个不空 输出左栝号 输出左子树的嵌套括号表示 若右子树不空，输出逗号 输出右子树的嵌套括号表示 输出右括号 3． 给出以十字链表作存储结构，建立图的算法，输入(i, j , V) , 其中i , j 为顶点号，v 为权值。 【答案】算法如下: 建立有向图的十字链表存储结构 假定权值为整型 建立顶点向量 当输入i 、j 、v 之一为0时，结 束算法运行 申请结点 弧结点中权值域 算法结束 4． 假设在二叉链表的结点中增设两个域:parent 域指示其双亲结点:flag 域(取值为历的递推形式的算法。 【答案】算法如下: 在增加双亲指针 和标志域 的二叉树中，不用栈后序遍历二叉树 ) 区分在遍 历过程中到达该结点时应继续向左、向右或访问该结点。试以此存储结构编写不用栈进行后序遍 向左 向右 访问根结点 找被访问结点的双亲 结束 5． 若x 和y 是两个采用顺序结构存储的串，编写一个比较两个串是否相等的函数。 【答案】算法如下: //本算法判断两个顺序存储的串x 和y 是否相等，相等返回1，否则返回0
相关内容
相关标签