●设∩表示集合的交运算，∪表示集合的并运算，┑A表示集合A的绝对补，A-B表示集合A与B的差，则A-B=(82)。
(82)A.A∪(A∩B)B.A∪┑BC.A∪(A∩B)D.A∩┑B
答案：(82)D
解析：所有属于A而不属于B的一切元素组成的集合S。称作B对A的差集，记作S=A-B。根据该定义，显然A-B=A∩┑B。
●集合Z26={0，1，…,25}，乘法密码的加密函数为Ek=Z26→Z26，Ek(i)=(ki)mod26，密钥k∈Z26-{0}，则加密函数K7(i)=(7i)mod26是一个(83)函数。
(83)A.满射但非单射
B.单射但非满射
C.非单射且非满射
D.单射且满射
答案：(83)D
解析：所i的取值为{0,1…，25}，因此{7i}={}。所以实质就是看7和26的最小公倍数是否在{7i}中。又7和26的最小公倍数为182。所以，f是单射。f的值域是{0，1…，25)，也有26个互不相同的元素，因此f是满射。
●与二分搜索算法类似，设计k分搜索算法(k>2)如下：首先检查n/k处(n为被搜索集合的元素个数)的元素是否等于要搜索的值，然后检查2n/k处的元素，…，这样，或者找到要搜索的元素，或者把集合缩小到原来的1/k;未找到要搜索的元素时，则继续在得到的集合上进行k分搜索;如此进行下去，直到找到要搜索的元素或搜索失败。此k分搜索算法在最坏情况下搜索成功的时间复杂度为(84)，在最好情况下搜索失败的时间复杂度为(85)。
(84)A.0(log n)
B.0(n log n)
C.0(logk n)
D.O(n logk n)
(85)A.0(log n)
B.O(n log n)
C.O(logk n)
D.O(n logk n)
答案：(84)C(85)C
解析：可以构造k叉树来描述k分查找。k分查找在查找成功时进行比较的关键个数最多不超过树的深度，即[n logkn(k+1)]+1，所以k分搜索算法在最坏情况下搜索成功的时间复杂度为0(n logn)。同样道理。查找不成功时。和给定值比较的关键字个数也至多为[n logkn(k+1)]+1，所以时间复杂度为0(n logk n)。
●在一颗完全二叉树中，其根的序号为1，(86)可判定序号为m和n的两个结点是否在同一层。
(86)A.[log2m]=[log2n]
B.log2m=log2n
C.[log2m]+1=[log2n]
D.[log2m]=[log2n]+1
答案：(86)A
解析：根据完全二叉树的性质，n层结点序号范围是[2h-1，2h-1]。因此可以用[log2p]=[log2q]判定。其值都是h一1。
●下列关键字序列中，(87)是堆。
(87)A.(10，50，80，30，60，20，15，18)
B.(10，30，60，20，15，18，50，80)
C.(10，15，18，50，80，30，60，20)
D.(10，18，15，20，50，80，30，60)
答案：(87)D
解析：堆的定义：n个元素的序列，当且仅当满足下面关系时。称为堆。ki≤k2i&&ki≤k(2i+1)或ki≥k2i&& ki≥k(2i+1)。若将和此序列对应的一维数组看成是一个完全二叉树。则堆的含义表明。完全二叉树中所有非终端结点的值均不大于(或不小于)其左右孩子结点的值。由此，若序列是堆，那么堆顶元素(完全二叉树的根)必为序列中n个元素的最小值(或最大值)。
●(88)从二叉树的任一结点出发到根的路径上，所经过的结点序列必按其关键字升序排列。
(88)A.二叉排序树
B.大顶堆
C.小顶堆
D.平衡二叉树
答案：(88)B
解析：根据大顶堆的性质。父结点总是大于子结点的关键值。所以从大顶堆任一结点出发到根的路径上，所经过的结点序列必按其关键字升序排列。
●若广义表L=((1，2，(3)))，则L的长度和深度分别为(89)。
(89)A.1和1
B.1和2
C.1和3
D.2和2
答案：(89)C
解析：广义表的长度是其元素个数，深度是广义表展开后括号的最大嵌套数。
●若对81个元素只进行三趟多路归并排序，则选取的归并路数为(90)。
(90)A.2
B.3
C.4
D.5
答案：(90)D
解析：一般情况下，对n个元素进行k路归并时，归并的趟数为大于logkm的最小整数。
●下面函数中渐进时间最小的是(91)。
(91)A.T1(n)=5n+nlog n
B.T2(n)=2n—lq log n
C.T3(n)=n2+3log n
D.T4(n)=n+90 log n
答案：(91)D
解析：常见渐进时间复杂度大小关系为0(1)≤0(n)≤O(nlogn)≤O(n2)o
●下面的程序段违反的算法原则是(92)。
/clip_image004_0000.jpg)
(92)A.健壮性
B.确定性
C.可行性
D.有穷性
答案：(92)D
解析：常函数中的while语句是死循环。
●蒙特卡罗(Monte Carlo)算法是一种常用的(93)算法。
(93)A.确定性
B.近似
C.概率
D.加密
答案：(93)C
解析：很多算法的每一个计算步骤都是固定的，而在下面我们要讨论的概率算法，允许算法在执行的过程中随机选择下一个计算步骤。许多情况下。当算法在执行过程中面临一个选择时，随机性选择常比最优选择省时。因此概率算法可在很大程度上降低算法的复杂度。概率算法的一个基本特征是对所求解问题的同一实例用同一概率算法求解两次可能得到完全不同的效果。这两次求解问题所需的时间甚至所得到的结果可能会有相当大的差别。一般情况下。可将概率算法大致分为四类：数值概率算法，蒙特卡罗(Monte Carlo)算法，拉斯维加斯(Las Ve-gas)算法和舍伍德(Sherwood)算法。
●分支一限界算法设计策略中通常采用(94)搜索问题的解空间。
(94)A.自底向上
B.深度优先
C.广度优先
D.拓扑序列
答案：(94)C
解析：分支限界法基本思想：分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。在分支限界法中。每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被子加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。
●下列算法中，在求解问题的过程中总是做出在当前看来是最好的选择，而并不从整体最优上加以考虑的算法是(95)。利用该设计方法可以解决(96)问题。
(95)A.分治法
B.贪心法
C.动态规划方法
D.回溯法
(96)A.排序
B.检索
C.背包
D.0/1背包
答案：(95)B(96)C
解析：贪心算法在求解问题的过程中并不从整体最优上加以考虑，而是做出在当前看来是最好的选择。利用贪心算法可以解决背包问题。
●下面的排序算法中，最坏情况下计算时间可以达到0(n log n)的是(97);该算法采用的设计方法是(98)。
(97)A.归并排序
B.插入排序
C.选择排序
D.冒泡排序
(98)A.回溯法
B.贪心法
C.动态规划方法
D.分治法
答案：(97)A(98)D
解析：以关键字比较为基础的排序算法在最坏情况下的计算时间下界为0(n log n)。归并排序在最坏情况下计算时间可以达到0(n log n)，其余三种算法在最坏情况下计算时间均是0(n2)。归并排序算法采用的设计方法是分而治之的方法。
