软件设计师第1部分计算机科学基础
第1部分计算机科学基础
●一般来讲，我们使用（1）来衡量查找算法的效率。
(1)A．所需的存储空间
B．元素总数
C．平均查找长度
D．算法难易程度
答案：(1)C
解析：查找算法效率的高低主要靠平均查找长度来衡量。
●某二叉树中，度为2的结点数为16个，度为1的结点数为31个，则叶结点数为(2)个。(2)A．15
B．16
C．17
D．47
答案：(2)C
解析：叶结点数为1+16 x2+31-16-31==17。
●在只想得到一个关键字序列中第k个最小元素之前的排序序列时，(3)排序方法的速度最快。如果有这样的一个序列(68，51，49，22，24，45，59，86，36，17，30，20，18)，得到第4个最小元素之前的部分序列(17，18，20，22)，使用所选择的算法实现时，要执行(4)次比较。
(3)A．基数排序
B．快速
C．归算
D．堆排序
(4)A．13
B．34
C．269
D．以上都错
答案：(3)D(4)B
解析：堆排序每一次调整，都可以得到最小或者最大元素，因此，在只想得到一个关键字序列中第k个最小元素之前的排序序列时，速度最快。采用堆排序算法时，经过34次比较，恰好可以将前4元素选出来。
●某有向图中含有n个顶点，则其有向边的数目最多为(5)。对于n个顶点k条边的无向连通图，利用Prim算法生成最小生成树的时间复杂度为(6)，利用Kruskal算法生成最小生成树的时间复杂度为(7)。
(5)A．n-1
B．n
C．n(n一1)
D．n(n一1)/2
(6)A．0((n+1)2)
B．0(n2+1)
C．0(n2-1)
D．0(n2)
(7)A．O(log2k)
B．O(log2k-1)
C．0(klog2k)
D．以上都错
答案：(5)C(6)D(7)C
解析：边最多的情况是：每个顶点到其他点均有一条边。此时没点有n一1条边，于是n个点共有n(n-1)条，由于是有向图，各边并不重复。利用Prim算法生成最小生成树的时间复杂度只与顶点数有关，复杂度为o(n2)；Kruskal算法生成最小生成树的时间复杂度只与边数有关，为0(klog2k)。
●某二叉树上的两个结点a、b，在(8)情况下，中序序列中a在b之前。
(8)A．a在b的右子树上
B．a在b的左子树上
C．a是b的祖先
D．a是b的子孙
答案：(8)B
解析：中序序列中，根结点总是在它的左子树的结点之后，右子树的结点之前。
●某线索二叉链表有k个结点中，则线索指针个数为(9)。
(9)A．k
B．k-1
C．k+1
D．k+10
答案：(9)C
解析．二叉链表中。线索指针个数比结点个数多1。
●某无向图有n个顶点e条边，则它的邻接表边表结点总数为(10)。
(10)A．n
B．e
C．2e
D．n+e
答案：(10)C
解析：一条边显然与两个顶点相联系，所以被记录2次。因此边表结点总数为2e。
●在某关键字互不相同的二叉排序树中，命题：最小元必无左孩子，最大元必无右孩子。是(11)。最小元和最大元一定是(12)。
(11)A．不正确
B．正确
C．命题错误
D．无法确定
(12)A．不是叶子节点
B．叶子节点
C．无法确定
D．以上都错
答案：(11)B(12)C
解析：在关键字互不相同的二叉排序树中，若最小元有左孩子，则左孩子小于该结点，与它是最小元矛盾。同理可知，最大元必无右孩子。最大元和最小元不一定是叶子结点。最小元可以有右结点，最大元可以有左孩子。
●某hash函数散列地址空间为0…n-1，k为关键字，假定散列函数为h(k)=k%P，当P为(13)时，冲突最小。
(13)A．小于n的最大素数
B．小于n的最大奇数
C．小于n的最大合数
D．小于n的最大偶数
答案：(13)A
解析：当P为小于n的最大素数时。散列函数的冲突比较小。
●在用二进制加法器对二一十进制编码的十进制数求和时，对有些结果需要修正。当和的四位二一十进制编码小于等于1001(相当于十进制数9)且向高位无进位时，(14)；当和小于等于1001且向高位有进位时，(15)；当和大于1001时，(16)。按照国标GB2312规定，一个汉字由(17)个字节组成。为了达到中西文兼容的目的，区分汉字与ASCIl码，汉字编码的最高位为(18)。
供选择的答案
(14)～(16)：A．不需修正
B．必须进行减6修正
C．必须进行加6修正
D．无法修正
(17)、(18)：A．1
B．0
C．2
D．2．5
答案：(14)A(15)C(16)C(17)C(18)A
解析：当和的四位二一十进制编码小于等于1001且向高位无进位时，加法结果不需要修正，其他情况均需要加6修正。GB2312规定，一个汉字由2个字节组成。汉字编码的最高位为1。
●一棵有9个叶子结点的哈夫曼(Huffman)树共有(19)个顶点。
(19)A．17
B．16
C．15
D．14
答案：(19)A
解析：哈夫曼(Huffman)树中没有度为l的分支结点。n个叶子经过n一1次合并，产生n一1个新结点。于是结点总数为n+n一1=17。本题也可以直接画出哈夫曼树而得到结果。
●如果仅知道一个指向链表中某结点的指针s，假设s的直接前驱P确实存在，则s所指结点数据元素与P的交换对于单链表(20)，对于单循环链表来说(21)，而对双向链表来说(22)。
(20)～(22)A．不可以交换
B．可以交换
C．无法确定
D．仅能交换一次
答案：(20)A(21)B(22)B
解析：对于单链表来说，仅知道一个结点的指针无法访问它的前驱结点，因此不能交换；对于单项循环链表来说，可以用一个指针沿着链表查找到s的前驱p，因此可以完成交换；而对于双向循环链表，同过s可以直接访问它的前驱P，因此可以交换。
●海明码是常用的“冗余校验”方法之一。在此方法中，若要求能检测出所有的双位错，并能校正单位错，则合法码字集中的码距至少为(23)。若原始数据的字长为5位，则采用海明码时其校验位至少为(24)位。对下面图1．1所示系统，仅当部件1，部件2和部件3全部正常工作时系统才能正常工作。图中数字为各部件的可靠性，整个系统的可靠性近似为(25)。如果将部件2和部件3改成由两个器件构成，如图1．2所示，只要器件a和b中有一个正常就能使部件2正常工作，只要器件c和d中有一个正常就能使部件3正常工作。图中数字是各器件可靠性，则部件2的可靠性是(26)，整个系统的可靠性近似为(27)。
(23)～(24)A．4
B．3
C．2
D．无法确定
(25)A．0.6800
B．0.7268
C．0.8168
D．0.9000
(26)A．0.68
B．0.88
C．0.97
D．0.99
(27)A．0.816
B．0.910
C．0.924
D．0.936
答案：(23)B(24)A(25)B(26)C(27)B
解析：海明码是一种可以纠正一位差错的编码。它是利用在信息位为k位，增加r位冗余位，构成一个n=k+r位的码字，然后用r个监督关系式产生的r个校正因子来区分无错和在码字中的n个不同位置的一位错。能检测出所有的双位错，并能校正单位错。则合法码字集中的码距至少为3位。
当部件(1)～(3)正常时，系统正常，则此概率为：0.85*0.9*0.95=0.7268。
如图b时，则部件2的可靠性为：1-(1-0.8)*(1-0.85)=0．97。同样，可得部件C正常的概率为0.99则系统可靠性为：0.85×0.97×0.99=0.816。
●在对二叉树进行前序、中序和后序遍历时，最适合采用的方法是(28)。
查找树中，由根结点到所有其他结点的路径长度的总和称为(29)，而(30)使上述路径长度总和达到最小，它一定是(31)。
在关于树的几个叙述中，只有(32)是正确的。
(28)A．队列操作
B．迭代程序
C．递归程序
D．栈操作
(29)A．路径和
B．深度和
C．总深度
D．内部路径长度
(30)A．丰满树
B．B+-树
C．B-树
D．穿线树
(31)A．B-树
B．平衡树
C．非平衡树
D．穿线树
(32)A．平衡树一定是丰满树
B．m阶B一树中，每个非叶子结点的后代个数≥[m/2]
C．m阶B-树中，具有k个后代的结点，必含有k-1个键值
D．用指针方式存储有n个结点二叉树，至少要有n+1个指针
答案：(28)C(29)D(30)A(31)B(32)C
解析：前序、中序和后序遍历法最适合采用递归算法来实现。查找树中，由根结点到所有其他结点的路径长度的总和称为内部路径长度，而使内部路径长度总和达到最小的树称为车满树。它必一定是平衡树，因为如果丰满树如果不是平衡树。则调整其成为平衡树后．。被调整结点高度必定减小，则内部路径长度随之减小。那么原树就不是丰满树。产生矛盾，得证。m阶B-树中，若结点含有k-1个键值，则具有k个后代。
●查找二叉树中，结点值大于左子树所有结点值，而小于右结点所有结点值。现在有一棵查找二叉树，它的结点A、B、c、D、E、F依次存放在一个起始地址为a(假定地址以字节为单位顺序编号)的连续区域中，每个结点占6个字节：前四个字节存放结点值，后二个字节依次放左指针、右指针。若该查找二叉树的根结点为D，则它的一种可能的前序遍历为(33)，相应的层次遍历为(34)。在以上两种遍历情况下，结点C的左指针的存放地址为(35)，它的内容为(36)。结点C的右指针的内容为(37)。
(33)A．DAFCBE
B．DFEACB
C．ADBCFE
D．DACBEF
(34)A．DAECFB
B．DFACEB
C．ABCFDE
D．DEFACB
(35)A．a+15
B．a+16
C．a+18
D．a+19
(36)A．a+6
B．a+10
C．a+14
D．a+18
(37)A．a+4
B．null
C．a+12
D．a+16
答案：(33)D(34)A(35)B(36)A(37)B
解析：可能的前序遍历为DACBEF。如图示。则其层次遍历为DAECFB。
C结点左指针指向B的首地址，即为a+6。C结点左指针的地址为C的第五字节，即a+12+4=a+16。结点A的右子树为空，右指针为null。
●一般来说，递归算法的执行过程可先后分成两个阶段，它们是(38)和(39)。
(38)A．枚举
B．试探
C．递推
D．分析
(39)A．返回
B．合成
C．回溯
D．回归
答案：(38)C(39)D
解析：递归算法的执行过程可分递推和回归两个阶段。在递推阶段，把较复杂的问题(规模为n)的求解推到比原问题简单一些的问题(规模小于n)的求解。回归阶段，当获得最简单情况的解后，逐级返回。依次得到稍复杂问题的解。
●当求解一个问题既可以用递归算法，也可以用递推算法时，我们优先考虑(40)算法，因为(41)。
(40)A．递归
B．递推
C．先递归后递推
D．先递推后递归
(41)A．递归的效率比递推高
B．递归易于问题求解
C．递推的效率比递归高
D．递推宜于问题分解
答案：(40)B(41)A
解析：递归算法不断进行函数调用和返回，需要使用堆栈保存返回地址，回归时需要弹栈回到调用函数中。所以耗费资源(时间，空间)较多，在递推、递归都可以使用的时候，使用递推可以获得更高的效率。
●数据结构中的贪心算法的特点是(42)。
(42)A．求取全部可行解
B．只求最优
C．不求最优，只求满意
D．求取全部最优解
答案：(42)C
解析：贪心算法是一种不追求最优解。只希望得到当前满意解的方法。
●二一十进制编码是一种使用4位二进制数表示一位十进制数的方法，在用二进制加法器求和需要特殊处理，当和的本位十进制数二一十进制编码小于等于1001且向高位无进位时(43)；当和小于等于1001且向高位有进位时，(44)；当和大于1001时，(45)。
(43)～(45)A．不需修正
B．加6修正
C．减6修正
D．无法判别
答案：(43)A(44)B(45)B
解析：二一十进制编码采用0001表示十进制1，0010表示十进制2，依次类推，1001表示十进制9。十进制运算时，当相加两数之和小于等于9(1001)时，可以直接相加，不需要修正；当大于9时便产生进位，直接相加得到时无效的编码，这时需对和数进行加6修正。因为4位二进制数能表示16个码元，而十进制数只有0到9十个码元。修正时加6，恰好能得到正确的十进制码元。例如1+9=10，正确码元为0000。二进制0001和1001直接相加得到1010。加上6即O110后。得到0000。
●“进位”位移入被操作数的最高位，其余所有位接收其相邻高位值，最低位舍去的操作是(46)指令。被操作数的最高位保持不变，其余所有位接收其相邻高位值，最低位移到“进位”位中的操作是(47)指令。在程序执行过程中改变按程序计数器顺序读出指令的指令属于(48)。实际地址是程序计数器的内容加上指令中形式地址值的寻址方式是(49)。特权指令在多用户、多任务的计算机系统中必不可少，它主要用于(50)。
(46)、(47)A．逻辑右移
B．算术右移
C．乘2运算
D．除2运算
(48)A．传送指令
B．转移指令
C．输入输出指令
D．特权指令
(49)A．相对寻址
B．直接寻址
C．基址寻址
D．变址寻址
(50)A．系统硬件自检和配置
B．检查用户的权限
C．用户写汇编程序时调用
D．系统资源的分配和管理
答案：(46)A(47)D(48)B(49)A(50)D
解析：逻辑右移指所有位右移，最低位舍去。若最高位不变，则为算术运算，具体操作视相应情况而定。转移指令改变程序计数器中顺序读出指令的地址值。使程序发生跳转。相对寻址地址值是当前程序计数器的值与指令中偏移量的和。特权指令用于对系统资源的管理和分配。
●算法中的每一条指令必须有确切的含义，并且在任何条件下，算法只有唯一的一条执行路径，这句话说明算法具有(51)特性。
(51)A．正确性
B．确定性
C．可行性
D．健壮性
答案：(51)B
解析：算法具有有穷性、确定性、可行性、输入、输出五个特点。其中算法中的每一条指令必须有确切的含义，并且在任何条件下。算法只有唯一的一条执行路径说明的是算法的确定性。
●排序算法中的快速排序算法采用的思路是(52)。
(52)A．回溯法
B．分治法
C．动态规划
D．分支定界法
答案：(52)B
解析：快速排序的基本思想是：按照某个基准元素，通过一轮排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比基准元素小：另外一部分的所有数据都比基准元素大，然后再按此方法对这两部分数据分别进行快速排序。整个排序过程可以递归进行，以此达到整个数据变成有序序列。
●哈夫曼(Huffman)编码是一种常用的压缩编码方法，它可以用来构造具有(53)的二叉树，这是一种采用了(54)策略的算法。
(53)A．后缀码
B．最优后缀码
C．前缀码
D．最优前缀码
(54)A．贪心
B．回溯
C．递推
D．分治
答案：(53)D(54)A
解析：哈夫曼(Huffman)编码是一种常用的压缩编码方法，是Huffman于1952年为压缩文本文件建立的。它的基本原理是频繁使用的数据用较短的代码表示，较少使用的数据用较长的代码代替，每个数据的编码各不相同。这些代码都是二进制码，且编码的长度是可变的。编码必须保证不能出现一个码字和另一个的前几位相同的情况。Huffman编码算法具体实现是：首先统计出每个符号出现的频率，然后把上述频率按从小到大的顺序排列。每一次选出最小的两个值，作为二叉树的两个叶子节点，将和作为它们的根节点，这两个叶子节点不再参与比较，新的根节点参与比较。重复上一步，直到最后得到和为1的根节点。将形成的二叉树的左节点标0，右节点标1。把从最上面的根节点到最下面的叶子节点途中遇到的0，1序列串起来，就得到了各个符号的编码。
●二分查找是查找算法中效率非常高的算法，当用递归算法实现n个不同元素构成的有序序列的二分查找，使用的递归工作栈的最小容量应为(55)。
(55)A．Inn
B．[n/2]
C．[log2n]
D．[log2(n+1)]
答案：(55)D
解析：将该有序序列做成一棵完全的二叉查找树，树的高度即为查找失败时进行递归调用次数最多的情况，
即log2(n+1)的整数部分值。
●函数的渐进时间是考虑当问题规模趋于无穷时，函数岁时间变化的趋势，下述函数中渐进时间最小的是(56)。
(56)A．T1(n)=3nlog2n-100log2n
B．T2(n)=2nlog2n-100log2n
C．T3(n)=n2—100log2n
D．T4(n)=nlog2n+100log2n
答案：(56)D
解析：对函数的渐进时间影响最大的是最高数量级，若相同则必须进一步考虑渐进表达式中的常数因子，通过比较不难得出T4(n)=nlog2n+100log2n渐进时间最小。
●写出每种算法第一趟排序后得到的结果：快速排序(选第一个记录为基准元素)得到(57)，希尔排序(增量为5)得到(58)，堆排序得到(59)，二路归并排序得到(60)，链式基数(基数为10)排序得到(61)：关键字(12，2，16，30，8，28，4，10，20，6，18)，递增排序。
(57)A．10，6，18，8，4，2，12，20，16，30，28
B．6，2，10，4，8，12，28，30，20，16，18
C．2，4，6，8，10，12，16，18，20，28，30
D．6，10，8，28，20，18，2，4，12，30，16
(58)A．2，4，6，8，10，12，16，18，20，28，30
B．6，2，10，4，8，12，28，30，20，16，18
C．12，2，10，20，6，18，4，16，30，8，28
D．30，10，20，12，2，4，16，6，8，28，18
(59)A．30，28，20，12，18，16，4，10，2，6，8
B．20，30，28，12，18，4，16，10，2，8，6
C．2，6，4，10，8，28，16，30，20，12，18
D．2，4，10，6，12，28，16，20，8，30，18
(60)A．2，12，16，8，28，30，4，6，10，18，20
B．2，12，16，30，8，28，4，10，6，20，18
C．12，2，l6，8，28，30，4，6，10，28，18
D．12，2，10，20，6，18，4，16，30，8，28
(61)A．10，6，18，8，4，2，12，20，16，30，28
B．12，2，10，20，6，18，4，16，30，8，28
C．2，4，6，8，10，12，16，18，20，28，30
D．30，10，20，12，2，4，16，6，8，28，18
答案：(57)B(58)C(59)C(60)B(61)D
解析：希尔排序的基本思想：将整个无序序列分割成若干小的子序列分别进行插入排序。序列分割方法：将相隔某个增量h的元素构成一个个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序，排序就完成。
堆排序的基本思想：对一组待排序记录，首先把它们按堆的定义排成一个序列(即建立初始小或大堆)，输出顶端最小或者最大元素，然后将剩余的关键字再调整成新堆。便得到次小或者次大的关键字。如此重复进行，直至全部关键字排成有序序列。
二路归并排序的基本思想：将两个有序文件合并成一个新的有序文件。它是把一个有n个记录的无序文件看成是由n个长度为l的有序文件组成的文件，然后进行两两归并。得到(n/2)个长度为2或1的有序文件。再两两归并，如此重复，直至全部有序。
基数排序的基本思想是：首先按最低有效位的值把n个关键宇分配到r个队列中，然后从小到大将各队列中关键字再依次收集起来；接着再按次低有效位的值把刚刚收集起来的关键字分配到r个队列中。重复上述过程，直至最高有效位，这样便得到一个从小到大的有序序列。队列采用链式存储分配时。称为链式基数排序。
●AOE(Activity On Edge)网中的关键路径是指(62)。
(62)A．最长的回路
B．最短的回路
C．从源点到汇点(结束顶点)的最短路径
D．从源点到汇点(结束顶点)的最长路径
答案：(62)D
解析：AOE(Activity On Edge)网是边表示活动的网。它是一个带权的有向无环图，顶点表示事件。弧表示活动，权表示活动持续的时间。通常AOE网用来估算工程完成的时间。完成工程的最短时间是从开始点到完成点的最长路径长度(关键路径)，即路径上各活动持续时间之和。
●以下关键字序列中不符合堆定义的是(63)。
(63)A．(202，187，200，179，182，162，184，142，122，112，168)
B．(202，200，187，184，182，179，168，162，142，122，112)
C．(202，187，142，179，182，162，168，200，184，112，122)
D．(112，122，142，162，168，179，182，l84，187，200，202)
答案：(63)D
解析：堆的定义如下：具有n个元素的序列(h1,h2…，hn)，当且仅当满足(hi>=h2i。hi>=2i+1)或(hi<=h2i，hi<=2i+1)(i=1，2…，n/2)时称之为堆，前者称为最大堆，后者称为最小堆。根据此定义判断。C不是堆。
●一个具有167个结点的完全二叉树，其叶子结点个数为(64)。
(64)A．83
B．84
C．85
D．86
答案：(64)B
解析：完全二叉树中只有度为0和度为2的结点。设为n0和n2，于是总结点数为no+n2。度为2的结点衍生出2个子结点。度为0的结点没有子结点；根结点不是任何点的子结点，所以结点总数还可以表示为2n2+1。于是得到等式nO+n2=2n2+1，推出nO=n2+1。总结点数=2n0-1。本题中。总结点数为167，得nO=84，即叶子结点个数为84。
●若一个森林(非连通无向图)具有n个结点、k条边(n>k)，则该森林中必有(65)棵树。(65)A．k
B．n
C．n-k
D．n+k
答案：(65)C
解析：设该森林共有m棵树，每棵树有ni个结点，根据树的性质可得：
1．n=n1+n2+r13…+nm
2．k=(n1-1)+(n2-1)+(n3-1)……+(nm-1)
上面两式相减得n-k=1+1+1+1……=m。而m是树的个数。
●若G是一个具有28条边的非连通无向图(不含自回路和多重边)，则图G至少有(66)个顶点。
(66)A．11
B．10
C．9
D．8
答案：(66)C
解析：G是一个非连通无向图，则G至少有2个连通分量。顶点数目最少时，即顶点容纳的边最多，则连通分量比是完全图。8个顶点形成的完全图可容纳36条边，再加一个自成一个连通分量的顶点，所以该图至少有9个点。
●将两个长度为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
(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
(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
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)。归并排序算法采用的设计方法是分而治之的方法。