《计算机软件技术基础》试题答案

《计算机软件技术基础》试题

1.线性表的链式存储结构与顺序存储结构相比优点是CD。

A。所有的操作算法实现简单B。便于随机存取

C.便于插入和删除D.便于利用零散的存储器空间

2。线性表是具有n个C的有限序列。

A。表元素B.字符C。数据元素

D。数据项E。信息项

3.若长度为n的线性表采用顺序存储结构,在其第I个位置插入一个新元素的算法的时间复

杂度为C.（1≤I≤n+1）

A。O（0)B。O(1)

C。O（n）D.O(n2)

4.设A是一个线性表（a,a,…，a），采用顺序存储结构，则在等概率的前提下，平均每插

12n

入一个元素需要移动的元素个数为B，平均每删除一个元素需要移动的元素个数

为

2(ni)

A；若元素插在a与a之间（0≤I≤n—1)的概率为,则平均每插入一

ii+1n(n1)

个元素所要移动的元素个数为C;

n1n

A.B。

22

2n13n1

C.D.

34

5。下列函数中，按它们在n时的无穷大阶数，最大的是D。

A.lognB。nlogn

C。2n/2D。n!

6.将下图所示的s所指结点加到p所指的结点之后，其语句应为：D。

nextnext

p

s

next

A。s—〉next=p+1;p-〉next=s；

B。(＊p)。next=s；(＊s）.next=(*p）.next;

C。s->next=p—>next；p—〉next=s—>next;

D.s—>next=p->next;p—>next=s；

7。将两个各有n个元素的有序表归并为一个有序表时，其最少的比较次数是A.

A.nB。2n-1

C。n-1D.2n

8。下面的程序段是合并两个无头结点链表(ha和hb）为一个无头结点链表ha的过程，作

为参数的两个链表都是按结点的data域由大到小链接的。合并后新链表的结点仍按此方式

链接。请填写下述空框,使程序能正确运行。

#defineNULL0

typedefstructnode｛

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—〉next;

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中所有元素(a,a,…,a)与表B的一个顺序子表（b,b,…b)完全相同(即

12nkk+1k+n—1

a=b,a=b,…a=b），则称表A包含在表B中。设ha,hb为带头结点的单链表，分别表

1k2k+1nk+n—1

示有序表A和B，下面的函数用于判别表A是否包含在表B中，若是，则返回true，否则返

回false。（提示：用递归实现）

＃definetrue1

#definefalse0

＃defineNULL0

typedefstructnode{

intdata；

structnode*next；

}node，linklisttype；

intinclusion（linklisttype＊ha，linklisttype＊hb){

linklisttype＊pa,*pb；

pa=ha—〉next；

pb=hb—〉next;

（1)；

while（(2))

if（pa—〉data=pb->data）(3)；

else(4)；

(5);

｝

参考答案：

(1)if(pa==NULL)return(true)

(2)pb！=NULL＆＆pa->data>=pb-〉data

（3)return(inclusion（pa，pb））

（4)pb=pb-〉next;

(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.请在空框处填

上适当内容，每框只填一个语句.

＃defineNULL0

typedefstructnode｛

intdata;

structnode＊next；

}node，linklisttype；

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）;

}

p->data=n;

(3）；/＊建立从尾链到首的环形结构*/

｝

return（head);

}

voidJosephus(intn,intj,intm)｛

linklisttype＊p，*q；

intj；

p=create_link_list(n）;

for(;I〉1;I--）p=p->next；

(4）;

while（j<n）{

for（I=1；I<=m—1；I++)p=p—〉next;

(5）；

printf(“％8d”，q->data);

（6)；

free（q);

j=j+1；

}

}

参考答案:

(1)p—>next=q；

(2)p=q；

