一、选择题（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．1            C．2            D．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;
}

兄弟，你有答案吗？？

都若干个小时了

答案消失了

恩

汗，有没有答案啊

兄弟 答案呢