1、软件设计师-数据结构与算法(二)及答案解析(总分：43.00，做题时间：90 分钟)1.在下面几个符号串编码集合中，不是前缀编码的是_。（分数：1.00）A.0,10,110,101B.(00,10,010,110,1110)C.00,010,0110,1000)D.(b,c,aa,ac,aba,abb,abc)堆排序是一种基于 (1) 的排序方法， (2) 不是堆。（分数：2.00）A.计数B.插入C.选择D.归并A.15，28，25，56，68，63，30B.15，28，25，30，68，63，56C.68，28，63，25，15，56，30D.68，56，39，63，28，25，152.
2、某工程计划图如图 3-68 所示，弧上的标记为作业编码及其需要的完成时间(天)，那么，作业 E 最迟应在第_天开始。（分数：1.00）A.7B.9C.12D.133._的特点是数据结构中元素的存储地址与其关键字之间存在某种映射关系。（分数：1.00）A.树形存储结构B.链式存储结构C.索引存储结构D.散列存储结构4.一个具有 n(n0)个顶点的连通无向图至少有_条边。（分数：1.00）A.n+1B.nC.D.n-15.如果只想得到 5000 个元素组成的序列中最小的 20 个元素序列，用_方法最合适。（分数：1.00）A.简单选择排序B.Shell 排序C.堆排序D.冒泡排序6.具有 n 个结
3、点的二叉树，采用二叉链表存储，共有_个空链域。（分数：1.00）A.n-1B.nC.n+1D.由于二叉树形态不定导致空链域个数不定7.对于任何一棵非空的二叉树，假设叶子接点的个数为 n0，而度数为的 2 的结点个数为 n2，用 n2=f(n0)来表示两者的关系，那么 f(99)的值为_。（分数：1.00）A.98B.99C.100D.1018.具有 n 个结点且互不相似的二叉树的总数是_。（分数：1.00）A.B.C.D.在下列算法设计方法中， (1) 在求解问题的过程中并不从整体最优上加以考虑，而是做出在当前看来是最好的选择。利用该设计方法可以解决 (2) 问题（分数：2.00）A.分治法B
4、.贪心法C.动态规划法D.回溯法A.排序B.检索C.背包D.0-1 背包9.已知某二叉树的后序遍历序列是 DABEC，中序遍历序列是 DEABC，它的前序遍历序列是_。（分数：1.00）A.ABCEDB.CEDBAC.DEABCD.DECAB10.利用逐点插入法建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，查找元素 30 要进行_次元素间的比较。（分数：1.00）A.4B.5C.6D.711.无向图中一个顶点的度是指图中_。（分数：1.00）A.通过该顶点的简单路径数B.通过该顶点的回路数C.与该顶点相邻的顶点数D.与该顶点连通的顶点数12.设下三
5、角矩阵 A： 如果以行序为主序将 A 的非零元素存储在一维数组 Bn(n+1)/2中，那么 A 的第 i 行第 j 列的非零元素aij(ij)在数组 B 中的下标为_。（分数：1.00）A.B.C.D.13.树的后序遍历序列等同于该树对应的二叉树的_。（分数：1.00）A.先序序列B.中序序列C.后序序列D.不确定14.若广义表 L=(1，2，3)，则 L 的长度和深度分别为_。（分数：1.00）A.1 和 1B.1 和 2C.1 和 3D.2 和 215.已知二叉树有 50 个叶子结点，则该二叉树的总结点数至少是_。（分数：1.00）A.96B.99C.100D.11316.一棵树高为 k
6、的完全二叉树至少有_个结点。（分数：1.00）A.2k-1B.2k-1-1C.2k-1D.2k17.下面有关线性表的叙述中，错误的是_。（分数：1.00）A.线性表采用顺序存储，必须占用一片连续的存储单元。B.线性表采用顺序存储，便于进行插入和删除操作。C.线性表采用链接存储，不必占用一片连续的存储单元。D.线性表采用链接存储，便于插入和删除操作。18.关于满二叉树、完全二叉树有以下说法：满二叉树不仅是一种特殊形态的二叉树，而且是一种特殊的完全二叉树。具有 n 个结点的满二叉树的高度为 +1。具有 n 个结点的完全二叉树的高度为 +1。具有 n 个结点的满二叉树的高度为 log2(n+1)。具
7、有 n 个结点的满二叉树共有叶子结点 （分数：1.00）A.B.C.D.全对19.在非空双向循环链表结点中，prior 域指向该结点的直接前驱，next 域指向直接后续，那么在 q 所指的结点后面插入 p 所指的结点的过程为_。（分数：1.00）A.qnext=p；pprior=q；qnextprior=p；pnext=qnext。B.pnext=qnext；qnext=p；qnextprior=p；pprior=q。C.pprior=q；pnext=qnext；qnext=p；qnextprior=p。D.pnext=qnext；qnextprior=p；pprior=q；next=p。20
8、.假设根结点的层数为 1，并设具有 n(n3)个结点的二叉树的最大高度为 h，设达到最大高度 h 时，不同的二叉树的数目为 m。有以下说法：hn h=log 2n+1 m=1 m=2 m=2 n-1其中正确的个数有_个。（分数：1.00）A.1B.2C.3D.421.已知一算术表达式的中缀形式为(A+B)*C-D/E，其前缀形式为_。（分数：1.00）A.-*A+BC/DEB.-*+ABC/DEC.-*+BAC/DED.-*AB+C/DE22.若采用邻接矩阵来存储简单有向图，则其某一个顶点 i 的人度等于该矩阵_。（分数：1.00）A.第 i 行中值为 1 的元素个数B.所有值为 1 的元素总
9、数C.第 i 行及第 i 列中值为 1 的元素总个数D.第 i 列中值为 1 的元素个数23.关于哈夫曼树、最优二叉树、哈夫曼算法，有以下说法：最优二叉树的形态不唯一，但是其 WPL 值是唯一确定的。哈夫曼树一定是最优二叉树，但最优二叉树不一定由哈夫曼算法来构造。则_。（分数：1.00）A.正确错误B.错误正确C.都对D.都错24.关键路径是指 AOE(Activity On Edge)网中_。（分数：1.00）A.最长的回路B.最短的回路C.从源点到汇点(结束顶点)的最长路径D.从源点到汇点(结束顶点)的最短路径在数据压缩编码的应用中，哈夫曼(Huffman)算法可以用来构造具有 (1) 的
10、二叉树，这是一种采用了 (2) 的算法。（分数：2.00）A.前缀码B.最优前缀码C.后缀码D.最优后缀码A.贪心B.分治C.递推D.回溯25.对于二维数组 a0 4,1 5，设每个元素占 1 个存储单元，且以列为主序存储，则元素 a2,2相对于数组空间起始地址的偏移量是_。（分数：1.00）A.5B.7C.10D.1526.算法是对问题求解过程的一类精确描述，算法中描述的操作都是可以通过已经实现的基本操作在限定时间内执行有限次来实现的，这句话说明算法具有_特性。（分数：1.00）A.正确性B.确定性C.可行性D.健壮性27.一棵二叉树的前序遍历序列为 ABCDEFG，它的中序遍历序列可能是_
11、。（分数：1.00）A.CABDEFGB.ABCDEFGC.DACEFBGD.ADBCFEG28.先序遍历能得到 ABC 序列的不同二叉树的最大个数为_。（分数：1.00）A.4B.5C.6D.729.关于森林的遍历有以下说法：森林的先序遍历等同于其对应的二叉树的先序遍历。森林的中序遍历等同于其对应的二叉树的中序遍历。森林的后序遍历等同于其对应的二叉树的后序遍历。森林的后序遍历等同于其对应的二叉树的中序遍历。其中正确的是_。（分数：1.00）A.B.C.D.30.一个含有 n 个顶点和 e 条边的简单无向图，在其邻接矩阵存储结构中共有_个零元素。（分数：1.00）A.eB.2eC.n2-eD.
12、n2-2e一般情况下，将递归程序转化成为非递归程序应该设置 (1) ，但是消除 (2) 时不需要使用。（分数：2.00）A.堆栈B.队列C.堆栈或队列D.数组A.直接递归B.间接递归C.尾递归D.递推某带权有向图如图 3-67 所示。（分数：5.00）A.V1、V 2、V 3、V 4、V 6、V 5、V 7、V 8B.V1、V 3、V 5、V 2、V 4、V 6、V 7、V 8C.V1、V 2、V 3、V 4、V 5、V 6、V 7、V 8D.V1、V 2、V 3、V 5、V 6、V 4、V 7、V 8A.1B.2C.3D.4A.15B.16C.17D.18A.5B.9C.10D.7A.12、
13、12B.12、13C.13、12D.13、13软件设计师-数据结构与算法(二)答案解析(总分：43.00，做题时间：90 分钟)1.在下面几个符号串编码集合中，不是前缀编码的是_。（分数：1.00）A.0,10,110,101 B.(00,10,010,110,1110)C.00,010,0110,1000)D.(b,c,aa,ac,aba,abb,abc)解析：对字符集进行编码时，要求字符集中任一字符的编码都不是其它字符的编码的前缀，这种编码称为前缀(编)码。A 的编码中，编码 10 是编码 101 的前面一部分，即是其前缀，因此不是前缀编码。堆排序是一种基于 (1) 的排序方法， (2)
14、不是堆。（分数：2.00）A.计数B.插入C.选择 D.归并解析：A.15，28，25，56，68，63，30B.15，28，25，30，68，63，56C.68，28，63，25，15，56，30D.68，56，39，63，28，25，15 解析：略。2.某工程计划图如图 3-68 所示，弧上的标记为作业编码及其需要的完成时间(天)，那么，作业 E 最迟应在第_天开始。（分数：1.00）A.7B.9C.12D.13 解析：该工程计划图其实就是 AOE 网，边(弧)表示活动(作业)。在 AOE 网中，从源点到汇点最长的路径称为关键路径。设关键路径长度为 K，从某顶点到汇点的最长路径为 M，那么
15、该顶点的最迟开始时间就是 K-M。某活动对应的弧的顶点的最迟开始时间减去该活动的持续时间就是该活动的最迟开始时间。该题中，从源点 1 到汇点 6 的最长路径为 123456，长度为 20。顶点 5 的最迟开始时间显然为20-3=17，那么活动 E 的最迟开始时间就为 17-4=13。3._的特点是数据结构中元素的存储地址与其关键字之间存在某种映射关系。（分数：1.00）A.树形存储结构B.链式存储结构C.索引存储结构D.散列存储结构 解析：4.一个具有 n(n0)个顶点的连通无向图至少有_条边。（分数：1.00）A.n+1B.nC.D.n-1 解析：在无向图中如果任意两点是可达的，则我们称其为
16、连通无向图。要把这 n 个顶点连通，可以让一个顶点向其它所有顶点连一条边，这样需要 n-1 条边，如图 3-75 所示。*此外，我们还可以让这 n 个结点首尾相接，这样也需要 n-1 条边，如图 3-76 所示。*所以至少需要 n-1 条边。5.如果只想得到 5000 个元素组成的序列中最小的 20 个元素序列，用_方法最合适。（分数：1.00）A.简单选择排序B.Shell 排序C.堆排序 D.冒泡排序解析：冒泡排序与简单选择排序均需要进行 20 趟排序，才能找到题目所求的序列；Shell 排序只有将这5000 个元素全部排序完成，才能找到题目所求的序列，因此排除 Shell 排序；堆排序需
17、要先建立初始堆后，再经过 20 次堆调整才能得到。冒泡排序、简单选择排序和堆排序这三种排序方法中堆排序的时间复杂度最小，所以选堆排序最合适。6.具有 n 个结点的二叉树，采用二叉链表存储，共有_个空链域。（分数：1.00）A.n-1B.nC.n+1 D.由于二叉树形态不定导致空链域个数不定解析：当采用二叉链表存储时，每个结点有两个指针域，分别指向左右子树的根结点，当有 n 个结点时共有 2n 个指针，又因为除根结点外每个结点都需要一个指针指向自己，所以就剩下 2n-(n-1)=n+1 个空链域。7.对于任何一棵非空的二叉树，假设叶子接点的个数为 n0，而度数为的 2 的结点个数为 n2，用 n
18、2=f(n0)来表示两者的关系，那么 f(99)的值为_。（分数：1.00）A.98 B.99C.100D.101解析：根据二叉树的性质，显然 n0=n2+1，所以有 n2=n0-1，从而 f(99)=99-1=98。8.具有 n 个结点且互不相似的二叉树的总数是_。（分数：1.00）A. B.C.D.解析：两棵树相似指的是形态一样，不考虑对应结点上的数据元素是否相同。具有 n 个结点但互不相似的树的数目为*。可以用特值法来验证。在下列算法设计方法中， (1) 在求解问题的过程中并不从整体最优上加以考虑，而是做出在当前看来是最好的选择。利用该设计方法可以解决 (2) 问题（分数：2.00）A.
19、分治法B.贪心法 C.动态规划法D.回溯法解析：A.排序B.检索C.背包 D.0-1 背包解析：贪心法是这样的一种解题方法：逐步给出解的各部分，在每一步“贪婪地”选择最好的部分解，但不顾及这样选择对整体的影响，因此一般得到的不是最好的解。解决背包问题描述：有不同价值、不同重量的物品 n 件，求从这 n 件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。解决背包问题较有效的方法一般用递归和贪婪法，而当背包问题的规模不是很大时，也可采用穷举法。9.已知某二叉树的后序遍历序列是 DABEC，中序遍历序列是 DEABC，它的前序遍历序列是_。（分数：1
20、.00）A.ABCEDB.CEDBA C.DEABCD.DECAB解析：由二叉树的后序遍历可以确定该二叉树的根结点(序列的最后一个结点)，在中序序列中该根结点将中序序列分为两部分，左边为其左子树的结点，右边为其右子树的结点，递归地操作下去便可以构造出这棵二叉树，如图 3-74 所示。*因此其前序遍历为：CEDBA。10.利用逐点插入法建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，查找元素 30 要进行_次元素间的比较。（分数：1.00）A.4B.5 C.6D.7解析：首先，根据给出的结点建立排序二叉树，如图 3-77 所示。*从该图中可以看出，30
21、 首先要与 50 比较，3050，所以进入结点 50 的左子树；接着与 43 比较，3043，所以进入结点 43 的左子树；然后与 20 比较，3020，所以进入结点 20 的右子树；再和 35 比较，3035，所以进入结点 35 的左子树；最后与 30 比较，结果相等，查找结束，所以此查找过程要进行 5 次比较。11.无向图中一个顶点的度是指图中_。（分数：1.00）A.通过该顶点的简单路径数B.通过该顶点的回路数C.与该顶点相邻的顶点数 D.与该顶点连通的顶点数解析：略。12.设下三角矩阵 A： 如果以行序为主序将 A 的非零元素存储在一维数组 Bn(n+1)/2中，那么 A 的第 i 行
22、第 j 列的非零元素aij(ij)在数组 B 中的下标为_。（分数：1.00）A.B. C.D.解析：按行优先存储就是把矩阵中的数据一行一行地顺次存入存储单元，此题中就按a11、a 21、a 22、a 31、a 32、a 33、a n1、a n2、a n3、a nn的顺序来存储。从第 1 行到第 i-1 行(a 11a i-1，i-1 )共有*个非零元素；在第 i 行，从 ai1至 aij共有 j 个非零元素，因此a11至 aij共有*个非零元素，而 a11对应的下标为 0，于是 aij对应的下标为*。13.树的后序遍历序列等同于该树对应的二叉树的_。（分数：1.00）A.先序序列B.中序序列
23、 C.后序序列D.不确定解析：树的后序遍历是指先依次后序遍历每棵子树，然后访问根结点。当树用二叉树表示法(也叫孩子兄弟表示法)存储时，可以找到唯一的一棵二叉树与之对应，我们称这棵二叉树为该树对应的二叉树。那么根据这个法则可知，树的后序遍历序列等同于该树对应的二叉树的中序遍历。例如，图 3-80 展示了一个转化实例。由图 3-80 可以看出，树的后序遍历和其对应的二叉树的中序遍历都是 BDCEA。注意，对于树而言，没有中序遍历。*14.若广义表 L=(1，2，3)，则 L 的长度和深度分别为_。（分数：1.00）A.1 和 1B.1 和 2 C.1 和 3D.2 和 2解析：略。15.已知二叉树
24、有 50 个叶子结点，则该二叉树的总结点数至少是_。（分数：1.00）A.96B.99 C.100D.113解析：任何一棵二叉树叶子结点数等于度为 2 的结点的个数加 1，因此此题中，度为 2 的结点的个数为50-1=49。二叉树中的结点的度只能为 0、1 或 2，如果该二叉树中没有度为 1 的结点，显然总结点数最小。那么究竟存不存在这样一棵树呢?当然存在，比如将 50 个结点赋以权值，构成一棵哈夫曼树，我们知道，哈夫曼树是正则二叉树(即没有度为 1 的结点)。因此总结点数至少为 50+49=99。16.一棵树高为 k 的完全二叉树至少有_个结点。（分数：1.00）A.2k-1B.2k-1-1
25、C.2k-1 D.2k解析：一棵高为 k 的完全二叉树，当第 k 层只有最左边一个结点时具有最少的结点。根据二叉树的性质，第 1 层到第 k-1 层共有结点 2k-1-1 个，因此它至少有 2k-1-1+1=2k-1个结点。17.下面有关线性表的叙述中，错误的是_。（分数：1.00）A.线性表采用顺序存储，必须占用一片连续的存储单元。B.线性表采用顺序存储，便于进行插入和删除操作。 C.线性表采用链接存储，不必占用一片连续的存储单元。D.线性表采用链接存储，便于插入和删除操作。解析：线性表若采用顺序存储，元素将占用一片连续的存储单元，在插入和删除一个元素时为保证仍是顺序存储必须移动大量元素(在
26、表尾插入或删除结点除外)，因此不方便。线性表若采用链式存储结构时不必占用连续的存储单元，在插入或删除结点时，只需修改指针即可，不必移动结点元素。18.关于满二叉树、完全二叉树有以下说法：满二叉树不仅是一种特殊形态的二叉树，而且是一种特殊的完全二叉树。具有 n 个结点的满二叉树的高度为 +1。具有 n 个结点的完全二叉树的高度为 +1。具有 n 个结点的满二叉树的高度为 log2(n+1)。具有 n 个结点的满二叉树共有叶子结点 （分数：1.00）A.B.C.D.全对 解析：若二叉树的每一层的结点数都是最大结点数，也就是说每一层都是满的，那么此时的二叉树便成为一棵满二叉树。若二叉树除最后一层外都
27、是满的，而且最后一层的结点都连续紧挨靠左，那么称此时的二叉树为完全二叉树。所谓的“完全”，指的是在给其结点按层次自上而下、同一层自左至右编号时，n 个结点(设完全二叉树结点总数为 n)与同深度的满二叉树中编号从 1 到 n 的结点一一对应。因此，正确。显然，是正确的。注意到，满二叉树是特殊的二叉树，因此也正确。值得指出的是，和中的 n 分别满足不同的条件，因此，和都正确。设具有 n 个结点的满二叉树的高度为 h，那么根据二叉树的性质有 n=2h-1，从而有 h=log2(n+1)，叶子结点的个数为 n-2h-1-1=2h-1=*，因此和都正确。值得指出的是和是等价的，只是表述不同而已。综上所述
28、，由于题干要求选最全面、最准确的，因此选 D。19.在非空双向循环链表结点中，prior 域指向该结点的直接前驱，next 域指向直接后续，那么在 q 所指的结点后面插入 p 所指的结点的过程为_。（分数：1.00）A.qnext=p；pprior=q；qnextprior=p；pnext=qnext。B.pnext=qnext；qnext=p；qnextprior=p；pprior=q。C.pprior=q；pnext=qnext；qnext=p；qnextprior=p。D.pnext=qnext；qnextprior=p；pprior=q；next=p。 解析：略。20.假设根结点的层数
29、为 1，并设具有 n(n3)个结点的二叉树的最大高度为 h，设达到最大高度 h 时，不同的二叉树的数目为 m。有以下说法：hn h=log 2n+1 m=1 m=2 m=2 n-1其中正确的个数有_个。（分数：1.00）A.1B.2 C.3D.4解析：显然，当二叉树的每一层只有一个结点时，它最高，因此有 h=n，于是正确。注意，“”是小于或等于的意思，只要其中一个成立便可使用，如 22 是成立的。显然不正确，它求出的是有 n 个结点的完全二叉树的高度。当二叉树的每一层只有一个结点时达到最大高度，这时，除根结点外，每一层的结点可以放在左边也可以放在右边，根据乘法原理，可得 m=2n-1。注意到
30、n3，所以 m1、m2，事实上，当不管是否 n3，都可以用 m=2n-1来统一表达。21.已知一算术表达式的中缀形式为(A+B)*C-D/E，其前缀形式为_。（分数：1.00）A.-*A+BC/DEB.-*+ABC/DE C.-*+BAC/DED.-*AB+C/DE解析：(A+B)*C-D/E 对应的二叉树如图 3-71 所示。*这棵二叉树的前序遍历-*+ABC/DE 就是(A+B)*C-D/E 的前缀形式。22.若采用邻接矩阵来存储简单有向图，则其某一个顶点 i 的人度等于该矩阵_。（分数：1.00）A.第 i 行中值为 1 的元素个数B.所有值为 1 的元素总数C.第 i 行及第 i 列中
31、值为 1 的元素总个数D.第 i 列中值为 1 的元素个数 解析：略。23.关于哈夫曼树、最优二叉树、哈夫曼算法，有以下说法：最优二叉树的形态不唯一，但是其 WPL 值是唯一确定的。哈夫曼树一定是最优二叉树，但最优二叉树不一定由哈夫曼算法来构造。则_。（分数：1.00）A.正确错误B.错误正确C.都对 D.都错解析：假设有 n 个权值w 1，w 2，w n)，构造一棵有 n 个叶子结点的二叉树，则称带权路径长度 WPL 最小的二叉树为最优二叉树，亦称哈夫曼树。值得注意的是，最优二叉树的形态不唯一，但是其 WPL 值是唯一确定的。这好比一个班里，张三、李四和王五体型各异但身高一样，而且是最高的，
32、显然最高的身高值只有一个。用哈夫曼算法构造出来的哈夫曼树一定是最优二叉树，定性地说，在哈夫曼算法中，每次构造新树时都是将权值最小的树尽量放在离根最远的地方，而将权值大的尽量放在离根近的地方，从而使得 WPL 最小。因此，哈夫曼树一定是最优二叉树。值得特别注意的是，哈夫曼算法可以确保构造出来的树是最优二叉树，但是最优二叉树并不一定非得用哈夫曼算法来构造。例如，给定权值2，3，4，7，8，9，可以构造出两棵最优二叉树 T1、T 2，如图 3-72所示。*显然它们的 WPL 都是 80，所以 T1、T 2都是是最优二叉树。T 1是用哈夫曼算法构造出来的，但 T2却不是用哈夫曼算法构造出来的，而是用上
33、文中提及的构造哈夫曼树最容易犯的错误想法构造出来的一棵树。从上面的例子可以看出，哈夫曼算法只是构造最优二叉树的“充分条件”，而不是“必要条件”。至于为什么将哈夫曼树称为最优二叉树，原因可能是由于哈夫曼最早给出了带有一般规律的构造最优二叉树的哈夫曼算法，为了纪念他，就用哈夫曼树来称呼所有的最优二叉树。24.关键路径是指 AOE(Activity On Edge)网中_。（分数：1.00）A.最长的回路B.最短的回路C.从源点到汇点(结束顶点)的最长路径 D.从源点到汇点(结束顶点)的最短路径解析：在数据压缩编码的应用中，哈夫曼(Huffman)算法可以用来构造具有 (1) 的二叉树，这是一种采用
34、了 (2) 的算法。（分数：2.00）A.前缀码B.最优前缀码 C.后缀码D.最优后缀码解析：A.贪心 B.分治C.递推D.回溯解析：25.对于二维数组 a0 4,1 5，设每个元素占 1 个存储单元，且以列为主序存储，则元素 a2,2相对于数组空间起始地址的偏移量是_。（分数：1.00）A.5B.7 C.10D.15解析：此类题型以前考过多次，为了让大家能更好地理解题目的意思以及解题的思想，图 3-81 给出了二维数组 a0 4, 1 5的结构。因为以列为主序存储，所以 a0, 1存储在 1 号存储单元，a1, 1存储在 2 号存储单元以此类推，a2, 2存储在 8 号存储单元，所以相对于数
35、组空间起始地址的偏移量为 8-1，即 7。偏移量就是差值。所以答案为：B。此外，若数组以行为主序存储，则数组的结构如图 3-82 所示。*26.算法是对问题求解过程的一类精确描述，算法中描述的操作都是可以通过已经实现的基本操作在限定时间内执行有限次来实现的，这句话说明算法具有_特性。（分数：1.00）A.正确性B.确定性C.可行性 D.健壮性解析：略。27.一棵二叉树的前序遍历序列为 ABCDEFG，它的中序遍历序列可能是_。（分数：1.00）A.CABDEFGB.ABCDEFG C.DACEFBGD.ADBCFEG解析：由前序遍历序列为 ABCDEFG 可知，这棵树的根结点为 A。先看选项
36、A，如果中序遍历是 CABDEFG，显然可以得出结点 C 是 A 的左孩子，而 BDEFG 都在 A 的右子树上，那么先序遍历时，应该是 ACB，也就是说 C 在 B 的前面，而题设中前序遍历是 ABC。类似地我们可以判断出 C、D 都不可能。结合选项 B 的中序遍历序列，我们可以得出此时对应的二叉树如图 3-73 所示。*28.先序遍历能得到 ABC 序列的不同二叉树的最大个数为_。（分数：1.00）A.4B.5 C.6D.7解析：题目的意思是：一种树含有三个结点 A、B、C，现以先序遍历这种树，得到 ABC 序列，那么这种树有多少种形式。由于树的结点总共只有 3 个，因此我们可以尝试着把所
37、有符合条件的树画出来，如图 3-79 所示。*所示答案应是 B。29.关于森林的遍历有以下说法：森林的先序遍历等同于其对应的二叉树的先序遍历。森林的中序遍历等同于其对应的二叉树的中序遍历。森林的后序遍历等同于其对应的二叉树的后序遍历。森林的后序遍历等同于其对应的二叉树的中序遍历。其中正确的是_。（分数：1.00）A.B. C.D.解析：根据森林和二叉树的转换规则，以及树的遍历定义可以得出，说法正确。值得注意的是，森林无后序遍历的定义。另外，树的先序遍历和后序遍历分别对应该树转换成的二叉树的先序遍历和中序遍历。树没有中序遍历的定义，不要把森林和树跟二叉树遍历的对应关系搞混了。30.一个含有 n
38、个顶点和 e 条边的简单无向图，在其邻接矩阵存储结构中共有_个零元素。（分数：1.00）A.eB.2eC.n2-eD.n2-2e 解析：邻接矩阵反映顶点间的邻接关系，设 G=(V，E)是具有 n(n1)个顶点的图，G 的邻接矩阵 M 是一个n 行 n 列的矩阵，并有若(i，j)或(i，jE，则 Mij=1；否则，Mij=0。由邻接矩阵的定义可知，无向图的邻接矩阵是对称的，即图中的一条边对应邻接矩阵中的两个非零元素。因此，在一个含有 n 个顶点和 e 条边的简单无向图的邻接矩阵中共有 n2-2e 个零元素。一般情况下，将递归程序转化成为非递归程序应该设置 (1) ，但是消除 (2) 时不需要使用
39、。（分数：2.00）A.堆栈 B.队列C.堆栈或队列D.数组解析：A.直接递归B.间接递归C.尾递归 D.递推解析：将递归程序转化成为非递归程时，一般需要设置栈。但对于尾递归可将其转化成递推，不需要栈。尾递归调用就是作为方法的最后一个操作出现的递归的方法调用。例如：打印数组 An值的递归算法：void recfunc(int A, int n)if(n=0)coutAn“;n-;|recfunc(A, n);可以改写为：void iterfunc(int A, int n)/消除了尾递归的非递归函数while(n=0)cout“value“Anendl;n-;某带权有向图如图 3-67 所示。
40、（分数：5.00）A.V1、V 2、V 3、V 4、V 6、V 5、V 7、V 8 B.V1、V 3、V 5、V 2、V 4、V 6、V 7、V 8C.V1、V 2、V 3、V 4、V 5、V 6、V 7、V 8D.V1、V 2、V 3、V 5、V 6、V 4、V 7、V 8解析：A.1B.2C.3 D.4解析：A.15B.16C.17 D.18解析：A.5B.9 C.10D.7解析：A.12、12B.12、13C.13、12D.13、13 解析：拓扑排序的方法是重复执行下列步骤：从图中选择一个入度为 0 的结点并输出之；从图中删除此结点及其所有的出边，直到 AOV 网中不存在入度为 0 的顶
41、点为止。在执行步骤时可能有几个人度为 0的结点，任选一个即可，从而导致可能会有多个拓扑排序。根据上述方法，显然可知(1)选 A。AOE 网中从源点到汇点路径长度最长的路径叫做关键路径。该 AOE 网中共有 3 条关键路径：V1V2V4V6V5V7V8、V 1V2V4V6V8、V 1V3V5V7V8，其长度均为 17。关键路径上的活动称为关键活动，也就是关键路径上所覆盖的有向边。此题中 3 条关键路径共覆盖了除 a5外的所有其它活动，如图 3-78 所示。*事件 Vk的最早发生时间是从源点到汇点的最长路径长度，V k的最迟发生时间是在不推迟整个工程完成的前提下 Vk最迟必须发生的时间。设关键路径长度为 X，顶点 Vk到汇点的最长路径长度为 Y，则 Vk的最迟发生时间为 X-Y。
