2021年浙江省中国计量大学数据结构与操作系统考研模拟试题
一、单项选择题：1～40小题，每小题2分，共80分。在每小题给出的四个选项中，请选出一项最符合题目要求的。
1. 函数fun的时间复杂度为（ ）。
float fun(float x, int n)
{ float result = 1.0f;
for( i=0; i < n*n/2; ++i)
{
result *= x;
}
return result
}
A．O( (n2/2)! ) B．0(2log2n) C．0(n2/2) D．O(n2)
2. 下列排序算法中，需要额外辅助存储空间最多的是（ ）。
A．归并排序 B．快速排序 C．堆排序 D．直接插入排序
3. 以下数据结构中，不属于线性表的是（ ）。
A. 队列 B. 栈 C. 图 D. 循环链表
4. 下面关于栈的描述中，错误的是（ ）。
A．先进后出
B．两头都可以插入和删除
C．可以用数组来实现
D．可以用链表来实现
5. 关于环形（循环）队列，错误的是（ ）。
A．先进先出 B．用数组来实现
C．可以提高空间的利用率 D．用循环链表来实现
6. 层数为8的二叉树其结点个数最多有（ ）。
A．1023 B．511 C．255 D．127
7. 有100个结点的无向图要确保是一个连通图至少应有（ ）。
A．101条边 B．99条边 C．50条边 D．6条边
8. 关于图的描述，错误的是（ ）。
A．有向图的邻接矩阵一定是对称矩阵
B. 完全图中的边一定比连通图中的边多
C．深度优先搜索的结果可能不唯一
D．广度优先搜索的结果可能不唯一
9. 下列排序算法中，哪个是不稳定的（不稳定指的是：关键字相同的两个数据，排序后它们的先后位置会变化）（ ）。
A．希尔排序 B．简单选择排序 C．插入排序 D．冒泡排序
10. 二叉查树中有1023个结点，查其中一个数据时，描述正确的是（ ）。
A．至少要比较10次
B．最多比较10次
C．不可能超过10次
D．如果是平衡二叉查树，可能要比较1023次
11. 图1所示这棵树的中序遍历结果是（ ）。
A．ABCDEF B. DBACEF C. DBAECF D. BACCEF
图1.树
12. 往栈中输入序列{1,2,……，n}后再逐个输出，则输出序列的最后一个元素是( )。
A．不确定 B．n-1 C．n D．1
13. 假设N个数据已经放在不同的数据结构，然后进行查，下列描述错误的是：（ ）。
A．如果采用合适的散列表，其查速度最快
B．用二叉查树来查比用折半查要快
C．链表上的查要比二叉查树 快
D．平衡二叉查树上的查要比普通二叉查树 快
14. 若数据序列5, 96, 12, 64, 78, 23, 49是采用下列方法之一得到的第一趟排序后的结果，则该排序算法是（ ）。
A．冒泡排序 B．直接插入排序 C．快速排序 D．归并排序
15. 对数据 8，1，4，9，6，3，5，2，7，0进行排序时，第一趟的排序结果如下：0,1,4,2,5,3,6,9,7,8；
则采用的排序算法是（ ）。
A．快速排序 B．直接插入排序 C．冒泡排序 D．归并排序
16. 把数据1，2，3，4，5，6，7通过插入操作构造一棵二叉查树，下列描述错误的是（ ）。
A．按照3,4,1,2,6,7,5的插入顺序构造的二叉查树，树高为3
B．按照4,2,1,3,6,5,7的插入顺序构造的二叉查树的查效率最高
C．按照3,4,1,2,6,7,5的插入顺序构造的二叉查树是平衡二叉树
D．按照4,2,1,3,6,5,7的插入顺序构造的二叉查树是平衡二叉树
17.已知一个数据序列中有1024个数据，且其已经有序排列，若采用最快的查算法和必要的存储结构，在该序列中要查一个数据元素，则平均比较次数最少要多少次（ ）。
A．512 B. 256 C. 10 D. 1
18.一棵满二叉树共有11层（树根为第一层），则叶子节点个数为（ ）。
A. 0 B. 2048 C. 1024 D. 512
19.若要检查文件中的括号是否匹配，采用的数据结构应该是（ ）。
A． 图 B. 二叉树 C. 栈 D. 栈
20.快递员每天要送很多包裹给客户，为了提高效率，缩短总路程长度，请问该选用什么样的
数据结构来设计路线（ ）。
A．线性表 B. 图 C.队列 D. 二叉树
21．操作系统是一种( )
A．实用软件 B.系统软件 C. 应用软件 D. 工具软件
22. 设置当前工作目录的主要目的是（ ）。
A. 节省外存空间 B. 节省内存空间
C. 加快文件的检索速度 D. 加快文件的读/写速度
23.进程从阻塞状态进入就绪状态的原因可能是( )
A. 被选中占有处理机 B. 等待某一事件发生
C. 等待的事件已发生 D. 时间片用完
24.在可变式分区分配方案中，某一作业完成后，系统收回其主存空间，并与相邻空闲区合并，为此需修改空闲区表，造成空闲区数无变化的情况是( )
A.无上邻空闲区，也无下邻空闲区
B.有上邻空闲区，也有下邻空闲区
C.有下邻空闲区但无上邻空闲区;或有上邻空闲区但无下邻空闲区
D. 以上三种都可以
25.假设某一机器的内存有2G,硬盘为300G,请问使用虚拟内存技术后，其虚拟内容的容量为（ ）
A. 2G B. 4G C. 300G D.302G
26.在基本分段存储管理中，逻辑地址转换为物联地址时，若段号超过段表长度，则会引起( )。
A. 输入输出中断 B. 缺段中断 C. 越界中断 D. 缺页中断
27.某个进程运行在( )中。
A. 内存 B. 硬盘
C. SWAPING交换区 D. 硬盘中的某个子目录
28.成组链接法可用于( )
A.磁盘空闲空间的管理 B.磁盘的驱动调度
C.文件目录的查 D.页式虚拟存贮管理中的页面调度
29.下列算法中用于磁盘调度的是( )
A. SSTF优先级高者优先算法 B. FIFO先进先出算法
C. 时间片轮转法RR D. 最短寻道时间优先
30.通道是一种（ ）。
A. I/O端口 B. 数据通道
C. I/O专用处理机 D. 软件工具
31.假设磁头当前位于100道，正在向磁道序号增加的方向移动。现有一个磁 道访问请求序列为28，55，12，68，110，180，170，195，采用先来先服务调度（FCFS）算法得到的磁道访问序列是（ ）。
A. 110,170,180,195,68,55,28,12 B. 28,55,12,68,110,180,170,195
数据结构与算法考研真题C. 110,170,180,195,12,28,55,68 D. 12,28,55,68,110,170,180,195
32.在通过索引分配技术时，若某一文件的索引块如下图所示：
11 4 2 1 -1 -1 |
请问，该索引文件大小总共占有磁盘空间（ ）块？
A. 4 B. 7 C. 5 D. 6
33. 在基本分页存储管理中，若采用最佳页面置换算法OPT，则当进程分配到的物理块数增加时，缺页中断的次数会（ ）
A. 一定减少 B.一定不会增加 C. 无影响 D.可能增加也可能减少
34. 采用（ ）不会产生内部碎片。
A. 分页式存储管理 B. 分段式存储管理
C. 固定分区式存储管理 D. 虚拟分页存储管理
35. 某基于动态分区存储管理的计算机，其主存容量为55MB(初始为空闲)，采用最佳适配（Best Fit）算法，分配和释放的顺序为：分配15MB,分配30MB,释放15MB,分配8MB,分配6MB,此时主存中最大空闲分区的大小是( )。
A. 10MB B. 9MB C. 7MB D. 15MB
36. 某计算机系统中有K台打印机，由4个进程竞争使用，每个进程最多需要3台打印机。该系统不可能发生死锁的K的最小值是（ ）。
A. 6 B. 10 C. 8 D. 9
37. 采用SPOOLing技术的目的是（ ）。
A. 提高独占设备的利用率 B. 提高主机效率
C. 减轻用户编程负担 D. 提高程序的运行速度
38．考虑以下页表结构：
页号 块号
0 | 2 |
1 | 5 |
2 | 1 |
3 | 9 |
假设页的大小为512字节, 即页内地址长度为 9 位，请把以下以十六进制表示的逻辑地址0x967，通过页表转换为物理地址（也用十六进制表示）是 （ ）。
A. 0x3417 B. 地址转换错误 C. 0x367 D. 0x567
39. 以下不是设备分配算法的是（ ）
A. 先来先服务 B. 短作业优先
C. 优先级高的优先 D. 以上几种都不是
40. 对两个并发进程，其互斥信号量为mutex；初值为1，若mutex＝0，则表明（ ）。
A．没有进程进入临界区
B．有一个进程进入临界区但没有进程处于阻塞状态
C．一个进程进入临界区而另一个进程正处于等待进入临界区状态
D．有两个进程进入临界区
二、综合应用题：41～45小题，共70分。
41.带有头节点的单链表，其节点结构为
data | next |
带有头结点的单链表如下图所示
请设计一个算法对两个有序单链表L1，L2进行求交的操作，得到新的链表L3，L3仍然保持有序的状态，要求：
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论