2017年内蒙古科技大学信息工程学院843数据结构考研题库
● 摘要
一、选择题
1． 图中有关路径的定义正确的是（ ）。
A. 由顶点和相邻顶点构成的边所形成的序列
B. 由不同顶点所形成的序列
C. 由不同边所形成的序列
D. 上述定义都不是
【答案】A
【解析】顶点Vp 到顶点Vq 之间的一条路径是指顶点序列
的数目称为路径的长度。
2． 下列关于AOE 网的叙述中，不正确的是（ ）。
A. 关键活动不按期完成就会影响整个工程的完成时间
B. 任何一个关键活动提前完成，那么整个工程将会提前完成
C. 所有的关键活动提前完成，那么整个工程将会提前完成
D. 某些关键活动若提前完成，那么整个工程将会提前完成
【答案】B
【解析】关键路径是指从有向图的源点到汇点的最长路径。某些关键活动提前完成，那么整个工程将会提前完成，但不是任何一个关键活动提前完成，就能保证整个工程将会提前完成。
3． 引入二叉线索树的目的是（ ）。
A. 加快查找结点的前驱或后继的速度
B. 为了能在二叉树中方便地进行插入与删除
C. 为了能方便地找到双亲
D. 使二叉树的遍历结果唯一
【答案】A
【解析】二叉线索树有指向前驱和后继的指针，因此加快了查找前驱和后继结点的速度。
4． 由3个结点可以构造出多少种不同的有向树？（ ）
A.2
B.3
C.4
D.5
【答案】A
【解析】满足以下条件的有向图称为有向树：①有且仅有一个结点的入度为0; ②除树根外结
第 2 页，共 72 页 ，路径上边
点的入度为1; ③从树根到任一结点有一有向通路。
5． 在下面的程序段中，对x 的赋值语句的时间复杂度为（ ）
【答案】C
【解析】两个循环嵌套，那么语句x :=x＋l :
则被执行了次。
6． 用邻接表存储图所用的空间大小（ ）。
A. 与图的顶点数和边数都有关 B. 只与图的边数有关
C. 只与图的顶点数有关 D. 与边数的平方有关
【答案】A
【解析】邻接表就是对图G 中的每个顶点Vi 建立一个单链表，第i 个单链表中的结点表示依附于顶点V i 的边，这个单链表就称为顶点Vi 的边表。因此邻接表既存储图的所有顶点，也存储顶点之间的边的信息。
7． 若无向图G= （V , E）中含7个顶点，则保证图G 在任何情况下都是连通的，则需要的边数最少是（ ）。
A.6
B.15
C.16
D.21
【答案】C
【解析】要保证无向图G 在任何情况下都是连通的，即任意变动图G 中的边，G 始终保持连通。首先需要图G 的任意6
个结点构成完全连通子图然后再添加一条边将第7个结点与需条边，连接起来，共需16条边。本题非常容易错误地选择选项A ，主要原因是对“保证图G 在任何情况下都是连通的”的理解，分析选项A ，在图G 中，具有7个顶点6条边并不能保证其一定是连通图，即有n-1 条边的图不一定是连通图。分析选项D ，图G 有7个顶点21条边，那么图G —定是无向完全图，无向完全图能 保证其在任何情况下都是连通的，但是这不符合题目中所需边数最少的要求。
8． 采用指令Cache 与数据Cache 分离的主要目的是（ ）
A. 减低Cache 的缺失损失
B. 提高Cache 的命中率
C. 减低CPU 平均访问时间
D. 减少指令流水线资源冲突
【答案】D
第 3 页，共 72 页
【解析】指令流水线不会断流，预取过来的都是指令
9． 对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（ ）。
A.95, 22, 91, 24, 94, 71
B.92, 20, 91, 34, 88, 35
C.21, 89, 77, 29, 36, 38
D.12, 25, 71, 68, 33, 34
【答案】A
【解析】各选项对应的查找过程如下图所示，从中看到选项B 、C 、D 对应的查找树都是二叉排序树，只有选项A 对应的查找树不是一棵二叉排序树，因为在以91为根的左子树中出现了比91大的结点94。
10．某设备中断请求的相应和处理时间为100m ，每400ns 发出一次中断请求，中断相应所容许的最长延迟时间为50ns , 贝U 在该设备持续工作过程中CPU 用于该设备的
百分比至少是（ ） A. B. C. D.
【答案】B
【解析】每400m 响应一次中断并且用100m 进行处理，所以该设备的时间占用CPU 时间
百分比为中断响应容许的延迟时间对此没有影响，属于干扰条件。
11．本地用户通过键盘登录系统时，首先获得的键盘输入信息的程序是（ ）。
A. 命令解释程序
B. 中断处理程序
C. 系统调用服务程序
D. 用户登录程序
【答案】B
【解析】外部设备在与计算机连接时有多种方式，中断技术就是一种常用方式。其工作原理
第 4 页，共 72 页 时间占整个CPU 时间
相关内容
相关标签