习题答案及练习.ppt
计算机软件基础(第三版)第二章习题答案及练习2.(a)O(n2)(b)O(n)(c)O(n3)3.3.O(n3)8.统计输入数中正数和负数的个数,输入统计输入数中正数和负数的个数,输入0则结束。则结束。main()int x,num1=0,num2=0;printf(input num);scanf(%d,&x);while(x!=0)if(x0)num1=num1+1;else num2=num2+1;scanf(%d,&x);printf(Positive num is:%dn,num1);printf(Negative num is:%dn,num2);LS28375PR(1)L=P-link;28375PRSL(2)R-data=P-data;28575PRS9.对以下单链表分别执行下列各程序段对以下单链表分别执行下列各程序段,并画出结果示意并画出结果示意图图.(3)R-data=P-link-data;28775PRS(4)P-link-link-link-data=P-data;25375PRS(5)T=P;while(T!=NULL)T-data=(T-data)*2;T=T-link;S2PR1014616(6)T=P;while(T-link!=NULL)T-data=(T-data)*2;T=T-link;S2PR101468(7)P=(JD*)malloc(sizeof(JD);P-data=10;R-link=P;P-link=S;LS28375RP10(8)T=L;T-link=P-link;free(P);LS2837PRT5(9)S-link=L;LS28375PR如果如果 S-link=L 则则S所指向的结点为尾结点所指向的结点为尾结点.12.(c)dcba13.(d)9,5,7,314.(a)T=T+1AnAn-1An-2.A1AT是栈顶元素是栈顶元素T1030 40base15.bc ,2#14图示16.采用队列数据结构。要做的工作:开辟一个队列采用队列数据结构。要做的工作:开辟一个队列结构的线性表;设置一个队头指针和一个队尾指针;结构的线性表;设置一个队头指针和一个队尾指针;有报到的或完成任务的,就排在队尾,需要工人做工有报到的或完成任务的,就排在队尾,需要工人做工时,从队头选派工人。时,从队头选派工人。17.入栈序列是入栈序列是(1、2、3),出栈序列是(),出栈序列是(2、1、3)19.i*(i-1)/2+j28.有有n个叶子结点的哈夫曼树,其结点总数为个叶子结点的哈夫曼树,其结点总数为2n-123.n24.12 i-125.CDBFGEA26.110027.835817115592728CDAEB0000111126.A,B,C,D,E 9,7,3,5,11C的编码是的编码是110021.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;ABCDACBDACBD试以二叉链表作为存储结构,将二叉树中所试以二叉链表作为存储结构,将二叉树中所有结点的左右子树进行交换有结点的左右子树进行交换34.O(n)35.(b)ab36.散列散列37.块与块之间按关键字有序。块与块之间按关键字有序。39.构造哈希函数,解决冲突。构造哈希函数,解决冲突。40.n(n+1)/242.直接插入排序直接插入排序43.18,307,142344.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(sdata!=e)&(p!=NULL)p=p-next;if(p!=NULL)printf(n Found”);else printf(n Not find e);return p;在链式线性表在链式线性表LB中查找值为中查找值为e的数据元素的位置的函数的数据元素的位置的函数typedef struct node int data;struct node*next NODE第二版第二版p70#7eint 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&P-data!=e)printf(“ERRORn”);return(n);关系运算符:关系运算符:=!=逻辑运算符:逻辑运算符:&|!错在哪?错在哪?main()int n=0;int m=0;float a;scanf(“%f”,&a);while(a!=0)if(a0)n=n+1;else m=m+1;scanf(“%f”,&a);printf(“%d,%dn”,n,m);/程序有问题吗?程序有问题吗?AA(int an);/错在哪?错在哪?AA(int b,n)int b,n;.main()static int a7;AA(a,7);a0b0top1T1=B/CA-B/C+D*E;初态;(a)top2OSNSBA;(b)OSA;(c)NSOSEDT2*+;(e)NSOS(g)NSOST3T2+;(f)T3=D*ENSOS/C T1T2;(d)NSOST2=A-T1T4;T4=T2+T3NS(h)初态;(a)top2OSNSBA;(b)OSA;(c)NSOST2T1A+;(e)NSOS(g)NSOST2T3+;(f)T3=A-T1NSOS/C T1A;(d)NSOST4;T4=T2+T3NS(h)A-B/C+D*E;T1=B/CT1DE+*T2=D*E错在哪?错在哪?在电话系统中在电话系统中,基本的数据元素是基本的数据元素是(用户名用户名,电话号码电话号码),电话电话系统的数据是大量的这类数据元素的集合系统的数据是大量的这类数据元素的集合.其中用户名是用汉其中用户名是用汉语拼音代替语拼音代替,数据元素的排列是按拼音字母升序排列数据元素的排列是按拼音字母升序排列,只有这只有这样样,才能进行高效率查询才能进行高效率查询.由于该系统中数据元素的数量事先很难确定由于该系统中数据元素的数量事先很难确定,增加或撤消增加或撤消用户电话是常有的操作用户电话是常有的操作.问题问题:1.如果让你设计一个电话号码查询系统如果让你设计一个电话号码查询系统,你认为采用什么你认为采用什么样的数据结构最好样的数据结构最好?为什么为什么?2.该系统中都有哪些常用的操作该系统中都有哪些常用的操作?简述每种操作的基本思简述每种操作的基本思想想.1阅读程序并回答问题:(1)程序执行了什么功能?(2)针对右面的图,写出程序的运行结果。typedefstructBiTNodeintdata;structBiTNode*lchild,*rchild;BiTNode,*BiTree;intpreprn(BiTtreeT)if(T-lchild!=NULL)&(T-rchild!=NULL))printf(T-data);preprn(T-lchild);preprn(T-rchild);elsereturnOK;abdecgfhi