数据结构实用教程习题答案(共41页).doc

《数据结构实用教程习题答案(共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

20、表。只允许在表的一端进行插入，而在表的另一端进行删除，将这种线性表称为队或队列（Queue），又叫先进先出的线性表，简称为FIFO（First In First Out）表。这三种结构有很多的相似之处，其差别主要体现在运算上，具有不同的运算特点。同线性表的运算相比，栈和队列在操做上受到限制。线性表可以在元素序列的任何位置上进行插入、删除操作，查找运算往往是线性表上使用频率最高的操作。查找、插入、删除的时间复杂度一般为O（n）。栈和队列的插入和删除运算都限制在线性表的表端完成，在栈和队列上不需要查找运算。栈和队列的插入及删除运算时间复杂度都可以为O（1）。3.3 设有编号为1，2，3，4的四辆车

21、，顺序进入一个栈式结构的站台，试写出这四辆车开出车站的所有可能的顺序。1 2 3 4 2 1 3 4 3 2 1 4 4 3 2 11 2 4 3 2 1 4 3 3 2 4 1 1 3 2 4 2 3 1 4 3 4 2 11 3 4 2 2 3 4 1 1 4 3 2 2 4 3 1 3.4 若数列1、2、3、4、5、6顺序进栈，假设P表示入栈操作，S表示出栈操作，例如：操作序列PSPSPSPSPSPS，可得到出栈序列为:。依此类推，请回答：（1）能否得到出栈序列？若能，请写出对应的操作序列。 （2）能否得到出栈序列？若能，请写出对应的操作序列。（3）对应操作序列：PPSSPPSPSPSS

22、，得到的出栈序列是什么？（4）对应操作序列：PPPPSPSSPSSS，得到的出栈序列是什么？（5）从上面的结果中你能总结出什么结论？（1）能得到。在123依次进栈后，3和2出栈，得部分输出序列32；然后4，5入栈，5出栈，得部分出栈序列325；6入栈并出栈，得部分输出序列3256；最后退栈，直到栈空。得输出序列。其操作序列为PPPSSPPSPSSS。（2）不能得到输出顺序为的序列。部分合法操作序列为ADAAAADDAD，得到部分输出序列1546后，栈中元素为23，3在栈顶，故不可能2先出栈，得不到输出序列。（3）（4）（5）借助栈由输入序列12n得到输出序列p1p2pn ,则在输出序列中不可能

23、存在这样的情形：存在着ijk使pjpkfront=sq-rear判断队满的条件是：（sq-rear+1）% MAXSIZE= = sq-front求队列长度的公式为：m =（sq-rear - sq-front+ MAXSIZE）% MAXSIZE;3.6 通常称正读和反读都相同的字符序列为“回文”，例如，“abcdeedcba”、 “abcdcba”是回文。若字符序列存储在一个单链表中，编写算法判断此字符序列是否为回文。（提示：将一半字符先依次进栈）#define maxsize 100typedef char datatype1;typedef struct datatype1 datam

24、axsize; int top; seqstack;typedef int datatype;typedef struct node datatype data; struct node *next; Linklist;Duichen(Linklist *head) int i=1;Linklist *p; seqstack *s;s=initSeqStack();p= head-next;n=0;while(p)n+; p=p-next;p=head-next;while(idata); i+; if (n%2!=0) p=p-next; while(p&p-data=pop(s) p=p-

25、next;if (p) return 0 else return 1;3.7 两个栈共享数组am空间，栈底分别设在两端，此时栈空、栈满的条件是什么？试写出两个栈公用的算法：Top(i), Push(i,x)和Pop(i)，其中i为栈的序号0或1。 #define m 100typedef char datatype;typedef struct node datatype am; int top0 , top1; seqstack; Seqstack ss,*s=&ss;int push(int i, datatype x) if (s-top1 = s-top0+1) printf(“ful

26、l”); return 0; if(i=0) s-top0+; s-as-top0=x; else s-top1-; s-as-top1=x; return 1;datatype pop(int i) if(i=0) if (s-top0= -1) printf(“empty”); return 0;s-top0-; return s-as-top0+1; else if (s-top1= m) printf(“empty”); return 0;s-top1+; return s-as-top1-1;datatype top(int i) if(i=0) if (s-top0= -1) pr

27、intf(“empty”); return 0; return s-as-top0; else if (s-top1=m) printf(“empty”); return 0; return s-as-top1;3.8 假设以数组am存放循环队列的元素，同时设变量rear 和length分别作为队尾指针和队中元素个数，试给出判别此循环队列的队满条件，并写出相应入队和出队的算法（在出队的算法中要返回队头元素）。#define m 100 int enqueue(int a, int rear, int length, int x) if(length = m) printf(“queue is

28、full”); return 0; rear=(rear+1)% m; arear=x; length +; return length; int dequeue(int a, int rear, int length, int *x) if(length =0) printf(“queueempty”); return 0; *x= a (rear- length +m)%m; length -; return length;4 多维数组及广义表4.1回答下列概念：三元组表、广义表、十字链表三元组表：稀疏矩阵中的非零元素三元组组成的线性表。广义表： 也称为列表（Lists）是n（n0）个元素

