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

一、名词解释

抽象数据类型、数据结构、数据结构的逻辑结构、数据结构的物理结构、算法、算法评价、时间复杂度、大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