【计算机类职业资格】软件设计师-数据结构与算法(三)及答案解析.doc

1、软件设计师-数据结构与算法(三)及答案解析(总分：128.00，做题时间：90 分钟)一、单项选择题(总题数：109，分数：128.00)由权值为 29，12，15，6，23 的 5 个叶子结点构造的哈夫曼树为 (57) ，其带权路径长度为 (58) 。（分数：2.00）A.B.C.D.A.85B.188C.192D.222简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图 G 有 n 个结点，其邻接矩阵为A1n，1n，且压缩存储在 B1k中，则 k 的值至少为 (20) 。若按行压缩存储对称矩阵的上三角元素，则当 n 等于 10 时，边(V6，V3)的信息存储在 B (21) 中。

2、（分数：2.00）(1). （分数：1.00）A.B.C.D.A.18B.19C.20D.211.对 n 个元素的有序表 A1n进行顺序查找，其成功查找的平均查找长度(即在查找表中找到指定关键码的元素时，所进行比较的表中元素个数的期望值)为_。（分数：1.00）A.nB.(n+1)/2C.log2nD.n22.广义表中的元素可以是原子，也可以是表，因此广义表的适用存储结构是_。（分数：1.00）A.链表B.静态数组C.动态数组D.散列表3.将一个无序序列中的元素依次插入到一棵_，并进行中序遍历，可得到一个有序序列。（分数：1.00）A.完全二叉树B.最小生成树C.二叉排序树D.最优二叉树4.设

3、循环队列 Q 的定义中有 rear 和 len 两个域变量，其中 rear 表示队尾元素的指针，len 表示队列的长度，如图 1-9 所示(队列长度为 3，队头元素为 e)。设队列的存储空间容量为 M，则队头元素的指针为_。（分数：1.00）A.B.C.D.利用贪心法求解 0-1 背包问题时， (27) 能够确保获得最优解。用动态规划方法求解 0-1 背包问题时，将“用前 i 个物品来装容量是 X 的背包”的 0-1 背包问题记为 KNAP(1，i，X)，设 fi(X)是 KNAP(1，i，X)最优解的效益值，第 j 个物品的重量和放入背包后取得效益值分别为 Wj和 pj(j=1n)。则依次求

4、解 f0(X)4，f 1(X)，f n(X)的过程中使用的递推关系式为 (28) 。（分数：2.00）A.优先选取重量最小的物品B.优先选取效益最大的物品C.优先选取单位重量效益最大的物品D.没有任何准则A.B.fi(X)=minfi-1(X)，f i-1(X)+piC.fi(X)=maxfi-1(X)，f i-1(X-Wi)+piD.fi(X)=minfi-1(X-Wi)，f i-1(X-Wi)+piE. Df i(X)=maxfi-1(X-Wi)，f i-1(X)+pi5.以比较为基础的排序算法在最坏情况下的计算时间下界为_。（分数：1.00）A.O(n)B.O(n2)C.O(log2n)

5、D.O(nlog2n)6.若将某有序树丁转换为二叉树 T1，则 T 中结点的后(根)序序列就是 T1 中结点的_遍历序列。例如，如图 1-8(a)所示的有序树转化为二叉树后如图 1-8(b)所示。（分数：1.00）A.B.C.D.7.已知某二叉树的中序序列为 CBDAEFI，先序序列为 ABCDEFI，则该二叉树的高度为_。（分数：1.00）A.2B.3C.4D.58.若对一个链表最常用的操作是在末尾插入结点和删除尾结点，则采用仅设尾指针的单向循环链表(不含头结点)时，_。（分数：1.00）A.插入和删除操作的时间复杂度都为 O(1)B.插入和删除操作的时间复杂度都为 O(n)C.插入操作的时

