《数据结构(第3版)习题答案.doc》由会员分享，可在线阅读，更多相关《数据结构(第3版)习题答案.doc（109页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、如有侵权，请联系网站删除，仅供学习与交流数据结构(第3版)习题答案【精品文档】第 109 页十二五普通高等教育国家级本科规划教材第 1 章绪论高等学校精品资源共享课程1.1 什么是数据结构？【答】：数据结构是指按一定的逻辑结构组成的一批数据，使用某种存储结构将这批数据存储于计算机中，并在这些数据上定义了一个运算集合。1.2 数据结构涉及哪几个方面？【答】：数据结构涉及三个方面的内容，即数据的逻辑结构、数据的存储结构和数据的运算集合。1.3 两个数据结构的逻辑结构和存储结构都相同，但是它们的运算集合中有一个运算的定义不一样，它们是否可以认作是同一个数据结构？为什么？【答】：不能，运算集合是数据结
2、构的重要组成部分，不同的运算集合所确定的数据结构是不一样的，例如，栈与队列它们的逻辑结构与存储结构可以相同，但由于它们的运算集合不一样，所以它们是两种不同的数据结构。1.4 线性结构的特点是什么？非线性结构的特点是什么？【答】：线性结构元素之间的关系是一对一的，在线性结构中只有一个开始结点和一个终端结点，其他的每一个结点有且仅有一个前驱和一个后继结点。而非线性结构则没有这个特点，元素之间的关系可以是一对多的或多对多的。1.5 数据结构的存储方式有哪几种？【答】：数据结构的存储方式有顺序存储、链式存储、散列存储和索引存储等四种方式。1.6 算法有哪些特点？它和程序的主要区别是什么？【答】：算法具
3、有（1）有穷性（2）确定性（3）0 个或多个输入（4）1 个或多个输出（5）可行性等特征。程序是算法的一种描述方式，通过程序可以在计算机上实现算法。1.7 抽象数据类型的是什么？它有什么特点？【答】：抽象数据类型是数据类型的进一步抽象，是大家熟知的基本数据类型的延伸和发展。抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。对一个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这些函数的参数性质。一旦定义了一个抽象数据类型及具体实现，程序设计中就可以像使用基本数据类型那样，十分方便地使用抽象数据类型。抽象数据类型的设计者根据这些描述给出操
4、作的具体实现，抽象数据类型的使用者依据这些描述使用抽象数据类型。1.8 算法的时间复杂度指的是什么？如何表示？【答】：算法执行时间的度量不是采用算法执行的绝对时间来计算的，因为一个算法在不同的机器上执行所花的时间不一样，在不同时刻也会由于计算机资源占用情况的不同，使得算法在同一台计算机上执行的时间也不一样，另外，算法执行的时间还与输入数据的状态有关，所以对于算法的时间复杂性，采用算法执行过程中其基本操作的执行次数，称为计算量来度量。算法中基本操作的执行次数一般是与问题规模有关的，对于结点个数为 n 的数据处理问题，用T(n)表示算法基本操作的执行次数。为了评价算法的执行效率，通常采用大写 O
5、符号表示算法的时间复杂度，大写 O 符号给出了函数 f 的一个上限。其它义如下：3十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程定义：f (n)=O (g (n) 当且仅当存在正的常数 c 和 n0，使得对于所有的 nn0，有 f (n) c g(n)。上述定义表明，函数 f 顶多是函数 g 的 c 倍，除非 n 小于 n0。因此对于足够大的 n (如 nn0)，g 是 f 的一个上限（不考虑常数因子 c）。在为函数 f 提供一个上限函数 g 时，通常使用比较简单的函数形式。比较典型的形式是含有 n 的单个项（带一个常数系数）。表 1-1 列出了一些常用的 g 函数及其名称。对于
6、表 1-1 中的对数函数 logn，没有给出对数基，原因是对于任何大于 1 的常数 a 和 b 都有 logan =logbn/logba,所以 logan 和 logbn 都有一个相对的乘法系数 1/logba，其中 a 是一个常量。表 1-1 常用的渐进函数1.9 算法的空间复杂度指的是什么？如何表示？【答】：算法的空间复杂度是指算法在执行过程中占用的额外的辅助空间的个数。可以将它表示为问题规模的函数，并通过大写O符号表示空间复杂度。1.10 对于下面的程序段，分析带下划线的语句的执行次数，并给出它们的时间复杂度 T(n)。（1） i+ ;（2） for(i=0;in;i+)if (aix
7、) x=ai;（3）for(i=0;in;i+)for(j=0;jn;j+)printf(“%d”,i+j) ;（4）for (i=1;i=n-1;i+) k=i;for(j=i+1;jaj+1) k=j;t=ak; ak=ai; ai=t;（5）for(i=0;in;i+)for(j=0;jn;j+)+x;s=s+x;【答】：（1）O（1）；（2）O（n）；（3）O（n2）；（4）O（n2）；（5）O（n2）4十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程第 2 章线性表及其顺序存储2.1 选择题（1）表长为 n 的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时
8、，插入一个元素所需移动元素的平均个数为（为（ A ）。E），删除一个元素所需移动元素的平均个数A（n1）/2En/2BnF(n+1)/2Cn+1G(n2)/2Dn1（2）设栈 S 和队列 Q 的初始状态为空，元素 e1、e2、e3、e4、e5 和 e6 依次通过栈 S，一个元素出栈后即进入队列 Q，若 6 个元素出队的序列为 e2、e4、e3、e6、e5 和 e1，则栈 S的容量至少应该为（ C ）。A6B4C3D2（3）设栈的输入序列为 1、2、3 n，若输出序列的第一个元素为 n，则第 i 个输出的元素为（ B ）。A不确定Bni+1CiDni（4）在一个长度为 n 的顺序表中删除第 i
9、个元素（1=i=n）时，需向前移动（ A ）个元素。AniBni+1Cni1Di（5）若长度为 n 的线性表采用顺序存储结构存储，在第 i 个位置上插入一个新元素的时间复杂度为（ A ）。AO(n)BO(1)CO(n2)DO(n3)（6）表达式 a*(b+c)d 的后缀表达式是（ BAabcd*+Babc+*dCabc*+dD+*abcd（7）队列是一种特殊的线性表，其特殊性在于（ C ）。A插入和删除在表的不同位置执行 B插入和删除在表的两端位置执行C插入和删除分别在表的两端执行 D插入和删除都在表的某一端执行（8）栈是一种特殊的线性表，具有（ B ）性质。A先进先出B先进后出C后进后出D顺
10、序进出（9）顺序循环队列中（数组的大小为 n），队头指示 front 指向队列的第 1 个元素，队尾指示 rear 指向队列最后元素的后 1 个位置，则循环队列中存放了 n 1 个元素，即循环队列满的条件为（ BA(rear+1)%n=front1C(rear)%n=frontB(rear+1)%n=frontDrear+1=front（10）顺序循环队列中（数组的大小为 6），队头指示 front 和队尾指示 rear 的值分别为 3和 0，当从队列中删除 1 个元素，再插入 2 个元素后，front 和 rear 的值分别为（ D ）。A5 和 1B2 和 4C1 和 5D4 和 22.2
11、 什么是顺序表？什么是栈？什么是队列？5十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程【答】：当线性表采用顺序存储结构时，即为顺序表。栈是一种特殊的线性表，它的特殊性表现在约定了在这种线性表中数据的插入与删除操作只能在这种线性表的同一端进行（即栈顶），因此，栈具有先进后出、后进先出的特点。队列也是一种特殊的线性表，它的特殊性表现在约定了在这种线性表中数据的插入在表的一端进行，数据的删除在表的另一端进行，因此队列具有先进先出，后进后出的特点。2.3 设计一个算法，求顺序表中值为 x 的结点的个数。【答】：顺序表的存储结构定义如下（文件名 seqlist.h）：#include #d
12、efine N 100typedef int datatype;typedef struct datatype dataN;int length; seqlist;/*预定义最大的数据域空间*/*假设数据类型为整型*/*此处假设数据元素只包含一个整型的关键字域*/*线性表长度*/*预定义的顺序表类型*/算法 countx（L,x）用于求顺序表 L 中值为 x 的结点的个数。int countx(seqlist *L,datatype x)int c=0;int i;for (i=0;ilength;i+)if (L-datai=x) c+;return c;2.4 设计一个算法，将一个顺序表倒
13、置。即，如果顺序表各个结点值存储在一维数组 a 中，倒置的结果是使得数组 a 中的 a0等于原来的最后一个元素，a1 等于原来的倒数第 2 个元素，a 的最后一个元素等于原来的第一个元素。【答】：顺序表的存储结构定义同题 2.3，实现顺序表倒置的算法程序如下：void verge(seqlist *L)int t,i,j;i=0;j=L-length-1;while (idatai;L-datai+=L-dataj;L-dataj-=t;2.5 已知一个顺序表中的各结点值是从小到大有序的，设计一个算法，插入一个值为 x 的结点，使顺序表中的结点仍然是从小到大有序。【答】：顺序表的定义同题 2.
14、3，实现本题要求的算法程序如下：6十二五普通高等教育国家级本科规划教材void insertx(seqlist *L,datatype x)int j;if (L-lengthlength-1;while (j=0 & L-datajx) L-dataj+1=L-dataj;j-;L-dataj+1=x;L-length+;2.6 将下列中缀表达式转换为等价的后缀表达式。(1) 5+6*7(2) (5-6)/7(3) 5-6*7*8(4) 5*7-8(5) 5*(7-6)+8/9(6) 7*(5-6*8)-9【答】：高等学校精品资源共享课程(7) 5+6*7(8) (5-6)/7(9) 5-6
15、*7*8(10)5*7-8(11)5*(7-6)+8/9(12)7*(5-6*8)-9后缀表达式：5 6 7*+后缀表达式：5 6-7/后缀表达式：5 6 7*8*-后缀表达式：5 7* 8-后缀表达式：5 7 6-*8 9/+后缀表达式：7 5 6 8*-*9-2.7 循环队列存储在一个数组中，数组大小为 n，队首指针和队尾指针分别为 front 和 rear，请写出求循环队列中当前结点个数的表达式。【答】：循环队列中当前结点个数的计算公式是：(n+rear-front)%n2.8 编号为 1,2,3,4 的四列火车通过一个栈式的列车调度站，可能得到的调度结果有哪些？如果有 n 列火车通过调
16、度站，请设计一个算法，输出所有可能的调度结果。【答】：方法一：算法思想：逐次输出所有可能，用回溯法。即：总体：对原始序列中的每一个元素，总是先入栈，后出栈1入栈后的操作：a.该元素出栈；b.下一个元素入栈；2出栈后的操作：a.（栈中其他元素）继续出栈；b. （原始序列中）下一个数入栈；注意：回溯法，关键在于回溯，即在某分支结点 X：处理 X 的一个子分支，再退回分支 X，接着处理 X 的下一个子分支,若所有 X 的子分支处理完，再退回上一层分支节点。所谓“退回”，7十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程实际上就是恢复。程序代码：(2_8_1.c)#include #def
17、ine MAX 26typedef struct schar aMAX;int top;Stack;/*定义一些全局变量*/Stack S; /*定义全局性的栈*/char dMAX,seqMAX; /*dMAX用于存储原始入栈序列，seqMAX用于存储输出序列*/int len; /*定义将通过栈的元素个数*/int count=0; /* 用于统计输出序列的个数 */void initStack(Stack *S) /*初始化空栈*/ S-top=-1; void push(Stack *S, char x) /*进栈*/if (S-top=MAX) return;S-top+;S-aS-
18、top=x;char pop(Stack *S)/*出栈*/if (S-top=-1) printf(ERROR, POP Empty Stack);return -1;S-top-;return S-aS-top+1;int isEmpty(Stack *S)/*判断栈是否为空*/if (S-top=-1) return 1;return 0;void outSeq(char *seq, int len)/*输出顶点序列*/int i;for(i=0; ilen; i+)printf(%2c,seqi);printf(n);void scheduler(int pos, int seq_po
19、s)8十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程pos: 处理到原始数据中的第 pos 个元素，seq_pos：若出栈，应放在当前输出数组的第 seq_pos 个位置int i=0;char t;/*对任何一个数，总是先进栈，再出栈。另外，这里不需要循环，类似于“查找数组中元素”用递归*/if(pos=len & isEmpty(&S) outSeq(seq,len); count+; int main()int i;printf(nplease input the num be scheduled: );scanf(%d, &len); /*用 len 存储待调度的火车数量
20、*/for(i=0; i1 时，perm(R)由(r1)perm(R1),(r2)perm(R2),(rn)perm(Rn)构成。依此递归定义，可设计产生 perm(R)的递归算法如下：递归解法：(2_8_2.c)#includeint cont=1;/*全局变量，用于记录所有可能的出栈序列个数*/void print(int str,int n);/*求整数序列 str从 k 到 n 的全排列*/void perm(int str,int k,int n)int i,temp;if (k=n-1) print(str,n);else for (i=k;in;i+)temp=strk; str
21、k=stri; stri=temp;perm(str,k+1,n); /*递归调用*/temp=stri; stri=strk; strk=temp;/*本函数判断整数序列 str是否满足进出栈规则,若满足则输出*/void print(int str,int n)int i,j,k,l,m,flag=1,b2;for(i=0;in;i+)/*对每个 stri判断其后比它小的数是否为降序序列*/ m=0;for(j=i+1;jstrj) if (m=0) bm+=strj;else if (strjb0) flag=0;else b0=strj;if(flag)/*满足出栈规则则输出 str中
22、的序列*/10十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程printf( %2d:,cont+);for(i=0;in;i+)printf(%d,stri);printf(n);int main()int str100,n,i;printf(input a int:); /*输出排列的元素个数*/scanf(%d,&n);for(i=0;in;i+) /*初始化排列集合*/stri=i+1;printf(input the result:n);perm(str,0,n);printf(n);return 0;当参与进出栈的元素个数为 4 时，输出的结果如下图所示。该算法执行的时
23、间复杂度为 O（n!）。随着 n 的增大，算法的执行效率非常的低。非递归解法：（2_8_3.c）对一组数穷尽所有排列，还可一种更直接的方法，将一个排列看作一个长整数，则所有排列对应着一组整数，将这组整数按从小到大的顺序排成一个数列，从对应最小的整数开始，按数列的递增顺序逐一列举每个排列对应的每一个整数，这能更有效地完成排列的穷举。从一个排列找出对应数列的下一个排列可在当前排列的基础上作部分调整来实现。倘若当前排列为1,2,4,6,5,3，并令其对应的长整数为 124653。要寻找比长整数 124653 更大的排列，可从该排列的最后一个数字顺序向前逐位考察，当发现排列中的某个数字比它前一个数字大
24、时，如本例中的 6 比它的前一位数字 4 大，则说明还有可能对应更大整数的排列。但为顺序从小到大列举出所有的排列，不能立即调整得太大，如本例中将数字 6 与数字 4 交换得到的排列为 126453 就不是排列 124653 的下一个排列。为得到排列 124653 的下一个排列，应从已考察过的那部分数11十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程字中选出比数字 4 大，但又是它们中最小的那一个数字，比如数字 5，与数字 4 交换。该数字也是从后向前考察过程中第一个比 4 大的数字，5 与 4 交换后，得到排列 125643。在前面数字1，2，5 固定的情况下，还应选择对应最小整
25、数的那个排列，为此还需将后面那部分数字的排列颠倒，如将数字 6，4，3 的排列顺序颠倒，得到排列 1,2,5,3,4,6，这才是排列 1，2，4，6，5，3 的下一个排列。按照以上想法可以编写非递归程序实现 n 个数的全排列，对满足进出栈规则的排列则计数并输出。/*本程序输出 1 2 . n 个序列进栈出栈的序列*/#include int pl(int n) int a100;int flag=1,flag1=0;FILE *rf ;int i,j,k,x,count=0;rf = fopen(stack.txt, w) ;for (i=1;i=n;i+)ai=i;while (flag)
26、flag1=1;/*最大处理范围为 99 个数*/*pl.txt 用于存放进出栈序列结果*/*初始序列*/* 还剩余未输出的排列*/* 判断本次排列是否符合进栈出栈序列 */for (i=1;i=n;i+) j=i+1;while (jai) j+; /* 找 ai后第一个比 ai小的元素 aj*/k=j+1;while (k=n)/* 如果 aj后还有比 ai小且比 aj大的元素,则此排列无效*/if ( ak aj) flag1=0;k+;if (flag1) for (i=1;i1 & aij & aiaj) i-;12十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程k=aj
27、;aj=ai;ai=k;k=j+1;for ( i=k+1;i=k & xnext=NULL Bp=NULL Cp-next=headDp=head（3）在带头结点的单链表中查找 x 应选择的程序体是（ C ）。Anode *p=head-next; while (p & p-info!=x) p=p-next;if (p-info=x)return p else return NULL;Bnode *p=head; while (p& p-info!=x) p=p-next; return p;Cnode *p=head-next;while (p&p-info!=x) p=p-next;
28、return p;Dnode *p=head; while (p-info!=x) p=p-next ; return p;（4）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ D ）。A必须是连续的C一定是不连续的B部分地址必须是连续的D连续不连续都可以（5）在一个具有 n 个结点的有序单链表中插入一个新结点并保持单链表仍然有序的时间复杂度是（ BAO(1)BO(n)CO(n2)DO(nlog2n)（6）用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时（ D ）。A仅修改队头指针C队头、队尾指针都要修改B仅修改队尾指针D队头,队尾
29、指针都可能要修改（7）若从键盘输入 n 个元素，则建立一个有序单向链表的时间复杂度为（ B ）。AO(n)BO(n2)CO(n3)DO(nlog2n)（8）下面哪个术语与数据的存储结构无关（ D ）。A顺序表B链表C散列表D队列（9）在一个单链表中，若删除 p 所指结点的后续结点，则执行（ A ）。Ap-next=p-next-next;Cp-next=p-next;Bp=p-next; p-next=p-next-next;Dp =p-next-next;（10）在一个单链表中，若 p 所指结点不是最后结点，在 p 之后插入 s 所指结点，则执行（ B ）。As-next=p;p-next=
30、s;Cs-next=p-next;p=s;Bs-next=p-next;p-next=s;Dp-next=s;s-next=p;3.2 设计一个算法，求一个单链表中的结点个数。【答】：单链表存储结构定义如下（相关文件：linklist.h）#include 14十二五普通高等教育国家级本科规划教材#include typedef struct node int data;struct node *next;linknode;typedef linknode *linklist;/*尾插法创建带头结点的单链表*/linklist creatlinklist() linklist head,r,s
31、;int x;head=r=(linklist)malloc(sizeof(linknode);printf(n 请输入一组以 0 结束的整数序列：n);scanf(%d,&x);while (x) s=(linklist)malloc(sizeof(linknode);s-data=x;r-next=s;r=s;scanf(%d,&x);r-next=NULL;return head;/*输出带头结点的单链表*/void print(linklist head) linklist p;p=head-next;printf(List is:n);while(p) printf(%5d,p-da
32、ta);p=p-next;printf(n);基于上述结构定义，求单链表中的结点个数的算法程序如下：int count(linklist head)高等学校精品资源共享课程int c=0;linklist p=head;while (p)15十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程c+;p=p-next;return c;3.3 设计一个算法，求一个带头结点单链表中的结点个数。【答】：带头结点的单链表的存储结构定义同题 3.2，实现本题功能的算法程序如下（3_3.c）#include linklist.hint count(linklist head) int c=0;li
33、nklist p=head-next;while (p)c+;p=p-next;return c;main()/*测试函数*/linklist head;head=creatlinklist();print(head);printf(nLength of head is:%d,count(head);getch();当输入 5 个数据时，产生的输出结果如下图所示：3.4 设计一个算法，在一个单链表中值为 y 的结点前面插入一个值为 x 的结点。即使值为 x 的新结点成为值为 y 的结点的前驱结点。【答】：#include linklist.hvoid insert(linklist head,
34、int y,int x)/*在值为 y 的结点前插入一个值为 x 的结点*/linklist pre,p,s;pre=head;16十二五普通高等教育国家级本科规划教材p=head-next;while (p & p-data!=y) pre=p;p=p-next;if (p)/*找到了值为 y 的结点*/ s=(linklist)malloc(sizeof(linknode);s-data=x;s-next=p;pre-next=s;高等学校精品资源共享课程void main()linklist head;int y,x;head=creatlinklist();print(head);/*
35、测试程序*/*创建单链表*/*输出单链表*/printf(n 请输入 y 与 x 的值:n);scanf(%d %d,&y,&x);insert(head,y,x);print(head);程序的一种运行结果如下图所示：3.5 设计一个算法，判断一个单链表中各个结点值是否有序。【答】：#include linklist.hint issorted(linklist head,char c)/*当参数 c=a时判断链表是否为升序，当参数 c=d是判断链表是否为降序*/ int flag=1;linklist p=head-next;switch (c)17十二五普通高等教育国家级本科规划教材ca
36、se a:/*判断带头结点的单链表 head 是否为升序*/while (p &p-next & flag)if (p-datanext-data) p=p-next;else flag=0;break;case d:/*判断带头结点的单链表 head 是否为降序*/while (p &p-next & flag)if (p-data=p-next-data) p=p-next;else flag=0;break;return flag;高等学校精品资源共享课程int main()/*测试程序*/ linklist head;head=creatlinklist();print(head);i
37、f (issorted(head,a) printf(单链表 head 是升序排列的！n);elseif (issorted(head,d) printf(单链表 head 是降序排列的！n);else printf(单链表 head 是无序的！n);程序运行时的三种输出结果如下图所示：3.6 设计一个算法，利用单链表原来的结点空间将一个单链表就地转置。【答】：#include linklist.hvoid verge(linklist head)18十二五普通高等教育国家级本科规划教材/*本函数的功能是就地倒置带头结点的单链表*/linklist p,q;p=head-next;head-next=NULL;高等学校精品资源共享课程while (p)/*每次从原表取一个结点插入到新表的最前面*/q=p;p=p-next;q-next=head-next;head-next=q;int main()linklist head;head=creatlinkli