2018年西安电子科技大学通信工程学院833计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、单项选择题
1． 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
A. 顺序表
B. 双链表
C. 带头结点的双循环链表
D. 单循环链表
【答案】A
【解析】线性表采用顺序表，便于进行存取任一指定序号的元素；线性表采用链表，便于进
行插入和删除操作。但该题是在最后进行插入和删除运算，所以利用顺序表存储方式最节省时间。
2． 下列选项中, 属于多级页表优点的是（ ）
A. 加快地址变换速度
B. 减少缺页中断次数
C. 减少页表项所占字节数
D. 减少页表所占的连续内存空间
【答案】D
【解析】多级页表避免了把所有的页表一直保存在内存中
3． 在下列表述中，正确的是（ ）
A. 含有一个或多个空格字符的串称为空格串
B. 对n(n＞0) 个顶点的网，求出权最小的n ﹣1条边便可构成其最小生成树
C. 选择排序算法是不稳定的
D. 平衡二叉树的左右子树的结点数之差的绝对值不超过1
【答案】C
【解析】平衡二叉树的左右子树的深度之差的绝对值不超过1。求最小生成树时，每次挑最小权值边，是要求该边的两点都在不同的连通分量上的。
4． n 个结点的完全有向图含有边的数目（ ）。
A.n*n
B.n(n+1)
C.n/2
D.n*(n－1)
【答案】D
【解析】在有向图中，如果任意两个顶点之间都存在边，则称为有向完全图。顶点个数为n 的无向图，最多有条边。如是有向图，需要在无向图的最多边的基础上乘以2，则为n(n－1) 。
5． 下面关于串的叙述中，不正确的是（ ）。
A. 串是字符的有限序列
B. 空串是由空格构成的串
C. 模式匹配是串的一种重要运算
D. 串既可以采用顺序存储，也可以采用链式存储
【答案】B
【解析】空格构成的串称空格串。空串用表示。零个字符的串称为空串，空格也是一个字符，因此B 项不正确。
6． 程序员利用系统调用打开I/O设备时，通常使用的设备标识是（ ）.
A. 逻辑设备名
B. 物理设备名
C. 主设备号
D. 从设备号
【答案】A
【解析】设备管理具有设备独立性的特点，操作系统以系统调用方式提供给应用程序使用逻辑设备名来请求使用某类设备时，调用中使用的是逻辑设备名，例如LPT1或COM1等. 而操作系统内部管理设备使用的是设备编号.
7． 在物理层接口特性中, 用于描述完成每种功能的事件发生顺序的是（ ）。
A. 机械特性
B. 功能特性
C. 过程特性
D. 电气特性
【答案】C 。
【解析】物理层的主要任务描述为确定与传输媒体接口的一些特性; 机械特性:主要定义物理连接的边界点, 即接插装置; 电气特性:规定传输二进制位时, 线路上信号的电压高低、阻抗匹配、传输速率和距离限制; 功能特性:主要定义各条物理线路的功能; 规程特性:主要定义各条物理线路的工作规程和时序关系。而从题干可以分析描述事件先后顺序的就是规程, 也就是过程特性, 答案
是C 。
8． 以下数据结构中，（ ）是非线性数据结构。
A. 树
B. 字符串
C. 队
D. 栈
【答案】A
【解析】非线性结构是指存在一对多或者多对一的关系。常见的非线性结构有树结构和图结构。
9． 采用开址定址法解决冲突的哈希查找中，发生集聚的原因主要是（ ）。
A. 数据元素过多
B. 负载因子过大
C. 哈希函数选择不当
D. 解决冲突的算法选择不好
【答案】D
【解析】开放定址法就是从发生冲突的那个单元开始，按照一定的次序，从散列表中查找出一个空闲的存储单元，把发生冲突的待插入元素存入到该单元中的一类处理冲突的方法。
10．在OSI 参考模型中，自下而上第一个提供端到端服务的层次是（ ）.
A. 数据链路层
B. 传输层
C. 会话层
D. 应用层
【答案】B
【解析】题目中指明了这一层能够实现端到端传输，也就是端系统到端系统的传输，数据链路层主要负责传输路径上相邻结点间的数据交付，这些结点包括了交换机和路由器等数据通信设备，这些设备不能被称为端系统，因此数据链路层不满足题意. 题目中指明了这一层能够实现传输，会话层只是在两个应用进程之间建立会话而已，应用层只是提供应用进程之间通信的规范，都不涉及传输. 所以本题答案应该是B 项. 在OSI 模型中网络层提供的是主机到主机的通信服务.
二、填空题
11．对n 个记录的表
【答案】n (n－1) /2
【解析】第一次需要n －1次比较，第i 此需要n －i 此比较，所以共需要
进行简单选择排序，所需进行的关键字间的比较次数为_____。 。