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

《《计算机软件技术基础》试题及答案.doc》由会员分享，可在线阅读，更多相关《《计算机软件技术基础》试题及答案.doc（37页珍藏版）》请在装配图网上搜索。

《计算机软件技术基础》试题 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是一个线性表(a1,a2,…,an)，采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为 B ，平均每删除一个元素需要移动的元素个数为 A ；若元素插在ai与ai+1之间(0≤I≤n-1)的概率为，则平均每插入一个元素所要移动的元素个数为 C ； A. B. C. D. 5.下列函数中，按它们在时的无穷大阶数，最大的是 D 。 A. logn B. nlogn C. 2n/2 D. n! s p next next next 6.将下图所示的s所指结点加到p所指的结点之后，其语句应为： D 。 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. n B. 2n-1 C. n-1 D. 2n 8.下面的程序段是合并两个无头结点链表(ha和 hb)为一个无头结点链表ha的过程，作为参数的两个链表都是按结点的data域由大到小链接的。合并后新链表的结点仍按此方式链接。请填写下述空框，使程序能正确运行。 #define NULL 0 typedef struct node{ int data; struct node *next; }node, linklisttype; void combine(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中所有元素(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。（提示：用递归实现） #define true 1 #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; (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。请在空框处填上适当内容，每框只填一个语句。 #define NULL 0 typedef struct node{ int data; struct node *next; }node, linklisttype; linklisttype *create_link_list(int n){ linklisttype *head, *p, *q; int I; 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); } void Josephus(int n, int j, int m){ linklisttype *p, *q; int j; p = create_link_list(n); for(;I>1;I--) p = p->next; (4) ; while(jnext; (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 #define NULL 0 typedef struct node{ int data; struct node *next; }NODE; NODE *append(NODE *last, int x){ 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处开始存储)，删除所有值相等的多余元素。 #define MAXSIZE 30 typedef struct{ int elem[MAXSIZE]; int length;/*表长*/ }sqlisttype; void exam21(sqlisttype *L){ int I,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和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-1 C. 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中顺序存储变为二叉链表存储的完全二叉树。请填写适当语句在下面的空格内，完成上述算法。 #define MAXSIZE 30 typedef struct btnode{ int data; struct btnode *lchild, *rchild; }BTN; void createtree(BTN *p,int A[], int I,int n){ (1) ; p->data=A[I]; if( (2) ) (3) ; else p->lchild=NULL; if( (4) ) createtree( (5) ); else p->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,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个记录的有序顺序表中进行折半查找，最大的比较次数是。 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为序列元素的个数。 void adjust(int list[], int root, int n){ /*将以root为下标的对应元素作为待调整堆的根，待调整元素放在list数组中，最大元素下标为n*/ int child,rootkey; rootkey = (1) ; child = 2*root; while(child < n){ if((child 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. 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. 数据 B. 作业 C. 中断 D. I/O (3): A. 分时 B. 多任务 C. 多用户 D. 实时 (4): A. PASCAL B. 宏 C. 汇编 D. C (5): A. 网络 B. 分时 C. 批处理 D. 实时 答案：CBBDD 43.本程序从键盘读入整数，并按从大到小的顺序输出输入整数中互不相等的那些整数。 程序一边读入整数，一边构造一个从大到小顺序链接的链表，直至不能从键盘读入整数，然后顺序输出链表上各表元的整数值。主函数每读入一个整数，就调用函数insert()，函数insert()将还未出现在链表上的整数按从大到小的顺序插入到链表中。 为了插入方便，链表在表首有一个辅助表元。 阅读下列C代码，在 (n) 处填入相应的字句以完成上述功能。 #include #include #define NULL 0 typedef struct node{ int val; struct node *next; }NODE; void insert(NODE *list,int x){ 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(){ int x; NODE *head, *p; /*首先建立只有辅助表元的空链表*/ head = (NODE *)malloc(sizeof(NODE)); (5) =NULL; printf(“Enter Integers:\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 #include 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) return(list); /*已有，被忽略*/ p = (NODE *)malloc(sizeof(NODE));p->val=x; /*生成新表元*/ if(v == list) list = p; else (1) ; (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的表元*/ if(v == list) list = list->next; else (3) ; (4) ; /*释放空间*/ } else printf(“没有找到!\n”); return(list); } main(){ int x,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); else list=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. CDROM D. 寄存器 答案：CDADB 48. A 是信息的载体，它能够被计算机识别、存储和加工处理。 A. 数据 B. 数据元素 C. 结点 D. 数据项 49.下列程序段的时间复杂度为 C 。 for(i=1;inext && jnext; j++; } if(i==j) return(p); else return(NULL); } 供选答案： A. O(n2) B. O(2n) C. O(n3) D. O(logn) 60.二维数组Amn按行序为主顺序存放在内存中，每个数组元素占1个存储单元，则元素aij的地址计算公式是 C 。 A. LOC(aij) = LOC(a11)+[(i-1)*m+(j-1)] B. LOC(aij) = LOC(a11)+[(j-1)*m+(i-1)] C. LOC(aij) = LOC(a11)+[(i-1)*n+(j-1)] D. LOC(aij) = LOC(a11)+[(j-1)*n+(i-1)] 61.以下哪一个不是队列的基本运算 C 。 A. 从队尾插入一个新元素 B. 从队列中删除第i个元素 C. 判断一个队列是否为空 D. 读取队头元素的值 62.在一个长度为n的顺序表中，向第i个元素之前插入一个新元素，需向后移动 B 个元素。 A. n-i B. n-i+1 C. n-i-1 D. i 63.从一个长度为n的顺序表中删除第i个元素时，需向前移动 A 个元素。 A. n-i B. n-i+1 C. n-i-1 D. i 64.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队空的条件是 B 。 A. front=rear+1 B. front=rear C. front+1=rear D. front=0 65.从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较 D 个结点。 A. n B. n/2 C. (n-1)/2 D. (n+1)/2 66.一个栈的入栈序列是a,b,c,d,e，则栈不可能的输出序列是 C 。 A. edcba B. decba C. dceab D. abcde 67.栈结构通常采用的两种存储结构是 A 。 A. 顺序存储结构和链表存储结构 B. 散列方式和索引方式 C. 链表存储结构和数组 D. 线性存储结构和非线性存储结构 68.判断一个顺序栈ST（最多元素为mo）为空的条件是 B 。 A. ST->top<>0 B. ST->top=0 C. st->top<>mo D. st->top==mo 69.不带头结点的单链表head为空表的判定条件是 A 。 A. head==NILL B. head->next==NULL C. head->next==head D. 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.假设双向链表结点的类型如下： typedef struct Linknode{ int data; struct Linknode *lLink; /*前驱结点指针*/ struct Linknode *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. BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF 75.常对数组进行的两种基本操作是 C 。 A. 建立和删除 B. 索引和修改 C. 查找和修改 D. 索引和查找 76.稀疏矩阵一般的压缩存储方法有两种，即 Ｃ 。 A. 二维数组和三维数组 B. 三元组和散列 C. 三元组和十字链表 D. 散列和十字链表 77.对下图所示的二叉表，按先根次序遍历得到的结点序列为 B 。 A. ABCDHEIFG B. ABDHIECFG C. HDIBRAFCG D. HIDBEFGAC 78.在一棵二叉树上，度为0的结点个数为n0，度为2的结点数为n2，则n0= A 。 A. n2+1 B. n2-1 C. n2 D. n2/2 79.某二叉树前序遍历结点的访问顺序是ABCDEFG，中序遍历结点的访问顺序是CBDAFGE，则其后序遍历结点的访问顺序是 A 。 A．CDBGFEA B. CDGFEAB C. CDBAGFE D. CDBFAGE 80.在下列存储形式中， D 不是树的存储形式。 A. 双亲表示法 B. 孩子链表表示法 C. 孩子兄弟表示法 D. 顺序存储表示法 81. 已知一棵二叉树的中序序列为cbedahgijf，后序序列为cedbhjigfa，则该二叉树为 B 。 82. 已知一棵权集W={2,3,4,7,8,9}的哈夫曼树，其加权路径长度WPL为 Ｃ 。 A. 20 B. 40 C. 80 D. 160 83.已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，…，nm个度为m的结点，问这棵树中叶子结点为 Ｃ 。 A. 1+ni(I-1) B. 1+ni(I+1) C. n1+n2+…+nm D. m·nm 84.如下图所示的4棵二叉树中， Ｃ 不是完全二叉树。 85.设高度为h的二叉树上只有度为0或度为2的结点，则此类二叉树中所包含的结点数至少为 B 。 A. 2h B. 2h-1 C. 2h+1 D. h+1 86.如下图所示的二叉树的中序遍历序列是 Ｃ 。 A. abcdgef B. dfebagc C. dbaefcg D. defbagc 87.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，则其前序遍历序列为 D 。 A. acbed B. decab C. deabc D. cedba 88.如果T2是由有序树T转换而来的二叉树，则T中结点的前序就是T2中结点的 A 。 A. 前序 B. 中序 C. 后序 D. 层次序 89.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。下面结论正确的是 A 。 A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B. 树的先根遍历序列与其对应的二叉树的后序遍历序列相同 C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D. 以上均不对 90. 深度为5的二叉树至多有 Ｃ 个结点。 A. 16 B. 32 C. 31 D. 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+m B. h+m=2n C. m=h-1 D. n=2h-1 95.如果某二叉树的前序为stuwv，中序为uwtvs，则该二叉树后序为 Ｃ 。 A. uwvts B. vwuts C. wuvts D. 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.用快速排序的方法对包含几个关键字的序列进行排序，最坏情况下，执行的时间为 D 。 A. O(n) B. O(log2n) C.O(nlog2n) D. O(n2) 99.在所有排序方法中，关键码（即关键字）比较的次数与记录的初始排列次序无关的是 D 。 A. 希尔排序 B. 冒泡排序 C. 直接插入排序 D. 直接选择排序 100.在归并排序过程中，需归并的趟数为 Ｃ 。 A. n B. C. D. 101.一组记录的排序代码为{46,79,56,38,40,84}，则利用堆排序的方法建立的初始堆为 B 。 A. {79,46,