2018年河北大学数学与信息科学学院907数据结构考研仿真模拟五套题
● 摘要
一、单项选择题
1． 下列程常段的时间复杂度是（ ）
A.O()
B.O(n) C.O() D.O()
【答案】C
【解析】外部循环的退出条件是k>n, 而对于k , 每次循环都执行
内部循环的退出条件是j>n, 对于j , 每次循环都执行, 所以循环次数为; , 所以每次循环次数为n 次。所以此程序
) , 即选C 。 段的时间复杂度为O(
2． 某计算机系统中有8台打印机，由K 个进程竞争使用，每个进程最多需要3台打印机. 该系统可能会发生死锁的K 最小值是（ ）.
A.2
B.3
C.4
D.5
【答案】C
【解析】死锁的抽屉原理一般描述是：将5个苹果放进4个抽屉，那么，必然有1个抽屉中至少有2个苹果. 计算机系统的资源分配充分体现了这一原理. 考察进程运行的特点，只要有一个进程能够运行，则运行结束后必然会归还资源，其余的进程也就会得到满足从而可以执行(这里考虑的资源主要是可重用的资源，不可重用的资源会消失，就不可用上述方法分析). 所以最少需要4个进程竞争使用，每个进程占用2台打印机，此时会产生死锁.
3． 二叉树在线索化后，仍不能有效求解的问题是（ ）。
A. 前序线索二叉树中求前序后继
B. 中序线索二叉树中求中序后继
C. 中序线索二叉树中求中序前驱
D. 后序线索二叉树中求后序后继
【答案】D
【解析】后序线索二叉树求后序后继要分3种情况，比较复杂，不是仅仅线索化后就能求解
的，算法上还要要分情况讨论。
4． 下列文件物理结构中，适合随机访问且易于文件扩展的是（ ）.
A. 连续结构
B. 索引结构
C. 链式结构且磁盘块定长
D. 链式结构且磁盘块变长
【答案】B
【解析】连续结构的优点是结构简单，缺点是不易于文件扩展，不易随机访问. 链式结构的优点是文件易于扩展，缺点是不易随机访问. 索引结构的优点是具有链式结构的优点并克服了它的缺点，可随机存取，易于文件扩展.
5． 若下图为10BaseT 网卡接收到的信号波形, 则该比特串是（ ）
A.00110110
B.10101101
C.01010010
D.11000101
【答案】A
【解析】以太网采用曼彻斯特编码, 其将一个码元分成两个相等的间隔, 前一个间隔为高电平而后一个间隔为低电平表示1, 反之则表示0。故根据波形图, 可得答案为A 。
6． n 个结点的完全有向图含有边的数目（ ）。
A.n*n
B.n(n+1)
C.n/2
D.n*(n－1)
【答案】D
【解析】在有向图中，如果任意两个顶点之间都存在边，则称为有向完全图。顶点个数为n 的无向图，最多有条边。如是有向图，需要在无向图的最多边的基础上乘以2，则为n(n－1) 。
7． 下列调整中, 不可能导致饥饿现象的是（ ）
A. 时间片转移
B. 静态优先及调度
C. 非抢占式作业优先
D. 抢占式短作业优先
【答案】A
【解析】时间片转移方法能在一个周期内使每个进程都得到一个时间片的CPU 使用时间, 不会产生饥饿的现象, 其余三个都会产生饥饿。
8． 下列线索二叉树中(用虚线表示线索) , 符合后序线索树定义的是（ ）。
【答案】D
【解析】线索二叉树利用二叉链表的空链域来存放结点的前驱和后继信息, 解题思路较简单。题中所给二叉树的后序序列为dbca 。结点d 无前驱和左子树, 左链域空, 无右子树, 右链域指向其后继结点b ; 结点b 无左子树, 左链域指向其前驱结点d ; 结点c 无左子树, 左链域指向其前驱结点b , 无右子树, 右链域指向其后继结点a 。所以正确选项为D 。
9． 某文件占10个磁盘块, 现要把该文件磁盘块逐个读入主存缓冲区, 并送用户区进行分析。假设一个缓冲区与一个磁盘块大小相同,
把一个磁盘块读人缓冲区的时间为
送到用户区的时间是, CPU
对一块数据进行分析的时间为
下, 读人并分析完该文件的时间分别是（ ）。 A. B. C. D.
【答案】B
【解析】这是一个简单的缓冲区的问题。由于缓冲区的访问是互斥的, 所以对单一缓冲区, 从磁盘写入和读出到用户区的操作必须串行执行, 也就是要保证互斥操作。而CPU 对数据的分析与从用户区读数据也是需要互斥操作, 但是CPU 分析与从磁盘写入缓冲区的操作可以并行。从本题看, 由于分析所用的时间小于从磁盘写入缓冲区的时间, 因此, CPU 会空闲。
单缓冲区的总时间=(磁盘写入缓冲区时间+缓冲区读出时间)
间=(100+50)X10+50=1550ns。
当采用双缓冲区时, 每块缓冲区的操作也必须满足互斥操作, 但是, 对两块缓冲区的操作却可
, 将缓冲区的数据传
。在单缓冲区和双缓冲区结构处理最后一块数据的时