1、程序员-数据结构与算法(三)及答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：40，分数：100.00)1.设数组 a1m，1n(2mn)，其第一个元素为 a1,1，最后一个元素为 am,n，若数细元素以行为主序存放，每个元素占用 k 个存储单元(k1)，则元素 a2,2的存储位置相对于数组空间首地址的偏移量为_。A(n+1)*k Bn*k+1 C(m+1)*k Dm*k+1（分数：2.00）A.B.C.D.2.某研究机构有 n 名研究人员(n2)，其每个人都与一名以上的同事有过研究项目合作关系，那么用_结构表示该机构研究人员间的项目合作关系较为合适。A树 B图 C
2、栈 D队列（分数：2.00）A.B.C.D.3.以下关于字符串的叙述中，正确的是_。A包含任意个空格字符的字符串称为空串B仅包含一个空格字符的字符串称为空串C字符串的长度是指串中所含字符的个数D字符串的长度是指串中所含非空格字符的个数（分数：2.00）A.B.C.D.4.设循环队列 Q 的定义中有 rear 和 size 两个域变量，其中，rear 指示队尾元素之后的位置，size 表示队列的长度，如图所示(队列长度为 3，队头元素为 x)。设队列的存储空间容量为 M，则队头元素的位置为_。（分数：2.00）A.B.C.D.5.已知某二叉树的先序遍历序列为 ABCD，中序遍历序列为 BADC，
3、则该二叉树的后序遍历序列为_。ABDCA BCDBA CDBCA DBCDA（分数：2.00）A.B.C.D.6.对于任意一个结点数为 n(n0)的二叉树，其高度 h_。A一定大于 n B一定小于 nC一定小于 log2n D一定大于 log2n（分数：2.00）A.B.C.D.7._最不适用于处理序列已经正序有序的情况。A冒泡排序 B快速排序 C归并排序 D直接插入排序（分数：2.00）A.B.C.D.8.以下关于顺序查找和二分查找的叙述中，正确的是_。A顺序查找方法只适用于采用顺序存储结构的查找表B顺序查找方法只适用于采用链表存储结构的查找表C二分查找只适用于采用顺序存储结构的查找表D二分
4、查找只适用于采用循环链表存储结构的查找表（分数：2.00）A.B.C.D.9.以下关于图的存储结构的叙述中，正确的是_。A有向图的邻接矩阵一定是对称的B有向图的邻接矩阵一定是不对称的C无向图的邻接矩阵一定是对称的D无向图的邻接矩阵一定是不对称的（分数：2.00）A.B.C.D.10.设数组 a1n，1m(m1，n1)中的元素以行为主序存放，每个元素占用 1 个存储单元，则数组元素 ai,j(1in，1jm)相对于数组空间首地址的偏移量为_。A(i-1)*m+j-1 B(i-1)*n+j-1C(j-1)*m+i-1 D(i-1)*n+j-1（分数：2.00）A.B.C.D.11.线性表采用单链表
5、存储结构时，访问表中元素的方式为_。A随机存取 B顺序存取 C索引存取 D散列存取（分数：2.00）A.B.C.D.12.有 n 个结点的有序单链表中插入一个新结点并保持有序的运算的时间复杂度为_。AO(1) BO(logn) CO(n) DO(n2)（分数：2.00）A.B.C.D.13.栈和队列的主要区别是_。A逻辑结构不同 B存储结构不同C基本运算数目不同 D插入运算和删除运算的要求不同（分数：2.00）A.B.C.D.14._不属于特殊矩阵。A对称矩阵 B对角矩阵 C稀疏矩阵 D三角矩阵（分数：2.00）A.B.C.D.15.一个高度为 h 的满二叉树的结点总数为 2h-1，其每一层结
6、点个数都达到最大值。从根结点开始顺序编号，每一层都从左到右依次编号，直到最后的叶子结点层为止。即根结点编号为 1，其左、右孩子结点编号分别为 2 和 3，再下一层从左到右的编号为 4、5、6、7，依此类推，那么，在一棵满二叉树中，埘于编号为 m 和 n 的两个结点，若 m=2n，则结点_。Am 是 n 的左孩子 Bm 是 n 的右孩予Cn 是 m 的左孩子 Dn 是 m 的右孩子（分数：2.00）A.B.C.D.16.在一棵非空二叉排序树中，关键字最小的结点的_。A左子树一定为空、右子树不一定为空B左子树不一定为空、右子树一定为空C左子树和右子树一定都为空D左子树和右子树一定都不为空（分数：2
7、.00）A.B.C.D.17.若采用链地址法对关键字序列(74，10，23，6，45，38，18)构造哈希表(或散列表)，设敞列函数为H(Key)=Key%7(%表示整除取余运算)，则哈希表中地址为_的单链表长度为 0(即没有关键字被映射到这些哈希地址)。A0、1 和 2 B1、2 和 3 C1、3 和 5 D0、1 和 5（分数：2.00）A.B.C.D.18.有 6 个顶点的图 G 的邻接表如下所示，以下关于图 G 的叙述中，正确的是_。（分数：2.00）A.B.C.D.19.单链表不具有的特点是_。A插入、删除运算不需要移动元素B可随机访问链表中的任一元素C不必事先估计存储空间值D所需存
8、储空间量与线性表长度成正比（分数：2.00）A.B.C.D.20.不适合采用栈结构的是_。A判断一个表达式中的括号是否匹配B判断一个字符串是否是中心对称C按照深度优先的方式后序遍历二叉树D按照层次顺序遍历二叉树（分数：2.00）A.B.C.D.21.设有字符串 S 和 P，串的模式匹配是指_。A确定 P 在 S 中首次出现的位置 B将 S 和 P 连接起来C将 S 替换为 P D比较 S 和 P 是否相同（分数：3.00）A.B.C.D.22.以下关于特殊矩阵和稀疏矩阵的叙述中，正确的是_。A特殊矩阵适合采用双向链表存储，稀疏矩阵适合采用单向链表存储B特殊矩阵的非零元素分布有规律，可以用一维数
9、组进行压缩存储C稀疏矩阵的非零元素分布没有规律，只能用二维数组压缩存储D稀疏矩阵的非零元素分布没有规律，只能用双向链表进行压缩存储（分数：3.00）A.B.C.D.23.已知某二叉树的先序遍历序列为 ABDCEFG、中序遍历序列为 BDACFGE，则该二叉树的层数为_。A3 B4 C5 D6（分数：3.00）A.B.C.D.24.在一棵非空的二叉排序树中，关键字最大的结点的_。A左子树一定为空，右子树不一定为空B左子树不一定为空，右子树一定为空C左子树和右子树一定都为空D左子树和右子树一定都不为空（分数：3.00）A.B.C.D.25.为实现快速排序算法，待排序列适合采用_。A顺序存储 B链式
10、存储 C散列存储 D索引存储（分数：3.00）A.B.C.D.26.若某无向图具有 n 个顶点、e 条边，则其邻接矩阵中值为 0 的元素个数为_。Ae B2e Cn*n-2e Dn-2e（分数：3.00）A.B.C.D.27.以下关于程序流程图、N-S 盒图和决策表的叙述中，错误的是_。AN-S 盒图可以避免随意的控制转移BN-S 盒图可以同时表示程序逻辑和数据结构C程序流程图中的控制流可以任意转向D决策表适宜表示多重条件组合下的行为（分数：3.00）A.B.C.D.28.以下关于哈希表的叙述中，错误的是_。A哈希表中元素的存储位置根据该元素的关键字值计算得到B哈希表中的元素越多，插入一个新元
11、素时发生冲突的可能性就越小C哈希表中的元素越多，插入一个新元素时发生冲突的可能性就越大D哈希表中插入新元素发生冲突时，需要与表中某些元素进行比较（分数：3.00）A.B.C.D.下三角矩阵 A08,08如下图所示，若将其下三角元素(即行下标不小于列下标的所有元素)按列压缩存储在数组 M0m中，即 A0,0存储在 M0、A1,0存储在 M1、A2,0存储在 M2，A8,8存储在 M44，则元素 A5,5存储在_。若将其下三角元素按行压缩存储在数组 M0m中，即 A0,0存储在 M0、A1,0存储在 M1、A1,1存储在 M2，A8,8存储在 M44，则元素 A5,5存储在_。（分数：6.00）(
12、1).AM15 BM20 CM35 DM39（分数：3.00）A.B.C.D.(2).AM15 BM20 CM35 DM39（分数：3.00）A.B.C.D.29.对 n 个元素的有序表 A1n进行二分(折半)查找，则成功查找到表中的任意一个元素时，最多与 A中的_个元素进行比较。An-1 Bn/2 C(log 2n)-1 D(log 2n)+1（分数：3.00）A.B.C.D.30.某二叉树为单枝树(即非叶子节点只有一个孩子节点)且具有 n 个节点(n1)则该二叉树_。A共有 n 层，每层有一个节点B共有 log2n 层，相邻两层的节点数正好相差一倍C先序遍历序列与中序遍历序列相同D后序遍历
13、序列与中序遍历序列相同（分数：3.00）A.B.C.D.31.以下应用中，必须采用栈结构的是_。A使一个整数序列逆转 B递归函数的调用和返回C申请和释放单链表中的节点 D装入和卸载可执行程序（分数：3.00）A.B.C.D.32.某图的邻接矩阵如下所示，则该图为_。ABCD （分数：3.00）A.B.C.D.33.在直接插入排序、冒泡排序、简单选择排序和快速排序方法中，能在第一趟排序结束后就得到最大(或最小)元素的排序方法是_。A冒泡排序和快速排序 B直接插入排序和简单选择排序C冒泡排序和简单选择排序 D直接插入排序和快速排序（分数：3.00）A.B.C.D.34.现需要将数字 2 和 7 分
14、别填入 6 个空格中的 2 个(每个空格只能填入一个数字)，已知第 1 格和第 2 格不能填 7，第 6 格不能填 2，则共有_种填法。A12 B16 C17 D20（分数：3.00）A.B.C.D.35.许多工作需要用曲线来拟合平面上一批离散的点，以便于直观了解趋势，也便于插值和预测。例如，对平面上给定的 n 个离散点(Xi,Yi)i=1，n)，先依次将每 4 个点分成一组，并且前一组的尾就是后一组的首；再对每一组的 4 个点，确定一段多项式函数曲线使其通过这些点。一般来说，通过给定的 4个点可以确定一条_次多项式函数曲线恰好通过这 4 个点。A2 B3 C4 D5（分数：3.00）A.B.
15、C.D.36.设 A 是 n*n 常数矩阵(n1)，X 是由未知数 X1，X 2，X n组成的列向量，B 是由常数 b1，b 2，b n组成的列向量，线性方程组 AX=B 有唯一解的充分必要条件不是_。AA 的秩等于 n BA 的秩不等于 0 CA 的行列式值不等于 0 DA 存在逆矩阵（分数：3.00）A.B.C.D.37.若在单向链表上，除访问链表中所有节点外，还需在表尾频繁插入节点，那么采用_最节省时间。A仅设尾指针的单向链表 B仅设头指针的单向链表C仅设尾指针的单向循环链表 D仅设头指针的单向循环链表（分数：2.00）A.B.C.D.38.已知某二叉树的先序遍历序列是 ABDCE，中序
16、遍历序列是 BDAEc，则该二叉树为_。ABCD （分数：2.00）A.B.C.D.39.对于二维数组 a16,18，设每个元素占 2 个存储单元，且以列为主序存储，则元素 a4,4相对于数组空间起始地址的偏移量是_个存储单元。A28 B42 C48 D54（分数：2.00）A.B.C.D.程序员-数据结构与算法(三)答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：40，分数：100.00)1.设数组 a1m，1n(2mn)，其第一个元素为 a1,1，最后一个元素为 am,n，若数细元素以行为主序存放，每个元素占用 k 个存储单元(k1)，则元素 a2,2的存储位置
17、相对于数组空间首地址的偏移量为_。A(n+1)*k Bn*k+1 C(m+1)*k Dm*k+1（分数：2.00）A. B.C.D.解析：解析 本题考查数组元素的存储。二维数组的存储结构可分为以行为主序和以列为主序两种方法。设每个元素占用 k 个单元，m、n 为数组的行数和列数，则以行为主序优先存储的地址计算公式为：Loc(aij)=Loc(a11)+(i-1)*n+(j-1)*k；以列为主序优先存储的地址计算公式为：Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*karr2,2-arr1,1=(1*n+1)*k=(n+1)*k2.某研究机构有 n 名研究人员(n2)，其每个人
18、都与一名以上的同事有过研究项目合作关系，那么用_结构表示该机构研究人员间的项目合作关系较为合适。A树 B图 C栈 D队列（分数：2.00）A.B. C.D.解析：解析 图是比树结构更复杂的一种数据结构。在图结构中，任意两个节点之间都可能有直接的关系，一个节点的前驱和后继的数目是没有限制的。图结构被用于描述各种复杂的数据对象。而在树结构中，除根节点没有前驱节点外，其余的每个节点只有唯一的一个前驱节点和多个后继结点。因此，题目中描述的关系用图结构表示较为合适。3.以下关于字符串的叙述中，正确的是_。A包含任意个空格字符的字符串称为空串B仅包含一个空格字符的字符串称为空串C字符串的长度是指串中所含字
19、符的个数D字符串的长度是指串中所含非空格字符的个数（分数：2.00）A.B.C. D.解析：解析 串(string)是字符串的简称，是由零个或多个字符组成的有限序列，记为 S=“a123an”。含零个字符的串(Null String)称为空串，用 表示。其他串称为非空串。任何串中所含字符的个数称为该串的长度(或串长)。空串的长度为 0。串中任意个连续的字符组成的子序列称为子串。主串是包含子串的串。两个串相等，当且仅当两个串值相等，即长度、位置都相等。空格也是串集合中的一个元素，多个空格组成空格串。4.设循环队列 Q 的定义中有 rear 和 size 两个域变量，其中，rear 指示队尾元素之
20、后的位置，size 表示队列的长度，如图所示(队列长度为 3，队头元素为 x)。设队列的存储空间容量为 M，则队头元素的位置为_。（分数：2.00）A.B.C.D. 解析：解析 设队列的队头指针为 front，front 指向队头元素。队列的存储空间容量为 M，说明队列中最多可以有 M 个元素；队列的长度为 len，说明当前队列中有 len 个元素。则有：Q.rear=(Q.front+Q.len-1)%MQ.front=(Q.rear-Q.len+1+M)%M5.已知某二叉树的先序遍历序列为 ABCD，中序遍历序列为 BADC，则该二叉树的后序遍历序列为_。ABDCA BCDBA CDBCA
21、 DBCDA（分数：2.00）A. B.C.D.解析：解析 本题中，先序序列为 ABCD，因此 A 是树根结点，中序序列为 BADC，因此 B 是左子树上的结点，C 和 D 是右子树上的结点，且 D 是 C 的左孩子。因此，该二叉树的后序遍历序列为 BDCA。6.对于任意一个结点数为 n(n0)的二叉树，其高度 h_。A一定大于 n B一定小于 nC一定小于 log2n D一定大于 log2n（分数：2.00）A.B.C.D. 解析：解析 具有 n 个结点的完全二叉树的深度为 log2n+1，其高度 h 大 1 于 log2n。7._最不适用于处理序列已经正序有序的情况。A冒泡排序 B快速排序
22、 C归并排序 D直接插入排序（分数：2.00）A.B. C.D.解析：解析 快速排序是对冒泡排序的一种改进。先通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后分别对这两部分记录继续进行排序，使得整个序列有序。但是，若初始记录序列按关键字有序或基本有序时，即每次划分都是将序列划分为某一半序列的元素为 0 的情况，此时快速排序将蜕化为冒泡排序，算法的时间复杂度为 O(n2)。8.以下关于顺序查找和二分查找的叙述中，正确的是_。A顺序查找方法只适用于采用顺序存储结构的查找表B顺序查找方法只适用于采用链表存储结构的查找表C二分查找只适用于采用顺序存储结构
23、的查找表D二分查找只适用于采用循环链表存储结构的查找表（分数：2.00）A.B.C. D.解析：解析 顺序查找，又称线性查找，顺序查找的过程是从线性表的一端开始，依次逐个与表中元素的关键字值进行比较，如果找到其关键字与给定值相等的元素，则查找成功；若表中所有元素的关键字与给定值比较都不成功，则查找失败。顺序查找的方法对于顺序存储和链式存储方式的查找表都适用。折半查找是一种采用顺序存储结构的线性表进行查找的方法，也称为二分查找。在进行折半查找之前，线性表中的数据元素必须按照关键字的值升序或降序排列。折半查找的过程是先将给定值与有序线性表中间位置上的元素的关键字进行比较，若两者相等，则查找成功；若
24、给定值小于该元素的关键字，那么选取中间位置元素关键字值小的那部分元素作为新的查找范围，然后继续进行折半查找；如果给定值大于该元素的关键字，那么选取比中间位置元素关键字值大的那部分元素作为新的查找范围，然后继续进行折半查找，直到找到关键字与给定值相等的元素或查找范围中的元素数量为零时结束。9.以下关于图的存储结构的叙述中，正确的是_。A有向图的邻接矩阵一定是对称的B有向图的邻接矩阵一定是不对称的C无向图的邻接矩阵一定是对称的D无向图的邻接矩阵一定是不对称的（分数：2.00）A.B.C. D.解析：解析 将邻接矩阵中的 0，1 换成权值，就是图的邻接矩阵。无向图的邻接矩阵是对称矩阵；顶点vi 的度
25、是邻接矩阵中第 i 行(或第 i 列)的元素 1 之和。有向图的邻接矩阵不一定是对称矩阵；顶点 vi 的出度是邻接矩阵中第 i 行元素之和，入度是邻接矩阵中第 i 列的元素之和。10.设数组 a1n，1m(m1，n1)中的元素以行为主序存放，每个元素占用 1 个存储单元，则数组元素 ai,j(1in，1jm)相对于数组空间首地址的偏移量为_。A(i-1)*m+j-1 B(i-1)*n+j-1C(j-1)*m+i-1 D(i-1)*n+j-1（分数：2.00）A. B.C.D.解析：解析 本题考查数组元素的存储。二维数组的存储结构可分为以行为主序和以列为主序两种方法。设每个元素占用 L 个单元，
26、m、n 为数组的行数和列数，则以行为主序优先存储的地址计算公式为：Loc(aij)=Loc(a11)+(i-1)*n+(j-1)*L；以列为主序优先存储的地址计算公式为：Loc(aij)=Loc(a11)+(i-1)*m+(i-1)*L。因此，当数组以行主序存储时，ai,j-a1,1=(i-1)*m+j-1。11.线性表采用单链表存储结构时，访问表中元素的方式为_。A随机存取 B顺序存取 C索引存取 D散列存取（分数：2.00）A.B. C.D.解析：解析 线性表采用单链表作为存储结构时，只能顺序地访问元素，而不能对元素进行随机存取，但其优点是插入和删除操作部需要移动元素。12.有 n 个结点
27、的有序单链表中插入一个新结点并保持有序的运算的时间复杂度为_。AO(1) BO(logn) CO(n) DO(n2)（分数：2.00）A.B.C. D.解析：解析 有 n 个结点的有序单链表中插入一个新结点并保持有序的设计思想是：创建一个 data 域值为 x 的新结点*p，然后插入到 head 所指向的单链表的第 i 个结点之前。为保证插入正确有效，必须查找到指向第 i 个结点的前一个结点的指针，主要的时间耗费在查找上，因而在长度为 n 的线性单链表进行插入操作的时间复杂度为 O(n)。13.栈和队列的主要区别是_。A逻辑结构不同 B存储结构不同C基本运算数目不同 D插入运算和删除运算的要求
28、不同（分数：2.00）A.B.C.D. 解析：解析 栈是只能在表的一端进行捅入、删除的线性表。栈中允许插入、删除的一端称为栈顶，相反，栈中不允许插入、删除的一端称为栈底。处于栈顶位置的数据元素称为栈顶元素。队列(queue)是一种只允许在一端进行插入，而在另一端进行删除的线性表，是一种操作受限的线性表。在表中只允许进行插入的一端称为队尾(rear)，只允许进行删除的一端称为队头(front)。队列的插入操作通常称为入队列或进队列，而队列的删除操作则称为出队列或退队列。因此，栈和队列的主要区别是插入运算和删除运算的要求不同。14._不属于特殊矩阵。A对称矩阵 B对角矩阵 C稀疏矩阵 D三角矩阵（
29、分数：2.00）A.B.C. D.解析：解析 特殊矩阵是值相同或零元素在矩阵中的分布有一定的规律的矩阵，主要包括称矩阵、三角矩阵和对角矩阵。15.一个高度为 h 的满二叉树的结点总数为 2h-1，其每一层结点个数都达到最大值。从根结点开始顺序编号，每一层都从左到右依次编号，直到最后的叶子结点层为止。即根结点编号为 1，其左、右孩子结点编号分别为 2 和 3，再下一层从左到右的编号为 4、5、6、7，依此类推，那么，在一棵满二叉树中，埘于编号为 m 和 n 的两个结点，若 m=2n，则结点_。Am 是 n 的左孩子 Bm 是 n 的右孩予Cn 是 m 的左孩子 Dn 是 m 的右孩子（分数：2.
30、00）A. B.C.D.解析：解析 本题考查二叉树的基本概念和性质。高度为 4 的满二叉树如下图所示。16.在一棵非空二叉排序树中，关键字最小的结点的_。A左子树一定为空、右子树不一定为空B左子树不一定为空、右子树一定为空C左子树和右子树一定都为空D左子树和右子树一定都不为空（分数：2.00）A. B.C.D.解析：解析 本题考查二叉排序树的基本概念。在二叉排序树中，若根结点具有左子树，则左子树中所有结点的关键码均小于根结点的关键码：若根结点具有右子树，则右子树中所有结点的关键码均大于根结点的关键码；左、右子树也是二叉排序树。因此，在一个二叉排序树中，同层次结点从左向右排序，结点的关键码序列呈
31、递增排序。由此可见，关键字最小的结点的左予树一定为空，右子树不一定为空。17.若采用链地址法对关键字序列(74，10，23，6，45，38，18)构造哈希表(或散列表)，设敞列函数为H(Key)=Key%7(%表示整除取余运算)，则哈希表中地址为_的单链表长度为 0(即没有关键字被映射到这些哈希地址)。A0、1 和 2 B1、2 和 3 C1、3 和 5 D0、1 和 5（分数：2.00）A.B.C.D. 解析：解析 本题考查 Hash 表的构造。根据所设置的 Hash 函数，计算各关键字对应的 Hash 地址为：H(74)=74 MOD 7=4 H(10)=10 MOD 7=3 H(23)=
32、23 MOD 7=2 H(6)=6 MOD 7=6H(45)=45 MOD 7=3 H(38)=38 MOD 7=3 H(18)=18 MOD 7=4则 Hash 表中地址为 0、1 和 5 的单链表长度为 0。18.有 6 个顶点的图 G 的邻接表如下所示，以下关于图 G 的叙述中，正确的是_。（分数：2.00）A.B. C.D.解析：解析 若图中每条边都是有方向的，则该图称为有向图。由图 G 所示的邻接表可以看出，在各顶点间的弧都是有方向的，因此 G 是有向图。该图中共存在 9 条弧，如下表所示。起点终点弧权(Vi)(Vj)值V1 V3 12V2 V1 15V2 V4 13V3 V4 21
33、V3 V5 15V3 V6 15V4 V5 16V5 V2 18V5 V6 1519.单链表不具有的特点是_。A插入、删除运算不需要移动元素B可随机访问链表中的任一元素C不必事先估计存储空间值D所需存储空间量与线性表长度成正比（分数：2.00）A.B. C.D.解析：解析 本题考查的是单链表的相关知识。单链表是单向的即他只可以访问下一级链表的指针，而双向链表是在单链表的基础上加上了反向指针。循环链表是闭合的，结构和单链表相似，但是尾指向首。单链表的特点有插入、删除运算不需要移动元素，不必事先估计存储空间值，所需存储空间量与线性表长度成正比。可随机访问链表中的任一元素是顺序表的特点，故选择 B。
34、20.不适合采用栈结构的是_。A判断一个表达式中的括号是否匹配B判断一个字符串是否是中心对称C按照深度优先的方式后序遍历二叉树D按照层次顺序遍历二叉树（分数：2.00）A.B.C.D. 解析：解析 本题考查的是栈的相关知识。栈是只能在某一端插入和删除的特殊线性表。栈就是一种类似桶堆积物品的数据结构，允许进行删除和插入的一端称栈顶，另一端称栈底，不含任何元素的栈称为空栈。栈读取数据是连续读取的，判断一个表达式中的括号是否匹配与判断一个字符串是否是中心对称都可以用栈的结构，按深度优先的方式遍历二叉树也是按线性数据表按顺序连续遍历，所以可以采用栈结构，而按照层次顺序遍历二叉树不是线性数据表连续的读取
35、数据，所以不能采用栈的结构。故选择 D。21.设有字符串 S 和 P，串的模式匹配是指_。A确定 P 在 S 中首次出现的位置 B将 S 和 P 连接起来C将 S 替换为 P D比较 S 和 P 是否相同（分数：3.00）A. B.C.D.解析：解析 本题考查的是串的模式匹配算法。串的模式匹配算法的目的是确定主串中所含子串第一次出现的位置(定位)，分为 BF 算法利 KMP 算法。BF 算法的设计思想：编写函数 Index(S，T，pos)函数，将主串 S 的第 pos 个字符和模式 P 的第 1 个字符比较，若相等，继续逐个比较后续字符；若不等，从主串 S的下一个字符(pos+1)起，重新与
36、 P 第一个字符比较，直到主串 S 的一个连续子串字符序列与模式 P 相等，返回值为 S 中与 P 匹配的子序列第一个字符的序号，即匹配成功，否则，匹配失败，返回值 0。故选择A。22.以下关于特殊矩阵和稀疏矩阵的叙述中，正确的是_。A特殊矩阵适合采用双向链表存储，稀疏矩阵适合采用单向链表存储B特殊矩阵的非零元素分布有规律，可以用一维数组进行压缩存储C稀疏矩阵的非零元素分布没有规律，只能用二维数组压缩存储D稀疏矩阵的非零元素分布没有规律，只能用双向链表进行压缩存储（分数：3.00）A.B. C.D.解析：解析 本题考查的是特殊矩阵与稀疏矩阵的相关概念。稀疏矩阵式指该矩阵中非零元素远远小于矩阵元
37、素的个数，而非零元素的排布又没有规律，则称该矩阵为稀疏矩阵。稀疏矩阵的存储过程：(1)压缩为三元组表，(2)存储三元组表，以顺序表存储或链式存储。只有当矩阵中非零元素个数 s 满足sm*n 时，方可采用三元组顺序表或十字链表存储。特殊矩阵是指非零元素或领域苏的分布有一定规律的矩阵，为了节省存储空间，特别是在高阶矩阵的情况下，可以利用特殊矩阵的规律，对它们进行压缩存储。故选择 B。23.已知某二叉树的先序遍历序列为 ABDCEFG、中序遍历序列为 BDACFGE，则该二叉树的层数为_。A3 B4 C5 D6（分数：3.00）A.B.C. D.解析：解析 本题考查的是二叉树遍历的相关知识。根据二叉
38、树的先序遍历和中序遍历的结果可以得出该二叉树为：24.在一棵非空的二叉排序树中，关键字最大的结点的_。A左子树一定为空，右子树不一定为空B左子树不一定为空，右子树一定为空C左子树和右子树一定都为空D左子树和右子树一定都不为空（分数：3.00）A.B. C.D.解析：解析 本题考查的是_叉树的关键字的相关知识。我们根据一个实例来分析下二叉树关键字值最大的结点的存储位置有何特点。以序列(50,72,43,85,75,20,.35,45,65,30)为例，最大结点 85 的位置有两种情形，分别如下图所示。25.为实现快速排序算法，待排序列适合采用_。A顺序存储 B链式存储 C散列存储 D索引存储（分
39、数：3.00）A. B.C.D.解析：解析 本题考查的是排序算法。待排序列只有采用数组(顺序表)存储，可以通过地址直接访问到数据，才一能实现快速排序算法。故选择 A。26.若某无向图具有 n 个顶点、e 条边，则其邻接矩阵中值为 0 的元素个数为_。Ae B2e Cn*n-2e Dn-2e（分数：3.00）A.B.C. D.解析：解析 邻接矩阵是表示顶点之间相邻关系的矩阵。设 G=(V,E)是一个图，其中 v=v1,v2,vn。G的邻接矩阵是一个具有下列性质的 n 阶方阵：对无向图而言，邻接矩阵一定是对称的，而且对角线一定为零，有向图则不一定如此。在无向图中，任一顶点 i 的度为第 i 列所有
40、元素的和，在有向图中顶点 i的出度为第 i 行所有元素的和，而入度为第 i 列所有元素的和。用邻接矩阵法表示图共需要 n2 个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需要 n(n-1)/2 个空间。从邻接矩阵的定义可分析得出：含有 n 个顶点的图的邻接矩阵是n2 阶方阵，对无向图而言，邻接矩阵一定是对称的，如果该图无环，则对角线元素为 0，两顶点之间有边相连，相应位置的元素为 1，无边相连为 0，所以其邻接矩阵中值为 0 的元素个数为 n*n-2e，故选择C。27.以下关于程序流程图、N-S 盒图和决策表的叙述中，错误的是
41、_。AN-S 盒图可以避免随意的控制转移BN-S 盒图可以同时表示程序逻辑和数据结构C程序流程图中的控制流可以任意转向D决策表适宜表示多重条件组合下的行为（分数：3.00）A. B.C.D.解析：解析 在 N-S 图中，每个处理步骤用一个盒子表示。盒子可以嵌套。盒子只能从上头进入，从下头走出，除此之外别无其他出入口，所以盒图限制了随意的控制转移，保证了程序的良好结构。28.以下关于哈希表的叙述中，错误的是_。A哈希表中元素的存储位置根据该元素的关键字值计算得到B哈希表中的元素越多，插入一个新元素时发生冲突的可能性就越小C哈希表中的元素越多，插入一个新元素时发生冲突的可能性就越大D哈希表中插入新
42、元素发生冲突时，需要与表中某些元素进行比较（分数：3.00）A.B. C.D.解析：解析 当选择某个哈希函数后，不同的关键字可能与同一个哈希地址相对应，这种现象称为冲突。哈希表中的元素越多，当插入一个新元素时，哈希地址出现冲突的可能性就越大。下三角矩阵 A08,08如下图所示，若将其下三角元素(即行下标不小于列下标的所有元素)按列压缩存储在数组 M0m中，即 A0,0存储在 M0、A1,0存储在 M1、A2,0存储在 M2，A8,8存储在 M44，则元素 A5,5存储在_。若将其下三角元素按行压缩存储在数组 M0m中，即 A0,0存储在 M0、A1,0存储在 M1、A1,1存储在 M2，A8,
43、8存储在 M44，则元素 A5,5存储在_。（分数：6.00）(1).AM15 BM20 CM35 DM39（分数：3.00）A.B.C. D.解析：(2).AM15 BM20 CM35 DM39（分数：3.00）A.B. C.D.解析：解析 若按列压缩：由 A0,0存储在 M0、A1,0存储在 M1、A2,0存储在 M2,A8,8存储在 M44，可推出，第一列共有 9 个元素，以此可计算出，A5,5存储在 M35。若按行压缩：上(下)三角矩阵是指矩阵的下(上)三角元素取值相同，设此取值为常数 C(一般为 0)，则三角矩阵只需存储常数 C和上(下)三角中的数据元素即可。故其压缩存储方式与对称矩
44、阵相同，只不过多出一个常数的存储空间。对于任意给定一组下标(i,j)，均可在 sa 中找到矩阵元 aij，反之，对所有的 k=0,1,2,n(n+1)/2-1，都能确定 sak中的元在矩阵中的位置(i,j)。n 阶对称矩阵 A 的压缩存储如下所示：29.对 n 个元素的有序表 A1n进行二分(折半)查找，则成功查找到表中的任意一个元素时，最多与 A中的_个元素进行比较。An-1 Bn/2 C(log 2n)-1 D(log 2n)+1（分数：3.00）A.B. C.D.解析：30.某二叉树为单枝树(即非叶子节点只有一个孩子节点)且具有 n 个节点(n1)则该二叉树_。A共有 n 层，每层有一个
45、节点B共有 log2n 层，相邻两层的节点数正好相差一倍C先序遍历序列与中序遍历序列相同D后序遍历序列与中序遍历序列相同（分数：3.00）A.B.C.D. 解析：31.以下应用中，必须采用栈结构的是_。A使一个整数序列逆转 B递归函数的调用和返回C申请和释放单链表中的节点 D装入和卸载可执行程序（分数：3.00）A.B. C.D.解析：32.某图的邻接矩阵如下所示，则该图为_。ABCD （分数：3.00）A.B.C. D.解析：33.在直接插入排序、冒泡排序、简单选择排序和快速排序方法中，能在第一趟排序结束后就得到最大(或最小)元素的排序方法是_。A冒泡排序和快速排序 B直接插入排序和简单选择
46、排序C冒泡排序和简单选择排序 D直接插入排序和快速排序（分数：3.00）A.B.C. D.解析：解析 冒泡排序第一趟排序结束后，将关键字最大(或最小)的记录安置到最后一个记录的位置上。简单排序：在进行每趟排序时，从无序的记录中选择出关键字最小(或最大)的记录，将其插入到有序序列(初始时为空)的尾部。快速排序：第一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，但并未将其中最小(或最大)的记录选择出来。直接插入排序：是将一个记录直接插入已排好的有序表中，得到一个新的、记录数增 1 的有序表，并没有比较最大(或最小)关键字。34.现需要将数字 2 和 7 分别填入 6 个空格中的 2 个(每个空格只能填入一个数字)，已知第 1 格和第 2 格不能填 7，第 6 格不能填 2，则共有_种填法。A12 B16 C17 D20（分数：3.00）A.B.C. D.解析：解析 总共有35.许多工作需要用曲线来拟合平面上一批离散的点，以便于直观了解趋势，也便于插值和预测。例如，对平面上给定的 n 个离散点(
