2018年河北大学电子信息工程学院929数据结构(电)考研仿真模拟五套题
● 摘要
一、单选题
1． 下列关于无向连通图特性的叙述中，正确的是（ ）.
(1)所有的顶点的度之和为偶数 (2)边数大于顶点个数减1 (3)至少有一个顶点的度为1 A. 只有(1) B. 只有(2) C. (1)和(2) D.(1)和(3) 【答案】A
【解析】在图中，
顶点的度
之和与边的数目满足关系式：
(n为图的
总结点数，e 为总边数) ，因此， (1)项正确. 对于(2)、(3)项中的特性不是一般无向连通图的特性，可以轻松地举出反例.“至少有一个顶点的度为1”的反例如下图1所示，“边数大于顶点个数减1”的反例如下图2所示
.
图
1
图2
2． 链表不具有的特点是（ ）。
A. 插入、删除不需要移动元素 B. 可随机访问任一元素 C. 不必事先估计存储空间 D. 所需空间与线性长度成正比 【答案】B
【解析】B 项是顺序表的特点。只要确定了顺序线性表的起始位置，线性表中的任一数据元素都可随机存取。
3． 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A ，并已知A 的左孩子的平衡因子为0, 右孩子的平衡因子为1，则应作（ ）型调整以使其平衡
A.LL B.LR C.RL D.RR
【答案】C
【解析】A 的平衡因子此时为-1，要使插入结点不平衡，必须插在右孩子的左子树上，A 平衡因子变成了-2. 则需要进行两次旋转(先右旋后左旋) 。
4． 采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中, 正确的是（ ）。
A. 递归次数与初始数据的排列次序无关
B. 每次划分后, 先处理较长的分区可以减少递归次数 C. 每次划分后, 先处理较短的分区可以减少递归次数 D. 递归次数与每次划分后得到的分区的处理顺序无关 【答案】D
【解析】快速排序是递归的, 递归过程可用一棵二叉树给出, 递归调用层次数与二叉树的深度一致。例如:待排序列{48, 62, 35, 77, 55, 14, 35, 98) , 采用快速排序方法, 其对应递归调用过程的二叉树如下图所示。
图
在最坏情况下, 若初始序列按关键码有序或基本有序时, 快速排序反而蜕化为冒泡排序。即其对应递归调用过程的二叉树是一棵单支树。因此快速排序的递归次数与初始数据的排列次序有关。但快速排序的递归次数与每次划分后得到的分区处理顺序无关, 即先处理较长的分区或先处理较短的分区都不影响递归次数。
5． 现有容量为10GB 的磁盘分区, 磁盘空间以簇(duster)为单位进行分配, 簇的大小为4KB , 若采用位图法管理该分区的空闲空间, 即用一位(bit)标识一个簇是否被分配, 则存放该位图所需簇的个数为（ ）
A.80 B.320 C.80K D.320K 【答案】A
【解析】磁盘的簇的个数为:
个
而一个簇的位示图能管理的簇的个数为:
所以需要簇的个数为
个
6． 设桟S 和队列Q 的初始状态为空，元素el ，e2，e3，e4，e5和e6依次通过栈S ，一个元素出栈后即进队列Q ，若6个元素出队的序列是e2，e4，e3，e6，e5，el ，则栈S 的容量至少应该是（ ）。
A.6 B.4 C.3 D.2
【答案】C
7． 循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。
A.rear ＝rear ＋l
B.rear ＝(rear＋1)mod(m﹣1) C.rear ＝(rear＋1)modm D.rear ＝(rear＋1)mod(m＋1) 【答案】D
8． 连续存储设计时，存储单元的地址（ ）。
A. 一定连续 B. 一定不连续 C. 不一定连续
D. 部分连续，部分不连续 【答案】A
【解析】连续存储是指数据的物理存储相连，即存储单元的地址是连续的。
9． 下列关于中断方式和DMA 方式比较的叙述中, 错误的是（ ）
A. 中断
方式请求的是方式请求的是CPU 处理时间, DMA 方式请求的是总线使用权
B. 中断响应发生在一条指令执行结束后, 中断响应发生在一条指令执行结束后, DMA 响应发生在一个总线事务完成后
C. 中断送由硬件完成
D. 中断设备
方式下数据传送通过软件完成, 方式下数据传送通过软件完成, DMA 方式下数据传方式适用于所有外部设备, 方式适用于所有外部设备, DMA 方式仅适用于快速外部
相关内容
相关标签