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

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

《大学计算机软件技术基础考试技术复习题.docx》由会员分享，可在线阅读，更多相关《大学计算机软件技术基础考试技术复习题.docx（18页珍藏版）》请在冰点文库上搜索。

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

线性表采用链式存储时，结点的存储地址（）

A.必须是不连续的

B.连续与否均可

C.必须是连续的

D.和头结点的存储地址相连续

由两个栈共享一个向量空间的好处是：

（）

A.减少存取时间，降低下溢发生的机率

B.节省存储空间，降低上溢发生的机率

C.减少存取时间，降低上溢发生的机率

D.节省存储空间，降低下溢发生的机率

假设以带行表的三元组表表示稀疏矩阵，则和下列行表

0

2:

33

i5

对应的稀疏矩阵是（）

在一棵度为3的树中，度为3的结点个数为2,度为2的结点个数为1,则度为0的结点个数为（）

A.4B.5C.6D.7

一棵含18个结点的二叉树的高度至少为（C）

A.3B.4C.5D.6

已知二叉树的先序序列为ABDECJF中序序列为DBEAF0则后序序列为（D）

A.DEBAFCB.DEFBCAC.DEBCFAD.DEBFCA

无向图中一个顶点的度是指图中（B）

A.通过该顶点的简单路径数B.与该顶点相邻接的顶点数

设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。

若对

索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，贝S在查找概

率相等的情况下，分块查找成功时的平均查找长度为（B）

A.21B.23C.41D.62

在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）

22

A.eB.2eC.n—eD.n—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时所需进行的关键字比较次数为2。

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

a

（1）画出b该图的图形；

c

（2）根据e邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍

广度优先遍历序列为：

abedc

LListnote（LListT）〃T是不带头结点的单链表的头指针

{

If（T&&T->next）{

P=T

;T=T—>next;q=T;

Ro

while（q－＞next）q=q－＞next；

Rt：

q－＞next=p；

}

returnT；

}

请回答下列问题：

（1）Ro和Rt行的功能是什么？

（2）说明算法的功能。

（1）Ro查询链表的尾结点，Rt将第一个结点链接到链表的尾部，作为新的尾结点

（2）使原单链表变为循环单链表，返回循环单链表的头指针

假设两个队列共享一个循环向量空间（参见右下图），

其类型Queue2定义如下：

typedefstruct{

DateTypedata[MaxSize]；

intfront[2],rear[2]；

}Queue2；

对于i=0或1，front[i]和rear[i]分别为第i个队列的头指针和尾指针请对以下算法填空，实现第i个队列的入队操作。

intEnQueue（Queue2*Q,inti,DateTypex）{//若第i个队列不满，则元素x入队列，并返回1；否则返回

if（i<0||i>1）return0

if（Q—>rear[i]==Q—>front[①]return0;

Q—>data[②]=x;

Q—>rear[i]=[③];

returnl;

}

1（i+1）%2（或1—i）

2Q->rear[i]

3（Q—>rear[i]+1）%Maxsize

已知一个图如下所示，其顶点按a、b、c、d、e、f顺序存放在邻接表的顶

点表中，请画出该图的邻接表，使得按此邻接表进行深度优先遍历时得到的顶点序列为acbefd，进行广度优先遍历时得到的顶点序列为acbdfe。

已知两个4X5的稀疏矩阵的三元组表分别如下：

0141601132

12218122—22

234—2522569

3422833425

44251

请画出这两个稀疏矩阵之和的三兀组表。

解：

从空树起，依次插入关键字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）的功能。

intalgo（intL[],intn）

{

inti=0,j,s=1,t=n;

while（i!

=（n+1）/2）

{

intx=L[s]；

i=s;j=t;

while（i<j）

{

while（i<j&&L[j]>=x）j--;

L[i]=L[j];

while（i<j&&L[i]<=x）i++;L[j]=L[i];

}

L[i]=x;

if（i<（n+1）/2）s=i+1;

elset=i-1;

}

if（i==0）return0;

elsereturnL[i];

}

（1）

（2）（3）

33题答案：

（1）外循环执行4次，函数返回值为3。

（2）将A[1]至A[8]中不小于A[1]的元素进行递增排序，如调用algo（A,8）

时最终排序结果为

21346789

队和栈的主要区别是（

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的功能。

voidalgo（Queue*Q）

StackS;

InitStack（&S）;

while（!

QueueEmpty（Q））

Push（&S,DeQueue（Q））;

while（!

StackEmpty（&S））

EnQueue（Q,Pop（&S））;

}

（1）87542

（2）队列倒置在数据结构中，数据的逻辑结构可以分成（）

A.内部结构和外部结构B.线性结构和非线性结构

C.紧凑结构和非紧揍结构D.动态结构和静态结构

在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（）

A.数据元素的相邻地址表示B.数据元素在表中的序号表示

C.指向后继元素的指针表示D.数据元素的值表示

设p指向单链表中的一个结点，s指向待插入的结点，则下述程序段的功能是（）

