数据结构课后习题及其他期末复习资料.ppt

首元结点、头结点、头指针的区别,习题选讲,栈与队列,树与二叉树,2.1 单项选择题 1. 一个向量（即一批地址连续的存储单元）第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是_ _。 A. 110 B. 108 C. 100 D. 120 2. 线性表的顺序存储结构是一种_ _的存储结构，而链式存储结构是一种_ _的存储结构。 A随机存取 B索引存取 C顺序存取 D散列存取 3. 线性表的逻辑顺序与存储顺序总是一致的，这种说法_ _。 A. 正确 B. 不正确 4. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址_ _。 A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续或不连续都可以,B,A,C,B,D,5. 在以下的叙述中，正确的是_ _。 线性表的顺序存储结构优于链表存储结构 线性表的顺序存储结构适用于频繁插入/删除数据元素的情况 线性表的链表存储结构适用于频繁插入/删除数据元素的情况 线性表的链表存储结构优于顺序存储结构 6. 每种数据结构都具备三个基本运算：插入、删除和查找，这种说法_ _。 A. 正确 B. 不正确 7. 不带头结点的单链表head为空的判定条件是_。 A. head= =NULL B. head-next= =NULL C. head-next= =head D. head!=NULL 8. 带头结点的单链表head为空的判定条件是_。 A. head= =NULL B. head-next= =NULL C. head-next= =head D. head!=NULL,C,A,A,B,9. 非空的循环单链表head的尾结点（由p所指向）满足_。 A. p-next= =NULL B. p= =NULL C. p-next= =head D. p= =head 10. 在双向循环链表的p所指结点之后插入s所指结点的操作是_。 A. p-right=s; s-left=p; p-right-left=s; s-right=p-right; B. p-right=s; p-right-left=s; s-left=p; s-right=p-right; C. s-left=p; s-right=p-right; p-right=s; p-right-left=s; D. s-left=p; s-right=p-right; p-right-left=s; p-right=s; 11. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行_。 A. s-next=p-next; p-next=s; B. p-next=s-next; s-next=p; C. q-next=s; s-next=p; D. p-next=s; s-next=q;,C,D,C,12. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行_。 A. s-next=p; p-next=s; B. s-next=p-next; p-next=s; C. s-next=p-next; p=s; C. p-next=s; s-next=p; 13. 在一个单链表中，若删除p所指结点的后续结点，则执行_。 A. p-next= p-next-next； B. p= p-next; p-next= p-next-next； C. p-next= p-next; D. p= p-next-next； 14. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较_个结点。 A. n B. n/2 C. (n-1)/2 D. (n+1)/2,B,A,D,15. 在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是_ _。 A. O(1) B. O(n) C. O (n2) D. O (nlog2n),1. B 2. A, C 3. B 4. D 5. C 6. A 7. A 8. B 9. C 10. D 11.C 12.B 13.A 14.D 15.B,B,首元结点、头结点、头指针的区别,首元结点：链表中存储线形表中第一个数据元素的结点,头结点：在链表首元结点之前附设一个结点。该结点的数据域不存储数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。,头指针：是指向链表中第一个结点（头结点或首元结点） 的指针。若链表中附设头结点，则不管线性表是否为空表， 头指针均不为空，否则表示空表的头指针为空。,linklist creater( ) char ch; linklist head; listnode *p，*r; /(， *head;) head=NULL;r=NULL; while(ch=getchar( )!=n) p=(listnode *)malloc(sizeof(listnode); pdata=ch; if(head=NULL) head=p; r=head; else,rnext=p; r=p; if (r!=NULL) rnext=NULL; return(head); ,linklist createlistr1( ) char ch; linklist head=(linklist)malloc(sizeof(listnode); listnode *p，*r r=head; while(ch=getchar( )!=n p=(listnode*)malloc(sizeof(listnode); pdata=ch; rnext=p; r=p; rnext=NULL; return(head); ,说明：第一个生成的结点是开始结点，将开始结点插入到空表中，是在当前链表的第一个位置上插入，该位置上的插入操作和链表中其它位置上的插入操作处理是不一样的，原因是开始结点的位置是存放在头指针（指针变量）中， 而其余结点的位置是在其前趋结点的指针域中。算法中的第一个if语句就是用来对第一个位置上的插入操作做特殊处理。,求表长 算法思路：设一个移动指针和计数器，初始化后，所指结点后面若还有结点，向后移动，计数器加1。 (1)设L是带头结点的单链表(线性表的长度不包括头结点)。 算法如下：,加头没加尾,int Length_LinkList1 (LinkList L) Lnode * p=L; /* p指向头结点*/ int j=0; while (p-next) p=p-next; j+ /* p所指的是第 j 个结点*/ return j; ,(2)设L是不带头结点的单链表。 算法如下： int Length_LinkList2 (LinkList L) Lnode * p=L; int j; if (p=NULL) return 0; /*空表的情况*/ j=1; /*在非空表的情况下，p所指的是第一个结点*/; while (p-next ) p=p-next; j+ return j; ,在上面的算法中，第一个结点的处理和其它结点是不 同的，原因是第一个结点加入时链表为空，它没有直 接前驱结点，它的地址就是整个链表的指针， 需要放 在链表的头指针变量中；而其它结点有直接前驱结点， 其地址放入直接前驱结点的指针域。,如果我们在链表的开始结点之前附加一个结点，并称它为头结点，那么会带来以下两个优点： a、由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其它位置上的操作一致，无需进行特殊处理； b、无论链表是否为空，其头指针是指向头结点在的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。,2.21 void reverse(SqList /reverse,例2.5 已知单链表H，写一算法将其倒置。 算法思路：依次取原链表中的每个结点，将其作为第一个结点插入到新链表中去，指针p用来指向当前结点，p为空时结束。算法如下：,void reverse (Linklist H) LNode *p; p=H-next; /*p指向第一个数据结点*/ H-next=NULL; /*将原链表置为空表H*/ while (p) q=p; p=p-next; q-next=H-next; /*将当前结点插到头结点的后面*/ H-next=q; ,该算法只是对链表中顺序扫描一边即完成了倒置，所以时间性能为O(n)。,2.22 void LinkList_reverse(Linklist 为简化算法,假设表长大于2,Rev(linklist L) /带头结点的单链表 Pnode p,q,r; p=L-link;if(p=NULL) return; q=p-link; if(q=NULL) return; r=q-link; while(r!=NULL) q-link=p; p=q; q=r; r=r-link; q-link=p; L-link-link=NULL; L-link=q; ,已知线性表A的长度为n，并且采用顺序存储结构，写一算法删除线性表中所有值为X的元素,Del (sqlist L,datatype x) int I,j; for(I=0;in;I+) if(L-datai=x) for(j=I;jn;j+) L-dataj=L-dataj+1; L-n-; ,L 指向无头结点的线性链表，写出删除链表中从下标为I的结点开始的连续k个结点的算法,Linklist Del (linklist L,int I,int k) pnode p,q; int j=0; p=L; while(p-link!=NULL,删除单链表中值相同的多余结点,Diff_link(Linklist llist) pnode p,q,r; p=llist-link; while( p!=NULL) q=p; r=q-link; while(r!=NULL) if(r-info=p-info) t=r-link; q-link=t; free(r); r=t; ,else q=r;r=r-link; P=p-link ,Void diff_link(linklist L) pnode p,q,r; for(p=L-link;p!=NULL;p-link) for(r=p,q=p-link;q!=NULL;q=q-link) if(p-info=q-info) r-link=q-link; free(q); q=r; else r=r-link; ,归并两个单链表为一个单链表,Linklist combine(linklist x,linklist y) linklist llist=(linklist)malloc(sizeof(struct Node); Pnode p=llist,px=x-link,py=y-link; While(px!=NULL|py!=NULL) if(px!=NULL) p-link=(linklist)malloc(sizeof(struct Node); p=p-link; P-info=px-info; px=px-link; if(py!=NULL),p-link=(linklist)malloc(sizeof(struct Node); p=p-link; P-info=px-info; py=py-link; P-link=NULL; Return(llist);,12、归并两个线性表,void merge1(LinkList /while /merge1,2.15 void ListConcat(LinkList ha,LinkList hb,LinkList hc)/把链表hb接在ha后面形成链表hc hc=ha;p=ha; while(p-next) p=p-next; p-next=hb; return(hc); /ListConcat,2.19 Status Delete_Between(Linklist L,int mink,int maxk)/删除元素递增排列的链表L中值大于mink且小于maxk的所有元素 p=L; while(p-next-datanext; /p是最后一个 不大于mink的元素 if(p-next) /如果还有比mink更大的元素 q=p-next; while(q-datanext; /q是第一个不小于maxk的元素 p-next=q; /Delete_Between,2.31 Status Delete_Pre(listnode *s)/删除单循环链表中结点s的直接前驱 p=s; while(p-next-next!=s) p=p-next; /找到s的前驱的前驱p p-next=s; return OK; /Delete_Pre,Linklist combine(Linklist list1,Linklist list2) Linklist list3=(Linklist)malloc(sizeof(struct Node); Pnode p1=list1-link,p2=list2-link,p3=list3; if(p1=list1,else p3-info=p2-info; p2=p2-link; p3-link=list3; return list3;,2.32 P指向双向链表的中间结点，写出完成下列功能的语句。 （1）在p结点后插入指针S所指向的结点。 （2）删除P所指结点的前驱结点。 （3）删除P结点。,(1) s-pre=p; s-next=p-next; p-next-pre=s; p-next=s;,(2) q=p-pre; p-pre=q-pre; q-pre-next=p; free(q);,(3) p-pre-next=p-next; p-next-pre=p-pre; free(p);,解决计算机与打印机之间速度不匹配的问题，需要设置一个数据缓冲区，应是一个什么结构。,判断一个队列Q（元素最多为n)为空的条件是：,Q-rear=Q-front,判断一个队列Q（元素最多为n)为满的条件是：,Q-rear-Q-front=n,判断一个循环队列Q（元素最多为n)为空的条件是：,判断一个循环队列Q（元素最多为n)为满的条件是：,Q-rear=Q-front,Q-front=Q-rear+1)%n,设有两个栈都采用顺序存储表示，并且共有一个存储区，现采用栈顶相对，迎面增长的方式存储，写出对两个站进行插入删除的操作。,分析：两个栈的栈底分别设在数组的两个断点，用两个指针指示两个栈的栈顶，两个栈迎面增长，当两个栈定相遇时发生溢出。,#define maxsize 100 Typedef struct tstack datatype datamaxsize; Int top1,top2; Int stacksize; tstack;,(1)初始化算法： State initstack(tstack *ts) ts=(tstack*)malloc(sizeof(sturct tstack); if(ts=NULL) printf(“out of spacen”); Ts-stacksize=maxsize; Ts-top1=-1; Ts-top2=maxsize; Return OK; ,入栈算法： Push(tstack *ts,int I,datatype x) if(top1=top2）return(overflow); If(I=0) top1+; ts-datats-top1=x; Else top2-; ts-datats-top2=x; Retrun ok; ,出栈算法： Pop(tstack *ts,int I,datatype x) if(I=0) if(top1=-1) return error; X=ts-datats-top1; Top1-; else if(top2=maxsize) return error; X=ts-datats-top2; Top2+; Return x; ,3.17 int IsReverse()/判断输入的字符串中 /IsReverse,abcde&edcba,3.31 int Palindrome_Test()/判别输入的字符串是否回文序列,是则返回1,否则返回0 InitStack(S);InitQueue(Q); while(c=getchar()!=) Push(S,c);EnQueue(Q,c); /同时使用栈和队列两种结构 while(!StackEmpty(S) Pop(S,a);DeQueue(Q,b); if(a!=b) return 0; return 1; /Palindrome_Test,abcba,递归算法为：,long Fib(int n) if(n=1|n=2) /终止递归条件 return 1; else return Fib(n-1)+Fib(n-2);,非递归算法为 long Fib1(int n) int a,b,c;/C代表当前项，a和b分别代表当前项前面的第2项和第1项 a=b=1; /给a和b赋初值1 if(n=1|n=2) return 1; else for(int i=3;i=n;i+) c=a+b; /求出当前项 a=b;/把前面第1项赋给前面第2项 b=c;/把当前项赋给前面第1项 return c;/返回所求的第n项 ,若将f=1+1/2+1/3+.+1/n (n3)转化为递归函数，其 递归出口是 ，递归体是 。,F(1)=1,F(n)=f(n-1)+1/n,有如下递归算法： Void print(int w) int I; if(w!=0) print(w-1); for(I=1;I=w;I+) printf(“%3d”,w); printf(“n”); ,Print（4）的结果是：,1 2 3 3 4 4 4,有一个不带头结点的单链表h，设计如下递归算法：,1、求以h为头指针的单链表的结点个数,设count(h)为计算单链表h的结点个数，递归模型如下： Count(h)=0 h=null Count(h)=1+count(h-next),Int count(listnode h) if (h=null) return 0; else return(1+count(h-next); ,2、正向显示以h为头指针的单链表的所有节点值,递归模型： Traverse(h) h=null 不做任何事 Traverse(h)=输出*h结点之值；traverse(h-next) 其他情况,Void traverse （listnode h) if(h=null) return; printf(“%d”,h-data); traverse(h-next); ,3、反向显示以h为头指针的单链表的所有结点值,Void revtraverse(listnode h) if(h=null) return; revtraverse(h-next); printf(“%d”,h-data); ,4、删除以h为头指针的单链表中值为x的第一个结点,Int delnode(listnode h,int x) listnode p; if(h=null) return 0; if(h-data=x) p=h; h=h-next; free(p); return(1); else delnode(h-next,x);,2.11设顺序表va中的数据元素递增有序，试写一算法将X插入顺序表的适当位置，该表有序。 Void insert(vector a,int n,int x) int I,j; if(xan) an+1=x; else I=1; while(x=aI) I+; for(j=n;j=I;j-) aj+1=aj; aI=x;n+;,比较两个线性表的大小。两个线性表的比较依据下列方法：设A、B是两个线性表，均用向量表示，表长分别为m和n。 A和B分别为 A 和 B 中除去最大共同前缀后的子表。 例如A=(x,y,y,z,x,z)， B=(x,y,y,z,y,x,x,z)，两表最大共同前缀为 (x,y,y,z) 。 则 A=（x,z）， B=（y,x,x,z）， 若A=B= 空表，则A=B； 若A=空表且B空表，或两者均不空且A首元素小于B首元素，则AB。,算法思路：首先找出A、B的最大共同前缀；然后求出A和B，之后在按比较规则进行比较，AB 函数返回1；A=B返回0；AB返回-1。 算法如下： int compare( A,B,m,n) int A,B; int m,n; int i=0,j,AS,BS,ms=0,ns=0; /*AS,BS作为A,B*/,while (Ai=Bi) i+; /*找最大共同前缀*/ for (j=i;j0 | ms0 ,node *link(x,y) node *x,*y; node *r,*s,*p,*q,*z; z=(node*)malloc(sizeof(node); r=z;p=x;q=y; While(p!=NULL|q!NULL) if(p!=NULL) s=(node*)malloc(sizeof(node); s-data=p-data; r-next=s; r=s; p=p-next; ,If(q!=NULL) s=(node*)malloc(sizeof(node); s-data=q-data; r-next=s; r=s; q=q-next; r-next=NULL; return(z); ,int GetValue_NiBoLan(char *str)/对逆波兰式求值 p=str; InitStack(s); /s为操作数栈 while(*p) if(*p是数) push(s,*p); else pop(s,a);pop(s,b); r=compute(b,*p,a); /假设compute为执行双目运算的过程 push(s,r); /else p+; /while pop(s,r);return r; /GetValue_NiBoLan,Compute(int b,char c,int a) float d; switch(c) case +:d=b+a; break; case -:d=b-a; break; case*:d=b*a; break; case /: d=b/a; break; ,【例1】试找出分别满足下面条件的所有二叉树： （1）前序序列和中序序列相同； （2）中序序列和后序序列相同； （3）前序序列和后序序列相同； （4）前序、中序、后序序列均相同。,解： （1） 空二叉树或任一结点均无左子树的非空二叉树 （2） 空二叉树或任一结点均无右子树的非空二叉树 （3） 空二叉树或仅有一个结点的二叉树 （4） 同（3）,【例2】已知一棵二叉树的前序遍历的结果序列是 ABECDFGHIJ 中序遍历的结果序列是 EBCDAFHIGJ 试画出这棵二叉树。,【解答】前序序列 ABECDFGHIJ，中序序列 EBCDAFHIGJ 时：,A,EBCD,FHIGJ,A,B,E,CD,HIGJ,F,前序序列 ABECDFGHIJ 中序序列 EBCDAFHIGJ,A,B,F,G,C,E,D,HI,J,A,B,E,C,D,F,G,J,H,I,例3：一棵二叉树的层序序列为ABCDEFGHIJ,中序列为DBGEHJACIF,求这棵二叉树,例4、已知一棵树的先根遍历序列GFKDAIEBCHJ,后根遍历序列为DIAEKFCJHBG,求对应的树。,树的先根对应二叉树的先序，树的后根对应二叉树的中序遍历,例5、若n个节点k条边的无向图是一个森林，(nk),则该森林中有多少棵树？,解：设森林中有m棵树，每棵树的顶点数为.,例6、深度为5的二叉树至多有结点数为多少？（深度从1开始计数） A 16 B 30 C 31 D 32 例7、高度为h的二叉树上只有度为0和2的结点，则此类二叉树中所包含的结点数至少为多少？（从1开始计数） A 2h B 2h-1 C 2h+1 D h+1,M=n-k,【例8】假定用于通信的电文仅由 8 个字母 c1, c2, c3, c4, c5, c6, c7, c8 组成, 各字母在电文中出现的频率分别为 5, 25, 3, 6, 10, 11, 36, 4。试为这 8 个字母设计不等长 Huffman 编码, 并给出该电文的总码数。,【解答】,0000 0001 001 0100 0101,011 10 11,则Huffman编码为 c1 c2 c3 c4 c5 c6 c7 c8 0100 10 0000 0101 001 011 11 0001 电文总码数为 4 * 5 + 2 * 25 + 4 * 3 + 4 * 6 + 3 * 10 + 3 * 11 + 2 * 36 + 4 * 4 = 257,例9 int LeafCount(Bitree T)/求二叉树中叶子结点的数目 if(!T) return 0; /空树没有叶子 else if(!T-lchild/左子树的叶子数加上右子树的叶子数 /LeafCount_BiTree,Int leafnum=0; Void countleaf(bintree t) if(t=null) return 0; If(t-lchild=null ,例10 void Bitree_Revolute(Bitree T)/交换所有结点的左右子树 T-lchildT-rchild; /交换左右子树 if(T-lchild) Bitree_Revolute(T-lchild); if(T-rchild) Bitree_Revolute(T-rchild); /左右子树再分别交换各自的左右子树 /Bitree_Revo