《计算机软件技术基础》复习答案

《计算机软件技术基础》复习题——答案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)的概率为)1()(2nnin，则平均每插入一个元素所要移动的元素个数为C；A.21nB.2nC.312nD.413n5.下列函数中，按它们在n时的无穷大阶数，最大的是D。A.lognB.nlognC.2n/2D.n!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.nB.2n-1C.n-1D.2n8.下面的程序段是合并两个无头结点链表(ha和hb)为一个无头结点链表ha的过程，作为参数的两个链表都是按结点的data域由大到小链接的。合并后新链表的结点仍按此方式链接。请填写下述空框，使程序能正确运行。spnextnextnext#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(n0)指明循环链表的结点个数，参数I(1≤I≤n)指明起始结点，参数m（m0是步长），指明从起始结点或前次被删除并输出的结点之后的第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(n0){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(;I1;I--)p=p-next;(4);while(jn){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()用于在链表中添加结点。#includestdio.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-dataB-data){last=append(last,A-data);A=A-next;}elseif((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=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和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．1243B.2134C.1432D.431219.以下D是C语言中”abcd321ABCD”的子串。A.abcdB.321ABC.“abcABC”D.“21AB”20.若串S=”software”，其子串的数目是C。A.8B.37C.36D.921.将一个A[1:100,1:100]的三对角矩阵，按行优先存入一维数组B[1:298]中，A中元素A66,65(即该元素的下标)在B数组中位置k为B。A.198B.195C.197D.19622.设高为h的二叉树只有度为0和2的结点，则此类二叉树的结点数至少为B，至多为F。高为h的完全二叉树的结点数至少为E，至多为F。A．2hB.2h-1C.2h+1D.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个结点的完全二叉树，已经顺序存储在一维数组A[1..n]中，下面的算法是将A中顺序存储变为二叉链表存储的完全二叉树。请填写适当语句在下面的空格内，完成上述算法。#defineMAXSIZE30typedefstructbtnode{intdata;structbtnode*lchild,*rchild;}BTN;voidcreatetree(BTN*p,intA[],intI,intn){(1);p-data=A[I];if((2))(3);elsep-lchild=NULL;if((4))createtree((5));elsep-rchild=NULL;}voidbtree(BTN*p,intA[],intn){createtree(p,