(3）p-〉next=head

(4)j=0

（5）q=p->next;

(6)p—〉next=q—〉next

11。在下列程序中，函数difference(A,B）用于求两集合之差C=A—B，即当且仅当e是A

中的一个元素，且不是B中的元素时，e是C中的一个元素。集合用有序链表实现，用一个

空链表表示一个空集合,表示非空集合的链表根据元素之值按递增排列，执行C=A—B之后,

表示集合A和B的链表不变，若结果集合C非空，则表示它的链表应根据元素之值按递增序

排列。函数append（）用于在链表中添加结点.

#include<stdio。h〉

#defineNULL0

typedefstructnode{

intdata;

structnode*next;

}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-〉data)；

A=A-〉next；

｝

else

if((2））｛

A=A-〉next;

B=B—〉next;

}

else

（3）;

while((4）)｛

last=append(last,A->data）；

A=A->next；

｝

（5）；

last=C;

C=C->next;

free(last）；

return(C）;

}

参考答案:

（1)A!=NULL＆B！=NULL

（2）A—〉data==B—>data

(3）B=B-〉next;

（4）A!=NULL

(5）last->next=NULL；

12。阅读以下算法，填充空格,使其成为完整的算法。其功能是在一个非递减的顺序存储线

性表中（从下标1处开始存储）,删除所有值相等的多余元素。

＃defineMAXSIZE30

typedefstruct{

intelem［MAXSIZE]；

intlength;/＊表长＊/

}sqlisttype；

voidexam21(sqlisttype*L)｛

intI，j；

I=2,j=1；

while（(1）)｛

if（L-〉elem[I］〈>L—>elem［j]){

（2）;

(3）；

}

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和5B。2和4

C.4和2D.5和1

17.设栈的输入序列为1，2，…，10，输出序列为a，a,…，a，若a=10,则a为C。

121057

A。4B。8C.不确定D.7

18.设栈的输入序列是1，2,3，4,则D不可能是其出栈序列。

A．1243B。2134C。1432D。4312

19.以下D是C语言中"abcd321ABCD”的子串。

A。abcdB.321ABC.“abcABC”D.“21AB”

20.若串S=”software”，其子串的数目是C。

A。8B。37C。36D。9

21.将一个A［1：100,1:100]的三对角矩阵，按行优先存入一维数组B［1：298]中，A中元

素A66,65(即该元素的下标）在B数组中位置k为B。

A.198B.195C.197D。196

22.设高为h的二叉树只有度为0和2的结点，则此类二叉树的结点数至少为B,

至多为F。高为h的完全二叉树的结点数至少为E，至多为F。

A．2hB.2h-1C.2h+1D。h+1

E.2h—1F.2h-1G.2h+1-1H.2h+1

23.一棵有124个叶结点的完全二叉树，最多有B个结点。

A。247B。248C。249D.251

24。若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉

树是C。

A。满二叉树B。哈夫曼树

C。堆D。二叉查找树

25。前序遍历和中序遍历结果相同的二叉树为F；前序遍历和后序遍历结果相同

的二叉树为B。

A.一般二叉树B。只有根结点的二叉树

C.根结点无左孩子的二叉树D。根结点无右孩子的二叉树

E.所有结点只有左孩子的二叉树F。所有结点只有右孩子的二叉树

26.具有n个结点的完全二叉树,已经顺序存储在一维数组A［1..n]中，下面的算法是将A

中顺序存储变为二叉链表存储的完全二叉树。请填写适当语句在下面的空格内,完成上述算

法.

＃defineMAXSIZE30

typedefstructbtnode｛

intdata；

structbtnode*lchild，＊rchild；

｝BTN；

voidcreatetree（BTN＊p,intA[］,intI，intn)｛

（1）;

p—>data=A［I]；

if（（2))

（3)；

else

p-〉lchild=NULL；

if(（4))

createtree((5)）;

else

p—〉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〈=n

(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个记录的有序顺序表中进行折半查找，最大的比较次数是logn1。

2

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，50

B.100,70,50，20，90,75,60，25，10，85，65,80

38.若要尽可能快地完成对实数数组的排序，且要求排序是稳定的，则应选C。

A.快速排序B。堆排序

C。归并排序D.希尔排序

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］;

（4)；

｝

}

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）：A.随机进出B.先进后出

C.后进后出D。进优于出

（4)：A。fB。c

C.aD。b

（5）:A.bB.c

C。aD.d

答案：ABCBC

42。操作系统主要是对计算机系统全部（1)进行管理，以方便用户、提高计算

机使用效率的一种系统软件。它的主要功能有：处理机管理、存储管理、文件管理、(2）

管理和设备管理等。Windows和Unix是最常用的两类操作系统。前者是一个具有图形界面

的窗口式的（3)系统软件,后者是一个基本上采用(4)语言编制而成

