数据结构算法题

1、前五章习题算法2.2算法设计题1.设计一个算法从一给定的有序顺序表L中删除元素值在X到Y(X=Y)之间的所有元素,要求以较高的效率实现,要求算法的空间复杂度为O(1)void delete(SqList &L,ElemType x,ElemType y) int i=0,k=0; while(i=x &L.elemi=y) k+; /记录被删记录的个数 else L.elemi-k=L.elemi; /前移k个位置 i+; L.length=L.length-k;2设一个有序表L,含有2n个整数,其中n个位负数,n个为正数,设计一个算法将L中所有元素按正负相间排列. 要求算法的空间复杂度为O(

2、1),时间复杂度为O(n) void move(SqList &L) int i=0,j=L.length-1; int temp; while(ij) /使得正数都在前半部分，负数都在后半部分 while(i0)i+; while(ij&L.elemj0)j-; if(ij) /交换L.elemi(负数)和L.elemj(正数) temp=L.elemi; L.elemi=L.elemj; L.elemj=temp; i=1; while(iL.length/2) /通过交换使得正负数相间 j=L.length-2; temp=L.elemi; L.elemi=L.elemj; L.elem

3、j=temp; i=i+2; j=j-2; 3.假设一两个元素依之=值递增有序排列的线性表A和B分别表示两个集合(同一 元素值各不相同),要求分别设计求A和B交并差集的算法,要求结果线形表中的元素依值递增有序排列,试对顺序表实现上述操作.交集:void intersection(SqList A,SqList B ,SqList &C) int i=0,j=0,k=0; while(iA.length&jB.length) if(A.elemiB.elemj) j+; else C.elemk=A.elemi; k+;i+;j+; /共同的元素 C.length=k;并集:void Union

4、(SqList A,SqList B ,SqList &C) int i=0,j=0,k=0; while(iA.length&jB.length) if(A.elemiB.elemj) C.elemk=B.elemj;k+;j+; else C.elemk=A.elemi; k+;i+;j+; /共同的元素只放一个 while(iA.len)C.elemk=A.elemi;k+;i+ while(jB.len)C.elemk=B.elemj;k+;j+ C.length=k;差集:void differnce(SqList A,SqList B ,SqList &C) int i=0,j=0

5、,k=0; while(iA.length&jB.length) if(A.elemiB.elemj) j+; else i+;j+; /共同的元素只放一个 while(iA.length)C.elemk=A.elemi;k+;i+ C.length=k;2.3线性表的链式存储结构 简答题:1. 描述以下三个概念的区别:头结点,头指针,首元结点(第一个元素结点).在单链表中设置头结点的作用是什么? 答：首元结点是指链表中存储线性表中第一个数据元素a1的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以

6、对空表.非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。否则表示空表的链表的头指针为空。这三个概念对单链表.双向链表和循环链表均适用。是否设置头结点，是不同的存储结构表示同一逻辑结构的问题。 头结点headdatalink 头指针 首元结点简而言之，头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息（内放头指针？那还得另配一个头指针！）首元素结点是指链表中存储线性表中第一个数据元素a1的结点。2

7、. 试比较线性表的两种存储结构的优缺点,在什么情况下用顺序表比链表好? 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。优点：存储密度大，存储空间利用率高。缺点：插入或删除元素时不方便。链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（next; /p指向单链表第一个结点L-next=NULL; /形成空的单链表while(p) /采用头插入法将p结点插入到头结点的后面实现逆置q=p;p=p-next;q-next=L-ne

8、xt;L-next=q;return OK;2试设计一个算法,求A和Bl两个单链表表示的集合的交集并集和差集,单链表中的数据递增有序排列并集：LinkList Bingji(LinkList &Head1,LinkList &Head2,LinkList &Head3) LNode *p1=Head1-next; LNode *p2=Head2-next;LNode *p3=Head3=Head1;while(p1 & p2) if(p1-data data) p3-next =p1; p3=p3-next ; p1=p1-next ; else if(p1-data p2-data) p3-

9、next =p2; p3=p3-next ; p2=p2-next ; else p3-next = p1; p3=p3-next ; p1=p1-next ; q=p2; free(q); p2=p2-next ; p3-next =(p1)?p1:p2;free(Head2);return Head3; 交集：LinkList Jiaoji(LinkList &Head1,LinkList &Head2,LinkList &Head3) LinkList pa,pb,r,p; pa=Head1-next;pb=Head2-next; r=Head3=Head1;while(pa&pb)if

10、(pa-datadata) r-next =pa-next ; free(pa); pa=r-next ;elseif(pa-datapb-data)pb=pb-next;elser-next=pa; r=pa;pa=pa-next;while(pa) r-next =pa-next ;free(pa); pa=r-next ; while (Head2-next) /释放Head2链表所有的结点空间 p=Head2-next; Head2-next=p-next; free(p); return Head3; 差集：LinkList Chaji(LinkList &Head1,LinkLis

11、t &Head2,LinkList &Head3) LinkList pa,pb,r,p; pa=Head1-next;pb=Head2-next; r=Head3=Head1;while(pa&pb)if(pa-datadata) r-next=pa; r=r-next; pa=pa-next;elseif(pa-datapb-data)pb=pb-next;elser-next=pa-next; free(pa);pa=r-next; while (Head2-next) /释放Head2链表所有的结点空间 p=Head2-next; Head2-next=p-next; free(p);