29、a1， a2， ，ai， an的有限序列，元素ai可以是原子或者是子表（子表亦是广义表）。十字链表：稀疏矩阵（即三元组表）的一种链接存储结构。稀疏矩阵中每个非零元素都用一个包含五个域的结点来表示，存储非零元素所在行的行号域i，存储非零元素所在列的列号域j，存储非零元素值的值域v，以及行指针域right和列指针域down，分别指向同一行中的下一个非零元素结点和同一列中的下一个非零元素结点。4.2二维数组在采用顺序存储时，元素的排列方式有哪两种？行优先和列优先。4.3 矩阵压缩存储的目的是什么？请写出对称阵压缩存储四种方式的地址公式。压缩存储的目的：节省矩阵的存储空间。将对称矩阵的下（上）三角存储

30、在数组长度为n（n+1）/2的数组sa中，设矩阵中的某一个元素aij在数组中的下标为k，则对称阵压缩存储四种方式下k的计算公式如下：（1）行优先顺序存储下三角（2）列优先顺序存储下三角（3）行优先顺序存储上三角（4）列优先顺序存储上三角4.4 在特殊矩阵和稀疏矩阵中，哪一种经过压缩存储后会失去随机存取的特性？稀疏矩阵。4.5 设有一个10阶的对称矩阵A，以行优先顺序存储下三角元素，其中a00为第一元素，其存储地址为1，每个元素占一个字节，则a85的地址为多少？若a11为第一元素，那么a85的地址又会是多少？若a00为第一元素，则a85的地址为：41若a11为第一元素，则a85的地址为：324.

