数据结构复习1、在单链表中指针所指结点有后继的条件是

1、在单链表Lpp-2、n（n大于1）个结点的各棵树中，其深度最小的那棵树的深度是 (2)n- (3) (4) (5) (6)n- 个结4、二叉树 7、在有序表A[1..12]A[12]8y指向二叉线索树的一叶子，xxyltag和rtag，1x(lchild,rchild分别代表左，x^.ltag:= ;x^.lchild:= ;y^.ltag:= y^.lchild:= ;x^.rtag:= ;x^.rchild:= IF(x^.lchild<>NIL)AND x^.lchild^.rchild:= (6)y 9、有N个顶点的有向图，至少需要量 13、n个结点的完全有向图含有边的数目 16、在一棵度为3的树中，度为2的结点个数是1，度为0的结点个数是6，则度为3的结点个数 全局量，且在调用count(t)0. struct data;structnode*lchild,*rchild;}node;intN2,NL,NR,N0;voidcount(node{if(t->lchild!=NULL)if(1) N2++;elseNL++; if(2) NR++;else if(t- ;if(t->rchild!=NULL) }/*callform:if(t!=NULL)

)stacktp。交换左、右子树 structnode{intdata;treelchild,rchild;}exchange(treet) r,p;tree stack[500];int while stack[(4) } （用O估计FORi:=1TOnDOFORj:=iTOnDO equal(l:pointer):boolean;VARp,q:pointer; result:Boolean;BEGINresult=true;p:=l^.link;q:=l^.pre;WHILE(p<>q)AND p^.data=q^.dataTHENBEGIN ; ; result=false和rear，且队头指针所指的单元闲置，则队满的条件是 ，队空的条件 26、下面表达式树所对应的表达式的前缀表达式是 ，后缀表达式 PROCinorder(bt:bitreptr);inistack(s);(1) WHILENOT [WHILEgettop(s)<>NILDO IFNOTempty(s)THEN [visit(gettop(s)^);p:=pop(s);(3) ]] 序列 MAX100typedefstruct{charinfo;structNode*llink,*rlink;}TNODE;charpred[MAX],inod[MAX];main(intargc,int{TNODE if(argc<3)exit0;strcpy(pred,argv[1]);strcpy(inod,argv[2]);}TNODE*restore(char*ppos,char*ipos,int{TNODE *ptr；char*rpos; if(n<=0)returnNULL; ;rpos<ipos+n;rpos++) if(*rpos==*ppos)break; ,kptr->rlink=restore((5) returnptr;}{if(ptr=NULL) }（1） DataType简称ADT)是指一个数学模型以及定义在非空的二叉树一定满足：某结点若有左孩子，则其中序前驱一定没有右孩子Yxm:正确kn个结点的完全二叉树，其编号最小的结点序号为2k-2+1。Yxm:错误nWPLHuffman4prime算法求最12435124351437528364yxh（4,6）①开放定址 撞，缺点是容易造成“即不是同义词的关键字争夺同一散列地址。b．di=12，-12，22，-22，…，k2（k≤m/2）称为二次探测再散列，它减少了，但不容易探测到全部表空4j+3（j为整数）的素数时才有可能。=②再散列法 函数计算散列地址，直到解决碰撞。该方法不易产生“，但增加了计算时间。③链地址法将关键字为同义词的记录在同一链表中，散列表地址区间用H[0..m-1]表示，分量初④建立公共溢出区设H[0..m-1]为基本表，凡关键字为同义词的记录，都填入溢出区示a,b,c,d,e，分别给出五个叶子对应的哈夫曼编码。7、采用哈希函数Ｈ（k）=3*kmod13并用线性探测开放地址法处理，在数列地址空间［0..12］中对关键字22,41,53,46,30,13,1,67,51（2）0123456789111212111 （3）ASLsucc=11/9 （4）ASLunsucc=29/131123491,2,3……，n,p1=npi1112、已知一个图如图所示，如从顶点a出发进行按深度优先遍历，可否得到序列acebdf 先遍历，能否得到序列abedfc?为什么？aacbefd010希表的实际平均查找长度是否满足要求α）m=15/0.67m=23H（key）=（关键字首尾字母在字母表中序号之和）MOD23。17datanexthead，链表无while {q=p; {if }tmp=q->data;q->data=p->data;p->data=tmp;p= } （2） sort(SqList&r,int while((1)) for )min=j;else max=j; )r[min] )r[min] >r[n-i+1];else((6));}(1)i<n-i+1(2)j<=n-i+1(3)r[j].key<r[min].key(4)min!=i(5)max==i(6)r[max]<-->r[n-i+1]堆是一种有用的数据结构.堆排序是一种_(1)_排序，堆实质上是一棵_(2)_N72，71，73是否满足堆的性质_(5)_。(1)选择(2)完全二叉 (3)O(nlogn底数为 (1)堆排序，快速排序，归并排序(2)归并排序(3)快速排序(4)堆排序第一趟第三趟第四趟第六趟第一趟第三趟第四趟第六趟1、voidAE(Stack&intx=Pop(S)+2*Pop(S);intfor(i=0;i<5;i++)Push(S,2*a[i]);while(!StackEmpty(S))print(Pop(S));}2voidABCBTNode*BT,int&c1,int&c2)if(BT!=NULL){}

if(BT->left==NULL&&BT->right==NULL) La。IntFor(i=0;i<5;i++)For(i=0;i<5;i++)4、intPrime(int{intintx=(int)sqrt(n);while(++i<=x)if(n%i==0)break;if(i>x)return1;elsereturn}A的功能：BiTree定义如下:TypedefstructBiTNode{emTypedata;structBiTNode*LChild,}BiTNode,{QueueQ;While(not If(e==NULL)break; }}}简述算法algovoidalgo(Queue{StackS;while(!QueueEmpty(Q))Push(&S,DeQueue(Q));while(!}yxh：(1)q中的元素为(8,7,5,4,22)q中的元素倒序。五算法填空 struct intstructnode}voiddel(lklistrear,int lklistq=rear //qif(q->next==q //rear->next==rearprintf(“itisempty!\n”); if_q- //rear { *ch； }HString*s，StatusStrCat(st*ts{intcharif(temp==NULL)return(0);for(i=0; for( ;i<s->len+t.len;i++)frs->ch=temp;}LNode是一个包含（data，Next）的结构体{LNode*newptr;newptr=newLNode;If {cerr<<"Memoryallocationfailare!"<<endl;} if LNode*While(P- LinkListf30(LinkListL,int{LinkListLc,p,pre; Lc=(LinkList)malloc(sizeof(ListNode));{ }{ }return}下列算法计算有向图GviintFindDegree(ALGraph*G,inti)//ALGraph{intdgree,j;EdgeNode*p; {while { p-{}}}return}中根：CGBAHEDJFI后根：GBCHEJIFDA出发，求它的深度优先生成树(4分(3）根据普利姆(Prim)算法，求它的最小生成树(请画出过程 列)(6分1xdata count1(lklisthead,int有深度。对每一结点，找其双亲，双亲的双亲，直至（根）0为止。intDepth(Ptree {intmaxdepth=0;{temp=0;while(f>0){temp++;f=t.nodes[f].parent;} //深度加1,并取新的双亲 maxdepth=temp;//最大深度更新} data[maxsize][maxsize]; crt for(i=1;i<=n;i++)for(j=1;j<=n;j++) for(i=1;i<=e;i++) } } clear(lklisthead) while p=head;head=head->next;} } depth(bitreptr if(!root) }} { {} voidInOrder(BiTree inttop=0;while(p||top>0){while(p)s[++top]=p;bt=p operate(ab,op)op算符，a和b分别表示左右两个运算对象。算法中允许直接函数operate(函数operate不必定义)，如果需要11编写算法，将一单链表逆转。要求逆转在原链表上进行，不允许重新构造一个链表（可以申明临时变量、指typedefstruct{ElemTypedata;StructLNode*next;}List,函数定义：voidinvert(List&typedefstructBiTNode{DataTypedata;StructBiTNode*LChild,*}BiTNode,函数定义：CountLeafBiTreeTint&LeafNum)voidCountLeaf(BiTreeT,int&LeafNum){{{

CountLeaf(T->lchild,LeafNum);structnode{elemtpstructnodeTypedefstructnode*bitreptr(指向根),*tpointer(指向一般结点);voidpreorder(bitreptrP)//P指向树根节点voidpreorder(bitreptr{{StatusInsert_Vex(MGraph&G,charv)//G上插入顶点{if(G.vexnum+1)>MAX_VERTEX_NUMreturnINFEASIBLE;returnvoidPrint_Hash(HashTableH)//按第一个字母顺序输出Hash表中的所有关键字,voidPrint_Hash(HashTableH)//按第一个字母顺序输出Hash表中的所有关键字,其中处理采用线性探测开放定{for(j=i;H.elem[j].key;j=(j+1)%hashsize[sizeindex线性探测if(H(H.elem[j].key)==i)printf("%s\n",H.elem[j]);intH(char*s)//Hash{if(s)returns[0]-96;//求关键一个字母的字母序号(小写)elsereturn0;structnode{elemtpstructnodeTypedefstructnode*bitreptr(指向根),*tpointer(指向一般结点);voidaftorder(bitreptrP){{}}StatusDelete_Arc(MGraph&G,charv,charw)//在邻接矩阵表示的图G上删除边{if((i=LocateV