数据结构练习题题库

2.叙述四类基本数据结构的名称与含义。4.叙述算法的时间复杂度。6.叙述线性结构与非线性结构的差别。7.叙述面向对象程序设计语言的特点。9.叙述参数传递的主要方式及特点。1.线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。()2.算法就是程序。()3.在高级语言（如C或PASCAL）中，指针类型是原子类型。()三、计算下列程序段中X=X+1的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入ai(i=0,1,…,n),x和n，输出为Pn(x0)。通常算法的输入和输出可采用下列两种方式之一：（1）通过参数表中的参数显式传递。（2）通过全局变量隐式传递。试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。设计实现抽象数据类型“有理数”。基本操作包括有理数的加法、减法、乘法、除法，以及1.3计算下列程序中x=x+1的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;T(n)=1+(1+2)+（1+2+3）+……+（1+2+……+n）=n(n+1)(n+2)/6.专业.专注.行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入为ai(i=0,1,…n)、x和n,输出为Pn(x0)。算法的输入和输出采用下列方法（1）通过参数表中的参数显式传递（2）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。【解答】（1）通过参数表中的参数显式传递优点：当没有调用函数时，不占用存，调用结束后形参被释放，实参维持，函数通用缺点：形参须与实参对应，且返回值数量有限。（2）通过全局变量隐式传递优点：减少实参与形参的个数，从而减少存空间以及传递数据时的时间消耗缺点：函数通用性降低，移植性差算法如下：通过全局变量隐式传递参数PolyValue()floatx,a[],p;printf(“\nn=”);scanf(“%f”,&n);printf(“\nx=”);scanf(“%f”,&x);for(i=0;i<n;i++)scanf(“%f”,&a[i]);/*执行次数：n次*/p=a[0];for(i=1;i<=n;i++)x=x*x;}printf(“%f”,p);}算法的时间复杂度：T(n)=O(n)通过参数表中的参数显式传递floatPolyValue(floata[],floatx,intn){floatp,s;p=x;for(i=1;i<=n;i++)p=p*x;}return(p);}算法的时间复杂度：T(n)=O(n).专业.专注..专业.专注.n.专业.专注..专业.专注.1.描述以下三个概念的区别：头指针，头结点，首元素结点。3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。（1）P->next=S;（2）P->next=P->next->next;（3）P->next=S->next;（4）S->next=P->next;（5）S->next=L;（6）S->next=NULL;（7）Q=P;（8）while(P->next!=Q)P=P->next;（9）while(P->next!=NULL)P=P->next;（10）P=Q;（11）P=L;（13）L=P;4.设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。5.写一算法，从顺序表中删除自第i个元素开始的k个元素。6.已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意7.试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性（1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。.专业.专注.8.假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表9.假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表某个结点的指针，试编写算法在链表中删除指针s所指结点的前趋结点。10.已知有单链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其它字符），试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。mmn注意：单链表的长度值m和n均未显式存储。12.将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间来构成这两个链表。13.建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的data域存放一个二进制位。并在此链表上实现对二进制数加1的运算。14.设多项式P(x)采用课本中所述方法存储。写一算法，对给定的x值，求P(x)的值。1．将若干城市的信息存入一个带头结点的单链表，结点中的城市信息包括城市名、城市（2）给定一个位置坐标P和一个距离D，返回所有与P的距离小于等于D的约瑟夫问题的一种描述是：编号为1，2，…，n的n个人按顺时针持有一个密码（正整数）。一开始任选一个整数作为报数上限值m,从第一个人开始顺时针顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，求出出列顺序。利用单向循环链表作为存储结构模拟此过程，按照出列顺序打印出各人的编号。1，4，7，2，3，5。约瑟夫环问题约瑟夫问题的一种描述为：编号1,2,…,n的n个人按顺时针方向围坐一圈，每个人持有一个密码（正整数）。一开始任选一个报数上限值m,从第一个人开始顺时针自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，求例如m的初值为20；n=7，7个人的密码依次是：3,1,7,2,4,8,4,出列顺序为6,1,4,7,2,3,5。typedefstructNode{.专业.专注.intpassword;structNode*next;}Node,*Linklist;voidJosephus(){LinklistL;Node*p,*r,*q;intm,n,C,j;L=(Node*)malloc(sizeof(Node));/*初始化单向循环链表*/if(L==NULL){printf("\n链表申请不到空间!");return;}L->next=NULL;r=L;printf("请输入数据n的值(n>0):");scanf("%d",&n);for(j=1;j<=n;j++)/*建立链表*/{p=(Node*)malloc(sizeof(Node));if(p!=NULL){printf("请输入第%d个人的密码:",j);scanf("%d",&C);p->password=C;p->num=j;r->next=p;r=p;}}r->next=L->next;printf("请输入第一个报数上限值m(m>0):");scanf("%d",&m);printf("*****************************************\n");printf("出列的顺序为:\n");p=L->next;while(n!=1)/*计算出列的顺序*/{while(j<m)/*计算当前出列的{q=p;/*q为当前结点p=p->next;}printf("%d->",p->num);m=p->password;/*获得新密码*/n--;.专业.专注.q->next=p->next;/*p出列*/r=p;p=p->next;free(r);}printf("%d\n",p->num);}2.7试分别以不同的存储结构实现单线表的就地逆置算法，即在原表的存储空间将线性表2【解答】（1）用一维数组作为存储结构voidinvert(SeqList*L,int*num){ElemTypetmp;for(j=0;j<=(*num-1)/2;j++)L[j]=L[*num-j-1];L[*num-j-1]=tmp;}}（2）用单链表作为存储结构voidinvert(LinkListL){Node*p,*q,*r;if(L->next==NULL)return;/*链表为空*/p=L->next;q=p->next;p->next=NULL;/*摘下第一个结点，生成初始逆置表*/while(q!=NULL)/*从第二个结点起依次头插入当前逆置r=q->next;q->next=L->next;L->next=q;}2.11将线性表A=(a1,a2,C=(a1,b1,……am,bm,bm+1,…….bn)当m<=n时，或C=(a1,b1,……an,bn,an+1,……am)当m>n时,线性表A、B、C以单链表作为存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。LinkListmerge(LinkListA,LinkListB,LinkListC)pa=A->next;/*pa表示A的当前结点*/pb=B->next;p=A;/*利用p来指向新连接的表的表尾，初始值指向表A的头结点*/while(pa!=NULL&&pb!=NULL)/*利用尾插法建立连接之后的链表*/.专业.专注.qb=qb->next;p->next=pa;/*交替选择表A和表B中的结点连接到新链表中；*/p=pa;p->next=pb;p=pb;pa=qa;pb=qb;}if(pa!=NULL)p->next=pa;/*A的长度大于B的长度*/if(pb!=NULL)p->next=pb;/*B的长度大于A的长度*/C=A;Return(C);}1.按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答：⑵如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因。（即写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。2.设队列中有A、B、C、D、E这5个元素，其中队首元素为A。如果对这个队直到队列成为空队列为止，得到输出序列：（1）A、C、E、C、C（2）A、C、E（3）A、C、E、C、C、C（4）A、C、E、C3.给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与4.按照四则运算加、减、乘、除和幂运算(↑)优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：A－B*C/D+E↑F是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘1+3&3-1’6.假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰式。7.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。8.要求循环队列不损失一个空间全部都能得到利用,设置一个标志域tag,以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队9.简述以下算法的功能（其中栈和队列的元素类型均为int（1）voidproc_1(StackS)n=0;.专业.专注.while(!EmptyStack(S)){n++;Pop(&S,&A[n]);}Push(&S,A[i]);}（2）voidproc_2(StackS,inte)InitStack(&T);while(!EmptyStack(S))}while(!EmptyStack(T))Push(&S,d);}（3）voidproc_3(Queue*Q)InitStack(&S);while(!EmptyQueue(*Q)){DeleteQueue(Q,&d);Push(&S,d);}while(!EmptyStack(S))EnterQueue(Q，d)}}1．回文判断。称正读与反读都相同的字符序列为“回文”序列。试写一个算法，判断依次读入的一个以为结束符的字母序列，是否为形如‘序列1&序列2’模式的字符序列。其中序列1和序列2中都不含字符‘&’，且序列2是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘1+3&3-1’则不设停车场是一个可停放n辆车的狭长通道，且只有一个大门可供汽车进出。在停车场，汽车按到达的先后次序，由北向南依次排列（假设大门在最南端）。若车场已停满n辆车，则后来的汽车需在门外的便道上等候，当有车开走时，便道上的第一辆车即可开入。当停车场某辆车要离开时，在它之后进入的车辆必须辆车开出大门后，其它车辆再按原次序返回车场。每辆车离开停车场时，应按其停留时间的长短交费（在便道上停留的时间不收费）。试编写程序，模拟上述管理过程。要求以顺序栈模拟停车场，以链队列模拟便道。从终端读入汽车到达或离去的数据，每组数据包括三项：①是“到达”还是“离去”；②汽车牌照；③“到达”或“离去”的时刻。与每组输入信息相应的输出信息为：如果是到达的车辆，则输出其在停车场中或便道上的位置；如果是离去的车辆，则输出其在停车场中停留的时间和应交的费用。（提示：需另设一个栈，临时停放为让路而从车场退出的车。）.专业.专注.商品货架可以看成一个栈，栈顶商品的生产日期最早，栈底商品的生产日期最近。上货时，需要倒货架，以保证生产日期较近的商品在较下的位置。用队列和栈作为周转，实现上述管3.1按3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答：（2）如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明【解答】（1）可能得到的出站车厢序列是：123、132、213、231、321。(2)不能得到435612的出站序列。因为有S(1)S(2)S(3)S(4)X(4)X(3)S(5)X(5)S(6)S(6)，此时按照“后进先出”的原则，出栈的顺序必须为X(2)X(1)。因为有S(1)X(1)S(2)S(3)X(3)S(4)S(5)X(5)X(4)X(2)X(1)。3.3给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？判断栈S满：如果S->top==Stack_Size-1表示栈满。(2)链栈（top为栈顶指针，指向当前栈顶元素前面的头结点）判断栈空：如果top->next==NULL表示栈空。判断栈满：当系统没有可用空间时，申请不到空间存放要进栈的元素，此时栈满。3．4照四则运算加、减、乘、除和幂运算的优先惯例，画出对下列表达式求值时操作数栈【解答】3．5写一个算法，判断依次读入的一个以为结束符的字母序列，是否形如‘序列1&序列2’.专业.专注.如，’a+b&b+a’是属于该模式的字符序列，而’1+3&3-1’则不是。{Stack*S;Charch,temp;InitStack(&S);Printf(“\n请输入字符序列：”);Ch=getchar();ch=getchar();}do/*判断序列2是否是序列1的逆序列*/Pop(&S,&temp);{return(FALSE);printf(“\nNO”);}}while(ch!=&&!IsEmpty(&S))if(ch==&&IsEmpty(&S)){return(TRUE);printf(“\nYES”);}/*序列2是序列1的逆序列{return(FALSE);printf(“\nNO”);}}/*IsHuiWen()*/3.8要求循环队列不损失一个空间全部都能得到利用，设置一个标志tag,以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此相应的入队与出队算法。intEnterQueue(SeqQueue*Q,QueueElementTypex){/*将元素x入队*/if(Q->front==Q->front&&tag==1)return(FALSE);if(Q->front==Q->front&&tag==0)tag=1;/*x入队前队空，x入队后重新设置标志Q->elememt[Q->rear]=x;Q->rear=(Q->rear+1)%MAXSIZE;/*设置队尾指针*/Return(TRUE);}intDeleteQueue(SeqQueue*Q,QueueElementType*x){/*删除队头元素，用x返回其值*/if(Q->front==Q->rear&&tag==0)/*队空*/return(FALSE);*x=Q->element[Q->front];Q->front=(Q->front+1)%MAXSIZE;if(Q->front==Q->rear)tag=0;Return(TUUE);/*重新设置队头指针*//*队头元素出队后队列为空，重新设置标志域.专业.专注.}编写求解Hanoi问题的算法，并给出三个盘子搬动时的递归调用过程。{/*将塔座X上按直径由小到大且至上而下编号为1到n的n个圆盘按规则搬到塔座Z上，Y可用做辅助塔座*/move(x,1,z);{Hanoi(n-1,x,z,y);move(x,n,z);Hanoi(n-1,y,x,z);}Hanoi(3,A,B,C)的递归调用过程：Hanoi(2,A,C,B):Hanoi(1,A,B,C)Move(A->B)Hanoi(1,C,A,B)Move(A->C)Hanoi(2,B,A,C)Hanoi(1,B,C,A)Move(B->C)Hanoi(1,A,B,C)move(A->C)move(C->B)move(B->A)move(A->C)1号搬到C3号搬到C1号搬到A2号搬到C1号搬到C1.按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行列是什么？123、213、132、231、321（312）.专业.专注.SXSSXSSXXXSX或S1X1S2S3X3S4S5X5X4X2S6X6（1）A、C、E、C、C（2）A、C、E（3）A、C、E、C、C、C（4）A、C、E、A、B、C、D、E（输出队首元素A）A、B、C、D、E、A（把队首元素A插入到队尾）B、C、D、E、A（删除队首元素A）C、D、E、A（再次删除队首元素B）C、D、E、A（输出队首元素C）D、E、A、C（删除队首元素C）E、A、C（再次删除队首元素D）.专业.专注.4.按照四则运算加、减、乘、除和幂运算(↑)优先关系的A－B*C/D+E↑F而‘1+3&3-1’则不是。（2）边读边出栈边比较，直到……中缀表达式：a+b后缀表达式:ab+.专业.专注.中缀表达式：a+b×c-d后缀表达式:abc×+d-中缀表达式：a+b×c-d/e后缀表达式:abc×+de/-abcd-×+ef/-.专业.专注.intEnterQueue(CLQueueintDeleteQueue(CLQueueQ初始状态：front==0,rear==0,tag==0队空条件：front==rear,tag==0.专业.专注..专业.专注..专业.专注.而‘1+3&3-1’则不是。n辆车，则后来的汽车需在门外的便道上等候，当有车开的数据，每组数据包括三项：①是“到达”还是“离去②汽车牌照；③“到达”或“离去”的时刻。与每组输入.专业.专注.暂时退车道暂时退车道便道StrLength(s);SubString(sub1,s,1,7);SubString(sub2,s,7,1);StrIndex(s,’A’,4);StrReplace(s,’STUDENT’,q);StrCat(StrCat(sub1,t),StrCat(sub2,q));2.编写算法，实现串的基本操作StrReplace(S,T,V)。3.假设以块链结构表示串，块的大小为1，且附设头结点。试编写算法，实现串的下列基本操作：StrAsign(S,chars)；StrCopy(S,T)；StrCompare(S,T)；StrLength(S)；.专业.专注.StrCat(S,T)；SubString(Sub,S,pos,len)。4．叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的5．已知：S=”(xyz)*”,T=”(x+z)*y”。试利用联接、求子串和置换等操作，将S转7．S是用结点大小为4的单链表存储的串,分别编写算法在第k个字符后插入串T，及从10．写算法，实现顺序串的基本操作StrCompare(s,t)。11．写算法，实现顺序串的基本操作StrReplace(&s,t,v)。（2）以顺序串作为存储结构来实现。2．编写一个行编辑程序EDLINE，完成以下功能：省时，从第一行开始，n2缺省时，到最后一行，（3）编辑第n行。editn：显示第n行的容，另输入一行3．设计一个文学研究辅助程序，统计小说中特定单词出现的频率和位置。4.1设s=’IAMASTUDENT’，t=’GOOD’，q=’WORKER’。给出下列操作的结果：【解答】StrLength(s)=14;SubString(sub1,s,1,7)sub1=’IAMA’;SubString(sub2,s,7,1)sub2=’’;StrIndex(s,4,’A’)=6;StrReplace(s,’STUDENT’,q);s=’IAMAWORKER’;StrCat(StrCat(sub1,t),StrCat(sub2,q))sub1=’IAMAGOODWORKER’。4.2编写算法，实现串的基本操作StrReplace(S,T,V)。intstrReplace(SStringS,SStringT,SStringV){/*用串V替换S中的所有子串T*/.专业.专注.pos=strIndex(S,1,T);/*求S中子串T第一次出现的位置*/if(pos==0)return(0);while(pos!=0)/*用串V替换S中的所有子串T*/{switch(T.len-V.len){for(i=0;i<=V.len;i++)/*用V替换T*/S->ch[pos+i]=V.ch[i];for(i=pos+t.ien;i<S->len;i--)/*将S中子串T后的所有S->ch[i-t.len+v.len]=S->ch[i];前移T.len-V.len个位置*/for(i=0;i<=V.len;i++)/*用V替换T*/S->ch[pos+i]=V.ch[i];S->len=S->len-T.len+V.len;if(S->len-T.len+V.len)<=MAXLEN/*插入后串长小于MAXLEN*/for(i=S->len-T.len+V.len;i>=pos+T.len;i--)S->ch[i]=S->ch[i-T.len+V.len];for(i=0;i<=V.len;i++)/*用V替换T*/S->ch[pos+i]=V.ch[i];S->len=S->len-T.len+V.len;}{/*替换后串长>MAXLEN,但串V可以全部替换*/if(pos+V.len<=MAXLEN){for(i=MAXLEN-1;i>=pos+T.len;i--)S->ch[i]=s->ch[i-T.len+V.len]for(i=0;i<=V.len;i++)/*用V替换T*/S->ch[pos+i]=V.ch[i];S->len=MAXLEN;}{for(i=0;i<MAXLEN-pos;i++)S->ch[i+pos]=V.ch[i];S->len=MAXLEN;}}/*switch()*/pos=StrIndex(S,pos+V.len,T);/*求S中下一个子串T的位置}/*while()*/return(1);}/*StrReplace()*/附加题：用链式结构实现定位函数。【解答】typedefstructNodestructNode*next;.专业.专注.}Node,*Lstring;intstrIndex(LstringS,intpos,LstringT)/*从串S的pos序号起，串T第一次出现的位{Node*p,*q,*Ppos;if(T->next==NULL||S->next==NULL)return(0);p=S->next;q=T->next;while(p!=NULL&&j<pos)/*p指向串S中第pos个字符*/if(j!=pos)return(0);while(p!=NULL&&q!=NULL){Ppos=p;/*Ppos指向当前匹配的起始字符*/if(p->data==q->data){p=p->next;q=q->next;}else/*从Ppos指向字符的下一个字符起从新匹配*/q=T->head->next;} }=NULL)return(pos+i);return(0);.专业.专注..专业.专注.5.1假设有6行8列的二维数组A，每个元素占用6个字节，存储器按字节编址。已知A的.专业.专注.5.2设有三对角矩阵A,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得n×n5.3假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩阵相加的算法，另设三元组5.4在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法只5.5写一个在十字链表中删除非零元素aij的算法。（1）HEAD[((a,b),(c,d))];（2）TAIL[((a,b),(c,d))];（3）TAIL[HEAD[((a,b),(c,d))]];（4）HEAD[TAIL[HEAD[((a,b),(c,d))]]];（5）TAIL[HEAD[TAIL[((a,b),(c,d))]]];元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵，试编写算法求出矩阵中的所有马5.2设有三对角矩阵An×n,将其三条对角线上的元素逐行的存于数组B[1..3n-2]中，使得 (2)i=[k/3]+1,j=[k/3]+k%3（[]取整，%取余）5.4在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法只【解答】算法（一）FastTransposeTSMatrix(TSMartrixA,TSMatrix*B){/*把矩阵A转置到B所指向的矩阵中去，矩阵用三元组表表示*/intposition[MAXSIZE];B->len=A.len;B->n=A.m;B->m=A.n;if(B->len>0){position[1]=1;for(t=1;t<=A.len;t++)position[A.data[t].col+1]++;/*position[col]存放第col-1列非零元素的个数,即利用pos[col]来记录第col-1列中非零元素的个数*//*求col列中第一个非零元素在B.data[]的位置，存放在position[col]中for(col=2;col<=A.n;col++)position[col]=position[col]+position[col-1];for(p=1;p<A.len;p++){col=A.data[p].col;.专业.专注.q=position[col];B->data[q].row=A.data[p].col;B->data[q].col=A.data[p].row;B->data[q].e=A.data[p].e;Position[col]++;}}算法(二)FastTransposeTSMatrix(TSMartrixA,TSMatrix*B){intposition[MAXSIZE];B->len=A.len;B->n=A.m;B->m=A.n;if(B->len>0){for(col=1;col<=A.n;col++)position[col]=0;for(t=1;t<=A.len;t++)position[A.data[t].col]++;/*计算每一列的非零元素的个数*//*从最后一列起求每一列中第一个非零元素在B.data[]中的位置，存放在position[col]for(col=A.n,t=A.len;col>0;col--){t=t-position[col];position[col]=t+1;}for(p=1;p<A.len;p++){col=A.data[p].col;q=position[col];B->data[q].row=A.data[p].col;B->data[q].col=A.data[p].row;B->data[q].e=A.data[p].e;Position[col]++;}}【解答】.专业.专注.第一种存储结构（1）HEAD[((a,b),(c,d))];(a,b)（2）TAIL[((a,b),(c,d))];((c,d))（3）TAIL[HEAD[((a,b),(c,d))]];(b)（4）HEAD[TAIL[HEAD[((a,b),(c,d))]]];b（5）TAIL[HEAD[TAIL[((a,b),(c,d))]]];(d)1．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。2．对题1所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。.专业.专注.结点，则该树中有多少个叶子结点并证明之。4.假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。6．给出满足下列条件的所有二叉树：①前序和后序相同③前序和后序相同8．画出与下列已知序列对应的树T:树的先根次序访问序列为GFKDAIEBCHJ；树的后根次序访问序列为DIAEKFCJHBG。9．假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.1010．已知二叉树采用二叉链表存放,要求返回二叉树T的后序序列中的第一个结点指针,是否可不用递归且不用栈来完成?请简述原因.12．已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。13．编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放14．分别写函数完成：在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。在后序线索二叉树T中，查找给定结点*p15．分别写出算法，实现在中序线索二叉树中查找给定结点*p在中序序列中的前驱与后继。16．编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数。17．对以孩子-兄弟链表表示的树编写计算树的深度的算法。18．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出后序遍历非递归的算法。19．设二叉树按二叉链表存放，写算法判别一棵二叉树是否是一棵正则二叉树。正则二叉树是指：在二叉树中不存在子树个数为1的结点。20．计算二叉树最大宽度的算法。二叉树的最大宽度是指：二叉树所有层中结点个数的最大22.证明：给定一棵二叉树的前序序列与中序序列，可唯一确定这棵二叉树；给定一棵二叉树的后序序列与中序序列，可唯一确定这棵二叉树；23.二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。24.二叉树按照二叉链表方式存储，编写算法，将二叉树左右子树进行交换。.专业.专注.1.[问题描述]建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序和后序），打印输出遍历结果。[基本要求]从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立）并对其进行遍历（先序、中序、后序），然后将遍历结果打印输出。要求采用递归和非递归两种方法实现。[测试数据]ABCффDEфGффFффф（其中ф表示空格字符）输出结果为：先序：ABCDEGF后序：CGBFDBA2．已知二叉树按照二叉链表方式存储，编写算法，要求实现二叉树的竖向显示（竖向显示就是二叉树的按层显示）。3．如题1要求建立好二叉树，按凹入表形式打印二叉树结构，如下图所示。A2.按凹入表形式打印树形结构，如下图所示。.专业.专注.6．1分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。【解答】具有3【解答】设树中结点总数为n,则n=n0+n1+……+nk树中分支数目为B,则B=n1+2n2+3n3+……+knk因为除根结点外，每个结点均对应一个进入它的分支，所以有n=B+1【解答】n0表示叶子结点数，n2表示度为2的结点数，则n0=n2+16.6试分别找出满足以下条件的所有二叉树:(1)前序序列与中序序列相同;【解答】(1)前序与中序相同：空树或缺左子树的单支树；(3)前序与后序相同：空树或只有根结点的二叉树。.专业.专注.6.9假设通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10【解答】66.11画出如下图所示树对应的二叉树。【解答】.专业.专注.6.15分别写出算法，实现在中序线索二叉树T中查找给定结点*p在中序序列中的前驱与后继。在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。（1）找结点的中序前驱结点BiTNode<spanlang=EN-USstyle='font-family:Arial;mso-bidi-font-family:.专业.专注.2．对题1所得各种形态的二叉树，分别写出前序、中序和.专业.专注..专业.专注.8．画出与下列已知序列对应的树T:树的先根次序访问序列为GFKDAIEBCHJ；.专业.专注.9．假设用于通讯的电文仅由8个字母组成，字母在电文中0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10完成?请简述原因.[提示]：无右子的“左下端”.专业.专注.[方法1]1）按先序查找2）超前查看子结点（3）按后voidDelSubTree(BiTree*bt,DataTypex)voidDelTree(BiTreebt,DataTypex).专业.专注.DelTree(bt->LChild,x);DelTree(bt->RChild,x);[方法2]1）先序查找2）直接查看当前根结点（3）用[方法3]1）先序查找2）直接查看当前根结点15．分别写出算法，实现在中序线索二叉树中查找给定结点.专业.专注.16．编写算法，对一棵以孩子-兄弟链表表示的树统计其叶（1）可将孩子-兄弟链表划分为根、首子树、兄弟树，递归（2）可利用返回值，或全局变量。19．设二叉树按二叉链表存放，写算法判别一棵二叉树是否是一棵正则二叉树。正则二叉树是指：在二叉树中不存在子style='font-size:16.0pt;mso-bidi-font-size:10.0pt;font-fa.专业.专注.(1)邻接多重表要求每个边结点中第一个顶点号小于第二个顶点号，且每个顶点的(2深度优先遍历该图所得顶点序列和边的序列；(3)广度优先遍历该图所得顶点序列和边的序列。.专业.专注.(1)每个事件的最早发生时间和最晚发生时间；(2)每个活动的最早开始时间和最晚开始时间；7.4已知如图所示的有向网，试利用Dijkstra算法求顶点1到其余顶点的最短路径，并给出算法执行过程中各步的状态。.专业.专注.7.5编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立7.6试在邻接矩阵存储结构上实现图的基本操作：InsertVertex(G,v)，InsertArc(G,v,w)，DeleteVertex(G,v)和DeleteArc(G,v,w)。7.7试用邻接表存储结构重做题7.6。7.8试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中，是否7.9同上题要求。试基于图的广度优先搜索策略写一算法。7.10试利用栈的基本操作，编写按深度优先策略遍历一个强连通图的非递归形式的算法。算法中不规定具体的存储结构，而将图Graph看成是一种抽象数据类型。7.11采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径（指顶点序列中不含有重现的顶点）的算法。V1,V2,V3,V4,V5,V6,V7,V8V1,V2,V4,V6,V5,V3,V7,V8V1,V2,V4,V6,V3,V5,V7,V8V1,V2,V4,V6,V7,V3,V5,V8V1,V2,V3,V8,V4,V5,V6,V7V1,V2,V3,V8,V4,V5,V7,V6.专业.专注.V1,V2,V3,V8,V5,V7,V4,V6①V1,V2,V4,V5,V3,V8②V1,V6,V5,V3,V8③V1,V6,V7,V8④V1,V2,V5,V7,V8一、分别用邻接矩阵和邻接表实现图的深度优先遍历和广度优先遍历。用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图（2）查询图中任意两个景点间的最短路径。（3）查询图中任意两个景点间的所有路径。三、编程求解关键路径问题。.专业.专注.1.专业.专注.162345130222312413521623.专业.专注.（5）十字链表（2）深度优先遍历该图所得顶点序列和边的序列；（3）广度优先遍历该图所得顶点序列和边的序列。.专业.专注.【解答】（2）深度优先搜索顶点序列：1-2-3-4-5-6边的序列1，22，33，44，55，6）（2）广度优先搜索顶点序列：1-2-3-6-5-4边的序列1，21，31，61，55，4）.专业.专注.注：本题中所求深度优先序列和广度优先序列有多种，以上为其中一种。源点终点最短路径路径长度（A）深度遍历：1，2，3，8，4，5，7，6或（B）广度遍历：1，2，4，6，3，5，7，8（C）拓扑序列：1，2，4，6，5，3，7，8（D）最短路径：1，2，5，7，8（E）关键路径：1，6，5，3，8按层遍历二叉树LayerOrder(BiTreeroot){LinkQueueQ;InitQueue(&Q);if(root==NULL)return;EnterQueue(&Q,root);while(!Empty(&Q)){DelQueue(&Q,&p);visite(p->data);if(p->LChild!=NULL)EnterQueue(&Q,p->LChild);if(p->RChild!=NULL)EnterQueue(&Q,p->RChild);}.专业.专注.55662423.专业.专注.1.专业.专注.1436136105052742748.1若对大小均为n的有序的顺序表和无序的顺序表分别进行查找，试在下列三种情况下分（1）查找不成功，即表中没有关键字等于给定值K的记录。（2）查找成功且表中只有一个关键字等于给定值K的记录。8.2画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均8.3试推导含12个结点的平衡二叉树的最大深度并画出一棵这样的树。8.4试从空树开始，画出按以下次序向2-3树(即3阶B-树)中插入关键码的建树过程：20，30，50，52，60，68，70。如果此后删除50和68，画出每一步执行后2-3树的状8.5选取哈希函数H(k)=(3k)%11，用线性探测再散列法处理冲突。试在0～10的散列地址空间中，对关键字序列（22，41，53，46，30，13，01，67）构造哈希表，并求等概率情况下查找成功与不成功时的平均查找长度。8.6试为下列关键字建立一个装载因子不小于0.75的哈希表，并计算你所构造的哈希表（ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG，CHANG，CHAO，YANG，JIN）8.7试编写利用折半查找确定记录所在块的分块查找算法。8.8试写一个判别给定二叉树是否为二叉排序树的算法。设此二叉树以二叉链表作存储结构，且树中结点的关键字均不同。.专业.专注.8.9编写算法，求出指定结点在给定的二叉排序树中所在的层数。8.10编写算法，在给定的二叉排序树上找出任意两个不同结点的最近公共祖先（若在两结8.11编写一个函数，利用二分查找算法在一个有序表中插入一个元素x，并保持表的有序8.12已知长度为12的表Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）。（1）试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树并求其等概率的情况下查找成功的平均查找长度。（2）若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。（3）按表中元素的顺序依次构造一棵平衡二叉排序树，并求其等概率的情况下查找成功8.13含有9个叶子结点的3阶B-树中至少有多少个非叶子结点？含有10个叶子结点的38.14写一时间复杂度为O(log2n+m)的算法，删除二叉排序树中所有关键字不小于x的结点，并释放结点空间。其中n为树中的结点个数，m为被删除的结点个数。8.15在平衡二叉排序树的每个结点中增加一个lsize域，其值为它的左子树中的结点数加1。编写一时间复杂度为O(logn)的算法，确定数中第k个结点的位置。用线性探测再散列法处理冲突，平均查找长度的上限为2。二、简单的员工管理系统。每个员工的信息包括：编号、、性别、出生年月、学历、职务、、住址等。系统的功能（1）查询：按特定条件查找员工。（2）修改：按编号对某个员工的某项信息进行修改。（3）插入：加入新员工的信息。（4）删除：按编号删除已离职的员工的信息。(5)排序：按特定条件对所有员工的信息进行排序。8．2【解答】5ASLsucc=（1+2X2+3X4+4X3）/10=2.9.专业.专注.ASLSUCC=(1X4+2X3+6)/8=2ASLUNSUCC=(2+1+8+7+6+5+4+3+2+1+1)/11=40/118.12【解答】ASLSUCC=(1+2X2+3X3+4X3+5X2+6)/12=3.5(2)排序为：Apr,Aug,Dec,Feb,Jan,July,June,Mar,May,Nov,Oct,Sep折半查找ASLSUCC=(1+2X2+3X4+4X5)/12=37/12.专业.专注.unsucc.专业.专注..专业.专注..专业.专注.9.1以关键码序列（503，，512，061，908，170，897，275，653，426）为例，手工执行以下排序算法，写出每一趟排序结束时的关键码状态：（1）直接插入排序2）希尔排序（增量d[1]=5（3）快速排序4）堆排序；（5）归并排序6）基数排序。9.2一组关键字码，40，27，28，12，15，50，7，采用快速排序或堆排序，写出每趟9.3不难看出，对长度为n的记录序列进行快速排序时，所需进行的比较次数依赖于这n=7时在最好情况下需进行多少次比较？请说明理由。对n=7给出一个最好情况的初始排列实例。9.4假设序列由n个关键字不同的记录构成，要求不经排序而从中选出关键字从大到小顺序的前k(k<n)个记录。试问如何进行才能使所作的关键字间比较次数达到最小？9.5插入排序中找插入位置的操作可以通过二分查找的方法来实现。试据此写一个改进9.6编写一个双向起泡的排序算法，即相邻两遍向相反方向起泡。9.7编写算法，对n个关键字取整数值的记录序列进行整理，以使所有关键字为负值的记录排在关键字为非负值的记录之前，要求：采取顺序存储结构，至多使用一个记录的辅助存储空间；算法的时间复杂度O(n)；讨论算法中记录的最大移动次数。9.8试以单链表为存储结构实现简单选择排序的算法9.9假设含n个记录的序列中，其所有关键字为值介于v和w之间的整数，且其中很多关键字的值是相同的。则可按如下方法排序：另设数组number[v...w]且令number[i]为统排序方法，并讨论此方法的优缺点。个数少于s,且s=?√n?.试写一个算法,用O(n)时间和O(1)附加空间完成这两个有序序列的归并。9.11偶交换排序如下所述：第一趟对所有奇数i,将a[i]和a[i+1]进行比较；第二趟对所有偶数i,将a[i]和a[i+1]进行比较，若a[i]>a[i+1],则将两者交换；第一趟对所有.专业.专注.（2）分析当初始序列为正序或逆序两种情况下，奇偶交换排序过程中所需进行的关键（3）写出奇偶交换排序的算法。9.12设计一个用链表表示的直接选择排序算法。9.13插入排序中找插入位置的操作可以通过二分查找的方法来实现。试据此写一个改进后9.14一个线性表中的元素为正整数或负整数。设计一个算法，将正整数和负整数分开，使线性表的前一半为负整数，后一半为正整数。不要求对元素排序，但要尽量减少交换写一个从空堆开始一个一个添入元素的建堆算法。9.17试比较直接插入排序、简单选择排序、快速排序、堆排序、归并排序、希尔排序和基数排序的时空性能、稳定性和适用情况。9.18在供选择的答案中填入正确答案：(1)、排序（分类）的方法有许多种：__A__法从未排序序列中依次取出元素，与排序序列（初始为空）中的元素作比较，将其放入已排序列的正确位置上；__B__法从未排序序列中挑选元素，并将其依次放入已排序序（初始时为空）的一端；交换排序法是对序列中元素进行一系列的比较，当被比较的两元素逆序时进行交换。__C___和__D__是基于这类方法的两种排序方法，而__D__是比__C__效率更高的方法，利用某种算法，根据元素的关键值计算出排序位置的方法是__E__。供选择答案序序序排排泡数冒基④⑧序序排排入希插哈③⑦序序排排速分②⑥序序排排择并选归①⑤(2)、一组记录的关键字为（46，79，56，38，40，84），利用快速排序的方法，以第一个记录为基准得到的一次划分结果为。A、38，40，46，56，79，84B、40，38，46，79，56，84C、40，38，46，56，79，84D、40，38，46，84，56，79A、堆排序B、冒泡排序C、快速排序D、SHELL排序()在一个大堆中，最小元素不一定在最后。()对n个记录采用快速排序方法进行排序，最坏情况下所需时间是o（nlog2n）。()在执行某排序算法过程中，出现了排序码朝着与最终排序序列相反方向移动的现象，则称该算法是不稳定的。一、随机生成30个数，试比较直接插入排序、简单选择排序、起泡排序、快速排序、堆排序和希尔排序的时空性能和稳定性。给出n个学生的考试成绩表，每条信息由与分数组成。.专业.专注.+(n+1))=(n+2)/2；两者不相同。（2）表中只有一个关键字等于给定值k的记录，无序表、有序表：顺序查找成功时，平均查找长度均为1/(n)*(1+2+…+n)=(n+1)/2；两者相同。（3）表中只有m个关键字等于给定值k的记录，无序表：ASL=n+1；有序表：ASL=（n+1）/2+m；两者不相同。582899747ASL=1/10（1+2*2+4*3+3*4）=2.99.119.14.专业.专注.中一9.19ASL=（4*1+2*2+3+6）/8=17/89.25intSearch-Seq(SSTableST,KeyTypekey){//在顺序表ST中顺序查找其关键字等于key的数据元素，ST按关键字自大至小有序，//若找到，则函数值为该元素在表中的位置，否则为0ST.elem[ST.length+1].key=key;for(i=1;ST.elem[i].key>key;++i);if(ST.elem[i].key==key)&&(i<=ST.length)returnielsereturn0;.专业.专注.}//Search-Seq9.31TelemTypeMaxv(BitreeT){//返回二叉排序树T中所有结点的最大值for(p=T;p->rchild;p=p->rchild);returnp->data;}//MaxvTelemTypeMinv(BitreeT){//返回二叉排序树T中所有结点的最小值for(p=T;p->lchild;p=p->lchild);returnp->data;}//MinvStatusIsBST(BitreeT){//判别T是否为二叉排序树((!T->lchild)||((T->lchild)&&(IsBST(T->lchild)&&(Maxv(T->lchild)<T->data)))&&((!T->rchild)||((T->rchild)&&(IsBST(T->rchild)&&(Minv(T->rchild)>T->data)))returnOKelsereturnERROR;}//IsBST9.33StatusOutputGEx(BitreeT,TelemTypex){//从大到小输出给定二叉排序树T中所有值不小于x的数据元素print(T->data);if(OutputGEx(T->lchild,x))returnOK;}elsereturnOK;}elsereturnOK;}//OutputGExintSearch_Sq(SSTableST,intkey){if(i>ST.length||ST.e.专业.专注.intSearch_Bin_Digui(SSTableST,intkey,intlo{returnSearch_Bin_Digui(ST,key,loelsereturnSearch_Bin_Digui(ST}intLocate_Bin(SSTableST,intkey){elseif(key>=r[ST.length].key)while(low<=high){if(key>=r[mid].key&intSearch_IdxSeq(IdxSqListL,intkey)//分块查{if(key>L.idx[L.blknum].mwhile(low<=high&&!found)//折半查找记录所在{if(key<=L.idx[mid].max.专业.专注.}for(k=j;L.elem[k]!=分析:在块进行顺序查找时,如果需要设置监视哨,则必须先保存相邻块LNode*Search_CSList(CSList&L,intkey)//在有序单循环链表存储结构上的查找算法,假定每次查找都{for(p=L.h,i=1;p->data!=key;for(p=L.t,i=L.tpos;p->data!=key;分析:由于题目中假定每次查找都是成功的,所以本算法中没有关于查找失败的DLNode*Search_DSList(DSList&L,intkey)//在有序双向循环链表存储结构{p=L.sp;{while(p->data>key)p=p->pre;}.专业.专注.{while(p->data<key)p=p->next;}{{if(T->lchild)MaxLT_MinGT(T-{if(T->lchild)Print_N{.专业.专注.{while(!p->ltag)p=p->lchild;//找到最小while(p&&p->data<b){if(p->data>a)printf({while(!p->ltag)p=p->lchild;{{{q=(BiThrNode*)malloc(sizeo}elseBSTree_Insert_Ke{{q=(BiThrNode*)malloc(sizeo}elseBSTree_Insert_Ke{while(!p->ltag)p=p->lchild;//找到中序起始while(p){.专业.专注.{}{while(!p->ltag)p=p->lchild;}//while//借助中序遍历找到元素x及其前驱和后继结点{elseif(T->ltag&&!T->rtag)//结elseif(!T->ltag&&!T->rtag{while(!r->rtag){}分析:本算法采用了先求出x结点的前驱和后继,再删除x结点的办法,这样修改线索时会比较简单,直接让{{.专业.专注.{}{}S->lchild=NULL;//插入的新结分析:这是一个与课本上不同的插入算法.在合并过程中,并不释放式来完成合并.这样,就必须按照后序序列把一棵树中的元素逐个连接构的混乱.voidBSTree_Split(BiTree&T,BiTree&A,BiT{if(T->rchild)BSTree_SplelseInsert_Key(B,T){{}{}BlcNode*lchild,*rc{.专业.专注.returnLocate_BlcTree(T->lchild,k);/BPLinkchild[MAXCHILD];//非叶结点的BPNode*next;//指向下一}{while(p.tag==BRANCH)//沿分支向下{for(i=0;i<p->keynum&&key>p->key[i];i+}for(i=0;i<p->keynum&&key!=p->key[i];i+{q=(TrieNode*)malloc(sizewhile(p&&i<=klen&&p->bh.ptr[ord(key[i])]){{p->bh.ptr[ord(key[i])]=q;/.专业.专注.}{r=(TrieNode*)malloc(sizeof(TrieNode));/last->bh.ptr[ord(key[i-1]r->bh.ptr[ord(p->lf.k[i])]=p;//新分支结点与新老}分析:当自上而下的查找结束时,存在两种情况.一种情况,树中没有待插一个叶子结点并连到分支结点上即可.另一种情况,有同义词,此时的部位新建一个下一层的分支结点,再把同义词和新关键字的叶子结点连到新分支结点的下一层.{while(p&&p->kind==BRANCH&&i