6、间复杂度为 O(1)，删除操作的时间复杂度为 O(n)D.插入操作的时间复杂度为 O(n)，删除操作的时间复杂度为 O(1)9.设商店有 10 元、5 元、2 元和 1 元的零币，每种零币的数量充足。售货员给顾客找零钱时，零币的数量越少越好。例如给顾客找零 29 元：先选 2 张 10 元币，然后选择 1 张 5 元币，再选择两张 2 元币。以上的找零钱方法采用了_策略。（分数：1.00）A.分治B.贪心C.动态规划D.回溯10.对 n 个元素的数组进行_，其平均时间复杂度和最坏情况下的时间复杂度都是 O(nlogn)。（分数：1.00）A.希尔排序B.快速排序C.堆排序D.选择排序对于具有

7、n 个元素的一个数据序列，若只需得到其中第 k 个元素之前的部分排序，最好采用 (47) ，使用分治(Divide and Conquer)策略的是 (48) 算法。（分数：2.00）A.希尔排序B.直接插入排序C.快速排序D.堆排序A.冒泡排序B.插入排序C.快速排序D.堆排序以下关于快速排序算法的描述中，错误的是 (104) 。在快速排序过程中，需要设立基准元素并划分序列来进行排序。若序列由元素(12，25，30，45，52，67，85)构成，则初始排列为 (105) 时，排序效率最高(令序列的第一个元素为基准元素)。（分数：2.00）A.快速排序算法是不稳定的排序算法B.快速排序算法在最

8、坏情况下的时间复杂度为 O(nlgn)C.快速排序算法是一种分治算法D.当输入数据基本有序时，快速排序算法具有最坏情况下的时间复杂度A.45，12，30，25，67，52，85B.85，67，52，45，30，25，12C.12，25，30，45，52，67，85D.45，12，25，30，85，67，5211.一个具有 n(n0)个顶点的连通无向图至少有_条边。（分数：1.00）A.n+1B.nC.n/2D.n-112.表达式“X=(A+B)(C-D/E)”的后缀表示为_。（分数：1.00）A.XAB+CDE/-x=B.XAB-C-DE/x=C.XAB+CDE-/x=D.NAB-CD-E/x

9、=13._不能保证求得 0-1 背包问题的最优解。（分数：1.00）A.分支限界法B.贪心算法C.回溯法D.动态规划策略14.由权值为 9，2，5，7 的 4 个叶子结点构造一棵哈夫曼树，该树的带权路径长度为_。（分数：1.00）A.23B.37C.44D.4615.对于关键字序列(26，25，72，38，8，18，59)，采用散列函数 H(Key)=Key mod 13 构造散列表(哈希表)。若采用线性探测的开放定址法解决冲突(顺序地探查可用存储单元)，则关键字 59所在散列表中的地址为_。（分数：1.00）A.6B.7C.8D.916.表达式 a*(b+c)-d 的后缀表达式为_。（分数：

10、1.00）A.abcd*+-B.abc+*d-C.abc*+d-D.-+*abcd已知一个线性表(16，25，35，43，51，62，87，93)，采用散列函数 H(Key)=Key mod 7 将元素散列到表长为 9 的散列表中。若采用线性探测的开放定址法解决冲突(顺序地探查可用存储单元)，则构造的哈希表为 (70) ，在该散列表上进行等概率成功查找的平均查找长度为 (71) (为确定记录在查找表中的位置，需和给定关键字值进行比较的次数期望值称为查找算法在查找成功时的平均查找长度)。（分数：2.00）(1).(1)0 1 2 3 4 56 7 83543165125 628793(2)0 1

11、 2 3 4 5 6 7 83543169325516287(3)0 1 2 3 4 5 6 7 83543165125876293(4)0 1 2 3 4 5 6 7835431651258762 93（分数：1.00）A.(1)B.(2)C.(3)D.(4)A.(5*1+2+3+6)/8B.(5*1+2+3+6)/9C.(8*1)/8D.(8*1)/9对于二叉查找树(Binary Search Tree)，若其左子树非空，则左子树上所有结点的值均小于根结点的值；若其右子树非空，则右子树上所有结点的值均大于根结点的值；左、右子树本身就是两棵二叉查找树。因此，对任意一棵二叉查找树进行 (64)

