数据结构习题集答案

1、第一章 概论1. 单项选择题1.1 B 1.2 C 1.3 A 1.4 D 1.5 A1.6 D 1.7 D 1.8 A 1.9 D 1.10 B2. 填空题2.1 逻辑结构 2.2 查找 2.3 读取2.4 插入 2.5 删除 2.6 更新2.7 索引存储 2.8 执行算法所需要的时间2.9 逻辑运算 2.10 存储结构3. 简答题3.1答：凡是能被计算机存储、加工的对象统称为数据，数据是一个集合。数据元素是数据的基本单位，是数据的一个元素。数据元素与数据之间的关系是元素与集合之间的关系。3.2答：数据：数据是信息的载体，它能够被计算机识别、存储和加工处理数据元素：是数据的基本单位。有时一个

2、数据元素包含几个数据项数据类型：是一个值的集合以及在这些值上定义的一组操作的总称数据结构：指的是数据之间的逻辑关系也称数据的逻辑结构。它包括线性结构和非线性结构两大类。存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构。线性结构：如果结构非空，则有且仅有一个开始结点和一个终端结点，并且所有的结点都最多只有一个直接前驱和一个直接后继非线性结构：该结构的逻辑特征是一个结点可能有多个直接前驱和直接后继3.3答：顺序存储结构是将各数据元素的存储位置按其之间的逻辑关系存放在一块连续的存储空间内，由数据元素的存储位置体现数据元素之间的逻辑关系。链式存储结构各数据元素不一定是存储在连续的一

3、块存储空间内，数据元素之间的逻辑关系与存储位置没有一一对应的关系，数据元素之间的逻辑关系，是依靠附加在存储数据元素的结点中的指针表示3.4答：a.算法必须是正确的b.执行算法所耗费的时间c.执行算法所耗费的空间，其中主要考虑辅助存储空间d.算法应易于理解、易于编码、易于调试等等。4. 应用题4.1其中语句y=y+1的频度是n-1，语句x=x+1的频度是（n-1）（2n+1）。所以该程序的算法时间复杂度是：T（n）=O（n-1）（2n+1）=O（n2）4.2由于嵌套最深的语句的频度为n，所以其算法的时间复杂度为O（n）。第二章 线性表1 单项选择题1.1 A 1.2 C 1.3 D 1.4 A

4、1.5 C1.6 A 1.7 C 1.8 A2 填空题2.1 n-i+1 2.2 n-I 2.3 相邻 2.4 p！=NULL 2.5 L*（i-1） 2.6 直接前驱2.7 表头指针 2.8 s-next=s2.9 s-next=s-prior=s3 简答题3.1答：a.线性表的顺序存储表示结构简单，不需要额外的存储空间，数据记录在逻辑上相邻，在存储位置上亦相邻，可随机存取，有些运算容易实现；但在做插入和删除运算时要移动大量的元素，表长是固定的，不易扩展。b.链式存储表示是动态结构，表长可任意扩充，插入和删除不需要移动大量的元素；但不能随机存取，需要增加相应的存储空间。3.2答： 在开始结点