12、 return Head3;3已知线性表中的元素以值递增有序排列,并以单链表作存储结构,试写一高效的算法,删除表中所有值大于mink且小于maxk的元素(若表中存在这样的元素),同时释放被删除的结点空间,并分析你的算法的时间复杂度(注意:mink和maxk是给定的两个参变量,它们的值可以和表中的元素相同,也可以不同)Status ListDelete_L(LinkList &L,ElemType mink,ElemType maxk)LinkList p,q,prev=NULL;if(minkmaxk)return ERROR;pre=L;p=pre-next; /pre是p的前驱，p是pre

13、的后继while(p&p-datanext; /while while(p&p-datanext=p-next; free(p); p=pre-next;return OK;3.2算法设计题假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针),试编写相应的队列初始化,如队列和出队列的算法1.typedef int ElemType;typedef struct QNodeElemType data;QNode *next;QNode,*QPtr;typedef structQPtr rear;int size;Queue;Status InitQueue(Que

14、ue& q)Q.rear=(Qnode*) malloc(sizeof(QNode); if (!Q.rear) exit(OVERFLOW);q.rear-next=q.rear; /空的循环链表q.size=0;return OK; Status EnQueue(Queue& q,ElemType e)QPtr p;p=(Qnode*) malloc(sizeof(QNode);if(!p) return exit(OVERFLOW);p-data=e; /创建被插入结点pp-next=q.rear-next;q.rear-next=p;q.rear=p; /将p所指结点插入到q.rear

15、的后面 q.size+;return OK; Status DeQueue(Queue& q,ElemType& e) QPtr p;if(q.size=0)return FALSE;p=q.rear-next-next; /p指向循环链表的第一个结点（即被删结点）e=p-data; q.rear-next-next=p-next; /删除p所指结点free(p); q.size-;return OK; 4.1算法设计题1. 编写一个实现串的置换操作Repalce(&s,T,V)的算法 int Replace(Stringtype &S,Stringtype T,Stringtype V);/

16、将串S中所有子串T替换为 V,并返回置换次数 for(n=0,i=1;i1) s1=SubStr(s,1,1);/s1=”a1” s2=SubStr(s,2,s1.len-1); /s2=”a2.an” Reverse(s2); /s2=”anan-1.a2” s=Concat(s2,s1); /连接 3. 利用C的库函数strlen,strcpy,strcat写一算法void Str lens(char *S,char *T,int i),将串T插入到串S的第i个位置上,若i大于S的长度,则插入不执行. void StrInsert(char *S, char *T, int i)/将串T插

17、入到串S的第i个位置上char *Temp;if(i=strlen(S)Temp=(char *)malloc(sizeof(charMaxsize);/ 设置一个临时串strcpy(Temp,&Si);/将第i位起以后的字符拷贝到临时串中strcpy(&Si, T);/将串T拷贝到串S的第i个位置处，覆盖后面的字符strcat(S,Temp);/把临时串中的字符联接到串S后面free( Temp );4.以 Hstring为存储表示,写一个求子串的算法 HString 是指以动态分配顺序串为存储表示，其定义为：typedef struct char *ch;int length;HStrin

18、g; void *substr( HString *sub,HString *s,int pos,int len)/用sub返回串s的第pos个字符起长度为len的子串。sub初始时为一空串/pos的合法位置为0=poslength-1int i;if (poss-length-1|lenlengthlen=s-length-pos;/设置子串的串长else sub-length=len; /设置子串的串长sub-ch=(char *)malloc(len*sizeof(char);/为sub-ch申请结点空间for(i=0;ilength;i+)/将s串中pos位置开始的共sub-lengt

19、h个字符复制到sub串中sub-chi=s-chpos+i;6.1 编写算法判别给定二叉树是否为完全二叉树 .int IsFull_Bitree(Bitree T)/判断二叉树是否完全二叉树,是则返回1,否则返回0 InitQueue(Q); flag=0; EnQueue(Q,T); /建立工作队列 while(!QueueEmpty(Q) DeQueue(Q,p); if(!p) flag=1; else if(flag) return 0; else EnQueue(Q,p-lchild); EnQueue(Q,p-rchild); /不管孩子是否为空,都入队列 /while retur

20、n 1; /IsFull_Bitree 分析:该问题可以通过层序遍历的方法来解决.不管当前结点 是否有左右孩子,都入队列.这样当树为完全二叉树时,遍历时得到是一个连续的不包含空 指针的序列.反之,则序列中会含有空指针.6.2.1编写递归算法,计算二叉树中椰子节点的数目思路：输出叶子结点比较简单，用任何一种遍历递归算法，凡是左右指针均空者，则为叶子，将其打印出来。法一：核心部分为：DLR(liuyu *root) /*中序遍历 递归函数*/if(root!=NULL) if(root-lchild=NULL)&(root-rchild=NULL)sum+; printf(%dn,root-dat

21、a); DLR(root-lchild); DLR(root-rchild); return(0); 法二：int LeafCount_BiTree(Bitree T)/求二叉树中叶子结点的数目 if(!T) return 0; /空树没有叶子 else if(!T-lchild&!T-rchild) return 1; /叶子结点 else return Leaf_Count(T-lchild)+Leaf_Count(T-rchild);/左子树的叶子数加 上右子树的叶子数 /LeafCount_BiTree 6.2.2写出求二叉树深度的算法,先定义二叉树的抽象数据类型,编写递归算法,求二叉树中以元素值为x的节点为根的子树的深度int Get_Sub_Depth(Bitree T,int x)/求二叉树中以值为x的结点为根的子树深度 if(T-data=x) printf(%dn,Get_Depth(T);