1、软件设计师-数据结构与算法(四)及答案解析(总分：42.00，做题时间：90 分钟)一、单项选择题(总题数：37，分数：42.00)1.若二叉树的先序遍历序列为 ABDECF，中序遍历序列为 DBEAFC，则其后序遍历序列为_。ADEBAFC BDEFBCA CDEBCFA DDEBFCA（分数：1.00）A.B.C.D.2.对于哈希表，如果将装填因子定义为表中装入的记录数与表的长度之比，那么向表中加入新记录时，_。A装填因子的值随冲突次数的增加而递减B装填因子越大发生冲突的可能性就越大C装填因子等于 1 时不会再发生冲突D装填因子低于 0.5 时不会发生冲突（分数：1.00）A.B.C.D.
2、3.下面关于栈和队列的叙述，错误的是_。A栈和队列都是操作受限的线性表B队列采用单循环链表存储时，只需设置队尾指针就可使入队和出队操作的时间复杂度都为 O(1)C若队列的数据规模 n 可以确定，则采用顺序存储结构比链式存储结构效率更高D利用两个栈可以模拟一个队列的操作，反之亦可（分数：1.00）A.B.C.D.4.已知某二叉树的中序序列为 CBDAEFI，先序序列为 ABCDEFI，则该二叉树的高度为_。A2 B3 C4 D5（分数：1.00）A.B.C.D.5.己知一棵度为 3 的树(一个结点的度是指其子树的数目，树的度是指该树中所有结点的度的最大值)中有5 个度为 1 的结点，4 个度为
3、2 的结点，2 个度为 3 的结点，那么，该树中的叶子结点数目为_。A10 B9 C8 D7（分数：1.00）A.B.C.D.斐波那契(Fibonacci)数列可以递归地定义为：（分数：2.00）(1).A5 B6 C7 D8（分数：1.00）A.B.C.D.(2).A动态规划 B分治 C回溯 D分支限界（分数：1.00）A.B.C.D.6.设某算法的计算时间可用递推关系式 T(n)=2T(n/2)+n 表示，则该算法的时间复杂度为_。AO(lgn) BO(nlgn) CO(n)DO(n 2)（分数：1.00）A.B.C.D.简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图 G 有
4、 n 个结点，其邻接矩阵为A1n，1n，且压缩存储在 B1k中，则 k 的值至少为 (20) 。若按行压缩存储对称矩阵的上三角元素，则当 n 等于 10 时，边(V6，V3)的信息存储在 B (21) 中。（分数：2.00）(1). （分数：1.00）A.B.C.D.(2).A18 B19 C20 D21（分数：1.00）A.B.C.D.7._在其最好情况下的算法时间复杂度为 O(n)。A插入排序 B归并排序 C快速排序 D堆排序（分数：1.00）A.B.C.D.8. () 的邻接矩阵是一个对称矩阵。A无向图 BAOV 网 CAOE 网 D有向图（分数：1.00）A.B.C.D.设一个包含个顶
5、点、E 条边的简单有向图采用邻接矩阵存储结构(矩阵元素 Aij等于 1/0 分别表示顶点 i 与顶点 j 之间有/无弧)，则该矩阵的元素数目为 (73) ，其中非零元素数目为 (74) 。（分数：2.00）(1).AE 2 BN 2 CN 2-E2 DN 2+E2（分数：1.00）A.B.C.D.(2).AN BN+E CE DN-E（分数：1.00）A.B.C.D.9.某双向链表中的结点如图 1-4 所示，删除 t 所指结点的操作为_。（分数：1.00）A.B.C.D.10.下面关于哈夫曼树的叙述中，正确的是_A哈夫曼树一定是完全二叉树B哈夫曼树一定是平衡二叉树C哈夫曼树中权值最小的两个结点
6、互为兄弟结点D哈夫曼树中左孩子结点小于父结点，右孩子结点大于父结点（分数：1.00）A.B.C.D.11.循环链表的主要优点是_。A不再需要头指针了B已知某个结点的位置后，能很容易找到它的直接前驱结点C在进行删除操作后，能保证链表不断开D从表中任一结点出发都能遍历整个链表（分数：1.00）A.B.C.D.12.对于关键字序列(26，25，72，38，8，18，59)，采用散列函数 H(Key)=Key mod 13 构造散列表(哈希表)。若采用线性探测的开放定址法解决冲突(顺序地探查可用存储单元)，则关键字 59 所在散列表中的地址为_。A6 B7 C8 D9（分数：1.00）A.B.C.D.
7、13.邻接矩阵和邻接表是图(网)的两种基本存储结构，对于具有 n 个顶点、e 条边的图，_。A进行深度优先遍历运算所消耗的时间与采用哪一种存储结构无关B进行广度优先遍历运算所消耗的时间与采用哪一种存储结构无关C采用邻接表表示图时，查找所有顶点的邻接顶点的时间复杂度为 O(n*e)D采用邻接矩阵表示图时，查找所有顶点的邻接顶点的时间复杂度为 O(n2)（分数：1.00）A.B.C.D.14.归并排序采用的算法设计方法属于_。A归纳法 B分治法 C贪心法 D回溯法（分数：1.00）A.B.C.D.15.设下三角矩阵(上三角部分的元素值都为 0)A0n，0n如图 1-10 所示，将该三角矩阵的所有非
8、零元素(即行下标不小于列下标的元素)按行优先压缩存储在容量足够大的数组 M中(下标从 1 开始)，则元素 Ai,j(0in，ji)存储在数组 M 的_中。（分数：1.00）A.B.C.D.设栈 S 和队列 Q 的初始状态为空，元素按照 a，b，c，d，e 的次序进入栈 S，当一个元素从栈中出来后立即进入队列 Q。若队列的输出元素序列是 c，d，b，a，e，则元素的出栈顺序是 (61) ，栈 S 的容量至少为 (62) 。（分数：2.00）(1).Aa，b，c，d，e Be，d，c，b，a Cc，d，b，a，e De，a，b，d，c（分数：1.00）A.B.C.D.(2).A2 B3 C4 D5
9、（分数：1.00）A.B.C.D.16.设商店有 10 元、5 元、2 元和 1 元的零币，每种零币的数量充足。售货员给顾客找零钱时，零币的数量越少越好。例如给顾客找零 29 元：先选 2 张 10 元币，然后选择 1 张 5 元币，再选择两张 2 元币。以上的找零钱方法采用了_策略。A分治 B贪心 C动态规划 D回溯（分数：1.00）A.B.C.D.17.用关键字序列 10，20，30，40，50 构造的二叉排序树(二叉查找树)为_。A BC D （分数：1.00）A.B.C.D.18.在平衡二叉树中，_。A任意结点的左、右子树结点数目相同B任意结点的左、右子树高度相同C任意结点的左、右子树
10、高度之差的绝对值不大于 1D不存在度为 1 的结点（分数：1.00）A.B.C.D.19.无向图中一个顶点的度是指图中_。A通过该顶点的简单路径数 B通过该顶点的回路数C与该顶点相邻的顶点数 D与该顶点连通的顶点数（分数：1.00）A.B.C.D.20.对以下 4 个序列用直接插入排序方法由小到大进行排序时，元素比较次数最少的是_。A89，27，35，78，41，15 B27，35，41，16，89，70C15，27，46，40，64，85 D90，80，45，38，30，25（分数：1.00）A.B.C.D.21.在二叉树的顺序存储中，每个结点的存储位置与其父结点、左右子树结点的位置都存在一
11、个简单的映射关系，因此可与三叉链表对应。若某二叉树共有 n 个结点，采用三叉链表存储时，每个结点的数据域需要 d 个字节，每个指针域占用 4 个字节，若采用顺序存储，则最后一个结点下标为 k(起始下标为 1)，那么_时采用顺序存储更节省空间。（分数：1.00）A.B.C.D.22.在最好和最坏情况下的时间复杂度均为 O(nlog2n)且稳定的排序方法是_。A基数排序 B快速排序 C堆排序 D归并排序（分数：1.00）A.B.C.D.某工程计划如图 1-6 所示，各个作业所需的天数如下表所示，设该工程从第 0 天开工，则该工程的最短工期是 (52) 天，作业 J 最迟应在第 (53) 天开工。（
12、分数：2.00）(1).A17 B18 C19 D20（分数：1.00）A.B.C.D.(2).A11 B13 C14 D16（分数：1.00）A.B.C.D.23.广义表中的元素可以是原子，也可以是表，因此广义表的适用存储结构是_。A链表 B静态数组 C动态数组 D散列表（分数：1.00）A.B.C.D.24.由权值为 9，2，5，7 的 4 个叶子结点构造一棵哈夫曼树，该树的带权路径长度为_。A23 B37 C44 D46（分数：1.00）A.B.C.D.25.字符串采用链表存储方式时，每个结点存储多个字符有助于提高存储密度。若采用结点大小相同的链表存储串，则在串比较、求子串、串连接、串替
13、换等串的基本运算中，_。A进行串的比较运算最不方便 B进行求子串运算最不方便C进行串连接最不方便 D进行串替换最不方便（分数：1.00）A.B.C.D.26.在_中，任意一个结点的左、右子树的高度之差的绝对值不超过 1。A完全二叉树 B二叉排序树C线索二叉树 D最优二叉树（分数：1.00）A.B.C.D.27.下面关于图(网)的叙述，正确的是_。A连通无向网的最小生成树中，顶点数恰好比边数多 1B若有向图是强连通的，则其边数至少是顸点数的 2 倍C可以采用 AOV 网估算工程的工期D关键路径是 AOE 网中源点至汇点的最短路径（分数：1.00）A.B.C.D.28.一个具有 n(n0)个顶点的
14、连通无向图至少有_条边。An+1 Bn Cn/2 Dn-1（分数：1.00）A.B.C.D.29.下面关于查找运算及查找表的叙述，错误的是_。A哈希表可以动态创建B二叉排序树属于动态查找表C二分查找要求查找表采用顺序存储结构或循环链表结构D顺序查找方法既适用于顺序存储结构，也适用于链表结构（分数：1.00）A.B.C.D.30.在常用的描述二叉排序树的存储结构中，关键字值最大的结点_。A左指针一定为空 B右指针一定为空C左、右指针均为空 D左、右指针均不为空（分数：1.00）A.B.C.D.31.具有 n 个顶点、e 条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均
15、为_。AO(n 2) BO(e 2) CO(n*e) DO(n+e)（分数：1.00）A.B.C.D.32.将一个无序序列中的元素依次插入到一棵_，并进行中序遍历，可得到一个有序序列。A完全二叉树 B最小生成树 C二叉排序树 D最优二叉树（分数：1.00）A.B.C.D.软件设计师-数据结构与算法(四)答案解析(总分：42.00，做题时间：90 分钟)一、单项选择题(总题数：37，分数：42.00)1.若二叉树的先序遍历序列为 ABDECF，中序遍历序列为 DBEAFC，则其后序遍历序列为_。ADEBAFC BDEFBCA CDEBCFA DDEBFCA（分数：1.00）A.B.C.D. 解析
16、：2.对于哈希表，如果将装填因子定义为表中装入的记录数与表的长度之比，那么向表中加入新记录时，_。A装填因子的值随冲突次数的增加而递减B装填因子越大发生冲突的可能性就越大C装填因子等于 1 时不会再发生冲突D装填因子低于 0.5 时不会发生冲突（分数：1.00）A.B. C.D.解析：3.下面关于栈和队列的叙述，错误的是_。A栈和队列都是操作受限的线性表B队列采用单循环链表存储时，只需设置队尾指针就可使入队和出队操作的时间复杂度都为 O(1)C若队列的数据规模 n 可以确定，则采用顺序存储结构比链式存储结构效率更高D利用两个栈可以模拟一个队列的操作，反之亦可（分数：1.00）A.B.C.D.
17、解析：4.已知某二叉树的中序序列为 CBDAEFI，先序序列为 ABCDEFI，则该二叉树的高度为_。A2 B3 C4 D5（分数：1.00）A.B.C. D.解析：5.己知一棵度为 3 的树(一个结点的度是指其子树的数目，树的度是指该树中所有结点的度的最大值)中有5 个度为 1 的结点，4 个度为 2 的结点，2 个度为 3 的结点，那么，该树中的叶子结点数目为_。A10 B9 C8 D7（分数：1.00）A.B. C.D.解析：斐波那契(Fibonacci)数列可以递归地定义为：（分数：2.00）(1).A5 B6 C7 D8（分数：1.00）A.B.C. D.解析：(2).A动态规划 B
18、分治 C回溯 D分支限界（分数：1.00）A.B. C.D.解析：6.设某算法的计算时间可用递推关系式 T(n)=2T(n/2)+n 表示，则该算法的时间复杂度为_。AO(lgn) BO(nlgn) CO(n)DO(n 2)（分数：1.00）A.B. C.D.解析：简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图 G 有 n 个结点，其邻接矩阵为A1n，1n，且压缩存储在 B1k中，则 k 的值至少为 (20) 。若按行压缩存储对称矩阵的上三角元素，则当 n 等于 10 时，边(V6，V3)的信息存储在 B (21) 中。（分数：2.00）(1). （分数：1.00）A.B.C.D
19、. 解析：(2).A18 B19 C20 D21（分数：1.00）A.B.C. D.解析：7._在其最好情况下的算法时间复杂度为 O(n)。A插入排序 B归并排序 C快速排序 D堆排序（分数：1.00）A. B.C.D.解析：8. () 的邻接矩阵是一个对称矩阵。A无向图 BAOV 网 CAOE 网 D有向图（分数：1.00）A. B.C.D.解析：设一个包含个顶点、E 条边的简单有向图采用邻接矩阵存储结构(矩阵元素 Aij等于 1/0 分别表示顶点 i 与顶点 j 之间有/无弧)，则该矩阵的元素数目为 (73) ，其中非零元素数目为 (74) 。（分数：2.00）(1).AE 2 BN 2
20、CN 2-E2 DN 2+E2（分数：1.00）A.B. C.D.解析：(2).AN BN+E CE DN-E（分数：1.00）A.B.C. D.解析：9.某双向链表中的结点如图 1-4 所示，删除 t 所指结点的操作为_。（分数：1.00）A. B.C.D.解析：10.下面关于哈夫曼树的叙述中，正确的是_A哈夫曼树一定是完全二叉树B哈夫曼树一定是平衡二叉树C哈夫曼树中权值最小的两个结点互为兄弟结点D哈夫曼树中左孩子结点小于父结点，右孩子结点大于父结点（分数：1.00）A.B.C. D.解析：11.循环链表的主要优点是_。A不再需要头指针了B已知某个结点的位置后，能很容易找到它的直接前驱结点C
21、在进行删除操作后，能保证链表不断开D从表中任一结点出发都能遍历整个链表（分数：1.00）A.B.C.D. 解析：12.对于关键字序列(26，25，72，38，8，18，59)，采用散列函数 H(Key)=Key mod 13 构造散列表(哈希表)。若采用线性探测的开放定址法解决冲突(顺序地探查可用存储单元)，则关键字 59 所在散列表中的地址为_。A6 B7 C8 D9（分数：1.00）A.B.C.D. 解析：13.邻接矩阵和邻接表是图(网)的两种基本存储结构，对于具有 n 个顶点、e 条边的图，_。A进行深度优先遍历运算所消耗的时间与采用哪一种存储结构无关B进行广度优先遍历运算所消耗的时间与
22、采用哪一种存储结构无关C采用邻接表表示图时，查找所有顶点的邻接顶点的时间复杂度为 O(n*e)D采用邻接矩阵表示图时，查找所有顶点的邻接顶点的时间复杂度为 O(n2)（分数：1.00）A.B.C.D. 解析：14.归并排序采用的算法设计方法属于_。A归纳法 B分治法 C贪心法 D回溯法（分数：1.00）A.B. C.D.解析：15.设下三角矩阵(上三角部分的元素值都为 0)A0n，0n如图 1-10 所示，将该三角矩阵的所有非零元素(即行下标不小于列下标的元素)按行优先压缩存储在容量足够大的数组 M中(下标从 1 开始)，则元素 Ai,j(0in，ji)存储在数组 M 的_中。（分数：1.00
23、）A. B.C.D.解析：设栈 S 和队列 Q 的初始状态为空，元素按照 a，b，c，d，e 的次序进入栈 S，当一个元素从栈中出来后立即进入队列 Q。若队列的输出元素序列是 c，d，b，a，e，则元素的出栈顺序是 (61) ，栈 S 的容量至少为 (62) 。（分数：2.00）(1).Aa，b，c，d，e Be，d，c，b，a Cc，d，b，a，e De，a，b，d，c（分数：1.00）A.B.C. D.解析：(2).A2 B3 C4 D5（分数：1.00）A.B. C.D.解析：16.设商店有 10 元、5 元、2 元和 1 元的零币，每种零币的数量充足。售货员给顾客找零钱时，零币的数量越
24、少越好。例如给顾客找零 29 元：先选 2 张 10 元币，然后选择 1 张 5 元币，再选择两张 2 元币。以上的找零钱方法采用了_策略。A分治 B贪心 C动态规划 D回溯（分数：1.00）A.B. C.D.解析：17.用关键字序列 10，20，30，40，50 构造的二叉排序树(二叉查找树)为_。A BC D （分数：1.00）A.B.C. D.解析：18.在平衡二叉树中，_。A任意结点的左、右子树结点数目相同B任意结点的左、右子树高度相同C任意结点的左、右子树高度之差的绝对值不大于 1D不存在度为 1 的结点（分数：1.00）A.B.C. D.解析：19.无向图中一个顶点的度是指图中_。
25、A通过该顶点的简单路径数 B通过该顶点的回路数C与该顶点相邻的顶点数 D与该顶点连通的顶点数（分数：1.00）A.B.C. D.解析：20.对以下 4 个序列用直接插入排序方法由小到大进行排序时，元素比较次数最少的是_。A89，27，35，78，41，15 B27，35，41，16，89，70C15，27，46，40，64，85 D90，80，45，38，30，25（分数：1.00）A.B.C. D.解析：21.在二叉树的顺序存储中，每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系，因此可与三叉链表对应。若某二叉树共有 n 个结点，采用三叉链表存储时，每个结点的数据域需
26、要 d 个字节，每个指针域占用 4 个字节，若采用顺序存储，则最后一个结点下标为 k(起始下标为 1)，那么_时采用顺序存储更节省空间。（分数：1.00）A. B.C.D.解析：22.在最好和最坏情况下的时间复杂度均为 O(nlog2n)且稳定的排序方法是_。A基数排序 B快速排序 C堆排序 D归并排序（分数：1.00）A.B.C.D. 解析：某工程计划如图 1-6 所示，各个作业所需的天数如下表所示，设该工程从第 0 天开工，则该工程的最短工期是 (52) 天，作业 J 最迟应在第 (53) 天开工。（分数：2.00）(1).A17 B18 C19 D20（分数：1.00）A.B.C.D.
27、解析：(2).A11 B13 C14 D16（分数：1.00）A.B. C.D.解析：23.广义表中的元素可以是原子，也可以是表，因此广义表的适用存储结构是_。A链表 B静态数组 C动态数组 D散列表（分数：1.00）A. B.C.D.解析：24.由权值为 9，2，5，7 的 4 个叶子结点构造一棵哈夫曼树，该树的带权路径长度为_。A23 B37 C44 D46（分数：1.00）A.B.C. D.解析：25.字符串采用链表存储方式时，每个结点存储多个字符有助于提高存储密度。若采用结点大小相同的链表存储串，则在串比较、求子串、串连接、串替换等串的基本运算中，_。A进行串的比较运算最不方便 B进行
28、求子串运算最不方便C进行串连接最不方便 D进行串替换最不方便（分数：1.00）A.B.C.D. 解析：26.在_中，任意一个结点的左、右子树的高度之差的绝对值不超过 1。A完全二叉树 B二叉排序树C线索二叉树 D最优二叉树（分数：1.00）A. B.C.D.解析：27.下面关于图(网)的叙述，正确的是_。A连通无向网的最小生成树中，顶点数恰好比边数多 1B若有向图是强连通的，则其边数至少是顸点数的 2 倍C可以采用 AOV 网估算工程的工期D关键路径是 AOE 网中源点至汇点的最短路径（分数：1.00）A. B.C.D.解析：28.一个具有 n(n0)个顶点的连通无向图至少有_条边。An+1
29、Bn Cn/2 Dn-1（分数：1.00）A.B.C.D. 解析：29.下面关于查找运算及查找表的叙述，错误的是_。A哈希表可以动态创建B二叉排序树属于动态查找表C二分查找要求查找表采用顺序存储结构或循环链表结构D顺序查找方法既适用于顺序存储结构，也适用于链表结构（分数：1.00）A.B.C. D.解析：30.在常用的描述二叉排序树的存储结构中，关键字值最大的结点_。A左指针一定为空 B右指针一定为空C左、右指针均为空 D左、右指针均不为空（分数：1.00）A.B. C.D.解析：31.具有 n 个顶点、e 条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为_。AO(n 2) BO(e 2) CO(n*e) DO(n+e)（分数：1.00）A.B.C.D. 解析：32.将一个无序序列中的元素依次插入到一棵_，并进行中序遍历，可得到一个有序序列。A完全二叉树 B最小生成树 C二叉排序树 D最优二叉树（分数：1.00）A.B.C. D.解析：
