2017年信阳师范学院计算机学科专业基础综合之数据结构考研复试核心题库
● 摘要
一、应用题
1． 对一个有t 个非零元素的矩阵，用的数组来表示，其中第0行的三个元素分别为m ，n ，t ，从第一行开始到最后一行，每行表示一个非零元素；第一列为矩阵元素的行号，第二列为其列号，第三列为其值。对这样的表示法，如果需要经常进行该操作-确定任意一个元素
在B 中的位置并修改其值，应如何设计算法可以使时间得到改善？
【答案】题中矩阵非零元素用三元组表存储，查找某非零元素时，按常规要从第一个元素开始查找，属于顺序查找，
时间复杂度为若使查找时间得到改善，可以建立索引，将各行行号及各行第一个非零元素在数组B 中的位置（下标）放入一向量C 中。若查找非零元素，可先在数组C 中用折半查找到该非零元素的行号，并取出该行第一个非零元素在B 中的位置，再到B 中
顺序（或折半）查找该元素，这时时间复杂度为
2． 写出下列排序算法的基本思想，并写出对序列（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
3．
已知一个整数序列
其中
则称x 为A 的主元素。
例如若存在
且则称5为主元素；
又如
则A 中没有主元素。假设A 中的n 个元素保存在一个一维数组中，请设计一个
尽可能高效的算法，找出A 的主元素。若存在主元素，则输出该元素；否则输出-1。要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C 或
【答案】
（1）算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素Num 。然后重新计数，确认Num 是否是主元素。
算法可分为以下两步：
①选取候选的主元素：依次扫描所给数组中的每个整数，将第一个遇到的整数Num 保存到c 中，记录Num 的出现次数为1; 若遇到的下一个整数仍等于Num ，则计数加1否则计数减1; 当计数减到0时，将遇到的下一个整数保存到c 中，计数重新记为1，开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素。
②判断c 中元素是否是真正的主元素，再次扫描该数组，统计c 中元素出现的次数，若大于则为主元素；否则，序列中不存在主元素。
（2）算法实现如下：
用来保存候选主元素，count 用来计数
设置A [0]为候选主元素
查找候选主元素
为A 中的候选主元素计数
处理不是候选主元素的情况
更换候选主元素
统计候选主元素的实际出现次数
确认候选主元素
或Java 语言描述算法，关键之处给出注释。 （3）说明你所设计算法的时间复杂度和空间复杂度。
不存在主元素
，空间复杂度为O （1）（3）时间复杂度为O （n ）。
4． 某网络中的路由器运行0SPF 路由协议，如表是路由器R1维护的主要链路状态信息（LSI ），如图是根据表及R1的接口名构造出来的网络拓扑。
表R1所维护的
LSI
图R1构造的网络拓扑
请回答下列问题。
（1）本题中的网络可抽象为数据结构中的哪种逻辑结构？
（2）针对表中的内容，设计合理的链式存储结构，以保存表中的链路状态信息（LSI ）。要求给出链式存储结构的数据类型定义，并画出对应表的链式存储结构示意图（示意图中可仅以ID 标识节点）。
（3）按照迪杰斯特拉（Dijikstra ）算法的策略，依次给出R1到达图中子网192.1.x.x 的最短路径及费用。
【答案】（1）图
相关内容
相关标签