2017年北京科技大学546计算机综合之数据结构考研复试核心题库
● 摘要
一、应用题
1． 设输入序列为2, 3, 4, 5, 6, 利用一个栈能得到序列2, 5, 3, 4, 6吗? 栈可以用单链表实现吗？
【答案】不能得到序列2, 5, 3, 4, 6。因为根据输入序列，2进栈之后，2出找，3, 4, 5依次进栈。5出栈，此时栈中剩下3, 4。因为4在栈顶，所以4应该比3先出栈，不能得到提供的序列。栈可以用单链表实现，这就是链栈。由于栈只在栈顶操作，所以链栈通常不设头结点。
2． 两个字符串s1和s2的长度分别为m 和n 。求这两个字符串最大共同子串算法的时间复杂度
，并简要说明理由。 为T （m ，n ）。估算最优的T （m , n ）
【答案】最优的T （m ，n ）是D （n ）。串S2是串S1的子串，且在S1中的位置是1。开始求出最大公共子串的长度恰是串S2的长度。一般情况下，
3． 请阅读下列算法，回答问题。
问题一：这是什么类型的排序算法，该排序算法稳定吗？
问题二：设置|的作用是什么? 若将WHILE--DO 语句中判断条件改为
算法将会有什么变化，是否还能正确工作？
【答案】问题一：此为直接插入排序算法，该算法稳定。
问题二：
采用的作用是监视哨，免去每次检测文件是否到尾，提高了排序效率。 描述算法后，算法变为不稳定排序，但能正常工作。 该
4． 某网络中的路由器运行0SPF 路由协议，如表是路由器R1维护的主要链路状态信息（LSI ），如图是根据表及R1的接口名构造出来的网络拓扑。
表R1所维护的LSI
图R1构造的网络拓扑
请回答下列问题。
（1）本题中的网络可抽象为数据结构中的哪种逻辑结构？
（2）针对表中的内容，设计合理的链式存储结构，以保存表中的链路状态信息（LSI ）。要求给出链式存储结构的数据类型定义，并画出对应表的链式存储结构示意图（示意图中可仅以ID 标识节点）。
（3）按照迪杰斯特拉（Dijikstra ）算法的策略，依次给出R1到达图中子网192.1.x.x 的最短路径及费用。
【答案】（1）图
（2）使用图的邻接表存储结构进行存储，数据类型定义如下：
该弧指向路由器的位置，0为没有
该弧指向的网络的网络前缀，空为没有
路由的基础IP ，当adjvex 不为0才有效
指向下一条弧的指针
连接的权值
表结点
第一个结点地址
头节点
链式存储结构示意图如下图所示：
（3
）目标网络
记为
记为
记为使用dijkstra 算法找最短路径步骤如下表所示：
相关内容
相关标签