2018年太原理工大学软件学院834数据结构和操作系统之数据结构考研基础五套测试题
● 摘要
一、单项选择题
1． 在用邻接表表示图时，拓扑排序算法时间复杂度为（ ）。
A.0(n)
B.0(n+e) C. D.
【答案】B
【解析】由于输出每个顶点的同时还要删除以它为起点的边，故拓扑排序的时间复杂度为0(n+e)
2． 某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为字节，页表项大小为2字节，逻辑地址结构为:
逻辑地址空间大小为
（ ）.
A.64
B.128
C.256
D.512
【答案】B
【解析】地址空间分为逻辑地址空间和物理地址空间. 页的大小为
采用二级页表，
一页可存放
3．
协议对0111110001111110组帧后对应的比特串为（ ）
A.011111000011111010
B.011111000111110101111110
C.01111100011111010
D.011111000111111001111101
【答案】A
【解析】HDLC 协议对比特串进行组帧时, HDLC 数据帧以位模式
个“0”。所以答案为A 。
第 2 页，共 74 页 页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是字节，页表项大小为2B ，字节，
故最少需要个页表项，本题中逻辑地址空间大小为个页面来保存页表项，故本题答案为B. 标识每一个帧的开始和结束, 因此在帧数据中凡是出现了5个连续的位“1”的时候, 就会在输出的位流中填充一
4． 有向带权图如下图图所示, 若采用迪杰斯特拉(Dijkstta)算法求从源点a 到其他各顶点的最短路径, 则得到的第一条最短路径的目标顶点是b , 第二条最短路径的目标顶点是c , 后续得到的其佘各最短路径的目标顶点依次是（ ）。
图 有向带权图
A.d , e , f
B.e , d , f
C.f , d , e
D.f , e , d
【答案】C 。
【解析】本题主要考查Dijkstta 算法的思想和解题步骤。题目执行算法过程中各步的状态如下表所示。执行Dijkstta 算法过程中各步的状态表, 故后续目标顶点依次为f , d , e 。
5． n 个结点的线索二叉树上含有的线索数为（ ）。
A.2n
B.n ﹣1
C.n ＋1
D.n
【答案】C
【解析】线索二叉树是利用二叉树的空链域加上线索，n 个结点的二叉树有n ＋1个空链域。
6． 下列排序算法中元素的移动次数和关键字的初始排列次序无关的是（ ）。
A. 直接插入排序
B. 起泡排序
C. 基数排序
D. 快速排序
第 3 页，共 74 页
【答案】C
【解析】C 项, 基数排序是采用分配和收集实现的, 不需要进行关键字的比较。ABD 三项都依赖关键字的比较, 不同的初始排列次序下元素移动的次数有很大变化, 最好情况元素正序, 则不用移动, 最坏情况元素反序, 则需要移动次(n为元素个数) 。
7． 4个圆盘的Hanoi 塔，总的移动次数为（ ）。
A.7 B.
C.15
D.16
【答案】C
【解析】Hanoi 问题总移动次数为:2M 次。
8． 循环两列放在一维数组中, end1指向队头元素, end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作, 队列中最多能容纳M-1个元素。初始时为空, 下列判断队空和队满的条件中, 正确的是（ ）
A. 队空:endl==end2; 队满:endl==(end2+l)modM
B. 队空Gendl==end2; 队满:Gend2==(endl+1)mod(M-1)
C. 队空Gend2==(endl+1)modM; 队满:Gendl==(end2+l)modM
D. 队空:
【答案】A
【解析】在循环队列中, 在少用一个元素空间的前提下, 可约定入队前, 测试尾指针在循环意义下加1后是否等于头指针, 若相等, 则队满。而队空的条件还是首尾指针是否相等。
9． 用海明码对长度为8位的数据进行检/纠错时, 若能纠正一位错, 则校验位数至少为（ ）
A.2
B.3
C.4
D.5
【答案】C
【解析】设校验位的位数为k , 数据位的位数为n , 根据海明码编码k 和n 应满足下述关系。
。
n=8, 当k=4时, , 符合要求, 校验位至少是4位, 故答案为C 。
10．下列命中组合情况中, 一次访存过程中不可能发生的是（ ）。
A.TLB 未命中, Cache 未命中, Page 未命中
B.TLB 未命中, Cache 命中, Page 命中
C.TLB 命中, Cache 未命中, Page 命中
D.TLB 命中, Cache 命中, Page 未命中
第 4 页，共 74 页 队满:
相关内容
相关标签