1、软件水平考试（初级）程序员上午（基础知识）章节练习试卷 9及答案与解析 1 一个非零的无符号二进制整数，将各位依次左移 3位，低位补零，则新的数是原来数的 (1)倍；在此基础上，再右移 2位，高位补零，则此时的数是原数的 (2)倍。补码表示中，最高位为符号位，一个以补码表示的正数，经 (3)后，可扩大 4倍；一个以补码表示的负数，若经 (4)后，可扩大 4倍，若经 (5)后，可缩小 4倍。 （ A） 1000 （ B） 50 （ C） 8 （ D） 4 （ A） 1000 （ B） 4 （ C） 8 （ D） 2 （ A）左移 2位，低位补 0 （ B）右移 2位，低位补 0 （ C）左移 2
2、位，低位补 1 （ D）右移 2位，低位补 1 （ A）左移 2位，低位补 0 （ B）右移 2位，低位补 0 （ C）左移 2位，低位补 1 （ D）右移 2位，低位补 1 （ A）左移 2位，高位补 0 （ B）右移 2位，高位补 0 （ C）左移 2位，高位补 1 （ D）右移 2位，高位补 1 6 二维数组 F的行下标为 2至 6，列下标为 1至 8， F的每个数据元素均占 4个字节。在按列存贮的情况下，已知数据元素 F3， 2的第一个字节是 2054，则 F3， 4和 F4， 3的第一个字节的地址分别为 (35)和 (36)，而数组的第一个数据元素的第一个字节和数组最后一个元素的最后
3、一个字节的地址分别为 (37)和 (38)。对一般的二维数组 G而言，当 (39)时，共按行存储的 GI， J的地址与按列存储的 GJ， I的地址相同。 （ A） 2056 （ B） 2094 （ C） 2092 （ D） 2120 （ A） 2092 （ B） 2088 （ C） 2078 （ D） 2124 （ A） 2004 （ B） 2044 （ C） 2030 （ D） 1984 （ A） 2183 （ B） 2189 （ C） 2161 （ D） 2187 （ A） C的列数与行数相同 （ B） G的列的上界与 G的行的上界相同 （ C） G的列的下界与 G的行的下界相同 （ D）
4、 G的列的上下界与 G的行的上下界相同 11 树是由结点构成的，其中根结点数目为 (40)。二叉树有 (41)个根结点，按一定的转换规则，任一树都可以转换成唯一对应的二叉树。二叉树的查找有深度优先和广度优先二类，深度优先包括 (42)。当一棵二叉树的前序序列和中序序列分别是HCZDBPCA和 ECBDHFAC时，其后序序列必是 (43)，层次序列为 (44)。 （ A）只有 1个 （ B） 1或多于 1个 （ C） 0或 1个 （ D）至少 2个 （ A）只有 1个 （ B） 1或多于 1个 （ C） 0或 1个 （ D）至少 2个 （ A）前序遍历后序遍历中序遍历 （ B）前序遍历后序遍历层
5、次遍历 （ C）前序遍历中序遍历层次遍历 （ D）中序遍历后序遍历层次遍历 （ A） BDEAGFHC （ B） EBDGACFH （ C） HCFEDCBA （ D） HFGDEABC （ A） BDEACGFH （ B） EBDGACFH （ C） HCFEDCBA （ D） HFCCDEAB 16 数值数据在机器中的表示法有原码、反码、补码 (又称增 码 )等方法。定点数真值。表示法唯一的表示法是 (45)；在 (46)表示方式中最高位为 “0”表示负号而为 “1”表示正号；机器码为 n位时，采用反码、补码和移码来表示小数点固定在符号位与最高有效位之间的定点数时所可表示的真值 X的范围分
6、别为 (47)、 (48)和 (49)。 （ A）反码 （ B）移码 （ C）原码 （ D）补码 （ A）反码 （ B）移码 （ C）原码 （ D）补码 （ A） -(1-2-(n-1)X(1-2-(n-1) （ B） -(1-2-(n-1)X1 （ C） -1X(1-2-(n-1) （ D） -1X1 （ A） -(1-2-(n-1)X(1-2-(n-1) （ B） -(1-2-(n-1)X1 （ C） -1X(1-2-(n-1) （ D） -1X1 （ A） -(1-2-(n-1)X(1-2-(n-1) （ B） -(1-2-(n-1)X1 （ C） -1X(1-2-(n-1) （ D）
7、-1X1 21 若一个二义树具有下列性质：除叶子结点外，每个结点的值都大于其左子树上的一切结点的值，并小于等于其右子树上一切结点的值。这是一棵 (50)树。 现有一个菲波那契数列 an， a0 =a1=1， ak=ak-1+ak-2， k=2， 3 若把 a1，a2， ， a9填入具有这种性质的二叉树，一般可采用 (51)遍历法遍历该树上全部结点，得到由结点的值组成的升序序列。对下图 1.2给出的二叉树图形填入a1， a9 后，其结点 n9的值为 (52)，根结点的值为 (53)。若欲插入 a1， a9的平均值，则应该在 (54)增加一个结点。 （ A） B-树 （ B）最佳查找树 （ C）穿
8、线树 （ D）查找树 （ A）深度优先 （ B）中序 （ C）后序 （ D） 前序 （ A） 13 （ B） 8 （ C） 21 （ D） 57 （ A） 8 （ B） 21 （ C） 34 （ D） 66 （ A） n2与 n4之间 （ B） n6下 （ C） n5与 n9之间 （ D） n9下 26 堆是一种特殊的数据结构，选项 (55)是一个最大堆。堆排序是一种 (56)排序，其时间复杂性为 (57)。 (58)是不稳定的排序算法。外排序是指 (59)。 （ A） 19， 75， 34， 26， 97， 56 （ B） 97， 75， 34， 56， 19， 26 （ C） 97， 56
9、， 26， 19， 34， 75 （ D） 19， 34， 26， 97， 56， 75 （ A）归并 （ B）交换 （ C）选择 （ D）插入 （ A） 0(n) （ B） 0(n2) （ C） （ D） 0(nlogn) （ A）直接插入排序 （ B）归并排序 （ C）冒泡排序 （ D）希尔 (shell)排序 （ A）用机器指令直接对硬盘中需排序数据排序 （ B）把需排序数据，用其他大容量机器排序 （ C）把外存中需排序数据一次性调入内存，排好序后，再输回外存 （ D）对外存中大于内存允许空间的需排序的数据，通过多次内外存问的交换实现排序。 31 计算机中十六位浮点数的表示格 式为图 1
10、.4 某机器码为1010001010000000。 若阶码为移码且尾数为反码，则其真值为 (60)； 若阶码为移码且尾数为原码，则其真值为 (61)； 若阶码为补码且尾数为反码，则其真值为(62)； 若阶码为补码且尾数为原码，则其真值为 (63)，将其规格化后的机器码为(64)。 （ A） 0.00000001012 （ B） 2010 （ C） 1.2510 （ D） 20.96937510 （ A） 0.00000001012 （ B） 2010 （ C） 1.2510 （ D） 20.96937510 （ A） 0.00000001012 （ B） 2010 （ C） 1.2510 （
11、D） 20.96937510 （ A） 0.00000001012 （ B） 2010 （ C） 1.2510 （ D） 20.96937510 （ A） 1010001010000000 （ B） 10010101000000 （ C） 1101010100000000 （ D） 11110001010000 36 全加器是由两个加数 Xi和 Yi以及低位来的进位 Ci-1作为输入，产生向高位的进位 Ci以及本位利 Si的逻辑电路。 (65)和 (66)分别是进位 和本位和的正确逻辑表达式。全加器亦可通过半加器来实现，此时 Si=(67)。若某计算机采用 8位带符号补码表示整数，则可由 8个
12、全加器 (i =1， 2， 8 ， i=8为最高位，即符号位 )串接构成 8位加法器， CO=0。该加法器有一个状态寄存器，记录运算结果的状态。其中， N和 V分别表示符号位与溢出标志位，则其逻辑表达式分别为 (68)和 (69)。 （ A） XiYi+XiCi-1+YiCi-1 （ B） XiYi+XiSj+YiSi （ C） XiYi+XiCi-1+YiCi-1 （ D） (XiYi+XiYi).Ci-1 （ A） XiYiCi-1+XiYiCi-1+XiYiCi-1+XIYiCi-1 （ B） Ci-1(XiYi+XiYi)+Ci-1(XiYi+XiYi) （ C） Ci(XiYi+Xi
13、Yi)+Ci(XiYi+XiYi) （ D） Ci(Xi+Yi+Ci-1)+XiYiCi-1 （ A） （ B） （ C） （ D） （ A） X8Y8+X8C7+Y8C7 （ B） C7 C8 （ C） C8 X8 Y8 （ D） C7(X8Y8+X8Y8)+C7(X8Y8+X8Y8) （ A） X8Y8+X8C7+Y8C7 （ B） C7 C8 （ C） C8 X8 Y8 （ D） C7(X8Y8+X8Y8)+C7(X8Y8+X8Y8) 41 任一棵树均可唯一地转换成与它对应的二叉树。由树转换成的二叉树中，结点N的左子结点是 N在原树里对应结点的 (70)，而 N的右子女是原树里对应结点的
14、(71)。在下列二叉树中，图 1.4为 (72)树，图 1.5为 (73)树，图 1.6为 (74)树。（ A）最左边的子结点 （ B）最右边的子结 （ C）最邻近的右兄弟 （ D）最邻近的左兄弟 （ A）最左边的兄弟 （ B）最右边的兄弟 （ C）最邻近的右兄弟 （ D）最邻近的左兄弟 （ A）查找树 （ B）满二叉树 （ C）平衡树但不是满二叉树 （ D） B+树 （ A）查找树 （ B）满二叉树 （ C）平衡树但不是满二叉树 （ D） B+树 （ A）查找树 （ B）满二叉树 （ C）平衡树但不是满二叉捌 （ D） B+树 46 二维数组 A的行下标范围是 1 6，列下标范围是 2 8，
15、每个数组元素占八个字节，则该数组的体积为 (75)个字节，若已知 x的最后一个元素的起始字节地址为428，则 A的首地址 (即第一个元素的起始字节地址 )为 (76)，记为 As。若按行存储，则 A2， 5的起始地址是 (77)，结束字节地址是 (78)。若按列存储，则 A4， 8的起始字节地址为 (79)。 （ A） 336 （ B） 340 （ C） 388 （ D） 394 （ A） 108 （ B） 100 （ C） 94 （ D） 86 （ A） As+72 （ B） As+80 （ C） As+88 （ D） As+96 （ A） As+79 （ B） As+95 （ C） As+
16、87 （ D） As+143 （ A） As+186 （ B） As+234 （ C） As+270 （ D） As+312 51 下面是某种计算机的 32位短浮 点数格式如图 1.7 其中， M为用定点小数表示的尾数的绝对值，占 23位； Ms是尾数的符号位，占 1位； Ms和 M一起表示尾数。 E为用定点整数表示的阶码，占 8位。若机器表示中取阶码的基数为 2，求采用下列五种不同编码方式时，浮点数 -123625E-3(隐含基数为 10)规格化后的机器码： 阶码用补码方式、尾数用原码方式时，为 (80)； 阶码用补码方式、尾数用反码方式时，为 (81)； 阶码用移码方式、尾数用原码方式时，
17、为 (82)； 阶码用移码方式、尾数用补码方式时，为 (83)； 阶码用移码方式、尾数用反码方式时，为 (84)； （ A） 10000111100001000110000000000000 （ B） 00000111100001000101111111111111 （ C） 10000111111110000101111111111111 （ D） 00000111111110111010000000000000 （ A） 10000111100001000110000000000000 （ B） 00000111100001000101111111111111 （ C） 100001111
18、11110000101111111111111 （ D） 00000111111110111010000000000000 （ A） 10000111111110111010000000000000 （ B） 00000111100001000110000000000000 （ C） 10000111100001000110000000000000 （ D） 00000111100001000101111111111111 （ A） 10000111111110111010000000000000 （ B） 00000111100001000110000000000000 （ C） 10000
19、111100001000110000000000000 （ D） 00000111100001000101111111111111 （ A） 10000111111110111010000000000000 （ B） 00000111100001000110000000000000 （ C） 00000111111110000101111111111111 （ D） 10000111100001000101111111111111 56 For users, microkernel technology promises(11), compact and sophisticated opera
20、ting systems that are typically(12) across a range of hardware platforms. （ A） quickly （ B） speed （ C） slow （ D） fast （ A） portable （ B） made （ C） moveable （ D） use 58 In C program, all variables must be declared before(52), usually at the(53) of the function before any executable statements. （ A） s
21、tated （ B） instructed （ C） illustrated （ D） use （ A） end （ B） middle （ C） beginning （ D） last 60 In C language, external variables have to be defined(54) function, this(55)actual storage for it. （ A） in （ B） out （ C） inside （ D） outside （ A） allocates （ B） locates （ C） finds （ D） 100ks for 62 A fire
22、wall is a security system designed to(62) an organizations network against(63) （ A） prevent （ B） protect （ C） develop （ D） exploit （ A） operating （ B） programming （ C） threats （ D） service 64 The following suggestions increase programs (69) and make them easier to Maintain： 1 Use a standard indentio
23、n technique， blank lines， form feeds， and spaces 2 Insert plenty of (70) into your code （ A） reliability （ B） security （ C） readability （ D） usability （ A） java code （ B） C+ code （ C） assemble code （ D） comments 软件水平考试（初级）程序员上午（基础知识）章节练习试卷 9答案与解析 1 【正确答案】 C 2 【正确答案 】 D 3 【正确答案】 A 4 【正确答案】 A 5 【正确答案】
24、 C 【试题解析】 无符号数每左移一位相当于乘以 2，新数是原来的 8倍。右移相当于除以 2；正数的补码表示和原码一样，所以，一个以补码表示的正数，经左移 2位，低位补 0后，可扩大 4倍；反码表示的负数，左移加倍时，低位需要补 0；右移缩小时，高位需要补 1。 6 【正确答案】 B 7 【正确答案】 C 8 【正确答案】 C 9 【正确答案】 B 10 【正确答案】 D 【试题解析】 该数组可看作为 58的矩 阵，已知其元素 F32首地址为 2054，则 F34首地址为： F32+ (4-2*5*4+(3-3)*4=2054+40=2094 F43首地址：F32+(3-2)*5*4+(4-3
25、)*4=2078。首元素首字节地址 F21=F32-(2-1)*5*4-(3-2)*4=2030。量后字节的地址为： F68=F 32+6*5*4+3*4*3=1180-1=1179，注意最后一个元素的最后一个字节地址的计算方法。 上面的各次计算可以推导出一个公 式： 已知 Fab的首地址，每列有 n个元素，每个元素占 m个字节，则 Fxy首址为： Fab+(y-b)*n*m+(x-a)*m。 按行存储的 GI， J的地址与按列存储的 GJ,I的地址相同时，则 G的列的上下界与 G的行的上下界相同。 按行 Gij=S+(i-r)*Lr+j-1按列 Gji=S+(i-1)/L1+j-r其中， r
26、， 1分别为行、列的上后， Lr与 L1分别为行长度和列长度，显然，若要二者相等，则有 r=1；Lr=L1。即：列的上下界与行的上下界相同。 11 【正确答案】 A 12 【正确答案】 C 13 【正确答案】 A 14 【正确答案】 B 15 【正确答案】 C 【试题解析】 树是结点的集合。树根有且仅有一个。二叉树可以有零个或一个根结点，根节点为零时，二叉树为空树。深度优先查找包括前序遍历、后序遍历、中序遍历。一棵二叉树的前序序列和中序序列分别是 HGEDBFCA和 EGBDHFAC，前序序列首元素是根元素，于是推断出树根为 H，由中序序列可以推断 EGBD为左子树， FAC为右子树，按照该法
27、推至子树剩一个节点，可得该二叉树的 全部构成。 16 【正确答案】 D 【试题解析】 真值为零的机器码，其原码表示有 (100) 和 (00 0)两种表示负零和正零。反码表示分别为 (1111 和 (000) 。只有补码对零的表示只有一种(000) 。移码的定义为： 2+x。可以看出 x 0时，最高位为 1； x 0时，最高位为 0。最后一问即是考察 n 位有符号定点小数的表示范围，反码表示时为： -(1-2-(n-1)X(1-2-(n-1)；补码表示范围： -1X(1-2-(n-1)；移码表示范围为： -1X(1-2-(n-1)。 17 【正确答案】 B 18 【正确答案】 A 19 【正确
28、答案】 C 20 【正确答案】 C 21 【正确答案】 D 22 【正确答案】 B 23 【正确答案】 A 24 【正确答案】 B 25 【正确答案】 D 【试题解析】 二叉查找树是叶子结点外，每个结点的值都大于其左子树上的一切结点的值，并小于等于其右子树上一切结点的值的树。用 a1， ， a9填充该树后，因为左子树的元素总小于根元素，右子树的元素均大于根元素，故使用中序遍历后，可得到元素的一个升序排列。填充元素后，可得 到如图 1.3所示二叉树： 于是 n9位置的元素为 a6=13，根结点 n1为 a7=21。a1， ， a9的平均值为 (1+2+3+5+8+13+21+34+55)/9=1
29、5.6位于 a6 a7间。即应在 n1(a7)的左子树上，而该子树上最大结点 n9，即是 a6，故可将新结点加在 n9下，加在 n9的右子树上。 26 【正确答案】 B 27 【正确答案】 C 28 【正确答案】 D 29 【正确答案】 D 30 【正确答案】 D 【试题解析】 堆是一个完全 (除最底层外都是满的 )二叉树，并满足 如下条件： 1、根结点若有子树，则子树一定也是堆。 2、根结点一定大于 (或小于 )子结点。 当根结点大于子结点时，称为最大堆，反之称为最小堆。因为要求堆必须是完全二叉树，所以可以用线性的数据结构，比如数组，来实现堆。利用数组实现，则对于长为 N的堆中的元素从 0到
30、 N-1排列，有： i的父结点： Patent(i)=(i+1)/2-1 i的左叶子： Left(i)=(i+1)*2-1 i的右叶子： Right(i)=(i+1)*2 故 97， 75， 34， 56， 19， 26是一个最大堆，而 19， 34， 26， 97， 56， 75是一个虽小堆。 堆排序是一种选择排序法，对大量的记录进行堆排序是非常有效的。其时间复杂度为 O(nlogn)， n为待排序记录。快速排序、堆排序、希尔排序等都是不稳定的排序，而基数排序、归并排序是一种稳定的排序。 外排序是指待排序记录数量很大，以致内存不能容纳所有记录，在排序过程中尚需对外存进行访问的排序过程。点一定
31、大于 (或小于 )子结点。 31 【正确答案】 C 32 【正确答案】 C 33 【正确答案】 A 34 【正确答案】 A 35 【正确答案】 B 【试题解析】 若阶码为移码且尾 数为反码，故阶码值为 1010-1000=0010，即 2，而因为尾数大于零，则去掉符号位后为 0.0101，故左移两位后得到真值为：1.012=1.2510； 尾数为原码时，去掉符号位，仍为 0.0101，故真值为：1.012=1.2510； 若阶码为补码且尾数为反码，变反加一得绝对值为 0110，则阶码值为 -0110=-6，尾数为 0.0101，故右移 6位后得到真值为 0.00000001012。 若阶码为补
32、码且尾数为原码，尾数为 0.0101，故右移 6位后得到真值为 0.00000001012。规格化使得尾数变成 (0.5， 1)之间的数，则尾数应为 0.101，则阶码应变为 -7，其补码表示为 1001。故规格机器码为 100101010000000。 36 【正确答案】 C 37 【正确答案】 D 38 【正确答案】 A 39 【正确答案】 D 40 【正确答案】 B 【试题解析】 本位进位为 1即两加数、低进位同时最少有两个为 1的情况，即XiYi+XiCi-1+YiCi-1。 本位和为 1可以分解为：当两加数与低进位均为 1的情况(XiYiCi-1)=111，此时进位 Ci 为 1；当
33、没有进位产生时，两加数、低进 位有一个为1的情况 Ci(Xi+Yi+Ci-1)将两式相加得到量终结果。注意，当两加数、低进位有两个为 1时， Ci 为 1，第二个式子为 0。 半加器起异或的作用， Si可表示为两加数、低进位三者若有两个相同，则 Si为 1。 即 Xi Ci-1 Yi 8位加法器中，若C7为 0，则符号位由 X8Y8决定，进行异或即可，或表示为 x8 y8。 若 C7为1，则可表示成 (X8Y8+X8Y8)，即 C7(X8Y8+X8Y8)+C7(X8Y8+X8Y8)。 若 C8=1，表示符号位运算产生进位，此时若 C7=0，表示低位没有进位，说明是两加数 的符号位运算产生了进位
34、，则结果符号位必然不同于两加数的符号，产生溢出；否则，没有溢出。若 C8=0，表示 c7， x8， y8量多有一个是 1，若 C7=1，说明符号位改变，产生溢出。这种情况可以用半加表示，即 C7 C8。 41 【正确答案】 A 42 【正确答案】 C 43 【正确答案】 C 44 【正确答案】 A 45 【正确答案】 B 【试题解析】 任一棵树均可唯一地转换成与它对应的二叉树。由树转换成的二叉树中，结点 N的左子是 N在原树里对应结点的最左子结点，而 N的右子是原树里对应结点的邻 近的右兄弟。平衡树是它的左子树和右子树也都是平衡二叉树并且左于树秘右子树的深度之差的绝对值不超过 1。二叉查找树是
35、如果根结点的左子树非空，则左子树上所有的结点的值都小于根值；如果根结点的右于树非空，则右子树上所有的结点的值都大于根值；根结点的左子树和右子树也都是二叉查找树。则图 所示各结点平衡因子都 =1，故为平衡树。图二中，结点值按字母序比较大小，则显然是二叉查找树。图三是满二叉树。 46 【正确答案】 A 47 【正确答案】 B 48 【正确答案】 C 49 【正确答案】 B 50 【 正确答案】 D 【试题解析】 数组体积为： (5+1)(7)8=336。因为最后一个元素的起始字节地址为 428，可知数组的末地址为 435，又数组所占空间为 336，所以数组首地址是100，即数组元素地址从 100开
36、始至 435结束，共 336字节。 按行存储，则 A2， 5=As+(17+4)8=As+88。结束于： As+88+7=As+95。按列存储， A4， 8=As +(8-2)6+(4-1)8=Ax+312。 51 【正确答案】 D 52 【正确答案】 B 53 【正 确答案】 A 54 【正确答案】 C 55 【正确答案】 D 【试题解析】 -123625E-3换算为二进制真值为 -1111011.101。即 -0.11110111012。 阶码用补码方式 0111、尾数用原码方式时 111101110100000000000000， Ms 为1。即 00000111111110111010
37、0000000000000。 阶码用补码方式 0111、尾数用反码方式时 0000100010000000000000， Ms 为 1。即 00000111100001000110000000000000 阶码用移码方式 10000111、尾数用原码方式时，即10000111111110111010000000000000 阶码用移码方式、尾数用补码方式： 000010001100000000000000 时，即 10000111100001000110000000000000 阶码用移码方式、尾数用反码方式时， 10000111100001000101111111111111。 56 【正确
38、答案】 D 57 【正确答案】 A 【试题解 析】 对用户来说，微内核技术承诺了可以实现快速，紧凑，复杂精密的操作系统，而且该系统在一定范围的硬件平台上都是轻便的。 58 【正确答案】 D 59 【正确答案】 C 【试题解析】 在一段 C程序中，所有变量在使用前必须声明，通常在函数的开始处，可执行语句之前声明。 60 【正确答案】 D 61 【正确答案】 A 【试题解析】 c语言中，外部变量必须在所有函数体之外定义，并为之分配实际内存空间。 62 【正确答案】 C 63 【正确答案】 B 【试题解析】 防火墙是一 个安全系统，它被设计用来保护某组织的网络不受威胁。 64 【正确答案】 C 65 【正确答案】 D 【试题解析】 以下建议能增加程序的可读性，使得它们更加容易维护。 1使用标准的缩排技术、空行、换页、空格。 2在代码中添加大量注释。
