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

1、计算机软件技术基础1 .线性表的链式存储结构与顺序存储结构相比优点是CD。A.所有的操作算法实现简单B.便于随机存取C.便于插入和删除D.便于利用零散的存储器空间2 .线性表是具有n个C的有限序列。A.表元素B.字符C.数据元素D.数据项E.信息项3 .若长度为n的线性表采用顺序存储结构，在其第I个位置插入一个新元素的算法的时间复杂度为C。(KI<n+1)A.O(0)B.O(1)C.O(n)D.O(n2)4.设A是一个线性表(ai,a2,an),采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为B,平均每删除一个元素需要移动的元素个数为A;若元素插在a与ai+i

2、之间(0wIwn-1)的概率为2mi),则平均每插入一个n(n1)元素所要移动的元素个数为A. U2P 2n 1C.35.下列函数中，按它们在A. log nn/2C. 2B.D.23n 14时的无穷大阶数，最大的是B. nlog nD. n!6 .将下图所示的s所指结点加到p所指的结点之后，其语句应为：DA. 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->ne

3、xt=s;7 .将两个各有n个元素的有序表归并为一个有序表时，其最少的比较次数是A。A.nB.2n-1C.n-1D.2n8.下面的程序段是合并两个无头结点链表(ha和hb)为一个无头结点链表ha的过程，作为参数的两个链表都是按结点的data域由大到小链接的。合并后新链表的结点仍按此方式链接。请填写下述空框，使程序能正确运行。#defineNULL0typedefstructnodeintdata;structnode*next;node,linklisttype;voidcombine(linklisttype*ha,linklisttype*hb)linklisttype*h,*p;h=(l

