数据结构期中试题(答案).doc

《数据结构期中试题(答案).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、在以下题目中任意选择做1．求下列程序段的时间复杂度<每小题5分）<1）for(i=0。ifor(j=0。jfor(k=0。kｘ＝ｘ＋delta；O(n3><2）i=1；while(ii=i*2。O(log2n><3）i=n*n。while(i!=1>i=i/2。O(log2n2>2.按增长率从小到大顺序排列以下函数<5分）n,n-n3+7n5,nlogn,2n/2,n3,logn,n1/2+logn,(3/2>n,n!,n2+lognb5E2RGbCAP答：logn，n1/2+logn，n,nlogn,n2+logn,n3,n-n3+7n

2、5,2n/2,(3/2>n,n!p1EanqFDPw3．问答题(1>．对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度分别为多少？(3分>答：访问节点复杂度为O(1>,增加、删除结点的时间复杂度为O(n>。(2>．若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？(5分>DXDiTa9E3d答:采用顺序存储结构.因为顺序存储存取操作复杂度为O(1>,效率高.(3>．双向链表中有两个指针域，llink和rlink，分别指回前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，请写出其插入操

3、作序列。<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答：.若串S1=”ABCDEFGHIJK”,S2=”9898”,S3=”###”执行replace(S1,0，substr(S

4、1,length(S2>,length(S3>>,S3>后，其结果是什么？<5分）xHAQX74J0X5/5答:ABCD###HIJK<7）．假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，请求出Loc[5，5]的值。<5分）LDAYtRyKfE答：Loc(5,5>=10+((5-1>*100+(5-1>>*2=818<8）.有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是多少？<5分）Zzz6ZB2Ltk非0元素占10*3*2=60字节；控制结构占3*2=

5、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

6、=q____；r=q。q=q->next。}}if(p==NULL>r->next=q。<4）if(q==NULL>r->next=p____。}<以下选择题每题4分）(2>．一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是输入序列为ABC，可以变为CBA时，经过的栈操作为

7、op,push,push,pop,popSixE2yXPq5(4>栈和队列的共同点是<1）已知两个单链表A和B,其头指针分别为heada和headb，编写一个函数从单链表A中删除自第i个元素起的共le