31、6 请给出图4.10中稀疏矩阵A67的三元组顺序表和十字链表存储结构图示。矩阵A67的三元组顺序表： 01234i13346j21643v11-3765矩阵A67及十字链表表示：4.7 广义表分几类？它们之间有什么关系？ 广义表分为：线性表、纯表、再入表和递归表四种。它们之间的关系满足：递归表再入表纯表线性表。4.8 分别求出下列广义表的表头、表尾及表长、表深。A=（a） 表头：a表尾：()表长：1表深：1B=（a,b）,（c,d）表头：（a,b）表尾：（c,d）表长：2表深：2C=（a,（b,c）,d,e）表头：a表尾：(（b,c）,d,e）表长：4表深：2D=（a,b,（c,d）,（e,（

32、f,g）表头：a表尾：（b,（c,d）,（e,（f,g）表长：4表深：44.9 请画出下列广义表的图形表示。A=（a,b,c）B=（A,d）C=（x ,A , B）5 树5.1 回答下列概念：树、二叉树、满二叉树、完全二叉树、哈夫曼树树：可以用二元组或递归两种方法定义树。树的二元组定义如下：设tree=（D，S），其中D是数据元素的集合，S是D中数据元素之间关系的集合。设关系rS，相对r，满足下列条件： （1）D中有且仅有一个开始结点，该结点被称为树的根（Root）；（2）除树根结点外，D中其余的结点有且仅有一个前趋结点；（3）从根到其余结点都有路径。则称tree是相对r的树形结构。二叉树：二

33、叉树（Binary Tree）是n（n0）个结点的有限集合，满足：（1）当n=0时，为空二叉树。（2）当n0时，是由一个根结点和两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成。满二叉树：每层结点数都达到最大值的二叉树。完全二叉树：除最下面一层外其余各层的结点数都达到最大值，并且最下一层上的结点都集中在最左边的若干位置上的二叉树。哈夫曼树：又称最优二叉树，是在含有n个叶子结点，权值分别为w1，w2，wn的所有二叉树中，带权路径长度WPL最小的二叉树。5.2 对于图5.37给出的树，回答下列问题：（1）写出它的二元组表示；（2）根结点、叶结点和分支结点分别都为哪些；（3）结点F的度数和层

34、数分别为多少； （4）结点B的兄弟和孩子分别为哪些？（5）从结点B到结点N是否存在路径？若存在请写出具体路径。（6）从结点C到结点L是否存在路径？若存在请写出具体路径。图5.37（1）该树采用二元组表示如下：设tree =（D，S），rSD = A， B， C， D， E， F， G， H， I，J， K， L， M，N R = ，（2）根结点：A 分支结点：B，D，F，G，H，I，M 叶结点：C，E，L，N，J，K（3）结点F的度数为1，层数为3。（4）结点B的兄弟为：C，D；孩子为E，F，G。（5）结点B到N存在路径，路径为：BFIMN。（6）结点C到L不存在路径。5.3 画出包含三个结点

35、的树和二叉树的所有不同形态，说明树和二叉树之间的区别与联系。包含三个结点的树： 包含三个结点的二叉树： 5.4 判断下列说法是否正确：（1）二叉树是度为2的有序树。 （）（2）二叉树中至少有一个结点的度为2。 （）（3）完全二叉树一定存在度为1的结点。 （）5.5 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为多少？叶子数为8。5.6 结点数为n的二叉树，高度最大是多少？最小是多少？将其扩充成完全二叉树时最多需要附加多少个虚点？结点数为n的二叉树，高度最大是n，最小是或。将其扩充成完全二叉树时最多需要附加的虚点个数：2n-1-n。5.7 分别画出图5.3

36、8中的二叉树的顺序存储结构和二叉链表存储结构的图示。图5.38顺序存储结构的图示：0123456789101112131415272829ABCDE#F#G#H#IJ二叉链表存储结构的图示：5.8 分别写出图5.38中二叉树的前序、中序和后序遍历序列。前序遍历序列：ABDEGCFHIJ中序遍历序列：DBGEACIHJF后序遍历序列：DGEBIJHFCA5.9 找出满足下面条件的二叉树：（1）前序遍历与中序遍历结果相同（2）前序遍历和后序遍历结果相同（3）中序遍历和后序遍历结果相同（1）只有右分支的单分支树。（2）只有一个根结点的二叉树。（3）只有左分支的单分支树。5.10 以二叉链表为存储结构

37、，请写出前序遍历的非递归算法。#define MAXSIZE 100typedef char DataType;typedef struct Node/* 二叉链表存储结构 */DataType data; struct Node *lchild,*rchild;BiTree;typedef BiTree* SElemType ;/* 栈中数据元素类型，栈中保存结点指针 */typedef struct SElemType dataMAXSIZE; int top;SeqStack;/* 栈的类型定义，顺序栈 */* 栈的基本操作的实现 */SeqStack *initSeqStack()/*

38、初始化栈*/ SeqStack *s;/*首先建立栈空间，然后初始化栈顶指针*/ s=(SeqStack*)malloc(sizeof(SeqStack); s-top= -1; return s;int push (SeqStack *s, SElemType x) if (s-top=MAXSIZE-1) /*栈满不能入栈*/printf(overflow); return 0; s-top+; s-datas-top=x; return 1;void pop (SeqStack *s) /*出栈，假设栈不空*/ s-top-; int empty (SeqStack *s) if (s-top= -1) return 1; else return 0; SElemType top (SeqStack *s) /*设栈不空*/return (s-datas-top ); void PreOrderFei(BiTree *p)/* 前序遍历二叉树的非递归算法 */SeqStack *s; s=initSeqStack(); while(1) while(p) printf(%c, p-data); push(s,p); p=p-lchild;/*先访问结点，后压栈*/ if (empty(s) break; p