《习题答案及练习.ppt》由会员分享，可在线阅读，更多相关《习题答案及练习.ppt（23页珍藏版）》请在三一办公上搜索。
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-data)*2;T=T-link;,(6)T
2、=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)dcba13.(d)9,5,7,314.(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.n24.12 i-125.CDBFGEA26.110027.8,26.A,B,C,D,E 9,7,3,5,11C的编码是1100,21.void change(NODE*T)NODE*m;if(T!=NULL)m=T-L T-L=T-R;T-R=m;change(T-L);change(T-R);,typedef struct nodeInt data；Struct node*L，*R；NODE；,A,C,B,D,A,C,B
4、,D,试以二叉链表作为存储结构，将二叉树中所有结点的左右子树进行交换,34.O(n)35.(b)ab36.散列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);return(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
5、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 程序的功能是什么?根据下面图示的递归执行过程,给出二叉树先序遍历算法的执行过程,int search(NODE*LB,int e)NODE*p;LB=p;while(p-data!=e),在链式线性表LB中查找值为e的数据元素的位置的函数,typedef struc
6、t 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,关系运算符：=!=,逻辑运算符：&|!,错在哪？,main()int n=0;int m=0;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；,
7、初态,(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 BiTNode int data;struct BiTNode*lchild,*rchild;BiTNode,*BiTree;int preprn(BiTtree T)if(T-lchild!=NULL),a,b,d,e,c,g,f,h,i,
