1.某树共有n个结点，其中所有分支结点的度为k（即每个非叶子结点的子树数目），则该树中叶子结点的个数为（ ）。
A.[n（k+1）-1]/k B.[n（k+1）+1]/k C.[n（k-1）+1]/k D.[n（k-1）-1]/k
所属知识点：数据结构与算法基础>树与二叉树的特性
答案解析：
本题可以画一棵简单的树验证4个选项，比如，以2个结点的树来看：
2.二叉树如右图所示，若进行顺序存储（即用一维数组元素存储该二叉树中的结点且通过下标反映结点间的关系，例如，对于下标为i的结点，其左孩子的下标为2i、右孩子的下标为2i+1），则该数组的大小至少为（ ）；若采用三叉链表存储该二叉树（各个结点包括结点的数据、父结点指针、左孩子指针、右孩子指针），则该链表的所有结点中空指针的数目为（ ）。
（1）A.6 B.10 C.12 D.15
（2）A.6 B.8 C.12 D.14
所属知识点：数据结构与算法基础>树与二叉树的特性
答案解析：用一维数组元素存储该二叉树中的结点且通过下标反映结点间的关系，实际上存储的是这棵二叉树对应的完全二叉树，因此需要的存储空间为2n-1=15(n为二叉树层数)。如下图所示：
| 1 | 2 | 3 | ^ | ^ | ^ | 7 | ^ | ^ | ^ | ^ | ^ | ^ | 14 | 15 |
釆用三叉链表存储该二叉树（各个结 点包括结点的数据、父结点指针、左孩子指针、右孩子指针）；如下图所示：
空指针数量为8。
3.输入受限的双端队列是指元素只能从队列的一端输入、但可以从队列的两端输出，如下图所示。若有8、1、4、2依次进入输入受限的双端队列，则得不到输出序列（）。
A.2、8、1、4 B.1、4、8、2 C.4、2、1、8 D.2、1、4、8
本题考查队列运算。
1. 对于输出序列2， 8， 1， 4，其运算过程为：元素8， 1， 4， 2依次进入队列，情形如下图所示。
2. 对于输出序列1、 4、 8、2，其运算过程为：元素8、 1先进入队列，情形如下图所示。
然后元素1出队，元素4入队并出队，元素2入队并出队，最后元素1出队，得到输出序列1、4、8、2。
3. 对于输出序列4、2、1、 8，其运算过程为：元素8、1、 4依次进入队列，如下图所示。
4.最大尺寸和问题描述为，在n个整数（包含负数）的数组A中，求之和最大的非空连续子数组,如数组A= (-2, 11, -4，13, -5，-2) ，其中子数组B= (11, -4, 13)具有最大子段和20 (11-4+13=20) 。求解该问题时,可以将数组分为两个n/2个整数的子数组最大子段或或者在前半段，或者在后半段，或者跨越中间元素，通过该方法继续划分问题，直至最后求出最大子段和，该算法的时间复杂度为（ ）。
A.O（nlgn） B.O（
所属知识点：数据结构与算法基础>分治法
答案解析：
本题中将数组不断进行二分，这个过程的时间复杂度为O(log2n)，划分后求解问题需要2个并列的for循环对划分后的数组进行求和比较，此时时间复杂度为O(n)，划分和求和过程应该是嵌套的，所以时间复杂度综合为O(nlgn)，本题应该选择A选项。
其算法过程可以设计如下：
5.对于二维数组a[0..4，1..5] ，设每个元素占1个存储单元，且以列为主序存储，则元素a[2，2]相对于数组空间起始地址的偏移量是（） 。
A.5 B.7 C.10 D.15
答案解析：本题考查数组元素的存储。
若二维数组A[L1…U1，L2..U2]以行为主序存储，每个元素占用d个存储单元，则元素A[I，J]的存储位置相对于数组空间首地址的偏移量为（（I-L1）×（U2-L2+ 1）+J-L2）×d；
若二维数组A[L1..U1，L2..U2]以列为主序存储，每个元素占用d个存储单元，则元素A[I，J]的存储位置相对于数组空间首地址的偏移量为（（J-L2）×（U1-L1 +1）+ I-L1）×d。
本题中d=1，L1=0.U1=4， L2=1.U2=5，代入后计算可得偏移量为7。
6.设栈S和队列Q的初始状态为空，元素a b c d e f g依次进入栈S。要求每个元素出栈后立即进入队列Q，若7个元素出队列的顺序为b d f e c a g，则栈S的容量最小应该是（ ）。
A.5 B.4 C.3 D.2
所属知识点：数据结构与算法基础>队列与栈
答案解析：本题考查数据结构基础知识。
根据队列的特点，元素出队的顺序与入队的顺序相同，因此，可知这7个元素的出栈顺序为b d f e c a g。对于入栈序列a b c d e f g，得出出栈序列b d f e c a g的操作过程为：push（a入）、push（b入）、pop（b出）、push（c入）、push（d入）、pop（d出）、push（e入）、push（f入）、pop（f出）、pop（e出）、pop（c出）、pop（a出）、push（g入）、pop（g出），如下图所示，从中可知栈S中元素最多时为4。因此，S的容量最小为4。
7.设有栈S和队列Q初始状态为空数据觉素序列a，b，c，d，e，f 依次通过栈 S，b，df，ec， a，则今中的元素最多时，栈底到且多个元素从S出栈后立即进入队列栈顶的元素依次为( ).
A.a,b,c
B.a,c.d
C.a,c,e,f
D.a,d,f,e
所属知识点：数据结构与算法基础>队列与栈
答案解析：
出队序列与入队序列是一致的，出队的序列是b,d,f, e, c, a，即入队序列也为b,d,f, e, c, a。
此时出栈后即入队，即出栈顺序也为b,d,f, e, c, a，元素出栈时，栈内情况依次如下：
栈S中元素最多时，从栈底到栈顶的元素依次为a、c、e、f。本题选择C选项。
8.( )是对稀疏矩阵讲行压缩存储的方式。
A.二维数组和双向链表
B.三元组顺序表和十字链表
C.邻接矩阵和十字链表
D.索引顺序表和双向链表
所属知识点：数据结构与算法基础>数组与矩阵
答案解析：
存储矩阵的一般方法是采用二维数组，其优点是可以随机地访问每一个元素，因而能够较容易地实现矩阵的各种运算。但对于稀疏矩阵而言，若用二维数组来表示，会重复存储了很多个0了，浪费空间，而且要花费时间来进行零元素的无效计算。所以必须考虑对稀疏矩阵进行压缩存储。
稀疏矩阵的三元组表的顺序存储结构称为三元组顺序表，常用的三元组表的链式存储结构是十字链表。
9.设用线性探查法解决冲突构造哈希表，且哈希函数为 H(key)=key%m，若在该哈希表中查找某关键字e 是成功的且与多个关键字进行了比较，则( )
A.这些关键字形成—个有序序列
B.这些关键字都不是e 的同义词
C.这些关键字都是 e的同义词
D.这些关键字的第一个可以不是e的同义词
所属知识点：数据结构与算法基础>散列表（哈希）
答案解析：
本题是对哈希查找表的考查。
关键字e的同义词，指的是其他关键字利用哈希函数进行求值时，得到的函数结果与e是一致的，此时这些关键字就是e的同义词。
在哈希表查找关键字e时成功且经过多次比较，可以知道经过计算e的位置，此时该位置存放的并不是关键字e，并且这些关键字的顺序与原序列顺序相关，与大小无关，A选项有序序列说法不正确。
由于本题采用的线性探测法解决哈希冲突，此时该位置对同义词开放，对非同义词也是开放的，也就是说，其他非同义关键字在使用线性探测法解决冲突时，也有可能直接占据该位置。所以对该位置进行比较的关键字，可能是e的同义词，也可能不是e的同义词，B和C的说法太过绝对，相比而言D的说法更合适，本题选择D选项。
10.对于一个初始无序的关键字序列，在下面的排序方法中，( )第一趟排序结束后，一定能将序列中的某个元素在最终有序序列中的位置确定下来。
①直接插入排序
②冒泡排序
③简单选择排序
④堆排序
⑤快速排序
⑥归并排序
A.①②③⑥
B.①②③⑤⑥
C.②③④⑤
D.③④⑤⑥
所属知识点：数据结构与算法基础>排序
答案解析：
选择类排序，每一轮会选择最值（最大值或最小值）与第一个位置进行交换，此时确定第一个元素位置。③④都满足要求。
冒泡排序，每一轮会让最值相邻交换直至放到最终的位置，②满足要求。
快速排序，每一轮会根据基准元素划分左右数组，此时基准元素的位置可以确定，因此⑤也满足要求。
其他排序方式每一轮只能确定元素的当前位置，不能确定该元素的最终位置。
本题选择C选项。
11.在求解某问题时，经过分析发现该问题具有最优子结构和重叠子问题性质。则适用(64) 算法设计策略得到最优解。若了解问题的解空间，并以广度优先的方式搜索解空间，则采用的是(65)算法策略。
(1)A.分治 B.贪心
C.动态规则 D.回溯
(2)A.动态规则 B.贪心
C.回溯 D.分支限界
所属知识点：数据结构与算法基础>其它
答案解析：
在求解某问题时，经过分析发现该问题具有最优子结构和重叠子问题性质。则适用（ ）算法设计策略得到最优解。若了解问题的解空间，并以广度优先的方式搜索解空间,则采用的是（ ）算法策略。
要想直接解决一个较大的问题，有时是相当困难的，分治法的设计思想是将一个难以解决的大问题分解成一些规模较小的相同问题，以便各个击破，分而治之。
动态规划法与分治法类似，其基本思想也是将带求解问题分解为若干个子问题，先求解子问题再从这些子问题的解得到原问题的解。与分治法不同的是，适合用动态规划法求解的问题，经分解得到的子问题往往不是独立的。若用分治法来解这类问题，则相同的子问题会被求解多次，以至于最后解决原问题需要耗费指数级时间。此时用一个中间表记录重复子问题的解，可以避免大量的重复计算。这就是动态规划法的基本思路。动态规划法的应用场景一般会出现“最优子结构”的描述，并且针对重复子问题的计算通过记录-查表，可以提高效率。本题第一空描述的是C选项动态规划法。
贪心法也经常用于解决最优化问题，与之不同的是，贪心法在解决问题的策略上是仅根据当前已有的信息做出选择，而且一旦做出选择，无论未来如何都不会改变。也就是只考虑当前最优，不考虑全局最优。一般不涉及划分和求解重复子问题。
回溯法可以系统地搜索一个问题的所有解或任意解。它在包含问题的解空间树中，按照深度优先的策略的策略，从根结点出发搜索解空间树。
分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法，但在一般情况下，分支限界法与回溯法的求解目标不同。分支限界法的求解目标是找出满足约束条件的一个解即可。由于求解目标不同，其探索方式与回溯法也不同，分支限界法以广度优先或以最小耗费优先的方式搜索解空间树。本题第二空描述的是D选项分支限界法。
12.对于求取两个长度为n的字符串的最长公共子序列（LCS）问题，利用（）策略可以有效地避免子串最长公共子序列的重复计算，得到时间复杂度为O（
（1）A .分治 B.贪心 C.动态规划 D.分支一限界
（2）A.3 B.4 C.5 D.6
所属知识点：数据结构与算法应用>动态规划法
答案解析：本题考查的是动态规划算法策略的典型应用。
LCS问题是利用动态规划策略解决的经典问题之一，利用动态规划求解该问题时可以通过查表得到已经计算出的子串的最长公共子序列，从而避免重复计算。利用动态规划算法可以得到题目中两个串的最长公共子序列长度为6，如“101011”。
13.在线性表L中进行二分查找，要求L（ ）。
A.顺序存储，元素随机排列
B.双向链表存储，元素随机排列
C.顺序存储，元素有序排列
D.双向链表存储，元素有序排列
所属知识点：数据结构与算法基础>二分查找
答案解析：本题考查二分查找相关知识。二分查找的前提条件是顺序存储，且有序排列。本题选择C选项。
14.对一待排序序列分别进行直接插入排序和简单选择排序，若待排序序列中有两个元素的值相同，则（ ）保证这两个元素在排序前后的相对位置不变。
A.直接插入排序和简单选择排序都可以
B.直接插入排序和简单选择排序都不能
C.只有直接插入排序可以
D.只有简单选择排序可以
所属知识点：数据结构与算法基础>排序
答案解析：直接插入排序是稳定的排序算法，选择排序是不稳定的排序算法。
15.采用贪心算法保证能求得最优解的问题是（ ）。
A.0-1背包
B.矩阵链乘
C.最长公共子序列
D.部分（分数）背包
所属知识点：数据结构与算法基础>贪心法
答案解析：贪心法在一般情况下一定能够得到满意解，不一定能够得到最优解。
贪心法能够获得最优解的前提是：（1）问题具有最优子结构，即规模为n的问题的最优解与规模为n-1的问题的解相关；（2）问题具有贪心选择性质，即问题的整体最优解可以通过一系列局部最优的选择得到。
部分背包问题具有以上性质，故可以通过贪心算法得到最优解。
16.对n个数排序，最坏情况下时间复杂度最低的算法是（ ）排序算法。
A.插入 B.冒泡 C.归并 D.快速
所属知识点：数据结构与算法基础>排序
答案解析：其他选项在最坏情况下的时间复杂度都是O(n2)，只有C选项归并排序，在最坏情况下，时间复杂度仍然是O(nlog2n)。
17.对于一个n阶的对称矩阵A，将其下三角区域（含主对角线）的元素按行存储在一维数组S中，设元素A[i][j]存放在S[k]中，且S[1]=A[0][0]，则k与i，j（i≤j）的对应关系是（ ）。
A.k = i（i+1）/2+j-1
B.k = j（j+1）/2+i+1
C.k = i（i+1）/2+j+1
D.k = j（j+1）/2+i-1
所属知识点：数据结构与算法基础>数组与矩阵
答案解析：本题有隐含条件需要注意，虽然前半段描述的是我们存储的下三角部分元素，但是最后提问的是i
【方法1】可用代入法解决问题。将S[1]=A[0][0]实例，对应上三角元素A[0][0]，代入选项验证可得，只有B和C选项符合要求；根据按行存储的顺序来看，下一个元素应该是A[1][0]，对应上三角元素A[0][1]，对应的一维数组位置为S[2]，代入BC选项进行验证，选项结果都为2，无法区分；根据按行存储的顺序来看，接下来元素应该是A[1][1]，对应上三角元素A[1][1]，对应的一维数组位置为S[3]，代入BC选项进行验证，选项结果都为3，无法区分；根据按行存储的顺序来看，接下来元素应该是A[2][0]，对应上三角元素A[0][2]，对应的一维数组位置为S[4]，代入BC选项进行验证，选项C结果为3不符合要求，选项B结果为4是正确的选项；所以本题选择B选项。
【方法2】也可以根据规律分析。对于对称矩阵A[][]结构如下：A[0][0] A[0][1] A[0][2] … A[0][n-1] A[0][n]A[1][0] A[1][1] A[1][2] … A[1][n-1] A[1][n]
A[2][0] A[2][1] A[2][2] … A[2][n-1] A[2][n]
…
A[n-1][0] A[n-1][1] A[n-1][2] … A[n-1][n-1] A[n-1][n]
A[n][0] A[n][1] A[n][2] … A[n][n-1] A[n][n]S[1]对应A[0][0]，对于下三角元素A[i][j]（i>=J），按行存储时，先处理前i-1行元素，此时每行对应元素分别为1、2、3、…、i-1、i个，求和，结果为（1+i）*i/2。接着处理第i行数据，本行列下标分别为0、1、2、…、j-1、j，共有j+1个元素。所以A[i][j]元素从S[1]开始，对应k=i（i+1）/2+j+1下标。这是下三角位置的分析过程。再根据本题问题，i
文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览33971 人正在系统学习中
声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！