《数据结构实用教程习题答案》由会员分享，可在线阅读，更多相关《数据结构实用教程习题答案（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 DataType data; struct Node *next; LinkList;LinkList * Reverse(
