《《计算机软件技术基础》试题及答案.doc》由会员分享，可在线阅读，更多相关《《计算机软件技术基础》试题及答案.doc（33页珍藏版）》请在金锄头文库上搜索。
1、计算机软件技术基础试题1 .线性表的链式存储结构与顺序存储结构相比优点是CD。2. 所有的操作算法实现简单B.便于随机存取便于插入和删除D.便于利用零散的存储器空间线性表是具有n个C的有限序列。3. A.表元素B.字符C.数据元素数据项E.信息项若长度为n的线性表采用顺序存储结构，在其第I个位置插入一个新元素的算法的时间复杂度为C(1WIWn+1)A.0(0)B.0(1)C.0(n)D.O(n2)设A是一个线性表(ai,a2,.,an),采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为，平均每删除一个元素需要移动的元素个数为A；若元素插在旬与as之间(0WIWn.1
2、)的概率为四，则平均每(+1)插入一个元素所要移动的元素个数为c:A.4. 2c2+1c3+14下列函数中，按它们在is时的无穷大阶数，最大的是D。A.lognB.nlognC.2n/2D.n!将下图所示的s所指结点加到p所指的结点之后，其语句应为：Dnextnext5. s-next=p+1;p-next=s;(*p).next=s;(*s).next=(*p).next;s-next=p-next;p-next=s-next;s-next=p-next;p-next=s;将两个务有n个元素的有序表归并为一个有序表时，其最少的比较次数是AoA.nB.2n-1C.n-1D.2n下面的程序段是合
3、并两个无头结点链表(ha和hb)为一个无头结点链表ha的过程，作为参数的两个链表都是按结点的data域由大到小链接的。合并后新链表的结点仍按此方式链接。清填写下述空框，使程序能正确运行。#defineNULLOtypedefstructnode(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!=N
4、ULL&hb!=NULL)if(ha-data=hb-data)(p-next=(1)P=(2)；(3)；/*较大的元素先插入7else(p-next=4P=(5)；(6)；)if(ha=NULL)(7)if(hb=NULL)(8)ha=h-next;free(h);参考答案：(1)hahb(2)p-next(5)p-next(3)ha=ha-next(6)hb=hb-next(8)p-next=ha(7)p-next=hb9.如果表A中所有元素(ai,a2,.,an)与表B的一个顺序子表(bk,bk+i,.bk+n-i)完全相同(即ai=bk,a2=bk+i,.an=bk+n-i),则称表A
5、包含在表B中。设ha,hb为带头结点的单链表，分别表示有序表A和B,下面的函数用丁判别表A是否包含在表B中，若是，则返回true,否则返回falseo(提示：用递归实现)#definetrue1#definefalse0#defineNULLOtypedefstructnode(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
6、);else(4);(5)；参考答案：10. if(pa=NULL)return(true)pb!=NULL&pa-data=pb-datareturn(inclusion(pa,pb)pb=pb-next;return(false)在本题的程序中，函数createjinkjist(n)建立一个具有n个结点的循环链表:函数josephus(n,l,m)对由createjinkjist(n)所建立的具有n个结点的循环链A按一定的次序逐个输出，并删除福表市的所有结点。参数n(n0)指明循环链表的结点个数，参数l(1WIWn)指明起始结点，参数m(m0是步长)，指明从起始结点或前次被删除并输出的结点
7、之后的第m个结点作为本次被输出并删除的结点。例如，对于下图所示的具有6个结点的循环链表，在调用josephus(6,3,2)后，将输出5,1,3,6,4,2。请在空框处填上适当内容，每框只填一个语句。#defineNULL0typedefstructnode(intdata;structnode*next;node,linklisttype;linklisttype*createjinkjist(intn)(linklisttype*head,*pf*q;intI;head=NULL;if(n0)head=(linklisttype*)malloc(sizeof(linklisttype);p
8、=head;for(l=1;ldata=I;q=(linklisttype*)malloc(sizeof(linklistttype);；)p-data=n;(3)/建立从尾链到首的环形结构/)return(head);)voidJosephus(intn,intj,intm)(linklisttype*p,*q;intj;p=createjinkjist(n);for(;l1;l-)p=p-next;；while(jn)for(l=1;lnext;(5)；printf(u%8dM,q-data);；free(q);j=j+1；)参考答案：11. p-next=q;P=q；p-next=hea
9、dj=0q=p-next;p-next=q-next在下列程序中，函数difference(A,B)用于求两集合之差C=A-B,即当且仅当e是A中的一个元素，且不是B中的元素时，e是C中的一个元素。集合用有序链表实现，用一个空链表表示一个空集合，表示非空集合的链表根据元素之值按递增排列，执行C=A-B之后，表示集合A和B的链表不变，若结果集合C非空,则表示它的链表应根据元素之值按递增序排列。函数append()用于在链表中添加结点。#include#defineNULLOtypedefstructnode(intdata;structnode*next;NODE;NODE*append(NOD
10、E*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(lastTA-data);A=A-next;)elseif(NA=A-next;B=B-next;)else(3);while(4)Nlast=append(last,A-data);A=A-next;)(
11、5)；last=C;C=C-next;free(last);return(C);)参考答案：12. A!=NULL&B!=NULLA-data=B-dataB=B-next;A!=NULLlast-next=NULL;阅读以下算法，填充空格，使其成为完整的算法。其功能是在一个非递减的顺序存储线性表中(从下标1处开始存储)，删除所有值相等的多余元素。#defineMAXSIZE30typedefstruct(intelemMAXSIZE;intlength;/*表长7)sqlisttype;voidexam21(sqlisttype*L)(intl,j;I=2,j=1；while(1)(if(L
12、-elemlL-elemj)(；)I+；)；参考答案：13. (1)ilengthjf(4)用单链表表示的链式队列的队头在链表的A位置。14. 链头B.链尾C.链中若用单链表表示队列，则应该选用B。带尾指针的非循环链表B.带尾指针的循环链表C.带头指针的非循环链表D.带头指针的循环链表在解决计算机主机与打印机之间速度不匹酎问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印，先放入打印缓冲区的数据先被打印。该缓冲区应该是一个B结构。15. A.堆栈B.队列C.数组D.线性表若用一个大小为6的数组来实现循环队列，且当前rear和front的值
13、分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为BoA.1和5B.2和4C.4和2D.5和1设栈的输入序列为1,2,10,输出序列为a2,.,aio,若a5=10,则由为COA.4B.8C.不确定D.7设栈的输入序列是1,2,3,4,则D不可能是其出栈序列。16. A.1243B.2134C.1432D.4312以下D是C语言中”abcd321ABCD”的子串。17. A.abedB.321ABC.abcABC”D.“21AB”若串S=nsoftwareM,其子串的数目是C。18. A.8B.37C.36D.9将一个A1:100,1:100的三对角矩阵，按
14、行优先存入一维数组B1:298中，A中元素A66,65(即该元素的下标)在B数组中位置k为B。19. A.198B.195C.197D.196设高为h的二又树只有度为。和2的结点，则此类二又树的结点数至少为至多为F。高为h的完全二又树的结点数至少为E至多为FoD.h+1H.2h+1_个结点。D.251A.2hB.2h-1C.2h+1E.2h1F.2h-1G.2h+1-1一棵有124个叶结点的完全二义树，最多有A.247B.248C.249若从二又树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二又树是CA.满二义树B.哈夫曼树堆D.二叉查找树前序遍历和中序遍历结果相同的二叉树为
15、:前序遍历和后序遍历结果相同的二又树为BB.只有根结点的二义树D.根结点无右孩子的二又树F.所有结点只有右孩子的二义树A.一般二叉树C.根结点无左孩子的二又树E.所有结点只有左孩子的二叉树具有n个结点的完全二义树，己经顺序存储在一维数组A1.n中，下面的算法是将A中顺序存储变为二义链表存储的完全二又树。请填写适当语句在下面的空格内，完成上述算法。#defineMAXSIZE30typedefstructbtnode(intdata;structbtnode*lchild,*rchild;BTN;voidcreatetree(BTN*p,intAQ,intI,intn)(；p-data=Al;if()；elsep-lchild=NULL;if(4)createtree();elsep-rchild=NULL;voidbtree(BTN*p,intA,intn)(
