第一章概论
1.数据：信息的载体,能被计算机识别、存储和加工处理。
2.数据元素：数据的基本单位，可由若干个数据项组成，数据项是具有独立含义的最小标识单位。
3.数据结构：数据之间的相互关系，即数据的组织形式。
它包括：1）数据的逻辑结构，从逻辑关系上描述数据，与数据存储无关，独立于计算机；
2）数据的存储结构，是逻辑结构用计算机语言的实现，依赖于计算机语言。
3）数据的运算，定义在逻辑结构上，每种逻辑结构都有一个运算集合。常用的运算：检索/插入/删除/更新/排序。
4.数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据的存储结构是逻辑结构用计算机语言的实现。
5.数据类型：一个值的集合及在值上定义的一组操作的总称。分为：原子类型和结构类型。
6.抽象数据类型：抽象数据的组织和与之相关的操作。优点：将数据和操作封装在一起实现了信息隐藏。
7. 抽象数据类型ADT：是在概念层上描述问题；类：是在实现层上描述问题；在应用层上操作对象（类的实例）解决问题。
8.数据的逻辑结构，简称为数据结构，有：
（1）线性结构，若结构是非空集则仅有一个开始和终端结点，并且所有结点最多只有一个直接前趋和后继。
（2）非线性结构，一个结点可能有多个直接前趋和后继。
9.数据的存储结构有：
1）顺序存储，把逻辑相邻的结点存储在物理上相邻的存储单元内。
2）链接存储，结点间的逻辑关系由附加指针字段表示。
3）索引存储，存储结点信息的同时，建立附加索引表，有稠密索引和稀疏索引。
4）散列存储，按结点的关键字直接计算出存储地址。
10.评价算法的好坏是：算法是正确的；执行算法所耗的时间；执行算法的存储空间（辅助存储空间）；易于理解、编码、调试。
11.算法的时间复杂度T(n)：是该算法的时间耗费，是求解问题规模n的函数。记为O(n)。
时间复杂度按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、……k次方阶O(n^k)、指数阶O(2^n)。
13.算法的空间复杂度S(n)：是该算法的空间耗费，是求解问题规模n的函数。
12.算法衡量：是用时间复杂度和空间复杂度来衡量的，它们合称算法的复杂度。
13. 算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。
第二章线性表
1.线性表：是由n(n≥0)个数据元素组成的有限序列。
2.线性表的基本运算有：
1）InitList(L),构造空表，即表的初始化；
2）ListLength(L),求表的结点个数，即表长；
3）GetNode(L,i),取表中第i个结点，要求1≤i≤ListLength(L)；
4）LocateNode(L,x)查找L中值为x的结点并返回结点在L中的位置，有多个x则返回首个，没有则返回特殊值表示查找失败。
5）InsertList(L,x,i)在表的第i个位置插入值为x的新结点，要求1≤i≤ListLength(L)+1；6）DeleteList(L,i)删除表的第i个位置的结点，要求1≤i≤ListLength(L)；
3.顺序表：把线性表的结点按逻辑次序存放在一组地址连续的存储单元里。
4.顺序表结点的存储地址计算公式：Loc(ai)=Loc(a1)+(i-1)*C；1≤i≤n
5.顺序表上的基本运算
（1）插入
void insertlist(seqlist *L,datatype x,int i)
{
int j;
if(i<1||i>L->length+1)
error(“position error”);
if(L->length>=listsize)
error(“overflow”);
for(j=L->length-1;j>=i-1;j--)
L->data[j+1]=L->data[j]; 结点后移
L->data[i-1]=x;
L->length++;
}
在顺序表上插入要移动表的n/2结点，算法的平均时间复杂度为O(n)。
（2）删除
void delete (seqlist *L,int i)
{
int j;
if(i<1||i>L->length)
error(“position error”);
for(j=i;j<=L->length-1;j++)
L->data[j-1]=L->data[j]; 结点前移
L->length--;
}
在顺序表上删除要移动表的（n+1）/2结点，算法的平均时间复杂度为O(n)。
6.单链表：只有一个链域的链表称单链表。
在结点中存储结点值和结点的后继结点的地址，data next data是数据域，next是指针域。
（1）建立单链表。时间复杂度为O(n)。
加头结点的优点：1）链表第一个位置的操作无需特殊处理；2）将空表和非空表的处理统一。（2）查找运算。时间复杂度为O(n)。
1）按序号查找。
Listnode * getnode(linklist head,int i)
{
int j;
listnode *p;
p=head;j=0;
while(p->next&&j p=p->next; 指针下移 j++; } if(i==j) return p; else return NULL; } 2）按值查找。 Listnode * locatenode(linklist head ,datatype key) { listnode *p=head->next; while(p&&p->data!=key) p=p->next; return p; } （3）插入运算。时间复杂度为O(n)。 Void insertlist(linklist head ,datatype x, int i) { listnode *p; p=getnode(head,i-1); if(p==NULL); error(“position error”); s=(listnode *)m alloc(sizeof(listnode)); s->data=x; s->next=p->next; p->next=s; } （4）删除运算。时间复杂度为O(n)。 Void deletelist(linklist head ,int i) { listnode *p ,*r; p=getnode(head ,i-1); if(p==NULL||p->next==NULL) error(“position error”); r=p->next; p->next=r->next; free(r); } 7.循环链表：是一种首尾相连的链表。特点是无需增加存储量，仅对表的链接方式修改使表的处理灵活方便。 8.空循环链表仅由一个自成循环的头结点表示。 9.很多时候表的操作是在表的首尾位置上进行，此时头指针表示的单循环链表就显的不够方便，改用尾指针rear来表示单循环链表。用头指针表示的单循环链表查找开始结点的时间是O(1),查找尾结点的时间是O(n)；用尾指针表示的单循环链表查找开始结点和尾结点的时间都是O (1)。 10.在结点中增加一个指针域，prior|data|next。形成的链表中有两条不同方向的链称为双链表。 1) 双链表的前插操作。时间复杂度为O(1)。 Void dinsertbefore(dlistnode *p ,datatype x) { dlistnode *s=malloc(sizeof(dlistnode)); s->data=x; s->prior=p->prior; s->next=p; p->prior->next=s; p->prior=s; } 2) 双链表的删除操作。时间复杂度为O(1)。 Void ddeletenode(dlistnode *p) { p->prior->next=p->next; p->next->prior=p->prior; free(p); } 11.顺序表和链表的比较 1）基于空间的考虑：顺序表的存储空间是静态分配的，链表的存储空间是动态分配的。顺序表的存储密度比链表大。因此，在线性表长度变化不大，易于事先确定时，宜采用顺序表作为存储结构。 2）基于时间的考虑：顺序表是随机存取结构，若线性表的操作主要是查找，很少有插入、删除操作时，宜用顺序表结构。对频繁进行插入、删除操作的线性表宜采用链表。若操作主要发生在表的首尾时采用尾指针表示的单循环链表。 12.存储密度=（结点数据本身所占的存储量）/（整个结点结构所占的存储总量） 存储密度：顺序表=1，链表<1。 第三章栈和队列 1.栈是限制仅在表的一端进行插入和删除运算的线性表又称为后进先出表（LIFO表）。插入、删除端称为栈顶，另一端称栈底。表中无元素称空栈。 2.栈的基本运算有： 1）initstack(s),构造一个空栈； 2）stackempty(s),判栈空； 3）stackfull(s),判栈满； 4）push(s,x),进栈； 5）pop (s),退栈； 6）stacktop(s)，取栈顶元素。 3.顺序栈：栈的顺序存储结构称顺序栈。 4.当栈满时，做进栈运算必定产生空间溢出，称“上溢”。当栈空时，做退栈运算必定产生空间溢出，称“下溢”。上溢是一种错误应设法避免，下溢常用作程序控制转移的条件。 5.在顺序栈上的基本运算： 1）置空栈。 Void initstack(seqstack *s) { s->top=-1; } 2)判栈空。 int stackem pty(seqstack *s) { return s->top==-1; } 3)判栈满。 int stackfull(seqstack *s) { return s->top==stacksize-1; } 4)进栈。 Void push(seqstack *s,datatype x) { if(stackfull(s)) error(“stack overflow”); s->data[++s->top]=x; } 5)退栈。 Datatype pop(seqstack *s) { if(stackem pty(s)) error(“stack underflow”); return S->data[s->top--]; } 6)取栈顶元素。 Dtatatype stacktop(seqstack *s) { if(stackem pty(s)) error(“stack underflow”); return S->data[s->top]; } 6.链栈：栈的链式存储结构称链栈。栈顶指针是链表的头指针。 7.链栈上的基本运算： 1）建栈。 Void initstack(linkstack *s) { s->top=NULL; } 2)判栈空。 Int stackem pty (linkstack *s) { return s->top==NULL; } 3) 进栈。 Void push(linkstack *s,datatype x) { stacknode *p=(stacknode *)m alloc(sizeof(stacknode)); p->data=x; p->next=s->top; s->top=p; } 4) 退栈。 Datatype pop(linksatck *s) { datatype x; stacknode *p=s->top; if(stackem pty(s)) error(“stack underflow”); x=p->data; s->top=p->next; free(p); return x; } 5) 取栈顶元素。 Datatype stacktop(linkstack *s) { if(stackem pty(s)) error(“stack is em pty”); return s->top->data; } 8.队列是一种运算受限的线性表，允许删除的一端称队首，允许插入的一端称队尾。队列又称为先进先出线性表，FIFO表。 9.队列的基本运算： 1）initqueue(q),置空队； 2）queueempty(q),判队空； 3）queuefull(q),判队满； 4）enqueue(q,x),入队； 5）dequeue(q),出队； 6）queuefront(q),返回队头元素。 10.顺序队列：队列的顺序存储结构称顺序队列。设置front和rear指针表示队头和队尾元素在向量空间的位置。 11.顺序队列中存在“假上溢”现象，由于入队和出队操作使头尾指针只增不减导致被删元素的空间无法利用，队尾指针超过向量空间的上界而不能入队。 12.为克服“假上溢”现象，将向量空间想象为首尾相连的循环向量，存储在其中的队列称循环队列。i=(i+1)%queuesize 13.循环队列的边界条件处理：由于无法用front==rear来判断队列的“空”和“满”。 解决的方法有： 1）另设一个布尔变量以区别队列的空和满； 2）少用一个元素，在入队前测试rear在循环意义下加1是否等于front； 3）使用一个记数器记录元素总数。 14.循环队列的基本运算： 1) 置队空。 Void initqueue(cirqueue *q) { q->front=q->rear=0; q->count=0; } 2) 判队空。 Int queueempty(cirqueue *q) { return q->count==0; } 3) 判队满。 Int queuefull(cirqueue *q) { return q->count==queuesize; } 4) 入队。 Void enqueue(cirqueue *q ,datatype x) { if(queuefull(q)) error(“queue overfolw”); q->count++; q->data[q->rear]=x; q->rear=(q->rear+1)%queuesize; } 5) 出队。 Datatype dequeue(cirqueue *q) { datatype tem p; if(queueempty(q)) error(“queue underflow”); tem p=q->data[q->front]; q->count--; q->front=(q->front+1)%queuesize; return tem p; } 6) 取队头元素。 Datatype queuefront(cirqueue *q) { if(queueempty(q)) error(“queue is empty”); return q->data[q->front]; } 15.链队列：队列的链式存储结构称链队列，链队列由一个头指针和一个尾指针唯一确定。 16.链队列的基本运算： 1) 建空队。 Void initqueue(linkqueue *q) { q->front=q->rear=NULL; } 2) 判队空。 Int queueempty(linkqueue *q) { return q->front==NULL&&q->rear==NULL; } 3) 入队。 Void enqueue(linkqueue *q,datatype x) { queuenode *p=(queuenode *)m alloc(sizeof(queuenode)); p->data=x; p->next=NULL; if(queueempty(q)) q-front=q->rear=p; else{ q->rear->next=p; q->rear=p; } } 4) 出队。 Datatype dequeue(linkqueue *q) { datatype x; queuenode *p; if(queueempty(q)) error(“queue is underflow”); p=q->front; x=p->data; q->front=p->next; if(q->rear==p) q->rear=NULL; free(p); return x; } 5) 取队头元素。 Datatype queuefront(linkqueue *q) { if(queueempty(q)) error(“queue is empty”); return q->front->data; } 第四章串 1.串：是由零个或多个字符组成的有限序列；包含字符的个数称串的长度； 2.空串：长度为零的串称空串；空白串：由一个或多个空格组成的串称空白串； 子串：串中任意个连续字符组成的子序列称该串的子串；主串：包含子串的串称主串；子串的首字符在主串中首次出现的位置定义为子串在主串中的位置； 3.空串是任意串的子串；任意串是自身的子串； 串常量在程序中只能引用但不能改变其值；串变量取值可以改变； 4.串的基本运算 1）int strlen(char *s);求串长。 2）char *strcpy(char * to,char * from);串复制。 3）char *strcat(char * to,char * from);串联接。 4）int strcmp(char *s1,char *s2);串比较。 5）char *strchr(char *s,char c);字符定位。 5.串的存储结构： （1）串的顺序存储：串的顺序存储结构称顺序串。按存储分配不同分为： 1）静态存储分配的顺序串： 直接用定长的字符数组定义，以“\0”表示串值终结。 #define maxstrsize 256 typedef char seqstring[maxstrsize]; seqstring s; 不设终结符，用串长表示。 Typedef struct{ Char ch[m axstrsize]; Int length; }seqstring; 以上方式的缺点是：串值空间大小是静态的，难以适应插入、链接等操作。 2）动态存储分配的顺序串： 简单定义：typedef char * string; 复杂定义：typedef struct{ char *ch; int length; }hstring; （2）串的链式存储：串的链式存储结构称链串。链串由头指针唯一确定。类型定义：typedef struct node{ char data; struct node *next; }linkstrnode; typedef linkstrnode *linkstring; linkstring s; 将结点数据域存放的字符个数定义为结点的大小。结点大小不为1的链串类型定义： #define nodesize 80 typedef struct node{ char data[nodesize]; struct node * next; }linkstrnode; 6.串运算的实现 （1）顺序串上的子串定位运算。 1）子串定位运算又称串的模式匹配或串匹配。主串称目标串；子串称模式串。 2）朴素的串匹配算法。时间复杂度为O(n^2)。比较的字符总次数为（n-m+1）m。 Int naivestrmatch(seqstring t,seqstring p) { int i,j,k; int m=p.length; int n=t.length; for(i=0;i<=n-m;i++){ j=0;k=i; while(j j++;k++; } if (j==m) return i; } return –1; } （2）链串上的子串定位运算。时间复杂度为O(n^2)。比较的字符总次数为（n-m+1）m。Linkstrnode * lilnkstrmatch(linkstring T, linkstring P) { linkstrnode *shift, *t, *p; shift=T; t=shift;p=P; while(t&&p){ if(t->data==p->data){ t=t->next; p=p->next; } else{ shift=shift->next; t=shift; p=P; } } if(p==NULL) return shift; else return NULL; } 第五章多维数组和广义表 1.多维数组：一般用顺序存储的方式表示数组。 2.常用方式有：1）行优先顺序，将数组元素按行向量排列； 2）列优先顺序，将数组元素按列向量排列。 3.计算地址的函数：LOC(Aij)=LOC(Ac1c2)+((i-c1)*(d2-c2+1)+j-c2)*d 4.矩阵的压缩存储：为多个非零元素分配一个存储空间；对零元素不分配存储空间。 （1）对称矩阵：在一个n阶的方阵A中，元素满足Aij=Aji 0<=i,j<=n-1;称为对称矩阵。元素的总数为：n(n+1)/2; 设：I=i或j中大的一个数；J=i或j中小的一个数； 则：k=I*(I+1)/2+J; 地址计算：LOC(Aij)=LOC(sa[k])=LOC(sa[0])+k*d= LOC(sa[0])+(I*(I+1)/2+J )* d （2）三角矩阵：以主对角线划分，三角矩阵有上三角和下三角；上三角的主对角线下元素均为常数c；下三角的主对角线上元素均为常数c。 元素总数为：(n(n+1)/2)+1; 以行优先顺序存放的Aij与SA[k]的关系： 上三角阵：k=i*(2n-i+1)/2+j-i; 下三角阵：k=i*(i+1)/2+j; （3）对角矩阵：所有的非零元素集中在以主对角线为中心的带状区域，相邻两侧元素均为零。|i-j|>(k-1)/2 以行优先顺序存放的Aij与SA[k]的关系：k=2i+j; 5.稀疏矩阵：当矩阵A中有非零元素S个，且S远小于元素总数时，称为稀疏矩阵。 对其压缩的方法有顺序存储和链式存储。 （1）三元组表：将表示稀疏矩阵的非零元素的三元组（行号、列号、值）按行或列优先的顺序排列得到的一个结点均是三元组的线性表，将该表的线性存储结构称为三元组表。其类型定义：#define maxsize 10000 typedef int datatype; typedef struct{ int i,j; datatype v; }trituplenode; typedef struct{ trituplenode data[m axsize]; int m,n,t; }tritupletable; （2）带行表的三元组表：在按行优先存储的三元组表中加入一个行表记录每行的非零元素在三元组表中的起始位置。类型定义： #define maxrow 100 typedef struct{ tritulpenode data[m axsize]; int rowtab[m axrow]; int m, n, t; }rtritulpetable; 6.广义表：是线性表的推广，广义表是n个元素的有限序列，元素可以是原子或一个广义表，记为LS。 7.若元素是广义表称它为LS的子表。若广义表非空，则第一个元素称表头，其余元素称表尾。 8.表的深度是指表展开后所含括号的层数。 9.把与树对应的广义表称为纯表，它限制了表中成分的共享和递归； 10.允许结点共享的表称为再入表； 11.允许递归的表称为递归表； 12.相互关系：线性表∈纯表∈再入表∈递归表； 13.广义表的特殊运算：1）取表头head(LS)；2）取表尾tail(LS); 第六章树 1.树：是n个结点的有限集T，T为空时称空树，否则满足： 1）有且仅有一个特定的称为根的结点； 2）其余结点可分为m个互不相交的子集，每个子集本身是一棵树，并称为根的子树。 2.树的表示方法：1）树形表示法；2）嵌套集合表示法；3）凹入表表示法；4）广义表表示法； 3.一个结点拥有的子树数称为该结点的度；一棵树的度是指树中结点最大的度数。 4.度为零的结点称叶子或终端结点；度不为零的结点称分支结点或非终端结点 5.根结点称开始结点，根结点外的分支结点称内部结点； 6.树中某结点的子树根称该结点的孩子；该结点称为孩子的双亲； 7.树中存在一个结点序列K1，K2，…Kn，使Ki为Ki+1的双亲，则称该结点序列为K1到Kn 的路径或道路； 8.树中结点K到Ks间存在一条路径，则称K是Ks的祖先，Ks是K的子孙； 9.结点的层数从根算起，若根的层数为1，则其余结点层数是其双亲结点层数加1；双亲在同一层的结点互为堂兄弟；树中结点最大层数称为树的高度或深度； 10.树中每个结点的各个子树从左到右有次序的称有序树，否则称无序树； 11.森林是m棵互不相交的树的集合。 12.二叉树：是n个结点的有限集，它或为空集，或由一个根结点及两棵互不相交的、分别称为该根的左子树和右子树的二叉树组成。 13.二叉树不是树的特殊情况，这是两种不同的数据结构；它与无序树和度为2的有序树不同。 14.二叉树的性质： 1）二叉树第i层上的结点数最多为2^(i-1)； 2）深度为k的二叉树至多有2^k-1个结点； 3）在任意二叉树中，叶子数为n0，度为2的结点数为n2，则n0=n2+1； 15.满二叉树是一棵深度为k的且有2^k-1个结点的二叉树； 16.完全二叉树是至多在最下两层上结点的度数可以小于2，并且最下层的结点集中在该层最左的位置的二叉树； 17.具有N个结点的完全二叉树的深度为log2N取整加1； 18.二叉树的存储结构 （1）顺序存储结构：把一棵有n个结点的完全二叉树，从树根起自上而下、从左到右对所有结点编号，然后依次存储在一个向量b[0~n]中，b[1~n]存放结点，b[0]存放结点总数。 各个结点编号间的关系： 1）i=1是根结点；i>1则双亲结点是i/2取整； 2）左孩子是2i, 右孩子是2i+1；（要小于n） 3）i>（n/2取整）的结点是叶子； 4）奇数没有右兄弟，左兄弟是i-1； 5）偶数没有左兄弟，右兄弟是i+1； （2）链式存储结构 结点的结构为：lchild|data|rchild ；相应的类型说明： typedef char data; typedef struct node{ datatype data; structnode *lchild , *rchild; }bintnode; typedef bintnode * bintree; 19.在二叉树中所有类型为bintnode的结点和一个指向开始结点的bintree类型的头指针构成二叉树的链式存储结构称二叉链表。 20.二叉链表由根指针唯一确定。在n个结点的二叉链表中有2n个指针域，其中n+1个为空。 21.二叉树的遍历方式有：前序遍历、中序遍历、后序遍历。时间复杂度为O(n)。 22.线索二叉树：利用二叉链表中的n+1个空指针域存放指向某种遍历次序下的前趋和后继结点的指针，这种指针称线索。加线索的二叉链表称线索链表。相应二叉树称线索二叉树。 23.线索链表结点结构：lchild|ltag|data|rtag|rchild；ltag=0,lchild是指向左孩子的指针；l tag=1,lchild是指向前趋的线索；rtag=0,rchild是指向右孩子的指针；rtag=1,rchild是指向后继的线索； 24.查找*p在指定次序下的前趋和后继结点。算法的时间复杂度为O(h)。线索对查找前序前趋和后序后继帮助不大。 25.遍历线索二叉树。时间复杂度为O(n)。 26.树、森林与二叉树的转换 （1）树、森林与二叉树的转换 1）树与二叉树的转换：1}所有兄弟间连线；2}保留与长子的连线，去除其它连线。该二叉树的根结点的右子树必为空。 2）森林与二叉树的转换：1}将所有树转换成二叉树；2}将所有树根连线。 （2）二叉树与树、森林的转换。是以上的逆过程。 27.树的存储结构 （1）双亲链表表示法：为每个结点设置一个parent指针，就可唯一表示任何一棵树。Data| parent （2）孩子链表表示法：为每个结点设置一个firstchild指针，指向孩子链表头指针，链表中存放孩子结点序号。Data|firstchild。 （3双亲孩子链表表示法：将以上方法结合。Data|parent|firstchild 数据结构（C语言版）（第2版） 课后习题答案 李冬梅 2015.3 目录 第1章绪论 (1) 第2章线性表 (5) 第3章栈和队列 (13) 第4章串、数组和广义表 (26) 第5章树和二叉树 (33) 第6章图 (43) 第7章查找 (54) 第8章排序 (65) 第1章绪论 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。 答案： 数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。 数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。 数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。 数据对象：是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。 逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 存储结构：数据对象在计算机中的存储表示，也称为物理结构。 抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。 2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 答案： 例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。 这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录，则称为顺序存储结构；如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。 即相同的逻辑结构，可以对应不同的存储结构。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 人生难得几回搏，此时不搏更待何时？ 第1章绪论 1.1 简述下列术语：数据 数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型 解：数据是对客观事物的符号表示 在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称 数据元素是数据的基本单位 在计算机程序常作为一个整体进行考虑和处理 数据对象是性质相同的数据元素的集合 是数据的一个子集 数据结构是相互之间存在一种或多种特定关系的数据元素的集合 存储结构是数据结构在计算机中的表示 数据类型是一个值的集合和定义在这个值集上的一组操作的总称 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作 是对一般数据类型的扩展 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别 解：抽象数据类型包含一般数据类型的概念 但含义比一般数据类型更广、更抽象 一般数据类型由具体语言系统部定义 直接提供给编程者定义用户数据 因此称它们为预定义数据类型 抽象数据类型通常由编程者定义 包括定义它所使用的数据和在这些数据上所进行的操作 在定义抽象数据类型中的数据部分和操作部分时 要求只定义到数据的逻辑结构和操作说明 不考虑数据的存储结构和操作的具体实现 这样抽象层次更高 更能为其他用户提供良好的使用接口 1.3 设有数据结构(D R) 其中 试按图论中图的画法惯例画出其逻辑结构图 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数） 解： ADT Complex{ 数据对象：D={r i|r i为实数} 数据关系：R={ 1.1解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 解： 1.4 解：ADT Complex{ 数据对象：D={r,i|r,i为实数} 数据关系：R={ 第一章概论 1.数据：信息的载体,能被计算机识别、存储和加工处理。 2.数据元素：数据的基本单位，可由若干个数据项组成，数据项是具有独立含义的最小标识单位。 3.数据结构：数据之间的相互关系，即数据的组织形式。 它包括：1）数据的逻辑结构，从逻辑关系上描述数据，与数据存储无关，独立于计算机； 2）数据的存储结构，是逻辑结构用计算机语言的实现，依赖于计算机语言。 3）数据的运算，定义在逻辑结构上，每种逻辑结构都有一个运算集合。常用的运算：检索/插入/删除/更新/排序。 4.数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据的存储结构是逻辑结构用计算机语言的实现。 5.数据类型：一个值的集合及在值上定义的一组操作的总称。分为：原子类型和结构类型。 6.抽象数据类型：抽象数据的组织和与之相关的操作。优点：将数据和操作封装在一起实现了信息隐藏。 7. 抽象数据类型ADT：是在概念层上描述问题；类：是在实现层上描述问题；在应用层上操作对象（类的实例）解决问题。 8.数据的逻辑结构，简称为数据结构，有： （1）线性结构，若结构是非空集则仅有一个开始和终端结点，并且所有结点最多只有一个直接前趋和后继。 （2）非线性结构，一个结点可能有多个直接前趋和后继。 9.数据的存储结构有： 1）顺序存储，把逻辑相邻的结点存储在物理上相邻的存储单元内。 2）链接存储，结点间的逻辑关系由附加指针字段表示。 3）索引存储，存储结点信息的同时，建立附加索引表，有稠密索引和稀疏索引。 4）散列存储，按结点的关键字直接计算出存储地址。 10.评价算法的好坏是：算法是正确的；执行算法所耗的时间；执行算法的存储空间（辅助存储空间）；易于理解、编码、调试。 第十章内部排序 10.23 void Insert_Sort1(SqList &L)//监视哨设在高下标端的插入排序算法{ k=L.length; for(i=k-1;i;--i) //从后向前逐个插入排序 if(L.r[i].key>L.r[i+1].key) { L.r[k+1].key=L.r[i].key; //监视哨 for(j=i+1;L.r[j].key>L.r[i].key;++j) L.r[j-1].key=L.r[j].key; //前移 L.r[j-1].key=L.r[k+1].key; //插入 } }//Insert_Sort1 10.24 void BiInsert_Sort(SqList &L)//二路插入排序的算法 { int d[MAXSIZE]; //辅助存储 x=L.r.key;d=x; first=1;final=1; for(i=2;i<=L.length;i++) { if(L.r[i].key>=x) //插入前部 { for(j=final;d[j]>L.r[i].key;j--) d[j+1]=d[j]; d[j+1]=L.r[i].key; final++; } else //插入后部 { for(j=first;d[j] 严蔚敏 数据结构C 语言版答案详解 第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 数据结构（C语言版）严蔚敏 第1章绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提 供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 数据结构c语言版复习公司内部档案编码：[OPPTR-OPPT28-OPPTL98-OPPNN08] 数据结构复习资料 一、填空题 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。 2. 数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的关系有限集合。 3. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。 4. 数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。 5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 6．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。 7. 在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。 8. 在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。 9．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、 索引和散列。 10. 数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。 11. 一个算法的效率可分为时间效率和空间效率。 12. 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有关。 13. 线性表中结点的集合是有限的，结点间的关系是一对一的。 14. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1 个元素。 15. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动n-i 个元素。 16. 在顺序表中访问任意一结点的时间复杂度均为 O(1)，因此，顺序表也称为 随机存取的数据结构。 17. 顺序表中逻辑上相邻的元素的物理位置必定相邻。单链表中逻辑上相邻的元素的物理位置不一定相邻。 18．在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。 19．在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。 20. 向量、栈和队列都是线性结构，可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。 21. 栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。 22. 队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 23. 不包含任何字符（长度为0）的串称为空串；由一个或多个空格（仅由空格符）组成的串称为空白串。 24. 子串的定位运算称为串的模式匹配；被匹配的主串称为目标串，子串 称为模式。 25. 假设有二维数组A 6×8 ，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为 288 B ；末尾元素A 57的第一个字节地址为 1282 ；若按行存储时，元素A 14 的第 一个字节地址为 (8+4)×6+1000=1072 ；若按列存储时，元素A 47 的第一个字节地址为 (6×7＋4)×6＋1000）＝1276 。 26．由３个结点所构成的二叉树有5种形态。 第1章绪论 1.1复习笔记 一、数据结构的定义 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。 二、基本概念和术语 数据 数据（data）是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称，它是计算机程序加工的“原料”。 2.数据元素 数据元素（data element）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 3.数据对象 数据对象（data object）是性质相同的数据元素的集合，是数据的一个子集。 4．数据结构 数据结构（data structure）是相互之间存在一种或多种特定关系的数据元素的集合。 （1）数据结构的基本结构 根据数据元素之间关系的不同特性，通常有下列四类基本结构： ① 集合。数据元素之间除了“同属于一个集合”的关系外，别无其它关系。 ② 线性结构。数据元素之间存在一个对一个的关系。 ③ 树形结构。数据元素之间存在一个对多个的关系。 ④ 图状结构或网状结构。数据元素之间存在多个对多个的关系。 如图1-1所示为上述四类基本结构的关系图。 图1-1 四类基本结构的关系图 （2）数据结构的形式定义 数据结构的形式定义为：数据结构是一个二元组Data_Structure==（D，S） 其中：D表示数据元素的有限集，S表示D上关系的有限集。 （3）数据结构在计算机中的表示 数据结构在计算机中的表示（又称映象）称为数据的物理结构，又称存储结构。它包括数据元素的表示和关系的表示。 ① 元素的表示。计算机数据元素用一个由若干位组合起来形成的一个位串表示。 ② 关系的表示。计算机中数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象。并由这两种不同的表示方法得到两种不同的存储结构：顺序存储结构和链式存储结构。 a.顺序映象的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。 b.非顺序映象的特点是借助指示元素存储地址的指针（pointer）表示数据元素之间的逻辑关系。 5.数据类型 数据类型（Data type）是一个值的集合和定义在这个值集上的一组操作的总称。按“值”的不同特性，高级程序语言中的数据类型可分为两类：一类是非结构的原子类型，值是不可分解的；另一类是结构类型，值是由若干成分按某种结构数据结构C语言版(第2版)严蔚敏人民邮电出版社课后习题答案
数据结构复习题集答案(c语言版严蔚敏)
数据结构习题集答案(C语言严版)
数据结构(c语言版)严蔚敏
严蔚敏版数据结构(c语言版)参考答案
严蔚敏数据结构题集(C语言版)完整
数据结构(C语言版)严蔚敏课后习题答案
数据结构c语言版复习
严蔚敏数据结构(C语言版)知识点总结笔记课后答案
相关主题
文本预览