的的系统软件。在（5）操作系统控制下，计算机能及时处理由过程控制反馈的

信息并作出响应。

供选答案：

(1）：A.应用软件B.系统软硬件

C。资源D。设备

(2):A。数据B。作业

C.中断D.I/O

(3):A.分时B.多任务

C.多用户D。实时

(4）:A。PASCALB.宏

C。汇编D.C

（5）:A.网络B.分时

C.批处理D.实时

答案:CBBDD

43.本程序从键盘读入整数,并按从大到小的顺序输出输入整数中互不相等的那些整数。

程序一边读入整数，一边构造一个从大到小顺序链接的链表，直至不能从键盘读入整数，

然后顺序输出链表上各表元的整数值。主函数每读入一个整数,就调用函数insert（),函数

insert（）将还未出现在链表上的整数按从大到小的顺序插入到链表中。

为了插入方便，链表在表首有一个辅助表元。

阅读下列C代码,在（n）处填入相应的字句以完成上述功能.

＃include<stdio.h〉

＃include〈malloc。h〉

＃defineNULL0

typedefstructnode｛

intval;

structnode＊next；

}NODE；

voidinsert（NODE＊list,intx)｛

NODE＊u,＊v，＊p;

u=list;v=u—〉next;

while((1)＆&x〈v—〉val){/*寻找插入位置＊/

u=v;v=u->next;

}

if((v==NULL|｜（2)）｛/＊判断是否要插入表元*/

p=(NODE＊）malloc（sizeof(NODE）);

p->val=x；/*生成新表元＊/

（3）=v;（4）=p；/＊插入新表元*/

｝

}

main（）｛

intx;

NODE*head,*p;

/*首先建立只有辅助表元的空链表*/

head=(NODE＊)malloc（sizeof(NODE)）;

(5）=NULL;

printf(“EnterIntegers：\n”）；

while（scanf（“％d”,＆x）==1)/*反复读入整数插入链表*/

insert（head,x）;

for(p=head->next;p！=NULL;p=p->next)/＊输出链表＊/

printf(“%d\t”,p-〉val);

printf(“\n”）；

}

答案:

（1)v!=NULL或v

(2)x>v->val或x！=v—〉val

(3）p->next

(4）u—>next

（5）head->next

44.计算机数据处理的对象是具有不同结构的各种数据，可以访问的最小数据信息单位是

(1)，可以引用的最小命名数据单位是(2）。

线性表是最简单的一种数据结构，有顺序和链接两种存储方式。线性表按链接方式存储

时，每个结点的包括(3）两部分。

线性表的查找有（4）和(5）两种，但(5)只能用

于顺序存储的情况。

供选答案：

(1）:A.数字B.字符

C.数据元素D。数据项

（2):A.结点B。记录

C.数据元素D。数据项

（3）:A。数据值与符号B.数据与指针

C.数据与表名D.头地址与尾地址

(4):A。随机查找B.顺序查找

C.二分法查找D.浏览

(5)：A。随机查找B.顺序查找

C.二分法查找D。浏览

答案：CDBBC

45.本程序用于从链盘读入整数，插入到链表，或从链表删除一个整数。

阅读下面的C代码，将应填入（n)处的字名写在答卷的对应栏内。

#include〈stdio。h>

＃include〈malloc。h>

typedefstructnode{

intval;

structnode*next;

｝NODE；

NODE*ins(NODE＊list，intx）｛/＊将x按从小到大的次序插入链表＊/

NODE＊u,*v=list,*p；

for（;v!=NULL&&x〈v-〉val;v=v—〉next);/＊寻找插入位置＊/

if（v!=NULL&&x==v->val)return(list）；/＊已有，被忽略＊/

p=(NODE*）malloc(sizeof(NODE));p—>val=x；/*生成新表元*/

if（v==list)list=p；

else（1)；

（2）；

returnlist；

}

NODE＊del（NODE＊list，intx）{/＊从链表中删除值为x的表元*/

NODE＊u，＊v;

for(v=list;v！=NULL＆＆x〈v-〉valu；u=v;v=v—>next);

if（v!=NULL＆&x==v->val）｛/*找到值为x的表元＊/

if（v==list）list=list—〉next；

else（3);

(4)；/*释放空间＊/

}

elseprintf(“没有找到!\n”）;

return（list);

｝

main(）｛

intx，ans;

NODE＊list=NULL,*p;

while（1）｛

printf(“\n输入1：将整数插入到链表。\n输入2：从链表删除一个整数。\n”)；

printf（“其它整数，结束程序。\n\t请输入选择!”)；

scanf(%d,＆ans）;

if（(5))return;

printf（“输入整数:”)；scanf（“％d",＆x)；

if(ans==1)list=ins（list,x)；

elselist=del(list,x);

for(p=list;p！=NULL；p=p—>next)

printf(“%4d”，p->val)；

}

｝

答案:

(1)u—〉next=p；

(2)p-〉next=v

(3)u-〉next=v->next

(4)free(v）

（5)ans!=1&＆ans!=2

46.从未排序的序列中，依次取出元素，与已排序序列的元素比较后，放入已排序序列中的

恰当位置上，这是（1)排序。从未排序的序列中，挑选出元素，放在已排序序

列的某一端位置，这是(2)排序.逐次将待排序的序列中的相邻元素两两比较,

凡是逆序则进行交换，这是(3)排序。如果整个排序过程都在内存中进行，称为

（4)排序。排序算法的复杂性与排序算法的(5）有关。

供选答案：

(1)：A.选择B.插入

C。比较D。归并

(2):A。选择B.插入

C。比较D。归并

(3):A。冒泡B。交换

C。比较D.散列

（4)：A。外部B.内部

C.外存D.内存

(5）：A.运算量大小与占用存储多少

B.运算量大小与处理的数据量大小

C.并行处理能力和占用存储多少

D。占用存储多少和处理的数据量大小

答案：BAABA

47.操作系统是对计算机资源进行的(1）系统软件，是（2)的接口。

在处理机管理中，进程是一个重要的概念,它由程序块、（3)和数据块三部

分组成，它有3种基本状态,不可能发生的状态转换是（4)。

虚拟存储器的作用是允许程序直接访问比内存更大的地址空间,它通常使用(5）

作为它的一个主要组成部分.

供选答案：

(1)：A。输入和输出B。键盘操作

C.管理和控制D。汇编和执行

(2）:A.软件和硬件B。主机和外设

C.高级语言和机器语言D.用户和计算机

（3）:A。进程控制块B。作业控制块

C.文件控制块D。设备控制块

(4）:A.运行态转换为就绪态B.就绪态转换为运行态

C。运行态转换为等待态D.等待态转换为运行态

(5):A.软盘B。硬盘

C。CDROMD.寄存器

答案：CDADB

48。A是信息的载体,它能够被计算机识别、存储和加工处理.

A.数据B。数据元素C.结点D.数据项

49。下列程序段的时间复杂度为C。

for（i=1；i<n；i++)｛

y=y+1；

for（j=0；j<=（2＊n）;j++）x++；

｝

供选答案：

A。O(n-1）B.O(2n)C。O（n2）D.O(2n+1)

50。下面程序段的时间复杂度为D.

i=1；

while(i<=n）i=i*2；

供选答案：

A。O(1）B.O（n)C.O（n2)D。O(logn）

2

51。下面程序段的时间复杂度为B。

a=0;b=1;

for(i=2；i<=n;i++）｛

s=a+b；

b=a；

a=s;

｝

供选答案:

A。O(1）B.O（n)C。O（logn）D。

2

O(n2）

52。数据结构是一门研究非数值计算的程序设计问题中，计算机的A以及它们之

间的关系和运算等的学科。

A.操作对象B。计算方法C.逻辑存储D。数据映象

53。在数据结构中，从逻辑上可以把数据结构分成C。

A。动态结构和静态结构B。紧凑结构和非紧凑结构

C。线性结构和非线性结构D。内部结构和外部结构

54.算法分析的目的是C。

A.找出数据结构的合理性

B.研究算法中输入和输出的关系

C.分析算法的效率以求改进

D。分析算法的易懂性和文档性

55.算法分析的两个主要方面是(4）。

A。间复杂性和时间复杂性B。正确性和简明性

C。可读性和文档性D。数据复杂性和程序复杂性

56.一个线性顺序表第一个元素的存储地址是100,每个元素的长度为2，则第5个元素的地

址为B。

A.110B.108C.100D.120

57。若已知一个栈的入栈序列是1,2,3，…,n,其输出序列为P,P，P,…，P，若P=n,则

123n1

P为C。

i

A。iB.n—iC。n-i+1D。不确定

58。对于一个栈，给出输入项A，B,C。如果输入项序列由A,B,C所组成，则不可能产生的

输出序列是A。

A。CABB。CBAC.ABCD.ACB

59.设有如下的单链表的按序号查找的算法，其时间复杂度为B。

LinkNode*GetNode(Linklisthead，inti){

intj；

ListNode*p；

P=head；j=0;

while（p—>next&&j<i）{

p=p->next；

j++；

}

if（i==j)

return(p)；

else

return（NULL)；

｝

供选答案:

A.O（n2)B。O（2n)C。O(n3）D。O（logn）

60.二维数组A按行序为主顺序存放在内存中,每个数组元素占1个存储单元，则元素a

mnij

的地址计算公式是C。

A。LOC(a）=LOC(a）+[（i—1)*m+(j-1)］

ij11

B.LOC（a)=LOC（a)+[（j—1)＊m+(i-1)]

ij11

C.LOC（a）=LOC（a)+[(i-1）*n+(j-1)］

ij11

D。LOC(a）=LOC（a）+[(j-1）＊n+（i—1)］

ij11

61.以下哪一个不是队列的基本运算C。

A。从队尾插入一个新元素B。从队列中删除第i个元素

C.判断一个队列是否为空D。读取队头元素的值

62.在一个长度为n的顺序表中,向第i个元素之前插入一个新元素,需向后移动B个

元素.

A.n—iB。n-i+1C.n-i-1D.i

63.从一个长度为n的顺序表中删除第i个元素时，需向前移动A个元素。

A。n-iB。n—i+1C.n-i—1D。i

64。在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾

指针，则判断队空的条件是B。

A.front=rear+1B.front=rearC.front+1=rearD.front=0

65.从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平

均比较D个结点。

A。nB。n/2C。（n—1)/2D.(n+1)/2

66.一个栈的入栈序列是a,b，c,d,e，则栈不可能的输出序列是C。

A.edcbaB。decbaC。dceabD。abcde

67。栈结构通常采用的两种存储结构是A。

A.顺序存储结构和链表存储结构B。散列方式和索引方式

C.链表存储结构和数组D.线性存储结构和非线性存储结构

68。判断一个顺序栈ST(最多元素为mo）为空的条件是B。

A。ST—>top〈>0B.ST—>top=0C。st—〉top〈〉moD.st

—>top==mo

69.不带头结点的单链表head为空表的判定条件是A。

A.head==NILLB.head—〉next==NULLC.head—〉next==headD.head！=

NULL

70.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p和q之间插入s结

点，则应执行C。

A.s—〉next=p—〉next；p->next=s；

B。p-〉next=s—〉next；s—〉next=p;

C.q—>next=s;s—〉next=p;

D。p->next=s;s—〉next=q;

71。假设双向链表结点的类型如下：

typedefstructLinknode｛

intdata;

structLinknode＊lLink;/＊前驱结点指针＊/

structLinknode＊rLink；/＊后继结点指针＊/

}

下面给出的算法是要把一个q所指新结点，作为非空双向链表中的p所指的结点前驱结点插

入到该双向链表中,能正确完成要求的算法段是C。

A．q—〉rLink=p；q—>lLink=p-〉lLink;p->lLink=q;p—>lLink->rLink=q;

B.p->lLink=q,q—>rLink=p；p—〉lLink—〉rLink=q；q->lLink=p—>lLink;

C.q-〉lLink=p—>lLink；q-〉rLink=p;p—〉lLink—〉rLink=q;p-〉lLink=q;

D.以上均不对

72。串是一种特殊的线性表，其特殊性体现在B。

A。可以顺序存储B.数据元素是一个字符

C。可以链接存储D.数据元素可以是多个字符

73。设有两个串p和q，求q在p中首次出现的位置的运算称作B。

A。连接B.模式匹配C.求子串D。求串长

74.设串s1=”ABCDEFG”，s2=”PQRST”，函数con（x，y)返回x和y串的连接串,subs(s,I,j）

返回串s的从序号i的字符开始的j个字符组成的子串,len(s）返回串s的长度，则con(sub

（s1,2，len（s2)）,sub（s1，len(s2)，2）)的结果是D.

A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF

75。常对数组进行的两种基本操作是C。

A。建立和删除B.索引和修改C。查找和修改D.索引和查找

76.稀疏矩阵一般的压缩存储方法有两种，即Ｃ.

A.二维数组和三维数组B。三元组和散列

C。三元组和十字链表D。散列和十字链表

77。对下图所示的二叉表，按先根次序遍历得到的结点序列为B。

A.ABCDHEIFGB.ABDHIECFG

C.HDIBRAFCGD.HIDBEFGAC

78。在一棵二叉树上，度为0的结点个数为n,度为2的结点数为n，则n0=A。

02

A.n+1B。n—1

22

C。nD。n/2

22

79.某二叉树前序遍历结点的访问顺序是ABCDEFG,中序遍历结点的访问顺序是CBDAFGE，则

其后序遍历结点的访问顺序是A。

A．CDBGFEAB.CDGFEAB

C.CDBAGFED。CDBFAGE

80。在下列存储形式中,D不是树的存储形式。

A。双亲表示法B。孩子链表表示法

C。孩子兄弟表示法D.顺序存储表示法

81.已知一棵二叉树的中序序列为cbedahgijf,后序序列为cedbhjigfa，则该二叉树为

B。

82.已知一棵权集W=｛2，3,4，7,8,9}的哈夫曼树，其加权路径长度WPL为Ｃ。

A。20B.40C。80D.160

83。已知一棵度为m的树中有n个度为1的结点，n个度为2的结点，…,n个度为m的结

12m

点，问这棵树中叶子结点为Ｃ。

A.1+n（I-1）B。1+n（I+1)C。n+n+…+nD.m·n

ii12mm

84。如下图所示的4棵二叉树中，Ｃ不是完全二叉树。

85。设高度为h的二叉树上只有度为0或度为2的结点，则此类二叉树中所包含的结点数至

少为B。

A.2hB。2h-1C.2h+1D。h+1

86。如下图所示的二叉树的中序遍历序列是Ｃ。

A。abcdgefB.dfebagcC.dbaefcgD.defbagc

87.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，则其前序遍历序列为

D.

A。acbedB.decabC。deabcD.cedba

88。如果T2是由有序树T转换而来的二叉树,则T中结点的前序就是T2中结点的A.

A。前序B。中序C。后序D.层次序

89.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、

中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。下面

结论正确的是A。

A。树的先根遍历序列与其对应的二叉树的先序遍历序列相同

B。树的先根遍历序列与其对应的二叉树的后序遍历序列相同

C。树的先根遍历序列与其对应的二叉树的中序遍历序列相同

D.以上均不对

90。深度为5的二叉树至多有Ｃ个结点。

A。16B。32C.31D。10

91。在一非空二叉树的中序遍序序列中，根结点的右边A.

A.只有右子树的所有结点B.只有右子树的部分

C.只有左子树的部分结点D。只有左子树的所有结点

92.树最适合用来表示Ｃ。

A.有序数据元素B.无序数据元素

C.元素之间具有分支层次关系的数据D.元素之间无联系的数据

93.设n，m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是C。

A。n在m的右方B。n是m的祖先

C。n在m的左方D。n是m的子孙

94.对一个满二叉树，m个树叶,n个结点，深度为h,则D。

A。n=h+mB.h+m=2n

C。m=h-1D。n=2h—1

95。如果某二叉树的前序为stuwv,中序为uwtvs，则该二叉树后序为Ｃ。

A。uwvtsB。vwuts

C.wuvtsD。wutsv

96。设待排序的记录为(20,16，13，14，19），经过下列过程将这些记录排序。

20，16,13,14，19

16,20，13，14,19

13，16，20,14,19

13,14，16,20，19

13，14，16,19,20

所用的排序方法是A.

A.直接插入排序B.冒泡排序

C.希尔排序D。堆排序

97.对下列4个序列用快速排序的方法进行排序，以序列的第一个元素为基础进行划分，在

第一趟划分过程中，元素移动次数最多的是A序列。

A.70,75，82，90,23,16,10，68

B。70，75,68,23，10，16,90,82

C。82,75,70,16,10，90,68,23

D。23,10,16,70，82，75,68,90

98。用快速排序的方法对包含几个关