2021年计算机软件基础复习题库带答案

《计算机软件基本》复习题库(带答案)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(n/2)，平均每删除一种元素需要移动元素个数为

A；若元素插在ai与ai+1之间(0≤I≤n-1)概率为，则平均每插入一种元素所要移动元素个数为C ；A. B.C. D.5.下列函数中，按它们在时无穷大阶数，最大是D。A.logn B.nlognC.2n/2 D.n!spnextnextnext6.将下图所示s所指结点加到spnextnextnextA.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-1C.n-1 D.2n8.下面程序段是合并两个无头结点链表(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->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=ha9.如果表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{ 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。请在空框处填上恰当内容，每框只填一种语句。#defineNULL0typedefstructnode{ 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->next11.在下列程序中，函数difference(A,B)用于求两集合之差C=A-B，即当且仅当e是A中一种元素，且不是B中元素时，e是C中一种元素。集合用有序链表实现，用一种空链表表达一种空集合，表达非空集合链表依照元素之值按递增排列，执行C=A-B之后，表达集合A和B链表不变，若成果集合C非空，则表达它链表应依照元素之值按递增序排列。函数append()用于在链表中添加结点。#include<stdio.h>#defineNULL0typedefstructnode{ 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处开始存储)，删除所有值相等多余元素。#defineMAXSIZE30typedefstruct{intelem[MAXSIZE];intlength;/*表长*/}sqlisttype;voidexam21(sqlisttype*L){ inti,j; i=1,j=2; while((1)){if(L->elem[i]!=L->elem[j]){ if(j!=(i+1)) (2);L->length=L->length-(j-i-1); (3);}else{(4);if(j>L->length) (5);}}}参照答案：(1)j<=L->length(2)for(intk=j;k<=L->length;k++) L->elem[k-(j-i-1)]=L->elem[k];(3)i++,j=i+1;(4) j++;(5){L->length=L->length-(j-i-1); break;}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和4C.4和2 D.5和117.设栈输入序列为1,2，…,10，输出序列为a1,a2,…,a10，若a5=10，则a7为C。A.4 B.8 C.不拟定 D.718.设栈输入序列是1,2,3,4，则D不也许是其出栈序列。A．1243 B.2134 C.1432 D.431219.如下D是C语言中”abcd321ABCD”子串。A.abcd B.321AB C.“abcABC” D.“21AB”20.若串S=”software”，其子串数目是C。A.8 B.37 C.36 D.921.将一种A[1:100,1:100]三对角矩阵，按行优先存入一维数组B[1:298]中，A中元素A66,65(即该元素下标)在B数组中位置k为B。A.198 B.195 C.197 D.19622.设高为h二叉树只有度为0和2结点，则此类二叉树结点数至少为B，至多为F。高为h完全二叉树结点数至少为E，至多为F。A．2h B.2h-1 C.2h+1 D.h+1E.2h-1 F.2h-1 G.2h+1-1 H.2h23.一棵有124个叶结点完全二叉树，最多有B个结点。A.247 B.248 C.249 D.25124.若从二叉树任一结点出发到根途径上所通过结点序列按其核心字有序，则该二叉树是C。A.满二叉树 B.哈夫曼树C.堆 D.二叉查找树25.前序遍历和中序遍历成果相似二叉树为F；前序遍历和后序遍历成果相似二叉树为B。A.普通二叉树 B.只有根结点二叉树C.根结点无左孩子二叉树 D.根结点无右孩子二叉树E.所有结点只有左孩子二叉树 F.所有结点只有右孩子二叉树26.具备n个结点完全二叉树，已经顺序存储在一维数组A[1..n]中，下面算法是将A中顺序存储变为二叉链表存储完全二叉树。请填写恰当语句在下面空格内，完毕上述算法。#defineMAXSIZE30typedefstructbtnode{ 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,n27.若在线性表中采用折半查找法查找元素，该线性表应当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,50B.100,70,50,20,90,75,60,25,10,85,65,8038.若要尽量快地完毕对实数数组排序，且规定排序是稳定，则应选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/241.表是一种数据构造，链表是一种(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答案：ABCBC42.操作系统重要是对计算机系统所有(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.实时答案：CBBDD43.本程序从键盘读入整数，并按从大到小顺序输出输入整数中互不相等那些整数。程序一边读入整数，一边构造一种从大到小顺序链接链表，直至不能从键盘读入整数，然后顺序输出链表上各表元整数值。主函数每读入一种整数，就调用函数insert()，函数insert()将尚未出当前链表上整数按从大到小顺序插入到链表中。为了插入以便，链表在表首有一种辅助表元。阅读下列C代码，在(n)处填入相应字句以完毕上述功能。#include<stdio.h>#include<malloc.h>#defineNULL0typedefstructnode{ 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->next44.计算机数据解决对象是具备不同构造各种数据，可以访问最小数据信息单位是

(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.浏览答案：CDBBC45.本程序用于从链盘读入整数，插入到链表，或从链表删除一种整数。阅读下面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); /*释放空间*/ } else printf(“没有找到!\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); 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!=246.从未排序序列中，依次取出元素，与已排序序列元素比较后，放入已排序序列中恰当位置上，这是(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.占用存储多少和解决数据量大小答案：BAABA47.操作系统是对计算机资源进行(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.寄存器答案：CDADB48.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(log2n)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(log2n) D.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.110 B.108 C.100 D.12057.若已知一种栈入栈序列是1,2,3,…,n，其输出序列为P1,P2,P3,…,Pn，若P1=n，则Pi为C。A.i B.n-i C.n-i+1 D.不拟定58.对于一种栈，给出输入项A,B,C。如果输入项序列由A,B,C所构成，则不也许产生输出序列是A。A.CAB B.CBA C.ABC D.ACB59.设有如下单链表按序号查找算法，其时间复杂度为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.二维数组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.i63.从一种长度为n顺序表中删除第i个元素时，需向前移动A个元素。A.n-i B.n-i+1 C.n-i-1 D.i64.在具备n个单元顺序存储循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队空条件是B。A.front=rear+1 B.front=rear C.front+1=rear D.front=065.从一种具备n个结点单链表中查找其值等于x结点时，在查找成功状况下，需平均比较D个结点。A.n B.n/2 C.(n-1)/2 D.(n+1)/266.一种栈入栈序列是a,b,c,d,e，则栈不也许输出序列是C。A.edcba B.decba C.dceab D.abcde67.栈构造普通采用两种存储构造是A。A.顺序存储构造和链表存储构造 B.散列方式和索引方式C.链表存储构造和数组 D.线性存储构造和非线性存储构造68.判断一种顺序栈ST（最多元素为mo）为空条件是B。A.ST->top<>0 B.ST->top=0 C.st->top<>mo D.st->top==mo69.不带头结点单链表head为空表鉴定条件是A。A.head==NILL B.head->next==NULL C.head->next==head D.head!=NULL70.在一种单链表中，已知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.BCDEF B.BCDEFG C.BCPQRST D.BCDEFEF75.常对数组进行两种基本操作是C。A.建立和删除 B.索引和修改 C.查找和修改 D.索引和查找76.稀疏矩阵普通压缩存储办法有两种，即Ｃ。A.二维数组和三维数组 B.三元组和散列C.三元组和十字链表 D.散列和十字链表77.对下图所示二叉表，按先根顺序遍历得到结点序列为B。A.ABCDHEIFG B.ABDHIECFGC.HDIBRAFCG D.HIDBEFGAC78.在一棵二叉树上，度为0结点个数为n0，度为2结点数为n2，则n0=A。A.n2+1 B.n2-1C.n2 D.n2/279.某二叉树前序遍历结点访问顺序是ABCDEFG，中序遍历结点访问顺序是CBDAFGE，则其后序遍历结点访问顺序是A。A．CDBGFEA B.CDGFEABC.CDBAGFE D.CDBFAGE80.在下列存储形式中，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.16083.已知一棵度为m树中有n1个度为1结点，n2个度为2结点，…，nm个度为m结点，问这棵树中叶子结点为Ｃ。A.1+ni(I-1) B.1+ni(I+1) C.n1+n2+…+nm D.m·nm84.如下图所示4棵二叉树中，Ｃ不是完全二叉树。85.设高度为h二叉树上只有度为0或度为2结点，则此类二叉树中所包括结点数至少为B。A.2h B.2h-1 C.2h+1 D.h+186.如下图所示二叉树中序遍历序列是Ｃ。A.abcdgef B.dfebagc C.dbaefcg D.defbagc87.已知某二叉树后序遍历序列是dabec，中序遍历序列是debac，则其前序遍历序列为

D。A.acbed B.decab C.deabc D.cedba88.如果T2是由有序树T转换而来二叉树，则T中结点前序就是T2中结点A。A.前序 B.中序 C.后序 D.层顺序89.树基本遍历方略可分为先根遍历和后根遍历；二叉树基本遍历方略可分为先序遍历、中序遍历和后序遍历。这里，咱们把由树转化得到二叉树叫做这棵树相应二叉树。下面结论对的是A。A.树先根遍历序列与其相应二叉树先序遍历序列相似B.树先根遍历序列与其相应二叉树后序遍历序列相似C.树先根遍历序列与其相应二叉树中序遍历序列相似D.以上均不对90.深度为5二叉树至多有Ｃ个结点。A.16 B.32 C.31 D.1091.在一非空二叉树中序遍序序列中，根结点右边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=2nC.m=h-1 D.n=2h-195.如果某二叉树前序为stuwv，中序为uwtvs，则该二叉树后序为Ｃ。A.uwvts B.vwutsC.wuvts D.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序列。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.用迅速排序办法对包括几种核心字序列进行排序，最坏状况下，执行时间为

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,56,38,40,80} B.{84,79,56,38,40,46}C.{84,79,56,46,40,38} D.{84,56,79,40,46,38}102.一组记录排序代码为{46,79,56,38,40,84}，则运用迅速排序办法，以第一种记录为基准得到一次划提成果为Ｃ。A.{38,40,46,56,79,84} B.{40,38,46,79,56,84}C.{40,38,46,56,79,84} D.{40,38,46,84,56,79}103.每次把待排序区间划分为左、右两个子区间，其中左区间中元素排序码均不大于等于基准元素排序码，右区间中元素排序码均不不大于等于基准元素排序码，此种排序办法叫做B。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,79,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个最大元素，最佳选用

Ｃ排序法。A.冒泡排序 B.迅速排序C.堆排序 D.希尔排序107.在待排序元素序列基本有序前提下，效率最高排序办法是A。A.插入排序 B.选取排序C.迅速排序 D.归并排序108.用某种排序办法对线性表{25,84,21,47,15,27,68,35,20}进行排序时，元素序列变化状况如下：(1)25,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.迅速排序办法在Ｃ状况下最不利于发挥其长处。A.要排序数据量太大 B.要排序数据中具有各种相似值C.要排序数据已基本有序 D.要排序数据个数为整数110.设有一种已按各元素值排好序线性表，长度不不大于2，对给定值K，分别用顺序查找法和二分查找法查找一种与K相等元素，比较次数分别为s和b。在查找不成功状况下，对的s和b数量关系是B。A.总有s=b B.总有s>bC.总有s<b D.与k值大小关于111.如果规定一种线性表既能较快地查找，又能适应动态变化规定，则可采用办法是

A。A.分块法 B.顺序法C.二分法 D.哈希法112.哈希表地址区间为0-17，哈希函数为H(k)=kmod17。采用线性探测法解决冲突，并将核心字序列{26,25,72,38,8,18,59}依次存储到哈希表中。那么，元素59存储在哈希表中地址是D。A.8 B.9C.10 D.11113.哈希表地址区间为0-17，哈希函数为H(k)=kmod17。采用线性探测法解决冲突，并将核心字序列{26,25,72,38,8,18,59}依次存储到哈希表中。如果要访问元素59，则需要搜索次数是Ｃ。A.2 B.3C.4 D.5114.在计算机系统中，容许各种程序同步进入内存并运营，这种办法称为D。A.Spodling技术 B.虚拟存储技术C.缓冲技术 D.多道程序设计技术115.分时系统追求目的是C。A.高吞吐率 B.充分运用内存C.迅速响应 D.减少系统开销116.引入多道程序目是D。A.提高实时响应速度 B.增强系统交互能力C.为了充分运用主存储器 D.充分运用CPU，减少CPU等待时间117.若把操作系统看作计算机系统资源管理者，下列D不属于操作系统所管理资源。A.程序 B.内存C.CPU D.中断118.A不属于多道程序设计概念。A.各种顾客同步使用一台计算机打印设备B.各种顾客同步进入计算机系统，并规定同步处在运营状态C.一种计算机系统从宏观上进行作业并行解决，但在微观上仍在串行操作D.各种作业同步存储在主存并处在运营状态119.操作系统CPU管理重要是解决C。A.单道程序对CPU占用 B.多道程序对CPU占用C.多道程序对CPU分派 D.多道程序或单道程序对CPU争夺120.分时操作系统是指B。A.各种顾客分时使用同一台计算机某一种终端B.多道程序分时共享计算机软、硬件资源C.多道程序进入系统后批量解决D.多顾客计算机系统121.A不是实时系统特性。A.很强交互性 B.具备对顾客信息及时响应性C.具备很强可靠性 D.有一定交互性122.工业过程控制系统中，运营操作系统最佳是B。A.分时系统 B.实时系统C.分布式操作系统 D.网络操作系统123.对解决事件有严格时间限制系统是B。A.分时系统 B.实时系统C.分布式操作系统 D.网络操作系统124.在下列操作系统中，强调吞吐能力是B。A.分时系统 B.多道批解决系统C.实时系统 D.网络操作系统125.操作系统中，当B时，进程从执行状态转变为就绪状态。A.进程被进程调度程序选中 B.时间片到C.等待某一事件 D.等待事件发生126.进程和程序主线区别在于D。A.与否具备就绪、运营和等待状态 B.与否被调入内存中C.与否占有解决机 D.静态与动态特点127.在单解决机系统中，若同步存在有10个进程，则处在就绪队列中进程最多为

C个。A.0 B.6C.9 D.10128.下列不属于临界资源是A。A.CPU B.公共变量C.公用数据 D.输入输出设备129.下面关于进程同步说法中，错误是D。A.为使进程共享资源，又使它们互不冲突，因而必要使这些有关进程同步B.系统中有些进程必要合伙，共同完毕一项任务，因而规定各有关进程同步C.进程互斥实质也是同步，它是一种特殊同步D.由于各进程之间存在着互相依从关系，必要规定各进程同步工作130.若S是P、V操作信号量，当S<0时，其绝对值表达A。A.排列在信号量等待队列中进程数B.可供使用临界资源数C.无资源可用D.无进程排队等待131.信号量S初始值为8，在S上调用10次P操作和6次V操作后，S值为D。A.10 B.8C.6 D.4132.系统中有两个进程A和B，每个进程都需使用1台打印机和扫描仪，但系统中当前只有一台打印机和1台扫描仪。如果当迈进程A已获得1台打印机，进程B已获得了1台扫描仪，此时如果进程A申请扫描仪，进程B申请打印机，两个进程都会等着使用已经被另一进行占用设备，则此时两个进程就进入到了B状态。A.竞争 B.死锁C.互斥 D.同步133.进程是D。A.一种程序段 B.一种程序单位C.一种程序与数据集合 D.一种程序一次执行134.B不是引入进程直接目。A.多道程序同步在主存中运营 B.程序需从头至尾执行C.主存中各程序之间存在着互相依赖，互相制约关系D.程序状态不断地发生变化135.下面关于进程和程序论述中，错误是C。A.进程是程序执行过程，程序是代码集合B.进程是动态，程序是静态C.进程可为各种程序服务，而程序不能为各种进程服务D.一种进程是一种独立运营单位，而一种程序段不能作为一种独立运营单位136.下面进程状态转换，不能实现是D。A.运营状态转到就绪状态 B.就绪状态转到运营状态C.运营状态转到阻塞状态 D.就绪状态转到阻塞状态137.下面关于进程控制块说法中，错误是D。A.进程控制块对每个进程仅有一种B.进程控制块记录进程状态及名称等C.进程控制块位于主存储区内D.进程控制块内容、格式及大小均相似138.下面关于进程创立原语说法中，错误是A。A.创立原语作用是自行建立一种进程B.创立原语工作是为被创立进程形成一种进程控制块C.创立原语不能自己单独执行D.创立原语都是由进程调用执行139.进程同步与互斥主线因素是B。A.进程是动态 B.进程是并行C.进程有一种进程控制块 D.进程是互相依存140.下面关于临界区说法中，错误是C。A.进程中，访问临界资源程序是临界区B.同步进行临界区进程必要互斥C.进入临界区内两个进程访问临界资源时必要互斥D.在同一时刻，只容许一种进程进入临界区141.V操作词V(S)，S为一信号量，执行V操作时完毕如下操作：S=S+1若S>0，则继续执行；若S<0则C。A.将进程阻塞，插入等待队列B.将队列中一种进程移出，使之处在运营状态C.将队列中一种进程移出，使之处在就绪状态D.将进程变为挂起状态142.在进程调度算法中，D是动态优先数拟定算法。A.按进程使用资源进行调度 B.按进程在队列中档待时间进行调度C.准时间片轮转调度 D.非剥夺方式优先数调度143.作业控制块JCB内容不涉及C。A.作业状态 B.作业进入系统时间C.作业对进程规定 D.作业对资源规定144.设有一组作业，它们提交时刻及运营时间如下表所示：作业号提交时刻运营时间(分钟)19:007029:403039:5010410:105则在单道方式下，采用短作业优先调度算法，作业执行顺序为D。A.1,3,4,2 B.4,3,2,1C.4,1,2,3 D.1,4,3,2145.有如下三个作业：A1以计算为主，A2以输入/输出为主，A3是计算和输入/输出兼顾，在作业调度中，若采用优先级调度算法，为尽量使解决器和外部设备并行工作，则它们优先级从高到低排列顺序是C。A.A1，A2，A3 B.A2，A3，A1C.A3，A2，A1 D.A2，A1，A3146.下面几种选项中，作业里必定没有是D。A.程序 B.初始数据C.作业阐明书 D.通道程序147.作业调度程序不能无端或无限地迟延一种作业执行，这是作业调度A。A.公平性原则 B.平衡资源使用原则C.极大流量原则 D.必要条件148.作业调度是A。A.从输入进挑选作业进入主存B.从读卡机挑选作业进输入井C.从主存中挑选作业进程解决器D.从等待设备队列中选用一种作业进程149.顾客通过D直接在终端控制作业执行。A.C语言 B.汇编语言C.操作控制命令 D.作业控制语言150.在作业调度算法中，C兼顾了短作业与长作业。A.先来先服务 B.计算时间最短优先C.均衡调度 D.最高响应比优先151.某作业任务是某紧急事务解决，应选取C算法较为适当。A.先来先服务 B.短作业优先C.优先数调度 D.响应比高者优先152.既有三个同步到达作业J1、J2和J3，它们执行时间分别为T1、T2和T3，且T1<T2<T3，系统按单道方式运营且采用短作业优先算法，则其平均周转时间为C。A.T1+T2+T3 B.(T1+T2+T3)/3C.T1+2*T2/3+T3/3 D.T1/3+2*T2/3+T3154.在页式存储管理系统中，整个系统页表个数是C。A.1个 B.2个C.和装入主存作业个数相似 D.不拟定155.虚拟存储器是D。A.可提高计算机执行指令速度外围设备B.容量扩大了磁盘存储器C.事实上不存在存储器D.可以容纳总和超过主存容量、各种作业同步运营一种地址空间156.存储管理目是实现B。A.提高计算机资源运用率 B.扩充主存容量，并提高主存运用效率C.有效使用和分派外存空间 D.提高CPU执行效率157.在虚拟页式存储管理中，由于所需页面不在内存，而引起缺页中断属于A。A.程序性中断 B.I/O中断C.硬件中断 D.时钟中断158.一进程刚获得三个存储块使用权，若该进程访问页面顺序是{1,3,2,1,2,1,5,1,2,3}，当采用先进先出调度算法时，发生缺页次数是C次。A.4 B.5C.6 D.7159.内存共享目是B。A.扩大内存空间，提高内存空间运用效率B.节约内存空间，实现进程间通信，提高内存空间运用效率C.共享内存中程序和数据D.以上说法均不对160.如下主存管理方案中，不采用动态重定位是B。A.页式管理 B.固定分区C.可变分区 D.段式管理161.最易形成诸多小碎片可变分区别配算法是B。A.最先适应算法 B.最优适应算法C.最坏适应算法 D.以上都不对162.页式存储管理中，页表大小由A决定。A.作业所占页多少 B.操作系统C.计算机编址范畴 D.系统统一指定163.在提供虚拟存储系统中，顾客逻辑地址空间重要受C限制。A.主存大小 B.辅存大小C.计算机编址范畴 D.主存中顾客区域大小164.在分段管理中，C。A.以段为单位分派，每段

1.从工作角度看操作系统,可以分为单顾客系统、批解决系统、B和实时系统。A.单机操作系统 B.分时操作系统C.面向过程操作系统 D.网络操作系统2.在下列系统中，B是实时系统。A.计算机激光照排系统 B.航空定票系统C.办公自动化系统 D.计算机辅助设计系统3.操作系统是一种B。A.应用软件 B.系统软件C.通用软件 D.工具软件4.引入多道程序目在于A。A.充分运用CPU，减少CPU等待时间B.提高实时响应速度C.有助于代码共享，减少主、辅存信息互换量D.充分运用存储器5.已经获得除Ｃ以外所有运营所需资源进程处在就绪状态。A.存储器 B.打印机C.CPU D.内存空间6.进程调度核心问题：一是选取合理B，二是恰本地进行代码转换。A.时间片间隔 B.调度算法C.CPU速度 D.内存空间7.采用轮转法调度是为了A。A.各种终端都能得到系统及时响应B.先来先服务C.优先级较高进程得到及时调度D.需CPU最短进程优先8.在一段时间内只容许一种进程访问资源，称为C。A.共享资源 B.临界区C.临界资源 D.共享区9.并发性是指若干事件在B发生。A.同一时刻 B.同一时间间隔C.不同步刻 D.不同步间间隔10.在单一解决器上，将执行时间有重叠几种程序称为C。A.顺序程序 B.多道程序C.并发程序 D.并行程序11.程序运营时，独占系统资源，只有程序自身能变化系统资源状态，这是指B。A.程序顺序执行再现性 B.程序顺序执行封闭性C.并发程序失去封闭性 D.并发程序失去再现性12.引入多道程序技术后，解决器运用率Ｃ。A.减少了 B.有所改进C.大大提高 D.没有变化，只是程序执行以便了13.在单一解决器上执行程序，多道程序执行是在B进行。A.同一时刻 B.同一时间间隔内C.某一固定期刻 D.某一固定期间间隔内14.在进程通信中，常Ｃ通过变量、数组形式来实现。A.高档通信 B.消息通信C.低档通信 D.管道通信15.管道通信是以B进行写入和读出。A.消息为单位 B.自然字符流C.文献 D.报文16.当代操作系统两个基本特性是Ｃ和资源共享。A.多道程序设计 B.中断解决C.程序并发执行 D.实现分时与实时解决17.为了描述进程动态变化过程，采用了一种与进程相联系Ｃ系统，依照它来感知进程存在。A.进程状态字 B.进程优先数C.进程控制块 D.进程起始地址18.顺序执行和并发程序执行相比，Ｃ。A.基本相似 B.有点不同C.并发程序执行总体上执行时间快 D.顺序程序执行总体上执行时间快19.进程是B。A.与程序等效概念 B.执行中程序C.一种系统软件 D.存储在内存中程序20.进程具备并发性和A两大重要属性。A.动态性 B.静态性C.易用性 D.封闭性21.操作系统在控制和管理进程过程中，涉及到D这一重要数据构造，这是进程存在唯一标志。A.FCB B.FIFOC.FDT D.PCB22.在单解决机系统中，处在运营状态进程A。A.只有一种 B.可以有各种C.不能被挂起 D.必要在执行完后才干被撤下23.如果某一进程获得除CP