发布时间 : 星期日 文章1-4章习题答案更新完毕开始阅读
for (int j=1;j<=n;j++)
printf(“%d*%d=%d\\n”,i,j,i*j);
A．O(n) B. O(n2) C．O(1) B. O(n3)
四、简答题
1、简述数据的逻辑结构和物理结构的关系
答：数据结构是指数据元素之间逻辑关系的整体，是从具体问题抽象出来的数据模型，有线性结构、树型结构和图型结构三种类型。物理结构是数据及其逻辑结构在计算机中的表示，分为顺序存储和非顺序存储两种类型。
数据的逻辑结构属于用户视图，是面向问题的，反映了数据内部的构成方式；数据的存储结构属于具体实现的视图，是面向计算机的。
一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构，其数据处理的效率往往是不同的。
2、叙述顺序表和链表在存储方式、空间占用、读取操作、插入和删除操作等方面的不同； 【答案要点】
1. 两者的存储结构不同。顺序用物理相邻实现逻辑相邻，大多用数组实现，链接存储用链
接的方式实现逻辑相邻，物理上不一定相邻；
2. 存储相同数量的数据，顺序存储占用空间小，链接存储占用空间大；
3. 读取操作：顺序存储为按元素序号随机访问，效率较高；链接存储为按元素序号顺序访
问，效率较低；
4. 插入和删除操作：顺序存储要移动约半数元素，效率较低；链接存储不需移动现有元素，
效率较高；
3、举例说明顺序存储的栈在元素出栈和进栈时栈顶指针的变化。
4、说明顺序存储的队列，在解决队满与队空的判断条件时，为什么将队首指针指向第一个元素之前？这样解决后存储容量有什么变化？ 5、举例说明栈与递归算法之间的关系。 答：（参考答案）
要点1：栈只能在栈顶操作；
要点2：递归算法是解决一个问题时，是通过解决与它具有相同解法的子问题而得到的；
5
要点3：在进行递归调用时，计算机系统自动建立栈，用于存储递归调用参数（下例中的）n和返回地址（下例中的r）,进栈；
要点4：当在一定条件下结束递归调用时，系统按照栈中存储的系数和返回地址逐步返回（出栈）到最初调用处，并得到最终结果。 要点4： 例：求f(n)=n! f(n)=1
f(n)=n*f(n-1)
n 0 1 2 3
n=0
n>0
退栈 1 1*1=1 2*1=2 3*2=6 f(n) f(0)=1 1*f(1-1) 2*f(2-1) 3*f(3-1) 当 n=3时 进栈
五、基本要求： 1、写出顺序表定义 2、写出链表结点定义 3、写出堆栈定义 4、写出循环顺序队列定义 5、写出链队定义 六、算法分析
以下有一组算法，请根据各算法的不同，回答不同的问题。 算法1：
//利用数组a[]排序 void sort (int a[],int n) {
6
int i,j,k,t;
for(i=0;i j=i; } } for(k=i+1;k if(a[k]>a[j]) j=k; t=a[i]; a[i]=a[j]; a[j]=t; 问题1：此算法的时间复杂度为： O(n2) 。 问题2：此算法属于： A. 。 A. 直接选择排序 B. 直接插入排序 算法2： int FindList(struct List *L,ElemType x) { } 问题1、算法适用的数据结构 ？ 问题2、算法功能？ 问题3、算法返回？ 问题4、算法有无健壮性？若有，是哪（些）语句？ 问题5、算法的关键语句是哪（些）语句？ 问题6、算法的时间复杂度大O（）？ 算法3： //在链表的表尾插入一个元素 void InsertLastList(struct sNode** HL, ElemType x) { 7 int i; for( i=0;i if(L->list[i]==x){ } return -1; x=L->list[i]; return i; } struct sNode* newp; newp=malloc(sizeof(struct sNode)); if(newp==NULL) { } printf(\exit(1); newp->data=x; newp->next=NULL; if(*HL==NULL) *HL=newp; else{ } struct sNode* p=*HL; while(p->next!=NULL) p=p->next; p->next=newp; 问题1、算法适用的数据结构 ？ 问题2、算法功能？ 问题3、算法返回？ 问题4、算法有无健壮性？若有，是哪（些）语句？ 问题5、算法的关键语句是哪（些）语句？ 问题6、算法的时间复杂度大O（）？ 算法4： //根据数据结构的类型的定义分析算法 typedef int ElemType; struct StackSq{ 8 int MaxSize;