软件设计师第1部分计算机科学基础一
软件设计师第1部分计算机科学基础二
●将两个长度为n的递减有序表归并成一个长度为2n的递减有序表，最少需要进行关键字比较(67)次。
(67)A.1
B.n-1
C.n
D.2n
答案：(67)C
解析：当一个有序表中的最小关键字比另一个表的最大关键字还大时，则最少比较关键字n次。
●设集合N={0，1，2，…}，f为从N到N的函数，且当0≤x≤90时f(x)=f(f(x+11))，当X>90时f(X)=X-10。经计算f(90)=81，f(89)=81，f(49)=(68)。
(68)A.39
B.49
C.81
D.92答案：(68)C
解析：当80<=90时，易得f(x)=f(f(x+11))=f(x+11-10)=f(x+1)，于是当80<=90时，f(x)恒等于f(89)即81。递推f(49)得f(49)=f(f(f(f(82))))=f(f(f(81)))=f(f(81))=f(81)=81。
●集合A={1.2.3}上的二元关系R为：R={<1，1>，<3，3>，<1，2>)}，则二元关系R是(69)。
(69)A.自反的
B.反自反的
C.对称的
D.传递的
答案：(69)C
解析：由<2，2>不属于R知R不是自反的;由<1，1>属于R知R不是反自反的;由<1，2>属于R而<2，1>不属于R知R不是对称的。
●快速排序最坏情况下的时间复杂度为(70)。
(70)A.0(log2n)
B.O(n)
C.O(nlog2n)
D.O(n2)
答案：(70)D
解析：对n个元素进行快速排序时，最坏情况下的时间复杂度为O(n2)。
●任何一个基于“比较”的内部排序的算法，若对5个元素进行排序，则在最坏情况下所需的比较次数至少为(71)。
(71)A.7
B.8
C.21
D.120
答案：(71)A
解析：对于5个记录的集合任何一个基于“比较”的内部排序的算法的判定树的叶子结点数目为5!，此判定树的树高至少为log25!。由5!=120，27=128，26=64可得6<7。因此在最坏情况下所需的比较次数至少为7。
●元素的存储地址与其关键字之间存在某种映射关系的存储结构是(72)。
(72)A.树形存储结构
B.线性存储结构
C.索引存储结构
D.散列存储结构
答案：(72)D
解析：散列存储结构中将结点按其关键值的散列地址存储到散列表中，其关键字与其存储地址之间按照某种关系进行映射。
●若循环队列存储在数组Q[0，m-1]中，变量r表示循环队列中队尾元素的实际位置，其移动按r=(r+1)mod m进行，变量l表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是(73)。
(73)A.r-1
B.(r-1+m)mod m
C.m-1
D.(1+r+m-1)mod m
答案：(73)D
解析：按照循环队列的定义，因为元素移动按照r=(r+1)mod m进行。当数组Q[m-1]存放了元素之后，下一个入队的元素将存放在Q[0]，因此。循环队列的队首元素的实际位置是(1+r+m-1)mod m。
●一个简单无向图含有n个顶点和e条边，则在其邻接矩阵存储结构中，零元素个数为(74)。
(74)A.e
B.2e
C.n2-e
D.n2-2e
答案：(74)D
解析：无向图的邻接矩阵是对称的，图中的一条边对应邻接矩阵中两个非零元素。因此该图的邻接矩阵存储结构中。零元素个数为n2-2e。
●一棵9个顶点的哈夫曼(Huffman)树共有(75)个叶子结点。
(75)A.7
B.6
C.5
D.4
答案：(75)C
解析：哈夫曼(Huffman)树是严格的二叉树。没有度为1的分支结点。n个叶子经过n-1次合并，产生n-1个新结点。于是得到关系式n+n-1=9，推出n=5。本题也可以直接画出哈夫曼树而得到结果。
●采用邻接矩阵来存储简单有向图时，则其某一个顶点i的出度等于该矩阵(76)。
(76)A.所有值为1的元素总数
B.第i行中值为1的元素个数
C.第i行中值为1的元素个数n2-2e
D.第i行及第i列中值为1的元素总个数
答案：(76)B
解析：采用邻接矩阵存储简单有向图时，其邻接矩阵第i行元素的和即为顶点i的出度，第i列元素的和即为顶点i的入度。
●在一棵度为4的树中，若有3个度为4的结点，有1个度为2的结点，没有度为1的结点，则有(77)个度为0的结点。
(77)A.9
B.10
C.11
D.12
答案：(77)C
解析i每个度为4的结点衍生出4个子结点，每个度为3的结点衍生出3个子结点，每个度为2的结点衍生出2个子结点，再加上根结点，于是结点总数为3*4+2+1=15。减去度非零的4个结点，得到度为0的结点数为11个。
●某二叉树的先根遍历序列中x结点在Y结点之前，而在其后根遍历序列中X结点在y结点之后，则x结点和Y结点的关系是(78)。
(78)A.X是Y的左兄弟
B.X是Y的祖先
C.X是Y的右兄弟
D.X是y的后裔
答案：(78)B
解析：二叉树的先根遍历序列中，根结点总是出现在其子树结点之前;二叉树的后根遍历序列中，根结点总是出现在其子树结点之后。因此。x结点是Y结点的祖先。
●设顺序存储的某线性表共有108个元素，按分块查找的要求等分为4块。若对索引表采用顺序查找方法来确定子块，且在确定的子块中也采用顺序查找方法，则在等概率的情况下，分块查找成功的平均查找长度为(79)。
(79)A.14
B.17
C.23
D.54
答案：(79)B
解析：分块查找(Blocking Search)又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法。二分查找表由”分块有序”的线性表和索弓l表组成。表R[1…n]均分为b块。前b-1块中结点个数为s=[n/ b]，第b块的结点数允许小于等于s;每一块中的关键字不一定有序。但前一块中的最大关键字必须小于后一块中的最小关键字，即表是”分块有序”的。抽取各块中的最大关键字及其起始位置构成一个索引表ID[1…b]。即：ID[i](1≤i≤b)中存放第i块的最大关键字及该块在表R中的起始位置。由于表R是分块有序的。所以索引表是一个递增有序表。分块查找的基本思想是：(1)首先查找索引表：索引表是有序表。可采用二分查找或顺序查找，以确定待查的结点在哪一块。(2)然后在已确定的块中进行顺序查找，由于块内无序，只能用顺序查找。
平均查找长度ASL：分块查找是两次查找过程。整个查找过程的平均查找长度是两次查找的平均查找长度之和。
①以二分查找来确定块，分块查找成功时的平均查找长度
ASL1=ASLbn+ASLsq≈log2(b+1)-1+(S+1)/2≈log2(n/s+1)+s/2
②以顺序查找确定块，分块查找成功时的平均查找长度
ASL2=(b+1)/2+(s+1)/2=(S2+2s+n)/(2s)
本题中。n=108，b=4，s=27，计算得平均查找长度为17。
●将一维数组A[0，m*n-1]存放到m行、n列的矩阵中，则下面的对应关系(80)可将元素 A[k](0≤k
(80)A.i=k/n，i=k%m
B.i=k/n，j=k%n
C.i=k/m，j=k%m
D.i=k/m，j=k%n
答案：(80)B
解析：把A数组的前n个元素放到B数组的第一行中，A数组的第n个元素放到B数组的第二行中。依此类推，A数组的最后n个元素放到B数组的最后一行。求A[k]在B数组中的位置，应先确定行，应该是k/n行，然后再确定列。显然是k%n。
●设f表示某个二元逻辑运算符，XfY的真值表见表1，则XfY等价于(81)。
(81) A.X∧┑Y
B.┑X∧Y
C.┑X∧┑Y
D.┑X∨┑Y
答案：(81)B
解析：将真值表的各项代入可得只有B正确。
●设∩表示集合的交运算，∪表示集合的并运算，┑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)。归并排序算法采用的设计方法是分而治之的方法。