2017年郑州大学联合培养单位安阳师范学院944计算机学科专业基础综合之数据结构考研题库
● 摘要
一、选择题
1． 在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个。
A.4 B.5 C.6 D.7
【答案】C
【解析】设度为0的结点数为x 则度为3的树总结点数n=度为0的结点数+度为1的结点数+度为2的结点数+度为3的结点数
从每个结点所指向的结点数的和的角度来计算度
为3
的树总结点数两种方法所计算出来的n 相等，所以
2． 在系统总线的数据线上，不可能传输的是（ ）。
A. 指令 B. 操作数
C. 握手（应答）信号 D. 中断类型号型号 【答案】C
【解析】握手（应答）信号属于通信联络控制信号应该在通信总线上传输，不可能在数据总线上传输。而指令、操作数和中断类型码都可以在数据线上传输。
3． 若一个栈以向量
存储，初始栈顶指针top 为n+1，则下面X 入栈的正确操作是（ ）。
【答案】C
【解析】题中初始栈顶指针top 为n+1, 而栈顶指针又位于最大下标以上，此时入栈应进行先减一操作。
4． 已知串
A.0123 B.1123 C.1231 D.1211
【答案】A
【解析】KMP 算法的next 数组建立的原则
第 2 页，共 66 页
其Next 数组值为（ ）。
5． 为支持
A. 连续结构 B. 链式结构 C. 直接索引结构 D. 多级索引结钩 【答案】A
【解析】为了实现快速随机播放，要保证最短的查询时间，即不能选取链表和索引结构，因此连续结构最优。
6． —个多道批处理系统中仅有P1和P2两个作业，P2比P1晚5ms 到达。它们的计算和P1:计算60ms ，作顺序如下：
计算
计算
计算
虑调度和切换时间，则完成两个作业需要的时间最少是（ ）。
A.240ms B.260ms C.340ms D.360ms
【答案】B 。
【解析】考查处理系统的性能计算，由于P2比PI 晚5ms 到达，PI 先占用CPU ，根据PI 和P2的执行过程，作业运行的甘特图如下所示，故答案为B 。
中视频文件的快速随机播放，播放性能最好的文件数据块组织方式是（ ）
操
若不考
7． 操作系统的
A. 用户级B. 用户级C. 用户级D. 用户级【答案】A 。
子系统通常由四个层次组成，每一层明确定义了与邻近层次的接口。其合理软件、设备无关软件、设备驱动程序、中断处理程序 软件、设备无关软件、中断处理程序、设备驱动程序 软件、设备驱动程序、设备无关软件、中断处理程序 软件、中断处理程序、设备无关软件、设备驱动程序
的层次组织排列顺序是（ ）。
【解析】对于一次设备的调用，操作系统为用户准备了系统调用的接口，当用户使用设备时，
第 3 页，共 66 页
首先在用户程序中发起一次系统调用，操作系统的设备无关层软件接到该调用请求后调用处理程序进行处理，根据调用格式和形参，再转到相应的设备驱动程序去处理；大部分设备在运行时是需要时间的，所以设备驱动程序会以中断方式驱动设备，即设置好控制寄存器参数和中断向量等参数后阻塞自己；当设备准备好或所需数据到达后设备硬件发出中断，设备驱动程序唤醒，将数据按上述调用顺序逆向回传到用户程序中，或继续驱动设备执行下一条指令。 因此，
软件从
上到下分为四个层次：用户层、与设备无关的软件层、设备驱动程序以及中断处理程序。
8． 若用一个大小为6的数组来实现循环队列，且当前rear 和front 的值分别为0和3, 当从队列中删除一个元素，再加入两个元素后，rear ，front 的值分别为多少？（ ）
A.1和5 B.2和4 C.4和2 D.5和1 【答案】B
【解析】入队操作的主要步骤
：个后
，
9． 程序段
加入一个后，
再加入一
删除一个后
，
出队操作的主要步骤
：
其中n 为正整数，则最后一行的语句最坏情况下的时间复杂度是（ ）。
【答案】D
【解析】这个是冒泡排序，最坏的情况下需要进行次交换，即时间复杂度是
10．在文件的索引节点中存放直接索引指针10个，一级二级索引指针各1个，磁盘块大小为1KB 。每个索引指针占4个字节。若某个文件的索引节点已在内存中，到把该文件的偏移量（按字节编址）为1234和307400 处所在的磁盘块读入内存。需访问的磁盘块个数分别是（ ）。
A.1, 2 B.1, 3 C.2, 3 D.2, 4
【答案】B
【解析】文件的索引结点的直接索引指针有10个，因此直接索引的偏移量范围是级索引的偏移量范围是
二级索引访问的偏移量范围是
一
偏移量1234
可以通过直接索引得到在磁盘块的地址，因此需要一次访问，307400需要通过二级索引查找其在
第 4 页，共 66 页
相关内容
相关标签