做做这套试卷，看能打多少分，2个小时后发布答案
一、选择题（3＇×12）
1.栈和队列都是（ ）
A) 顺序存储的线性结构 B) 链式存储的非线性结构
C)限制存取点的线性结构 D) 限制存取点的非线性结构
2.若串s=”computer”,其子串个数是( )
A)8 B) 37 C)36 D)9
3、在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍
A) 1/2 B) 2 C) 4 D) 1
4、下列排序中,( )是堆
A)(100,80,55,60,50,40,58,35,20 )
B)(100,80,55,60,50,40,35,58,20)
C)(100,80,55,58,50,40,6035,20)
D)(100,70,55,60,50,40,58,35,20)
5、设树T的度为4,其中度为1、2、3和4的结点个数为4、2、1、1，则T中的叶子数为（ ）
A)5 B) 6 C) 7 D) 8
6、将二叉树的概念推广到三叉树,则一棵有244个结点的完全三叉树的高度为( )
A)4 B)5 C)6 D)7
7、操作系统中采用多道程序设计技术，以提高CPU和外部设备的( ) 。
A．利用率 B．可靠性 C．稳定性 D．兼容性
8、进程和程序的一个本质区别是（ ）。
A ．前者为动态的，后者为静态的； B ．前者存储在内存，后者存储在外存 C 前者在一个文件中，后者在多个文件中；
D 前者分时使用 CPU, 后者独占 CPU
9、有作业控制块JCB连成一串而形成的排队队列称为（ ）。
A．挂起队列 B．阻塞队列
C．就绪队列 D．后备队列
10、在页式存储管理中，块内位移量等于页内位移量是因为（ ）。
A．页和块的大小都是2的整数次方 B．一页是装入内存的连续空间内的
C．页和块的大小相等 D．页和块的大小不等
11、利用SPOOL技术实现虚拟设备的目的是( )。
A．把独享的设备变为可以共享B．便于独享设备的分配
C．便于对独享设备的管理D．便于独享设备与CPU并行工作
12、若信号量S初值为2，当前值为?1，则表示有( )个进程在与S相关的队列上等待。
A．0 B．1C．2D．3
二、填充题（1.5＇×10）
1、感知进程存在的唯一标志是（ ）。
2、数据元素在计算机中有两种基本的存储结构（ ）和（ ）。
3、操作系统的五大管理功能是（ ）、存储器管理、（ ）作业管理和用户接口。
4、深度为k（k>1）的完全二叉树至少有( )个结点.至多有( )个结点.
5、设G为具有n个顶点的无向图，则最多有（ ）条边；若G为具有n个顶点的有向图，则最多有（ ）条边。
6、按资源分配特点，设备类型可分为以下三类：（ ）、共享 、虚拟。
三、判断题（1＇×10）
1.一棵二叉树可以由它的先序序列和后序序列唯一确定。
2.线性表采用链式存储时,结点的存储空间可以是不连续的。
3.进程的互斥和同步总是因相互制约而同时引起
4.计算机中的资源是指计算机的硬件和操作系统两个部分。
5.死锁是指两个或多个进程都处于互等状态而无法继续工作。
6.请求分页存储管理系统，若把页面的大小增加一倍，则缺页中断次数会减少50％。
7.在一个只有单个CPU的计算机中，进程不能并行操作。
8.有n个顶点、n－1条边的图是一棵生成树。
9.用二叉链表存储n个结点的二叉树，结点的2n个指针域中有n－1个空指针。
P.V操作必须成对出现，有一个P操作就一定有一个V操作。
四、简答计算题（33分）
1. 一个虚拟地址结构用24个二进制位表示。其中12个二进制位表示页面尺寸。试问这种虚拟地址空间总共多少页？每页的尺寸是多少？（7分）
2. 已知一棵二叉树的中序遍历结点排列为DGBAECHIF,后序遍历结点排列为GDBEIHFCA.试画出该二叉树。（7分）
3、对关键字序列（9，4，3，8，10，7，6，5，1，2）
（1）画出构造的初始大根堆。（5分）
（2）画出步长为5的一趟希尔排序结果。（4分）
4、设某作业占有7个页面，如果在主存中只允许装入4个工作页面(即工作集为4)，作业运行时，实际访问页面的顺序是1， 2， 3， 6， 4， 7， 3， 2， 1， 4， 7， 5， 6， 5， 2， 1。试用fifo与lru页面调度算法，列出各自的页面淘汰顺序和缺页中断次数，以及最后留驻主存4页的顺序。(假设开始的4个页面已装入主存) （10分）
五、算法设计（6分）.
以下为用头插法建立单链表的运算，分析算法，请在( )处填上正确的语句。
LinkList CreateList()// 建立线性表
{ LinkList H=(LinkList)malloc(sizeof(LNode)); /*生成头结点*/
H->next=NULL; /*空表*/
Lnode *s;
int x; /*设数据元素的类型为int*/
scanf("%d",&x);
while(x!=-1)
{s=(LinkList)malloc(sizeof(LNode));
（ 1 ）
（ 2 ）（ 3 ）
scanf("%d",&x);
}
Return H;
}
[解决办法]
1:c
2:c
3:d
4:b
5:d
6:b
7:a?
8:a
9:b?
10:c?
11:不知道
12:d?
二:
1:不知道
2:不知道
3:不知道
4: 2^(k-1)+2, 2^k+1
5: n*(n-1), n*(n-1)*2
6:不知道
三:
1:什么意思?确定什么东西?
2:Y
3:N
4:N
5:Y
6:不知道
7:N
8:Y
9:N
[解决办法]
一、选择题（3＇×12）
1. 栈和队列都是（A ）
A) 顺序存储的线性结构 B) 链式存储的非线性结构
C)限制存取点的线性结构 D) 限制存取点的非线性结构
2. 若串s=”computer”,其子串个数是( B)
A)8 B) 37 C)36 D)9
3、在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ D）倍
A) 1/2 B) 2 C) 4 D) 1
4、下列排序中,(A )是堆
A) (100,80,55,60,50,40,58,35,20 )
B) (100,80,55,60,50,40,35,58,20)
C) (100,80,55,58,50,40,6035,20)
D) (100,70,55,60,50,40,58,35,20)
5、设树T的度为4,其中度为1、2、3和4的结点个数为4、2、1、1，则T中的叶子数为（A ）
A)5 B) 6 C) 7 D) 8
6、将二叉树的概念推广到三叉树,则一棵有244个结点的完全三叉树的高度为( )
A)4 B)5 C)6 D)7
7、操作系统中采用多道程序设计技术，以提高CPU和外部设备的( D) 。
A．利用率 B．可靠性 C．稳定性 D．兼容性
8、进程和程序的一个本质区别是（D ）。
A ．前者为动态的，后者为静态的； B ．前者存储在内存，后者存储在外存 C 前者在一个文件中，后者在多个文件中；
D 前者分时使用 CPU, 后者独占 CPU
9、有作业控制块JCB连成一串而形成的排队队列称为（ ）。
A．挂起队列 B．阻塞队列
C．就绪队列 D．后备队列
10、在页式存储管理中，块内位移量等于页内位移量是因为（ B）。
A．页和块的大小都是2的整数次方 B．一页是装入内存的连续空间内的
C．页和块的大小相等 D．页和块的大小不等
11、利用SPOOL技术实现虚拟设备的目的是( A)。
A．把独享的设备变为可以共享 B．便于独享设备的分配
C．便于对独享设备的管理 D．便于独享设备与CPU并行工作
12、若信号量S初值为2，当前值为?1，则表示有( )个进程在与S相关的队列上等待。
A．0 B．1 C．2 D．3
二、填充题（1.5＇×10）
1、 感知进程存在的唯一标志是（ ）。
2、 数据元素在计算机中有两种基本的存储结构（顺序 ）和（连表 ）。
3、 操作系统的五大管理功能是（ ）、存储器管理、（ ）作业管理和用户接口。
4、 深度为k（k>1）的完全二叉树至少有( )个结点.至多有( )个结点.
5、 设G为具有n个顶点的无向图，则最多有（ ）条边；若G为具有n个顶点的有向图，则最多有（ ）条边。
6、 按资源分配特点，设备类型可分为以下三类：（ ）、共享 、虚拟。
三、判断题（1＇×10）
1. 一棵二叉树可以由它的先序序列和后序序列唯一确定。T
2. 线性表采用链式存储时,结点的存储空间可以是不连续的。T
3. 进程的互斥和同步总是因相互制约而同时引起 F
4. 计算机中的资源是指计算机的硬件和操作系统两个部分。 F
5. 死锁是指两个或多个进程都处于互等状态而无法继续工作。T
6. 请求分页存储管理系统，若把页面的大小增加一倍，则缺页中断次数会减少50％。
7. 在一个只有单个CPU的计算机中，进程不能并行操作。 T
8. 有n个顶点、n－1条边的图是一棵生成树。
9. 用二叉链表存储n个结点的二叉树，结点的2n个指针域中有n－1个空指针。
P.V操作必须成对出现，有一个P操作就一定有一个V操作。
四、简答计算题（33分）
1. 一个虚拟地址结构用24个二进制位表示。其中12个二进制位表示页面尺寸。试问这种虚拟地址空间总共多少页？每页的尺寸是多少？（7分）
2. 已知一棵二叉树的中序遍历结点排列为DGBAECHIF,后序遍历结点排列为GDBEIHFCA.试画出该二叉树。（7分）
3、对关键字序列（9，4，3，8，10，7，6，5，1，2）
（1） 画出构造的初始大根堆。（5分）
（2） 画出步长为5的一趟希尔排序结果。（4分）
4、设某作业占有7个页面，如果在主存中只允许装入4个工作页面(即工作集为4)，作业运行时，实际访问页面的顺序是1， 2， 3， 6， 4， 7， 3， 2， 1， 4， 7， 5， 6， 5， 2， 1。试用fifo与lru页面调度算法，列出各自的页面淘汰顺序和缺页中断次数，以及最后留驻主存4页的顺序。(假设开始的4个页面已装入主存) （10分）
五、算法设计（6分）.
以下为用头插法建立单链表的运算，分析算法，请在( )处填上正确的语句。
LinkList CreateList() // 建立线性表
{ LinkList H=(LinkList)malloc(sizeof(LNode)); /*生成头结点*/
H->next=NULL; /*空表*/
Lnode *s;
int x; /*设数据元素的类型为int*/
scanf("%d",&x);
while(x!=-1)
{s=(LinkList)malloc(sizeof(LNode));
（ 1 ）
（ 2 ）（ 3 ）
scanf("%d",&x);
}
Return H;
}
