数据结构1-4章习题答案

更新时间:2024-07-06 12:05:01 阅读量: 综合文库 文档下载

说明:文章内容仅供预览,部分内容可能不全。下载后的文档,内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的,是否完整无缺。

一、名词解释

抽象数据类型、数据结构、数据结构的逻辑结构、数据结构的物理结构、算法、算法评价、时间复杂度、大O表示法、线性表、栈、队列、广义表、稀疏矩阵 二、填空

1、抽象数据类型是由一组 数据结构 和在该组数据结构上的一组 操作 所组成。 2、在定义某种数据结构时,其数据域的数据类型可分为 简单类型 和 结构体类型 两种,为增强其通用性,应将其再定义为 通用数据 类型。

3、如果将线性数据结构关系描述为1:1,那么树型和图型数据结构应分别为 1:N 、 M:N 。

4、数据结构简单地说是指 数据 以及相互之间的 联系 。

5、算法应具备以下5个特性: 有穷性 、 正确性 、 可行性 、输入和输出。 6、在分析各种算法的时间复杂度时,一般只讨论相应的数量级,用f(n)表示,请问其中n的含义是 处理问题的样本量 。

7、对于一个以顺序实现的循环队列Q[m],队首、队尾指针分别为f和r,其盘空的条件是 f=r ,盘满的条件是 (r+1)%m=f 。

8、循环链表的主要优点是 最大限度的利用空间 。

9、链表对于数据元素的插入和删除不需要移动结点,只需改变相关结点的 指针 域的值。 10、在一个链式栈中,若栈顶指针等于NULL,则为 空栈 。

11、主程序第一次调用递归函数被称为外部调用,递归函数自己调用自己被称为内部调用,它们都需要利用栈保存调用后的 返回地址 地址。

12、某算法在求解一个10阶方程组时,运算次数是500,求解一个30阶方程组时,运算次数是4500,则该算法的时间复杂度为 O(N2) 。

三、选择题

1、对一个线性表的存取操作很少,而插入和删除操作较多时应采用 B 存储结构。

1

A.顺序存储 B.链式存储 C. 索引存储 D.散列式存储

2、对一个线性表的随机存取操作较多时,应采用 B 存储结构。 A.静态顺序存储 B. 动态顺序存储 C. 动态链接存储 D. 静态链接存储 3、对一个顺序存储结构的栈,栈满的判断条件是( D ) A.S.top= =-1 B.S.top= =0

C.S.top= =MaxSize D. S.top= =MaxSize-1

4、若循环队列有 n个顺序存储单元,front、rear分别为队首和队尾指针则判断队满的条件是(C)

A. (front+1)%n= =rear B. (front-1)%n= =rear C. (rear+1) %n= =front D. (rear-1)%n= = front 5、下列是顺序存储线性表排序的算法 void Sort(List& L) { }

问:此算法的时间复杂性为: B A. O(n) B.(n2) C. (n*i) D. (n*j)

int i,j; ElemType x; for(i=1;i

x=L.list[i]; for(j=i-1;j>=0;j--)

if(x

L.list[j+1]=L.list[j];

else

break;

L.list[j+1]=x;

四、简答题

1、简述线性表的顺序存储和链接存储实现的异同。

2

答:(参考答案)

2、举例说明顺序存储的栈在元素出栈和进栈时栈顶指针的变化。

3、说明顺序存储的队列,在解决队满与队空的判断条件时,为什么将队首指针指向第一个元素之前?这样解决后存储容量有什么变化? 4、举例说明栈与递归算法之间的关系。 答:(参考答案)

要点1:栈只能在栈顶操作;

要点2:递归算法是解决一个问题时,是通过解决与它具有相同解法的子问题而得到的; 要点3:在进行递归调用时,计算机系统自动建立栈,用于存储递归调用参数(下例中的)n和返回地址(下例中的r),进栈;

要点4:当在一定条件下结束递归调用时,系统按照栈中存储的系数和返回地址逐步返回(出栈)到最初调用处,并得到最终结果。 例:求f(n)=n! f(n)=1

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) f(n)=n*f(n-1)

n 0 1 2 3

当 n=3时 进栈

五、算法分析

以下有一组算法,请根据各算法的不同,回答不同的问题。 算法1:

//利用数组a[]排序 void sort (int a[],int n) {

3

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:

//在链表的表尾插入一个元素

void InsertRear(LNode*& HL,const ElemType& item) {

1:LNode* newptr; 2:newptr=new LNode; 3:if(newptr==NULL) {

4:cerr<<\

4

}

5:exit(1);

6:newptr->data=item; 7:newptr->next=NULL; 8:if(HL==NULL)

9:HL=newptr;

10:else{

11:LNode* p=HL; 12:while(p->next!=NULL)

13:p=p->next;

14:p->next=newptr;

}

}问题1:从算法评价的角度看,此算法中的3:—5:语句体现了算法的: 健壮性 。

问题2:此算法返回类型为: A. A. 空 B. 逻辑值 算法3:

//根据数据结构的类型的定义分析算法 typedef int ElemType; struct Stack{ };

void Push(Stack& S,const ElemType& item) {

if( ){ } S.top++;

S.stack[S.top]=item;

int k=sizeof(ElemType);

S.stack=(ElemType*)realloc(S.stack,2*S.MaxSize*k); S.MaxSize=2*S.MaxSize; int MaxSize; ElemType *stack; int top;

}问题1:根据此算法定义的数据结构的类型,此算法的功能是 向顺序栈中推入一个元素 。

问题2:if语句中的条件应修改为: B. 。 A. S.top= =S.MaxSize B. S.top= =S.MaxSize-1

六、广义表:A(a,(b,c,d),(#),((e,f),g))

要求1:画出此广义表的图形表示。

要求2:画出此广义表带表头附加结点的存储结构。 要求3:此广义表长度:4 ;此广义表深度: 3 。

5

七、已知线性表A={a1、a2、……an}采用链接存储结构,其数据域由4个值域组成,假设依次为 char code[]

char name[] int max int min

要求:

1、定义单链表结点(包括对数据域的定义); 2、从单链表的表尾删除一个结点。 (参考答案)

答1:struct goods{ char code[5];

};

char name[15]; int max; int min;

typedef goods ElemType; struct LNode { ElemType data;

};

LNode *next;

答2:ElemType Delete(LNode *HL) { }

LNode *p=HL; while(p->next!=NULL)

p=p->next; temp=p->data; delete p; return temp;

6

七、已知线性表A={a1、a2、……an}采用链接存储结构,其数据域由4个值域组成,假设依次为 char code[]

char name[] int max int min

要求:

1、定义单链表结点(包括对数据域的定义); 2、从单链表的表尾删除一个结点。 (参考答案)

答1:struct goods{ char code[5];

};

char name[15]; int max; int min;

typedef goods ElemType; struct LNode { ElemType data;

};

LNode *next;

答2:ElemType Delete(LNode *HL) { }

LNode *p=HL; while(p->next!=NULL)

p=p->next; temp=p->data; delete p; return temp;

6

本文来源:https://www.bwwdw.com/article/4t1.html

Top