09年5月软考数据库系统工程师专家参考答案(上午)
09年5月软考数据库系统工程师专家参考答案(下午)
第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位。