12、 遍历可以得到一个结点元素的递增序列。在具有 n 个结点的二叉查找树上进行查找运算，在最坏情况下的算法复杂度为 (65) 。（分数：2.00）A.先序B.中序C.后序D.层序A.O(n2)B.O(nlog2n)C.O(log2n)D.O(n)17.栈是一种按“后进先出”原则进行插入和删除操作的数据结构，因此，_必须用栈。（分数：1.00）A.实现函数或过程的递归调用及返回处理时B.将一个元素序列进行逆置时C.链表结点的申请和释放D.可执行程序的装入和卸载18.设一个包含 N 个顶点、E 条边的简单无向图采用邻接矩阵存储结构(矩阵元素 Aij等于1/0 分别表示顶点 i 与顶点 j 之间有/无边

13、)，则该矩阵中的非零元素数目为_。（分数：1.00）A.NB.EC.2ED.N+E19.若一个问题既可以用迭代方式也可以用递归方式求解，则_方法具有更高的时空效率。（分数：1.00）A.迭代B.递归C.先递归后迭代D.先迭代后递归20.某双向链表中的结点如图 1-4 所示，删除 t 所指结点的操作为_。（分数：1.00）A.B.C.D.21.无向图中一个顶点的度是指图中_。（分数：1.00）A.通过该顶点的简单路径数B.通过该顶点的回路数C.与该顶点相邻的顶点数D.与该顶点连通的顶点数22.对于长度为 m(m1)的指定序列，通过初始为空的一个栈、一个队列后，错误的叙述是_。（分数：1.00）A

14、.若入栈和入队的序列相同，则出栈序列和出队序列可能相同B.若入栈和入队的序列相同，则出栈序列和出队序列可以互为逆序C.入队序列与出队序列关系为 1:1，而入栈序列与出栈序列关系是 1:n(n1)D.入栈序列与出栈序列关系为 1:1，而入队序列与出队序列关系是 1:n(n1)23.设某算法的计算时间可用递推关系式 T(n)=2T(n/2)+n 表示，则该算法的时间复杂度为_。（分数：1.00）A.O(lgn)B.O(nlgn)C.O(n)D.O(n2)24.某算法的时间复杂度表达式为 T(n)=an2+bnlgn+cn+d，其中，n 为问题的规模，a、b、c 和 d为常数，用 O 表示其渐近时间

15、复杂度为_。（分数：1.00）A.O(n2)B.O(n)C.O(nlgn)D.O(1)25.利用动态规划方法求解每对结点之间的最短路径问题(all pairs shortest path problem)时，设有向图 G=V,E共有 n 个结点，结点编号 1n，设 C 是 G 的成本邻接矩阵，D k(i,j)即为图G 中结点 i 到 j 并且不经过编号比 k 还大的结点的最短路径长度(D n(i,j)即为图 G 中结点 i 到 j的最短路径长度)，则求解该问题的递推关系式为_。（分数：1.00）A.Dk(i,j)=Dk-1(i,j)+C(i,j)B.Dk(i,j)=minDk-1(i,j),D

16、k-1(i,j)+C(i,j)C.Dk(i,j)=Dk-1(i,k)+Dk-1(k,j)D.Dk(i,j)=minDk-1(i,j),Dk-1(i,k)+Dk-1(k,j)26.给定一个有 n 个元素的有序线性表。若采用顺序存储结构，则在等概率前提下，删除其中的一个元素平均需要移动_个元素。（分数：1.00）A.(n+1)/2B.n/2C.(n-1)/2D.127.为了便于存储和处理一般树结构形式的信息，常采用孩子一兄弟表示法将其转换成二又树(左子关系表示父子，右子关系表示兄弟)，与图 1-3 所示的树对应的二叉树是_。（分数：1.00）A.B.C.D.28.下面 C 程序段中“count+”

