搜索
1/5在以下题目中任意选择做1．求下列程序段的时间复杂度每小题5分）1）for(i=0。in。i++for(j=0。ji。j++for(k=0。kj。k++ｘ＝ｘ＋delta；O(n32）i=1；while(ini=i*2。O(log2n3）i=n*n。while(i!=1i=i/2。O(log2n22.按增长率从小到大顺序排列以下函数5分）n,n-n3+7n5,nlogn,2n/2,n3,logn,n1/2+logn,(3/2n,n!,n2+lognb5E2RGbCAP答：logn，n1/2+logn，n,nlogn,n2+logn,n3,n-n3+7n5,2n/2,(3/2n,n!p1EanqFDPw3．问答题(1．对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度分别为多少？(3分答：访问节点复杂度为O(1,增加、删除结点的时间复杂度为O(n。(2．若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？(5分DXDiTa9E3d答:采用顺序存储结构.因为顺序存储存取操作复杂度为O(1,效率高.(3．双向链表中有两个指针域，llink和rlink，分别指回前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，请写出其插入操作序列。6分）RTCrpUDGiT答:q-rlink=p。q-llink=p-llink,p-llink-rlink=q。p-llink=q。5PCzVD7HxA这是答案之一，还可以有其它答案）(4．在单链表和双向链表中，能否从当前结点出发访问到任何一个结点?(3分答：单链表不行，双向链表可以。(5．给出循环队列中元素个数的计算式(设队最大长度为N,队首指针FRONT，队尾指针REAR。5分）jLBHrnAILg答：R-F+N）%N(6.若串S1=”ABCDEFGHIJK”,S2=”9898”,S3=”###”执行replace(S1,0，substr(S1,length(S2,length(S3,S3后，其结果是什么？5分）xHAQX74J0X答:ABCD###HIJK7）．假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占22/5个存储单元，基地址为10，请求出Loc[5，5]的值。5分）LDAYtRyKfE答：Loc(5,5=10+((5-1*100+(5-1*2=8188）.有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是多少？5分）Zzz6ZB2Ltk非0元素占10*3*2=60字节；控制结构占3*2=6字节。共66字节。4．填空与选择(1．以下程序采用链表合并的方法，将两个已排序的单链表合并成一个链表而不改变其排序性升序），这里两链表的头指针分别为p和q.(每空3分dvzfvkwMI1voidmergelink(SLNode*p,SLNode*q{SLNode*h,*r。1）_h=(SLNode*malloc(sizeof(SLNode。_____h-next=NULL。r=h。while((p!=NULL&&(q!=NULL{if(p-data=q-data{2）r-next=p___；r=p。p=p-next；}else{3）r-next=q____；r=q。q=q-next。}}if(p==NULLr-next=q。4）if(q==NULLr-next=p____。}以下选择题每题4分）(2．一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是B）。A.23415B.54132C.23145D.15432rqyn14ZNXI(3输入序列为ABC，可以变为CBA时，经过的栈操作为B）A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popEmxvxOtOcoC.push,push,pop,pop,push,popD.push,pop,push,push,pop,popSixE2yXPq5(4栈和队列的共同点是C）。A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点5）对稀疏矩阵进行压缩存储目的是C）A．便于进行矩阵运算B．便于输入和输出C．节省存储空间D．降低运算的时间复杂度5.程序设计题(程序题主要看其思路是否正确1）已知两个单链表A和B,其头指针分别为heada和headb，编写一个函数从单链表A中删除自第i个元素起的共len个元素，然后将单链表A插入到单链表B的第j个元素之前。15分）6ewMyirQFLintDelInsertSLNode*heada，SLNode*headb，inti，intj，len）kavU42VRUs{3/5SLNode*p,*q,*u。intk。ifi1||len1||j1）{printf“参数错误\n”）；Return0；}p=heada；∥k=0；whilep!=null&&ki-1）{k++；p=p-next；}ifp==null）{printf“给的%d太大\n”,i）；return0；}q=p-next；k=0；whileq!=null&&klen）{k++；u=q。q=q-next；freeu）；}∥删除结点，后移指针。ifklen）{printf“给的%d太大\n”,len）；return0；}p-next=q；∥A链表删除了len个元素。if(heada-next!=null∥heada-next=null说明链表中结点均已删除，无需往B表插入y6v3ALoS89{whilep-next!=null）p=p-next；∥找A的尾结点。q=headb；∥q为链表B的工作指针。k=0；∥计数whileq!=null&&kj-1）∥查找第j个结点。{k++；q=q-next；}∥查找成功时，q指向第j-1个结点ifq==null）{printf“给的%d太大\n”,j）；return0；}p-next=q-next；∥将A链表链入q-next=heada-next；∥A的第一元素结点链在B的第j-1个结点之后}freeheada）；∥释放A表头结点。}∥算法结束。(2利用两个栈sl,s2模拟一个队列时，编程实现用栈的运算实现队列的插入，删除以及判队空运算。15分）M2ub6vSTnP(1intenqueue(SeqStack*s1,SeqStack*s2,elemtpx0YujCfmUCw//s1是容量为n的栈，栈中元素类型是elemtp。本算法将x入队列，若入队列成功返回1，否则返回0。eUts8ZQVRd{if(s1-top==n&&StackNotEmpty(s2{printf(“栈满”。return(0。}//s1满s2非空,这时s1不能再入栈。if(s1-top==n&&!StackNotEmpty(s2//若s2为空，先将s1退栈,元素再压栈到s2。sQsAEJkW5T{while(StackNotEmpty(s1{POP(s1,x。PUSH(s2,x。}PUSH(s1,x。return(1。//x入栈，实现了队列元素的入队。}(2voiddequeue(SeqStack*s1,SeqStack*s2,elemtpxGMsIasNXkA//s2是输出栈，本算法将s2栈顶元素退栈，实现队列元素的出队。4/5{if(StackNotEmpty//栈s2不空，则直接出队。{POP(s2,x。printf(“出队元素为”,x。}else//处理s2空栈。if(!StackNotEmpty(s1{printf(“队列空”。return。}//若输入栈也为空，则判定队空。TIrRGchYzgelse//先将栈s1倒入s2中，再作出队操作。{while(StackNotEmpty(s1{POP(s1,x。PUSH(s2,x。}POP(s2,x。//s2退栈相当队列出队。printf(“出队元素”，x。}}//结束算法dequue。(3intqueue_empty(//本算法判用栈s1和s2模拟的队列是否为空。{if(!StackNotEmpty(s1&&!StackNotEmpty(s2return(1。//队列空。7EqZcWLZNXelsereturn(0。//队列不空。}3）设s、t为两个字符串，分别放在两个一维数组中，m、n分别为其长度，请编写一个函数判断t是否为s的子串。如果是，输出子串所在位置第一个字符），否则输出0。(10分lzq7IGf02Eintindex(chars[],chart[],intm,intn//字符串s和t用一维数组存储，其长度分别为m和n。本算法求字符串t在字符串s中的第一次出现，如是，输出子串在s中的位置，否则输出0。zvpgeqJ1hk{inti=0,j=0。while(i=m-n&&j=n-1if(s[i]==t[j]{i++。j++。}//对应字符相等，指针后移。else{i=i-j+1。j=0。}//对应字符不相等，I回溯，j仍为0。if(i=m-n&&j==n{printf(“t在s串中位置是%d”,i-n+1。return(i-n+1。}//匹配成功NrpoJac3v1elsereturn(0。//匹配失败}//算法index结束6．设有下列递归算法:intvol(intn{if(n==0return0。elsereturnvol(n-1+2。}如该函数被调用时，参数n值为3,函数调用结束时返回值为多少?用图示描述函数的递归调用执行过程。(12分1nowfTG4KI函数返回值是65/5vol(3)vol(2)return2+vol(2)vol(2)vol(1)return2+vol(1)vol(1)vol(0)return2+vol(0)vol(0)return0vol(3)0246申明：所有资料为本人收集整理，仅限个人学习使用，勿做商业用途。