2017年北京物资学院物联网工程与技术911计算机学科专业基础综合之数据结构考研导师圈点必考题汇编
● 摘要
一、填空题
1． 数据结构中评价算法的两个重要指标是_____。
【答案】算法的时间复杂度和空间复杂度
2． 当广义表中的每个元素都是原子时，广义表便成了_____。
【答案】线性表
【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。
3． 如果按关键码值递増的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。 【答案】
【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺 序查找效率一样为
4． 遍历图的过程实质上是_____，广度优先遍历图的时间复杂度_____; 深度优先遍历图的时间复杂度_____, 两者不同之处在于_____, 反映在数据结构上的差别是_____。
【答案】查找顶点的邻接点的过程；0（n+e）; 0（n+e）; 访问顶点的顺序不同；队列和栈
【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。
5． 已知一循环队列的存储空间为其中队头和队尾指针分别为front 和rear , 则此循环队列判满的条件是（ ） 【答案】
6． 执行顺序查找时，存储方式可以是_____，折半查找时，要求线性表_____，分块查找时要求线性表_____，而哈希表的查找，要求线性表的存储方式是_____。
【答案】顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储
7． 在循环队列中，队列长度为n ，存储位置从0到，
【答案】
编号，以rear 指示实际的队尾元素，现要在此队列中插入一个新元素，新元素的位置是（ ）。
8． 按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_____的排序方法。
【答案】稳定
9． 建立索引文件的目的是_____。
【答案】提高查找速度
10．若用n 表示图中顶点数目，则有_____条边的无向图成为完全图。
【答案】n （n-l ）/2
【解析】无向完全图中任意一个顶点都和其他n-1个顶点都有一条边，即为n （n-l ）。又因为每条边重复出现两次，所有无向完全图的边数为n （n-l ）/2。
二、选择题
11．用有向无环图描述表达式（A+B）*（，至少需要顶点的数目为（ ）（A+B）/A）。
A.5 B.6 C.8 D.9
【答案】A
6条边 【解析】一共5个结点
12．—棵二叉树高度为h ，所有结点的度或为0或为2，则这棵二叉树最少有（ ）个结点。
A.2h
B.
C.
D.
【答案】B
【解析】此树满足哈夫曼树，除根节点外每层有两个节点。
13．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。
A. 单链表
B. 仅有头指针的单循环链表
C. 双链表
D. 仅有尾指针的单循环链表
【答案】D
【解析】仅有尾指针的单循环链表，在最后插入元素和删除第一个元素都会用到这个尾指针。
14．在一株高度为2的5阶B 树中，所含关键字的个数最少是（ ）
A.5
B.7
C.8
D.14
【答案】A
【解析】根据B 树的定义可知，跟结点最少含有个关键字，高度为2的阶B 树最少有（5-1）+1=5个关键字，其中根节点含有个关键字，第2层结点含有1关键字。
15．用哈希（散列）方法处理冲突（碰撞）时可能出现堆积（聚集）现象，下列选项中，会受堆积现象直接影响的是（ ）
A. 存储效率
B. 数列函数
C. 装填（装载）因子
D. 平均查找长度
【答案】D
【解析】哈希方法冲突会使在查找冲突的关键字时，还要根据冲突处理办法多次比较关键字，则直接影响了平均查找长度。
16．下列给出的指令系统特点中，有利于实现指令流水线的是（ ）。
I. 指令格式规整且长度一致
II. 指令和数据按边界对齐存放
III. 只有Load / Store指令才能对操作数进行存储访问
A.
仅
B.
仅
C.
仅
D.
【答案】D
【解析】特点I 和III 都是RISC 机的特征，而特点II 则有利于指令和数据的存放，所以以上三个特点都有利于实现指令流水线。
17．算法的计算量的大小称为计算的（ ）。
A. 效率
B. 复杂性
C. 现实性
D. 难度
【答案】B
【解析】算法复杂度通常分为时间复杂度和空间复杂度，算法的计算量的大小可以用时间复杂度衡量，即可以称为计算的复杂度。
18．下列选项中，用于设备和控制器（
A.PCI
B.USB ’接口）之间互连的接口标准是（ ）
相关内容
相关标签