数据结构算法题

前五章习题算法2.2算法设计题设计一个算法从一给定的有序顺序表L中删除元素值在X到Y(X〈=Y)之间的所有元素，要求以较高的效率实现，要求算法的空间复杂度为0(1)voiddelete(SqList&L,ElemTypex,ElemTypey){mti=0.k=0;while(i<L.length)(if(L.elem[i]>=x&&L.elem[i]<=y)k++;//记录被删记录的个数elseL.elem[i-k]=L.elem[i];//前移k个位置1++;)L.length=L.length-k;}2设一个有序表L,含有2n个整数，其中n个位负数,n个为正数，设计一个算法将L中所有元素按正负相间排列.要求算法的空间复杂度为0(1),时间复杂度为O(n)voidmove(SqList&L){mti=OJ=L.length-l;mttemp;while(Kj)//使得正数都在前半部分，负数都在后半部分(wliile(i<j&&L.elem[i]>O)i++;while(i<j&&L.elem[j]<0)j—;if(ivj)〃交换L.elem[i](负数)和L.elem[j](正数)(temp=L.elem[i];L.elem[i]=L.elemIj];L.elemlj]=temp;}1=1;while(i<L.lengtli'2)〃通过交换使得正负数相间(j=L.length-2;temp=L.elem[i];L.elem[i]=L.elem[j];L.elem|j]=temp;i=i+2;J=J・2；)}3,假设一两个元素依之二值递增有序排列的线性表A和B分别表示两个集合(同一元素值各不相同)，要求分别设计求A和B交并差集的算法,要求结果线形表中的元素依值递增有序排列，试对顺序表实现上述操作.交集：voidintersection(SqListA.SqListB,SqList&C){hiti=O,j=O,k=O;wliile(i<A.length&&j<B.length){if(A.elem[i]<B.elem[j])i++;elseif(A.elem[i]>B.elem[j])j++;else{C.elem[k]=A.elem[i];k++；i++j-H-；)//共同的元素}C.length=k;}并集：voidUnion(SqListA,SqListB,SqList&C){hiti=O,j=O,k=O;wliile(i<A.length&&j<B.length){if(A.elem[i]<B.elem[j])(C.elem[k]=A.elem[i]:k++；i++；}elseif(A.elem[i]>B.elemfj])(C.elem[k]=B.elem[j];k++J++;}else{C.elem[k]=A.elem[i];k++;i++j-H-；)//共同的元素只放一个}wliile(i<A.len)(C.elem[k]=A.elem[i];k++;i-H-}wliile(j<B.len)(C.elem[k]=B.elem[j];k-H-J-H-}C.length=k;}差集：voiddiffernce(SqListA.SqListB,SqList&C){hiti=O,j=O,k=O;wliile(i<A.length&&j<B.length){if(A.elem[i]<B.elem[j])(C.elem[k]=A.elem[i]:k++；i++；}elseif(A.elem[i]>B.elem|j])(j++；}else{i++j++;}〃共同的元素只放一个}wliile(i<A.length){C.elem[k]=A.elem[i];k++;i++}C.length=k;2.3线性表的链式存储结构简答题：描述以下三个概念的区别:头结点，头指针，首元结点（第一个元素结点）.在单链表中设置头结点的作用是什么？答：首元结点是指链表中存储线性表中第一个数据元素疆的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表.非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。否则表示空表的链表的头指针为空。这三个概念对单链表.双向链表和循环链表均适用。是否设置头结点，是不同的存储结构表示同一逻辑结构的问题。头结点head■adataluik头指针首元结点简而言之，头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息（内放头指针？那还得另配一个头指针！！！）首元素结点是指链表中存储线性表中第一个数据元素31的结点。试比较线性表的两种存储结构的优缺点，在什么情况下用顺序表比链表好？①顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。优点：存储密度大，存储空间利用率高。缺点：插入或删除元素时不方便。②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值,另一部分存放表示结点间关系的指针优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（<1）,存储空间利用率低。顺序表适宜于做查找这样的静态操作；链表宜于做插入.删除这样的动态操作。若线性表的长度变化不大，旦其主要操作是查找，则采用顺序表；若线性表的长度变化较大，旦其主要操作是插入.删除操作，则采用链表。算法设计题1试写一算法，对单链表的实现就地逆置StatusListOppose_L（LinkList&L）{LinkListp,q;p=L->next;//p指向单链表第一个结点L->next=NULL;〃形成空的单链表while（p）（〃采用头插入法将p结点插入到头结点的后面实现逆置q=p;p=p->next;q->next=L->next;L->next=q;)returnOK;2试设计一个算法，求A和Bl两个单链表表示的集合的交集并集和差集，单链表中的数据递增有序排列并集：LinkListBmgji(LuikList&HeadLLuikList&Head2XuikList&Head3){LNode*pl=Headl->next;LNode*p2=Head2->next;LNode*p3=Head3=Headl;wliile(pl&&p2){if(pl->data<p2->data){p3->next=pl;p3=p3->next;pl=pl->next;}else{if(pl->data>p2->data)p3->next=p2;p3=p3->next;p2=p2->next;}elsep3->next=pl;p3=p3->next;pl=pl->next;q=p2;fiee(q);p2=p2->next;}}}p3->next=(pl)?pl:p2;free(Head2);returnHead3;}交集：LinkListJiaoji(LuikList&HeadLLuikList&Head2.LuikList&Head3){LinkListpa,pb,r,p;pa=Headl->next;pb=Head2->next;i-Head3=Headl;while(pa&&pb)(if(pa->data<pb->data)(r->next=pa->next;free(pa);pa=r->next;}elseif(pa->data>pb->data)pb=pb->next;else(r->next=pa;r=pa;pa=pa->next;}}while(pa)(r->next=pa->next;free(pa);pa=i•->next;}while(Head2->next)〃释放Head2链表所有的结点空间{p=Head2->next;Head2->next=p->next;free(p);returnHead3;}差集：LinkListChaji(LuikList&HeadLLuikList&Head2.LinkList&Head3){LinkListpa,pb,r,p;pa=Headl->next;pb=Head2->next;i-Head3=Headl;while(pa&&pb)(if(pa->data<pb->data)r->next=pa;r=i•->next;pa=pa->next;)elseif(pa->data>pb->data)pb=pb->next;else(r->next=pa->next;fiee(pa);pa=r->next;)}while(Head2->next)〃释放Head2链表所有的结点空间{p=Head2->next;Head2->next=p->next;free(p);returnHead3;}3己知线性表中的元素以值递增有序排列，并以单链表作存储结构，试写一高效的算法，删除表中所有值大于Iirnik且小于maxk的元素(若表中存在这样的元素)，同时释放被删除的结点空间，并分析你的算法的时间复杂度(注意:mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同,也可以不同)StatusListDelete_L(LuikList&L.ElemTypeniiiik,ElemTypemaxk){LinkListp,q.prev=NULL;if(nuiik>maxk)retiirnERROR;pre=L;p=pre->next;〃pre是p的前驱，p是pre的后继while(p&&p->data<=nuiik)(〃寻找第一大于mink的元素，让p指向它，pre指向其前驱pre=p;p=p->next;}//whilewlule(p&&p->data<maxk)〃删除大于mink小于maxk的结点{pre->next=p->next;free(p);p=pre->next;}leturnOK;}3.2算法设计题假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针)，试编写相应的队列初始化，如队列和出队列的算法l.typedefmtElemType;typedefstmctQNode(ElemTypedata;QNode*next;}QNode,*QPti;typedefstmct(QPtrrear;intsize;}Queue;StatusIiiitQueue(Queue&q)(Q.reai-(Qnode*)malloc(sizeof(QNode));if(IQ.rear)exit(OVERFLOW);q.reai->next=q.rear;〃空的循环链表q.size=0;returnOK;)StatusEnQueue(Queue&q,ElemTypee)(QPtip;p=(Qnode*)malloc(sizeof(QNode));retuniexit(OVERFLOW);p->data=e;〃创建被插入结点pp->next=q.iear->next;q.reai->next=p;q.reai=p;〃将p所指结点插入到q.rear的后面}q.size++;returnOK;}StatusDeQueue(Queue&q,ElemType&e){QPtip;if(q.size==O)ieturnFALSE;p=q.reai->next->next;〃p指向循环链表的第一个结点(即被删结点)e=p->data;q.rear->next->next=p->next;//删除p所指结点fiee(p);}q.size--;returnOK;}4.1算法设计题1.编写一个实现串的置换操作Repalce(&s,T,V)的算法mtReplace(Stringtype&S,StringtypeT^StrmgtypeV)^/将串S中所有子串T替换为V,并返回置换次数fbr(n=O4=l；i<=Stilen(S)-Strlen(T)+l;i++)〃注意i的取值范围if(!StrCompare(SubString(S,i,Strlen(T)),T))〃找到了与T匹配的子串(〃分别把T的前面和后面部分保存为head和tailStrAssign(head,SubStiiiig(S.14-1))；StrAssign(taiLSubStrmg(Sj+Strlen(T),Stiien(S)-i-Stilen(T)+l));StrAssign(S,Concat(head,V));StrAssign(S,Concat(S,tail));〃把head,"tail连接为新串i+=Strlen(V);〃当前指针跳到插入串以后n++；n++；}//ifleturnn;"/Replace设计一个递归算法，利用串的基本运算StrleiigthO，SubsUO，CoiicatQ等将非空串s的所有字符逆置.voidreveise(SqStiing&s){SqStringsl,s2;if(StiLength(s)>1)(sl=SubSti<s,l,l)y/sl=^ar,s2=SubStr(s,2,s1.len-1);//s2="a2…an”Reverse(s2);〃s2=”anan-l.….a2ns=Concat(s2,s1);//连接}}利用C的库函数strlen.strcpy,strcat写一算法voidStilens(char*S,char*T,mti),将串T插入到串s的第1个位置上，若1大于S的长度，则插入不执行.voidStrliisert(char*S,char*T,mti){//将串T插入到串S的第i个位置上char*Temp;if(i<=stiien(S))(Tenip=(char*)malloc(sizeof(char[Maxsize]));//设置一个临时串strcpy(Temp,&S[i])y/^第1位起以后的字符拷贝到临时串中strcpy(&S[i],T);〃将串T拷贝到串S的第1个位置处，覆盖后面的字符strcat(S,Temp);//把临时串中的字符联接到串S后面fiee(Temp);)以Hstring为存储表示,写一个求子串的算法HStrmg是指以动态分配顺序串为存储表示，其定义为：typedefstmct(char*ch;intlength;jHStimg;void*substr(HStiiiig*sub,HStiing*s,intpos.mtlen){〃用sub返回串s的第pos个字符起长度为len的子串。sub初始时为一空串//pos的合法位置为0<=pos<=s->lengtli-1inti;if(pos<0||pos>s->length-i||len<=0)Enor(Mparametererror!n);//参数不合法，子串为空串if(s->lengtli<pos+len)//s串中没有足够的元素sub->len=s->length-pos;//设置子串的串长elsesub->length=len;〃设置子串的串长sub->ch=(cliar*)malloc(len*sizeof(char))y/sub->ch申请结点空间foi(i=0;i<sub->length;i++)//将s串中pos位置开始的共sub->length个字符复制到sub串中sub->ch[i]=s->ch[pos+i];}6.1编写算法判别给定二叉树是否为完全二叉树.intIsFuU_Bitree(BitreeT)//判断二叉树是否完全二叉树，是则返回1,否则返回0(ImtQueue(Q);flag=0;EiiQueue(Q,T);〃建立工作队列while(!QueueEmpty(Q)){DeQueue(Q,p);if(!p)flag=l;elseiRflag)return0:else(EnQueue(Q,p->lchild);EnQueue(Q,p->rchild);//不管孩子是否为空，都入队列})//wlulereturn1;}//IsFull_Bitree分析:该问题可以通过层序遍历的方法来解决.不管当前结点是否有左右孩子，都入队列.这样当树为完全二叉树时，遍历时得到是一个连续的不包含空指针的序列.反之测序列中会含有空指针.6.2.1编写递归算法，计算二叉树中椰子节点的数目思路：输出叶子结点比较简单，用任何一种遍历递归算法，凡是左右指针均空者，则为叶子,将其打印出来。法1:核心部分为：DLR(liuyu*root)/*中序遍历递归函数*/(if(ioot!=NULL)(if((ioot->lchild==NULL)&&(ioot->rcliild==NULL)){sum-H-;prmtf(H%dn'^root^data);}DLR(root->lchild);DLR(root->rchild);)return(O);)法二：mtLeafCount_BiTree(BitieeT)〃求二叉树中叶子结点的数目(if(!T)return0;//空树没有叶子elseif(!T->lchild&&!T->rchild)return1;〃叶子结点elsereturnLeaf_Count(T->lcliild)+LeaCCount(T->rchild)y/左子树的叶子数加上右子树的叶子数}//LeafCount_BiTree6.2.2写出求二叉树深度的算法，先定义二叉树的抽象数据类型，编写递归算法,求