17、语句执行的次数为_。for(int i=1；i=11；i*=2)for(int j=1；j=I；j+)count+；（分数：1.00）A.15B.16C.31D.3229.在平衡二叉树中，_。（分数：1.00）A.任意结点的左、右子树结点数目相同B.任意结点的左、右子树高度相同C.任意结点的左、右子树高度之差的绝对值不大于 1D.不存在度为 1 的结点30.对于二维数组 a04，15，设每个元素占 1 个存储单元，且以列为主序存储，则元素a2，2相对于数组空间起始地址的偏移量是_。（分数：1.00）A.5B.7C.10D.15求解该算法的计算时间时，仅考虑算法 Move 所做的计算为主要计算，

18、且 Move 为常数级算法。则算法 F 的计算时间 T(n)的递推关系式为 (25) ；设算法 Move 的计算时间为 k，当 n=4 时，算法F 的计算时间为 (26) 。（分数：2.00）A.T(n)=T(n-1)+1B.T(n)=2T(n-1)C.T(n)=2T(n-1)+1D.T(n)=2T(n+1)+1A.14kB.15kC.16kD.17k31.邻接矩阵和邻接表是图(网)的两种基本存储结构，对于具有 n 个顶点、e 条边的图，_。（分数：1.00）A.进行深度优先遍历运算所消耗的时间与采用哪一种存储结构无关B.进行广度优先遍历运算所消耗的时间与采用哪一种存储结构无关C.采用邻接表表

19、示图时，查找所有顶点的邻接顶点的时间复杂度为 O(n*e)D.采用邻接矩阵表示图时，查找所有顶点的邻接顶点的时间复杂度为 O(n2)32.对于 n(n0)个元素构成的线性序列 L，在_时适合采用链式存储结构。（分数：1.00）A.需要频繁修改 L 中元素的值B.需要频繁地对 L 进行随机查找C.需要频繁地对 L 进行删除和插入操作D.要求 L 存储密度高33.给定一组长度为 n 的无序序列，将其存储在一维数组 a0n-1中。现采用如下方法找出其中的最大元素和最小元素：比较 a0和 an-1，若 a0较大，则将二者的值进行交换；再比较a1和 an-2，若 a1较大，则交换二者的值；然后依次比较

20、a2和 an-3、a3和 an-4、，使得每一对元素中的较小者被交换到低下标端。重复上述方法，在数组的前 n/2 个元素中查找最小元素中在后 n/2 个元素中查找最大元素，从而得到整个序列的最小元素和最大元素。上述方法采用的算法设计策略是_。（分数：1.00）A.动态规划法B.贪心法C.分治法D.回溯法34.要在 88 的棋盘上摆放 8 个“皇后”，要求“皇后”之间不能发生冲突，即任何两个“皇后”不能在同一行、同一列和相同的对角线上，则一般采用_来实现。（分数：1.00）A.分治法B.动态规划法C.贪心法D.回溯法35.在_存储结构中，数据结构中元素的存储地址与其关键字之间存在某种映射关系。（

21、分数：1.00）A.顺序(Sequence)B.链表(Link)C.索引(Index)D.散列(Hash)36._算法策略与递归技术的联系最弱。（分数：1.00）A.动态规划B.贪心C.回溯D.分治某工程计划如图 1-6 所示，各个作业所需的天数如下表所示，设该工程从第 0 天开工，则该工程的最短工期是 (52) 天，作业 J 最迟应在第 (53) 天开工。（分数：2.00）A.B.C.D.A.B.C.D.为了在状态空间树中 (11) ，可以利用 LC-检索(Least Cost Search)快速找到一个答案结点。在进行 LC-检索时，为避免算法过分偏向于纵深检查，应该 (12) 。（分数：

