大学计算机软件技术基础考试技术复习题.doc

(完整版)大学计算机软件技术基础考试技术复习题
线性表采用链式存储时，结点的存储地址（ )
A．必须是不连续的
B．连续与否均可
C．必须是连续的
D．和头结点的存储地址相连续
由两个栈共享一个向量空间的好处是：( ）
A．减少存取时间，降低下溢发生的机率
B．节省存储空间,降低上溢发生的机率
C．减少存取时间，降低上溢发生的机率
D．节省存储空间，降低下溢发生的机率

假设以带行表的三元组表表示稀疏矩阵，则和下列行表
0
2
3
3
5
对应的稀疏矩阵是( ）

在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为( ）
A．4 B．5 C．6 D．7
一棵含18个结点的二叉树的高度至少为( C ）
A.3 B。4 C。5 D.6
已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为（ D ） A.DEBAFC B.DEFBCA C.DEBCFA D.DEBFCA
无向图中一个顶点的度是指图中（ B ）
A。通过该顶点的简单路径数 B.与该顶点相邻接的顶点数
C。通过该顶点的回路数 D。与该顶点连通的顶点数
设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为（ B )
A.21 B。23 C。41 D.62

在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( ）
A．e B．2e C．n2－e D．n2－2e
用某种排序方法对关键字序列（25，84,21，47，15，27,68，35，20)进行排序时，序列的变化情况如下：
20，15，21，25，47，27，68，35，84
15，20，21,25，35，27，47，68，84
15，20，21，25，27，35，47，68，84
则所采用的排序方法是( ）
A．选择排序 B．希尔排序 C．归并排序 D．快速排序

数据的逻辑结构是从逻辑关系上描述数据，它与数据的 存储（或存储结构） 无关,是独立于计算机的。
在一个带头结点的单循环链表中，p指向尾结点的直接前驱,则指向头结点的指针head可用p表示为head= p－＞next－＞next 。
栈顶的位置是随着 进栈和退栈 操作而变化的。
假设一个9阶的上三角矩阵A按列优先顺序压缩存储在一维数组B中，其中B［0]存储矩阵中第1个元素a1，1，则B[31］中存放的元素是 a4,8 .
已知一棵完全二叉树中共有768结点，则该树中共有 384 个叶子结点.
已知一个图的广度优先生成树如右图所示,则与此相
应的广度优先遍历序列为 abefcdg 。

从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需___前移___一个位置。
在队列中,允许进行插入操作的一端称为____队尾____，允许进行删除操作的一端称为___队头___。

在有序表（12，24，36，48，60,72，84）中二分查找关键字72时所需进行的关键字比较次数为 ２ 。

已知一个无向图的顶点集为｛a， b, c， d, e} ,其邻接矩阵如下所示
a
b
c
d
e

（1)画出该图的图形；
(2）根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。
该图的图形为：

深度优先遍历序列为:abdce
广度优先遍历序列为：abedc

LList note（LList T) //T是不带头结点的单链表的头指针
｛
If （T&＆T->next） ｛
p=T；T=T－〉next；q=T;
Ro: while（q－〉next) q=q－>next；
Rt: q－〉next=p；
}
return T；
}
请回答下列问题:
（1）Ro和Rt行的功能是什么?
（2)说明算法的功能.

(1）Ro查询链表的尾结点,Rt将第一个结点链接到链表的尾部，作为新的尾结点
（2)使原单链表变为循环单链表，返回循环单链表的头指针

