2016年武汉科技大学计算机科学与技术学院数据结构(C语言版)复试笔试最后押题五套卷
● 摘要
一、选择题
1． 用数组r 存储静态链表，结点的next 域指向后继，工作指针j 指向链中结点，使j 沿链移动的操作为（ ）。
答:A
【解析】因为是用数组存储，这里所说的工作指针j 相当于数组的下标，结点是存储一个值域和next 域，next 域就是存放下一个结点的下表，所以只要将next 域中的值赋给j 就可以实现j 沿链移动。
2． 在页式存储管理系统中，采用某些页面置换算法，会出现Belady 异常现象，即进程的缺页次数会随着分配给该进程的页框个数的增加而增加。下列算法中，可能出现Belady 异常现象的是（ ）。
I . LRU 算法
A. 仅 II
B .仅 I II
C. 仅I III
D. 仅 II III
答:A
【解析】Belady 现象只有FIFO 算法才会出现
3． 下列排序算法中，其中（ ）是稳定的。
A. 堆排序，起泡排序
B. 快速排序，堆排序
C. 直接选择排序，归并排序
D. 归并排序，起泡排序
答:D
4． 下列不是设计一个“好”的算法应考虑达到的目标是（ ）。
A. 可行的
B. 健壮的
C. 无二义性的
D. 可读性好的
II. FIFO 算法 III. OPT 算法
答:A
【解析】设计一个“好”的算法应考虑以下目标：正确性；可读性；健壮性；效率和低存储量需求。可行性是算法的五个基本特征之一，不是一个好的算法该达到的目标。
5． 已知一个长度为16的顺序表L , 其元素按关键字有序排列。若采用折半查找法查找一个L 中不存在的元素，则关键字的比较次数最多是（ ）。
A.4
B.5
C.6
D.7
答:B
【解析】折半查找法在查找不成功时和给定值进行比较的关键字个数最多为（l 〇g2n ） +1，在本题中，n=16, 故比较次数最多为5。
6． 已知三叉树T 中6个叶结点的权分别是2，3, 4, 5，6，7, T的带权（外部）路径长度最小是（ ）
A.27
B.46
C.54
D.56
答:B
【解析】利用三叉树的6个叶子结点的权构建最小带权生成树，
最小的带权路径长度为
7． 下列措施中，能加快虚实地址转换的是1增大快表（TLB ） 2让页表常驻内存3增大交换区（ ）。
A. 仅1
B. 仅2
C. 仅 1，2
D. 仅 2, 3
答:C
【解析】加大快表能增加快表的命中率，即减少了访问内存的次数；让页表常驻内存能够使cpu 不用访问内存找页表，从也加快了虚实地址转换。而增大交换区只是对内存的一种扩充作用，对虚实地址转换并无影响
8．
协议对
A.011111000011111010
B.011111000111110101111110
C.01111100011111010
D.011111000111111001111101
答:A 组帧后对应的比特串为（ ）
HDLC 协议对比特串进行组帧时，HDLC 数据帧以位模式0111 1110标识每一个帧的【解析】
开始和结束，因此在帧数据中凡是出现了 5个连续的位“1”的时候，就会在输出的位流中填充一个“0”。所以答案为A 。
9． 基于比较方法的n 个数据的内部排序。 最坏情况下的时间复杂度能达到的最好下界是（ ）。
A.0（nlogn ）
B.O （logn ）
C.O （n ） D.
答:A
【解析】在内部排序中，最坏情况下的时间复杂度为0（nlogn ）。
已知待排序的n 个元素可分为个组，每个组包含k 个元素，且任一组内的各元素均分别大干前一
10．元素a , b , c , d , e 依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d 开头的序列个数是（ ）。
A.3
B.4
C.5
D.6
答:B
【解析】d 首先出栈后的状态如下图所示。
此时可有以下4种操作：
（1）e 进找后出栈，出梭序列为decba 。
（2）c 出找，e 进找后出栈，出找序列为dceba 。
（3）cb 出找，e 进找后出栈，出找序列为dcbea 。
（4）cba 出找，e 进找后出找，出找序列为dcbae 。
二、填空题
11．从平均时间性能而言，_____排序最佳。
答:快速
【解析】快速算法的平均时间复杂度为nlogn 。
相关内容
相关标签