22、2.00）A.找出任一个答案结点B.找出所有的答案结点C.找出最优的答案结点D.进行遍历A.使用精确的成本函数 c(.)来做 LC-检索B.使用广度优先检索C.使用深度优先检索D.在成本估计函数37.己知一个线性表(38，25，74，63，52，48)，假定采用散列函数 h(key)=key % 7 计算散列地址，并散列存储在散列表 A0，6中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为_。（分数：1.00）A.1.5B.1.7C.2.0D.2.338.具有 n 个顶点、e 条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为_。（分

23、数：1.00）A.O(n2)B.O(e2)C.O(n*e)D.O(n+e)39.利用逐点插入法建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，查找元素 30 要进行_次元素间的比较。（分数：1.00）A.4B.5C.6D.740.分治算法设计技术_。（分数：1.00）A.一般由三个步骤组成：问题划分、递归求解、合并解B.一定是用递归技术来实现C.将问题划分为 k 个规模相等的子问题D.划分代价很小而合并代价很大41.对于哈希表，如果将装填因子定义为表中装入的记录数与表的长度之比，那么向表中加入新记录时，_。（分数：1.00）A.装填因子的值随冲突次数

24、的增加而递减B.装填因子越大发生冲突的可能性就越大C.装填因子等于 1 时不会再发生冲突D.装填因子低于 0.5 时不会发生冲突42.表达式“(a+b)*(c-d)”的后缀表示为_。（分数：1.00）A.ab+cd-*B.abcd+-*C.ab+*cd-D.abcd*+-43.某算法的时间复杂度可用递归式 表示，若用 表示，则正确的是_（分数：1.00）A.B.C.D.44.设 L 为广义表，将 head(L)定义为取非空广义表的第一个元素，tail(L)定义为取非空广义表除第一个元素外剩余元素构成的广义表。若广义表 L=(x，y，z)，a，(u，t，w)，则从 L 中取出原子项 y 的运算是

