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;isize;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;