《计算机软件技术基础》复习题(含答案)

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

2、动的元素个数为；若兀素插在ai与ai+i之间(0 w I w n-i)的概率为2(n - i),则平均每插入一个n(n 1)元素所要移动的元素个数为A.2c 2n 1C.3B.D.n23n 145.下列函数中，按它们在A. log nnT笛时的无穷大阶数，最大的是n/2C. 26.将下图所示的DnextnextnextB. nlog nD. n!s所指结点加到p所指的结点之后，其语句应为:A. s->next=p+1; p->next=s;B. (*p).next=s; (*s).next=(*p).next;C. s->next=p->next; p->next

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

4、ombine(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 = _(3)(2)elsep->next =(4);(5)；(8) if(ha=NULL) if(hb=NULL) ha

5、= h->next; free(h);参考答案ha(4) hb p->next=hb(2) p->next(5) p->next9.如果表中所有元素(ai,a2,an)与表(3) ha=ha->next(6) hb=hb->next(8) p->next=ha的一个顺序子表(b k,b k+i,b k+n-i)完全相同(即ai=bk,a2=bk+i,a n=bk+n-i),则称表A包含在表B中。设ha, hb为带头结点的单链表，分别表示有序表A和B,下面的函数用于判别表 A是否包含在表 B中，若是，则返回true ,否则返 回false 。(提示：用递

6、归实现)#define true i #define false 0#define NULL 0 typedef struct node int data;struct node *next;node, linklisttype;int inclusion(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) retu

7、rn(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 w I w n)指明起

8、始结点，参数m (m>0是步长)，指明从起始结点或前次被删除并输出的结点之后的第m个结点作为本次被输出并删除的结点。 例如，对于下图所示的具有 6个结点的循 环链表，在调用josephus(6,3,2) 后，将输出5,1,3,6,4,2。请在空框处填上适当内容，每框只填一个语句。#define NULL 0typedef struct nodeint data;struct node *next;node, linklisttype;linklisttype *create_link_list(int n)linklisttype *head, *p, *q;int I;head = N

9、ULL;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); ；p->data = n;；/*建立从尾链到首的环形结构*/return(head);void Josephus(int n, int j, int m) linklisttype *p, *q;int j；p = c

10、reate_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->next11.在下列程序中，函数difference(A,B)用于求两集合之差C

11、=A-B,即当且仅当e是A中的一个元素，且不是 B中的元素时，e是C中的一个元素。集合用有序链表实现，用一个空链 表表示一个空集合，表示非空集合的链表根据元素之值按递增排列，执行C=A-B之后，表示集合A和B的链表不变，若结果集合C非空，则表示它的链表应根据元素之值按递增序排列。 函数append()用于在链表中添加结点。#include <stdio.h>#define NULL 0typedef struct nodeint data;struct node *next;NODE;NODE *append(NODE *last, int x)last->next=(NOD