25、_。（分数：1.00）A.head(tail(tail(L)B.tail(head(head(L)C.head(tail(head(L)D.tail(tail(head(L)45.以下的算法设计方法中，_以获取问题最优解为目标。（分数：1.00）A.回溯法B.分治法C.动态规划D.递推46.在如图 1-7 所示的平衡二叉树(树中任一结点的左右子树高度之差不超过 1)中，结点 A 的右子树 AR 高度为 h，结点 B 的左子树 BL 高度为 h，结点 C 的左子树 CL、右子树 CR 高度都为 h-1。若在 CR 中插入一个结点并使得 CR 的高度增加 l，则该二叉树_。（分数：1.00）A.B

26、.C.D.一个具有 m 个结点的二叉树，其二叉链表结点(左、右孩子指针分别用 left 和 right 表示)中的空指针总数必定为 (80) 个。为形成中序(先序、后序)线索二叉树，现对该二叉链表所有结点进行如下操作：若结点 p 的左孩子指针为空，则将该左指针改为指向 p 在中序(先序、后序)遍历序列的前驱结点；若 p 的右孩子指针为空，则将该右指针改为指向 p 在中序(先序、后序)遍历序列的后继结点。假设指针 s 指向中序(先序、后序)线索二叉树中的某结点，则 (81) 。（分数：2.00）A.m+2B.m+1C.mD.m-1A.s-right 指向的结点一定是 s 所指结点的直接后继结点B

27、.s-left 指向的结点一定是 s 所指结点的直接前驱结点C.从 s 所指结点出发的 right 链可能构成环D.s 所指结点的 left 和 right 指针一定指向不同的结点47.由元素序列(27，16，75，38，51)构造平衡二叉树，则首次出现的最小不平衡子树的根(即离插入结点最近且平衡因子的绝对值为 2 的结点)为_。（分数：1.00）A.27B.38C.51D.7548.若某算法在问题规模为 n 时，其基本操作的重复次数可由下式表示，则该算法的时间复杂度为_。（分数：1.00）A.O(n)B.O(n2)C.O(logn)D.O(nlogn)设栈 S 和队列 Q 的初始状态为空，元

28、素按照 a，b，c，d，e 的次序进入栈 S，当一个元素从栈中出来后立即进入队列 Q。若队列的输出元素序列是 c，d，b，a，e，则元素的出栈顺序是 (61) ，栈 S 的容量至少为 (62) 。（分数：2.00）A.a，b，c，d，eB.e，d，c，b，aC.c，d，b，a，eD.e，a，b，d，cA.2B.3C.4D.549.下面关于图(网)的叙述，正确的是_。（分数：1.00）A.连通无向网的最小生成树中，顶点数恰好比边数多 1B.若有向图是强连通的，则其边数至少是顸点数的 2 倍C.可以采用 AOV 网估算工程的工期D.关键路径是 AOE 网中源点至汇点的最短路径50.对 n 个元素的

29、有序表 A1n进行二分(折半)查找(除 2 取商时向下取整)，查找元素 Ai(1in)时，最多与 A 中的_个元素进行比较。（分数：1.00）A.nB.log2n-1C.n/2D.log2n+151.若总是以待排序列的第一个元素作为基准元素进行快速排序，那么在最好情况下的时间复杂度为_。（分数：1.00）A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)对于求取两个长度为 n 的字符串的最长公共子序列(LCS)问题，利用 (35) 策略可以有效地避免子串最长公共子序列的重复计算，得到时间复杂度为 O(n2)的正确算法。串1，0，0，1，0，1，0，1和0，1，0，1，1，0，

30、1，1的最长公共子序列的长度为 (36) 。（分数：2.00）A.分治B.贪心C.动态规划D.分支限界A.3B.4C.5D.652.若排序前后关键字相同的两个元素相对位置不变，则称该排序方法是稳定的。_排序是稳定的。设求解某问题的递归算法如下：F(int n)if (n=1)Move(1)；elseF(n-1)；Move(n)；F(n-1)；（分数：1.00）A.归并B.快速C.希尔D.堆53.求单源点最短路径的迪杰斯特拉(Dijkstra)算法是按_的顺序求源点到各顶点的最短路径的。（分数：1.00）A.路径长度递减B.路径长度递增C.顶点编号递减D.顶点编号递增54.表达式“X=A+B(C

31、-D)/E”的后缀表示形式可以为_(运算符优先级相同时，遵循左结合的原则)。（分数：1.00）A.XAB+CDE/-x=B.XA+BC-dE/x=C.XABCd-xE/+=D.XABCDE+x-/=55.设某算法的计算时间表示为递推关系式 T(n)=T(n-1)+n(n0)及 T(0)=1，则该算法的时间复杂度为_。（分数：1.00）A.O(lgn)B.O(nlgn)C.O(n)D.O(n2)56.某一维数组中依次存放了数据元素 15，23，38，47，55，62，88，95，102，123，采用折半(二分)法查找元素 95 时，依次与_进行了比较。（分数：1.00）A.62，88，95B.6

32、2，95C.55，88，95D.55，9557.迪杰斯特拉(Diikstra)算法按照路径长度递增的方式求解单源点最短路径问题，该算法运用了_算法策略。（分数：1.00）A.贪心B.分而治之C.动态规划D.试探+回溯58.字符串采用链表存储方式时，每个结点存储多个字符有助于提高存储密度。若采用结点大小相同的链表存储串，则在串比较、求子串、串连接、串替换等串的基本运算中，_。（分数：1.00）A.进行串的比较运算最不方便B.进行求子串运算最不方便C.进行串连接最不方便D.进行串替换最不方便59.在最好和最坏情况下的时间复杂度均为 O(nlog2n)且稳定的排序方法是_。（分数：1.00）A.基数

33、排序B.快速排序C.堆排序D.归并排序60.若用 n 个权值构造一棵最优二叉树(哈夫曼树)，则该二叉树的结点总数为_。（分数：1.00）A.2nB.2n-1C.2n+1D.2n+261.与逆波兰式 ab+-c*d-对应的中缀表达式是_。（分数：1.00）A.a-b-c*dB.-(a+b)*c-dC.-a+b*c-dD.(a+b)*(-c-d)62.在 11 个元素的有序表 A111中进行折半查找( （分数：1.00）A.B.C.D.结点数目为 n 的二叉查找树(二叉排序树)的最小高度为 (40) ，最大高度为 (41) 。（分数：2.00）A.nB.n/2C.log2nD.A.nB.n/2C.

34、log2nD.斐波那契(Fibonacci)数列可以递归地定义为：（分数：2.00）A.B.C.D.A.B.C.D.63.在_中，任意一个结点的左、右子树的高度之差的绝对值不超过 1。（分数：1.00）A.完全二叉树B.二叉排序树C.线索二叉树D.最优二叉树已知一个二又树的先序遍历序列为、，中序遍历序列为、，则该二叉树的后序遍历序列为 (97) 。对于任意一棵二叉树，叙述错误的是 (98) 。（分数：2.00）A.、B.、C.、D.、A.由其后序遍历序列和中序遍历序列可以构造该二叉树的先序遍历序列B.由其先序遍历序列和后序遍历序列可以构造该二叉树的中序遍历序列C.由其层序遍历序列和中序遍历序列

35、可以构造该二叉树的先序遍历序列D.由其层序遍历序列和中序遍历序列不能构造该二叉树的后序遍历序列64.一个算法是对某类给定问题求解过程的精确描述，算法中描述的操作都可以通过将已经实现的基本操作执行有限次来实现。这句话说明算法具有_特性。（分数：1.00）A.有穷性B.可行性C.确定性D.健壮性65.对以下 4 个序列用直接插入排序方法由小到大进行排序时，元素比较次数最少的是_。（分数：1.00）A.89，27，35，78，41，15B.27，35，41，16，89，70C.15，27，46，40，64，85D.90，80，45，38，30，2566.循环链表的主要优点是_。（分数：1.00）A.

36、不再需要头指针了B.已知某个结点的位置后，能很容易找到它的直接前驱结点C.在进行删除操作后，能保证链表不断开D.从表中任一结点出发都能遍历整个链表67.下面关于二叉树的叙述，正确的是_。（分数：1.00）A.完全二叉树的高度 h 与其结点数 n 之间存在确定的关系B.在二叉树的顺序存储和链式存储结构中，完全二叉树更适合采用链式存储结构C.完全二叉树中一定不存在度为 1 的结点D.完全二叉树中必定有偶数个叶子结点68.已知某二叉树的中序、层序序列分别为 DBAFCE、FDEBCA，则该二叉树的后序序列为_。（分数：1.00）A.BCDEAFB.ABDCEFC.DBACEFD.DABECF在活动图

37、中，结点表示项目中各个工作阶段的里程碑，连接各个结点的边表示活动，边上的数字表示活动持续的时间。在下面的活动图 1-1 中，从 A 到 J 的关键路径是 (15) ，关键路径长度是 (16) ，从 E 开始的活动启动的最早时间是 (17) 。（分数：3.00）A.B.C.D.A.B.C.D.A.B.C.D.69.某一维数组中依次存放了数据元素 12，23，30，38，41，52，54，76，85，在用折半(二分)查找方法(向上取整)查找元素 54 时，所经历“比较”运算的数据元素依次为_。（分数：1.00）A.41，52，54B.41，76，54C.41，76，52，54D.41，30，76，

38、5470.对于 n 个元素的关键字序列 k1，k 2，k n，当且仅当满足关系 ki k2i且ki k2i+1(2in，2i+1 （分数：1.00）A.B.C.D.71.在二叉树的顺序存储中，每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系，因此可与三叉链表对应。若某二叉树共有 n 个结点，采用三叉链表存储时，每个结点的数据域需要 d 个字节，每个指针域占用 4 个字节，若采用顺序存储，则最后一个结点下标为 k(起始下标为 1)，那么_时采用顺序存储更节省空间。（分数：1.00）A.B.C.D.72.若有数组声明 a03，02，14，设编译时为 a 分配的存储空间首地址

39、为 base_a，且每个数组元素占据一个存储单元。当元素以行为序存放(即按 a0，0，1，a0，0，2，a0，0，3，a0，0，4，a0，1，1，a0，1，2，a3，2，4顺序存储)时，则数组元素 a2，2，2在其存储空间中相对 base_a 的偏移量是_。（分数：1.00）A.8B.12C.33D.4873._在其最好情况下的算法时间复杂度为 O(n)。（分数：1.00）A.插入排序B.归并排序C.快速排序D.堆排序74.下面关于查找运算及查找表的叙述，错误的是_。（分数：1.00）A.哈希表可以动态创建B.二叉排序树属于动态查找表C.二分查找要求查找表采用顺序存储结构或循环链表结构D.顺序

40、查找方法既适用于顺序存储结构，也适用于链表结构75.关于算法与数据结构的关系，_是正确的。（分数：1.00）A.算法的实现依赖于数据结构的设计B.算法的效率与数据结构无关C.数据结构越复杂，算法的效率越高D.数据结构越简单，算法的效率越高76.用插入排序和归并排序算法对数组3，1，4，1，5，9，6，5进行从小到大排序，则分别需要进行_次数组元素之间的比较。（分数：1.00）A.12，14B.10，14C.12，16D.10，1677. () 的邻接矩阵是一个对称矩阵。（分数：1.00）A.无向图B.AOV 网C.AOE 网D.有向图78.若二叉树的先序遍历序列为 ABDECF，中序遍历序列为

41、 DBEAFC，则其后序遍历序列为_。（分数：1.00）A.DEBAFCB.DEFBCAC.DEBCFAD.DEBFCA79.表达式(a-b)*(c+5)的后缀表示是_。（分数：1.00）A.a b c 5+*-B.a b-c+5*C.a b c-*5+D.a b-c 5+*80.拓扑序列是无环有向图中所有顶点的一个线性序列，图中任意路径中的各个顶点在该图的拓扑序列中保持先后关系，_为图 1-2 所示有向图的一个拓扑序列。（分数：1.00）A.B.C.D.81.在常用的描述二叉排序树的存储结构中，关键字值最大的结点_。（分数：1.00）A.左指针一定为空B.右指针一定为空C.左、右指针均为空D

42、.左、右指针均不为空82.归并排序采用的算法设计方法属于_。（分数：1.00）A.归纳法B.分治法C.贪心法D.回溯法83.下面关于哈夫曼树的叙述中，正确的是_（分数：1.00）A.哈夫曼树一定是完全二叉树B.哈夫曼树一定是平衡二叉树C.哈夫曼树中权值最小的两个结点互为兄弟结点D.哈夫曼树中左孩子结点小于父结点，右孩子结点大于父结点84.下面关于二叉排序树的叙述，错误的是_。（分数：1.00）A.对二叉排序树进行中序遍历，必定得到结点关键字的有序序列B.依据关键字无序的序列建立二叉排序树，也可能构造出单支树C.若构造二叉排序树时进行平衡化处理，则根结点的左子树结点数与右子树结点数的差值一定不超

43、过 1D.若构造二叉排序树时进行平衡化处理，则根结点的左子树高度与右子树高度的值一定不超过185.输入受限的双端队列是指元素只能从队列的一端输入，但可以从队列的两端输出，如图 1-5所示。若有 8，1，4，2 依次进入输入受限的双端队列，则得不到输出序列_。（分数：1.00）A.B.C.D.86.设下三角矩阵(上三角部分的元素值都为 0)A0n，0n如图 1-10 所示，将该三角矩阵的所有非零元素(即行下标不小于列下标的元素)按行优先压缩存储在容量足够大的数组 M中(下标从 1 开始)，则元素 Ai,j(0in，ji)存储在数组 M 的_中。（分数：1.00）A.B.C.D.87.下面关于栈和队列的叙述，错误的是_。（分数：1.00）A.栈和队列都是操作受限的线性表