软件技术基础习题课资料

软件技术基础习题课P17-5：完数#include<stdio.h>//判断n是否是完数typedefintbool;boolisWanShu(intn){intsum=0,j;for(j=1;j<n;j++){if(0==n%j)sum+=j;}if(sum==n){printf("%d是完数,",n);return1;}else{return0;}}//输出整数的n的因子（自身除外）voidprintFactor(intn){inti;printf("%d的因子:",n);for(i=1;i<n;i++){if(n%i==0)printf("%d",i);}printf("\n");}intmain(){ inti; for(i=1;i<=1000;i++) { if(isWanShu(i)) {//如果i是完数，则输出它的因子。

printFactor(i); } } return0;}2.3习题P26一、1B，2CB,3BD,4C,5C,6CB,7A,8D二、1×(基本)，2√，3√，4×(最小),5√，6√，7×三、1：逻辑关系2：集合、线性、树型、图状。3：没有，一个4：一个，一个，后继，任意个5：任意个6：有穷性、确定性、可行性、输入、输出7：8：9：物理10：数据、数据元素、数据项11：时间复杂度、空间复杂度，计算量、存储量12：问题规模13：1，n,,不可行四-1：次数x：1，2，3，4,…i：2，4，8，16,…T(n)=o(log(n))3.6习题一：1A,2B,3B,4B,5B,6D,7B,8D,9B,10A,11C,12C,13C,14B.二：1√，2×，3√，4×，5√，6√7×，8√，9×，10×，11√12×，13×，14×，15√三：1：前驱结点外，前驱，后继，后继结点2：线性，长度3：p->next=head4：5：n/2,该元素在线性表中的位置6：删除7：p->next=NULL;8：s->next=p->next;p->data=s->data;s->data=temp;9：n-110：b,c,e,d,a11：rear=(rear+1)%m;A[rear]=x;12：后进先出，先进先出，操作受限13：栈14：队尾P78-1要求存储的线性表长度变化不大，即不常做插入删除操作时适合选用顺序表，因易先定其大小；线性长度变化大，即常做插入删除操作时适合选用链表，因难估计其存储规模。P79-2如果长度大于等于2，则将首结点连接到表尾,第二个结点作为新的首结点，返回头指针。否则直接返回头指针。LL^P79-3顺序存储结构，因能够随机存取，存取快，O(1)。P79-6可以得到14种输出序列：abcd,abdc,acbd,acdb,adcb,bacd,bcad,bcda,bdca,cbad,cbda,cdba,dcba,badc.P79-7后缀表达式规则：建立一个栈，从左至右扫描，若遇操作数，直接输出；若遇运算符，则必须与栈顶比较，若级别比栈顶高则进栈，否则退出栈顶。A+BC**DE/_A＋B*C－D/E/_+P79-7后缀表达式规则：建立一个栈，从左至右扫描，若遇操作数，直接输出；若遇运算符，则必须与栈顶比较，若级别比栈顶高则进栈，否则退出栈顶。9_24**_89-2*4+(8+1)/31+3(++//+voidlnsert(List*L，intx，inti){//不带头结点的单链表的第i个元素之前插入一个元素

List*p=L;intj=1;while(p!=NULL&&j<i-1)//找到第i-1个元素

{p=p—>next；j++；}if(i<=0||p==NULL)printf(”插入位置不正确！＼n”)；

else{

q=(List*)malloc(sizeof(List))；

q—>data=x；

if(i==1)//在第一个元素之前插入

{q—>next=L；L=q；}else//在其它位置插入

{q—>next=p—>next；

p—>next=q；

}}}P79-五-2建立一个整数型单链表，查找其中值为4的第一个结点。如果查找成功，则输出这个结点的编号；否则输出不存在的提示。补充voidfind(head,4)node*head;elemtype4;{ node*p; p=head; while(p!=NULL&&p->data!=4) p=p->next; if(p!=NULL) printf(“结点找到了！”); else printf(“结点没找到！”);}形参还是实参？声明4的类型/4是变量名？ voidfind(head,x) node*head; intx; {……}voidfind(node*head){ node*p;intk=1; p=head; while(p!=NULL&&p->data!=4) {p=p->next;k++;} if(p!=NULL) printf(“结点找到了！编号为%d”,k); else printf(“结点没找到！”);}在带头结点的链表中找，头编号为1第五层有5个叶子结点的完全二叉树，最多有多少个结点？可能有哪些情况？补充123114589126710性质1：在二叉树的第i层上至多有2i-1个结点(i>=1)。性质2：深度为k的二叉树至多有2k

–1

个结点(k>=1)。①(24-1)+5=20②(25-1)+((25