12、E *)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; else if( (2)A=A->next; B=B->next; else ； while( (4)last=

13、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->data B=B->next;(4) A!=NULL(5) last->next=NULL;12.阅读以下算法，填充空格，使其成为完整的算法。其功能是在一个非递减的顺序存储线 性表中(从下标1处开始存储)，删除所有值相等的多余元素。#define MAXSIZE 30 typedef structint elemM

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

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

16、5=10,则a7为C。A. 4B. 8C.不确定D.718 .设栈的输入序列是1,2,3,4 ,则 D不可能是其出栈序列。A. 1243B.2134C.1432D.431219.以下 D是C语言中" abcd321ABCD的子串。A. abcdB. 321ABC. "abcABCD.“21AB20.右用S= software ,其子串的数目是A. 8B. 37C。C. 36D.921.将一个 A1:100,1:100 的三对角矩阵,A66,65(即该元素的下标)在B数组中位置A.198B.195按行优先存入一维数组k 为 B。C. 197D.B1:29819622.设高为h

17、的二叉树只有度为 0和2的结点，则此类二叉树的结点数至少为B至多为 F 。高为h的完全二叉树的结点数至少为 E ,至多为 FA. 2hB. 2h-1C. 2h+1D.h+1E. 2 h-1F. 2 h-1G. 2 h+1-1H. 2 h+123 .一棵有124个叶结点的完全二叉树，最多有 B 个结点。A. 247B.248C.249D. 25124 .若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是 C。A.满二叉树B.哈夫曼树C.堆D.二叉查找树25 .前序遍历和中序遍历结果相同的二叉树为F;前序遍历和后序遍历结果相同的二叉树为B。A. 一般二叉树B.只有根结

18、点的二叉树C.根结点无左孩子的二叉树D.根结点无右孩子的二叉树E.所有结点只有左孩子的二叉树F.所有结点只有右孩子的二叉树26 .具有n个结点的完全二叉树，已经顺序存储在一维数组A1.n中，下面的算法是将A中顺序存储变为二叉链表存储的完全二叉树。请填写适当语句在下面的空格内，完成上述算法。#define MAXSIZE 30typedef struct btnodeint data;struct btnode *lchild, *rchild;BTN;void createtree(BTN *p,int A, int I,int n)；p->data=AI; if( (2)；elsep-

19、>lchild=NULL; if( (4) createtree( (5);elsep->rchild=NULL;void btree(BTN * p ,int A,int n) 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,n27 .若在线性表中采用折半查找法查找元素，该线性表应该C。A.元素按值有序B.采用顺序存储结构C.元素按值有序，且

20、采用顺序存储结构D.元素按值有序，且采用链式存储结构28 .在分块检索中，对 256个元素的线性表分成 6 块最好，每块的最佳长度是16;若每块的长度为 8,其平均检索长度为21。29 .假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行 D 次探测。A. K-1 次B. K 次C. K+1 次D. K(K+1)/2 次30 .在n个记录的有序顺序表中进行折半查找，最大的比较次数是Jog2 n +1。31 .Hash技术广泛应用于查找过程，选择 Hash函数的标准是 和 处理冲突的技术有优有劣，其共同标准是 。32 .在下述排序算法中，所需辅助存储空间最多的是B,

21、所需辅助存储空间最小的是 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 方法最快oA.冒泡排序B.快速排序C.希尔排序D.堆排序

22、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.快速排序B.堆排序C.归并排序D.希尔排序39 .从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为 A 排序法。A.插入排序B.交换排序C.选择排序D.归并排序40 .直接插入排序在最好情况下的时间复杂度为B。A. O(logn)B. O(n)C. O(n

23、logn)D. O(n 2)41.下面函数是将任意序列调整为最大堆的算法，请将空白部分填上：将任意序列调整为最大堆通过不断调用adjust函数，即for(i=n/2;i>0;i-) adjust(list, i, n);其中list为待调整序列所在数组(从下标1开始)，n为序列元素的个数。void adjust(int list, int root, int n)/*将以root为下标的对应元素作为待调整堆的根，待调整元素放在list数组中，最大元素下标为n*/int child,rootkey;rootkey =;child = 2*root;while(child < n)if

24、(child<n) && (listchild<listchild+1)(2)；if(rootkey > listchild)break;elselist (3) =listchild;(4);list (5) =rootkey;参考答案：(1) listroot(2) child+; child/2(4) child *= 2; child/241 .表是一种数据结构，链表是一种(1)。队列和栈都是线性表，栈的操作特性是 (2),队列的操作特性是(3)。今有一空栈 S,对下列待进栈的数据元素序列a,b,c,d,e,f依次进栈、进栈、出栈、进栈、进栈、出栈的操

25、作，则此操作完成后，栈S的栈顶元素为 (4),栈底元素为(5)。供选答案：(1):A.非顺序存储线性表B.D.非顺序存储非线性表 顺序存储非线性表C.顺序存储线性表(2)：A.随机进出B.先进后出C.先进先出D.出优于进(3)：A.随机进出B.先进后出C.后进后出D.进优于出(4)：A.fB.cC.aD.b(5)：A.bB.c答案：C. aABCBCD.d42 .操作系统主要是对计算机系统全部(1)进行管理，以方便用户、提高计算机使用效率的一种系统软件。它的主要功能有：处理机管理、存储管理、文件管理、'理和设备管理等。 Windows和Unix是最常用的两类操作系统。前者是一个具有图形

26、界面的 窗口式的 系统软件，后者是一个基本上采用(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.实时答案：CBBDD43 .本程序从键盘读入整数，并按从大到小的顺序输出输入整数中互不相等的那些整数。程序一边读入整数，一边构造一个从大到小顺序链接的链表，直至不能从键盘读入整数，然后顺序输出链表上各表元的整数值

27、。主函数每读入一个整数，就调用函数insert(),函数insert() 将还未出现在链表上的整数按从大到小的顺序插入到链表中。为了插入方便，链表在表首有一个辅助表元。阅读下列C代码，在 (n)处填入相应的字句以完成上述功能。#include <stdio.h> #include <malloc.h>#define NULL 0typedef struct nodeint val;struct node *next;NODE;void insert(NODE *list,int x)NODE *u, *v, *p;u = list; v = u->next;/*寻

28、找插入位置*/*判断是否要插入表元*/*生成新表元*/插入新表元*/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()int x;NODE *head, *p;/*首先建立只有辅助表元的空链表 */head = (NODE *)malloc(sizeof(NODE);(5) =NULL;printf(Enter Integers:n);while(scanf( "

29、%d ,&x) = 1)/*反复读入整数插入链表 */insert(head,x);for(p=head->next;p!=NULL;p=p->next)/* 输出链表 */printf( "%dt" ,p->val);printf( "n ");答案： v != NULL 或 v(2) x > v->val 或 x != v->val(3) p->next(4) u->next(5) head->next44 .计算机数据处理的对象是具有不同结构的各种数据，可以访问的最小数据信息单位是(1)

30、,可以引用的最小命名数据单位是(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 .本程序用于从链盘读入整数，插入到链表，或从链表删除一个整数。阅读下面的C代码，将应填入(

31、n)处的字名写在答卷的对应栏内。#include <stdio.h>#include <malloc.h>typedef struct node int val;struct node * next;NODE;NODE * ins(NODE *list, int x)/*将x按从小到大的次序插入链表*/NODE *u, *v=list, *p;for(; v != NULL && x < v->val ; v = v->next);/*寻找插入位置 */if(v != NULL && x = v->val) ret

32、urn(list);/* 已有，被忽略 */p = (NODE *)malloc(sizeof(NODE);p->val=x; /*生成新表元 */if(v = list) list = p; else；(2)； return list;NODE * del(NODE * list, int x) /*从链表中删除值为x的表元*/NODE *u, *v;for(v = list; v != NULL && x < v->valu; u=v;v=v->next);if(v != NULL && x = v->val)/* 找到值为 x

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

34、("%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 != 246 .从未排序的序列中，依次取出元素，与已排序序列的元素比较后，放入已排序序列中的恰当位置上，这是 (1)排序。从未

35、排序的序列中，挑选出元素，放在已排序序列 的某一端位置，这是 排序。逐次将待排序的序列中的相邻元素两两比较，凡是逆序则进行交换，这是 (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)系统软

36、件，是 (2)的接口。在处理机管理中， 进程是一个重要的概念，它由程序块、(3)和数据块三部分组成，它有3种基本状态，不可能发生的状态转换是(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.寄存器答

37、案：CDADB48. A 是信息的载体，它能够被计算机识别、存储和加工处理。A.数据B.数据元素C.结点D.数据项49.下列程序段的时间复杂度为 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(n 2)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(log 2n)51 .下面程序段的时间复杂度为B。a=0;b=1;for(i=2;i<=n;i+)s=a+b;

38、b=a;a=s;供选答案：D. O(n 2)A 以及它们之D.数据映象A. O(1)B. O(n)C. O(log 2n)52 .数据结构是一门研究非数值计算的程序设计问题中，计算机的 间的关系和运算等的学科。A.操作对象B.计算方法C.逻辑存储53 .在数据结构中，从逻辑上可以把数据结构分成CA.动态结构和静态结构B.紧凑结构和非紧凑结构D.内部结构和外部结构B.正确性和简明性D.数据复杂性和程序复杂性C.线性结构和非线性结构54 .算法分析的目的是C 。A.找出数据结构的合理性B.研究算法中输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性55 .算法分析的两个主要方面

39、是 (4)A.间复杂性和时间复杂性C.可读性和文档性56 .一个线性顺序表第一个元素的存储地址是100,每个元素的长度为 2,则第5个元素的地址为_BA. 110B.108C.100D.12057 .若已知一个栈的入栈序列是1,2,3, , ,n ,其输出序列为 P1,P2,P3, , ,Pn,若P1=n,则P为 C。A. iB. n-iC. n-i+1D.不确定58 .对于一个栈，乂出输入项A,B,C。如果输入项序列由A,B,C所组成，则不可能产生的输出序列是 A。A. CABB. CBAC. ABCD. ACB59 .设有如下的单链表的按序号查找的算法，其时间复杂度为B。LinkNode

40、*GetNode(Linklist head, int i)int j;ListNode *p;P = head; j=0;while(p->next && j<i)p = p->next; j+;if(i=j)return(p);elsereturn(NULL);供选答案:A. O(n 2)B. O(2n)C. O(n 3)60 .二维数组Am故行序为主顺序存放在内存中，每个数组元素占D. O(logn)个存储单元，则元素aj的地址计算公式是A. LOC(a ij) = LOC(a B. LOC(a ij) = LOC(a C. LOC(a ij) = LO

41、C(a D. LOC(a ij) = LOC(aii)+(i-1)*m+(j-1)ii)+(j-1)*m+(i-1)ii)+(i-1)*n+(j-1)ii)+(j-1)*n+(i-1)61 .以下哪一个不是队列的基本运算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个单元的顺序

42、存储的循环队列中,假定front和rear分别为队首指针和队尾指针，则判断队空的条件是A. front=rear+165.从一个具有 均比较 DA. nB. front=rearn个结点的单链表中查找其值等于C. front+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 .判断一个顺序栈

43、ST (最多元素为B.散列方式和索引方式D.线性存储结构和非线性存储结构A. ST->top<>0B. ST->top=0m。为空的条件是 BC. st->top<>moD. st->top=moA. head=NILL69 .不带头结点的单链表head为空表的判定条件是B. head->next=NULL C. head->next=head D. head != NULL70 .在一个单链表中，已知 q所指结点是p所指结点的前驱结点，若在 p和q之间才1入s结点，则应执行CA. s->next = p->next; p

44、->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 .假设双向链表结点的类型如下:typedef struct Linknodeint data;struct Linknode *lLink;struct Linknode *rLink;/*前驱结点指针*/*后继结点指针*/下面给出的算法是要把一个q所指新结点，作为非空双向链表中的p所指的结点前驱结点插入到该双向链表中，能正确完成要求的算法段是C。A. q-

45、>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 .串是一种特殊的线性表，其特殊性体现在 BA.可以顺序存储B.数据元素是一个字符C.可以链接存储D.数

46、据元素可以是多个字符73 .设有两个串p和q,求q在p中首次出现的位置的运算称作BA.连接B.模式匹配C.求子串D.求串长74 .设串 s1 = " ABCDEFG, s2=" PQRST ,函数 con(x,y)返回 x和 y 串的连接串，subs(s,I,j)len(s)返回串s的长度，则的结果是 D返回串s的从序号i的字符开始的j个字符组成的子串,con(sub(s1,2,len(s2),sub(s1,len(s2),2)A. BCDEFB. BCDEFGC. BCPQRSTD. BCDEFEF75 .常对数组进行的两种基本操作是C。A.建立和删除B.索引和修改 C.

47、查找和修改D.索引和查找76 .稀疏矩阵一般的压缩存储方法有两种，即C 。A.二维数组和三维数组B.三元组和散列C.三元组和十字链表D.散列和十字链表77 .对下图所示的二叉表，按先根次序遍历得到的结点序列为BD. HIDBEFGACA. ABCDHEIFGB. ABDHIECFGC. HDIBRAFCG78 .在一棵二叉树上，度为 0的结点个数为n0,度为2的结点数为n2,则n0= A。A. n 2+1B. n 2-1C. n 2D. n 2/279 .某二叉树前序遍历结点的访问顺序是ABCDEFG中序遍历结点的访问顺序是CBDAFGE则其后序遍历结点的访问顺序是A。B. CDGFEABD.

48、 CDBFAGEA. CDBGFEAC. CDBAGFE80 .在下列存储形式中，D 不是树的存储形式。A.双亲表示法B.孩子链表表示法C.孩子兄弟表示法D.顺序存储表示法81 .已知一棵二叉树的中序序列为cbedahgijf ,后序序列为cedbhjigfa ,则该二叉树为B。82.已知一棵权集 W=2,3,4,7,8,9A.20B.40的哈夫曼树，其加权路径长度WPL为C. 80D.16083 .已知一棵度为 m的树中有m个度为1的结点，n2个度为2的结点，nm个度为m的结点，问这棵树中叶子结点为 C。A. 1+n i(I-1)B. 1+n i (I+1) C. n 1+n?+, +nmD

49、. m nm84 .如下图所示的4棵二叉树中， C不是完全二叉树。85 .设高度为h的二叉树上只有度为 0或度为2的结点，则此类二叉树中所包含的结点数至 少为 B。A. 2hB. 2h-1C.2h+1D. h+1A.abcdgef86 .如下图所示的二叉树的中序遍历序列是CB. dfebagc C. dbaefcgD. defbagc87.已知某二叉树的后序遍历序列是dabec,中序遍历序列是 debac,则其前序遍历序列为DA. acbedB. decabC. deabcD. cedba88 .如果T2是由有序树T转换而来的二叉树，则T中结点的前序就是 T2中结点的A ，A.前序B.中序C.

50、后序D.层次序89 .树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。下面结论正确的是A。A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同B.树的先根遍历序列与其对应的二叉树的后序遍历序列相同C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同D.以上均不对90 .深度为5的二叉树至多有C个结点。A. 16B. 32C. 31D. 1091 .在一非空二叉树的中序遍序序列中，根结点的右边A。A.只有右子树的所有结点B.只有右子树的部分C.只有左子树的部分结点D.只有左子树的所有结点

51、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,贝U D。A. n=h+mB.h+m=2nC. m=h-1D. n=2 h-195.如果某二叉树的前序为stuwv ,中序为uwtvs ,则该二叉树后序为 C。A. uwvtsB. vwutsC. wuvtsD. wutsv96 .设待排序的记录为(20,16,13,14,19)

52、,经过下列过程将这些记录排序。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,90,82C. 82,75,70,16,10,90,68,23D. 23,10,16,70,82,75,68,9098 .用快速排序

53、的方法对包含几个关键字的序列进行排序，最坏情况下，执行的时间为 D。A. O(n)B. O(log 2n)C.O(nlog 2n)D. O(n 2)99 .在所有排序方法中，关键码(即关键字)比较的次数与记录的初始排列次序无关的是 D。A.希尔排序B.冒泡排序C.直接插入排序D.直接选择排序100 .在归并排序过程中，需归并的趟数为C 。A. nB. nC. |lnlog2nD.log 2 n101 .一组记录的排序代码为46,79,56,38,40,84,则利用堆排序的方法建立的初始堆为 B。A. 79,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 .每次把待排序的区间划分为左、右两个子区间，其中左区间中元素的排序码均