4、inklisttype*)malloc(sizeof(linklisttype);h->next=NULL;p=h;while(ha!=NULL&&hb!=NULL)if(ha->data>=hb->data)p->next=；p=(2);；elsep->next=(4);p=；(6);if(ha=NULL)；if(hb=NULL)(8);ha=h->next;free(h);参考答案：(1)ha(2)p->next(4)hb(5)p->next(7)p->next=hb9.如果表A中所有元素(a1,a2,an)与表/

5、*较大的元素先插入*/(3) ha=ha->next(6) hb=hb->next(8) p->next=haB的一个顺序子表(b k,b k+1, -力k+n-1)完全相同(即a1=bk,a2=bk+1,an=bk+n-1）,则称表A包含在表B中。设ha,hb为带头结点的单链表,分别表示有序表A和B,下面的函数用于判别表A是否包含在表B中，若是，则返回true,否则返回false。（提示：用递归实现）#definetrue1#definefalse0#defineNULL0typedefstructnodeintdata;structnode*next;node,linkl

6、isttype;intinclusion(linklisttype*ha,linklisttype*hb)linklisttype*pa,*pb;pa=ha->next;pb=hb->next;；while(2)if(pa->data=pb->data)(3);else(4);；参考答案：(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.在本

7、题的程序中，函数create_link_list(n)建立一个具有n个结点的循环链表；函数josephus(n,I,m)对由create_link_list(n)所建立的具有n个结点的循环链表按一定的次序逐个输出，并删除链表中的所有结点。参数n(n>0)指明循环链表的结点个数，参数I(1wIwn)指明起始结点，参数m(m>0是步长)，指明从起始结点或前次被删除并输出的结点之后的第m个结点作为本次被输出并删除的结点。例如，对于下图所示的具有6个结点的循环链表，在调用josephus(6,3,2)后，将输出5,1,3,6,4,2。请在空框处填上适当内容，每框只填一个语句。#define

8、NULL0typedefstructnodeintdata;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(linkl

9、istttype);；p->data=n;/*建立从尾链到首的环形结构*/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=h

10、ead(4) j=0(5) q=p->next;(6) p->next=q->next11.在下列程序中，函数difference(A,B)用于求两集合之差C=A-B,即当且仅当e是A中的一个元素，且不是B中的元素时，e是C中的一个元素。集合用有序链表实现，用一个空链表表示一个空集合，表示非空集合的链表根据元素之值按递增排列，执行C=A-B之后，表示集合A和B的链表不变，若结果集合C非空，则表示它的链表应根据元素之值按递增序排列。函数append()用于在链表中添加结点。#include<stdio.h>#defineNULL0typedefstructnodei

11、ntdata;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()if(A->data<B->data)last=append(last,A->data);A=A->next;els

12、eif(2)A=A->next;B=B->next;else；while()last=append(last,A->data);A=A->next;；last=C;C=C->next;free(last);return(C);参考答案：(1) A!=NULL&B!=NULL(2) A->data=B->dataB=B->next;(4) A!=NULL(5) last->next=NULL;12.阅读以下算法，填充空格，使其成为完整的算法。其功能是在一个非递减的顺序存储线性表中(从下标1处开始存储)，删除所有值相等的多余元素。#de

13、fineMAXSIZE30typedefstructintelemMAXSIZE;intlength;/*表长*/sqlisttype;voidexam21(sqlisttype*L)intI,j;I=2,j=1;while(儿if(L->elemI<>L->elemj)(2)；I+；(4)；参考答案：(1) i<=L->length(2)j+；(4)13 .用单链表表示的链式队列的队头在链表的A位置。A.链头B.链尾C.链中14 .若用单链表表示队列，则应该选用B。A.带尾指针的非循环链表B.带尾指针的循环链表C.带头指针的非循环链表D.带头指针的循环链表

14、15 .在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印，先放入打印缓冲区的数据先被打印。该缓冲区应该是一个B结构。A.堆栈B.队列C.数组D.线性表16 .若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为B。A.1和5C.4和217.设栈的输入序列为1,2,10,B.2和4D.5和1输出序列为a1,a2,a10,若a5=10,则a7为C。A.418.设栈的输入序列是B.81,2,3,4,则DC

15、.不确定D.7/、可能是其出栈序列。A.124319.以下DB.2134是C语言中”C.1432abcd321ABCD的子串。D.4312A.abcdB.321AB20.右-串S=software,其子串的数目是C."abcABCC。D.“21A甘A.8B.3721.将一个A1:100,1:100的三对角矩阵,A66,65(即该元素的下标)在B数组中位置C.36按行优先存入一维数组k为B。D.9B1:298中，A中元素A.198B.195C.197D.19622.设局为h的二叉树只有度为0和2的结点，则此类二叉树的结点数至少为B,至多为F。高为h的完全二叉树的结点数至少为E,至多为F

16、。A.2hB.2h-1C.2h+1D.h+1E.2h-1F.2h-1G.2h+1-1H.2h+123.一棵有124个叶结点的完全二叉树，最多后_B个结点。A.247B.248C.249D.25124 .若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是C。A.满二叉树B.哈夫曼树C.堆D.二叉查找树25 .前序遍历和中序遍历结果相同的二叉树为F;前序遍历和后序遍历结果相同的二叉树为B。A.一般二叉树B.只有根结点的二叉树C.根结点无左孩子的二叉树D.根结点无右孩子的二叉树E.所有结点只有左孩子的二叉树F.所有结点只有右孩子的二叉树26 .具有n个结点的完全二叉树，

17、已经顺序存储在一维数组A1.n中，下面的算法是将A中顺序存储变为二叉链表存储的完全二叉树。请填写适当语句在下面的空格内，完成上述算法。#defineMAXSIZE30typedefstructbtnodeintdata;structbtnode*lchild,*rchild;BTN;voidcreatetree(BTN*p,intA,intI,intn)；p->data=AI;if()；elsep->lchild=NULL;if()createtree(5);elsep->rchild=NULL;voidbtree(BTN*p,intA,intn)createtree(p,A

18、,1,n);参考答案：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,n27 .若在线性表中采用折半查找法查找元素，该线性表应该C。A.元素按值有序B.采用顺序存储结构C.元素按值有序，且采用顺序存储结构D.元素按值有序，且采用链式存储结构28 .在分块检索中，对256个元素的线性表分成6块最好，每块的最佳长度是16;若每块的长度为8,其平均检索长度为21。29 .假定有K个关键字互为同义词，若用线性探测法把这K个

19、关键字存入散列表中，至少要进行D次探测。A.K-1次B.K次C.K+1次D.K(K+1)/2次30 .在n个记录的有序顺序表中进行折半查找，最大的比较次数是log2n1。31 .Hash技术广泛应用于查找过程，选择Hash函数的标准是和处理冲突的技术有优有劣，其共同标准是。32 .在下述排序算法中，所需辅助存储空间最多的是B,所需辅助存储空间最小的是C,平均速度最快的是A。A.快速排序B.归并排序C.堆排序33 .在文件局部有序或文件长度较小的情况下，最佳内部排序的方法是A。A.直接插入排序B.冒泡排序C.简单选择排序34 .快速排序在最坏情况下时间复杂度是O(n2),比A的性能差。A.堆排序

20、B.冒泡排序C.简单选择排序35 .若需在O(nlogn)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是C。A.快速排序B.堆排序C.归并排序D.希尔排序36 .如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用B方法最快oA.冒泡排序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,8038 .若要尽可能快地完成对实数数组的排序，且要求排序是稳定的，则应选CA.快速排序

21、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为序列元素的个数。voidad

22、just(intlist,introot,intn)/*将以root为下标的对应元素作为待调整堆的根，待调整元素放在list数组中，最大元素下标为n*/intchild,rootkey;rootkey=；child=2*root;while(child<n)if(child<n)&&(listchild<listchild+1)(2)；if(rootkey>listchild)break;elselist(3)=listchild;(4);list(5)=rootkey;参考答案：(1) listroot(2) child+;child/2(4) chi

23、ld*=2;child/241.表是一种数据结构，链表是一种(1)。队列和栈都是线性表，栈的操作特性是(2),队列的操作特性是。今有一空栈S,对下列待进栈的数据元素序列a,b,c,d,e,f依次进栈、进栈、出栈、进栈、进栈、出栈的操作，则此操作完成后，栈S的栈顶元素为(4),栈底元素为(5)。供选答案：(1):A.非顺序存储线性表C.顺序存储线性表B.D.非顺序存储非线性表顺序存储非线性表(2)：A.随机进出B.先进后出C.先进先出D.出优于进(3)：A.随机进出B.先进后出C.后进后出D.进优于出(4)：A.fB.cC.aD.b(5)：A.bB.cC.aD.d答案：ABCBC42.操作系统主

24、要是对计算机系统全部(1)进行管理，以方便用户、提高计算机使用效率的一种系统软件。它的主要功能有：处理机管理、存储管理、文件管理、'理和设备管理等。Windows和Unix是最常用的两类操作系统。前者是一个具有图形界面的窗口式的(3)系统软件，后者是一个基本上采用(4)语言编制而成的的系统软件。在(5)操作系统控制下，计算机能及时处理由过程控制反馈的信息并作出响应。供选答案：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.实时

25、答案：CBBDD43.本程序从键盘读入整数，并按从大到小的顺序输出输入整数中互不相等的那些整数。程序一边读入整数，一边构造一个从大到小顺序链接的链表，直至不能从键盘读入整数，然后顺序输出链表上各表元的整数值。主函数每读入一个整数，就调用函数insert(),函数insert()将还未出现在链表上的整数按从大到小的顺序插入到链表中。为了插入方便，链表在表首有一个辅助表元。阅读下列C代码，在(n)处填入相应的字句以完成上述功能。#include<stdio.h>#include<malloc.h>#defineNULL0typedefstructnodeintval;str

26、uctnode*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;=v；(4)=p;/*main()intx;NODE*head,*p;/*首先建立只有辅助表元的空链表*/head=(NODE*)malloc(sizeof(NOD

27、E);(5)=NULL;printf("Ente门ntegers:n");while(scanf("%d,&x)=1)/*反复读入整数插入链表*/insert(head,x);for(p=head->next;p!=NULL;p=p->next)/*输出链表*/printf("%dt",p->val);printf("n”);答案：(1) v!=NULL或v(2) x>v->val或x!=v->val(3) p->next(4) u->next(5) head->next4

28、4 .计算机数据处理的对象是具有不同结构的各种数据，可以访问的最小数据信息单位是(1),可以引用的最小命名数据单位是(2)。线性表是最简单的一种数据结构，有顺序和链接两种存储方式。线性表按链接方式存储时，每个结点的包括(3)两部分。线性表的查找有(4)和(5)两种，但(5)只能用于顺序存储的情况。供选答案：A.数字B.字符C.数据兀素D.数据项(2)：A.结点B.记录C.数据兀素D.数据项(3)：A.数据值与符号B.数据与指针C.数据与表名D.头地址与尾地址(4)：A.随机查找B.顺序查找C.二分法查找D.浏览(5)：A.随机查找B.顺序查找C.二分法查找D.浏览答案：CDBBC45 .本程序

29、用于从链盘读入整数，插入到链表，或从链表删除一个整数。阅读下面的C代码，将应填入(n)处的字名写在答卷的对应栏内。#include<stdio.h>#include<malloc.h>typedefstructnodeintval;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->va

30、l)return(list);/*已有，被忽略*/p=(NODE*)malloc(sizeof(NODE);p->val=x;/*生成新表元*/if(v=list)list=p;else；(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;els

31、e(3);；/*释放空间*/elseprintf("没有找到!n");return(list);main()intx,ans;NODE*list=NULL,*p;while(1)printf("n输入1：将整数插入到链表。n输入2：从链表删除一个整数。n");printf("其它整数，结束程序。nt请输入选择！”);scanf(%d,&ans);if(5)return;printf("输入整数：");scanf("%d,&x);if(ans=1)list=ins(list,x);elselist=d

32、el(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!=246 .从未排序的序列中，依次取出元素，与已排序序列的元素比较后，放入已排序序列中的恰当位置上，这是(1)排序。从未排序的序列中，挑选出元素，放在已排序序列的某一端位置，这是(2)排序。逐次将待排序的序列中的相邻元素两两比较，凡是逆序则进行交换，这是(

33、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.占用存储多少和处理的数据量大小答案：BAABA47 .操作系统是对计算机资源进行的(1)系统软件，是(2)的接口。在处理机管理中，进程是一个重要的概念，它由程序块、(3)和数据块三部分组成，它有3种基本状态，不可能发生的状态转换

34、是(4)。虚拟存储器的作用是允许程序直接访问比内存更大的地址空间，它通常使用作为它的一个主要组成部分。供选答案：(1):A.C.输入和输出管理和控制B.D.键盘操作汇编和执行(2):A.软件和硬件B.主机和外设C.Wj级语百和机器语百D.用户和计算机(3):A.进程控制块B.作业控制块C.文件控制块D.设备控制块(4):A.运行态转换为就绪态B.就绪态转换为运行态C.运行态转换为等待态D.等待态转换为运行态(5):A.软盘B.硬盘C.CDROMD.寄存器答案：CDADB48 .A是信息的载体，它能够被计算机识别、存储和加工处理。A.数据B.数据元素C.结点D.数据项49 .下列程序段的时间复杂

35、度为C。for(i=1;i<n;i+)y=y+i;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(log2n)51 .下面程序段的时间复杂度为B。a=0;b=1;for(i=2;i<=n;i+)s=a+b;b=a;a=s;D. O(n 2)A 以及它们之D.数据映象供选答案：A.O(1)B.O(n)C.O(log2n)52 .数据结构是一门研究非数值计算的程序设计问题

36、中，计算机的间的关系和运算等的学科。A.操作对象B.计算方法C.逻辑存储53 .在数据结构中，从逻辑上可以把数据结构分成CA.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构54.算法分析的目的是C 。A.找出数据结构的合理性B.研究算法中输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性55 .算法分析的两个主要方面是 (4)A.间复杂性和时间复杂性D.内部结构和外部结构B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性56 .一个线性顺序表第一个元素的存储地址是100,每个元素的长度为 2,则第5个元素的地址为 B。A.110B.10857

37、.若已知一个栈的入栈序列是 为 C。A. iB. n-iC. 1001,2,3,n,其输出序列为C. n-i+1D. 120P1,P2,P3,，Pn,若 P = n,则 PD.不确定A,B,C所组成，则不可能产生的输D. ACBB。58 .对于一个栈，七出输入项A,B,C。如果输入项序列由出序列是A。A.CABB.CBAC.ABC59 .设有如下的单链表的按序号查找的算法，其时间复杂度为LinkNode*GetNode(Linklisthead,inti)intj;ListNode*p;P=head;j=0;while(p->next&&j<i)p=p->ne

38、xt;j+;if(i=j)return(p);elsereturn(NULL);供选答案:A. O(n 2)B. O(2n)C. O(n 3)60 .二维数组Amn按行序为主顺序存放在内存中，每个数组元素占D. O(logn)个存储单元，则元素aj的地址计算公式是A. LOC(a ij) = LOC(a B. LOC(a ij) = LOC(a C. LOC(a ij) = LOC(a D. LOC(a ij) = LOC(a11)+(i-1)*m+(j-1) n)+(j-1)*m+(i-1) 11)+(i-1)*n+(j-1) n)+(j-1)*n+(i-1)61 .以下哪一个不是队列的基本

39、运算A.从队尾插入一个新元素C.判断一个队列是否为空OB.从队列中删除第iD.读取队头元素的值个元素62 .在一个长度为n的顺序表中，向第i个元素之前插入一个新元素, 元素。需向后移动BA. n-iB. n-i+163 .从一个长度为n的顺序表中删除第A. n-iB. n-i+1C. n-i-1i个兀素时，需向前移动C. n-i-1D. i个元素。D. i64.在具有n个单元的顺序存储的循环队列中,假定front和rear分别为队首指针和队尾指针，则判断队空的条件是A. front=rear+165.从一个具有 均比较 DA. nB. front=rearn个结点的单链表中查找其值等于C. f

40、ront+1=rearx的结点时,D. front=0在查找成功的情况下，需平个结点。B. n/266 . 一个栈的入栈序列是 a,b,c,d,eA. edcbaB. decbaC. (n-1)/2,则栈不可能的输出序列是C.dceabD. (n+1)/2D. abcde67 .栈结构通常采用的两种存储结构是A.顺序存储结构和链表存储结构C.链表存储结构和数组68 .判断一个顺序栈ST (最多元素为B.散列方式和索引方式D.线性存储结构和非线性存储结构A. ST->top<>0B. ST->top=0m。为空的条件是 BC. st->top<>moD.

41、 st->top=mo69 .不带头结点的单链表head为空表的判定条件是A. head=NILLB.head->next=NULLC.head->next=headD.head!=NULL70 .在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p和q之间才1入s结点，则应执行CA. 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 .假设双向链表结点

42、的类型如下:typedefstructLinknodeintdata;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->

43、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的

44、字符开始的con(sub(s1,2,len(s2),sub(s1,len(s2),2)j个字符组成的子串，len(s)返回串s的长度，则A. BCDEFB. BCDEFG的结果是 DC. BCPQRSTD. BCDEFEF75 .常对数组进行的两种基本操作是A.建立和删除B.索引和修改CC.76 .稀疏矩阵一般的压缩存储方法有两种，即A.二维数组和三维数组B.C.三元组和十字链表D.O查找和修改CD.索引和查找三元组和散列散列和十字链表77 .对下图所示的二叉表，按先根次序遍历得到的结点序列为B. ABDHIECFGD. HIDBEFGACA.ABCDHEIFGC.HDIBRAFCG78 .在

45、一棵二叉树上，度为0的结点个数为n0,度为2的结点数为n2,则n0=A。A.n2+1B.n2-1C.n2D.n2/279.某二叉树前序遍历结点的访问顺序是ABCDEFG中序遍历结点的访问顺序是CBDAFGE则其后序遍历结点的访问顺序是A。B. CDGFEABA.CDBGFEAC.CDBAGFED.CDBFAGE80 .在下列存储形式中，D不是树的存储形式。A.双亲表示法B.孩子链表表示法C.孩子兄弟表示法D.顺序存储表示法81 .已知一棵二叉树的中序序列为cbedahgijf,后序序列为cedbhjigfa,则该二叉树为B。82.已知一棵权集 W=2,3,4,7,8,9A.20B.40的哈夫曼

46、树，其加权路径长度WPL为C. 80D.16083 .已知一棵度为m的树中有m个度为1的结点，氏个度为2的结点，nm个度为m的结点，问这棵树中叶子结点为C。A.1+ni(I-1)B.1+ni(I+1)C.ni+n2+-+nmD.mnm84 .如下图所示的4棵二叉树中，C不是完全二叉树。85 .设高度为h的二叉树上只有度为0或度为2的结点，则此类二叉树中所包含的结点数至少为B。A.2hB.2h-1C.2h+1D.h+186 .如下图所示的二叉树的中序遍历序列是C。A.abcdgefB.dfebagcC.dbaefcgD.defbagc87 .已知某二叉树的后序遍历序列是dabec,中序遍历序列是

47、debac,则其前序遍历序列为D。A.acbedB.decabC.deabcD.cedba88 .如果T2是由有序树T转换而来的二叉树，则T中结点的前序就是T2中结点的A，A.前序B.中序C.后序D.层次序89 .树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。下面结论正确的是A。A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同B.树的先根遍历序列与其对应的二叉树的后序遍历序列相同C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同D.以上均不对90 .深度为5的二叉树至多有C个结

48、点。A.16B.32C.31D.1091 .在一非空二叉树的中序遍序序列中，根结点的右边A。A.只有右子树的所有结点B.只有右子树的部分C.只有左子树的部分结点D.只有左子树的所有结点92.树取适合用来去小C。A.有序数据兀素B.无序数据兀素C.兀素之间具有分支层次关系的数据D.兀素之间无联系的数据93.设n,m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是CA.n在m的右方B.n是m的祖先C.n在m的左方D.n是m的子孙94.对一个满二叉树，m个树叶，n个结点，深度为h,贝UD。A.n=h+mB.h+m=2nC.m=h-1D.n=2h-195.如果某二叉树的前序为stuwv,中序为

49、uwtvs,则该二叉树后序为CA.uwvtsB.vwutsC.wuvtsD.wutsv96 .设待排序的记录为(20,16,13,14,19),经过下列过程将这些记录排序。20,16,13,14,1916,20,13,14,1913,16,20,14,1913,14,16,20,1913,14,16,19,20所用的排序方法是A。A.直接插入排序B.冒泡排序C.希尔排序D.堆排序97 .对下列4个序列用快速排序的方法进行排序，以序列的第一个元素为基础进行划分，在第一趟划分过程中，元素移动次数最多的是序列。A.70,75,82,90,23,16,10,68B.70,75,68,23,10,16,

50、90,82C.82,75,70,16,10,90,68,23D.23,10,16,70,82,75,68,9098 .用快速排序的方法对包含几个关键字的序列进行排序，最坏情况下，执行的时间为D。A.O(n)B.O(log2n)C.O(nlog2n)D.O(n2)99 .在所有排序方法中，关键码(即关键字)比较的次数与记录的初始排列次序无关的是D。A.希尔排序B.冒泡排序C.直接插入排序D.直接选择排序100 .在归并排序过程中，需归并的趟数为C。A.nB.nC.nlog2nD.log2n101 .一组记录的排序代码为46,79,56,38,40,84,则利用堆排序的方法建立的初始堆为B。A.7

51、9,46,56,38,40,80B.84,79,56,38,40,46C.84,79,56,46,40,38D.84,56,79,40,46,38102 .一组记录的排序代码为46,79,56,38,40,84,则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为C。A.38,40,46,56,79,84B.40,38,46,79,56,84C.40,38,46,56,79,84D.40,38,46,84,56,79103 .每次把待排序的区间划分为左、右两个子区间，其中左区间中元素的排序码均小于等于基准元素的排序码，右区间中元素的排序码均大于等于基准元素的排序码，此种排序方法叫做B。

52、A.堆排序B.快速排序C.冒泡排序D.希尔排序104 .一组记录的排序码为一个字母序列Q,D,F,X,A,P,N,B,Y,M,C,W,按归并排序方法对该序列进行一趟归并后的结果为D。A. D,F,Q,X,A,B,N,P,C,M,W,YB. D,F,Q,A,P,X,B,N,Y,C,M,WC. D,Q,F,X,A,P,N,B,Y,M,C,WD. D,Q,F,X,A,P,B,N,M,Y,C,W105 .一组记录的排序码为25,48,16,35,79,82,23,40,36,72，其中，含有5个长度为2的有序表，按归并排序方法对该序列进行一趟归并后的结果为A。A.16,25,35,48,23,40,7

53、9,82,36,72B.16.25,35,48,79,82,23,36,40,72C.16,25,48,35,79,82,23,36,40,72D.16,25,35,48,79,23,36,40,72,82106 .设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用C排序法。B.快速排序A.冒泡排序C.堆排序D.希尔排序107 .在待排序的元素序列基本有序的前提下，效率最高的排序方法是A。A.插入排序B.选择排序C.快速排序D.归并排序108 .用某种排序方法对线性表25,84,21,47,15,27,68,35,20进行排序时，元素序列的变化情况如下：(1) 2

54、5,84,21,47,15,27,68,35,20(2) 20,15,21,25,47,27,68,35,84(3) 15,20,21,25,35,27,47,68,84(4) 15,20,21,25,27,35,47,68,84则所采用的排序方法是D。A.选择排序B.希尔排序C.归并排序D.快速排序109 .快速排序方法在C情况下最不利于发挥其长处。A.要排序的数据量太大B.要排序的数据中含有多个相同值C.要排序的数据已基本有序D.要排序的数据个数为整数110 .设有一个已按各元素的值排好序的线性表，长度大于2,对给定的值K,分别用顺序查找法和二分查找法查找一个与K相等的元素，比较的次数分别为s和bo在查找不成功的情况下，正确的s和b的数量关系是B。A.总有s=bB.总有s>bC.