s->next=p->next;p->next=s;

s->da

t=p->data;p->data=s->data;

ta=t;

A.结点*p与结点*s的数据域互换

B.在p所指结点的元素之前插入元素

C.在p所指结点的元素之后插入元素

D.在结点*p之前插入结点*s栈和队列都是（

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个结点，则该树共有—2A3+7/2=11___个叶子结点。

假设元素只能按a,b,c,d的顺序依次进栈，且得到的岀栈序列中的第一个元素为c,则可能得到的岀栈序

列为，不可能得到的出栈序列为

1）cbad,cbda,cdba

2）cabd,cadb,cdab

若以邻接矩阵表示有向图，则邻接矩阵上

第i行中非零元素的个数即为顶点vi的。

岀度

下列函数的功能是，对以带头结点的单链表作为存储结构的两个递增有序表（表中不存在值相同的数据元

素）进行如下操作：

将所有在Lb表中存在而La表中不存在的结点插入到La中，其中La和Lb分别为两个链表的头指针。

请在空缺处填入合适内容，使其成为一个完整的算法。

voidunion

（LinkList

La,

LinkList

Lb）

1

//本算法的功能是将所有

Lb表中存在而

La表中不存在的结点插入到

La表中

LinkList

pre=La,

q;

LinkList

pa=La

->

next;

LinkList

pb=Lb

->

next;

free

（Lb）;

while

（pa

&&pd）

{

{

if

（pa

->data

->

data）

{

pre

=pa;pa=

pa

->

next;}

else

if

（pa->

data

>

pb

>data）

{

⑴

pre=pb;

pb=pb->next;

（2）

}

else

}

}

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）处理结果。

Voidsort（intR[],intn）

{

intpass=0,k,exchange,x;

do{

k=pass%2+1;

exchange=0;

while（k

{

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

36

12

第二趟

（pass

=1）:

8

5

9

3

71

62

在长度为n的顺序表中删除第i个元素（1

若不带头结点的单链表的头指针为head，则该链表为空的判定条件是（

引起循环队列队头位置发生变化的操作是（

若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是（

由同一关键字集合构造的各棵二叉排序树

和元素的个数。

（3）

设m=40,rear=13,quelen=19,求队头元素的位置；

（1）

quelen

==m

（2）

quelen

==0

（3）

（13

-19+40）%40=34

（4）

（rear

-quelen+m）%m

写出一般情况下队头元素位置的表达式。

（4）

阅读下列算法，并回答问题：

（3）

简述算法的功能。

inti=0,j;

while（ilength&&x>L->data[i]）i++;

if（ilength&&x==L->data[i]）{//找到x，则删除x,大于x的数前移

for（j=i+1;jlength;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）写出上述函数调用过程中进行元素交换操作的总次数。

voidf32

（intR[],intn）{

int

i,t;

for

（i=0;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个进程共享同一临界资源，若使用信号量机制实现对一临界资源的互斥访问，则信号量的变化范围是（）。

A1至-（m-1）B.1至m-1C.1至-mD.1至m

在下面关于虚拟存储器的叙述中，正确的是（）。

A.要求程序运行前必须全部装入内存且在运行过程中一直驻留在内存

B.要求程序运行前不必全部装入内存且在运行过程中不必一直驻留在内存

C.要求程序运行前不必全部装入内存但是在运行过程中必须一直驻留在内存

D.要求程序运行前必须全部装入内存但在运行过程中不必一直驻留在内存

采用段式存储管理的系统中，若地址用24位表示，其中8位表示段号，则允许每段的最

大长度是（）。

2416—832

A.2B.2C.2D.2

进程主要由程序、数据和PCB三部分内容组成，其中

PCB是进程存在的惟一标识，而数据部分也可以为其它进程共享。

当处理器空闲时，调度程序从就绪进程队列中选择一个进程给其分配CPU处

于阻塞状态的进程是不会获得CPU勺。

在响应比最高者优先的作业调度算法中，当各个作业等待时间相同时，运行

的作业将得到优先调度；当各个作业要求运行的时间相同时，等待时间长的

作业得到优先调度。

某系统中共有10台磁带机被m个进程竞争，每个进程最多要求3台磁带机，那么当m

的取值为_不超过4的整数___时，系统不会发生死锁。

设有8页的逻辑空间，每页有1024字节，它们被映射32块的物理存储区中，那么，逻

辑地址的有效位是_13_位，物理地址至少是_15_位

页号

物理块号

0

3

1

4

2

6

在一个分页存储管理系统中，页长为4KB某一作业的页表如图1所示，虚拟地址3000对应的物理地址为

12K+3000=152888。

说明作业调度和进程调度的区别，分析：

在可获得处理机时，应将它分给哪个就绪进程由哪一级调度程序负责？

答：

作业调度用于决定把外存中处于后备队列中的哪些作业调入内存，并为它们创建进程，分配资源，然后将新创建进程插入就绪队列；进程调度决定将处理机分配给就绪进程队列的哪个进程。