数据结构实用教程习题答案(共41页).doc
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《数据结构实用教程习题答案(共41页).doc》由会员分享,可在线阅读,更多相关《数据结构实用教程习题答案(共41页).doc(41页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、精选优质文档-倾情为你奉上1 绪论1.1 回答下列概念:数据结构,数据的逻辑结构,数据的存储结构,算法数据结构: 按照某种逻辑关系组织起来的一批数据,用一定的存储方式存储在计算机的存储器中,并在这些数据上定义一个运算的集合,就称为一个数据结构。数据的逻辑结构: 数据元素之间的逻辑关系,是根据实际问题抽象出来的数学模型。数据的存储结构: 是指数据的逻辑结构到计算机存储器的映射。算法: 是指对数据元素进行加工和处理1.2 数据结构研究的三方面内容是什么?它们之间有什么联系和区别?三方面内容: 数据的逻辑结构、数据的存储结构和数据运算的集合。联系和区别:数据的逻辑结构是数学模型,数据的存储结构是指逻
2、辑结构到存储区域的映射,运算是定义在逻辑结构上,实现在存储结构上。1.3 简述数据结构中讨论的三种经典结构及其逻辑特征。三种经典结构:线性表、树和图。线性表:有且仅有一个开始结点和一个终端结点,其余的内部结点都有且仅有一个前趋结点和一个后继结点,数据元素间存在着一对一的相互关系。树:有且仅有一个开始结点,可有若干个终端结点,其余的内部结点都有且仅有一个前趋结点,可以有若干个后继结点,数据元素间存在着一对多的层次关系。图:可有若干个开始结点和终端结点,其余的内部结点可以有若干个前趋结点和若干个后继结点,数据元素间存在着多对多的网状关系。1.4 实现数据存储结构的常用存储方法有哪几种?简述各种方法
3、的基本思想。常用存储方法有四种:顺序存储、链接存储、索引存储、散列存储。各种方法的基本思想:顺序存储:把逻辑上相邻的数据元素存储在物理位置上相邻的存储单元里。链接存储:通过附加指针域表示数据元素之间的关系。索引存储:除了存储数据元素,还要建立附加索引表来标识数据元素的地址。散列存储:根据数据元素的关键字直接计算出该结点的存储地址,称为关键字地址转换法。1.5 算法的特性是什么?如何定性的评价一个算法的优劣?算法的特性:有穷性、确定性、可行性、输入、输出。算法的定性评价标准有:正确性、可读性、健壮性、简单性。1.6 算法的定量评价标准是什么?算法的定量评价标准有:时间复杂度和空间复杂度。时间复杂
4、度:是一个算法运行时所耗费的系统时间,也就是算法的时间效率。空间复杂度:是一个算法运行时所耗费的存储空间,也就是算法的空间效率。1.7 写出下列程序段中带标号语句的频度,并给出执行各程序段的时间复杂度(n为整数)。(1)i=1; (2)s=1;while(in)do for(i=1;i=n;i+) 【1】i+; 【1】s=s*i;(3)s=0; (4)i=1;for(i=l;in;i+) while(i*i=i;j-) 【1】i+; 【1】s=s+i+j; (5)i=1; (6)x=1;y=100;while(in)do do 【1】i=i*2; 【1】x+;y-; While(xy); 答:
5、(1) n-1, O(n) (2)n,O(n) (3)(n+2)(n-1)/2, O(n2) (4) , O( ) (5)(n-1)+1,O(n) (6)50,O(1)2 线性表2.1 回答下列概念:线性结构,线性表,顺序表,单链表,静态链表 线性结构:设Data_Structure =(D,S),rS,相对r,D中有且仅有一个开始结点和一个终端结点,其余的内部结点都有且仅有一个前趋和一个后继,则称Data_Structure是相对r的线性结构。线性表:是具有相同属性的n(n0)个数据元素的有限序列。顺序表:顺序表(Sequential List)是采用顺序存储结构的线性表。单链表:每个结点只
6、附加一个指向后继的指针域,这样的链表称为单链表(Single Linked List)静态链表:用数组实现的链表,指针就变换为数组的下标,结点即为数组中的下标变量,由于需要预先分配一个较大的数组空间,因此这种链表称之为静态链表。2.2 比较顺序表和链表这两种线性表不同存储结构的特点。逻辑关系的表示:顺序表隐含表示关系,链表显示表示关系。2存储密度:顺序表的存储密度大,而链表的存储密度小。3存储分配方式:顺序表的存储空间是预先静态分配的一块连续存储空间,在程序执行之前必须明确规定它的存储规模。链表不用事先估计存储规模,动态分配和释放存储空间,存储空间可连续也可不连续。4存取方法:顺序表可以随机存
7、取,链表必须顺序存取。5插入、删除操作:在顺序表中做插入、删除时平均移动表中一半的元素;在链表中作插入、删除时,只要修改指针域,而不需要移动元素。所以顺序表的插入、删除效率低,链表的插入、删除效率高。6实现语言:顺序表容易实现,任何高级语言中都有数组类型。而链表的操作是基于指针的,对于没有提供指针类型的高级语言,必须采用静态链表。总之,两种存储结构各有长短,选择那一种由实际问题中的主要因素决定。通常“较稳定”的线性表选择顺序存储,而频繁做插入、删除的线性表,即动态性较强的线性表宜选择链接存储。2.3 已知长度为n的线性表A中的元素是整数,写算法求线性表中值大于item的元素个数。分两种情况编写
8、函数:(1)线性表采用顺序存储;(2)线性表采用单链表存储。(1)线性表采用顺序存储#define MAX 1024typedef int DataType;typedef struct DataType dataMAX;int last; SeqList;int LocateElem (SeqList *L, DataType item)int i,j=0; for(i=0;ilast ;i+) if( L-datai item ) j+; return j;(2)线性表采用单链表存储typedef int DataType;typedef struct Node DataType data
9、; struct Node *next; LinkList;LinkList *locateElem(LinkList *L, DataType item ) LinkList *p=L-next; int i=0; while ( p ) if( p-data item) i+; p=p-next; return i ;2.4 已知长度为n的线性表A中的元素是整数,写算法删除线性表中所有值为item的数据元素。分两种情况编写函数:(1)线性表采用顺序存储;(2)线性表采用单链表存储。(1)线性表采用顺序存储#define MAX 1024typedef int DataType;typede
10、f struct DataType dataMAX;int last; SeqList; int LocateElem (SeqList *L, DataType item)int i=0; While(ilast) if( L-datai =item ) for(j=i+1;jlast;j+) L-dataj-1=L-dataj; L-last -; Else i+; (2)线性表采用单链表存储typedef int DataType;typedef struct Node DataType data; struct Node *next; LinkList;int deleteDupNod
11、e(LinkList *L, DataType item) LinkList *p,*q,*r; q= L; p=L-next; while (p) if (p-data=item) q-next=p-next; free(p); p=q-next;else q=p; p=p-next; 2.5 设长度为Max的顺序表L中包含n个整数且递增有序。试写一算法,将x 插入到顺序表的适当位置上,以保持表的有序性,并且分析算法的时间复杂度。#define MAX 1024typedef int DataType;typedef struct DataType dataMAX;int last; Seq
12、List;int inserts(SeqList *L, DataType x) int i; if (L-last =Max-1) printf(“full”); return 0; i= L-last;while(i=0& L-datai x) L-data i+1= L-data i-;/“相当于L-data i+1= L-data i;i-;”L-data i+1=x; L-last +; return 1;2.6 设带头结点的单链表L中的数据元素是整型数且递增有序。试写一算法,将x 插入到单链表的适当位置上,以保持表的有序性,并且分析算法的时间复杂度。typedef int Data
13、Type;typedef struct Node DataType data; struct Node *next; LinkList;void InsertList(LinkList *L,datetype x)LinkList *p,*s;s=(LinkList *)malloc(sizeof(Linklist);s-data=x;p=L;while(p-next)&(p-next-datanext;s-next=p-next; p-next=s;2.7 试写一算法实现对不带头结点的单链表H进行就地逆置。 typedef int DataType;typedef struct Node D
14、ataType data; struct Node *next; LinkList;LinkList * Reverse(LinkList *H)LinkList *p,*q;if (!H) return;p=H-next; q=H-next; H-next=NULL;While(q)q=q-next; p-next= H; H =p; p=q; return H;2.8 若带头结点的单链表L中的数据元素是整型数,编写算法对单链表L进行排序。typedef int DataType;typedef struct Node DataType data; struct Node *next; Li
15、nkList;void InsertList(LinkList *L)LinkList *p,*q,*s;if (!L-next |!L-next-next) return;q= L-next-next; L-next-next= NULL;while(q)s=q; q=q-next;p=L;while(p-next)&(p-next-datadata ) p=p-next;s-next=p-next; p-next=s; 2.9 设单链表X和单链表Y分别存储了两个字符串,设计算法找出X中第一个不在Y中出现的字符。typedef char DataType;typedef struct Nod
16、e DataType data; struct Node *next; LinkList;linklist *search(linklist *x, linklist *y) linklist *p,*q; p=x; q=y; while(p&q) if(p-data!=q-data) q=q-next;else p=p-next; q=y; return p; 2.10 已知递增有序的两个单链表A和B各存储了一个集合。设计算法实现求两个集合的交集运算C=AB。typedef int DataType;typedef struct Node DataType data; struct Node
17、 *next; LinkList;LinkList *union(LinkList *A,LinkList *B) LinkList *C, *p,*q,*s*r; p=A-next;q=B-next; C=A; r=C; while (p&q) if (p-data=q-data) r-next=p; r=p; p=p-next;q=q-next;else if (p-datadata) p=p-next; else q=q-next; r-next= NULL ; free(B); return C;2.11 已知递增有序的两个单链表A和B,编写算法将A、B归并成一个递增有序的单链表C。t
18、ypedef int DataType;typedef struct Node DataType data; struct Node *next; LinkList;LinkList *union(LinkList *A,LinkList *B) LinkList *C, *p,*q,*s*r; p=A-next;q=B-next; C=A; r=C; while (p&q) if (p-datadata) s=p; p=p-next; else s=q; q=q-next; r-next=s;r=s; if (!q) r-next=q;else r-next=p; free(B); retu
19、rn C;3 栈和队列3.1 回答下列概念:栈,队列,顺序栈,链队列栈:栈(Stack)是运算受限的线性表,限制它的插入和删除操作仅在表的一端进行。队列:只允许在表的一端进行插入,而在表的另一端进行删除,将这种线性表称为队或队列(Queue)。顺序栈:采用顺序方式存储的栈称为顺序栈(Sequential Stack)。链队列:采用链接方法存储的队列称为链队列(Linked Queue)。3.2 栈和队列各有什么特点?简述栈、队列和线性表的差别。栈(Stack)是运算受限的线性表,限制它的插入和删除操作仅在表的一端进行,又称为后进先出的线性表(Last In First Out),简称 LIFO
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实用教程 习题 答案 41
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内