2017年武汉轻工大学数学与计算机学院810数据结构考研冲刺密押题
● 摘要
一、填空题
1． 顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。
【答案】视哨。
2． 线性表
【答案】（n －1）/2
【解析】删除第一个元素需要移动n －i 次，以此类推，删除最后一个元素需要移动0次。平 均次数为
3． 在基于关键字比较且时间为O （nl 〇g2n ）的排序中，若要求排序是稳定的，则可选用_____，则可选用_____排序。 排序；若要求就地排序（及辅助空间为0（1））
【答案】归并；堆
4． 外排序的基本操作过程是_____和_____。
；归并 【答案】生成有序归并段（顺串）
5． 分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。
【答案】起泡；快速
，【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为〇（n ） 而快速排序算法需要比较的次数达到最大，时间复杂度为
6． 已知二维数组中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时
，
【答案】1196
第 2 页，共 55 页
【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监
用数组表示，假定删除表中任一元素的概率相同，则删除一个元素
平均需要移动元素的个数是_____。
的地址是：_____。
【解析】设元素的行标为i ，列标为j 。则它的存储位置为：
7． 在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_____、_____、_____、_____。
【答案】
8． 二叉树的前序序列和中序序列相同的条件是_____。
【答案】空树或任何结点至多只有右子树的二叉树
【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。
9． —棵左子树为空的二叉树在前序线索化后，其中的空链域的个数为 _____。
【答案】2
【解析】只有根结点的做指针为空和最右边的叶结点的右指针为空。
10．文件可按其记录的类型不同而分成两类，即_____和_____文件。
【答案】操作系统文件；数据库
11．在单链表中设置头结点的作用是_____。
【答案】方便运算
12．已知链队列的头尾指针分别是f 和r , 则将值x 入队的操作序列是_____。
【答案】
【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。
二、选择题
13．在OSI 参考模型中，直接为会话层提供服务的是（ ）
A. 应用层 B. 表示层 C. 传输层 D. 网络层 【答案】C
【解析】OSI 参考模型中，下层直接为上层提供服务，而会话层的下层为传输层。
14．使用浏览器访问某大学Web 网站主页时，不可能使用的协议是（ ）
A.PPP B.ARP C.UDP D.SMTP
第 3 页，共 55 页
【答案】D
【解析】SMTP 是简单邮件传输协议，访问主页时并不涉及邮件相关协议。
15．在系统内存中设置磁盘缓冲区的主要目的是（ ）。
A. 减少磁盘I/O次数 B. 减少平均寻道时间 C. 提高磁盘数据可靠性 D. 实现设备无关性 【答案】A
【解析】访问磁盘的开销远远大于访问内存的开销。磁盘缓冲区便是利用主存中的存储空间，来暂存从磁盘中读出（或写入）的信息，频繁使用的一部分磁盘数据和信息，暂时存放在磁盘缓存中，可减少访问磁盘的次数。
16．下列关于进程和线程的叙述中，正确的是（ ）。
A. 不管系统是否支持线程，进程都是资源分配的基本单位 B. 线程是资源分配的基本单位，进程是调度的基本单位 C. 系统级线程和用户级线程的切换都需要内核的支持 D. 同一进程中的各个线程拥有各自不同的地址空间 【答案】A 。
“线程是资源分配的基本单位，【解析】利用排除法来确定正确答案：进程是调度的基本单位”这句话说反了，明显错误。“系统级线程和用户级线程的切换都需要内核的支持”也不正确，因为用户级线程的切换由用户编写的RuntimeSystem 执行的，内核并不感知。“同一进程中的各个线程拥有各自不同的地址空间”明显错误，引入线程的目的就是为了同一进程的所有线程能共享进程的地址空间，故“不管系统是否支持线程，进程都是资源分配的基本单位”是正确的。
17．某CPU 主频为1.03GHz , 采用4级指令流水线，每个段的执行需要1个时钟周期。假定CPU
执行了100条指令，在其执行过程中没有发生任何流水线阻塞，此时流水线的吞吐率为（ ）
A. B. C. D. 【答案】C
【解析】采用4级流水线执行100条指令，在执行过程中共用
条指令/秒，故答案为C 。
第 4 页，共 55 页
条指令/秒
条指令/秒
条指令/秒
条指令/秒
个时钟周期。
CPU 的主频是1.03GHz , 也就是说每秒钟有1.03G 个时钟周期。流水线的吞吐率
为
相关内容
相关标签