《2017年北京师范大学政府管理学院986软件基础考研强化模拟题.doc》由会员分享，可在线阅读，更多相关《2017年北京师范大学政府管理学院986软件基础考研强化模拟题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年北京师范大学政府管理学院986软件基础考研强化模拟题一、应用题1 带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径，假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：该最短路径初始时仅包含初始顶点，令当前顶点为初始顶点；选择离最近且尚未在最短路径中的顶点V ，加入到最短路径中，修改当前顶点请证明之；否则请举例说明。【答案】题目中方法不一定能（或不能）求得最短路径。举例说明： 图（a ） 图（b ）图（a ）中，假设初始顶点1到目标顶点4之间有一条边，权值x=2。显然图（a ）中这顶点1和顶点4之间的最短路径长度为2
2、。若按照题目中给定的方法找到的路径为初始顶点1经过中间结点2、3到目标顶点4, 即初始顶点显然， 一目标顶点4, 所经过的边的权值分别为 重复步骤，直到是目标顶点时为止。请问上述方法能否求得最短路径? 若该方法可行，因此按照题目中给定的方法所求得的路径并不是这两个顶点之间的最短路径。图（b ）中，假设初始顶点为1、目标顶点为4, 欲求从顶点1到顶点4之间的最短路径。显然，按照题目中给定的方法无法求出顶点1到顶点4的路径，而事实上顶点1到顶点4的最短路径为1到4。2 假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，“loading ”和“being
3、”的存储映像如图所示。 图 存储映像7K 意图设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为第 2 页，共 33 页请设计一个时间上尽可能高效的算法，找出由strl 和str2所指的两个链表共同后缀的起始位置（如图中字符i 所在结点的位置p ）。要求：（1）给出算法的基本设计思想。 （2）根据设计思想，采用C 或【答案】（1）算法的基本设计思想：分别求出strl 和str2所指的两个链表的长度m 和n ;将两个链表以表尾对齐：令指针p 、q 分别指向strl 和str2的头结点，若表中的第个结点；若则使q 指向链表中的第表尾的长度相等。反复将指针p 和q 同步向后移动，
4、并判断它们是否指向同一结点。若p 和q 指向同一结点，则该点即为所 求的共同后缀的起始位置。（2）用C 语言算法描述如下： 两个指针同步向后移动 （3）参考答案的时间复杂度为：或其中m 、n 分别为两个链表的长度。3 已知一棵二叉树的后序遍历序列为EICBGAHDF , 同时知道该二叉树的中序遍历序列为CEIFGBADH ， 试画出该二叉树。【答案】该二叉树如图所示： 返回共同C 缀的起始点 则使p 指向链个结点，即使指针p 和q 所指的结点到或JA V A 语言描述算法，关键之处给出注释。（3）说明你所设计算法的时间复杂度。第 3 页，共 33 页 图 4 写出下列排序算法的基本思想，并写出
5、对序列（23，12，35，47，16，25，36，19，21，16）进行排序时每一趟的结果。 【答案】此排序为双向起泡排序：从前向后一趟排序下来得到一个最大值，若其中发生交换，则再从后向前一趟排序，得到一个最小值。第一趟：12，23，35，16，25，36， 19，21，16， 47 第二趟：12，16，23，35，16，25，36， 19，21，47 第三趟：12，16，23，16，25，35， 19，21，36， 47 第四趟：12， 16， 16，23， 19， 25， 35， 21， 36，47 第五趟：12，16，16，19，23，25，21，35， 36， 47 第六趟：12，16，16，19，21， 23，25，35， 36， 47 第七趟：12，16，16，19，21，23，25，35， 36， 47 5 设依以下次序给出关键字：34，16，19，21，5，49，24，62，3，17，45，8，构造3阶树。要求从空树开始，每插入一个关键字，画出一棵树。【答案】如图所示： 第 4 页，共 33 页 一、应用题考研试题
