还剩9页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
前五章习题算法
2.2算法设计题
1.设计一个算法从一给定的有序顺序表L中删除元素值在X到YX=Y之间的所有元素要求以较高的效率实现要求算法的空间复杂度为O1voiddeleteSqListLElemTypexElemTypey{inti=0k=0;whileiL.length{ifL.elem[i]=xL.elem[i]=yk++;//记录被删记录的个数elseL.elem[i-k]=L.elem[i];//前移k个位置i++;}L.length=L.length-k;}2设一个有序表L含有2n个整数其中n个位负数n个为正数设计一个算法将L中所有元素按正负相间排列.要求算法的空间复杂度为O1时间复杂度为OnvoidmoveSqListL{inti=0j=L.length-1;inttemp;whileij//使得正数都在前半部分,负数都在后半部分{whileijL.elem[i]0i++;whileijL.elem[j]0j--;ifij//交换L.elem[i]负数和L.elem[j]正数{temp=L.elem[i];L.elem[i]=L.elem[j];L.elem[j]=temp;}}i=1;whileiL.length/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交并差集的算法要求结果线形表中的元素依值递增有序排列试对顺序表实现上述操作.交集:voidintersectionSqListASqListBSqListC{inti=0j=0k=0;whileiA.lengthjB.length{ifA.elem[i]B.elem[j]i++;elseifA.elem[i]B.elem[j]j++;else{C.elem[k]=A.elem[i];k++;i++;j++;}//共同的元素}C.length=k;}并集:voidUnionSqListASqListBSqListC{inti=0j=0k=0;whileiA.lengthjB.length{ifA.elem[i]B.elem[j]{C.elem[k]=A.elem[i];k++;i++;}elseifA.elem[i]B.elem[j]{C.elem[k]=B.elem[j];k++;j++;}else{C.elem[k]=A.elem[i];k++;i++;j++;}//共同的元素只放一个}whileiA.len{C.elem[k]=A.elem[i];k++;i++}whilejB.len{C.elem[k]=B.elem[j];k++;j++}C.length=k;}差集:voiddiffern__SqListASqListBSqListC{inti=0j=0k=0;whileiA.lengthjB.length{ifA.elem[i]B.elem[j]{C.elem[k]=A.elem[i];k++;i++;}elseifA.elem[i]B.elem[j]{j++;}else{i++;j++;}//共同的元素只放一个}whileiA.length{C.elem[k]=A.elem[i];k++;i++}C.length=k;}
2.3线性表的链式存储结构简答题:
1.描述以下三个概念的区别:头结点头指针首元结点第一个元素结点.在单链表中设置头结点的作用是什么答首元结点是指链表中存储线性表中第一个数据元素a1的结点为了操作方便,通常在链表的首元结点之前附设一个结点,称为头结点,该结点的数据域中不存储线性表的数据元素,其作用是为了对链表进行操作时,可以对空表.非空表的情况以及对首元结点进行统一处理头指针是指向链表中第一个结点(或为头结点或为首元结点)的指针若链表中附设头结点,则不管线性表是否为空表,头指针均不为空否则表示空表的链表的头指针为空这三个概念对单链表.双向链表和循环链表均适用是否设置头结点,是不同的存储结构表示同一逻辑结构的问题头结点headàdatalink头指针首元结点简而言之,头指针是指向链表中第一个结点(或为头结点或为首元结点)的指针;头结点是在链表的首元结点之前附设的一个结点;数据域内只放空表标志和表长等信息(内放头指针?那还得另配一个头指针!!!)首元素结点是指链表中存储线性表中第一个数据元素a1的结点
2.试比较线性表的两种存储结构的优缺点在什么情况下用顺序表比链表好
①顺序存储时,相邻数据元素的存放地址也相邻(逻辑与物理统一);要求内存中可用存储单元的地址必须是连续的优点存储密度大,存储空间利用率高缺点插入或删除元素时不方便
②链式存储时,相邻数据元素可随意存放,但所占存储空间分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针优点插入或删除元素时很方便,使用灵活缺点存储密度小
(1),存储空间利用率低顺序表适宜于做查找这样的静态操作;链表宜于做插入.删除这样的动态操作若线性表的长度变化不大,且其主要操作是查找,则采用顺序表;若线性表的长度变化较大,且其主要操作是插入.删除操作,则采用链表算法设计题1试写一算法对单链表的实现就地逆置StatusListOppose_LLinkListL{LinkListpq;p=L-next;//p指向单链表第一个结点L-next=NULL;//形成空的单链表whilep{//采用头插入法将p结点插入到头结点的后面实现逆置q=p;p=p-next;q-next=L-next;L-next=q;}returnOK;}2试设计一个算法求A和Bl两个单链表表示的__的交集并集和差集单链表中的数据递增有序排列并集LinkListBingjiLinkListHead1LinkListHead2LinkListHead3{LNode*p1=Head1-next;LNode*p2=Head2-next;LNode*p3=Head3=Head1;whilep1p2{ifp1-datap2-data{p3-next=p1;p3=p3-next;p1=p1-next;}else{ifp1-datap2-data{p3-next=p2;p3=p3-next;p2=p2-next;}else{p3-next=p1;p3=p3-next;p1=p1-next;q=p2;freeq;p2=p2-next;}}}p3-next=p1p1:p2;freeHead2;returnHead3;}交集LinkListJiaojiLinkListHead1LinkListHead2LinkListHead3{LinkListpapbrp;pa=Head1-next;pb=Head2-next;r=Head3=Head1;whilepapb{ifpa-datapb-data{r-next=pa-next;freepa;pa=r-next;}elseifpa-datapb-datapb=pb-next;else{r-next=pa;r=pa;pa=pa-next;}}whilepa{r-next=pa-next;freepa;pa=r-next;}whileHead2-next//释放Head2链表所有的结点空间{p=Head2-next;Head2-next=p-next;freep;}returnHead3;}差集LinkListChajiLinkListHead1LinkListHead2LinkListHead3{LinkListpapbrp;pa=Head1-next;pb=Head2-next;r=Head3=Head1;whilepapb{ifpa-datapb-data{r-next=pa;r=r-next;pa=pa-next;}elseifpa-datapb-datapb=pb-next;else{r-next=pa-next;freepa;pa=r-next;}}whileHead2-next//释放Head2链表所有的结点空间{p=Head2-next;Head2-next=p-next;freep;}returnHead3;}3已知线性表中的元素以值递增有序排列并以单链表作存储结构试写一高效的算法删除表中所有值大于mink且小于__xk的元素若表中存在这样的元素同时释放被删除的结点空间并分析你的算法的时间复杂度注意:mink和__xk是给定的两个参变量它们的值可以和表中的元素相同也可以不同StatusListDelete_LLinkListLElemTypeminkElemType__xk{LinkListpqprev=NULL;ifmink__xkreturnERROR;pre=L;p=pre-next;//pre是p的前驱,p是pre的后继whilepp-data=mink{//寻找第一大于mink的元素,让p指向它,pre指向其前驱pre=p;p=p-next;}//whilewhilepp-data__xk//删除大于mink小于__xk的结点{pre-next=p-next;freep;p=pre-next;}returnOK;}
3.2算法设计题假设以带头结点的循环链表表示队列并且只设一个指针指向队尾元素结点注意不设头指针试编写相应的队列初始化如队列和出队列的算法
1.typedefintElemType;typedefstructQNode{ElemTypedata;QNode*next;}QNode*QPtr;typedefstruct{QPtrrear;intsize;}Queue;StatusInitQueueQueueq{Q.rear=Qnode*__llocsizeofQNode ;if !Q.rearexitOVERFLOW ;q.rear-next=q.rear;//空的循环链表q.size=0;returnOK;}StatusEnQueueQueueqElemTypee{QPtrp;p=Qnode*__llocsizeofQNode ;if!preturnexitOVERFLOW;p-data=e;//创建__入结点pp-next=q.rear-next;q.rear-next=p;q.rear=p;//将p所指结点插入到q.rear的后面}q.size++;returnOK;}StatusDeQueueQueueqElemTypee{QPtrp;ifq.size==0returnFALSE;p=q.rear-next-next;//p指向循环链表的第一个结点(即被删结点)e=p-data;q.rear-next-next=p-next;//删除p所指结点freep;}q.size--;returnOK;}
4.1算法设计题
1.编写一个实现串的置换操作Repal__sTV的算法intRepla__StringtypeSStringtypeTStringtypeV;//将串S中所有子串T替换为V并返回置换次数{forn=0i=1;i=StrlenS-StrlenT+1;i++//注意i的取值范围if!StrCompareSubStringSiStrlenTT//找到了与T匹配的子串{//分别把T的前面和后面部分保存为head和tailStrAssignheadSubStringS1i-1;StrAssigntailSubStringSi+StrlenTStrlenS-i-StrlenT+1;StrAssignSConcatheadV;StrAssignSConcatStail;//把headVtail连接为新串i+=StrlenV;//当前指针跳到插入串以后n++;n++;}//ifreturnn;}//Repla__
2.设计一个递归算法利用串的基本运算StrlengthSubstrConcat等将非空串s的所有字符逆置.voidreverseSqStrings{SqStrings1s2;ifStrLengths1{s1=SubStrs11;//s1=”a1”s2=SubStrs2s
1.len-1;//s2=”a
2...an”Reverses2;//s2=”anan-
1.....a2”s=Concats2s1;//连接}}
3.利用C的库函数strlenstrcpystrcat写一算法voidStrlenschar*Schar*Tinti将串T插入到串S的第i个位置上若i大于S的长度则插入不执行.voidStrInsertchar*Schar*Tinti{//将串T插入到串S的第i个位置上 char*Temp; ifi=strlenS { Temp=char*__llocsizeofchar[__xsize];//设置一个临时串 strcpyTempS[i];//将第i位起以后的字符拷贝到临时串中 strcpyS[i]T;//将串T拷贝到串S的第i个位置处,覆盖后面的字符 strcatSTemp;//把临时串中的字符联接到串S后面 freeTemp; } }
4.以Hstring为存储表示写一个求子串的算法HString是指以动态分配顺序串为存储表示,其定义为 typedefstruct{ char*ch; intlength; }HString;void*substrHString*subHString*sintposintlen {//用sub返回串s的第pos个字符起长度为len的子串sub初始时为一空串 //pos的合法位置为0=pos=s-length-1 inti; ifpos0||poss-length-1||len=0 Errorparametererror!;//参数不合法,子串为空串 ifs-lengthpos+len//s串中没有足够的元素 sub-len=s-length-pos;//设置子串的串长 elsesub-length=len;//设置子串的串长 sub-ch=char*__lloclen*sizeofchar;//为sub-ch申请结点空间 fori=0;isub-length;i++//将s串中pos位置开始的共sub-length个字符__到sub串中 sub-ch[i]=s-ch[pos+i]; }
6.1编写算法判别给定二叉树是否为完全二叉树.intIsFull_BitreeBitreeT//判断二叉树是否完全二叉树是则返回1否则返回0{InitQueueQ;flag=0;EnQueueQT;//建立工作队列while!QueueEmptyQ{DeQueueQp;if!pflag=1;elseifflagreturn0;else{EnQueueQp-lchild;EnQueueQp-rchild;//不管孩子是否为空都入队列}}//whilereturn1;}//IsFull_Bitree分析:该问题可以通过层序遍历的方法来解决.不管当前结点是否有左右孩子都入队列.这样当树为完全二叉树时遍历时得到是一个连续的不包含空指针的序列.反之则序列中会含有空指针.编写递归算法计算二叉树中椰子节点的数目思路输出叶子结点比较简单,用任何一种遍历递归算法,凡是左右指针均空者,则为叶子,将其打印出来法一核心部分为DLRliuyu*root/*中序遍历递归函数*/{ifroot!=NULL{ifroot-lchild==NULLroot-rchild==NULL{sum++;printf%d\nroot-data;}DLRroot-lchild;DLRroot-rchild;}return0;}法二intLeafCount_BiTreeBitreeT//求二叉树中叶子结点的数目{if!Treturn0;//空树没有叶子elseif!T-lchild!T-rchildreturn1;//叶子结点elsereturnLeaf_CountT-lchild+Leaf_CountT-rchild;//左子树的叶子数加上右子树的叶子数}//LeafCount_BiTree写出求二叉树深度的算法先定义二叉树的抽象数据类型编写递归算法求二叉树中以元素值为x的节点为根的子树的深度intGet_Sub_DepthBitreeTintx//求二叉树中以值为x的结点为根的子树深度{ifT-data==x{printf%d\nGet_DepthT;//找到了值为x的结点求其深度exit1;}}else{ifT-lchildGet_Sub_DepthT-lchildx;ifT-rchildGet_Sub_DepthT-rchildx;//在左右子树中继续寻找}}//Get_Sub_DepthintGet_DepthBitreeT//求子树深度的递归算法{if!Treturn0;else{m=Get_DepthT-lchild;n=Get_DepthT-rchild;returnmnm:n+1;}}//Get_Depth编写按层次顺序同一层自左至右遍历二叉树的算法voidLayerOrderBitreeT//层序遍历二叉树{InitQueueQ;//建立工作队列EnQueueQT;while!QueueEmptyQ{DeQueueQp;visitp;ifp-lchildEnQueueQp-lchild;ifp-rchildEnQueueQp-rchild;}}//LayerOrder假定二叉树采用二叉链表存储结构存储设计一个算法计算一棵给定二叉树的结点总数.intNodesBTNode*T{intnum1num2;ifT==NULLreturn0;elseifT-lchild==NULLT-rchild==NULLreturn1;else{num1=NodesT-lchild;num2=NodesT-rchild;returnnum1+num2+1;}}。