计算机软件技术基础期末复习题docx.docx
- 文档编号:13328521
- 上传时间:2023-06-13
- 格式:DOCX
- 页数:88
- 大小:196.14KB
计算机软件技术基础期末复习题docx.docx
《计算机软件技术基础期末复习题docx.docx》由会员分享,可在线阅读,更多相关《计算机软件技术基础期末复习题docx.docx(88页珍藏版)》请在冰点文库上搜索。
计算机软件技术基础期末复习题docx
《计算机软件技术基础》复习题1
1.线性表的链式存储结构与顺序存储结构相比优点是。
A.所有的操作算法实现简单B,便于随机存取
C.便于插入和删除D.便于利用零散的存储器空间
2.线性表是具有n个的有限序列。
A.表元素B.字符C,数据元素
D.数据项E.信息项
3.若长度为n的线性表采用顺序存储结构,在其第I个位置插入一个新元素的算法的时间复杂度为。
(lWIWn+1)
A.0(0)B.0
(1)
C.0(n)D.0(n2)
4.设A是一个线性表(&,如,…,缶),采用顺序存储结构,则在等概率的前提下,平均每插入一个元素需要移动的元素个数为,平均每删除一个元素需要移动的元素个数为
:
若元素插在辅与眦之间(OWIWn-1)的概率为2("—Z),则平均每插入一个n(n+1)
元素所要移动的元素个数为;
n—1n
A.B.一
22
八2%+13〃+1
C.D.
34
5.下列函数中,按它们在"T3时的无穷大阶数,最大的是.
A.log/?
B.nlog/7
C.2n/2D.n!
6.
将下图所示的s所指结点加到p所指的结点之后,其语句应为:
next
A.s->next=p+l;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.nB.2n~l
C.n-1D.2n
8.下面的程序段是合并两个无头结点链表(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=;
⑶;
else(
p->next=(4)
P=(5)
⑹;
}
if(ha==NULL)(7)
if(hb=NULL)(8)
ha=h~>next;
free(h);
9.如果表A中所有元素(ai,a2,•••,an)与表B的一个顺序子表(bk,bk+i,..・bk+n-i)完全相同(即a】=bk,a2=bk+i,・・・an=bm),则称表A包含在表B中。
设ha,hb为带头结点的单链表,分别表示有序表A和B,下面的函数用于判别表A是否包含在表B中,若是,则返回true,否则返回falseo(提示:
用递归实现)^definetrue1#definefalse0^defineNULL0typedefstructnode(intdata;
structnode*next;
}node,linklisttype;
intinclusion(linklisttype*ha,linklisttype*hb)(linklisttype*pa,*pb;
pa=ha-〉next;
pb=hb~>next;
⑴;
while(
(2))
if(pa->data=pb~>data)(3)
else(4)
(5);
10.在本题的程序中,函数ereate_link_list(n)建立一个具有n个结点的循环链表;函数josephus(n,I,m)对由create_link_list(n)所建立的具有n个结点的循环链表按一定的次序逐个输出,并删除链表中的所有结点。
参数n(n>0)指明循环链表的结点个数,参数1(1WlWn)指明起始结点,参数m(m>0是步长),指明从起始结点或前次被删除并输出的结点之后的第m个结点作为本次被输出并删除的结点。
例如,对于下图所示的具有6个结点的循环链表,在调用josephus(6,3,2)后,将输出5,1,3,6,4,2。
请在空框处填上适当内容,每框只填一个语句。
^defineNULL0
typedefstructnode(
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=l;I<=n-l;I++)(/*此循环用于建立一个链表,链表的内容从1至nT*/
p->data=I;
q=(linklisttype*)malloc(sizeof(linklistttype));
⑴;
⑵;
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;
⑷;
while(j for(1=1;I<=m-1;I++)p=p->next; ⑸; printf("%8d”,q-〉data); ⑹; free(q); j=j+l; } } 11.在下列程序中,函数difference(A,B)用于求两集合之差C=A-B,即当且仅当e是A中的一个元素,且不是B中的元素时,e是C中的一个元素。 集合用有序链表实现,用一个空链表表示一个空集合,表示非空集合的链表根据元素之值按递增排列,执行C=A-B之后,表示集合A和B的链表不变,若结果集合C非空,则表示它的链表应根据元素之值按递增序排列。 函数append()用于在链表中添加结点。 ^include ^defineNULL0 typedefstructnode( intdata; structnode*next; )N0DE; 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~>datadata)( last=append(last,A->data); A=A->next; } else if( (2)){ A=A~>next; B=B->next; }else while((4))( last=append(last,A->data); A=A-〉next; } ⑸; last—C; C=C-〉next; free(last); return(C); } 12.阅读以下算法,填充空格,使其成为完整的算法。 其功能是在一个非递减的顺序存储线性表中(从下标1处开始存储),删除所有值相等的多余元素。 ftdefineMAXSIZE30 typedefstruct( intelem[MAXSIZE]; intlength;/*表长*/ }sqlisttype; voidexam21(sqlisttype*L){ inti,j; i=l,j=2; while( (1)){ if(L->elem[i]! =L->elem[j]){ if(j! =(i+l))⑵; L-〉length=L->length-(j-iT); ⑶; else{ ⑷; if(j>L->length)(5);} }} 13.用单链表表示的链式队列的队头在链表的位置。 A.链头B.链尾C.链中 14.若用单链表表示队列,则应该选用。 A.带尾指针的非循环链表B.带尾指针的循环链表 C.带头指针的非循环链表D.带头指针的循环链表 15.在解决计算机主机与打印机之间速度不匹配问题时,通常设置一个打印数据缓冲区,主 机将要输出的数据依次写入该缓冲区,而打印机则从该缓冲区中取出数据打印,先放入打印缓冲区的数据先被打印。 该缓冲区应该是一个结构。 A,堆栈B.队列 C,数组D.线性表 16.若用一个大小为6的数组来实现循环队列,且当前rear和front的值分别为0和3。 当从队列中删除一个兀素,再加入两个兀素后,rear和front的值分别为。 A.1和5B.2和4 C.4和2D.5和1 17.设栈的输入序列为1,2,•••,10,输出序列为ai,a2,•••,aio,若a5=10,则a? 为 A.4 B.8 C.不确定 D.7 18,设栈的输入序列是1,2,3,4,则. 不可能是其出栈序列。 A.1243 B.2134 C.1432 D.4312 19.以下— 是c语言中” abcd321ABCD”的子串。 A.abed B.321AB C."abcABC” D.“21AB” 20.若串S= •software”,其子串的数目是。 A.8 B.37 C.36 D.9 21.将一个A[l: 100,1: 100]的三对角矩阵,按行优先存入一维数组B[l: 298]中,A中元素A66,65(即该元素的下标)在B数组中位置k为。 A.198B.195C.197D.196 22.设高为h的二叉树只有度为0和2的结点,则此类二叉树的结点数至少为,至多为。 高为h的完全二叉树的结点数至少为,至多为。 A.2hB.2h-lC.2h+lD.h+1 E.2卜'F.2h-lG.2h+l-lH.2h+l 23.一棵有124个叶结点的完全二叉树,最多有个结点。 A.247B.248C.249D.251 24.若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序,则该二叉 树是0 A.满二叉树B.哈夫曼树 C.堆D.二叉查找树 25.前序遍历和中序遍历结果相同的二叉树为;前序遍历和后序遍历结果相同的二叉树为。 A,一般二叉树B.只有根结点的二叉树 C.根结点无左孩子的二叉树D.根结点无右孩子的二叉树 E,所有结点只有■左孩子的二叉树F.所有结点只有右孩子的二叉树 26.具有n个结点的完全二叉树,已经顺序存储在一维数组A[l..n]中,下面的算法是将A中顺序存储变为二叉链表存储的完全二叉树。 请填写适当语句在下面的空格内,完成上述算法。 #defineMAXSIZE30 typedefstructbtnode( intdata; structbtnode*lchild,*rchild; }BTN; voidcreatetree(BTN*p,intA[],intI,intn)( ⑴; p->data=A[I]; if( (2)) ⑶; else p->lchild=NULL; if((4)) createtree((5)); else p-〉rchild=NULL; } voidbtree(BTN*p,intA[],intn){ createtree(p,A,1,n); } 27.若在线性表中采用折半查找法查找元素,该线性表应该o A.元素按值有序B.采用顺序存储结构 C.元素按值有序,且采用顺序存储结构D.元素按值有序,且采用链式存储结构 28.在分块检索中,对256个元素的线性表分成16块最好,每块的最佳长度是 16;若每块的长度为8,其平均检索长度为21。 29.假定有K个关键字互为同义词,若用线性探测法把这K个关键字存入散列表中,至少要 进行次探测。 A.K-1次B.K次 C.K+1次D.K(K+l)/2次 30.在n个记录的有序顺序表中进行折半查找,最大的比较次数是L10g2〃」+1。 31.Hash技术广泛应用于查找过程,选择Hash函数的标准是和。 处理冲突的技术有优有劣,其共同标准是o 32.在下述排序算法中,所需辅助存储空间最多的是,所需辅助存储空间最小的是,平均速度最快的是。 A.快速排序B.归并排序C.堆排序 33.在文件局部有序或文件长度较小的情况下,最佳内部排序的方法是= A.直接插入排序B.冒泡排序C.简单选择排序 34.快速排序在最坏情况下时间复杂度是0(n2),比的性能差。 A.堆排序B.冒泡排序C.简单选择排序 35.若需在0(nlogn)的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方 法是o A.快速排序B.堆排序 C.归并排序D.希尔排序 36.如果只想得到1000个兀素组成的序列中第5个最小兀素之前的部分排序的序列,用方法最快o A.冒泡排序B.快速排序 C.希尔排序D.堆排序E.简单选择排序 37.以下结点序列是堆的为。 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.若要尽可能快地完成对实数数组的排序,且要求排序是稳定的,则应选。 A.快速排序B.堆排序 C.归并排序D.希尔排序 39.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较,然后将其放在 已排序序列的合适位置,该排序方法称为排序法。 A.插入排序B.交换排序 C.选择排序D.归并排序 40.直接插入排序在最好情况下的时间复杂度为o A.0(logn)B.0(n) C.O(nlogn)D.0(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 if((child ⑵; if(rootkey>list[child]) break; else( list[(3)]=list[child]; ⑷; list[(5)]=rootkey; 41.表是一种数据结构,链表是一种 (1)。 队列和栈都是线性表,栈的操作特性 是—⑵,队列的操作特性是—(3)。 今有一空栈S,对下列待进栈的数 据元素序列a,b,c,d,e,f依次进栈、进栈、出栈、进栈、进栈、出栈的操作,则此操作完成 后,栈S的栈顶元素为(4) 栈底兀素为一 ⑸。 供选答案: (1): A.非顺序存储线性表 B. 非顺序存储非线性表 C.顺序存储线性表 D. 顺序存储非线性表 ⑵: A.随机进出 B. 先进后出 C.先进先出 D. 出优于进 ⑶: A.随机进出 B. 先进后出 C.后进后出 D. 进优于出 ⑷: A.f B. C C.a D. b A. b C.aD.d 42.操作系统主要是对计算机系统全部 (1)进行管理,以方便用户、提高计算机 使用效率的一种系统软件。 它的主要功能有: 处理机管理、存储管理、文件管理、 (2)管 理和设备管理等。 Windows和Unix是最常用的两类操作系统。 前者是一个具有图形界面的窗口式的(3)系统软件,后者是一个基本上采用(4)语言编制而成的 的系统软件。 在(5)操作系统控制下,计算机能及时处理由过程控制反馈的信息 并作出响应。 供选答案: (1): A. 应用软件 B. 系统软硬件 C. 资源 D. 设备 ⑵: A. 数据 B. 作业 C. 中断 D. I/O (3): A. 分时 B. 多任务 C. 多用户 D. 实时 (4): A. PASCAL B. 宏 C. 汇编 D. C ⑸: A. 网络 B. 分时 C. 批处理 D. 实时 43.本程序从键盘读入整数,并按从大到小的顺序输出输入整数中互不相等的那些整数。 程序一边读入整数,一边构造一个从大到小顺序链接的链表,直至不能从键盘读入整数,然后顺序输出链表上各表元的整数值。 主函数每读入一个整数,就调用函数insert(),函数insert()将还未出现在链表上的整数按从大到小的顺序插入到链表中。 为了插入方便,链表在表首有一个辅助表元。 阅读下列C代码,在(n)处填入相应的字句以完成上述功能。 ftinclude #include typedefstructnode( intval; structnode*next; }NODE; voidinsert(NODE*list,intx)( NODE*u,*v,*p; u=list: v=u—〉next; /*寻找插入位置*/ /*判断是否要插入表元*/ /*生成新表元*/ while( (1)&&x } if((v==NULL|| (2)){ p=(NODE*)malloc(sizeof(NODE));p->val=x; ⑶=v;(4)=p;/*插入新表元*/ main()( intx; NODE*head,*p; /*首先建立只有辅助表元的空链表*/ head=(NODE*)malloc(sizeof(NODE)); (5)二NULL; printf("EnterIntegers: \n,,); /*反复读入整数插入链表*/ /*输出链表*/ while(scanf(,&x)==1) insert(head,x); for(p=head->next;p! 二NULL;p=p->next) printf("%d\t”,p->val); printf("\n”); 44.计算机数据处理的对象是具有不同结构的各种数据,可以访问的最小数据信息单位是⑴,可以引用的最小命名数据单位是— (2)。 线性表是最简单的一种数据结构,有顺序和链接两种存储方式。 线性表按链接方式存储时,每个结点的包括(3)两部分。 线性表的查找有⑷和(5)两种,但(5)只能用于顺 序存储的情况。 供选答案: (1): A. 数字 B. 字符 C. 数据元素 D. 数据项 (2): A. 结点 B. 记录 C. 数据元素 D. 数据项 ⑶: A. 数据值与符号 B. 数据与指针 C. 数据与表名 D. 头地址与尾地址 (4): A. 随机查找 B. 顺序查找 C. 二分法查找 D. 浏览 ⑸: A. 随机查找 B. 顺序查找 C. 二分法查找 D. 浏览 45.本程序用于从链盘读入整数,插入到链表,或从链表删除一个整数。 阅读下面的C代码,将应填入(n)处的字名写在答卷的对应栏内。 ftinclude ^include typedefstructnode( intval; structnode*next; }NODE; NODE*ins(NODE*list,intx)(/*将x按从小到大的次序插入链表*/ NODE*u,*v=list,*p; for(;v! =NULL&&x =NULL&&x=v->val)return(list);/*已有,被忽略*/ p=(NODE*)malloc(sizeof(NODE));p->val=x;/*生成新表元*/if(v==list)list=p; else (1); ⑵; returnlist; } NODE*del(NODE*list,intx){/*从链表中删除值为x的表元*/ NODE*u,*v; for(v=list;v! =NULL&&x if(v! =NULL&&x==v->val)(/*找到值为x的表元*/ if(v==list)list=list->next; else(3); ⑷;/*释放空间*/ } elseprintf("没有找到! \n”); return(list); } main()( intx,ans; NODE*list=NULL,*p; while (1)( printf("\n输入1: 将整数插入到链表。 \n输入2: 从链表删除一个整数。 \n”);printf("其它整数,结束程序。 \n\t请输入选择! ”); scanf(%d
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机软件 技术 基础 期末 复习题 docx