北京工业大学计算机896数据结构考研真题答案2.pdf

北京工业大学数据结构考研题解答 2010 年算法设计 1. 递归计算二叉树的高度。 【解析】没有太大难度，辅导时讲过的。递归程序注意先写好递归终止条件。 intint BinTreeHighBinTreeHigh(BTree tree) ifif(tree=NULL) returnreturn 0; elseelse intint L = BinTreeHigh(tree-lchild); intint R = BinTreeHigh(tree-rchild); returnreturn 1 + (LR ? L : R); / 1 + maxL, R 2. 荷兰国旗问题。 【解析】思路类似快速排序的一趟划分算法。要想按红白蓝顺序排列，只要扫描整个序列， 遇到红色交换到前面，遇到蓝色交换到后面，设置两个变量，分别记录前面和后面两个子序 列的位置。 （也可以想象在序列的前后两端各有一个栈。 ） i,k =323132311332= j k=3 交换kj, j- i,k= 22313231133= j 3 k=2 跳过：k+ i =2 k= 2313231133= j 3 k=2 跳过：k+ i =22 k=313231133= j3 k=3 交换kj, j- i =22 k=31323113= j 33 k=3 交换kj, j- i =22 k=3132311= j333 k=3 交换kj, j- i =22 k=113231= j3333 k=1 交换ki, i+, k+ (这里k+防止i=k时死循环) 1i =22 k=13231= j3333 k=1 交换ki, i+, k+ 11i =22 k=3231= j3333 k=3 交换kj, j- 11i =22 k=123= j33333 k=1 交换ki, i+, k+ 111i =2 2k=23= j33333 k=2 跳过：k+ 111i =222k=3= j33333 k=3 交换kj, j- (k=j 时还要继续循环) 111i =222= j k=333333 kj 结束 【参考解答】设红、白、蓝分别用 1、2、3 表示。序列为线性结构，故采用线性表作为数据 结构，针对该问题选择 n 个元素的数组作为线性表的存储结构。算法如下： / 将 n 个红、白、蓝元素（分别用1、2、3表示）组成的序列 / 按照红、白、蓝的顺序排列 voidvoid ArrangeArrange(intint a, intint n) intint i = 0; / 从前向后保存红色（1）元素 intint j = n-1; / 从后向前保存蓝色（3）元素 intint k = 1; whilewhile(k=j) ifif(ak=1) intint t=ak; ak=ai; ai=t; / 交换ak和ai i+; k+; / 注意：这里k+防止i=k时陷入死循环 elseelse ifif(ak=3) intint t=ak; ak=aj; aj=t; / 交换ak和aj j-; elseelse k+; 【补充】 对于数据结构， 最简单就是用数组表示线性表。 如果非要复杂一点， 可以用顺序表。 【参考解答】设红、白、蓝分别用 1、2、3 表示。序列为线性结构，故采用线性表作为数据 结构，针对该问题特点选择顺序表作为线性表的存储结构。算法如下： / 顺序表最大容量 constconst intint MAX_SIZE = 1024; / 顺序表结构 typedeftypedef structstruct intint elemMAX_SIZE; intint length; SqList; / 将 n 个红、白、蓝元素（分别用1、2、3表示）组成的序列 / 按照红、白、蓝的顺序排列 voidvoid ArrangeArrange(SqList / 从前向后保存红色（1）元素 intint j = L.length-1; / 从后向前保存蓝色（3）元素 intint k = 1; whilewhile(k=j) ifif(L.elemk=1) intint t=L.elemk; L.elemk=L.elemi; L.elemi=t; / 交换k和i i+; k+; / 注意：这里k+防止i=k时陷入死循环 elseelse ifif(L.elemk=3) intint t=L.elemk; L.elemk=L.elemj; L.elemj=t; / 交换k和j j-; elseelse k+; 2011 年算法设计 1、冒泡排序。 【解析】本题考查冒泡排序，采用顺序表作为存储结构。要做到一旦发现待排记录有序就立 即停止排序，只要在每趟排序过程中检查是否有交换发生，如果某一趟排序结束后，没有发 生交换，则可以断定待排记录已经有序，则可以结束排序。 本题难度不大，但要特别注意以下细节： （1）待排记录用顺序表存储，且 r0空闲，这意味 着待排序列为 L.r1.n（n 代表 L.length） ； （2）题目给定了数据结构，在算法中必须使用该 数据结构。如比较记录的大小时，应该比较记录的关键字 key。 （3）排序过程中，不要造成 下标越界。 如： i 从 1 循环到 n-1， 表示最多需要 n-1 趟排序， 内层循环中 j 要从 1 循环到 n-i， 相当于 jn-i+1，才能保证不会出现下标越界。可以用边界值验证法加以验证。如当 i=1 时， 内循环中 j 取 1 到 n-1，这样才能保证下面 j+1 最大为 n，从而保证 rj+1不会下标越界。 【参考解答】 / 对顺序表L.r1.n冒泡非递减排序 / 一旦待排序列有序排序过程立即停止 voidvoid BubbleSort(SqList iL.length; i+) boolbool changed = falsefalse; / 一趟排序中是否发生交换 forfor(intint j=1; j L.rj+1.key) / 比较关键字，逆序则交换 L.r0 = L.rj; L.rj = L.rj+1; L.rj+1 = L.r0; changed = truetrue; / 置发生交换的标志 ifif(!changed) breakbreak; / 没有交换发生，表明已经有序，停止排序 2、利用图的遍历判断连通图中是否存在回路。 【解析】与图的路径相关的问题，一般采用深度优先搜索。 但是，这个题目本身似乎有些问题。 （1）如果这个连通图是无向图，只要图中有边存在，那么像 A-B-A 这样的回路必然存在， 所以这似乎已经不是个问题了。 （2） 如果这个图是一个强连通图，则必然存在经过所有顶点的一条路径，也必然存在回路， 所以也不能算是问题了。 只能认为题目中所说的是弱连通图弱连通图 （即如果将有向图中的弧当成边 ， 则改图一定是连通图） 。 对于弱连通图，还要注意下面几个问题： （1）从图中某个顶点出发，可能存在遍历不到的顶点（如下图中顶点 F）。所以，即使从 某个顶点出发，遍历过程中没有发现回路，也不能断定整个图中没有回路，有必要从不同的 顶点开始遍历。 （2）也不能单纯地认为，在遍历过程中遇到已经访问过的顶点，就表明图中存在回路。比 如，假如去掉下图中的弧 EB，并且从 A 开始深度优先遍历，如果遍历序列为 ABCEFGD，那么， 在访问完 D 之后，遇到了已经访问过的顶点 E，但这并不意味着图（已删除弧 EB）中存在回 路。所以在设置访问标志的方式上要进行修改，即：访问顶点时设置访问标志，当从该顶点 遍历完成返回时要清除访问标志，其目的是，让设置访问标志的顶点仅出现在一条路径中， 从而保证一旦遇到访问过的顶点，必然存在回路。 【参考解答】 如果在遍历过程中遇到同一同一条条遍历路径上遍历路径上已经访问过的顶点， 则表明图中存在 回路。 constconst intint VEX_MAX = 100; / 图中最大顶点数 intint visitedVEX_MAX; / 同一条遍历路径上顶点的访问标志 / 从顶点v出发深度优先搜索图G，判断图中是否存在回路 boolbool existCyclePathexistCyclePath(Graph G, intint v) / 访问顶点v visitedv = 1; / 置访问标志 / 遍历v的邻接点w forfor(w=FirstAdjVex(G,v); w!=NULL; w=NextAdjVex(G,v,w) / 如果w已访问过，必存在回路，直接返回（无需继续遍历） ifif(visitedw) return truereturn true; A B C D E F G / 如果从w出发，发现回路，则返回（无需继续遍历） ifif(existCyclePath(G, w) return truereturn true; / 已遍历完v的所有邻接点，未发现回路，从顶点v返回 visitedv = 0; / 清除访问标志 returnreturn false; / 未发现回路 【补充】 往届学生问过这个题目， 参见教学网站上的另一种解答 （用邻接矩阵实现） （提示： Ctrl+单击链接，校园网内可以访问教学网站） 。 3、稀疏一元多项式。 【解析】本题以稀疏一元多项式为应用背景，考查数据结构、存储结构设计相关知识。多项 式可以看作是线性结构， 可以用线性表来表示， 由于稀疏多项式的特殊性， 考虑空间利用率， 可以选择链表作为存储结构。多项式的运算通常都是按指数大小顺序处理，所以，具体地， 可以采用按指数排序的单链表作为存储结构。链表中每个结点表示一元多项式中的一个项， 每一项都要包含系数和指数， 从而可以用一个链表表示一个一元多项式。 其存储结构定义应 包括结点（项）的定义和链表（多项式）的定义。 当然，完全可以参考课本第二章给出的同样的例子加以解答，但是，本试题绝不是要求背诵 课本内容，应根据所学知识独立地进行设计，课本上的内容仅仅当做一种模糊的提示。 另外，考试过程中时间紧张，对于各种符号和名称不必过于纠结，只要简化地给出即可。比 如：系数 coefficient，指数 exponent，多项式 polynomial，都可以简化给出，系数用 coeff 或 c，指数用 exp 或 e，多项式用 Poly 甚至 P，都不是什么大问题。 【参考解答】一元多项式可以看作现行结构，故采用线性表作为数据结构。由于稀疏一元多 项式中存在很多零元，所以适合采用链表作为存储结构，以提高空间利用率。一元多项式的 运算通常按照各项指数的大小顺序处理， 所以， 可以采用按指数升序排列的单链表作为存储 结构。定义如下： / 一元多项式的项，作为链表数据元素 typedeftypedef structstruct ItemType doubledouble coef; / 系数 intint exp; / 指数 ItemType, ElemType; / 单链表 typedeftypedef structstruct LNode ElemType data; structstruct LNode *next; LNode, *LinkList; / 一元多项式类型 typedeftypedef LinkList Polynomial; 2012 年算法设计 1、调整序列，负整数在前，正整数在后。 【解析】算法思路非常类似快速排序一趟划分算法，只不过，为了区分正整数和负整数，应 该让序列中的元素与 0 比较。 另外，题目对时间复杂度和空间复杂度都有要求。因此，不能采用一般的排序算法。 【参考解答】 / 调整顺序表L中的元素，使负整数在前，正整数在后 voidvoid adjustadjust(SqList intint j = L.size-1; whilewhile(ij) whilewhile(i0) j-; whilewhile(ileft; p-left = B; 3、地铁换乘系统设计。 【解析】本题目以地铁换乘问题为应用背景，考查数据结构的应用能力。在答题过程中要紧 扣问题的应用背景，选择合理的数据结构和存储结构，只要言之有理，允许存在多种解决方 案，不一定是唯一的。 每条地铁线路有很多站点， 多条地铁线路可能会经过同一个站点以便换乘不同地铁线路。 要 解决的问题是， 输入起点和终点， 给出地铁的换乘方案。 可以转化为在图中搜索路径的问题。 涉及的数据主要是站点以及站点间距离， 采用图作为数据结构。 如果采用邻接矩阵作为存储 结构，该图非零（非无穷）元素比较少，适合采用邻接表作为存储结构。 【参考解答】 （1）本问题主要涉及地铁站点以及站点间的连通关系（或距离）等数据。 （2）考虑到每条地铁线路有很多站点，多条地铁线路可能会经过同一个站点，站点之间的 关系比较复杂，因此，应该选用图为其数据结构。 （3）图的存储结构通常有两种：邻接矩阵和邻接表。因为，一般情况下，对于大多数地铁 站，与其相邻的站点往往只有两个。因此，如果采用邻接矩阵作为存储结构，由于非零元素 比较少，会导致存储空间的浪费。所以，应采用邻接表作为图的存储结构。 如果进一步考虑查询换乘操作更加方便， 可以将从某站点出发不换乘即可到达的所有站点都 看作是该站点的邻接点。在这种情况下，如果地铁线路较少，如只有一两条线路，也可以采 用邻接矩阵作为存储结构。如地体线路较多，采用邻接矩阵仍然存在较大的空间浪费，这种 情况下，还是应该采用邻接表作为存储结构。 2013 年数据结构 一、单选 1-5. CDABC 6-10. BAABC 【解析】 1. 选项 D 指的是具体的数据类型。 2. 选项 A：一般情况下，算法的时间复杂度是问题规模的函数，不可能是无关的。选项 B、 C 明显错误。选项 D：算法的时间复杂度只考虑问题的规模，不考虑程序设计语言。 4. 三元组顺序表的快速转置算法，首先计算转置后每一行的起始位置（包括按转置后的行 数 n 初始化位置计数器 O(n)，统计每行元素个数 O(t)，计算每行起始位置 O(n)） ，然后逐个 元素转置 O(t)。总的时间复杂度为 O(n+t)。 6. 456=255+201（最后一层）=127+128（倒数第二层）+201（最后一层） ，最后一层有 201 个结点。201/2=1001，故倒数第二层有 100 个度为 2 的结点和 1 个度为 1 的结点，以及 128-100-1=27 个叶子结点。所以，度为 2 的结点数为 127+100=227，叶子结点为 201+27=228 个。 实际上，根据二叉树的性质，叶子结点数等于度为 2 的结点数加 1，只有选项 B 符合这一性 质，故而可以排除选项 A 和 C。根据题意，给定完全二叉树的结点数，该完全二叉树的结构 可以唯一确定，也可以排除选项 D。 7. 更准确地说，生成树中没有简单简单回路。相比之下，B、C、D 错误明显。 9. 堆排序是选择排序方法的一种，堆的作用主要是充分利用元素之间的大小关系，在选择 最大（最小）元素时减少比较次数。 10. 归并排序是稳定的。简单选择排序是不稳定的，例如(2,2,1)，经过简单选择排序得到的 结果是(1,2,2)，是不稳定的。 二、填空 1. 算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的 2. 在链式存储结构中插入和删除操作不需要移动元素 3. LOC(0,0)+(in+j) L 4. 为了保证在任何位置上都能沿原路返回，换下一个位置继续搜索 5. 4 6. 顶点 V1在 V2前面 7. 连接后的字符串长度超过了定长顺序存储允许的最大长度 8. 关键字的集合要远远大于地址集合，很难避免“冲突” 9. 堆可以映射为一个完全二叉树 10. 减少最坏情况发生的可能性，提高快速排序的效率 【解析】 5. 可以根据先序和中序序列画出二叉树，然后转化为对应的森林。但是，注意到，为了确 定森林中树的数目，只要分析对应二叉树根结点的右孩子，右孩子的右孩子，以此类推。左 子树可以忽略。如题，忽略根的左子树可以得到先序序列 AXCFIM，中序序列 XACFMI，画出 这棵二叉树（如下图） ，可知对应的森林有 4 棵树。 三、解答题 1. 广义表。 【解析】题目考查广义表基本概念及其类型定义。对于广义表的类型定义，不必死记硬背， 关键是理解。广义表的内容存储在结点中，结点有两种类型：原子结点和子表结点，原子结 点要保存具体数据，必须有数据域（类似链表中的 data 域） 。而子表通常用表头和表尾来表 示，在存储结构中用头、尾两个指针（类似链表中的 next 指针域）来实现。对于一个具体 的结点，要么是原子结点，要么是子表结点，二者必居其一。为了充分利用存储空间，可以 让原子结点和子表结点通过 union 类型共享空间。原子和子表共享空间之后，必须要有办法 区分一个结点到底是原子还是子表， 这就有必要在结点结构中增加一个标志， 访问结点的内 容时，首先判断这个标志，确定该结点的类型是原子还是子表。如果结点的类型是原子，则 可以访问 union 中原子结点的数据域。反之，如果结点类型是子表，则可以访问 union 中子 表的表头、表尾两个指针。理解了广义表结点的结构，其类型定义也就不难给出了。 另外，因为 union 并不常用，但也不必纠结于其中的细节。换个角度，如果没有用 union， 在类型定义中“错误”地写成了 struct，也没有什么了不起。只不过是每个结点中既包含了 原子结点的数据， 也包含了子表的头、 尾指针， 而我们只能根据类型标志使用其中的一部分， 另一部分“闲置” ，浪费了一点存储空间而已。换成 union 之后，也只不过是（按原子结点 和表结点两者中所需空间最大的那个）分配“一块”空间，由两者中的一个来使用罢了。 【参考解答】 （1）广义标的长度描述了目录的章节数，广义标的深度描述了目录的最大层次数。 （2）广义表中的子表对应目录中的章，原子对应目录中的小节。 （3）广义表的存储结构如下： / 区分原子与子表的标志 typedeftypedef enumenum ATOM, LIST GLNodeTag; / 广义表类型定义 typedeftypedef structstruct GLNode GLNodeTag tag; / 结点类型标志 unionunion / 原子结点和子表结点的联合 AtomType data; / 原子结点 structstruct GLNode *hp; / 表头指针 GLNode *tp; / 表尾指针 ptr; / 子表结点包括表头、表尾指针 ; GLNode, *GList; / 广义表结点和广义表类型 2. 树和二叉树。 【解析】题目考查树和二叉树的关系。 【参考解答】 （1）用孩子-兄弟链表表示树，容易将树形结构转换为二叉树，同时，树中访问孩子和兄弟 A C X F I M 等各种操作也容易实现。 （2）对于树中给定结点，其子孙结点位于二叉树中对应结点的左子树上。如下图，树中结 点 B 的子孙在对应二叉树中为 B 的左子树。 （3）对于树中给定结点，其下一个兄弟结点是二叉树中对应结点的右孩子。如上图，树中 结点 B 的下一个兄弟 C，在对应二叉树中正好是 B 的右孩子。 3. 最短路径。 【解析】题目考查邻接矩阵、最短路径等知识。画图时，将顶点围成一圈，任何边画起来都 很方便。题目只要求最短路径结果，因此可以直接在图上计算求得。 【参考解答】 （1）根据图 G 的邻接矩阵可以画出该图如下： （2）从顶点 1 到顶点 7 共有 5 条路径，例如：路径 1257 长度 30，路径 1367 长度 14，路径 147 长度 15。 （3） 用迪杰斯特拉算法求得顶点1到顶点7的最短路径是1367 （或13647） ， 路径长度为 14。 4. 二叉排序树。 【解析】题目考查二叉排序树、平衡化、查找长度等相关基础知识。 【参考解答】 （1）构造二叉排序树如下图(a)。 （2）构造平衡二叉排序树如上图(b)。 A B C D E F A B C D E F 1 2 3 4 5 6 7 8 15 2 12 6 8 4 3 9 5 39 26 10 17 12 38 60 19 48 7 40 39 10 38 17 40 26 60 7 48 (a) (b) 19 12 （3） 等概率情况下， 所构建的二叉排序树的平均查找长度为： (1+2*2+3*3+4*3+5+6)/11=37/11。 所构建的平衡二叉排序树平均查找长度为：(1+2*2+3*4+4*4)/11=33/11=3。 5. 哈希表。 【解析】题目考查哈希表造表、查找、查找长度等基础知识。 【参考解答】 （1）41,30,52 （2）41,42,32,21,30 （3）(1+1+2+1+1+1+1+5+8)/9=21/9=7/3 四、阅读算法 【解析】该算法整体上对二叉树进行中序非递归遍历，在访问结点时，复制结点中的数据， 插入到链表表头（逆向建表） 。故算法结束后，链表中的元素为中序遍历结果的逆序排列。 【参考解答】 （1） （2）单链表 H 中每个结点的链接顺序与二叉树中序遍历的顺序正好相反。 （3）如果所给二叉树是二叉排序树，单链表 H 中结点数据按降序排列。 五、算法设计 1. 计数排序 【解析】题目中已经把计数排序的思路描述得比较清楚，不再赘述。注意计数值与排序位置 的关系。该算法时间复杂度为 O(n2)。 【参考解答】 （1）