假设两个队列共享一个循环向量空间(参见右下图），
其类型Queue2定义如下：
typedef struct{
DateType data[MaxSize]；
int front[2］,rear［2]；
｝ Queue2；
对于i=0或1,front［i]和rear[i］分别为第i个队列的头指针和尾指针。请对以下算法填空，实现第i个队列的入队操作。
int EnQueue (Queue2*Q,int i,DateType x)
{//若第 i个队列不满，则元素x入队列，并返回1；否则返回0
if（i〈0|｜i>1）return 0；
if(Q－〉rear[i］==Q－>front［ ① ］ return 0；
Q－〉data[ ② ]=x；
Q－>rear[i]=［ ③ ]；
return1；
}

①（i＋1）%2（或1－i）
②Q－>rear［i]
③（Q－〉rear［i］＋1）％Maxsize
已知一个图如下所示，其顶点按a、b、c、d、e、f顺序存放在邻接表的顶点表中,请画出该图的邻接表，使得按此邻接表进行深度优先遍历时得到的顶点序列为acbefd,进行广度优先遍历时得到的顶点序列为acbdfe。

已知两个4×5的稀疏矩阵的三元组表分别如下：
0 1 4 16 0 1 1 32
1 2 2 18 1 2 2 －22
2 3 4 －25 2 2 5 69
3 4 2 28 3 3 4 25
4 4 2 51
请画出这两个稀疏矩阵之和的三元组表。
解：

从空树起，依次插入关键字40，8，90，15,62，95，12，23，56，32，构造一棵二叉排序树。
（1)画出该二叉排序树
（2）画出删去该树中元素值为90的结点之后的二叉排序树.

阅读下列函数algo，并回答问题。
(1）假设整型数组A［1。。8]中的元素依次为(3，8，9，1，7，4，2，6)。执行函数调用algo(A，8）时，外层while的循环体执行多少次？函数的返回值是多少？
（2)简述函数algo（L，n)的功能。
int algo（int L［]，intn）
｛
int i=0,j，s=1，t=n;
while （i！=(n+1）/2）
｛
int x=L[s］；
i=s;j=t；
while（i＆lt；j）
｛
while(i＆lt；j ＆& L［j］＆gt；=x)j-—；
L[i］=L［j]；
while（i＆lt;j && L［i］＆lt;=x)i++；
L［j]=L[i］;
}
L［i］=x;
if(i＆lt；（n+1）/2）s=i+1；
else t=i-1；
}
if（i==0)return 0；
else return L[i];
｝ (1） (2） (3）
33题答案：
（1）外循环执行4次，函数返回值为3。
（2)将A[1]至A［8］中不小于A[1］的元素进行递增排序，如调用algo(A,8)时最终排序结果为2 1 3 4 6 7 8 9
队和栈的主要区别是（  d    ）
A.逻辑结构不同                            B。存储结构不同
C.所包含的运算个数不同                    D。限定插入和删除的位置不同
链栈与顺序栈相比,比较明显的优点是(  d    )
A。插入操作更加方便                        B。删除操作更加方便
C。不会出现下溢的情况                    D。不会出现上溢的情况
二叉树中第5层上的结点个数最多为(   d   )
A.8                         B.15
C.16                        D.32
假设队列q中的元素为(2，4，5，7，8)，其中“2”为队头元素。写出执行函数调用algo（＆q）后的队列q；
（2)简述算法algo的功能.
void algo(Queue ＊Q）
｛
  Stack S;
  InitStack(&S）;
  while (!QueueEmpty（Q))
    Push(&S， DeQueue（Q));
  while （! StackEmpty（＆S））
    ＥnQueue(Q,Pop（&S)）；
｝
(1）87542
（2) 队列倒置
在数据结构中，数据的逻辑结构可以分成(　　　）
A．内部结构和外部结构   B．线性结构和非线性结构
C．紧凑结构和非紧揍结构   D．动态结构和静态结构
在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（　　　）
A．数据元素的相邻地址表示  B．数据元素在表中的序号表示
C．指向后继元素的指针表示  D．数据元素的值表示
设p指向单链表中的一个结点,s指向待插入的结点，则下述程序段的功能是(　　　)
　　　　　s -〉 next = p -> next;    p —〉 next = s;
          t = p —〉 data;     p —> data = s —〉 data；    s —>data = t；
A．结点＊p与结点*s的数据域互换
B．在p所指结点的元素之前插入元素
C．在p所指结点的元素之后插入元素
D．在结点＊p之前插入结点＊s
栈和队列都是（　　　）
A．限制存取位置的线性结构  B．顺序存储的线性结构
C．链式存储的线性结构   D．限制存取位置的非线性结构
当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为（　　　）
A．左子树的叶子结点    B．左子树的分支结点
C．右子树的叶子结点    D．右子树的分支结点
希尔排序的增量序列必须是（　　　）
A．递增的      B．随机的
C．递减的      D．非递减的
如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为(　　　)
A．插入排序      B．归并排序
C．冒泡排序      D．堆排序
已知指针p指向单链表中某个结点，则语句p -> next =p —〉 next —> next的作用是________________。
删除＊P的直接后继结点
删除双向循环链表中*p的前驱结点(存在)应执行的语句是____________。
q = p—>pre;
q-〉pre—〉next = p;
p—〉pre = q—>pre；
free( q ）;
栈下溢是指在____栈空________时进行出栈操作。
已知完全二叉树T的第5层只有7个结点，则该树共有___2^3 + 7 / 2 = 11___个叶子结点.
在有向图中，以顶点v为终点的边的数目称为v的_____入度_______。

假设元素只能按a，b，c,d的顺序依次进栈，且得到的出栈序列中的第一个元素为c，则可能得到的出栈序列为________________,不可能得到的出栈序列为________________
1）cbad, cbda, cdba
2)cabd, cadb， cdab
若以邻接矩阵表示有向图,则邻接矩阵上
　第i行中非零元素的个数即为顶点vi的________________.
出度
下列函数的功能是,对以带头结点的单链表作为存储结构的两个递增有序表（表中不存在值相同的数据元素）进行如下操作：将所有在Lb表中存在而La表中不存在的结点插入到La中,其中La和Lb分别为两个链表的头指针。请在空缺处填入合适内容，使其成为一个完整的算法.
　void union (LinkList La， LinkList Lb）
{
  //本算法的功能是将所有Lb表中存在而La表中不存在的结点插入到La表中
  LinkList pre = La， q；
  LinkList pa = La -> next;
  LinkList pb = Lb -〉 next；
  free (Lb）；
  while (pa && pd)
  ｛
   if (pa -> data 〈pb -> data)
   ｛  pre = pa； pa = pa —〉 next；｝
   else if （pa —〉 data > pb —>data)
   ｛
          （1）       ;
    pre = pb;
    pb = pb -> next；
          (2)       ;
   }
   else
   {
    q = pb; pb = pb -〉 next; free (q);
   }
  }
  if （pb)
          （3）         ;
｝

(1) pre—〉next = pb
（2） pre-〉next = pa
（3) pre-〉next = pb
已知整形数组L［1。。8]中的元素依次为（9，8，5，7，6，3，2，1)，阅读下列函数，并写出执行函数调用　sort(L, 8)时，对L进行的头两趟（pass分别为0和1)处理结果。
　Void sort (int R[]，int n)
｛
　 int pass = 0， k, exchange， x;
　 do ｛
　  k=pass％2+1;
　  exchange = 0;
　  while (k<n)
　  ｛
　  　if (R［k]〉R[k+1］）
　  　{
　   x = R［k］； R[k］ = R[k+1］； R［k+1］ = x;
　   exchange =1；
     ｝
K+=2
         ｝       
   　pass ++;
   ｝while （exchange = = 1|｜ pass <=1);
}
第一趟（pass = 0）： 8 9 5 7 3 6 1 2
第二趟（pass = 1）: 8 5 9 3 7 1 6 2
在长度为n的顺序表中删除第i个元素（1≤i≤n）时,元素移动的次数为（      )
A。 n-i+1                  B。 i
C。 i+1                    D。 n—i
若不带头结点的单链表的头指针为head，则该链表为空的判定条件是（      ）
A. head==NULL                   B. head—>next==NULL
C。 head！=NULL                  D. head-〉next==head
引起循环队列队头位置发生变化的操作是（      ）
A。 出队                      B. 入队
C. 取队头元素                D. 取队尾元素
若进栈序列为1，2,3，4,5，6，且进栈和出栈可以穿插进行,则不可能出现的出栈序列是（      ）
A。 2，4,3,1，5，6                B。 3,2，4，1，6，5
C。 4，3，2，1，5，6                D. 2，3，5，1，6，4
对关键字序列（56，23，78,92,88，67,19，34）进行增量为3的一趟希尔排序的结果为（      ）
A. （19,23，56，34，78,67,88,92）         B。 (23，56,78，66，88，92，19，34)
C. (19，23，34，56,67，78，88，92)         D. （19，23,67，56，34，78，92,88)
由同一关键字集合构造的各棵二叉排序树（      )
A。 其形态不一定相同，但平均查找长度相同
B。 其形态不一定相同,平均查找长度也不一定相同
C。 其形态均相同，但平均查找长度不一定相同
D。 其形态均相同，平均查找长度也都相同
数据的逻辑结构在计算机存储器内的表示，称为数据的_____存储结构_______。
假设以数组seqn［m］存放循环队列的元素,设变量rear和quelen分别指示循环队列中队尾元素的位置和元素的个数。
(1)写出队满的条件表达式；
(2）写出队空的条件表达式；
（3）设m=40,rear=13,quelen=19,求队头元素的位置；
(4)写出一般情况下队头元素位置的表达式。
（1） quelen == m
(2） quelen == 0
（3) ( 13 - 19 + 40 ） ％ 40 = 34
(4） （ rear - quelen + m ) ％ m
阅读下列算法，并回答问题:
（1)设顺序表L=(3,7,11，14，20,51)，写出执行f30（＆L，15）之后的L；
（2)设顺序表L=(4,7，10,14，20，51），写出执行f30（&L,10）之后的L；
（3）简述算法的功能。
void f30(SeqList＊L， DataType x)
{
     int i =0， j;
     while (i<L—>length ＆＆ x>L-〉data［i]）i++;
     if(i<L—>length &＆ x==L—>data［i]）  ｛//找到x，则删除x，大于x的数前移
        for（j=i+1;j<L—〉length；j++)
            L—>data［j-1］=L—〉data[j］；
        L-〉length--；
     } else {//没找到，插入x， 大于x的数后移
        for（j=L—〉length；j>i;j—-）
            L—〉data［j］=L->data［j-1］;
        L—〉data［i］=x;
        L-〉length++；
     ｝
}
（1） L=(3,7，11，14,15，20,51)
（2) L=(4，7，14,20,51）
(3） 在顺序表L中查找数x，
    找到,则删除x，
    没找到，则在适当的位置插入x，插入后,L依然有序。
假设数组L［8］=｛3,0，5,1,6,4，2，7}，写出执行函数调用f32（L，8)后的L；
（2)写出上述函数调用过程中进行元素交换操作的总次数.
void f32（int R[]，int n){
  int i,t；
   for (i=0；i〈n—1；i++)
     while （R［i］！=i)｛
         t=R［R［i］］;       
         R［R［i]］=R［i］；  
         R［i］=t；
     ｝
