2018年北京物资学院计算机软件与理论911计算机学科专业基础综合之数据结构考研核心题库
● 摘要
一、填空题
1． 在二叉树中，指针p 所指结点为叶结点的条件是_____。
【答案】
【解析】叶子节点的左右孩子都不存在。
2． 应用prim 算法求解连通网络的最小生成树问题。
(1)针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。(始顶点号，终顶点号，权值
)
(2)下面是Prim 算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。
的值在
图的顶点数，应由用户定义
用二维数组作为邻接矩阵表示
生成树的边结点
边的起点与终点
边上的权值
最小生成树定义
从顶点rt 出发构造图G 的最小生成树T , rt 成为树的根结点
初始化最小生成树
T
第 2 页，共 63 页
中
依次求MST 的候选边
遍历当前候选边集合
选具有最小权值的候选边
图不连通，出错处理
修改候选边集合
【答案】(1)
(2)
【解析】Prim 算法的执行类似于寻找图的最短路径的Dijkstra 算法。假设是N 上最小生成树边的集合。算法从属于
的边为止。
3． 二叉树的前序序列和中序序列相同的条件是_____。
【答案】空树或任何结点至多只有右子树的二叉树
【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。
4． 数据结构是研讨数据的_____和_____以及它们之间的相互关系，并对与这种结构定义相应的_____, 设计出相应的_____。
【答案】逻辑结构；物理结构；操作(运算) ；算法
5． 在循环队列中，队列长度为n ，存储位置从0到，n ﹣1编号，以rear 指示实际的队尾元素，现要在此队列中插入一个新元素，新元素的位置是_____。
【答案】
6． 如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_____。
【答案】69
【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。
，
属于E 中找一条代价最小的边
加入集合
是连通图
，
，v ，
直到
开始，重复执行下述操作:在所有u 属于
，同时将并入
第 3 页，共 63 页
7． 在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_____; 对于有向图来说等于该顶点的_____。
【答案】度；出度
8． 有五个数据依次入找:1，2，3，4，5。在各种出栈的序列中，以3，4先出栈的序列有_____。(3在4之前出栈)
【答案】3个
【解析】以3，4先出栈的序列有34521、34215、34251共3个。
9． 遍历图的过程实质上是_____，广度优先遍历图的时间复杂度____；深度优先遍历图的时间复杂度_____，两者不同之处在于_____，反映在数据结构上的差别是_____。
【答案】查找顶点的邻接点的过程；0(n+e)；0(n+e)；访问顶点的顺序不同；队列和栈 【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。
10．假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素在B 中的存储位置k ＝_____。(注:矩阵元素下标从1开始)
【答案】93
【解析】对于上三角矩阵，k ＝(i﹣l)(2n﹣i ＋2)/2＋(j﹣i) ＋l 。将i ＝j ＝9，n ＝15代入得93。
二、单项选择题
11．数据链路层采用选择重传协议(SR)传输数据, 发送方已发送了0H3号数据帧, 现已收到1号帧的确认, 而0、2号帧依次超时, 则此时需要重传的帧数是（ ）。
A.1 B.2 C.3 D.4
【答案】B
【解析】在选择重传协议中, 接收方逐个地确认正确接收的分组, 不管接收到的分组是否有序, 只要正确接收就发送选择ACK 分组进行确认。因此选择重传不支持累积确认, 要特别注意其与GBN 协议的区别。本题收到1号帧的确认, 说明1号帧正确接收, 0和2号帧依次超时, 因此必须重传, 然而3号帧尚未超时, 是否正确接收未知, 故不用重传, 因此必须重传0和2号帧, 答案是B 。
12．假设某计算机的存储系统由Cache 和主存组成. 某程序执行过程中访存1000次，其中访问Cache 缺失(未命中)50次，则Cache 的命中率是（ ）.
A.5% B. C.50% D.95% 【答案】D
第 4 页，共 63 页
相关内容
相关标签