1 绪论1.1回答下列概念:数据结构,数据的逻辑结构,数据的存储结构,算法数据结构:按照某种逻辑关系组织起来的一批数据,用一定的存储方式存储在计算机的存储器中,并在这些数据上定义一个运算的集合,就称为一个数据结构。
数据的逻辑结构:数据元素之间的逻辑关系,是根据实际问题抽象出来的数学模型。
数据的存储结构:是指数据的逻辑结构到计算机存储器的映射。
算法:是指对数据元素进行加工和处理1.2数据结构研究的三方面内容是什么?它们之间有什么联系和区别?三方面内容: 数据的逻辑结构、数据的存储结构和数据运算的集合。
联系和区别:数据的逻辑结构是数学模型,数据的存储结构是指逻辑结构到存储区域的映射,运算是定义在逻辑结构上,实现在存储结构上。
1.3简述数据结构中讨论的三种经典结构及其逻辑特征。
三种经典结构:线性表、树和图。
线性表:有且仅有一个开始结点和一个终端结点,其余的内部结点都有且仅有一个前趋结点和一个后继结点,数据元素间存在着一对一的相互关系。
树:有且仅有一个开始结点,可有若干个终端结点,其余的内部结点都有且仅有一个前趋结点,可以有若干个后继结点,数据元素间存在着一对多的层次关系。
图:可有若干个开始结点和终端结点,其余的内部结点可以有若干个前趋结点和若干个后继结点,数据元素间存在着多对多的网状关系。
1.4实现数据存储结构的常用存储方法有哪几种?简述各种方法的基本思想。
常用存储方法有四种:顺序存储、链接存储、索引存储、散列存储。
各种方法的基本思想:顺序存储:把逻辑上相邻的数据元素存储在物理位置上相邻的存储单元里。
链接存储:通过附加指针域表示数据元素之间的关系。
索引存储:除了存储数据元素,还要建立附加索引表来标识数据元素的地址。
散列存储:根据数据元素的关键字直接计算出该结点的存储地址,称为关键字-地址转换法。
1.5算法的特性是什么?如何定性的评价一个算法的优劣?算法的特性:有穷性、确定性、可行性、输入、输出。
算法的定性评价标准有:正确性、可读性、健壮性、简单性。
1.6算法的定量评价标准是什么?算法的定量评价标准有:时间复杂度和空间复杂度。
时间复杂度:是一个算法运行时所耗费的系统时间,也就是算法的时间效率。
空间复杂度:是一个算法运行时所耗费的存储空间,也就是算法的空间效率。
1.7 写出下列程序段中带标号语句的频度,并给出执行各程序段的时间复杂度(n为整数)。
(1)i=1; (2)s=1;while(i<n)do for(i=1;i<=n;i++)【1】i++; 【1】s=s*i;(3)s=0; (4)i=1;for(i=l;i<n;i++) while(i*i<=n)for (j=n;j>=i;j--) 【1】i++;【1】s=s+i+j;(5)i=1;(6)x=1;y=100;while(i<n)do do{【1】i=i*2; 【1】x++;y--;}While(x<y);答:(1) n-1, O(n) (2)n,O(n) (3)(n+2)(n-1)/2, O(n2)(4(5)㏒(n-1)+1,O(n) (6)50,O(1)2 线性表2.1 回答下列概念:线性结构,线性表,顺序表,单链表,静态链表线性结构:设Data_Structure =(D,S),r∈S,相对r,D中有且仅有一个开始结点和一个终端结点,其余的内部结点都有且仅有一个前趋和一个后继,则称Data_Structure是相对r的线性结构。
线性表:是具有相同属性的n(n≥0)个数据元素的有限序列。
顺序表:顺序表(Sequential List)是采用顺序存储结构的线性表。
单链表:每个结点只附加一个指向后继的指针域,这样的链表称为单链表(Single Linked List)静态链表:用数组实现的链表,指针就变换为数组的下标,结点即为数组中的下标变量,由于需要预先分配一个较大的数组空间,因此这种链表称之为静态链表。
2.2 比较顺序表和链表这两种线性表不同存储结构的特点。
1.逻辑关系的表示:顺序表隐含表示关系,链表显示表示关系。
2.存储密度:顺序表的存储密度大,而链表的存储密度小。
3.存储分配方式:顺序表的存储空间是预先静态分配的一块连续存储空间,在程序执行之前必须明确规定它的存储规模。
链表不用事先估计存储规模,动态分配和释放存储空间,存储空间可连续也可不连续。
4.存取方法:顺序表可以随机存取,链表必须顺序存取。
5.插入、删除操作:在顺序表中做插入、删除时平均移动表中一半的元素;在链表中作插入、删除时,只要修改指针域,而不需要移动元素。
所以顺序表的插入、删除效率低,链表的插入、删除效率高。
6.实现语言:顺序表容易实现,任何高级语言中都有数组类型。
而链表的操作是基于指针的,对于没有提供指针类型的高级语言,必须采用静态链表。
总之,两种存储结构各有长短,选择那一种由实际问题中的主要因素决定。
通常“较稳定”的线性表选择顺序存储,而频繁做插入、删除的线性表,即动态性较强的线性表宜选择链接存储。
2.3 已知长度为n的线性表A中的元素是整数,写算法求线性表中值大于item的元素个数。
分两种情况编写函数:(1)线性表采用顺序存储;(2)线性表采用单链表存储。
(1)线性表采用顺序存储#define MAX 1024typedef int DataType;typedef struct{ DataType data[MAX];int last;} SeqList;int LocateElem (SeqList *L, DataType item){ int i,j=0;for(i=0;i<=L->last ;i++)if( L->data[i] >item ) j++;return j;}(2)线性表采用单链表存储typedef int DataType;typedef struct Node{ DataType data;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;typedef struct{ DataType data[MAX];int last;} SeqList;int LocateElem (SeqList *L, DataType item){ int i=0;While(i<=L->last)if( L->data[i] ==item ){for(j=i+1;j<=L->last;j++) L->data[j-1]=L->data[j]; L->last --; }Else i++;}(2)线性表采用单链表存储typedef int DataType;typedef struct Node{ DataType data;struct Node *next;}LinkList;int deleteDupNode(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 data[MAX];int last;} SeqList;int inserts(SeqList *L, DataType x){int i;if (L->last ==Max-1) {printf(“full”); return 0;}i= L->last;while(i>=0&& L->data[i] >x)L->data [i+1]= L->data [i--];L->data [i+1]=x; L->last ++; return 1;}2.6 设带头结点的单链表L中的数据元素是整型数且递增有序。
试写一算法,将x 插入到单链表的适当位置上,以保持表的有序性,并且分析算法的时间复杂度。
typedef int DataType;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->data<x))p=p->next;s->next=p->next; p->next=s;}2.7 试写一算法实现对不带头结点的单链表H进行就地逆置。
typedef int DataType;typedef struct Node{ DataType data;struct Node *next;}LinkList;LinkList * Reverse(LinkList *H){ L inkList *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;}LinkList;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->data< s->data )) p=p->next;s->next=p->next; p->next=s;}}2.9 设单链表X和单链表Y分别存储了两个字符串,设计算法找出X中第一个不在Y中出现的字符。