（11）设根结点的层次为0，则高度为k的二叉树的最大结点数为
A．2k
B．2k-1
C）2k+1
D．2k+1-1
（12）对线性表进行二分法查找，其前提条件是
A．线性表以顺序方式存储，并已按关键码值排好序
B．线性表以顺序方式存储，并已按关键码值的查找频率排好序
C．线性表以链接方式存储，并已按关键码值排好序
D．线性表以链接方式存储，并已按关键码值的查找频率排好序
（13）在包含1000个元素的线性表中实现如下各运算，哪一个所需的执行时间最长？
A．线性表按顺序方式存储，在线性表的第10个结点后面插入一个新结点
B．线性表按链接方式存储，在线性表的第10个结点后面插入一个新结点
C．线性表按顺序方式存储，删除线性表的第990个结点
D．线性表按链接方式存储，删除指针P所指向的结点
（14）设有字符序列（Q，H，C，Y，P，A，M，S，R，D，F，X），问新序列（F，H，C，D，P，A，M，Q，R，S，Y，X）是下列哪一个排序算法一趟扫描的结果？
A．起泡排序
B．初始步长为4的希尔排序
C．二路归并排序
D．以第一元素为分界元素的快速排序
（15）下面关于B树运算的叙述中，正确的是
A．若插入过程中根结点发生分裂，则B树的高度加1
B．每当进行插入运算，就往B树的最下面一层增加一个新结点
C．若要删除的关键码出现在根结点中，则不能真正删除，只能做标记
D．删除可能引起B树结点个数减少，但不会造成B树高度减小
（16）下列关于中断的叙述中，错误的是
A．时间片到时属于时钟中断
B．目态下执行特权指令将产生程序性中断
C．缺页中断属于自愿性中断
D．打印机完成打印将产生输入输出中断
下面第（17）-（18）题基于如下描述：
有5个进程P1，P2，P3，P4，P5，它们几乎同时进入就绪队列，它们的优先数和需要的处理器时间如下表所示。假设优先数小的优先级高，忽略进行调度等所花费的时间。
| 进程 | 处理器时间 | 优先数 |
| P1 P2 P3 P4 P5 |
10 1 2 1 5 |
3 |
（17）采用"不可剥夺优先数"调度算法，进程执行的次序是
A．P2、P1、P5、P3、P4
B．P2、P3、P1、P5、P4
C．P4、P1、P3、P5、P2
D．P4、P3、P1、P5、P2
（18）采用"不可剥夺优先数"调度算法，进程在就绪队列中的平均等待时间为
A．6
B．7
C．8
D．9
（19）下列各项中哪一个不是虚拟页式存储管理中缺页中断处理所做的工作？
A．通过文件系统将所需页面从外存调入内存
B．调用内存分配程序
C．修改页表
D．调度被中断程序继续执行
（20）下列哪一个是引入工作集模型的前提因素？
A．系统效率下降
B．页面淘汰算法选择不合理
C．程序的局部性原理
D．分配给进程的物理页面数太少
责任编辑：小草
