南昌大学2001年数据结构考研试题和参考答案

南昌大学2001年数据结构考研试题和参考答案
报考专业:计算机应用             考试科目:数据结构 (A)
一. 选择题(每题选择一个答案, 将序号填入下划线处,每题2分,共10分)
1. 假定初始序列是递增的,并且按递增序排列,则(  )排序方法花时间最少.
     A.快速    B. shell    C.直接插入     D.冒泡
2. 二维数组 a[0..8, 1..10]按行存放时元素 a[ 8,5 ]的起始地址与按列存放时元素(  )的起始地址相同.
     A. a [8,5]    B. a [3,10]      C. A[5,8]     D. A[0,9]
3. 有一棵平衡二叉树,根结点为A,A的右孩子为B,B的左孩为叶结点C,当A,B二结点的平衡因子分别为(   )时,在结点C下, 插入一个新结点后得到的新树是不平衡的.
     A. 0,0       B. 1,0         C. –1,0        D. 0,1
4.在循环链表中设立一个头结点的理由是(    ).
     A.便于找到链表的首结点         B.可以用头结点记录链表长度
     C.可以使得作插入,删去时不必顾及插入的或删去的结点是否链表的首结点.
     D.可以把首结点与尾结点公开
5.非空的广义表可与有根有序的有向图对应,如果一个有根的有向图中含有回路,那么它对应的广义表是(   )
     A.线性表      B.纯表    C.再入表     D.递归表
二.填空题(每题2分,共10分)
1. 有20个元素的有序表按二分法查找,假定查找每个元素的概率是相等的,则查找成功的平均比较次数为________次.
2. 链接栈的结点有二个域: info, link ,栈顶指针为st, 下列程序段可以把元素x压入栈内:
     new(p); p?.inf=x; ______;
3. 一个好的散列函数的标准是________________.
4. 一个循环队列用数组Q[0..100]存贮其元素, 已知队头,队尾指针分别为80与50, 则当前队列中有_______个元素.
5. 用200个不同的数来构造二叉排序树, 其高度不会超过_______,但也不会少于_______(假定空二叉树的高度为0).

三.算法应用题(每题6分, 共30分)
1. 对下图表示的树林, (1)写出它的后根序序列.(2)画出与它对应的二叉树.

           A        D         G
   
           B       E          H
         
          C       F          I
2. 对序列(26,36,41,38,44,15,68,12,6,51,25)散列存贮于数组A[0..14]中,散列函数为H(R)=Rmod13, 用线性探测法解决冲突,请画出散列表的状况.
3.设有关键码序列: 51(1), 73, 47,95,49,51(2).试写出快速排序(从小到大)与堆排序(从大到小)的最终结果.
4.画出下图的邻接表(要求:出边表中的结点按序号由小到大排列),然后使用该邻接表手工执行深度优先算法(从结点6开始),请写出你得到的遍历序列.
                     1
               2        6
      3               5
             4
5.对下图用用Prim算法从结点6开始构造最小生成树,(1)请用图表示构造的过程.(2)如果从其他结点开始,有没有可能构造出不相同的最小生成树?
(图略)
四.算法设计题(共50分)
1. 求带权有向图中每对结点之间的最短路径的Floyd算法如下:
   (1)(Path数组置初态)
       for I:= 1 to n do
         for j:= 1 to n do
          if adj[I,j]<? then path[I,j]:=(1)
                    else path[I,j]:=(2);
       (2)(求最短路径)
          for k:= 1 to n do
            for I:= 1 to n do
              for j:= 1 to n do
               if adj[I,j]>adj[I,k]+adj[k,j] then
                  begin adj[I,j]:=(3);path[I,j]:=(4) end
请你解答如下问题(1)完成上述算法填空. (2)矩阵adj 的初值是什么?算法结束时,adj[I,j] 和path[I,j]的值表示什么意义?(14分)
2. 写出按对放序线索化以t 为根指针的二叉树的非递归算法.假定用负指针表示线索,并且对栈的基本运算均可调用(12分)
3. 写一算法,重排实型数组R[1..n]中元素的顺序,使得所有负数均排在非负数之前.(要求:不排序,附加空间0(1))(10分)
4. 有一个带有头结点的循环双链表,表头指针为head,结点有四个域,data ,flreg ,llink ,rlink ,其中flreg记录结点数据的访问次数.假定链表的结点已按访问次数不增序排列.(1)画出此链表的结构示意图.(2)写一算法查找链表中是否有值为x的结点,如有,则让该结点的访问次数加1 ,并且要使链表仍保持不增序,如没有,则不作任何工作.(14分)

