软件设计师第1部分计算机科学基础.doc

第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<N<=90时，易得F(X)=F(F(X+11))=F(X+11-10)=F(X+1)，于是当80<N<=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<LOG25!<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<M*N)表示成矩阵的第I行、第J列的元素(0≤I<M，0≤J<N)。 　　(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，所以时