1. 数据结构是一门研究程序设计中数据（元素）以及它们之间的关系和运算筹的学科
2. 在数据结构中从逻辑上可以把数据结构分为（线性结构和非线性结构）两类
3. 数据的逻辑结构是（数据元素之间逻辑）关系的整体
4. 下列说法中不正确的是（数据项可由若干个数据元素构成）
5. 在计算机的存储器中表示数据时，物理地址和逻辑地址的相对位置相同并且是连续的，称之为（顺序存储结构）
6. 在链式存储结构中，一个存储结点通常用于存储一个（数据元素）
7. 数据运算（其执行效率与采用何种存储结构有关）
8. 数据结构在计算机内存中的表示是指（数据的存储结构）
9. 在数据结构中，与所使用的计算机无关的是（逻辑结构）
10. 数据采用链式存储结构时要求（每个结点占用一片连续的存储区域）
11. 以下叙述正确的是（III.链式存储结构通过链指针表示数据元素之间的关系）
12. 以下（长度有限）不是算法的基本特征
13. 在计算机中算法指的是解决某一问题的有限运算序列，他必须具备输入，输出，（可行性，有穷性和确定性）
14. 下面关于算法的说法正确的是（一个算法所花的时间等于该算法中每条语句的执行时间之和）
15. 算法的时间复杂度与（问题规模）有关
16. 算法分析的主要任务之一是分析（算法的执行时间和问题规模之间的关系）
17. 算法分析的目的是（分析算法的效率以求改进）
18. 某算法的时间复杂度为O（n2），表明该算法的（执行时间与n2成正比）
19. 某算法的时间复杂度为O（n）表示该算法的（执行时间与n呈现线性增长的关系）
20. 算法的空间复杂度是指（算法中需要的临时变量所占用存储空间的大小）
21. 线性表是（一个有限序列，可以为空）
22. 在一个长度为n的顺序表中向第i个元素之前插入一个新元素时需要向后移动（n-i+1）个元素
23. 链表不具有的特点（可随机访问任一元素）
24. 若线性表最常用的运算是存取第i个元素以及前驱元素值，则采用（顺序表）存储方式节省时间
25. 在单链表中，若p结点不是尾结点，在其中插入s结点的操作是（s next = p next p next = s）
26. 在一个单链表中，删除p结点之后的一个结点的操作是（p next = p next next）
27. 某线性表最常用的运算是在尾元素之后插入元素和删除开始元素，则以下（仅有尾结点指针的循环单链表）存储方式最节省运算时间
28. 如果对含有n个元素的线性表的运算只有4种，即删除第一个元素，删除尾元素，在第一个元素前面插入新元素，在尾元素的后面插入新元素，则最好使用（只有首结点指针没有尾结点指针的循环双链表）
29. 以下关于有序表的叙述正确的是（有序表既可以采用顺序表存储，也可以采用链表存储）
30. 在只有尾结点指rear没有头结点的非空循环单链表中，删除开始结点的时间复杂度为（O1）
31. 在有n个元素的顺序表中的任意位置插入一个元素所需移动元素的平均次数为n/2
32. 带头结点的单链表L为空的判定条件是L->next==NULL
33. 线性表采用某种链式存储结构，在该链表上删除尾结点的时间复杂度为O1 则该链表是（循环双链表）
34. 两个长度分别为m，n的有序单链表，在采用二路归并算法产生一个有序单链表时，算法的时间复杂度为O（m+n）
35. 有一个长度为n的循环单链表L，在p所指的结点之前插入一个新结点，其时间复杂度为O（n）
36. 顺序表具有随机存取特性，所以查找值为x的元素的时间复杂度为O（1）×
37. 在含有n个结点的单链表L中，将p所指结点（非首结点）与其前驱结点交换，时间复杂度为O（1）×
38. 向顺序表中插入一个元素平均要移动大约一半的元素√
39. 对于单链表来说需要从头结点出发才能扫描表中的全部结点√
40. 由于顺序表需要一整块连续的存储空间，所以存储空间利用率高×
41. 以下数据结构中元素之间为线性关系的是（以上都是）
42. 栈和队列的共同点是（只允许在端点处插入和删除元素）
43. 设一个栈的输入序列为a，b，c，d，则借助一个栈所得到的输出序列不可能是（dabc）
44. 已知一个栈的进栈序列是1,2，3，.....n，其输出序列是p1...若p1 = n 则pi的值是（n-i+1）
45. 设n个元素......则p2的值是（不可能是1）
46. 循环队列（不会产生假溢出）
47. 设有5个元素的进栈序列是.....栈容量至少是（4）
48. 表达式a*(b+c)-d的后缀表达式是（abc+*d-）
49. 表达式（a+a*b）*a+c*b/a的后缀表达式是（aab*+a*cb*a/+）
50. 在数据处理过程中常需要保存一些中间数据，如果先保存的数据先处理，则使用（队列）来保存这些数据
51. 栈是一种具有（后进先出）特性的线性表
52. 当利用大小为n.....首先应执行top++语句修改top指针
53. 若用带头结点的单链表st来表示链栈，则栈空的条件是（st->next==NULL）
54. 若环形队列的最大容量为MaxSize....公式为（（rear-front+MaxSize）%MaxSize）
55. 为了解决队列的假溢出现象，应采用队（循环）列
56. 在n个元素连续进栈以后，他们的出栈顺序和进栈顺序一定正好相反√
57. 栈顶元素和栈低元素有可能是同一个元素√
58. n个元素进队的顺序和出队的顺序总是一致的√
59. 无论是顺序队还是链队，插入，删除运算的时间复杂度都是O（1）√
60. 若用data【1...m】...只能进行m次
61. 串是一种特殊的线性表，其特殊性体现在（数据元素是一个字符）
62. 以下关于串的叙述中正确的是（串是一种特殊的线性表）
63. 串的长度是（串中所含字符的个数）
64. 两个字符串相等的条件是（串的长度相等且对应的字符相同）
65. 设S为.....个数为（+-）
66. 若串S=“software”，其子串个数为（37）
67. 一个链串的结点类型如下：如果每个字符占一个字节...该链串的存储密度为（3/4）
68. 串采用结点大小为1的链表作为其存储结构是指（链表中每个结点的数据域中只存放一个字符）
69. 设有两个串s和t，判断t是否为s子串的算法称为（串匹配）
70. 在BF模式中，j与i字符不相等，i的位移方式为（i=i-j+1）
71. 在BF模式中，j与i字符不相等，j的位移方式为（j=0）
72. 在kmp模式中，j与i不相等时，i的位移方式为（i不变）
73. 在kmp模式中，j与i不相等时，j的位移方式为（j=next[j]）
74. 在kmp模式中，j与i相等时，i的位移方式为（i++）
75. 在kmp模式中，j与i相等时，j的位移方式为（j++）
76. 设目标串为s，模式串为t，在kmp中next【4】=2的含义是（表示t4字符前面最多有两个字符和开头的两个字符相同）
77. 设串 s1 = “i am a student”,则串长为（14）
78. 设目标串s=“abccdcdccbaa”，模式串t=“cdcc”若采用BF算法，则在第（6）趟成功
79. 已知模式串t=“aaababcaabbcc”则t【3】=‘b’，next【3】=（2）
80. 已知t=“abcaabbcabcaabdab”，该模式串的next数组值为（-1 0 0 0 1 1 2 0 0 1 2 3 4 5 6 0 1）
81. 数组A[0..5,0.6]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5,5]的地址是[1175]
82. 数组通常具有的两种基本操作是[查找和修改]
83. 对矩阵压缩存储是为了[减少存储空间]
84. 稀疏矩阵一般的压缩存储方法有两种，即[三元组和十字链表]
85. 设有一个n行n列的对称矩阵A,将其下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那第i行的对角元素A[i][i]存放于B中[(i+3)*i/2]处
86.对n阶对称矩阵作压缩存储时，需要表长为[n(n+1)/2]的顺序表
87.若将n阶上三角矩阵A按列优先顺序压缩存放在一维数组B[1..n(n+1)/2]中，A中第一个非零元素a1,1存于B数组的b1中，则应存放到bk中的非零元素aij(i≤j)的下标i、j与k的对应关系是[j(i-1)/2+i
]
88. 将一个A[1.100,1..100]的三对角矩阵，按行优先存入一维数组B[1.298]中，A中元素 A66,65(即该元素行下标i=66,列下标j=65),在B数组中的位置K为[195]
89. 广义表((a, b), c,(d,(e)))的表尾是[(c,(d,(e)))]
90. 下面说法不正确的是[广义表的表头总是一个广义表]
91. 广义表(a,((b,(c,d,(e,f))),g))的深度为[5]
92. 以下关于二叉树遍历的说法中，错误的是[一颗二叉树中，若每个结点最多只有左孩子，没有右孩子，则先序和后续序列相同]
93. 二叉树若用顺序存储结构表示，则下列4种运算中的[层次遍历]二叉树最容易实现。
94. 给定二叉树如图所示。设N代表二叉树的根,L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3,1,7,5,6,2,4则其遍历方式是[RNL]
95. 以下关于二叉树的说法中正确的是[二叉树中每个结点的度可以小于2]
96. 以下关于二叉树的说法中正确的是[二叉树中度为0的结点个数等于度为2的结点个数加1]
97. 设有13个权值，用他们组成一颗哈夫曼树，则该哈夫曼树共有[25]个结点
98. 假设每个结点值为单个字符，而一棵树的后根遍历序列为ABCDEFGHIJ，则其根结点值是[J]
99. 一颗完全二叉树中有1001个结点，其中度为1的结点个数是[1]
100. 若知道该二叉树的[中序和后序序列],便可以唯一确定该二叉树
101. 一颗二叉树的先序遍历为ABCDEF，中序遍历序列为CBAEDF，则后序遍历序列为[CBEFDA]
102. 某颗二叉树中，X结点有左孩子Y结点，则在其先序遍历中[访问X结点后立即访问Y结点]
103. 若二叉树采用二叉链存储结构，要删除该二叉链中所有结点并释放他们占用的空间，利用[后序]遍历方法最合适
104. 根据使用频率为5个字符设计的哈夫曼编码不可能是[100,11,10,1,0]
105. 下面关于哈夫曼树的说法，错误的是[哈夫曼树中除了度为1的结点外，还有度为2的结 点和叶子结点]
106. 在二叉树中，指针p所指结点为叶子结点的条件是[p->lchild==null && p->rchild==null]
107. 一颗含有50个结点的二叉树，他的最小高度是[6]
108. 一颗含有65个结点的高度最大的二叉树，第10层有[1]个结点
109. 一颗含有50个结点的二叉树，他的最大高度是[50]
110. 一颗含有50个结点的二叉树中，第6层有[19]个结点
111. 非空二叉树的先序序列的最后一个结点一定是叶子结点（对）
112. 哈夫曼树是带权路径长度最短的二叉树，权值越大的结点离根结点越远（错）
113. 在哈夫曼树中，权值相同的叶子结点都在同一层上（错）
114. 存在这样的二叉树，对它采用任何次序的遍历，结果相同（对）
115. 如果具有n个顶点的图恰好是一个环，则他有[2n]颗生成树
116. 对有n个顶点、e条边且使用邻接表存储的有向图进行深度优先遍历，其算法的时间复杂度是[O(n+e)]
117. 一个有n个顶点的无向图最多有[n(n-1)/2]条边
118. 用Dijkstra算法求一个带权有向图G中从顶点0出发的最短路径,在算法执行的某时刻，S={0,2,3,4}，选取的目标顶点是顶点1，则可能修改最短路径是[从顶点0到顶点1的最短路径]
119. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的[先序遍历]算法
120. 有一个顶点编号为0~4的带权有向图G，现用Floyd算法求任意两个顶点之间的最短路径，在算法执行的某时刻，已经考虑了0~2的顶点，现考虑顶点3，则以下叙述中正确的是[所有两个顶点之间的路径都可能被修改]
121. 对于n个顶点e条边的有向带权图，可以通过Dijkstra算法求出所有两个顶点之间的最短路径，此时的时间复杂度为[O(n3)]
122. 任何一个带权无向连通图[有一颗或多颗]最小生成树
123. Dijkstra算法是[按长度递增的顺序求出图的某顶点到其余顶点的最短路]方法求出图中从某点到其余顶点最短路径的
124. 以下关于广度优先遍历的叙述中正确的是[对一个强连通图调用一次广度优先遍历算法便可访问所有的顶点]
125. 对于某个带权连通图构造最小生成树，以下说法中正确的是[仅该图的最小生成树的总代价一定是唯一的]
126. 用Prim算法求一个连通的带权图的最小代价生成树，在算法执行的某时刻，已选取的顶点集合U={1,2,3}，已选取的边的集合TE={（1,2）（2,3）}，要选取下一条权值最小的边，应当从[{(1,4)，(3,4)，(3,5)，(2,5)}]组中选取
127. 用Dijkstra算法求一个带权有向图G中从顶点0出发的最短路径，在算法执行的某时刻，S={0,2,3,4}，下一步选取的目标顶点可能是[顶点7]
128. 对有n个顶点、e条边且使用邻接矩阵存储的有向图进行广度优先遍历，其算法的时间复杂度[O(n2)]
129. 一个无向连通图的生成树是含有该连通图的全部顶点的[极小连通子图]
130. 图的遍历是指[从一个顶点出发访问图中所有顶点且每个顶点只能访问一次]
131. 如果从无向图的任一顶点出发进行一次深度优先遍历即可访问所有顶点，则该图一定是[连通图]
132. 非空无向图的临界矩阵是一个[对称矩阵]
133. 用Kruskal算法求一个连通的带权图的最小代价生成树，在算法执行的某时刻，已选取的边集合TE={（1,2），（2,3），（3,5）}，要选取下一条权值最小的边，不可能选取的边[(1,3)]
134. 以下[遍历]方法可用于求无向图的连通分量
135. 在一个具有n个顶点的无向连通图中至少有[n-1]
136. 以下叙述中错误的是[图的深度优先遍历不适合有向图]
137. 一个有向图G=（V,E），V={0,1,2,3,4}，E={<0,1>,<1,2>,<0,3>,<1,2>,<1,4>,<2,4>,<4,3>}，现按深度优先遍历算法遍历，从顶点0出发，所得到的顶点序列是[0,1,2,4,3]
138. 在一个无向图中，所有顶点的度之和等于边数的[2]倍
139. 在使用Prim和Kruskal算法构造最小生成树时，前者更适合于[稀疏图]，后者更适合于[稠密图]
140. 一个具有n个顶点的无向图是一个环，则它有[2n]颗生成树
141. 一个带权连通图的最小生成树[不一定是]唯一的
142. 已知一无向图G=（V，E），其中，V={a,b,c,d,e},E={(a,b),(a,d),(a,c)(d,c),(b,e)}，现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是[深度优先]遍历方法
143. 含有n个顶点的无向图都连通全部顶点至少需要[n-1]条边
144. 已知一无向图G=（V，E），其中，V={a,b,c,d,e},E={(a,b),(a,d),(a,c)(d,c),(b,e)}，现用某一种图遍历方法从顶点a开始遍历图，得到的序列为adbce，则采用的是[广度优先]遍历方法
145. 对于无向图生成树，其深度优先生成树和广度优先生成树一定不相同（错）
146. 图的深度优先遍历算法和广度优先遍历算法是两种不同的算法，所以任何图的这两种遍历序列是不可能相同的（错）
147. 任何一个图，一旦指定源点，其深度优先遍历序列是唯一的（错）
148. 下列排序方法中，辅助空间为O（n）的是[归并排序]
149. 以下排序方法中，稳定的排序方法是[基数排序]
150. 快速排序在[排序的数据已基本有序]的情况下最不利于发挥其长处
151. 下列排序方法中，[归并排序]在一趟结束后不一定能选出一个元素放在其最终位置上
152. 以下序列不是堆的是{100，85，40，77，80，60，66，98，82，10，20}
153. 目前来讲，基于比较的内排序方法最好的平均时间复杂度为[O(nlog2n)]
154. 为实现快速排序法，待排序序列宜采用存储方式是[顺序存储]
155. 在排序算法中，每次从未排序的元素中通过关键字直接比较选取最小关键字的元素，加入到已排序元素的末尾，该排序方法是[简单选择排序]
156. 以下不属于内排序的方法是[拓扑排序]
157. 已知序列{18,12,16,10,5,15,2,8,7}是大根堆，删除一个元素后再调整为大根堆，调整后的大根堆是[{16，12，15，10，5，7，2，8}]
158. 内排序方法的稳定性是指[经过排序后，能使关键字相同的元素保持原顺序中的相对位置不变]
159. 以下[冒泡排序]方法在数据基本有序时效率最好
160. 下列排序方法中稳定的排序算法是[归并排序]
161. 在快速排序、堆排序、归并排序中，[归并]排序是最稳定的
162. 对数据序列{5,1,7,9,8,6,3,4,2,10}采用冒泡排序方法进行递增排序，每趟通过交换归位关键字最小的元素，经过一趟后的排序结果是[{1,5,2,7,9,8,6,3,4,10}]
163. 如果一组数据采用某种排序方法进行排序，排序后相同关键字的元素的相对位置不发生改变称该排序方法是[稳定]的
164. 每次从无序子表中取出一个元素，通过依次比较把它插入到有序子表的适当位置，此种排序方法称为[直接插入排序]
165. 内排序方法要求数据一定以顺序表方式存储[错]
166. 排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止（错）
167. 冒泡排序中，关键字比较的次数与初始数据序列有关，而元素移动的次数与初始数据序列无关[错]
168. 从时间性能看，堆排序总是优于简单选择排序
169. 对于不同的初始数据序列，二路归并排序算法中关键字比较次数有所不同[对]
170. 简单选择排序是一种不稳定的排序方法[对]
171. n个元素采用二路归并排序算法，总的趟数为n[错]
172. 当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响算法时间复杂度的主要因素[错]
173. 二路归并排序算法的时间复杂度与初始数据序列的顺序无关[对]
174. 所有内排序算法中的比较次数与初始元素序列的排序无关
---
1、简述二叉树与度为 2 的树之间的差别。
答：二叉树的子树有严格的左、右之分，其次序不能任意颠倒，某个结点即使只有一棵子树，
也区分是左子树还是右子树，而在度为 2 的树中，某个结点只有一棵子树时，是不区分左右
性的。除此之外，二叉树可以是空树，而度为 2 的树至少有一个度为 2 的结点，所以不能为
空树。
2、为了实现以下各种功能，x 结点表示该结点的位置，给出树的最适合的存储结构：
（1）求 x 和 y 结点的最近祖先结点。
（2）求 x 结点的所有子孙结点。
（3）求根结点到 x 结点的路径。
（4）求 x 结点的所有右边兄弟结点。
（5）判断 x 结点是否为叶子结点。
（6）求 x 结点的所有孩子结点。
答: （1）双亲存储结构。
（2）孩子链存储结构。
（3）双亲存储结构。
（4）孩子兄弟链存储结构。
（5）孩子链存储结构。
（6）孩子链存储结构。
3、设二叉树 bt 的一种存储结构如表 1 所示。其中，bt 为树根结点指针，lchild、rchild 分别
为结点的左、右孩子指针域，在这里使用结点编号作为指针域值，0 表示指针域值为空；data
为结点的数据域。请完成下列各题：
表 1 二叉树 bt 的一种存储结构
（1）画出二叉树 bt 的树形表示。
（2）写出按先序、中序和后序遍历二叉树 bt 所得到的结点序列。
答:（1）二叉树 bt 的树形表示如下图所示。
（2）先序序列: abcedfhgij 。
中序序列: ecbhfdjiga。
后序序列: echfjigdba。
4、给定一棵非空二叉树 b，采用二叉链存储结构，说明查找中序序列的第一个结点和最后
一个结点的过程。
答：中序序列的第一个结点就是根结点的最左下结点，其查找过程如下。
p= b;
while (p->lchild!= NULL) //循环结束，p 指向中序序列的第一个结点
p = p->lchild;
中序序列的最后一个结点就是根结点的最右下结点，其查找过程如下。
p= b;
while (p->rchild!= NULL) //循环结束，p 指向中序序列的最后一个结点
p = p->rchild;
5、若某非空二叉树的先序序列和中序序列正好相反，则该二叉树的形态是什么?
答：二叉树的先序序列是 NLR、中序序列是 LNR，要使 NLR = RNL(中序序列反序)成
立，则 R 必须为空，所以满足条件的二叉树的形态是所有结点没有右子树的单支树。
6、一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来。试求出空格
处的内容，并画出该二叉树。
先序序列: _ B__ F__ ICEH_ G
中序序列: D__ KFIA__ EJC_ 后序序列: _ K_ FBHJ__ G__ A
答：由后序序列可知根结点为 A，先序序列的第一个空为 A，由中序序列可知，左子树有 5
个结点，由先序序列可知，左子树中有 B、F、I 结点，所以中序序列的第一个空为 B，可推
出先序序列的第 2 个空为 D，第 3 个空为 K；右子树有 5 个结点，由中序序列可知，右子树
中有 E、J、C 结点，所以先序序列中第 4 个空为 J，这样产生完整的先序序列，可知右子树
根结点为 C，由中序序列可知，C 的左子树有 3 个结点，为 E、H、J，所以中序序列的第 2
个空为 H，C 的左子树只有一个结点 G，所以中序序列的第 3 个空为 G。
从而构造出的二叉树如下图所示：
则先序序列为 ABDFKICEHJG；中序序列为 DBKFIAHEJCG；后序序列为 DKIFBHJEGCA
7、假设一段正文由字符集{a,b,c,d,e,f}中的字母构成，这 6 个字母在这段正文中出现的次数
分别是{12,18,26,6,4,34}。回答以下问题：
（1）为这 6 个字母设计哈夫曼编码。
（2）求带权路径长度 WPL。
（3）设每个字节由 8 个二进制位组成，计算按照哈夫曼编码存储这段正文需要多少字节?
答：（1）构造的哈夫曼树如图所示，
对应的哈夫曼编码如下。
a: 001, b: 01, c: 10, d: 0001, e: 0000, f: 11。
（2）该哈夫曼树的 WPL=(4+6)*4+12*3+(18+ 26+34)*2=232。
（3）存储这段正文所需要的二进制位数恰好等于 WPL，所以对应 232/8=29 个字节。
8、若已知一棵完全二叉树（所有节点值均不同）的先序、中序或后序遍历序列中的一种，
能够唯一确定这棵二叉树吗？如果能，请以其中一种遍历序列来说明构造该二叉树的过程。
如果不能，并举一个反例予以说明。
答：能够。因为任一种遍历序列中含有节点个数 n，当 n 已知时就可以确定完全二叉树的形
态，以给定先序遍历序列 a1a2…an为例，由该完全二叉树形态得到的先序遍历序列 b1b2…bn，
则 bi=ai，这样就可以唯一构造这棵二叉树。
9、已知一棵二叉树的中序序列为 cbedahgijf，后序序列为 cedbhjigfa，给出该二叉树的树形
表示，并写出先序序列。
10、给定 6 个字符 a~f ，它们的权值集合 W = {2, 3, 4, 7, 8, 9}，试构造关于 W 的一棵哈
夫曼树，求其带权路径长度 WPL 和各个字符的哈夫曼编码。
答：由权值集合 W 构建的哈夫曼树如图所示。其带权路径长度 WPL=(9+7+8)*2+4*3+(2+3)*4= 80。
11、已知某二叉树的中序遍历序列为 BFDJGACHKEI，后序遍历序列 FJGDBKHIECA，请画出该
二叉树，并给出该二叉树的先序遍历序列。
12、Dijkstra 算法用于求单源最短路径，为了求一个图中所有顶点对之间的最短路径，可以
以每个顶点作为源点调用 Dijkstra 算法，Floyd 算法和这种算法相比有什么优势？
答：对于有 n 个顶点的图，求所有顶点对之间的最短路径，若调用 Dijkstra 算法 n 次，其时
间复杂度为 O(n3)。Floyd 算法的时间复杂度也是 O(n2)。但 Floyd 算法更快，这是因为前者
每次调用 Dijkstra 算法时都是独立执行的，路径比较中得到的信息没有共享，而 Floyd 算法
中每考虑一个顶点时所得到的路径比较信息保存在 A 数组中，会用于下次的路径比较，从
而提高了整体查找最短路径的效率。
13、简述图有哪两种主要的存储结构，并说明各种存储结构在图中的不同运算（如图的遍历、
求最小生成树、最短路径等）中有什么样的优越性？
图的存储结构主要有邻接矩阵和邻接表。
（1）邻接矩阵：容易判定图中任意两个顶点之间是否有边相连，所以对于图的遍历是可行
的。同时特别方便提取一条边的权值，所以在求最小生成树和最短路径时采用邻接矩阵作为
存储结构。
（2）邻接表：容易找到任一顶点的所有邻接点，所以邻接表对于图的遍历也是可行的，
但要判断任意两个顶点 i 和 j 之间是否有边相连，则需搜索第 i 个及第 j 个单链表，这一点不
如邻接矩阵方便。
14、证明当深度优先遍历算法应用于一个连通图时遍历过程中所经历的边形成一棵树。
证明：由深度优先遍历算法可知，一个连通图中的每个顶点访问一次并且仅访问一次。在遍
历过程中，从一个顶点到另外一个顶点时必须经过连接这两个顶点的边。这样，当深度优先
遍历将图中的全部顶点都访问一次后共经过了其中 n-1 条边，而这 n-1 条边恰好把图中的 n
个顶点全部连通，即图的 n 个顶点和这 n-1 条边构成了图的一个连通分量。具有 n 个顶点和
n-1 条边的连通图为树。
15、有一个带权有向图如图所示，回答以下问题:
（1）给出该图的邻接矩阵表示。
（2）给出该图的邻接表表示。
答: （1）该图的邻接矩阵表示如下。
（2）该图的邻接表表示如下图所示。
16、对于一个顶点个数超过 4 的带权无向图，回答以下问题：
(1)该图的最小生成树一定是唯一的吗？如果所有边的权都不相同，那么其最小生成树一定
是唯一的吗?
(2)如果该图的最小生成树不是唯一的，那么调用 Prim 算法和 Kruskal 算法构造出的最小生成
树一定相同吗?
(3)如果图中有且仅有两条权最小的边，它们一定出现在该图的所有最小生成树中吗?简要说
明理由。
(4)如果图中有且仅有 3 条权最小的边，它们一定出现在该图的所有最小生成树中吗？简要
说明理由。
答：(1) 该图的最小生成树不一定是唯一的。如果所有边的权都不相同，那么其最小生成树
一定是唯一的。
(2)若该图的最小生成树不是唯一的，那么调用 Prim 算法和 Kruskal 算法构造出的最小生成树
不一定相同。
(3)如果图中有且仅有两条权最小的边，它们一定会出现在该图的所有最小生成树中。因为
在采用 Kruskal 算法构造最小生成树时首先选择这两条权最小的边加入，不会出现回路(严格
的证明可以采用反证法)。
(4)如果图中有且仅有 3 条权最小的边，它们不一定出现在该图的所有最小生成树中。因为
在采用 Kruskal 算法构造最小生成树时，选择这 3 条权最小的边加入有可能出现回路。例如，
如下图所示的带权无向图，有 3 条边的权均为 1，它们一定不会同时出现在其任何最小生成
树中。
17、对于如图所示的带权无向图，直接给出利用普里姆算法（从顶点 0 开始构造）
和克鲁斯卡尔算法构造出的最小生成树的结果（注意：按求解的顺序给出最小生
成树的所有边，每条边用(i，j)表示）。
答:利用 Prim 算法从顶点 0 出发构造的最小生成树为：
{(0,1),(0,3),(1,2),(2,5),(5,4)}, 利用克鲁斯卡尔算法构造出的最小生成树为{(0,1),(0,3),(1,2),(5,4),(2,5)}。
18、对于图所示的带权有向图，采用 Dijkstra 算法求从顶点 0 到其他顶点的最
短路径，要求给出求解过程，包括每一步的 S 集合、dist 和 path 数组元素。
答：该图对应的邻接矩阵如下：
在求最短路径时，S（存放顶点集），dist[]（存放最短路径长度）和 path[]（存
放最短路径）的变化如下：
最后得到的结果如下：
顶点 0 到顶点 1 的最短距离为 5，最短路径为：0、4、1
顶点 0 到顶点 2 的最短距离为 6，最短路径为：0、4、1、2
顶点 0 到顶点 3 的最短距离为 7，最短路径为：0、4、1、3
顶点 0 到顶点 4 的最短距离为 2，最短路径为：0、4。
19、对于如图所示的带权有向图，若采用 Dijkstra 算法求从顶点 a 到其他顶点
的最短路径和长度，第一条最短路径为：a->c，路径长度 2，则求得的剩余最短
路径依次是什么？（请按 Dijkstra 算法执行时产生最短路径的顺序，给出各最
短路径及其长度）。
答：第二条：a->c->f，长度为 6
第三条：a->c->e，长度为 10
第四条：a->c->f->d，长度为 11
第五条：a->c->f->d->g，长度为 14
第六条：a->b，长度为 15
20、一个含有 n 个互不相同的整数的数组 R[1..n]，其中所有元素是递减有序的，将其看成是
一棵完全二叉树，该树构成一个大根堆吗？若不是，请给一个反例，若是，请说明理由。
答案：该数组一定构成一个大根堆。 当 R 是递减时，其数组元素为 k1 、k2 、…、kn ，
从中看出下标越大的元素值越小，对于任一元素 ki ，有 ki >k2i ，ki >k2i+1 （i<n/2），
这正好满足大根堆的特性，所以构成一个大根堆。
21、简要回答下列关于堆排序中堆的一些问题：
（1）通常堆采用顺序还是链式存储结构？
（2）设有一个小根堆，即堆中任意结点的关键字均小于它的左孩子和右孩子的关键字。其
中具有最大关键字的结点可能在什么地方？
答：（1）通常堆采用顺序存储结构。
（2）小根堆中具有最大关键字的结点只可能出现在叶子结点中。因为最小堆的最小关键字
的结点必是根结点，而最大关键字的结点由偏序关系可知，只有叶子结点可能是最大关键字
的结点。
---
//层次遍历二叉树
BTNode* queue[60];
int head=-1,tail=-1;
queue[++tail]=root;//入队
while(!(head==tail)){
BTNode* p=queue[head+1];
head++;
printf("%c",p->data);
if(p->lchild) queue[++tail]=p->lchild;
if(p->rchild) queue[++tail]=p->rchild;
}
//归并排序
int mid = (low + high) >> 1;
MergeSort(a, low, mid);
MergeSort(a, mid + 1, high);
//合并
Merge(a, low, mid, high);
KMP
int next[10];
Next(T,next);//根据模式串T,初始化next数组
int i=1;
int j=1;
while (i<=strlen(S) && j<=strlen(T))
{
//j==0:代表模式串的第一个字符就和指针i指向的字符不相等；S[i-1]==T[j-1],如果对应位置字符相等，两种情况下，指向当前测试的两个指针下标i和j都向后移
if (j==0 || S[i-1]==T[j-1])
{
i++;
j++;
}
else
{
j=next[j];//如果测试的两个字符不相等，i不动，j变为当前测试字符串的next值
}
}
if (j>strlen(T))
{
//如果条件为真，说明匹配成功
return i-(int)strlen(T);
}
return -1;
//快速排序
//对数据元素a[low]~a[high]进行快速排序
int i = low, j = high;
int temp = a[low];
while (i<j)
{
//在右端扫描
while (i < j && temp < a[j])
j--;
if (i < j)
{
a[i] = a[j];
i++;
}
//在左端扫描
while (i < j && temp > a[i])
i++;
if (i < j)
{
a[j] = a[i];
j--;
}
}
a[i] = temp;
if (low < i)
QuickSort(a, low, i - 1);
if (high > i)
QuickSort(a, j + 1, high);
//矩阵深度优先遍历
visited[V] = 1;//访问过的顶点标记为1
printf("%2d", V);//在进行遍历之前打印访问的顶点
for (int j = 0; j < G->n; j++)//从第0个顶点开始判断，直到最后一个顶点
{
if (!visited[j] && G->edges[V][j] == 1)
//若顶点vexs[j]与顶点vexs[i]相连，并且vexs[j]没有访问过
{
DFS(G, j);//那就访问vexs[j]
}
}
//十转八进制
int x;
int i = 0;
while(a>=8)
{
x=a%8;
i++;
SS_Push(ss,x);
a=a/8;
}
SS_Push(ss,a);
int e;
for(int j = 0;j <= i;j++)
{
bool flag=SS_Pop(ss,e);
printf("%d",e);
}
//BF算法
int i=0,j=0;
while (i<strlen(B) && j<strlen(A)) {
if (B[i]==A[j]) {
i++;
j++;
}else{
i=i-j+1;
j=0;
}
}
//跳出循环有两种可能，i=strlen(B)说明已经遍历完主串，匹配失败；j=strlen(A),说明子串
//遍历完成，在主串中成功匹配
if (j==strlen(A)) {
return i-strlen(A)+1;
}
//运行到此，为i==strlen(B)的情况
return 0;
//删除链表结点
ListNode* cur = head;
int count = 0;
while(cur != NULL){
count++;
cur = cur->next;
}
//当倒数n个节点和链表长度相等时，需要特殊考虑。
if(count == k){
return head->next;
}
ListNode* fast = head;
ListNode* slow = head;
//fast多走的步数
while(k-1 > 0){
if(fast == NULL){
return NULL;
}
fast = fast->next;
k--;
}
//两个一起走找到K节点并且删除
ListNode* prev = NULL;
while(fast != NULL && fast->next != NULL){
prev = slow;
fast = fast->next;
slow = slow->next;
}
prev->next = slow->next;
return head;
//图的深度优先遍历
ArcNode* p;
printf("%d ", v);
visited[v] = 1;
p = G->adjlist[v].firstarc;
while (p != NULL)
{
if (visited[p->adjvex] == 0)
DFS(G, p->adjvex);
p = p->nextarc;
}
//图的广度优先遍历
ArcNode* p;
int graph_queue[MAXV], queue_front = 0, queue_rear = 0;
int visited[MAXV];
int i;
int adjvex;
for (i = 0; i < G->n; i++)
{
visited[i] = 0;
}
printf("%d ", v);
visited[v] = 1;
queue_rear = (queue_rear + 1) % MAXV;
graph_queue[queue_rear] = v;
while (queue_front != queue_rear)
{
queue_front = (queue_front + 1) % MAXV;
adjvex = graph_queue[queue_front];
p = G->adjlist[adjvex].firstarc;
while (p != NULL)
{
if (visited[p->adjvex] == 0)
{
printf("%d ", p->adjvex);
visited[p->adjvex] = 1;
queue_rear = (queue_rear + 1) % MAXV;
graph_queue[queue_rear] = p->adjvex;
}
p = p->nextarc;
}
}
printf("\n");
//前中构造二叉树
if(i1>i2 && p1>p2)
return NULL;
BTNode* BTP=(BTNode*)malloc(sizeof(BTNode));
char* p;
BTP->data=*pa;
int k;
for(p = ia ; p< ia + (i2-i1) ; p++){//找到根节点
if(*p == *pa) break;
}//此时p在中序中根节点位置
//因为是char 大小为1 地址相减
k = p-ia;//k为根节点在in中位置
//小于k的部分为左子树 大于k的为右子树
BTP->lchild = InPreToTree(pa+1, ia, p1+1, p1+k, i1, i1+k-1);
BTP->rchild = InPreToTree(pa+k+1, ia+k+1, p1+1+k, p2, i1+k+1, i2);
return BTP;
//中后构造二叉树
char r= *(post+n-1),*p;//最后一个为根节点
if(n<=0)return NULL;
BTNode* BT=(BTNode*)malloc(sizeof(BTNode));
BT->data=r;
for(p=in;p<in+n;p++)
{
if(*p==r)
break;
}//p为中序中根节点位置
int k=p-in;//k更新左子树长度
BT->lchild=InPostToTree(post,in,k);
BT->rchild=InPostToTree(post+k,in+k+1,n-k-1);
return BT;
Comments NOTHING