第二章习题答案及练习.ppt

1、计算机软件基础(第三版) 第二章习题答案及练习,( a) O(n2) (b) O(n) (c)O(n3) 3. O(n3),8. 统计输入数中正数和负数的个数，输入0则结束。main() int x,num1=0,num2=0; printf(input num); scanf(%d,(1) L=P-link;,(2) R-data=P-data;,9. 对以下单链表分别执行下列各程序段,并画出结果示意图.,(3) R-data=P-link-data;,(4) P-link-link-link-data=P-data;,(5) T=P; while(T!=NULL) T-data=(T-da

2、ta)*2; T=T-link; ,(6) T=P; while(T-link!=NULL) T-data=(T-data)*2; T=T-link; ,(7) P=(JD*)malloc(sizeof(JD); P-data=10; R-link=P; P-link=S;,P,10,(8) T=L; T-link=P-link; free(P);,(9) S-link=L;,如果 S-link= =L 则S所指向的结点为尾结点.,12. (c) dcba 13. (d) 9,5,7,3 14. (a) T=T+1,15. bc , 2,#14 图示,16. 采用队列数据结构。要做的工作：开辟

3、一个队列结构的线性表；设置一个队头指针和一个队尾指针；有报到的或完成任务的，就排在队尾，需要工人做工时，从队头选派工人。,17. 入栈序列是(1、2、3），出栈序列是（2、1、3）,19. i*(i-1)/2+j,28.有n个叶子结点的哈夫曼树，其结点总数为2n-1,23. n 24. 12 i-1 25. CDBFGEA 26. 1100 27. 8,26. A, B, C, D, E 9, 7 , 3, 5,11 C的编码是1100,21. void change(NODE *T) NODE *m; if(T!=NULL) m=T-L T-L=T-R; T-R=m; change(T-L)

4、; change(T-R); ,typedef struct node Int data； Struct node *L，*R； NODE；,A,C,B,D,A,C,B,D,试以二叉链表作为存储结构，将二叉树中所有结点的左右子树进行交换,34. O(n) 35. (b) ab 36. 散列 37. 块与块之间按关键字有序。 39. 构造哈希函数，解决冲突。 n(n+1)/2 直接插入排序 18，307，1423 8,给出下列函数的递归和非递归算法 F(n)=,n+1,n*F(n-1),int F(int n), int m; if(n=0) m=1; else m=n*F(n-1); retu

5、rn (m);,非递归函数,int F(int n) int f1=1,s=1; if(n=0) return 1; while(s=n) f1=f1*s; s=s+1; return (f1);,int F(int n) int cj; if (n= =0|n= =1) cj=1; else cj=n*F(n-1); return(cj); ,F(4),n,4,cj=4*F(3);,Return(cj);,n,2,cj=2*F(1);,Return(cj);,n,3,cj=3*F(2);,Return(cj);,n,1,cj=1,Return(cj);,补充作业3 程序的功能是什么? 根据下

6、面图示的递归执行过程,给出二叉树先序遍历算法的执行过程,int search(NODE* LB,int e) NODE *p; LB=p; while(p-data!=e) ,在链式线性表LB中查找值为e的数据元素的位置的函数,typedef struct node,int data;,struct node *next NODE,第二版p70 #7,e,int AA（R，e） P=R；int n=1； while（P-data!=e | p-next=NULL) p=p-next; n=n+1; if(p-next=NULL ,关系运算符： = = = !=,逻辑运算符： int m=0;

7、float a; scanf(“%f”, /程序有问题吗？,AA( int an);/错在哪？ AA(int b，n) int b，n； . main() static int a7; AA(a,7);,a0,b0,top1,T1=B/C,A-B/C+D*E；,初态,(a),top2,OS,NS,B,A,;,(b),OS,A,;,(c),NS,OS,T2,T1,A,+,;,(e),NS,OS,T2,T3,+,;,(f),T3=A-T1,NS,OS,/,C,T1,A,;,(d),NS,OS,T4,；,T4=T2+T3,NS,(h),A-B/C+D*E；,T1=B/C,T1,D,E,+,*,T2=D*E,错在哪？,在电话系统中,基本的数据元素是(用户名,电话号码),电话系统的数据是大量的这类数据元素的集合.其中用户名是用汉语拼音代替,数据元素的排列是按拼音字母升序排列,只有这样,才能进行高效率查询. 由于该系统中数据元素的数量事先很难确定,增加或撤消用户电话是常有的操作. 问题: 1. 如果让你设计一个电话号码查询系统, 你认为采用什么样的数据结构最好?为什么? 2. 该系统中都有哪些常用的操作? 简述每种操作的基本思想.,1 阅读程序并回答问题： （1） 程序执行了什么功能？ （2） 针对右面的图，写出程序的运行结果。 typedef struct Bi