下载掌阅APP，畅读海量书库
立即打开
1）对 n 个元素的有序表 A [1… n ]进行二分（折半）查找（除2取商时向下取整），查找元素 A [ i ]时，最多与 A 中的______个元素进行比较。
A. n
B.└log 2 n ┘-1
C. n /2
D.└log 2 n ┘+1
2）设有如图3-7所示的下三角矩阵 A [0…8，0…8]，将该三角矩阵的非零元素（即行下标不小于列下标的所有元素）按行优先压缩存储在数组 M [1… m ]中，则元素 A [ i ， j ]（0≤ i ≤8， j ≤ i ）存储在数组 M 的______中。
图3-7 三角矩阵
A.
B.
C.
D.
3）若用 n 个权值构造一棵最优二叉树（哈夫曼树），则该二叉树的节点总数为______。
A.2 n
B.2 n -1
C.2 n +1
D.2 n +2
4）栈是一种按“后进先出”原则进行插入和删除操作的数据结构，因此______必须用栈。
A.实现函数或过程的递归调用及返回处理时
B.将一个元素序列进行逆置
C.链表节点的申请和释放
D.可执行程序的装入和卸载
5）对以下4个序列用直接插入排序方法由小到大进行排序时，元素比较数最少的是______。
A.89,27,35,78,41,15
B.27,35,41,16,89,70
C.15,27,46,40,64,85
D.90,80,45,38,30,25
6）对于哈希表，如果将装填因子 a 定义为表中装入的记录数与表的长度之比，那么向表中加入新记录时______。
A. a 的值随冲突次数的增加而递减
B. a 越大，发生冲突的可能性就越大
C. a 等于1时不会再发生冲突
D. a 低于0.5时不会再发生冲突
7）用关键字序列10、20、30、40、50构造的二叉排序树（二叉查找树）为______。
A.
B.
C.
D.
8）若某算法在问题规模为 n 时基本操作的重复次数可由下式表示，则该算法的时间复杂度为______。
A. O ( n )
B. O ( n 2 )
C. O (log 2 n )
D. O ( n log 2 n )
9）若对一个链表最常用的操作是在末尾插入节点和删除尾节点，则采用仅设尾指针的单向循环链表（不含头节点）时______。
A.插入和删除操作的时间复杂度都为 O （1）
B.插入和删除操作的时间复杂度都为 O （ n ）
C.插入操作的时间复杂度为 O （1），删除操作的时间复杂度为 O （ n ）
D.插入操作的时间复杂度为 O （ n ），删除操作的时间复杂度为 O （1）
10）下面关于哈夫曼树的叙述中，正确的是______。
A.哈夫曼树一定是完全二叉树
B.哈夫曼树一定是平衡二叉树
C.哈夫曼树中权值最小的两个节点互为兄弟节点
D.哈夫曼树中左孩子节点小于父节点，右孩子节点大于父节点
11）______是图3-8的合法拓扑序列。
图3-8 有序图
A.654321
B.123456
C.563421
D.564213
12）某一维数组中依次存放了数据元素15，23，38，47，55，62，88，95，102，123，采用二分法查找元素95时，依次与______进行了比较。
A.62,88,95
B.62,95
C.55,88,95
D.55,95
13）已知一棵度为3的树（一个节点的度是指其子树的数目，树的度是指该树中所有节点的度的最大值）中有5个度为1的节点，4个度为2的节点，2个度为3的节点，那么，该树中的叶子节点数目为______。
A.10
B.9
C.8
D.7
14）某算法的时间复杂度可用递归式
表示，若用
O
表示该算法的渐近时间复杂度的紧致界，则正确的是______。
A. O ( n lg 2 n )
B. O ( n lg n )
C. O ( n 2 )
D. O ( n 3 )
15）下面的C程序段中，count++语句执行的次数为______。
A.15
B.16
C.31
D.32
16）______不能保证求得0/1背包问题的最优解。
A.分支限界法
B.贪心算法
C.回溯法
D.动态规划策略
17）对 n 个元素的有序表 A [ i ， j ]进行顺序查找，其成功查找的平均查找长度（即在查找表中找到指定关键码的元素时，所进行比较的表中元素个数的期望值）为______。
A. n
B.( n +1）/2
C.log 2 n
D. n 2
18）在______中，任意一个节点的左、右子树的高度之差的绝对值不超过1。
A.完全二叉树
B.二叉排序树
C.线索二叉树
D.最优二叉树
19）设一个包含 N 个顶点、 E 条边的简单无向图采用邻接矩阵存储结构（矩阵元素 A [ i ][ j ]等于1/0分别表示顶点 i 与顶点 j 之间有/无边），则该矩阵中的非零元素数目为______。
A. N
B. E
C.2 E
D. N + E
20）对于关键字序列（26，25，72，38，8，18，59），采用散列函数 H （Key）=Key mod13构造散列表（哈希表）。若采用线性探测的开放定址法解决冲突（顺序地探查可用存储单元），则关键字59所在散列表中的地址为______。
A.6
B.7
C.8
D.9
21）要在8×8的棋盘上摆放8个“皇后”，要求“皇后”之间不能发生冲突，即任何两个“皇后”不能在同一行、同一列和相同的对角线上，则一般采用______来实现。
A.分治法
B.动态规划法
C.贪心法
D.回溯法
22）分治算法设计技术______。
A.一般由三个步骤组成：问题划分、递归求解、合并解
B.一定是用递归技术来实现的
C.将问题划分为 k 个规模相等的子问题
D.划分代价很小，而合并代价很大
23）某算法的时间复杂度可用递归式
表示，若用
O
表示该算法的渐近时间复杂度的紧致界，则正确的是______。
A.
B. O ( n 2 )
C. O ( n )
D.
24）插入排序和归并排序算法对数组＜3，1，4，1，5，9，6，5＞进行从小到大排序，则分别需要进行______次数组元素之间的比较。
A.12,14
B.10,14
C.12,16
D.10,16
25）在KMP模式匹配算法中，需要求解模式串 p 的next函数值，其定义如下（其中， j 是字符在模式串中的序号）。对于模式串“ abaabaca ”，其next函数值序列为______。
A.01111111
B.01122341
C.01234567
D.01122334
26）对于线性表（由 n 个同类元素构成的线性序列），采用单向循环链表存储的特点之一是______。
A.从表中任意节点出发都能遍历整个链表
B.对表中的任意节点可以进行随机访问
C.对于表中的任意一个节点，访问其直接前驱和直接后继节点所用时间相同
D.第一个节点必须是头节点
27）一棵满二叉树的每一层节点个数都达到最大值，对其中的节点从1开始顺序编号，即根节点编号为1，其左、右孩子节点编号分别为2和3，再下一层从左到右的编号为4、5、6、7，以此类推，每一层都从左到右依次编号，直到最后的叶节点层为止，则用______可判定编号为 m 和 n 的两个节点是否在同一层。
A.log 2 m =log 2 n
B.└log 2 m ┘=└log 2 n ┘
C.└log 2 m ┘+1=└log 2 n ┘
D.└log 2 m ┘=└log 2 n ┘+1
28）______是由权值集合{8，5，6，2}构造的哈夫曼树。
A.
B.
C.
D.
29）迪杰斯特拉（Dijkstra）算法用于求解图上的单源点的最短路径。该算法按路径长度递增次序产生最短路径，从本质上说，该算法是一种基于______策略的算法。
A.分治
B.动态规划
C.贪心
D.回溯
30）在有 n 个无序无重复元素值的数组中查找第 i 小的数的算法描述如下：任意取一个元素 r ，用划分操作确定其在数组中的位置，假设元素 r 为第 k 小的数。若 i 等于 k ，则返回该元素值；若 i 小于 k ，则在划分的前半部分递归地进行划分操作找第 i 小的数，否则在划分的后半部分递归地进行划分操作找第 k-i 小的数。该算法是一种基于______策略的算法。
A.分治
B.动态规划
C.贪心
D.回溯
31）对于一个长度大于1且不存在重复元素的序列，令其所有元素依次通过一个初始为空的队列后，再通过一个初始为空的栈。设队列和栈的容量都足够大，一个序列通过队列（栈）的含义是序列的每个元素都入队（栈）和出队（栈）一次且仅一次。对于该序列在上述队列和栈上的操作，正确的叙述是______。
A.出队序列和出栈序列一定相同
B.出队序列和出栈序列一定互为逆序
C.入队序列与出队序列一定相同，入栈序列与出栈序列不一定相同
D.入栈序列与出栈序列一定互为逆序，入队序列与出队序列不一定互为逆序
32）在字符串的KMP模式匹配算法中，需要求解模式串 p 的next函数值，其定义如下。若模式串p为“ aaabaaa ”，则其next函数值为______。
A.0123123
B.0123210
C.0123432
D.0123456
33）若 n 2 、 n 1 、 n 0 分别表示一棵二叉树中度为2、度为1和叶节点的数目（节点的度定义为节点的子树数目），则对于任何一棵非空的二叉树______。
A. n 2 一定大于 n 1
B. n 1 一定大于 n 0
C. n 2 一定大于 n 0
D. n 0 一定大于 n 2
34）从存储空间的利用率角度来看，以下关于数据结构中图的存储的叙述，正确的是______。
A.有向图适合采用邻接矩阵存储，无向图适合采用邻接表存储
B.无向图适合采用邻接矩阵存储，有向图适合采用邻接表存储
C.完全图适合采用邻接矩阵存储
D.完全图适合采用邻接表存储
35）递增序列 A （ a 1 ， a 2 ，…， a n ）和 B （ b 1 ， b 2 ，…， b n ）的元素互不相同，若需将它们合并为一个长度为2 n 的递增序列，则当最终的排列结果为______时，归并过程中元素的比较次数最多。
A. a 1 , a 2 ,…, a n , b 1 , b 2 ,…, b n
B. b 1 , b 2 ,…, b n , a 1 , a 2 ,…, a n
C. a 1 , b 1 , a 2 , b 2 ,…, a i , b i ,…, a n , b n
D. a 1 , a 2 ,…, a i /2 , b 1 , b 2 ,…, b i /2 , a i /2+1 ,…, a n , b i /2+1 , b i /2+2 ,…, b n
36）某货车运输公司有一个中央仓库和 n 个运输目的地，每天要从中央仓库将货物运输到所有的运输目的地，到达每个运输目的地一次且仅一次，最后回到中央仓库。在两个地点 i 和 j 之间运输货物存在费用 c ij 。为求解旅行费用总和最小的运输路径，设计算法如下：首先选择离中央仓库最近的运输目的地1，然后选择离运输目的地1最近的运输目的地2……每次在未访问过的运输目的地中选择离当前运输目的地最近的运输目的地，最后回到中央仓库。该算法采用了 ① 算法设计策略，其时间复杂度为 ② 。
①A.分治
B.动态规划
C.贪心
D.回溯
②A. O ( n 2 )
B. O ( n )
C. O ( n log 2 n )
D. O (1)
37）现要对 n 个实数（仅包含正实数和负实数）组成的数组 A 进行重新排列，使得其中所有的负实数都位于正实数之前。求解该问题的算法的伪代码如下，则该算法的时间和空间复杂度分别为______。
A. O （ n ）和 O （ n ）
B. O （1）和 O （ n ）
C. O （ n ）和 O （1）
D. O （1）和 O （1）
38）在字符串的模式匹配过程中，如果模式串的每个字符依次和主串中一个连续的字符序列相等，则称为匹配成功。如果不能在主串中找到与模式串相同的子串，则称为匹配失败。在布鲁特-福斯模式匹配算法（朴素的或基本的模式匹配）中，若主串和模式串的长度分别为 n 和 m （且 n 远大于 m ），且恰好在主串末尾的 m 个字符处匹配成功，则在上述的模式匹配过程中，字符的比较次数最多为______。
A. n × m
B.( n-m +l)× m
C.( n-m -l)× m
D.( n-m )× n
39）若某二叉树的后序遍历序列为 KBFDCAE ，中序遍历序列为 BKEFACD ，则该二叉树为______。
A.
B.
C.
D.
40）在13个元素构成的有序序列 M [1…13]中进行二分查找（向下取整），若找到的元素为 M [4]，则被比较的元素依次为______。
A. M [7]、 M [3]、 M [5]、 M [4]
B. M [7]、 M [5]、 M [4]
C. M [7]、 M [6]、 M [4]
D. M [7]、 M [4]
41）拓扑排序是将有向图中的所有顶点排成一个线性序列的过程，并且该序列满足：若在AOV网中从顶点 v i 到 v j 有一条路径，则顶点 v i 必然在顶点 v j 之前。对于如图3-9所示的有向图，______是其拓扑序列。
图3-9 有向图
A.1234576
B.1235467
C.2135476
D.2134567
42）如图3-10所示为一棵 M 阶树， M 最有可能的值为______。
图3-10 M 阶树
A.1
B.2
C.3
D.4
43）将数组{1，1，2，4，7，5}从小到大排序，若采用 ① 排序算法，则元素之间需要进行的比较次数最少，共需要进行 ② 次元素之间的比较。
①A.直接插入
B.归并
C.堆
D.快速
②A.5
B.6
C.7
D.8
44）哈夫曼编码方案是基于 ① 策略的。用该方案对包含 a ～ f 六个字符的文件进行编码，文件包含100000个字符，每个字符出现的频率（用百分比表示）如表3-2所示，则与固定长度编码相比，该编码方案节省了 ② 存储空间。
表3-2 每个字符出现的频率
①A.分治
B.贪心
C.动态规划
D.回溯
②A.21%
B.27%
C.18%
D.36%
45）采用顺序表和单链表存储长度为 n 的线性序列，根据序号查找元素，其时间复杂度分别为______。
A. O （1）和 O （1）
B. O （1）和 O （ N ）
C. O （ N ）和 O （1）
D. O （ N ）和 O （ N ）
46）设元素序列 a ， b ， c ， d ， e ， f 经过初始为空的栈 S 后，得到出栈序列 cedfba ，则栈 S 的最小容量为______。
A.3
B.4
C.5
D.6
47）输出受限的双端队列是指元素可以从队列的两端输入，但只能从队列的一端输出。若有 e 1 ， e 2 ， e 3 ， e 4 依次进入输出受限的双端队列，则得不到输出序列______。
A. e 4 , e 3 , e 2 , e 1
B. e 4 , e 2 , e 1 , e 3
C. e 4 , e 3 , e 1 , e 2
D. e 4 , e 2 , e 3 , e 1
48）考虑下述背包问题的实例。有5件物品，背包容量为100，每件物品的价值和重量如表3-3所示，并且已经按照物品的单位重量价值从大到小排好序，根据物品单位重量价值大优先的策略装入背包中，则采用了 ① 设计策略。考虑0/1背包问题（每件物品要么全部放入要么全部不放入背包）和部分背包问题（物品可以部分放入背包），求解该实例，得到的最大价值分别为 ② 。
表3-3 物品的价值和重量
①A.分治
B.贪心
C.动态规划
D.回溯
②A.605和630
B.605和605
C.430和630
D.630和430
49）给定 n 个整数构成的数组 A ={ a 1 ， a 2 ，…， a n }和整数 x ，判断 A 中是否存在两个元素 a i 和 a j ，使得 a i + a j = x 。为了求解该问题，首先用归并排序算法对数组 A 进行从小到大排序，然后判断是否存在 a i + a j = x ，具体如以下伪代码所示，则求解该问题时排序算法应用了 ① 算法设计策略，整个算法的时间复杂度为 ② 。
①A.分治
B.贪心
C.动态规划
D.回溯
②A. O ( n )
B. O ( n lg n )
C. O ( n 2 )
D. O ( n lg 2 n )
50）一棵高度为 h 的满二叉树的节点总数为2 h -1，从根节点开始，自上而下、同层次节点从左至右对节点按照顺序依次编号，即根节点编号为1，其左、右孩子节点编号分别为2和3，再下一层从左到右的编号为4，5，6，7，以此类推。那么，在一棵满二叉树中，对于编号为 m 和 n 的两个节点，若 n =2 m +1，则______。
A. m 是 n 的左孩子
B. m 是 n 的右孩子
C. n 是 m 的左孩子
D. n 是 m 的右孩子
51）以下关于哈希查找的叙述中，正确的是______。
A.哈希函数应尽可能复杂一些，以消除冲突
B.构造哈希函数时应尽量使关键字的所有组成部分都能起作用
C.进行哈希查找时，不再需要与查找表中的元素进行比较
D.在哈希表中只能添加元素，不能删除元素
52）以下关于线性表存储结构的叙述，正确的是______。
A.线性表采用顺序存储结构时，访问表中任意一个指定序号的元素的时间复杂度为常量级
B.线性表采用顺序存储结构时，在表中任意位置插入新元素的运算时间复杂度为常量级
C.线性表采用链式存储结构时，访问表中任意一个指定序号的元素的时间复杂度为常量级
D.线性表采用链式存储结构时，在表中任意位置插入新元素的运算时间复杂度为常量级
53）设循环队列 Q 的定义中有front和size两个域变量，其中front表示队头元素的指针，size表示队列的长度，如图3-11所示（队列长度为3，队头元素为 x ，队尾元素为 z ）。设队列的存储空间容量为 M ，则队尾元素的指针为______。
图3-11 循环队列
A.( Q .front+ Q .size-1)
B.( Q .front+ Q .size-1+ M )% M
C.( Q .front -Q .size)
D.( Q .front -Q .size+ M )% M
54）在一个有向图 G 的拓扑序列中，顶点 v i 排列在 v j 之前，说明图 G 中______。
A.一定存在弧（ v j ， v i ）
B.一定存在弧
C.可能存在 v i 到 v j 的路径，而不可能存在 v j 到 v i 的路径
D.可能存在 v j 到 v i 的路径，而不可能存在 v i 到 v j 的路径
55）以下关于哈夫曼树的叙述，正确的是______。
A.哈夫曼树一定是满二叉树，其每层节点数都达到最大值
B.哈夫曼树一定是平衡二叉树，其每个节点左、右子树的高度差为-1、0或1
C.哈夫曼树中左孩子节点的权值小于父节点，右孩子节点的权值大于父节点
D.哈夫曼树中叶节点的权值越小，则距离树根越远；叶节点的权值越大，则距离树根越近
56）某哈希表（散列表）的长度为 n ，设散列函数为 H （Key）=Key mod p ，采用线性探测法解决冲突。以下关于 p 值的叙述中，正确的是______。
A. p 的值一般为不大于 n 且最接近 n 的质数
B. p 的值一般为大于 n 的任意整数
C. p 的值必须为小于 n 的合数
D. p 的值必须等于 n
57）对 n 个基本有序的整数进行排序，若采用插入排序算法，则时间复杂度和空间复杂度分别为 ① 。若采用快速排序算法，则时间复杂度和空间复杂度分别为 ② 。
①A. O （ n 2 ）和 O （ n ）
B. O （ n ）和 O （ n ）
C. O （ n 2 ）和 O （1）
D. O （ n ）和 O （1）
②A. O （ n 2 ）和 O （ n ）
B. O （ n log 2 n ）和 O （ n ）
C. O （ n 2 ）和 O （1）
D. O （ n log 2 n ）和 O （1）
58）在求解某问题时，经过分析发现该问题具有最优子结构性质，在求解过程中子问题被重复求解，则采用 ① 算法设计策略。若定义问题的解空间，以深度优先的方式搜索解空间，则采用 ② 算法设计策略。
①A.分治
B.动态规划
C.贪心
D.回溯
②A.动态规划
B.贪心
C.回溯
D.分支限界
59）若对线性表的最常用操作是访问任意指定序号的元素，并在表尾加入和删除元素，则适宜采用______存储。
A.顺序表
B.单链表
C.双向链表
D.哈希表
60）某二叉树如图3-12所示，若进行顺序存储（即用一维数组元素存储该二叉树中的节点且通过下标反映节点间的关系，例如，对于下标为 i 的节点，其左孩子的下标为2 i 、右孩子的下标为2 i +1），则该数组的大小至少为 ① ；若采用三叉链表存储该二叉树（各个节点包括节点的数据、父节点指针、左孩子指针、右孩子指针），则该链表的所有节点中空指针的数目为 ② 。
图3-12 二叉树
①A.6
B.10
C.12
D.15
②A.6
B.8
C.12
D.14
61）某双端队列如图3-13所示，要求元素进出队列必须在同一端口，即从A端进入的元素必须从A端出，从B端进入的元素必须从B端出，则对于4个元素的序列 e l 、 e 2 、 e 3 、 e 4 ，若要求前两个元素（ e l 、 e 2 ）从A端口按次序全部进入队列，后两个元素（ e 3 、 e 4 ）从B端口按次序全部进入队列，则可能得到的出队序列是______。
图3-13 双端队列
A. e l 、 e 2 、 e 3 、 e 4
B. e 2 、 e 3 、 e 4 、 e l
C. e 3 、 e 4 、 e l 、 e 2
D. e 4 、 e 3 、 e 2 、 e l
62）实现二分查找（折半查找）时，要求查找表______。
A.顺序存储，关键码无序排列
B.顺序存储，关键码有序排列
C.双向链表存储，关键码无序排列
D.双向链表存储，关键码有序排列
63）某个算法的时间复杂度递归式为 T （ n ）= T （ n -l）+ n ，其中 n 为问题的规模，则该算法的渐近时间复杂度为 ① ，若问题的规模增加到16倍，则运行时间增加到 ② 倍。
①A. O ( n )
B. O ( n lg n )
C. O ( n 2 )
D. O ( n 2 lg n )
②A.16
B.64
C.256
D.1024
64）Prim算法和Kruscal算法都是无向连通网的最小生成树的算法，Prim算法从一个顶点开始，每次从剩余的顶点中取出一个顶点加入，该顶点与当前的生成树中的顶点的连边权重最小，直到得到一棵最小生成树；Kruscal算法从权重最小的边开始，每次从不在当前的生成树中的顶点中选择权重最小的边加入，直到得到一棵最小生成树。这两个算法都采用了 ① 设计策略，且 ② 。
①A.分治
B.贪心
C.动态规划
D.回溯
②A.若网较稠密，则Prim算法更好
B.两个算法得到的最小生成树是一样的
C.Prim算法比Kruscal算法效率更高
D.Kruscal算法比Prim算法效率更高
65）对于线性表，相对于顺序存储，采用链表存储的缺点是______。
A.数据元素之间的关系需要占用存储空间，导致存储密度不高
B.表中的节点必须占用地址连续的存储单元，存储密度不高
C.插入新元素时需要遍历整个链表，运算的时间效率不高
D.删除元素时需要遍历整个链表，运算的时间效率不高
66）若一个栈初始为空，其输入序列是1，2，3，…， n -1， n ，其输出序列的第一个元素为 k （1≤ k ≤└ n /2┘），则输出序列的最后一个元素是______。
A.值为 n 的元素
B.值为1的元素
C.值为 n-k 的元素
D.不确定的
67）在某个二叉查找树（即二叉排序树）中进行查找时，效率最差的情形是该二叉查找树是______。
A.完全二叉树
B.平衡二叉树
C.单枝树
D.满二叉树
68）在字符串的KMP模式匹配算法中，需先求解模式串的next函数值，其定义如下（ j 表示模式串中字符的序号，从1开始）。若模式串 p 为“ abaac ”，则其next函数值为______。
A.01234
B.01122
C.01211
D.01111
69）在排序过程中，快速排序算法是在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于等于基准元素，而后面一部分元素值大于基准元素。然后分别对前后两个部分进行进一步划分。根据上述描述，快速排序算法采用了 ① 算法设计策略。可知确定基准元素操作的时间复杂度为 O （ n ），则快速排序算法的最好和最坏情况下的时间复杂度为 ② 。
①A.分治
B.动态规划
C.贪心
D.回溯
②A. O （ n ）和 O （ n log 2 n ）
B. O （ n ）和 O （ n 2 ）
C. O （ n log 2 n ）和 O （ n log 2 n ）
D. O （ n log 2 n ）和 O （ n 2 ）
70）对一待排序序列分别进行直接插入排序和简单选择排序，若待排序序列中有两个元素的值相同，则______保证这两个元素在排序前后的相对位置不变。
A.直接插入排序和简单选择排序都可以
B.直接插入排序和简单选择排序都不能
C.只有直接插入排序可以
D.只有简单选择排序可以
71）已知一个文件中出现的各字符及其对应的频率如表3-4所示。若采用定长编码，则该文件中字符的码长应为 ① 。若采用哈夫曼编码，则字符序列“ face ”的编码应为 ② 。
表3-4 字符及其对应的频率
①A.2
B.3
C.4
D.5
②A.110001001101
B.001110110011
C.101000010100
D.010111101011
72）设栈 S 和队列 Q 的初始状态为空，元素 abcdefg 依次进入栈 S 。要求每个元素出栈后立即进入队列 Q ，若7个元素出队列的顺序为 bdfecag ，则栈 S 的容量最小应该是_____。
A.5
B.4
C.3
D.2
73）某二叉树的前序遍历序列为 cabfedg ，中序遍历序列为 abcdefg ，则该二叉树是_____。
A.完全二叉树
B.最优二叉树
C.平衡二叉树
D.满二叉树
74）对某有序顺序表进行二分查找时，_____不可能构成查找过程中关键字的比较序列。
A.45,10,30,18,25
B.45,30,18,25,10
C.10,45,18,30,25
D.10,18,25,30,45
75）用某排序方法对一元素序列进行非递减排序时，若可保证在排序前后排序码相同者的相对位置不变，则称该排序方法是稳定的。简单选择排序法是不稳定的，_____可以说明这个性质。
A.21 48 21*6317
B.17 21 21*48 63
C.63 21 48 21*17
D.21*17 48 63 21
76）优先队列通常采用 ① 数据结构实现。向优先队列中插入一个元素的时间复杂度为 ② 。
①A.堆
B.栈
C.队列
D.线性表
②A. O ( n )
B. O (1)
C. O (log 2 n )
D. O ( n 2 )
77）一个无向连通图 G 上的哈密尔顿（Hamilton）回路是指从图 G 上的某个顶点出发，经过图上所有其他顶点一次且仅一次，最后回到该顶点的路径。一种求解无向图上的哈密尔顿回路算法的基本思想如下：
假设图 G 存在一个从顶点 u 0 出发的哈密尔顿回路 u 0 —u 1 —u 2 —u 3 —… —u 0 —u n -1 —u 0 。算法从顶点 u 0 出发，访问该顶点的一个未被访问的邻接顶点 u 1 ， 接着从顶点 u 1 出发，访问 u 1 的一个未被访问的邻接顶点 u 2 ……对顶点 u i 重复进行以下操作：访问 u i 的一个未被访问的邻接顶点 u i+ 1 ，若 u i 的所有邻接顶点均已被访问，则返回顶点 u i -1 ，考虑 u i -1 的下一个未被访问的邻接顶点，仍记为 u i ，直到找到一个哈密尔顿回路或者找不到哈密尔顿回路，算法结束。
下面是算法的C语言实现。
（1）常量和变量说明
n ：图 G 中的顶点数。
c [][]：图 G 的邻接矩阵。
k ：统计变量，当前已经访问的顶点数为 k +1。
x [ k ]：第 k 个访问的顶点编号，从0开始。
visited[ x [ k ]]：第 k 个顶点的访问标志，0表示未访问，1表示已访问。
（2）C程序
问题1：根据题干说明，填充C代码中的空 ①～⑤ 。
问题2：根据题干说明和C代码，算法采用的设计策略是 ⑥ ，该方法在遍历图的顶点时，采用的是 ⑦ 方法（深度优先或广度优先）。
78）希尔排序算法又称最小增量排序算法，其基本思想是：
步骤01 构造一个步长序列delta1，delta2，…，delta k ，其中delta1= n /2，后面的每个delta是前一个的1/2，delta k =1。
步骤02 根据步长序列进行 k 趟排序。
步骤03 对于第 i 趟排序，根据对应的步长delta，将等步长位置的元素分组，对同一组内的元素在原位置上进行直接插入排序。
下面是算法的C语言实现。
（1）常量和变量说明
data：待排序数组，长度为 n ，待排序数据记录在data[0] data[1]…data[ n -1]中。
n ：数组 a 中的元素个数。
delta：步长数组。
（2）C程序
问题1：根据说明和C代码，填充C代码中的空 ①～④ 。
问题2：根据说明和C代码，该算法的时间复杂度 ⑤ O （ n 2 ）（小于、等于或大于）。该算法是否稳定 ⑥ （是或否）。
问题3：对数组（15，9，7，8，20，-1，4）用希尔排序方法进行排序，经过一趟排序后得到的数组为 ⑦ 。
1）D。
2）A。
按行方式存储时，元素
A
[
i
，
j
]之前的元素个数为1+2+…+
i
+
j
，由于数组
M
的下标从1开始，因此存储
A
[
i
，
j
]的是
M
[1+2+…+
i
+
j
+1]，即
。
3）B。
二叉树具有以下性质：度为2的节点（双分支节点）数比度为0的节点（叶节点）数正好少1。而根据最优二叉树（哈夫曼树）的构造过程可知，最优二叉树中只有度为2和0的节点，因此其节点总数为2 n -1。
4）A。
栈是一种“后进先出”的数据结构。将一个元素序列逆置时，可以使用栈，也可以不使用。链表节点的申请和释放次序与应用要求相关，不存在“先申请后释放”的操作要求。可执行程序的装入与卸载，也不存在“后进先出”的操作要求。对于函数的递归调用与返回，一定是后被调用执行的先返回。
5）C。
当序列基本有序时，直接插入排序的过程中元素比较的次数较少，当序列为逆序时，元素的比较次数最多。
6）B。
装填因子 a 表示了哈希表的装满程度，显然 a 越大，发生冲突的可能性就越大。
7）C。
根据关键字序列构造二叉排序树的基本过程是，若需插入的关键字大于树根，则插入右子树；若小于树根，则插入左子树；若为空树，则作为树根节点。
8）B。
根据题中给出的递归定义式进行推导，可得 T （ n ）= n +（ n -1）+…+2+1，因此时间复杂度为 O （ n 2 ）。
9）C。
设尾指针的单向循环链表（不含头节点）如图3-14所示。
图3-14 单向循环链表
设节点的指针域为next，新节点的指针为 s ，则在尾指针所指节点后插入节点的操作为：
s->next=t->next,t->next=s;t=s;
也就是插入操作的时间复杂度为 O （1）。
要删除尾指针所指的节点，必须通过遍历操作找到尾节点的前驱节点，其操作序列如下：
删除操作的时间复杂度为 O （ n ）。
10）C。
构造最优二叉树的哈夫曼算法如下：
①根据给定的 n 个权值{ w 1 ， w 2 ，…， w n }，构成 n 棵二叉树的集合 F ={ T 1 ， T 2 ，…， T n }，其中每棵二叉树 T i 中只有一个权为 w i 的根节点，其左右子树均空。
② 在 F 中选取两棵权值最小的二叉树作为左、右子树构造一棵新的二叉树，置新构造的二叉树的根节点的权值为其左、右子树根节点的权值之和。
③从 F 中删除这两棵树，同时将新得到的二叉树加入 F 中。
重复②、③，直到 F 中只含一棵树为止。这棵树便是最优二叉树（哈夫曼树）。从以上叙述可知，哈夫曼树中权值最小的两个节点互为兄弟节点。
11）A。
拓扑排序是将AOV网中的所有顶点排成一个线性序列的过程，并且该序列满足：若在AOV网中从顶点 v i 到 v j 有一条路径，则在该线性序列中顶点 v i 必然在顶点 v j 之前。
对AOV网进行拓扑排序的方法如下：
①在AOV网中选择一个入度为零（没有前驱）的顶点且输出它。
②从网中删除该顶点及与该顶点有关的所有边。
③重复上述两步，直至网中不存在入度为零的顶点为止。
本题中只有序列654321可由上述过程导出。
对有向图进行拓扑排序的结果会有两种情况：一种是所有顶点已输出，此时整个拓扑排序完成，说明网中不存在回路；另一种是尚有未输出的顶点，剩余的顶点均有前驱顶点，表明网中存在回路。
12）D。
对序列15，23，38，47，55，62，88，95，102，123进行二分查找的过程可用以下二叉树之一描述，其中图3-15左图描述的是除2以后向下取整时的判定过程，右图则对应除2以后向上取整时的判定过程。
图3-15 二分查找树
从上图可知，二分法查找95时，参与比较的元素依次为55、95，或者62、102、95。
13）B。
设树中的节点总数为 n ，分支数目为 m ，那么 n =5+4+2+叶节点数， m =5×1+4×2+2×3。
在树中，节点总数等于分支数目加上1，即 n = m +1。
因此，叶节点数=5×1+4×2+2×3+1-5-4-2=9。
14）A。
该题可以用主方法来求解，对于该递归式， a =2， b =2， f （ n ）= n lg n ，属于第二种情况，因此其时间复杂度为 O （ n lg 2 n ）。该题还可以用递归树求解。
15）A。
分析算法的时间复杂度并不是确定算法运行的具体时间的长短，而是执行某个（某些）操作的次数。该题要求计算count++语句执行的次数，根据上述C程序段可知， i =1时执行1次， i =2时执行2次， i =4时执行4次， i =8时执行8次，总共执行次数为1+2+4+8=15。
16）B。
17）B。
假设从前往后找，则所找元素为第1个元素时，与表中的1个元素进行了比较，所找元素为第2个元素时，与表中的2个元素进行了比较，以此类推，所找元素为第 n 个元素时，与表中的 n 个元素进行了比较，因此平均查找长度等于（1+2+…+ n ）/ n 。
18）A。
在平衡二叉树中，任意一个节点的左、右子树的髙度之差的绝对值不超过1。
虽然在结构上都符合二叉树的定义，但完全二叉树、线索二叉树、二叉排序树与最优二叉树的应用场合和概念都不同。
线索二叉树与二叉树的遍历运算相关，是一种存储结构。
二叉排序树的结构与给定的初始关键码序列相关。
最优二叉树（即哈夫曼树）是一类带权路径长度最短的二叉树，由给定的一个权值序列构造。
线索二叉树、二叉排序树和最优二叉树在结构上都不要求是平衡二叉树。
在完全二叉树中，去掉最后一层后就是满二叉树，而且最后一层上的叶节点必须从该层的最左边开始排列，满足任意一个节点的左、右子树的高度之差的绝对值不超过1的条件，因此在形态上是平衡的二叉树。
19）C。
无向图的邻接矩阵是一个对称矩阵，每条边会表示两次，因此矩阵中的非零元素数目为2 E 。
20）D。
对于关键字序列（26，25，72，38，8，18，59）和散列函数 H （Key）=Key mod13，采用线性探测的开放定址法解决冲突构造的散列表如图3-16所示。
图3-16 散列图
21）D。
N -皇后问题是一个经典的计算问题，该问题基于一些约束条件来求问题的可行解。该问题不易划分为子问题求解，因此分治法不适用：由于不是要求最优解，因此不具备最优子结构性质，也不宜用动态规划法和贪心法求解。而系统搜索法——回溯法可以有效地求解该问题。
22）A。
分治法是一种重要的算法设计技术（设计策略），该策略将原问题划分成 n 个规模较小而结构与原问题相似的子问题，递归地解决这些子问题，然后合并其结果，最终得到原问题的解。分治算法往往用递归技术来实现，但并非必需。分治算法最理想的情况是划分为 k 个规模相等的子问题，但很多时候往往不能均匀地划分子问题。分治算法的代价在划分子问题和合并子问题的解上，根据不同的问题，划分的代价和合并的代价有所不同。例如归并排序中，主要的计算代价在合并解上，而在快速排序中，主要的计算代价在划分子问题上。
23）A。
24）A。
插入排序算法的基本思想是将待排序数组分为两个部分：已排好序部分和未排序部分。其主要步骤为：开始时，第一个元素在已排好序部分中，其余元素在未排序部分中。然后依次从未排序部分中取出第一个元素，从后向前与排好序部分的元素进行比较，并将其插入已排好序部分的正确位置，直到所有元素排好序。
归并排序的基本思想是将待排序数组划分为子问题，对子问题求解，然后合并解。其主要步骤为：将数组分为两个相同规模的子数组，分别包含前 n /2个元素和后 n /2个元素，递归地排序这两个子数组，合并排好序的两个子数组，依次比较两个排好序的子数组的元素，得到整个数组的排好序的序列。
根据上述算法思想和算法步骤，可以得到题中实例的比较次数分别为12和14。
25）B。
26）A。
随机访问是指可由元素的序号和第一个元素存储位置的首地址计算得出该序号所对应元素的存储位置，这要求这一组元素必须连续地存储，链表存储结构中元素的存储位置是可以分散的，仅通过指针将逻辑上相邻而存储位置不要求相邻的元素链接起来，而且只能顺着指针所指示的方向进行遍历。
单向循环链表中指针的指示方向是单方向的，对于表中的任意一个元素，访问其直接后继的运算时间复杂度为 O （1），访问其直接前驱的运算时间复杂度为 O （ n ）。链表中是否含有头节点要看具体的应用情况和运算要求，并没有必须设置的要求。
27）B。
28）C。
构造最优二叉树的哈夫曼算法如下：
① 根据给定的 n 个权值{ w 1 ， w 2 ，…， w n }，构成 n 棵二叉树的集合 F ={ T 1 ， T 2 ，…， T n }，其中每棵二叉树 T i 中只有一个权为 w i 的根节点，其左右子树均为空。
② 在 F 中选取两棵权值最小的二叉树作为左、右子树构造一棵新的二叉树，置新构造的二叉树的根节点的权值为其左、右子树根节点的权值之和。
③从 F 中删除这两棵树，同时将新得到的二叉树加入 F 中。
重复②、③，直到 F 中只含一棵树为止。这棵树便是最优二叉树（哈夫曼树）。根据题中给出的权值集合，构造哈夫曼树的过程如图3-17所示。
图3-17 构造哈夫曼树
29）C。
单源点最短路径问题是指给定图 G 和源点 v 0 ，求从 v 0 到图 G 中其余各顶点的最短路径。迪杰斯特拉（Dijkstra）算法是一个求解单源点最短路径的经典算法，其思想是：把图中所有的顶点分成两个集合 S 和 T ， S 集合开始时只包含顶点 v 0 ， T 集合开始时包含图中除了顶点 v 0 之外的所有顶点。凡是以 v 0 为源点，已经确定了最短路径的终点并入 S 集合中，顶点集合 T 则是尚未确定最短路径的顶点集合。按各顶点与 v 0 间最短路径长度递增的次序，逐个把 T 集合中的顶点加入 S 集合中，使得从 v 0 到 S 集合中各顶点的路径长度始终不大于从 v 0 到 T 集合中各顶点的路径长度。该算法是以一种贪心的方式将 T 集合中的顶点加入 S 集合中的，而且该贪心方法可以求得问题的最优解。
30）A。
从题干可以看出，划分操作与快速排序中的划分操作是一样的，确定某个元素（如 r ）的最终位置，划分后，在 r 之前的元素都小于 r ，在 r 之后的元素都大于 r （假设无重复元素）。因此可以据此确定 r 是数组中第几小的数。题干所述的算法把找第 i 小的数转换为确定任意一个元素是第几小的数，然后根据这个结果，再依据该元素划分后得到的结果在前一部分还是后一部分来继续确定某个元素为第几小的数，重复这种处理，直到找到第 i 小的数。这是分治策略的一个典型应用。
31）C。
栈和队列是两种常用的数据结构。栈的特点是后进先出，队列的特点是先进先出。因此，入队序列与出队序列一定相同。在入栈序列一定的情况下，由于元素的出栈时机不同，会形成不同的出栈序列，入栈序列与出栈序列可以相同，也可以不同。
32）A。
KMP模式匹配算法是对基本模式匹配算法的改进，其改进之处在于：每当匹配过程中出现相比较的字符不相等时，不需要回溯主串的字符位置指针，而是利用已经得到的“部分匹配”结果将模式串向右“滑动”尽可能远的距离，再继续进行比较。
在KMP算法中，依据模式串的next函数值实现子串的滑动。若令next[ j ]= k ，则next[ j ]表示当模式串中的 p j 与主串中的相应字符不相等时，令模式串的 p k 与主串的相应字符进行比较。
根据next的定义，模式串“ aaabaaa ”的next函数值为0123123。
33）D。
对任何一棵二叉树，若其终端节点数为 n 0 ，度为2的节点数为 n 2 ，则 n 0 = n 2 +l。证明如下：
设一棵二叉树上的叶节点数为 n 0 ，单分支节点数为 n 1 ，双分支节点数为 n 2 ，则总节点数为 n 0 + n 1 + n 2 。
在一棵二叉树中，所有节点的分支数（即度数）应等于单分支节点数加上双分支节点数的2倍，即总的分支数为 n 1 +2 n 2 。
由于二叉树中除根节点以外，每个节点都有唯一的一个分支指向它，因此二叉树中，总的分支数=总节点数-1。因此， n 1 +2 n 2 = n 0 + n 1 + n 2 -l，即 n 0 = n 2 +l。
34）C。
图的基本存储结构有邻接矩阵表示法和邻接链表表示法。图的邻接矩阵表示利用一个矩阵来表示图中顶点之间的关系。对于具有 n 个顶点的图 G =（ V ， E ），其邻接矩阵是一个 n 阶方阵，且满足：
图中的顶点数决定了邻接矩阵的阶和邻接表中的单链表数目，无论是对有向图还是无向图，边数的多少决定了单链表中的节点数，而不影响邻接矩阵的规模，因此完全图适合采用邻接矩阵存储。
35）C。
归并的过程是：取序列 A 的一个元素 a i 和序列 B 的一个元素 b j ，若 a i ＞ b j ，则输出 b j ；接下来令其与 b j +1 比较，若 a i ＞ b j +1 ，则输出 b j +1 ，否则输出 a i ；接下来令 a i +1 与 b j 比较，重复以上过程，直至将所有元素输出。
对于最终排列 a 1 ， a 2 ，…， a n ， b 1 ， b 2 ，…， b n 的情况，归并过程中进行了 n 次比较，分别是 a 1 ＜ b 1 ， a 2 ＜ b 1 ，…， a n ＜ b 1 ，最后依次输出 b 1 ， b 2 ，…， b n 。
对于最终排列为 b 1 ， b 2 ，…， b n ， a 1 ， a 2 ，…， a n 的情况，归并过程中进行了 n 次比较，分别是 b 1 ＜ a 1 ， b 2 ＜ a 1 ，…， b n ＜ a 1 ，最后依次输出 a 1 ， a 2 ，…， a n 。
对于最终排列为 a 1 ， b 1 ， a 2 ， b 2 ，…， a i ， b i ，…， a n ， b n 的情况，归并过程中进行了2 n -1次比较，分别是 a 1 ＜ b 1 ， b 1 ＜ a 2 ， a 2 ＜ b 2 ， b 2 ＜ a 3 ，…， a n ＜ b n 。
若最终排列为 a 1 ， a 2 ，…， a i /2 ， b 1 ， b 2 ，…， b i /2 ， a i /2+1 ， a i /2+2 ，…， a n ， b i /2+1 ， b i /2+2 ，…， b n ，则在归并过程中，分别是 a 1 ， a 2 ，…， a i /2 各与 b 1 进行一次比较，共 i /2次；然后是 b 1 ， b 2 ，…， b i /2 各与 a i /2+1 进行一次比较，共 i /2次；接下来是 a i /2+1 ， a i /2+2 ，…， a n 各与 b i /2+1 进行一次比较，共 n-i /2次，合计比较次数为 i /2+ i /2+ n-i /2= n + i /2。
因为
i
≤
n
，所以总比较次数
。
因为
n
≥2，所以
，可见比较次数最多的应选C。
36）①C。
②A。
由于每次选择下一个要访问的城市时都是基于与当前最近的城市来进行的，是一种贪心的选择策略，因此采用的是贪心策略。而货车从中央仓库出发，第一个要到达的目的地是在 n 个目的地中选择一个，第二个要到达的目的地是在 n -1个目的地中选择一个，以此类推，第 n 个要到达的目的地是在1个目的地中选择一个，因此时间复杂度为 O （ n 2 ）［ n +（ n -1）+…+l= n ×（ n +l）/2］。
37）C。
根据伪代码可知，算法的基本思想是从前往后检查元素，若为负数，则继续向前检查；若遇到正数，则开始从后往前检查元素，若为正数，则继续往前检查，若遇到负数，则与前面遇到的正数进行交换。重复检查元素，所有元素检查完毕，根据该思想可知每个元素，因此算法的时间复杂度为线性时间，即 O （ n ）。在该过程中，仅需要一个额外的辅助存储空间，以便进行元素的交换，因此空间复杂度为常数，即 O （1）。
38）B。
假设主串和模式串的长度分别为 n 和 m ，位置序号从0开始计算。设从主串的第 i 个位置开始与模式串匹配成功，在前 i 趟匹配中（位置0～ i -1），每趟不成功的匹配都是模式串的第一个字符与主串中相应的字符不相同，则在前 i 趟匹配中，字符的比较共进行了 i 次，而第 i =1（从位置 i 开始）趟成功匹配的字符比较次数为 m ，所以总的字符比较次数为 i + m （0≤ i ≤ n-m ）。
而在最坏情况下，每一趟不成功的匹配都是模式串的最后一个字符与主串中相应的字符不相等，则主串中新一趟的起始位置为 i-m +2。设从主串的第 f 个字符开始匹配时成功，则前 i 趟不成功的匹配中，每趟都比较了 m 次，总共比较了 i × m 次，第 i +1趟的成功匹配也比较了 m 次。因此，最坏情况下的比较次数为（ n-m +l）× m 。
39）A。
根据后序遍历序列 KBFDCAE ，可以确定根节点为 E ，然后根据中序遍历序列 BKEFACD ，可以确定 B 、 K 为左子树的节点， F 、 A 、 C 、 D 是右子树的节点。再根据左子树的后序遍历序列 KB 、中序遍历序列 BK ，可以确定 B 是左子树的根节点， K 在节点 B 的右子树上。同理，可推出其他节点的位置。
40）A。
设查找表的元素存储在一维数组 r [l… n ]中，在表中的元素已经按关键字递增方式排序的情况下，进行二分查找的方法是：首先将待查元素的关键字（key）值与表 r 中间位置（下标为mid）记录的关键字进行比较，若相等，则查找成功；若 key＞ r [mid].key，则说明待查记录只可能在后半子表 r [mid+l… t i ]中，下一步应在后半子表中进行查找，若 key＜ r [mid].key，则说明待查记录只可能在前半子表 r [l…mid-1]中，下一步应在 r 的前半子表中进行查找，通过逐步缩小范围，直到查找成功或子表为空时失败为止。
二分查找的过程可以用一棵二叉树描述，方法是以当前查找区间的中间位置序号作为根，左半子表和右半子表中的记录序号分别作为根的左子树和右子树上的节点，具有13个节点的二分查找判定树如图3-18所示。
图3-18 二分查找树
41）C。
题中所示有向图的拓扑序列有：1235476，2135476，1235746，2135746。
42）D。
在 M 阶树的定义中，要求：
①树中的每个节点至多有 M 棵子树。
②若根节点不是叶节点，则至少有两棵子树。
③除根之外的所有非终端节点至少有 M /2棵子树。
因此，本题图中所示的树最可能为4阶树。
43）①A。
②B。
用插入排序算法排序该输入数组，第二个元素1需要和第一个元素1进行一次比较，第三个元素2需要和第二个元素1进行一次比较，第四个元素4需要和第三个元素2进行一次比较，第五个元素7需要和第四个元素4进行一次比较，第六个元素5需要和第五个元素7进行一次比较，比7小，和元素7交换，再和第四个元素4进行一次比较，得到最终的排序结果。因此，一共需要进行6次比较。
44）①B。
②A。
该实例构造的最优编码树如图3-19所示。
图3-19 最优编码树
实例中包含6个字符，若用定长编码，则需要三位，对包含100000个字符的文件，需要3×100000=300000位的存储空间。而采用哈夫曼编码，则需要（18000+26000+32000）×2+12000×3+（4000+8000）×4=236000位的存储空间，节省了21%的存储空间。
45）B。
对于长度为 n 的线性序列，若采用顺序表（一维数组）存储，则每个元素的位序与存储该元素的数组元素下标有直接的对应关系，可进行随机查找，时间复杂度为 O （1）；若采用单链表存储，则只能进行顺序访问，即必须从头指针出发，结合计数顺着指针链找到指定序号的元素，时间复杂度为 O （ n ）。
46）B。
栈是一种后进先出的数据结构。本题中，根据元素入栈次序及出栈序列，每次需要出栈操作时栈的状态如图3-20所示，从图中可以看出，栈中的元素个数最多时为4。
图3-20 栈的状态
47）D。
该双端队列具有两个入口，所以 e l 、 e 2 、 e 3 进入队列后，从出口看可形成如下排列：
先出 e 1 ，则得到 e l e 2 e 3 。
先出 e 2 ，则得到 e 2 e l e 3 。
先出 e 3 ，则得到 e 3 e l e 2 或 e 3 e 2 e l 。
要在输出序列中首先得到 e 4 ，元素 e 4 只能从出口端进入队列，结合前三个元素的可能排列，因此以 e 4 打头的输出序列有： e 4 e l e 2 e 3 ， e 4 e 2 e l e 3 ， e 4 e 3 e l e 2 ， e 4 e 3 e 2 e l 。
48）①B。
②C。
背包问题是典型的算法问题，包括两种形式，即0/1背包问题和部分背包问题。在0/1背包问题中，每个物品要么全部放入背包中，要么不放入背包中，求解在特定背包容量下装入背包物品的最大价值。在部分背包问题中，每个物品可以部分放入背包中，求解在特定背包容量下装入背包物品的最大价值。
基于单位重量价值最大优先的策略来将物品放入背包中，本质上是一种贪心策略。在该策略下求0/1背包问题，不能确保得到最优解，事实上在本题给出的实例中是得不到最优解的。而对于部分背包问题，是可以得到最优解的。
基于单位重量价值最大优先的策略求解本题给出的实例。对于0/1背包问题，首先将物品1、2和3放入背包中，4和5都不能再放入背包，此时背包重量为5+25+30=60，获得的价值为50+200+180=430。对于部分背包问题，首先将物品1、2和3放入背包中，此时背包重量为60，获得的价值为430，还有剩余容量100-60=40，可以将部分物品4放入背包，放入40/45=8/9的物品4，价值为225×8/9=200，因此得到的总价值为430+200=630。
49）①A。
②B。
本题给出的问题求解算法包括两个部分，即归并排序和搜索元素。归并排序是一个采用分治策略的经典排序算法；而搜索过程则是从两端往里判断是否存在 a i + a p x ，此过程不涉及分治、贪心、动态规划和回溯等策略。因此，算法采用的是分治策略。
算法的时间复杂度也是从两个部分分析得到的。归并排序的时间复杂度为 O （ n lg n ），而搜索过程的时间复杂度为 O （ n ）。因此，算法的时间复杂度为 O （ n lg n ）。
50）D。
用验证的方法求解，以高度为3的满二叉树（见图3-21）为例进行说明。
图3-21 满二叉树
从中可以看出，若 n =2 m +l，则节点 n 是 m 的右孩子节点。
51）B。
哈希表是通过一个以记录的关键字为自变量的函数（称为哈希函数或散列函数）得到该记录的存储地址而构造的查找表，所以在哈希表中进行查找操作时，必须用同一哈希函数计算得到待查记录的存储地址，然后到相应的存储单元里去获得有关信息，再判定查找是否成功。
冲突是指哈希函数将关键字不同的元素映射到同一个存储地址。要减少冲突，就要设法使哈希函数尽可能均匀地把关键字映射到存储区的各个存储地址上，这样就可以提高查找效率。构造哈希函数时，一般应使关键字的所有组成部分都能起作用。
52）A。
线性表进行顺序存储时，逻辑上相邻的元素，其物理位置也相邻，因此在已知第一个元素存储位置和元素序号的情况下，可计算出表中任意指定序号元素的存储位置，即按照序号访问元素是随机的，该运算的时间复杂度为 O （1），也就是常量级。而插入元素时就需要移动一些元素了，在最坏情况下要移动表中的所有元素，因此该运算的时间复杂度为 O （ n ），其中 n 为线性表的长度。
线性表进行链式存储时，逻辑上相邻的元素，其物理位置不要求相邻，因此需要额外的存储空间表示元素之间的顺序关系。在链表上查找元素和插入元素的运算时间复杂度都为 O （ n ）。
53）B。
根据题目中所给的示意图， Q .front为队头元素的指针，该指针加1后得到队列中的第2个元素（即 y ）的指针，由于队列中存储位置编号是在0～ M -1之间循环的，队头指针加上1个增量后可能会超出该范围，应该用整除取余运算恢复一下，因此由 Q .front可以计算出队列尾部元素的指针为（ Q .front+ Q .size-1+ M ）% M 。
54）C。
对一个有向图 G 进行拓扑排序的方法如下：
①在 G 中选择一个入度为0（没有前驱）的顶点且输出它。
②从网中删除该顶点以及与该顶点有关的所有弧。
③重复上述两步，直至网中不存在入度为0的顶点为止。
显然，若存在弧＜ v i ， v j ＞，则 v j 的入度就不为0，而要删除该弧，则 v i 的入度应为0，因此在拓扑序列中， v i 必然在 v j 之前。另外，进行拓扑排序时，可能存在 v i 和 v j 的入度同时为0的情形，此时，在第①步可先输出 v i ，后输出 v j 。因此，在拓扑序列中，顶点 v i 排列在 v j 之前，不一定存在弧＜ v i ， v j ＞，一定不存在弧＜ v j ， v i ＞，也一定不存在 v j 到 v i 的路径，而可能存在 v i 到 v j 的路径。
55）D。
哈夫曼树是一类带权路径长度最短的树，根据一组权值构造出来。构造过程为：
① 根据给定的 n 个权值{ w 1 ， w 2 ，…， w n }，构成 n 棵二叉树的集合 F ={ T 1 ， T 2 ，…， T n }，其中每棵树 T i 中只有一个权为 w i 的根节点，其左右子树均空。
② 在 F 中选取两棵权值最小的树作为左、右子树构造一棵新的二叉树，置新构造的二叉树的根节点的权值为其左、右子树根节点的权值之和。
③从 F 中删除这两棵树，同时将新得到的二叉树加入 F 中。
根据权值集合{0.25，0.30，0.08，0.25，0.12}构造的哈夫曼树如图3-22所示，从中可以知道，哈夫曼树中叶节点的权值越小，则距离树根越远，叶节点的权值越大，则距离树根越近。
图3-22 哈夫曼树
56）A。
在应用散列函数构造哈希表（或散列表）时，设计散列函数的目标是：作为一个压缩映像函数，它应具有较大的压缩性，以节省存储空间；应具有较好的散列性，虽然冲突是不可避免的，但应尽量减少。题中所给的是常用的除留余数法， p 值一般为不大于 n 且最接近 n 的质数。
57）①D。
②C。
排序和查找是基本的计算问题，存在很多相关的算法，不同的算法适用于不同的场合。不同的数据，输入特点相同的算法也有不同的计算时间。若数据基本有序，对插入排序算法而言，则可以在近似线性时间内完成排序，即 O （ n ）；而对于快速排序算法，则是其最坏情况，需要二次方非线性才能完成排序，即 O （ n 2 ）。两个算法在排序时仅需要一个额外的存储空间，即空间复杂度均为常数时间复杂度 O （1）。
58）①B。
②C。
59）A。
线性表的元素在逻辑上是一个线性序列，若最常用的操作是访问任意指定序号的元素，而且其插入和删除元素的操作均在表尾进行，不需要移动其他元素，则其存储结构采用顺序表最为合适。
60）①D。
题图所示的二叉树有6个节点，根节点的编号为1，其左孩子和右孩子分别为2和3，按照右孩子链继续，3号节点的右孩子编号为7，7号节点的右孩子编号为15，因此该二叉树进行顺序存储时数组大小至少为15。
②B。
采用三叉链表存储时，每个节点有3个指针域，共18个指针域，其中12个孩子指针用了5个，剩余7个为空指针，6个父节点指针用了5个，剩余1个为空（即根节点无双亲），因此节点中的指针域有8个为空。
61）D。
按照题目所述， e 1 、 e 2 从A端口按次序全部进入队列， e 3 、 e 4 从B端口按次序全部进入队列。在这种情形下， e 1 和 e 3 不可能先出队列，所以排除选项A和C。若 e 2 先出队列，则剩下的3个元素中，只能是 e 1 或 e 4 出队列，所以 e 2 、 e 3 、 e 4 、 e 1 是不可能的出队序列，这样就排除了选项 B。选项D的 e 4 、 e 3 、 e 2 、 e 1 是可能的出队序列。
62）B。
二分查找是一种高效的查找方法，其思路是：待查找元素先与序列中间位置上的元素比较，若相等，则查找成功；若待查找元素较大，则接下来到序列的后半区进行二分查找，否则到序列的前半区进行二分查找。显然，要快速定位序列的中间位置，首先，查找表必须进行顺序存储；其次，从二分查找过程可知，序列必须有序排列才行。
63）①C。
直接展开递归式 T （ n ）= T （ n -1）+ n
= T ( n -2）+( n -1）+ n
= T ( n -3）+( n -2）+( n -1）+ n
=1+2+…+ n
= n ( n +1）/2
= O ( n 2 )
得到该算法的时间复杂度为 O （ n 2 ）。
②C。
当问题的规模增加到16倍时，运行时间增加到16 2 =256倍。
64）①B。
Prim算法从扩展顶点开始，每次总是“贪心地”选择与当前顶点集合中距离最短的顶点，而Kruscal算法从扩展边开始，每次总是“贪心地”选择剩余的边中最小权重的边，因此两个算法都是基于贪心策略进行的。
②A。
Prim算法的时间复杂度为 O （ n 2 ），其中 n 为图的顶点数，该算法的计算时间与图中的边数无关，因此该算法适合求边稠密的图的最小生成树；Kruscal算法的时间复杂度为 O （ m log 2 m ），其中 m 为图的边数，该算法的计算时间与图中的顶点数无关，因此该算法适合求边稀疏的图的最小生成树。当图稠密时，用Prim算法效率更高。但若事先没有关于图的拓扑特征信息，则无法判断两者的优劣。由于一个图的最小生成树可能有多棵，因此不能保证用这两种算法得到的是同一棵最小生成树。
65）A。
对于线性表（ a 1 ， a 2 ，…， a n ），顺序存储时表中元素占用的存储单元地址是连续的，因此逻辑上相邻的元素，其物理位置也相邻。线性表采用链式存储有单链表、双向链表、循环链表等形式。链式存储的基本特点是逻辑上相邻的元素不要求物理位置上相邻，所以需要在元素的存储单元中专门表示下一个（或上一个）元素的存储位置信息，从而可以得到元素间的顺序信息。
66）D。
以 n 等于4为例说明。输入序列为1234，输出序列的第一个元素可以为1或2。若为1，则输出序列可能为1234、1243、1342、1324、1432；若为2，则输出序列为2134、2143、2314、2341、2431。
以上序列都可由合法的入栈、出栈操作序列给出，从中可知无法确定输出序列中最后一个元素的值。
67）C。
非空二叉查找树中的节点分布特点是左子树中的节点均小于树根，右子树中的节点均大于树根。因此，在二叉查找树中进行查找时，走了一条从树根出发到所找到节点的路径，到达一个空的子树则表明查找失败。
根据定义，高度为 h 的满二叉树中有2 h -l个节点，每一层上的节点数都达到最大值。完全二叉树的最高层只要求节点先占据左边的位置。在平衡二叉树中，任何一个节点的左子树高度与右子树高度之差的绝对值不大于1，单枝树中每个节点只有一个子树。在节点数确定后，二叉查找树的形态为单枝树时查找效率最差。
68）B。
KMP是进行字符串模式匹配运算效率较高的算法。根据对next函数的定义，模式串前两个字符的next值为0、1。对于第3个字符“ a ”，其在模式串中的前缀为“ ab ”，从该子串找不出前缀和后缀相同的部分，因此，根据定义，该位置字符的next值为1。对于第4个字符“ a ”，其在模式串中的前缀为“ aba ”，该子串只有长度为1的前缀“ a ”和后缀“ a ”相同，根据定义，该位置字符的next值为2。
对于第5个字符“ c ”，其在模式串中的前缀为“ abaa ”，该子串只有长度为1的前缀“ a ”和后缀“ a ”相同，根据定义，该位置字符的next值为2。
综上可得，模式串“ abaac ”的next函数值为01122。
69）①A。
快速排序算法是应用最为广泛的排序算法之一。其基本思想是将 n 个元素划分为两个部分：一部分元素值小于某个数，另一部分元素值大于某个数。该数的位置确定后，进一步划分前面部分和后面部分。根据该叙述可以知道，这里采用的是分治算法设计策略。
②D。
快速排序算法的最好情况就是，每一次划分都正好将数组分成长度相等的两半，形成一棵平衡的二叉树。最坏情况就是，每一次划分将数组分成0和剩余两部分，形成一棵倾斜的二叉树。快速排序算法的最好和最坏情况下的时间复杂度分别为 O （ n log 2 n ）和 O （ n 2 ）。
70）C。
直接插入排序的思想是： n 个待排序的元素由一个有序表和一个无序表组成，开始时有序表中只包含一个元素。在排序过程中，每次从无序表中取出第一个元素，将其插入有序表中的适当位置，使有序表的长度不断加长，完成排序过程。
例如，对序列21，48，21*，9进行直接插入排序，21和21*的相对位置在排序前后可保持，如下所示：
第一趟得到有序子序列：21，48。
第二趟得到有序子序列：21，21*，48。
第三趟得到有序序列：9，21，21*，48。
简单选择排序的过程是：第一趟在 n 个记录中选取最小记录作为有序序列的第一个记录，第二趟在 n -1个记录中选取最小记录作为有序序列的第二个记录，第 i 趟在 n-i +1个记录中选取最小的记录作为有序序列中的第 i 个记录，直到序列有序排列。
对序列21，48，21*，9进行简单选择排序，过程如下：
第一趟选出最小元素，将其交换至1号位置，序列为9，48，21*，21。
第二趟选出次小元素，将其交换至2号位置，序列为9，21*，48，21。
第三趟选出第三小元素，将其交换至3号位置，序列为9，21*，21，48。
从该例可知，简单选择排序过程不能保证排序码相同的两个元素在排序前后的相对位置不变，直接插入排序则可以。
71）①B。
字符在计算机中是用二进制表示的，每个字符用不同的二进制编码来表示。码的长度影响存储空间和传输效率。若是定长编码方法，用2位码长，只能表示4个字符，即00、01、10和11；若用3位码长，则可以表示8个字符，即000、001、010、011、100、101、110、111。对于题中给出的例子，一共有6个字符，因此采用3位码长的编码可以表示这些字符。
②A。
哈夫曼编码是一种最优的不定长编码方法，可以有效地压缩数据。要使用哈夫曼编码，除了知道文件中出现的字符之外，还需要知道每个字符出现的频率。图3-23a是题中给出的对应编码树，可以看到，每个字符及其对应编码如图3-23b所示，因此字符序列“ face ”的编码应为110001001101，选择A。
图3-23 哈夫曼编码过程
72）B。
根据队列的特点，元素出队的顺序与入队的顺序相同，因此，可知这7个元素的出栈顺序为 bdfecag 。对于入栈序列 abcdefg ，得到出栈序列 bdfecag 的操作过程为：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 出），如图3-24所示，可知栈 S 中元素最多时为4。因此， S 的容量最小为4。
图3-24 栈进出过程
73）C。
根据题中所给的遍历序列，可知其对应的二叉树如图3-25所示。
图3-25 二叉树
74）B。
进行二分查找时，首先与表中间位置上的元素进行比较，若待查找的元素大于中间元素，则接下来在后半区（是比中间元素更大者组成的有序子表）进行二分查找，否则在前半区（是比中间元素更小者组成的有序子表）进行二分查找。二分查找过程可用二分查找判定树来描述，即大于中间元素时走右分支，小子中间元素时走左分支，等于时查找成功结束。选项B是不可能的查找路径。
75）A。
76）①A。
②C。
优先队列是一种常用的数据结构，通常用堆实现。对应大顶堆和小顶堆，存在最大优先队列和最小优先队列。以最大优先队列为例，优先队列除了具有堆上的一些操作，如调整堆、构建堆之外，还有获得优先队列的最大元素、抽取出优先队列的最大元素、向优先队列插入一个元素和增大优先队列中某个元素的值。其中除了获得优先队列的最大元素的时间复杂度为 O （1）之外，其他几个操作的时间复杂度均为二叉树的高度，即 O （log 2 n ）。
77）问题1：①visited[0]=1，②visited[x[k]]==0，③c[x[k]][0]==1，④visited[x[k]]=1，⑤k=k-1、k--或--k。
问题2：⑥回溯法，⑦深度优先。
空①处及上下几行代码（while循环之前）是默认从0号顶点开始，x[0]=0表示0号顶点被访问过了，k=k+1也表示已经找到一个满足条件的顶点，故空①处肯定是设置0号顶点已经被访问过了，应该填visited[0]=1。
空②处根据注释可知邻接顶点x[k]未被访问过，执行break，则x[k]号顶点未被访问过的判断条件是visited[x[k]]==0，即②的答案。c[x[k-1]x[k]]==1是判断之前已经被访问过的顶点（x[k-1]）与x[k]是否为相邻顶点。
空③处的if判断表达式“找到一条哈密尔顿回路”，成立条件为x[k]<n，且k==n-1，同时还要满足 x[k]号顶点未被访问过（空②处已经判断），最后还要保证 x[k]号顶点与0号顶点之间有边（判断条件c[x[k]][0]==1）才行，故空③处应该填写c[x[k]][0]==1。
空④处为“设置当前顶点的访问标志，继续下一个顶点”，则k应该加1，且应该设置x[k]号顶点被访问过，即空④应该填写visited[x[k]]=1。
空⑤处所属的else代码块表示“没有未被访问过的邻接顶点，回退到上一个顶点”，则应该进行回溯，回退到上一个顶点，回溯的过程即使取消前一步因为“试探”而做的操作，即取消之前“试探”过程中设置的顶点编号（x[k]=0），取消之前“试探”过程中访问过的顶点（visited[x[k]]=0），取消之前因为“试探”而增加的顶点数量（k=k-1），故空⑤应该填写k=k-1（或k--、--k）。
该算法中，如下代码块即使去查找与x[k-1]号顶点相邻的顶点（从x[k]号开始“试探”），也是找到一个马上执行关键字break（即结束循环），然后执行该while循环后的代码块，之后的过程将不再查找x[k-1]号顶点的其他相邻顶点，如果x[k]号顶点不满足条件，则执行循环中else部分代码，即继续“试探”x[k]+1号顶点。如果在找到一个相邻顶点的情况下，还要继续去搜索其他的相邻顶点，则为广度优先方式，本题显然不是，而是深度优先。
根据以上分析，再结合以下代码块，此代码的功能为回退到上一个顶点继续搜索上一个顶点的其他相邻顶点，同时在回溯的过程中要取消之前因为“试探”而进行的操作。
通过以上分析，本题使用的是回溯法，用它可以系统地搜索一个问题的所有解或任一解。回溯法是一个既有系统性又带有跳跃性的搜索算法。它在包含问题所有解的解空间树中，按照深度优先的策略，从根节点出发搜索空间树，算法搜索解空间树的任一个节点时，总是先判断该点是否肯定不包含问题的解。如果肯定不包含，则跳过以该节点为根的子树的系统，逐层向其祖先节点回溯，否则进入该子树，继续按深度优先的策略进行搜索。只要搜索到任一解就可以结束了。
78）问题1：① k = k /2，② k ＞1，③ data[ k ]＜data[ k-dt ]，④ data[ j + dk ]= t 。
问题2：⑤ 小于，⑥ 否。
问题3：⑦（4，9，-1，8，20，7，15）。