2018年广西师范大学计算机科学与信息工程学院826数据结构(含C程序设计)之数据结构考研强化五套模拟题
● 摘要
一、单项选择题
1． 已知序列25, 13, 10, 12, 9是大根堆, 在序列尾部插入新元素18, 将其再调整为大根堆, 调整过程中元素之间进行的比较次数是（ ）。
A.1
B.2
C.4
D.5
【答案】B
【解析】对堆插入或删除一个元素, 有可能不满足堆的性质, 堆被破坏, 需要调整为新堆。
(1)为原堆,
(2)为插入18后,
(3)比较10与18, 交换后,
(4)比较25与18, 不交换, 即为调整后的新的大根堆。
因此调整过程中元素之间进行的比较次数为2。
2． 若一个用户进程通过read 系统调用读取一个磁盘文件中的数据, 则下列关于此过程的叙述中, 正确的是（ ）。
Ⅰ. 若该文件的数据不在内存, 则该进程进入睡眠等待状态;
Ⅱ. 请求read 系统调用会导致CPU 从用户态切换到核心态;
Ⅲ.read 系统调用的参数应包含文件的名称
A. 仅Ⅰ、Ⅱ
B. 仅Ⅰ、Ⅲ
C. 仅Ⅱ、Ⅲ
D. Ⅰ、Ⅱ和Ⅲ
【答案】A
【解析】对于Ⅰ, 当所读文件的数据不再内存时, 产生中断(缺页中断、缺段中断) , 原进程进入睡眠等待状态(阻塞状态) , 直到所需数据从外村调入内存后, 将该进程唤醒, 使其变为就绪状态。对于Ⅱ, read 系统调用cpu 将从用户态切换到核心态, 从而获取操作系统提供的服务。对于Ⅲ, 在操作
Open 系统调用的参数需要包含文件的系统中, 要读一个文件首先要open 系统调用将该文件打开。
路径名与文件名, 而read 系统调用只需使用open 返回的文件描述符, 并不使用文件名作为参数。Read 系统调用要求用户提供三个输入参数:
①文件描述符; ②buf 缓冲区首址; ③传送的字节数n 。
read 系统调用的功能是试图从fd 所指示的文件中读入n 个字节的数据, 并将它们送至由指针buf 所指示的缓冲区中。
3． 设桟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
4． 下列选项中, 属于多级页表优点的是（ ）
A. 加快地址变换速度
B. 减少缺页中断次数
C. 减少页表项所占字节数
D. 减少页表所占的连续内存空间
【答案】D
【解析】多级页表避免了把所有的页表一直保存在内存中
5． 下列选项中的英文缩写均为总线标准的是（ ）。
A.PCI 、CRT 、USB 、EISA
B.ISA 、CPI 、VESA 、EISA
C.ISA 、SCSI 、RAM 、MIPS
D.ISA 、EISA 、PCI 、PCI-Express
【答案】D
【解析】选项A 中的CRT 和USB 、选项B 中的CPI 、选项C 中的RAM 和MIPS 均不是总线
标准的英文缩写, 只有选项D 中的英文缩写均为总线标准。
6． 已知待排序的n 个元素可分为n/k个组，每个组包含k 个元素，且任一组内的各元素均分别大干前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为（ ）。 A.
B.
C.
D.
【答案】B
【解析】因组与组之间己有序，故将n/k个组分别排序即可，基于比较的排序方法每组的时
，全部时间下界为间下界为
0 。
7． 若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（ ）.
A.. 起泡排序
B. 插入排序
C. 选择排序
D. 二路归并排序
【答案】B
【解析】经过两趟排序后，A 项起泡排序的结果是两个最小或最大的元素放到了序列的最终位置；B 项插入排序的结果是前三个数有序即可；C 项选择排序结果是两个最小的元素在最前面按顺序排好；D 项二路归并排序的结果是长度为4的子序列有序，即前4个数排好序，接下来的4个数排好序. 显然题目中的元素序列只能是插入排序第二趟排序后的结果，因此，B 项正确.
8． 在用邻接表表示图时，拓扑排序算法时间复杂度为（ ）。
A.0(n)
B.0(n+e) C. D.
【答案】B
【解析】由于输出每个顶点的同时还要删除以它为起点的边，故拓扑排序的时间复杂度为0(n+e)
9． 假定变量i 、f 和d 的数据类型分为int 、float 和double(int用补码表示, float 和double 分别用IEEE754单精度和双精度浮点数格式表示) , 已知
器中执行下列关系表达式, 则结果为“真”的是（ ）。
(Ⅰ)
(Ⅱ)
。若在32位机
相关内容
相关标签