2018年北京物资学院计算机应用技术911计算机学科专业基础综合之数据结构考研核心题库
● 摘要
一、填空题
1． 在拓扑分类中，拓扑序列的最后一个顶点必定是_____的顶点。
【答案】出度为0
【解析】如果最后一个顶点的出度不为0, 则必定还有顶点存在，与题目所说的最后一个顶点矛盾，所有最后一个顶点的出度必定为零。
2． 假定查找有序表 中每个元素的概率相等，则进行折半查找时的平均查找长度为_____。
【答案】
表
平均查找次数为
3．
给定一组数据WPL 的值为_____。
【答案】5；96
【解析】每次找两个最小的权值构建哈夫曼树:
4． 从平均时间性能而言，_____排序最佳。
【答案】快速
【解析】快速算法的平均时间复杂度为nlogn 。
5． G 是一个非连通无向图，共有28条边，则该图至少有_____个顶点。
【答案】9
【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。
第 2 页，共 61 页
【解析】折半查找时每个的次数如表所示:
。
以它构造一棵哈夫曼树，则树高为_____，带权路径长度
6． 高度为h 的堆中，最多有_____元素，最少有_____个元素。
【答案】
。当最后一层只有
【解析】当这个堆构成的是满二叉树时，元素的个数最多，元素个数为
一个元素时，此时堆的元素个数最少，元素个数为。
7． 已知一循环队列的存储空间为，其中n ＞m ，队头和队尾指针分别为front 和rear ，则此循环队列判满的条件是_____
【答案】
8． 数据结构中评价算法的两个重要指标是_____。
【答案】算法的时间复杂度和空间复杂度
9． 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长(也称增 量序列) 依次是4， 2， 1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。
【答案】3; (10，7，-9，0，47，23，1，8，98，36)
10．属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
二、单项选择题
11．串是一种特殊的线性表，其特殊性体现在（ ）。
A. 数据元素是一个字符 B. 可以顺序存储
C. 数据元素可以是多个字符 D. 可以链接存储 【答案】A
12．某磁盘的转速为10, 000转/分, 平均寻道时间是6ms , 磁盘传输速率是为
, 读取一个4KB 的扇区所需平均时间约为（ ）
A.9ms B. C.12ms D. 【答案】B
【解析】磁盘转速是10000转/分钟, 平均转一转的时间是6ms , 因此平均查询扇区的时间是3ms , 平均寻道时间是6ms , 读取4KB
扇区信息的时间为
。
第 3 页，共 61 页
, 磁盘控制器延迟
, 信息延迟的时间为0.2ms ,
总时间为
13．下列关于进程和线程的叙述中, 正确的是（ ）。
A. 不管系统是否支持线程, 进程都是资源分配的基本单位 B. 线程是资源分配的基本单位, 进程是调度的基本单位 C. 系统级线程和用户级线程的切换都需要内核的支持 D. 同一进程中的各个线程拥有各自不同的地址空间 【答案】A 。
【解析】利用排除法来确定正确答案:“线程是资源分配的基本单位, 进程是调度的基本单位”这句话说反了, 明显错误。“系统级线程和用户级线程的切换都需要内核的支持”也不正确, 因为用户级线程的切换由用户编写的RimtimeSystem 执行的, 内核并不感知。“同一进程中的各个线程拥有各自不同的地址空间”明显错误, 引入线程的目的就是为了同一进程的所有线程能共享进程的地址空间, 故“不管系统是否支持线程, 进程都是资源分配的基本单位”是正确的。
14．—个栈的入栈序列为1, 2, 3, ……, n , 其出栈序列是, 则可能。若, 则取值的个数是（ ）
A. B. C.
D. 无法确定
【答案】C
【解析】除了3本身以外, 其他的值均可以取到, 因此可能取值的个数为n-1。
15．某自治系统内采用RIP 协议，若该自治系统内的路由器R1收到其邻居路由器R2的距离矢量，距离矢量中包含信息“＜netl ，16＞”，则能得出的结论是（ ）.
A.R2可以经过R1到达netl ，跳数为17 B.R2可以到达netl ，跳数为16 C.R1可以经过R2到达netl ，跳数为17 D.R1不能经过R2到达netl 【答案】D
【解析】RIP 允许一条路径最多只能包含15个路由器，因此距离等于16时相当于不可达，因此RIP 协议里规定16为路由不可达，答案为D.
16．若某单处理器多进程系统中有多个就绪态进程, 则下列关于处理机调度的叙述中, 错误的是（ ）。
A. 在进程结束时能进行处理机调度 B. 创建新进程后能进行处理机调度 C. 在进程处于临界区时不能进行处理机调度
D. 在系统调用完成并返回用户态时能进行处理机调度
第 4 页，共 61 页
相关内容
相关标签