计算机软件技术基础试题1.线性表的链式存储结构与顺序存储结构相比优点是 CD ; A. 所有的操作算法实现简单 B. 便于随机存取 C. 便于插入和删除D. 便于利用零散的存储器空间 2.线性表是具有n 个 C 的有限序列;A. 表元素B. 字符C. 数据元素D. 数据项E. 信息项3.若长度为n 的线性表采用顺序存储结构,在其第I 个位置插入一个新元素的算法的时间复杂度为 C ;1≤I ≤n+1 A. O0 B. O1 C. OnD. On 24.设A 是一个线性表a 1,a 2,…,a n ,采用顺序存储结构,则在等概率的前提下,平均每插入一个元素需要移动的元素个数为 B ,平均每删除一个元素需要移动的元素个数为 A ；若元素插在a i 与a i+1之间0≤I ≤n-1的概率为)1()(2+-n n i n ,则平均每插入一个元素所要移动的元素个数为 C ；A. 21-n B. 2n C. 312+nD. 413+n5.下列函数中,按它们在∞→n 时的无穷大阶数,最大的是 D ;A. log nB. nlog nC. 2n/2D. n6.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-1C. n-1D. 2n8.下面的程序段是合并两个无头结点链表ha和 hb为一个无头结点链表ha的过程,作为参数的两个链表都是按结点的data域由大到小链接的;合并后新链表的结点仍按此方式链接;请填写下述空框,使程序能正确运行;define NULL 0typedef struct node{int data;struct node next;}node, linklisttype;void combinelinklisttype ha, linklisttype hb{linklisttype h, p;h = linklisttype mallocsizeoflinklisttype;h->next = NULL;p = h;whileha = NULL && hb = NULLifha->data>=hb->data{ /较大的元素先插入/p->next = 1 ;p = 2 ;3 ;}else{p->next = 4 ;p = 5 ;6 ;}ifha==NULL 7 ;ifhb==NULL 8 ;ha = h->next;freeh;}参考答案： 1 ha 2 p->next 3 ha=ha->next4 hb5 p->next6 hb=hb->next7 p->next=hb 8 p->next=ha9.如果表A中所有元素a1,a2,…,a n与表B的一个顺序子表b k,b k+1,…b k+n-1完全相同即a1=b k,a2=b k+1,…a n=b k+n-1,则称表A包含在表B中;设ha,hb为带头结点的单链表,分别表示有序表A和B,下面的函数用于判别表A 是否包含在表B中,若是,则返回true,否则返回false;提示：用递归实现define true 1define false 0define NULL 0typedef struct node{int data;struct node next;}node, linklisttype;int inclusionlinklisttype ha, linklisttype hb{linklisttype pa, pb;pa = ha->next;pb = hb->next;1 ;while 2ifpa->data=pb->data 3 ;else 4 ;5 ;}参考答案：1 ifpa==NULL returntrue2 pb=NULL && pa->data>=pb->data3 returninclusionpa, pb4 pb = pb->next;5 returnfalse10.在本题的程序中,函数create_link_listn建立一个具有n个结点的循环链表；函数josephusn,I,m 对由create_link_listn所建立的具有n个结点的循环链表按一定的次序逐个输出,并删除链表中的所有结点;参数nn>0指明循环链表的结点个数,参数I1≤I≤n指明起始结点,参数mm>0是步长,指明从起始结点或前次被删除并输出的结点之后的第m个结点作为本次被输出并删除的结点;例如,对于下图所示的具有6个结点的循环链表,在调用josephus6,3,2后,将输出5,1,3,6,4,2;请在空框处填上适当内容,每框只填一个语句;define NULL 0typedef struct node{int data;struct node next;}node, linklisttype;linklisttype create_link_listint n{linklisttype head, p, q;int I;head = NULL;ifn>0{head = linklisttype mallocsizeoflinklisttype;p = head;forI=1;I<=n-1;I++{ /此循环用于建立一个链表,链表的内容从1至n-1/p->data = I;q = linklisttype mallocsizeoflinklistttype;1 ;2 ;}p->data = n;3 ; /建立从尾链到首的环形结构/}returnhead;}void Josephusint n, int j, int m{linklisttype p, q;int j;p = create_link_listn;for;I>1;I-- p = p->next;4 ;whilej<n{forI=1;I<=m-1;I++ p = p->next;5 ;printf“%8d”,q->data;6 ;freeq;j=j+1;}}参考答案：1 p->next = q;2 p = q;3 p->next = head4 j=05 q=p->next;6 p->next = q->next11.在下列程序中,函数differenceA,B用于求两集合之差C=A-B,即当且仅当e是A中的一个元素,且不是B中的元素时,e是C中的一个元素;集合用有序链表实现,用一个空链表表示一个空集合,表示非空集合的链表根据元素之值按递增排列,执行C=A-B之后,表示集合A和B的链表不变,若结果集合C非空,则表示它的链表应根据元素之值按递增序排列;函数append用于在链表中添加结点;include <stdio.h>define NULL 0typedef struct node{int data;struct node next;}NODE;NODE appendNODE last, int x{last->next=NODE mallocsizeofNODE;last->next->data=x;returnlast->next;}NODE differenceNODE A ,NODE B{NODE C,last;C=last=NODE mallocsizeofNODE;while 1ifA->data < B->data{last=appendlast,A->data;A=A->next;}elseif 2 {A=A->next;B=B->next;}else3 ;while 4 {last=appendlast,A->data;A=A->next;}5 ;last=C;C=C->next;freelast;returnC;}参考答案：1 A=NULL & B=NULL2 A->data==B->data3 B=B->next;4 A=NULL5 last->next=NULL;12.阅读以下算法,填充空格,使其成为完整的算法;其功能是在一个非递减的顺序存储线性表中从下标1处开始存储,删除所有值相等的多余元素;define MAXSIZE 30typedef struct{int elemMAXSIZE;int length;/表长/}sqlisttype;void exam21sqlisttype L{int I,j;I=2,j=1;while 1 {ifL->elemI<>L->elemj{2 ;3 ;}I++;}4 ;}参考答案：1 i<=L->length23 j++;413.用单链表表示的链式队列的队头在链表的 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和4C. 4和2D. 5和117.设栈的输入序列为1,2,…,10,输出序列为a1,a2,…,a10,若a5=10,则a7为 C ;A. 4B. 8C.不确定D.718.设栈的输入序列是1,2,3,4,则 D 不可能是其出栈序列;A． 1243 B. 2134 C. 1432 D. 431219.以下 D 是C语言中”abcd321ABCD”的子串;A. abcdB. 321ABC. “abcABC”D. “21AB”20.若串S=”software”,其子串的数目是 C ;A. 8B. 37C. 36D. 921.将一个A1:100,1:100的三对角矩阵,按行优先存入一维数组B1:298中,A中元素A66,65即该元素的下标在B数组中位置k为 B ;A. 198B. 195C. 197D. 19622.设高为h的二叉树只有度为0和2的结点,则此类二叉树的结点数至少为 B ,至多为F ;高为h的完全二叉树的结点数至少为 E ,至多为 F ;A． 2h B. 2h-1 C. 2h+1 D.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 个结点的完全二叉树,已经顺序存储在一维数组A1..n 中,下面的算法是将A 中顺序存储变为二叉链表存储的完全二叉树;请填写适当语句在下面的空格内,完成上述算法; define MAXSIZE 30 typedef struct btnode{ int data;struct btnode lchild, rchild;}BTN;void createtreeBTN p,int A, int I,int n{ 1 ; p->data=AI; if 2 3 ; elsep->lchild=NULL;if 4 createtree 5 ; elsep->rchild=NULL; }void btreeBTN p ,int A,int n{ createtreep,A,1,n; }参考答案：1 p=BTN mallocsizeofBTN2 2I<=n3 createtreep->lchild,A,2I,n4 2I+1<=n5 p->rchild,A,2I+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. KK+1/2次30.在n 个记录的有序顺序表中进行折半查找,最大的比较次数是⎣⎦1log 2+n ;31.Hash 技术广泛应用于查找过程,选择Hash 函数的标准是 和 ;处理冲突的技术有优有劣,其共同标准是 ;32.在下述排序算法中,所需辅助存储空间最多的是 B ,所需辅助存储空间最小的是 C ,平均速度最快的是 A ; A.快速排序B. 归并排序C. 堆排序33.在文件局部有序或文件长度较小的情况下,最佳内部排序的方法是 A ;A. 直接插入排序B. 冒泡排序C. 简单选择排序34.快速排序在最坏情况下时间复杂度是On2,比 A 的性能差;A. 堆排序B. 冒泡排序C. 简单选择排序35.若需在Onlogn的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是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. OlognB. OnC. OnlognD. On241.下面函数是将任意序列调整为最大堆的算法,请将空白部分填上：将任意序列调整为最大堆通过不断调用adjust函数,即fori=n/2;i>0;i-- adjustlist, i, n;其中list为待调整序列所在数组从下标1开始,n为序列元素的个数;void adjustint list, int root, int n{/将以root为下标的对应元素作为待调整堆的根,待调整元素放在list数组中,最大元素下标为n/ int child,rootkey;rootkey = 1 ;child = 2root;whilechild < n{ifchild<n && listchild<listchild+12 ;ifrootkey > listchildbreak;else{list 3 =listchild;4 ;}}list 5 =rootkey;}参考答案：1 listroot2 child++;3 child/24 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. cC. aD. b5: A. b B. cC. aD. d答案：ABCBC42.操作系统主要是对计算机系统全部 1 进行管理,以方便用户、提高计算机使用效率的一种系统软件;它的主要功能有：处理机管理、存储管理、文件管理、 2 管理和设备管理等;Windows 和Unix是最常用的两类操作系统;前者是一个具有图形界面的窗口式的 3 系统软件,后者是一个基本上采用 4 语言编制而成的的系统软件;在 5 操作系统控制下,计算机能及时处理由过程控制反馈的信息并作出响应;供选答案：1: A. 应用软件 B. 系统软硬件C. 资源D. 设备2: A. 数据 B. 作业C. 中断D. I/O3: A. 分时 B. 多任务C. 多用户D. 实时4: A. PASCAL B. 宏C. 汇编D. C5: A. 网络 B. 分时C. 批处理D. 实时答案：CBBDD43.本程序从键盘读入整数,并按从大到小的顺序输出输入整数中互不相等的那些整数;程序一边读入整数,一边构造一个从大到小顺序链接的链表,直至不能从键盘读入整数,然后顺序输出链表上各表元的整数值;主函数每读入一个整数,就调用函数insert,函数insert将还未出现在链表上的整数按从大到小的顺序插入到链表中;为了插入方便,链表在表首有一个辅助表元;阅读下列C代码,在 n 处填入相应的字句以完成上述功能;include <stdio.h>include <malloc.h>define NULL 0typedef struct node{int val;struct node next;}NODE;void insertNODE list,int x{NODE u, v, p;u = list; v = u->next;while 1 && x < v->val{ /寻找插入位置/u=v;v=u->next;}ifv==NULL || 2 { /判断是否要插入表元/p = NODE mallocsizeofNODE;p->val = x; /生成新表元/3 = v;4 = p; /插入新表元/}}main{int x;NODE head, p;/首先建立只有辅助表元的空链表/head = NODE mallocsizeofNODE;5 =NULL;printf“Enter Integers:\n”;whilescanf“%d”,&x == 1 /反复读入整数插入链表/inserthead,x;forp=head->next;p=NULL;p=p->next /输出链表/printf“%d\t”,p->val;printf“\n”;}答案：1 v = NULL或v2 x > v->val 或 x = v->val3 p->next4 u->next5 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>typedef struct node{int val;struct node next;}NODE;NODE insNODE list, int x{ /将x按从小到大的次序插入链表/NODE u, v=list, p;for; v = NULL && x < v->val ; v = v->next;/寻找插入位置/ifv = NULL && x == v->val returnlist; /已有,被忽略/p = NODE mallocsizeofNODE;p->val=x; /生成新表元/ifv == list list = p;else 1 ;2 ;return list;}NODE delNODE list, int x{ /从链表中删除值为x的表元/NODE u, v;forv = list; v = NULL && x < v->valu; u=v;v=v->next;ifv = NULL && x == v->val{ /找到值为x的表元/ifv == list list = list->next;else 3 ;4 ; /释放空间/}else p rintf“没有找到\n”;returnlist;}main{int x,ans;NODE list=NULL, p;while1{printf“\n输入1：将整数插入到链表;\n输入2：从链表删除一个整数;\n”;printf“其它整数,结束程序;\n\t请输入选择”;scanf%d,&ans;if 5 return;printf“输入整数：”;scanf“%d”,&x;ifans==1 list=inslist,x;else list=dellist,x;forp=list;p=NULL;p=p->nextprintf“%4d”,p->val;}}答案：1 u->next = p;2 p->next = v3 u->next = v->next4 freev5 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. CDROMD. 寄存器答案：CDADB48. A 是信息的载体,它能够被计算机识别、存储和加工处理;A. 数据B. 数据元素C. 结点D. 数据项49.下列程序段的时间复杂度为 C ;fori=1;i<n;i++{y=y+1;forj=0;j<=2n;j++ x++;}供选答案：A. On-1B. O2nC. On2D. O2n+150.下面程序段的时间复杂度为 D ;i=1;whilei<=n i=i2;供选答案：A. O1B. OnC. On2D. Olog2n51.下面程序段的时间复杂度为 B ;a=0;b=1;fori=2;i<=n;i++{s=a+b;b=a;a=s;}供选答案：A. O1B. OnC. Olog2nD. On252.数据结构是一门研究非数值计算的程序设计问题中,计算机的 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. 12057.若已知一个栈的入栈序列是1,2,3,…,n,其输出序列为P1,P2,P3,…,P n,若P1=n,则P i为 C ;A. iB. n-iC. n-i+1D.不确定58.对于一个栈,给出输入项A,B,C;如果输入项序列由A,B,C所组成,则不可能产生的输出序列是A ;A. CABB. CBAC. ABCD. ACB59.设有如下的单链表的按序号查找的算法,其时间复杂度为 B ;LinkNode GetNodeLinklist head, int i{int j;ListNode p;P = head; j=0;whilep->next && j<i{p = p->next;j++;}ifi==jreturnp;elsereturnNULL;}供选答案：A. On2B. O2nC. On3D. Ologn60.二维数组A mn按行序为主顺序存放在内存中,每个数组元素占1个存储单元,则元素a ij的地址计算公式是 C ;A. LOCa ij = LOCa11+i-1m+j-1B. LOCa ij = LOCa11+j-1m+i-1C. LOCa ij = LOCa11+i-1n+j-1D. LOCa ij = LOCa11+j-1n+i-161.以下哪一个不是队列的基本运算 C ;A. 从队尾插入一个新元素B. 从队列中删除第i个元素C. 判断一个队列是否为空D. 读取队头元素的值62.在一个长度为n的顺序表中,向第i个元素之前插入一个新元素,需向后移动 B 个元素;A. n-iB. n-i+1C. n-i-1D. i63.从一个长度为n的顺序表中删除第i个元素时,需向前移动 A 个元素;A. n-iB. n-i+1C. n-i-1D. i64.在具有n个单元的顺序存储的循环队列中,假定front和rear分别为队首指针和队尾指针,则判断队空的条件是 B ;A. front=rear+1B. front=rearC. front+1=rearD. front=065.从一个具有n个结点的单链表中查找其值等于x的结点时,在查找成功的情况下,需平均比较 D 个结点;A. nB. n/2C. n-1/2D. n+1/266.一个栈的入栈序列是a,b,c,d,e,则栈不可能的输出序列是 C ;A. edcbaB. decbaC. dceabD. abcde67.栈结构通常采用的两种存储结构是 A ;A. 顺序存储结构和链表存储结构B. 散列方式和索引方式C. 链表存储结构和数组D. 线性存储结构和非线性存储结构68.判断一个顺序栈ST最多元素为mo为空的条件是 B ;A. ST->top<>0B. ST->top=0C. st->top<>moD. st->top==mo69.不带头结点的单链表head为空表的判定条件是 A ;A. head==NILLB. head->next==NULLC. head->next==headD. 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.假设双向链表结点的类型如下：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”,函数conx,y返回x和y串的连接串,subss,I,j返回串s的从序号i的字符开始的j个字符组成的子串,lens返回串s的长度,则consubs1,2,lens2,subs1,lens2,2的结果是 D ;A. BCDEFB. BCDEFGC. BCPQRSTD. BCDEFEF75.常对数组进行的两种基本操作是 C ;A. 建立和删除B. 索引和修改C. 查找和修改D. 索引和查找76.稀疏矩阵一般的压缩存储方法有两种,即Ｃ ;A. 二维数组和三维数组B. 三元组和散列C. 三元组和十字链表D. 散列和十字链表77.对下图所示的二叉表,按先根次序遍历得到的结点序列为 B ;A. ABCDHEIFGB. ABDHIECFGC. HDIBRAFCGD. HIDBEFGAC78.在一棵二叉树上,度为0的结点个数为n0,度为2的结点数为n2,则n0= A ;A. n2+1B. n2-1C. n2D. n2/279.某二叉树前序遍历结点的访问顺序是ABCDEFG,中序遍历结点的访问顺序是CBDAFGE,则其后序遍历结点的访问顺序是 A ;A．CDBGFEA B. CDGFEABC. CDBAGFED. CDBFAGE80.在下列存储形式中, D 不是树的存储形式;A. 双亲表示法B. 孩子链表表示法C. 孩子兄弟表示法D. 顺序存储表示法81. 已知一棵二叉树的中序序列为cbedahgijf,后序序列为cedbhjigfa,则该二叉树为B ;82. 已知一棵权集W={2,3,4,7,8,9}的哈夫曼树,其加权路径长度WPL为Ｃ ;A. 20B. 40C. 80D. 16083.已知一棵度为m的树中有n1个度为1的结点,n2个度为2的结点,…,n m个度为m的结点,问这棵树中叶子结点为Ｃ ;A. 1+n i I-1B. 1+n i I+1C. n1+n2+…+n mD. m·n m84.如下图所示的4棵二叉树中, Ｃ不是完全二叉树;85.设高度为h的二叉树上只有度为0或度为2的结点,则此类二叉树中所包含的结点数至少为B ;A. 2hB. 2h-1C. 2h+1D. h+186.如下图所示的二叉树的中序遍历序列是Ｃ ;A. abcdgefB. dfebagcC. dbaefcgD. defbagc87.已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,则其前序遍历序列为D ;A. acbedB. decabC. deabcD. cedba88.如果T2是由有序树T转换而来的二叉树,则T中结点的前序就是T2中结点的 A ;A. 前序B. 中序C. 后序D. 层次序89.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历;这里,我们把由树转化得到的二叉树叫做这棵树对应的二叉树;下面结论正确的是A ;A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同B. 树的先根遍历序列与其对应的二叉树的后序遍历序列相同C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同D. 以上均不对90. 深度为5的二叉树至多有Ｃ个结点;A. 16B. 32C. 31D. 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+mB. h+m=2nC. m=h-1D. n=2h-1 95.如果某二叉树的前序为stuwv,中序为uwtvs,则该二叉树后序为 Ｃ ;A. uwvtsB. vwutsC. wuvtsD. wutsv96.设待排序的记录为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,9098.用快速排序的方法对包含几个关键字的序列进行排序,最坏情况下,执行的时间为 D ; A. OnB. Olog 2nC.Onlog 2nD. On 299.在所有排序方法中,关键码即关键字比较的次数与记录的初始排列次序无关的是 D ; A. 希尔排序B. 冒泡排序C. 直接插入排序D. 直接选择排序100.在归并排序过程中,需归并的趟数为 Ｃ ; A. nB. nC. ⎣⎦n n 2logD. ⎣⎦n 2log101.一组记录的排序代码为{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,202 20,15,21,25,47,27,68,35,843 15,20,21,25,35,27,47,68,844 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=bB. 总有s>bC. 总有s<bD. 与k值大小有关111. 如果要求一个线性表既能较快地查找,又能适应动态变化的要求,则可采用的方法是A ;A. 分块法B. 顺序法C. 二分法D. 哈希法112. 哈希表的地址区间为0-17,哈希函数为Hk=k mod 17;采用线性探测法处理冲突,并将关键字序列{26,25,72,38,8,18,59}依次存储到哈希表中;那么,元素59存放在哈希表中的地址是 D ; A. 8 B. 9C. 10D. 11113. 哈希表的地址区间为0-17,哈希函数为Hk=k mod 17;采用线性探测法处理冲突,并将关键字序列{26,25,72,38,8,18,59}依次存储到哈希表中;如果要访问元素59,则需要的搜索次数是Ｃ ;A. 2B. 3C. 4D. 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. CPUD. 中断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. 网络操作系统。