｝

while（)｛}里是把R［ i ］ 和 R[ R[ i ］ ］ 交换；
（1) L = { 0, 1, 2， 3， 4， 5， 6， 7 ｝;
(2）5次
能进行二分查找的线性表，必须以(　A　　）
A．顺序方式存储,且元素按关键字有序
B．链式方式存储,且元素按关键字有序
C．顺序方式存储，且元素按关键字分块有序
D．链式方式存储,且元素按关键字分块有序
数组采用顺序存储方式表示是因为通常不对数组进行___插入和删除______操作。
结点数为20的二叉树可能达期的最大高度为____19_____。
在现代操作系统中引入了（ ），从而使并发和共享成为可能。
A.单道程序 B。 磁盘 C。 对象 D。多道程序
( )操作系统允许在一台主机上同时连接多台终端，多个用户可以通过各自的终端同时交互地使用计算机。
A。网络 B.分布式 C。分时 D。实时
当一个进程处于（ ）状态时，称其为等待（或阻塞）状态。
A. 它正等待中央处理机 B。 它正等待合作进程的一个消息
C。 它正等待分给它一个时间片 D. 它正等待进入内存
一个进程释放一种资源将有可能导致一个或几个进程（ )。
A.由就绪变运行 B。由运行变就绪 C.由阻塞变运行 D。由阻塞变就绪
有m个进程共享同一临界资源,若使用信号量机制实现对一临界资源的互斥访问,则信号量的变化范围是（ ）.
A.1至 –(m—1) B。1至m—1 C.1至–m D.1至m
在下面关于虚拟存储器的叙述中，正确的是（ ）。
A。要求程序运行前必须全部装入内存且在运行过程中一直驻留在内存
B。要求程序运行前不必全部装入内存且在运行过程中不必一直驻留在内存
C.要求程序运行前不必全部装入内存但是在运行过程中必须一直驻留在内存
D.要求程序运行前必须全部装入内存但在运行过程中不必一直驻留在内存

采用段式存储管理的系统中,若地址用24位表示,其中8位表示段号,则允许每段的最大长度是（ )。
A。224 B.216 C.28 D。232
进程主要由__程序_____、___数据_____和_____PCB_______三部分内容组成，其中____PCB____是进程存在的惟一标识,而_____数据_____部分也可以为其它进程共享。
当处理器空闲时，调度程序从 __就绪_____ 进程队列中选择一个进程给其分配CPU,处于____阻塞________状态的进程是不会获得CPU的。
在响应比最高者优先的作业调度算法中，当各个作业等待时间相同时，运行时间短_____ 的作业将得到优先调度；当各个作业要求运行的时间相同时，___等待时间长___ 的作业得到优先调度。
某系统中共有10台磁带机被 m 个进程竞争，每个进程最多要求3台磁带机，那么当m的取值为_不超过4的整数___时，系统不会发生死锁。
设有8页的逻辑空间,每页有1024字节，它们被映射32块的物理存储区中，那么,逻辑地址的有效位是__13________位,物理地址至少是_____15_____位。
在一个分页存储管理系统中，页长为4KB，
页号
物理块号
0
3
1
4
2
6
某一作业的页表如图1所示，虚拟地址3000对应的物理地址为12K+3000=152888 。

说明作业调度和进程调度的区别，分析:
在可获得处理机时,应将它分给哪个就绪进程
由哪一级调度程序负责?
答：作业调度用于决定把外存中处于后备队列中的哪些作业调入内存,并为它们创建进程，分配资源,然后将新创建进程插入就绪队列；进程调度决定将处理机分配给就绪进程队列的哪个进程。