5、之前附设的一个结点称为头结点，它的数据域值是无意义的，而开始结点是链表中存储线性表中第一个元素的结点。3.3答：循环链表和双向链表4 算法设计4.1在顺序表中第i个位置上插入元素x j=L-length-1 L-dataj4.2将顺序表中位置为i的元素删除 jlength-1 L-dataj; 4.3头插法建立单链表(ListNode *)malloc(sizeof(ListNode) head 4.4尾插法建立单链表head=s; r-next=s; 4.5在链表中查找序号为i的结点p-next&jnext;4.6将值为x的结点插入到单链表的第i个位置上GetNode(head,i-1);p

6、-next;4.7删除单链表中的第i个结点p-next;r-next;第三章 栈和队列1. 单项选择题1.1 B 1.2 B 1.3 D 1.4 C 1.5 D1.6 B 1.7 A 1.8 C 1.9 B 1.10 A1.11 A 1.12 B 1.13 A 1.14 A 1.15 B1.16 A 1.17 B 1.18 D 1.19 B 1.20 D2. 填空题2.1 先进先出2.2 S.top=-12.3 S.top=maxsize-12.4 栈满2.5 空栈2.6 n-12.7 s.topnext2.11 ls-next=NULL2.12 首2.13 b2.14队空否1.15 sq.d

7、atai2.16 sq.datamax2.17 max+12.18 尾2.19 02.20 03.简答题3.1答：进栈操作是先将栈顶指针加1后，再将待插入元素入栈，退栈操作则是先取出栈顶元素，在使栈顶指针减1。3.2答：入队操作的指针移动语句为：cq.rear=(cq.rear+1)%QueueSize；出队操作的指针移动语句为：cq.front=(cq.front+1)%QueueSize；3.3答：所有可能的出站顺序有：123，132，213，231，321，不可能是312，因为当3号车进站并出站后，站台上有1号车和2号车，不可能先出1号而后出2号。3.4答：出队操作是删除队头元素（修改头

8、指针）之后，再返回该删除元素值，而取队头操作仅仅是取出队头元素值返回，不修改队头指针。3.5答：简述下面给出的算法的功能是什么？（假设栈元素为整数类型）此算法的功能是通过一个数组将一个栈中的所有元素逆置存放。 3.6答：该算法的功能是通过一个中间栈T，达到删除栈S中所有与变量C相同的元素。3.7答：只设头指针的入队操作时间复杂度为O（n）；只设尾指针的入队操作时间复杂度为O（1）3.8答：栈叫先进后出表或叫后进先出表。栈的插入和删除都从称为栈顶的一端进行，一般线性表可以在线性表的中间及两端进行插入和删除操作。3.9答：队列叫先进先出表（FIFO）或叫后进后出表，队列的插入只能在队列的一端进行，

9、该端称为队尾。队列的删除只能从另一端进行，该端称为队头。一般线性表可以在线性表的中间及两端进行插入和删除操作。3. 10答：栈和队列都是加了限制的线性表，栈叫后进先出表，队列叫先进先出表。栈和队列的插入和删除运算都在端点进行，栈的插入与删除在同一端点，队列的插入与删除在不同的端点进行。栈与队列的元素个数都是可变的，同一个栈或同一个队列中的元素类型是一致的。3.11写出下列程序段的输出结果 输出结果：stack3.12 简述下列算法的功能 借助数组将S栈内的元素倒置3.13 简述下列算法的功能借助T栈将S栈内的元素倒置4.算法设计4.1顺序栈的六种基本操作 S-data+S-top=x; S-d

10、ataS-top4.2循环队列基本算法 Q-rear=(Q-rear+1)%QueueSize; return Q-dataQ-front第四章 串1.单项选择题1.1 A 1.2 B 1.3 D 1.4 A 1.5 B1.6 C 1.7 B 1.8 B2.填空题2.1 122.2 abcdefg3.简答题3.1答：串长度为零的串称为空串，它不包含任何字符；而空格串是有若干个空格字符构成的串，它的长度取决于空格的个数。3.2答：串的特殊性就在于它的每个元素仅由一个字符组成。3.3答：子串的定位运算又称为串的模式匹配，子串定位就是要在主串中找出一个与给定子串相同的子串，把这个主串称为目标串，而给

11、定的子串称为模式串。3.4答：两个串相等的充分必要条件是两串的长度相等且对应位置的字符相同。第五章 多维数组和广义表1.单项选择题1.1 D 1.2 C 1.3 B 1.4 D 1.5 C 1.6 B2.填空2.1 LOC（A00）+（n*i+j）*k2.2 3322.3 42第六章 树1.单项选择题1.1C 1.2A 1.3D 1.4B 1.5B 1.6C 1.7B 1.8D 1.9B 1.10D1.11A 1.12A 1.13B 1.14A 1.15A1.16A 1.17C 1.18A 1.19B 1.20B2.填空2.1 2k-1 2.2 2k-1 2.3 n0-12.4 2i-1 2.

12、5 5 2.6 02.7 n+1 2.8 2n-1 2.9 中序2.10 双亲链表表示法 2.11 孩子链表表示法2.12 2k-1 2.13 7 2.14 183.简答3.1 树：是n(n0)个结点的有限集T，T为空时称空树，否则它满足如下两个条件：有且仅有一个特定的称为根的结点；其余的结点可分为m（m0）个互不相交的子集T1，T2，Tm，其中每个子集本身又是一棵树，并称其为根的子树。3.2 二叉树：是n(n0)个结点的有限集，它或者是空集（n=0）,或者由一个根结点及两个互不相交的、分别称作这个根的左子树和右子树的二叉树组成。3.3 树的遍历：是指沿着某条搜索路线，依次对树中的每个结点均做

13、一次且仅做一次访问。3.4 哈夫曼树：在权为w1,w2,，wn的n个结点所构成的所有二叉树中，带权路径长度最小的二叉树称为最优二叉树，又称哈夫曼树。4.应用bdgacehf4.1 后序遍历序列：gdbehfcabchadefg4.2 先序遍历序列：abcdefgh4.3 BCHADEFGJI4.4 data firstchild12 3 4 5 6 78 9 ABCDE F G H I J root 0 1 2 3 4 5 6 7 8 94.5 下标0123456789 MaxTreeSize-1 dataABCDEFGHIJparent-10001123334.6 D H F I C G J

14、 A B E T4.7 假设7个结点分别为a、b、c、d、e、f、g，它们对应的权值为8、11、13、5、17、25、21，构造的哈夫曼树如下：该哈夫曼树的带权路径长度为：WPL=84+54+173+113+133+252+212 =287gfedbca 100 45 5521 24 25 30 11 13 17 13 8 5 5.算法5.1i=n;im;i+Tp1.parent= Tp2.parent=i第七章 图1.单项选择题1.1A 1.2C 1.3B 1.4B 1.5D 1.6C 1.7A 1.8B 1.9C 1.10B1.11A 1.12C 1.13B 1.14B 1.15C1.16

15、C 1.17 D 1.18C 1.19C 1.20A1.21C 1.22A 1.23D 1.24A 1.21B2.填空2.1 n-1 2.2 1 2.3 O(n+e)2.4 O(n+e) 2.5 求矩阵第i列非零元素之和2.6 将矩阵第i行全部元素置为0 2.7 最小2.8 n-1 2.9 1 2.10 2(n-1)2.11 n(n-1) 2.12 28 2.13 先序2.14 按层次 2.15 邻接表 2.16 逆邻接表3.简答3.1图的深度优先遍历：假设给定图的初态是所有顶点均未曾访问过，在G上任选一顶点v作为源点，则深度优先遍历定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从

16、v出发搜索v的每个邻接点w，若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直到图中所有和源点v有路径相通的顶点均被访问过；若此时图中仍有未访问有顶点，则另选一个尚未被访问过的顶点作为新的源点重复上述过程，直到所有顶点均已访问过。3.2 图的广度优先遍历：假设给定图的初态是所有顶点均未曾访问过，在G上任选一顶点v作为初始出发点，则广度优先遍历定义如下：首先访问出发点v，接着依次访问v的所有邻接点w1,w2,wt,然后再依次访问与w1,w2,wt邻接的所有未曾访问过的顶点。直到图中所有和源点v有路径相通的顶点均被访问过；若此时图中仍有未访问有顶点，则另选一个尚未被访问过的顶点作为新的源点

17、重复上述过程，直到所有顶点均已访问过。3.3 拓扑排序：对于一个有向无环图进行拓扑排序，是将G中所有顶点排成一个线性序列，使得对图中任意一个顶点u和v，若E(G)，则u在线性序列中出现在v之前。3.4 连通图：在无向图G中，若从顶点vi到顶点vj有路径，则称vi和vj是连通的，若V（G）上任意两个不同的顶点vi和vj都连通，则称G为连通图。3.5 强连通图：在有向图中，若对于V（G）中任意两个不同的顶点vi和vj，都存在从vi到vj以及vj到vi的路径，则称G是强连通图。3.6 最小生成树：对于连通的带权图G，其生成树也是带权的，我们把生成树T的各边的权值总和称为该树的权，将权值最小的生成树称

18、为G的最小生成树，简记MST。4.应用4.1存拓扑排序序列：123654123546231424.2最小生成树：4.3 邻接矩阵：广度优先遍历结果：124536深度优先遍历结果：1234564.4 图G的邻接表：01234 3 4 4 2 2 1 2 3 0 1 0 1 V1 V2 V3 V4 V54.5 图G的逆邻接表： 3 0 0 2 V1 V2 V3 V4E F G H I J 0123顶点入度出度V112V210V311V4115.算法5.1 i=0;in;i+ k=0;ke;k+5.2 !QueueEmpty(&Q) j=0;jn;j+5.3 k=0;kn-1;k+ e=Tm;Tmt

19、k;Tk=e;5.4 !StackEmpty(&S)p=G.adjlisti.firstedge第八章 排序1 单项选择1.01 B 1.02 D 1.03 C 1.04 B 1.05 A 1.06 A 1.07 A 1.08 C 1.09 A 1.10 A1.11 B 1.12 D 1.13 D 1.14 A 1.15 C1.16 A 1.17 D 1.18 A 2 填空1.01分配排序 1.02静态查找 1.03动态查找 1.04冲突 1.05排序 1.06哈希函数（散列函数）1.07 n-1 1.08 0 1.09多关键字文件3 简答3.01简述稳定排序和非稳定排序。若待排序的文件中，存

20、在有多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是稳定的；反之若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。3.02简述插入排序算法中的哨兵作用 在插入排序算法中，将要前插的记录ri保存在r0称作为哨兵。它的主要作用是用来在查找循环中“监视”下标变量j是否越界，因为r0就是ri本身，所以一旦越界（即j=0）则循环条件r0.key=high为止。3.04如何选择合适的排序方法？若n较小时，可以采用直接插入、直接选择或冒泡排序方法；若文件初始状态基本有序，则可以选择直接插入、冒泡排序方法；若n较大时，则应选择快速排序、

21、堆排序或归并排序方法。4 应用4.01给定数据35，27，86，39，58，19，46，74；请写出按插入排序的每一趟结果。3527 86 39 58 19 46 7427 3586 39 58 19 46 7427 35 8639 58 19 46 7427 35 39 8658 19 46 7427 35 39 58 8619 46 7419 27 35 39 58 8646 7419 27 35 39 46 58 867419 27 35 39 46 58 74 864.02给定数据49，33，61，82，75，12，25，58，29；请写出按快速排序的每一趟结果。49 33 61 82

22、 75 12 25 58 2929 33 25 124975 82 58 6112 2529334961 587582122529 33 49 5861 75 82 12 25 29 33 49 58 61 75 824.03给定数据35，27，86，39，58，19，46，74；请写出按选择排序的每一趟结果。1927 86 39 58 35 46 7419 2786 39 58 35 46 7419 27 3539 58 86 46 7419 27 35 3958 86 46 7419 27 35 39 4686 58 7419 27 35 39 46 5886 7419 27 35 39

23、46 58 748619 27 35 39 46 58 74 864.04给定数据48，32，61，82，75，19，25，58；请写出按冒泡排序的每一趟结果。48 32 61 82 75 19 25 581948 32 61 82 75 25 5819 2548 32 61 82 75 5819 25 3248 58 61 82 7519 25 32 4858 61 75 8219 25 32 4858 61 75 8219 25 32 48 58 61 75 824.05给定数据38，29，81，34，58，19，46，76；请写出按冒泡排序的每一趟结果。38 29 81 34 58 19

24、 46 761938 29 81 34 58 46 7619 2938 34 81 46 58 7619 2938 34 81 46 58 7619 29 3438 46 81 58 7619 29 34 3846 58 81 7619 29 34 38 46 58 81 764.06给定数据52，33，61，82，75，18，45，58，26；请写出按快速排序的每一趟结果。52 33 61 82 75 18 45 58 2626 33 45 185275 82 58 61182645 335261 58758218 263345 525861 75 8218 26 33 45 52 58 6

25、1 75 825 算法5.01直接插入排序算法（递增）Ri.key Ri-1.keyj = i-15.02冒泡排序算法（递增）i nRj+1.key Rj.key5.03归并排序算法i=m & j=high P+, i+第九章 查找1 单项选择1.01 B 1.02 D 1.03 B 1.04 A 1.05 D1.06 B 1.07 C 1.08 D 1.09 A 1.10A1.11 C 1.12 C 1.13 D 1.14 C 1.15 B1.16 B 1.17 C 1.18 C 1.19 A 2 填空2.01 动态查找表 2.02 散列函数（哈希函数） 2.03 散列表的长度2.04 28

26、 2.05 60 2.06 32.07 5 2.08 35 2.09 272.10 (n+1)/2 2.11 log2(n+1)-1 2.12 (s2+2s+n)/(2s)2.13 散列查找方法 2.14 按关键字有序 3 简答3.01简述静态查找和动态查找。若在查找的同时对查找表进行修改操作（插入或删除操作），则相应的查找表称之为动态查找表；否则称之为静态查找表。3.02什么是平均查找路径长度ASL。通常把查找过程当中对关键字比较的平均次数作为平均查找路径长度。若n是查找表的结点数，pi是查找第i个结点的概率，ci是找到第i个结点的比较次数，则平均查找路径长度 ASL= pici。3.03简

27、述二分查找的基本思想。设rlowhigh为当前的查找区间，首先确定区间的中点位置m=(low+high)/2；然后将待查关键字K与rm.key进行比较，若相等则查找成功并返回位置m；若Krm.key，则令low=m+1；确定新的查找区间再次进行查找，直到查找成功或查找区间为零时（查找失败）结束。3.04简述二叉排序树的性质。若它的左子树非空，则左子树上所有结点的值均小于根结点的值；若它的右子树非空，则右子树上所有结点的值均大于根结点的值；左、右子树本身仍是一棵二叉排序树。3.05简述散列表中的冲突（碰橦）概念。有两个不同的关键字k1和k2，通过散列函数计算映射到表的同一个位置空间时，即：H(k

28、1)=H(k2)，则称之为发生冲突（碰橦），而发生冲突的两个关键字称为该散列函数的同义词。3.06散列函数的选择标准是什么？散列函数选择有两条标准：简单和均匀。简单是指散列函数的计算简单快捷；均匀是指散列函数能将集合中的关键字以等概率映射到查找表的任何一个位置空间。3.07简述在散列表中拉链法解决冲突的基本思想。拉链法解决冲突的做法是，将所有关键字为同义词的结点链接在同一个单链表中。首先选定散列表的长度m，然后构造由m个头指针组成的指针数组T0m-1，凡是映射地址为i的结点，均插入以Ti为头指针的链表中。4 应用4.01按拉链法构造构造散列函数表 0123456515635154662374126181030在等