《计算机软件技术基础》试题及答案Word格式.docx
《《计算机软件技术基础》试题及答案Word格式.docx》由会员分享，可在线阅读，更多相关《《计算机软件技术基础》试题及答案Word格式.docx（38页珍藏版）》请在冰点文库上搜索。
next=s;
B.（*p）.next=s;
（*s）.next=（*p）.next;
C.s->
next=p->
next;
next=s->
D.s->
7.将两个各有n个元素的有序表归并为一个有序表时，其最少的比较次数是A。
A.n B.2n-1
C.n-1 D.2n
8.下面的程序段是合并两个无头结点链表（ha和hb）为一个无头结点链表ha的过程，作为参数的两个链表都是按结点的data域由大到小链接的。
合并后新链表的结点仍按此方式链接。
请填写下述空框，使程序能正确运行。
#defineNULL0typedefstructnode{
intdata;
structnode*next;
}node,linklisttype;
voidcombine（linklisttype*ha,linklisttype*hb）{linklisttype*h,*p;
h=（linklisttype*）malloc（sizeof（linklisttype））;
h->
next=NULL;
p=h;
while（ha!
=NULL&
&
hb!
=NULL）
if（ha->
data>
=hb->
data）{ /*较大的元素先插入*/p->
next=
（1）;
p=
（2）;
（3）;
}else{
p->
next=（4）;
p=（5）;
（6）;
}
if（ha==NULL）（7）;
if（hb==NULL）（8）;
ha=h->
free（h）;
参考答案：
（1）ha
（2）p->
next（3）ha=ha->
next（4）hb（5）p->
next（6）hb=hb->
next（7）p->
next=hb （8）p->
next=ha
9.如果表A中所有元素（a1,a2,„,an）与表B的一个顺序子表（bk,bk+1,„bk+n-1）完全相同（即a1=bk,a2=bk+1,„an=bk+n-1），则称表A包含在表B中。
设ha，hb为带头结点的单链表，分别表示有序表A和B，下面的函数用于判别表A是否包含在表B中，若是，则返回true，否则返回false。
（提示：
用递归实现）
#definetrue1#definefalse0#defineNULL0typedefstructnode{
intinclusion（linklisttype*ha,linklisttype*hb）{linklisttype*pa,*pb;
pa=ha->
pb=hb->
（1）;
while（
（2））
if（pa->
data=pb->
data）（3）;
else （4）;
（5）;
参考答案：
（1）if（pa==NULL）return（true）
（2）pb!
=NULL&
pa->
=pb->
data（3）return（inclusion（pa,pb））
（4）pb=pb->
（5）return（false）
10.在本题的程序中，函数create_link_list（n）建立一个具有n个结点的循环链表；
函数
josephus（n,I,m）对由create_link_list（n）所建立的具有n个结点的循环链表按一定的次序逐个输出，并删除链表中的所有结点。
参数n（n>
0）指明循环链表的结点个数，参数I（1
≤I≤n）指明起始结点，参数m（m>
0是步长），指明从起始结点或前次被删除并输出的结点之后的第m个结点作为本次被输出并删除的结点。
例如，对于下图所示的具有6个结点的循环链表，在调用josephus（6,3,2）后，将输出5,1,3,6,4,2。
请在空框处填上适当内容，每框只填一个语句。
linklisttype*create_link_list（intn）{linklisttype*head,*p,*q;
intI;
head=NULL;
if（n>
0）{
head=（linklisttype*）malloc（sizeof（linklisttype））;
p=head;
for（I=1;
I<
=n-1;
I++）{ /*此循环用于建立一个链表，链表的内容从1至n-1*/p->
data=I;
q=（linklisttype*）malloc（sizeof（linklistttype））;
（1）;
（2）;
data=n;
（3）;
/*建立从尾链到首的环形结构*/
return（head）;
voidJosephus（intn,intj,intm）{linklisttype*p,*q;
intj;
p=create_link_list（n）;
for（;
I>
1;
I--）p=p->
（4）;
while（j<
n）{
=m-1;
I++）p=p->
printf（“%8d”,q->
data）;
free（q）;
j=j+1;
（1）p->
next=q;
（2）p=q;
（3）p->
next=head
（4）j=0
（5）q=p->
（6）p->
next=q->
11.在下列程序中，函数difference（A,B）用于求两集合之差C=A-B，即当且仅当e是A中的一个元素，且不是B中的元素时，e是C中的一个元素。
集合用有序链表实现，用一个空链表表示一个空集合，表示非空集合的链表根据元素之值按递增排列，执行C=A-B之后，表示集合A和B的链表不变，若结果集合C非空，则表示它的链表应根据元素之值按递增序排列。
函数append（）用于在链表中添加结点。
#include<
stdio.h>
#defineNULL0typedefstructnode{
}NODE;
NODE*append（NODE*last,intx）{
last->
next=（NODE*）malloc（sizeof（NODE））;
last->
next->
data=x;
return（last->
next）;
NODE*difference（NODE*A,NODE*B）{NODE*C,*last;
C=last=（NODE*）malloc（sizeof（NODE））;
while（
（1））
if（A->
data<
B->
data）{last=append（last,A->
A=A->
}else
if（
（2））{
A=A->
B=B->
while（（4））{last=append（last,A->
last=C;
C=C->
free（last）;
return（C）;
（1）A!
B!
=NULL
（2）A->
data==B->
data（3）B=B->
（4）A!
（5）last->
next=NULL;
12.阅读以下算法，填充空格，使其成为完整的算法。
其功能是在一个非递减的顺序存储线性表中（从下标1处开始存储），删除所有值相等的多余元素。
#defineMAXSIZE30typedefstruct{
intelem[MAXSIZE];
intlength;
/*表长*/
}sqlisttype;
voidexam21（sqlisttype*L）{intI,j;
I=2,j=1;
while（
（1））{
if（L->
elem[I]<
>
L->
elem[j]）{
I++;
（4）;
（1）i<
=L->
length
（2）
（3）j++;
（4）
13.用单链表表示的链式队列的队头在链表的A 位置。
A.链头 B.链尾 C.链中
14.若用单链表表示队列，则应该选用B 。
A.带尾指针的非循环链表 B.带尾指针的循环链表C.带头指针的非循环链表 D.带头指针的循环链表
15.在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主
机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印，先放入打印缓冲区的数据先被打印。
该缓冲区应该是一个B 结构。
A.堆栈 B.队列
C.数组 D.线性表
16.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。
当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为B 。
A.1和5 B.2和4
C.4和2 D.5和1
17.设栈的输入序列为1,2，„,10，输出序列为a1,a2,„,a10，若a5=10，则a7为C 。
A.4 B.8 C.不确定 D.7
18.设栈的输入序列是1,2,3,4，则D 不可能是其出栈序列。
A．1243 B.2134 C.1432 D.4312
19.以下D 是C语言中”abcd321ABCD”的子串。
A.abcd B.321AB C.“abcABC” D.“21AB”
20.若串S=”software”，其子串的数目是C 。
A.8 B.37 C.36 D.9
21.将一个A[1:
100,1:
100]的三对角矩阵，按行优先存入一维数组B[1:
298]中，A中元素
A66,65（即该元素的下标）在B数组中位置k为B 。
A.198 B.195 C.197 D.196
22.设高为h的二叉树只有度为0和2的结点，则此类二叉树的结点数至少为B，至多为F。
高为h的完全二叉树的结点数至少为E，至多为F。
A．2h B.2h-1C.2h+1 D.h+1
E.2h-1 F.2h-1 G.2h+1-1 H.2h+1
23.一棵有124个叶结点的完全二叉树，最多有B 个结点。
A.247 B.248 C.249 D.251
24.若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉
树是C 。
A.满二叉树 B.哈夫曼树
C.堆 D.二叉查找树
25.前序遍历和中序遍历结果相同的二叉树为F ；
前序遍历和后序遍历结果相同的二叉树为B 。
A.一般二叉树 B.只有根结点的二叉树
C.根结点无左孩子的二叉树 D.根结点无右孩子的二叉树
E.所有结点只有左孩子的二叉树 F.所有结点只有右孩子的二叉树
26.具有n个结点的完全二叉树，已经顺序存储在一维数组A[1..n]中，下面的算法是将A中顺序存储变为二叉链表存储的完全二叉树。
请填写适当语句在下面的空格内，完成上述算法。
#defineMAXSIZE30typedefstructbtnode{
structbtnode*lchild,*rchild;
}BTN;
voidcreatetree（BTN*p,intA[],intI,intn）{
data=A[I];
if（
（2））
（3）;
else
lchild=NULL;
if（（4））
createtree（（5））;
rchild=NULL;
voidbtree（BTN*p,intA[],intn）{createtree（p,A,1,n）;
（1）p=（BTN*）malloc（sizeof（BTN））
（2）2*I<
=n
（3）createtree（p->
lchild,A,2*I,n）（4）2*I+1<
（5）p->
rchild,A,2*I+1,n
27.若在线性表中采用折半查找法查找元素，该线性表应该C 。
A.元素按值有序 B.采用顺序存储结构
C.元素按值有序，且采用顺序存储结构D.元素按值有序，且采用链式存储结构
28.在分块检索中，对256个元素的线性表分成16 块最好，每块的最佳长度是
16 ；
若每块的长度为8，其平均检索长度为21 。
29.假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要
进行D
A.K-1次
次探测。
B.K次
C.K+1次
D.K（K+1）/2次
30.在n个记录的有序顺序表中进行折半查找，最大的比较次数是log2n 1。
31.Hash技术广泛应用于查找过程，选择Hash函数的标准是 和 。
处理冲突的技术有优有劣，其共同标准是 。
32.在下述排序算法中，所需辅助存储空间最多的是B ，所需辅助存储空间最小
的是C ，平均速度最快的是A 。
A.快速排序 B.归并排序 C.堆排序
33.在文件局部有序或文件长度较小的情况下，最佳内部排序的方法是A 。
A.直接插入排序 B.冒泡排序 C.简单选择排序
34.快速排序在最坏情况下时间复杂度是O（n2），比A 的性能差。
A.堆排序 B.冒泡排序 C.简单选择排序
35.若需在O（nlogn）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是C 。
A.快速排序 B.堆排序
C.归并排序 D.希尔排序
36.如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用
B 方法最快。
A.冒泡排序 B.快速排序
C.希尔排序 D.堆排序 E.简单选择排序
37.以下结点序列是堆的为A 。
A.100,90,80,60,85,75,20,25,10,70,65,50B.100,70,50,20,90,75,60,25,10,85,65,80
38.若要尽可能快地完成对实数数组的排序，且要求排序是稳定的，则应选C 。
39.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为A 排序法。
A.插入排序 B.交换排序
C.选择排序 D.归并排序
40.直接插入排序在最好情况下的时间复杂度为B 。
A.O（logn） B.O（n）
C.O（nlogn） D.O（n2）
41.下面函数是将任意序列调整为最大堆的算法，请将空白部分填上：
将任意序列调整为最大堆通过不断调用adjust函数，即for（i=n/2;
i>
0;
i--）adjust（list,i,n）;
其中list为待调整序列所在数组（从下标1开始），n为序列元素的个数。
voidadjust（intlist[],introot,intn）{
/*将以root为下标的对应元素作为待调整堆的根，待调整元素放在list数组中，最大元素下标为n*/
intchild,rootkey;
rootkey=
（1）;
child=2*root;
while（child<
n）{
if（（child<
n）&
（list[child]<
list[child+1]））
（2）;
if（rootkey>
list[child]）
break;
else{
list[（3）]=list[child];
list[（5）]=rootkey;
（1）list[root]
（2）child++;
（3）child/2
（4）child*=2;
（5）child/2
41.表是一种数据结构，链表是一种
（1） 。
队列和栈都是线性表，栈的操作特性是
（2） ，队列的操作特性是（3） 。
今有一空栈S，对下列待进栈的数据元素序列a,b,c,d,e,f依次进栈、进栈、出栈、进栈、进栈、出栈的操作，则此操作完成后，栈S的栈顶元素为（4） ，栈底元素为（5） 。
供选答案：
（1）:
A.非顺序存储线性表 B.非顺序存储非线性表C.顺序存储线性表 D.顺序存储非线性表
（2）:
A.随机进出 B.先进后出
C.先进先出 D.出优于进
（3）:
C.后进后出 D.进优于出
（4）:
A.f B.c
C.a D.b
（5）:
A.b B.c
C.a D.d
答案：
ABCBC
42.操作系统主要是对计算机系统全部
（1）进行管理，以方便用户、提高计算机使用效率的一种系统软件。
它的主要功能有：
处理机管理、存储管理、文件管理、
（2）管理和设备管理等。
Windows和Unix是最常用的两类操作系统。
前者是一个具有图形界面的窗口式的（3）系统软件，后者是一个基本上采用（4）语言编制而成的的系统软件。
在（5）操作系统控制下，计算机能及时处理由过程控制反馈的信息并作出响应。
（1）:
A.应用软件 B.系统软硬件
C.资源
D.设备
（2）:
A.数据
C.中断
B.作业
D.I/O
（3）:
A.分时C.多用户
A.PASCAL
B.多任务D.实时
B.宏
C.汇编
A.网络
D.C
B.分时
C.批处理
D.实时
CBBDD
43.本程序从键盘读入整数，并按从大到小的顺序输出输入整数中互不相等的那些整数。
程序一边读入整数，一边构造一个从大到小顺序链接的链表，直至不能从键盘读入整数，
然后顺序输出链表上各表元的整数值。
主函数每读入一个整数，就调用函数insert（），函
数insert（）将还未出现在链表上的整数按从大到小的顺序插入到链表中。
为了插入方便，链表在表首有一个辅助表元。
阅读下列C代码，在（n） 处填入相应的字句以完成上述功能。
#include<
malloc.h>
intval;
voidinsert（NODE*list,intx）{NODE*u,*v,*p;
u=list;
v=u->
while（
（1）&
x<
v->
val）{ /*寻找插入位置*/u=v;
v=u->
if（（v==NULL||
（2））{ /*判断是否要插入表元*/p=（NODE*）malloc（sizeof（NODE））;
val=x;
/*生成新表元*/
（3）=v;
（4）=p;
/* 插入新表元*/
main（）{
intx;
NODE*head,*p;
/*首先建立只有辅助表元的空链表*/head=（NODE
升级会员 