2018年天津科技大学842自命题计算机学科专业基础综合之数据结构考研强化五套模拟题
● 摘要
一、单项选择题
1． 和顺序栈相比，链栈有一个比较明显的优势是（ ）。
A. 通常不会出现栈满的情况
B. 通常不会出现栈空的情况
C. 插入操作更容易实现
D. 删除操作更容易实现
【答案】A
2． 设无向图的顶点个数为m 则该图最多有（ ）条边。
A.n-1 B. C.
D.0E.n2
【答案】B
【解析】在数据结构中仅讨论简单图，在计算无向图的最多边时，不考虑顶点与顶点的边。因此边数最多时，构成的是无向完全图。此时的边数为
3． 程序段
与对换；
其中n 为正整数，则最后一行的语句最坏情况下的时间复杂度是（ ）。
A.D(n)
B.O(nlogn)
C.O(n3)
D.O(n2)
【答案】D
【解析】这个是冒泡排序，最坏的情况下需要进行l ＋2＋... ＋n ﹣l 次交换，即时间复杂度是0(n2) 。
4． 先序序列为a , b , c , d 的不同二叉树的个数是（ ）。
A.13
B.14
C.15
第 2 页，共 47 页 。
【答案】B
【解析】二叉树的先序遍历定义为:若二叉树为空, 则空操作; 否则, 访问根节点, 然后先序遍历左子树, 最后先序遍历右子树。本题中, 结点a 为二叉树的根节点, 左右子树的先序遍历可能存在下面四种情况:
①左子树为空, bcd 为右子树; ②b 为左子树, cd 为右子树; ③bc 为左子树, d 为右子树; ④bcd 为左子树, 右子树为空。
然后将左右子树继续分解, 如第①种情况的右子树先序遍历(bcd)可能有:
A. 左子树为空, 右子树为cd ;
b. 左子树为c , 右子树为d ;
c. 左子树为cd , 右子树为空。
按照这种方法继续分解左右子树, 直到不能再分解为止, 可得第①和④种情况各包含5种不同情况, 第②和③种情况各包含2种情况, 因此总共有14种不同的二叉树。
5． 单级中断系统中, 中断服务程序内的执行顺序是（ ）。
Ⅰ保护现场; Ⅱ开中断; Ⅲ关中断; Ⅳ保存断点; Ⅴ中断事件处理; Ⅵ恢复现场; Ⅶ中断返回 A. B. C. D.
【答案】A
【解析】程序中断有单级中断和多级中断之分, 单级中断在CPU 执行中断服务程序的过程中不能被打断, 即不允许中断嵌套。保存断点与关中断的任务是由硬件(中断隐指令) 完成的, 所以在单级中断系统中, 中断服务程序内应完成的任务有:
①保存现场; ②中断事件处理; ③恢复现场; ④开中断; ⑤中断返回。
6． 设系统缓冲区和用户工作均采单, 从外读入1个数据块到系统缓冲区的时间为100, 从系统缓冲区读入1个数据块到用户工作区的时间为5, 对用户工作区中的1个数据块行分析的时间为90(如下图所示) 。进程从外设读入并分析2个数据块的最短时间是（ ）
图
第 3 页，共 47 页
B.295
C.300
D.390
【答案】C
【解析】数据块1从外设到用户工作区的总时间为105, 在这段时间中数据块2没有进行操作。在数据块1进行分析处理时, 数据块2从外设到用户工作区的总时间为105, 这段时间是并行的。再加上数据块2进行处理的时间90, 总共是300, 故答案为C 。
7． 从堆中删除一个元素的时间复杂度为（ ）。
A.O(1) B.
C.O(n) D.
【答案】B
【解析】堆中删除一个元素，需要重新调整堆，其时间复杂度为
8． 某磁盘的转速为10, 000转/分, 平均寻道时间是6ms , 磁盘传输速率是
为, 读取一个4KB 的扇区所需平均时间约为（ ）
A.9ms B.
C.12ms D.
【答案】B
【解析】磁盘转速是10000转/分钟, 平均转一转的时间是6ms , 因此平均查询扇区的时间是3ms , 平均寻道时间是6ms , 读取4KB
扇区信息的时间为
。
9． 对给定的关键字序列110, 119, 007, 911, 114, 120, 122进行基数排序, 则第2趟分配收集后得到的关键字序列是（ ）
A.007.110.119.114.911.120.122
B.007, 110, 119, 114, 911, 122, 120
C.007, 110, 911, 114, 119, 120, 122
D.110, 120, 911, 122, 114, 007, 119
【答案】C
【解析】基数排序的第1趟排序是按照个位数字来排序的, 第2趟排序是按然十位数字的大小进行排序的, 故答案是C 选项。
10．b ，(c，d) ，(e，(f，g))) ， 广义表A ＝(a，则式子Head(Tail(Head(Tail(Tail(A)))))的值为（ ）。
A.(g)
B.(d)
C.c
D.d
第 4 页，共 47 页 。 , 磁盘控制器延迟
, 信息延迟的时间为0.2ms ,
总时间为