2018年兰州大学信息科学与工程学院811计算机专业基础之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 假定用两个一维数组L 【N 】和R 【N 】作为有N 个结点1，2，…，N
的二叉树的存储结构。
和
分别指示结点i 的左儿子和右儿子，
，使
) 表示i 的左(右) 儿子为空。试写一个
存放结点i 的父亲；然后再写一个判别结点u 是否
算法，由L 和R 建立一个一维数组为结点V 的后代的算法。
【答案】算法如下:
和
是含有N 个元素且指示二叉树结点i 左儿子和右儿子的一维数组
T 数组初始化
若结点i 的左子女是则结点L 的
双亲是结点
i
若结点i 的右子女是R , 则R 的
双亲是
i
判断U 是否是V 的后代
2． 对给定关键字序号j(1 中找到关键字从小到大排在第j 位上的记 本算法据此建立结点i 的双亲数组T , 并判断结点U 是否是结点V 的后代 录，写一个算法利用快速排序的划分思想实现上述查找(要求用最少的时间和最少的空间) 。 例如:给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。 【答案】算法如下； 在后半部分继续进行划分 在前半部分继续进行划分 3． —个有向图G=(V，E) 的平方图 ，使得表示。 【答案】算法如下: 4． 在二叉排序树的结构中，有些数据元素值可能是相同的，设计一个算法实现按递增有序打印结点的数据域，要求相同的数据元素仅输出一个，算法还应能报出最后被滤掉而未输出的数据元素个数，对如图所示的二叉排序树，输出为:10，12，13，15，18，21，27，35，42。滤掉3个元素。 且 满足下述性质 : 当且仅当存在某个顶点 22 。写一个算法从给定的G 求出G , G 和G 可分别用两个邻接表 图 【答案】算法如下: 递增序输出二叉排序树中结点的值，滤去重复元素 中序遍历左子树 是当前访问结点的前驱，调用本算法时初值为 null 记重复元素，调用 本算法时初值为 前驱后移 中序遍历右子树 结束 算法 5． 己知L 为链表的头结点地址，表中共有m(m＞3) 个结点，从表中第i 个结点(l＜i ＜m) 起到第m 个结点构成一个循环部分链表，设计将这部分循环链表中所有结点顺序完全倒置的算法。 【答案】算法如下: //L是有m 个结点的链表的头结点的指针。表中从第个结点到第m 个结点构成循环部分链表//本算法将这部分循环链表倒置 //p是工作指针，初始指向第二结点(已假定i ＞ l) //pre是前驱结点指针，最终指向第i ﹣i 个结点 //计数器 //查找第i 个结点 //査找结束，P 指向第i 个结点 //暂存第i 个结点的指针 //p指向第i ＋l 个结点，准备逆置 //上面while 循环结束时，j ＝i ﹣1现从第i ＋1结点开始逆置 //暂存P 的后继结点 + //逆置P 结点 //P恢复为当前待逆置结点 //计数器增 1 //将原第i 个结点的后继指针指向原第m 个结点 二、应用题