参考答案
一. 判断题:2,4,7,9,10,12,13 Y
二.
1. 执行时间的不确定,  执行顺序的不确定
2. 作业的输入, jcb的建立
3. 程序的顺序执行.
4. 执行期间不允许中断,作为原语的程序段不允许并发执行.
5. 发送进程名,接收进程名,数据,有关数据的操作
6. 不同作业流
7. 地址结构,寻址方式
8. 互斥
9. 地址由小到大, 分区由小到大, 分区由大到小
10. 19
11. 重定位(地址变换)
三.
1. 进程的调度功能:
(1) 记录系统中所有进程的情况.(1分)
(2) 选择占有处理机的进程.(1分)
(3) 进行进程上下文的切换.(1分)
优先数调度法是根据进程的优先级别俩进行调度的.一般分为静态优先数和动态优先数两种调度法.动态优先数是指随着时间的推移,要对各进程的优先数重新计算.动态优先数调度性能高,系统效率也较高.(2分)
2. 设备管理程序的功能是:
(1) 提供和进程管理系统的接口.(1分)
(2) 进行设备的分配. (1分)
(3) 实行设备和设备,设备和CPU之间的并行操作. (1分)
(4) 进行缓冲区的管理. (1分)
通过Spooling技术可将独享设备改为可共享的设备. (1分)
3. (1)取出指令的有效地址.
(2)根据作业的页大小或存储块的大小,计算该有效地址对应的页号和页内位移量.
   (3)通过页号到作业的页表中查到对应的块号.
   (4)通过块号和页内位移量计算有效地址所对应的内存物理地址.
(5) 通过物理地址到内存取指令或取数.
4. 作业调度主要的任务是按一定的原则对外存输入井上的大量后备作业时行选择,给选出的作业分配内存,输入输出设备等必要的资源,并建立相应的进程,以使该作业的进程获得竞争处理机的权利,同时还负责回收系统的资源.(2分)
交换调度主要任务是按照给定的原则和策略,将处于外存交换区中的就绪状态或等待状态的进程调入内存,或把处于内存就绪状态或内存等待状态的进程交换到外存交换区.
进程调度主要任务是按照某种策略和方法选取一个就绪进程占用处理机.(1分)
  (1)  属于进程调度一级(1分)
  (2)   属于交换调度一级(1分)
5. 操作系统为用户提供了两类接口.一个是系统为用户提供的各种命令接口;另一个是系统调用. (1分)
使用操作命令进行作业控制有两种方式:脱机方式和联机方式.脱机方式利用作业控制语言来编写表示用户控制意图的作业控制程序即作业说明书.联机控制方式是指用户使用系统提供的操作命令和系统会话,交互地控制程序执行和管理计算机系统.(2分)
系统调用是操作系统提供给编程人员的唯一接口.编程人员利用系统调用,在源程序一级动态请求和释放系统资源,调用系统中已有的系统功能来完成那些与机器硬件部分相关的工作以及控制程序的执行速度等.(2分)
四. 第一个程序的使用顺序是按列进行的,所以缺页次数为256*256=65536次
   第二个程序的使用顺序与存储顺序一致,所以缺页次数为256次.
   (解释各1分,结论各2 分)
参考答案五. 未分解的访盘次数为:一个盘块占1024div48=21个目录,所以256的目录要占256div21+1=13(块),平均访盘次数=(13+1)/2=7次.
分解后: 一个盘块占1024div 8=128个目录,所以256个目录占256div 128=2个盘块.平均访盘次数=(1+2)/2+1=2.5次.
一般地,若某个目录文件用N个盘块存放文件目录表目,必用M个盘块存放符号文件目录表目,则查找该目录文件中的一个文件目录表目而引起的访盘次数从(N+1)/2变为(M+1)/2+1.于是:
当N-M>2时,访盘次数减少.
当N-M=2时,访盘次数相等.
当N-M<2时,访盘次数增加.
六. (参考答案)
定义三个信号量2分)
S: 表示是否可以把数存入缓冲嚣,由于缓冲器中每次只能放一个数,所以它的初始值为”1”
SO: 表示缓冲嚣中是否有奇数,初始值为”0”,表示无奇数.
SE: 表示缓冲嚣中是否有偶数,初始值为”0”,表示无偶数.
并发程序如下 (类PASCAL语言描述)(8分)
begin
   S ,SO ,SE : semaphore ;
   S:=1;
   SO:=0;SE:=0;
Cobegin
Process  R
    X:intrger;
     begin
         L1: 从输入设备上读一个数:
         X:=读入的数;
          P(S);
          B:=x;
          If B=奇数 then V(SO)
                     Else  V(SE);
                        Goto  L1;
          End;
   Process  W1
    Y:intrger;
     begin
         L2: P(SO);
         Y:=B;
          V(S);
           打印y中数;
            Goto  L2;
          End;
    Process  W2
       Z:intrger;
        begin
          L3: P(SE);
           Z:=B;
            V(S);
            打印z中数;
            Goto  L3;
          End;
     Coend;
End;
七. (参考答案)
定义三个信号量3分)
customers=0;    //顾客等待服务的信号量
barbers=0;      //理发师等待顾客的信号量
mutex=1;       // 互斥信号量(对共享变量操作)
一个计数共享变量(1分)
waiting=0;        等待理发的顾客数
一个常量CHAIRs表示椅子总数(1分)
程序如下10分)
Process  barber
begin
      while  true  do
      begin
        P(customers);             顾客数为零,则入睡
        P(mutex);                进入临界区
              Waiting:=waiting-1;  减少顾客数
      V(barbers);                理发师准备理发
      V(mutex);                 
         Cut_hair();             理发
       End;
End;
Process  customer
begin
       P(mutex);                进入临界区
       If (waiting<CHAIRs)
       begin
        Waiting=waiting+1;       增加等待的顾客数
       V(customers);             如有必要,则唤醒理发师
       V(mutex);                释放信号量mutex
       P(barbers);               如果无顾客.则理发师入睡
       Get_hair()                进入理发室理发
       end
       else
       V(mutex)                已满,不能停留