1、程序员-计算机科学基础及答案解析(总分：122.00，做题时间：90 分钟)一个非零的无符号二进制整数，将各位依次左移 3位，低位补零，则新的数是原来数的 (1) 倍；在此基础上，再右移 2位，高位补零，则此时的数是原数的 (2) 倍。补码表示中，最高位为符号位，一个以补码表示的正数，经 (3) 后，可扩大 4倍；一个以补码表示的负数，若经 (4) 后，可扩大 4倍，若经 (5) 后，可缩小 4倍。（分数：5.00）A.1000B.50C.8D.4A.1000B.4C.8D.2A.左移 2位，低位补 0B.右移 2位，低位补 0C.左移 2位，低位补 1D.右移 2位，低位补 1A.左移 2位
2、，低位补 0B.右移 2位，低位补 0C.左移 2位，低位补 1D.右移 2位，低位补 1A.左移 2位，高位补 0B.右移 2位，高位补 0C.左移 2位，高位补 1D.右移 2位，高位补 1将十进制数-35 化成二进制数原码、补码、反码表示(符号位和数值位共 8位)。二进制数原码为： (6) ，补码为 (7) ；反码为 (8) （分数：3.00）A.1 0100011B.1 0100001C.1 0110011D.00100011A.1 1010101B.1 101110lC.1 0011101D.0 1011101A.1 1011101B.1 101110lC.1 1011100D.0
3、10111001.下面程序段的时间复杂度是 (9) 。for(i=0，k=0；n；1+)k+=Aij；for(j=1；jm；j+)Aij=1（分数：1.00）A.O(n)B.O(m+n+1)C.O(m+n)D.O(m*n)2.在单链表中，指针 P指向元素为 x的结点，语句 (10) 现“删除 x的后继”（分数：1.00）A.p=pmext；B.pnext=pnextnext；C.pnext=p；D.p=pnextnext；3.某单循环链表头指针为 head且表长大于 1，指针 p指向表中某个结点，若 pnextnext= head，则 (11) 。（分数：1.00）A.p指向头结点B.p指向尾
4、结点C.*p的直接后继是头结点D.*P的直接后继是尾结点4.判定“带头结点的链队列为空”的条件是 (12) 。（分数：1.00）A.front= =NULLB.rear= =NULLC.front =Q.rearD.front!=Q.rear5.在一个单链表 HL中，若要向表头插入一个由指针 P指向的结点，则执行 (13) 。（分数：1.00）A.HL=p；pnext=HL；B.pnext=HL；HL=p；C.pnext=HL；p=HL；D.Pnext=HLnext；HLnext=p；6.n个顶点的强连通图中至少含有 (14) 。（分数：1.00）A.n-1条的向边B.n条有向边C.n(n-1
5、)/2条有向边D.n(n-1)条有向边7.广义表 A=(a，(h)，()，(c，(d)，e)的深度为 (15) 。（分数：1.00）A.4B.5C.6D.78.一棵含 28个结点的：二叉树的高度至少为 (16) 。（分数：1.00）A.3B.4C.5D.69.已知二叉树的中序序列为 DBEACPC，先序序列为 ABDECPC，则后序序列为 (17) 。（分数：1.00）A.DEBACFCB.DEFCBCAC.DEBCFCAD.DEBCFCA10.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为 (18) 。（分数：1.00）A.O(1)B.O(n)C.D.O(n2)在某关键字互不相同的二叉
6、排序树中，命题：最小元必无左孩子，最大元必无右孩子。是 (19) 。最小元和最大元一定是 (20) 。（分数：2.00）A.不正确B.正确C.命题错误D.无法确定A.不是叶子节点B.叶子节点C.无法确定D.以上都错11.由权值分别为 3，8，6，2，5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为 (21) 。（分数：1.00）A.24B.48C.72D.5312.无向图中一个顶点的度是指图中 (22) 。（分数：1.00）A.通过该顶点的简单路径数B.与该顶点相邻接的顶点数C.通过该顶点的回路数D.与该顶点连通的顶点数13.已知一个图如图 1.1所示，从顶点 b出发进行广度优先遍历可能得到
7、的序列为 (23) 。（分数：1.00）A.b a c e d fB.b a c d f eC.b a c e f dD.b a c e f d14.当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为 (24) 参数，以节省参数值的传输时间和存储参数的空间。（分数：1.00）A.整形B.引用型C.指针型D.常值引用型15.向一个长度为 N的顺序表中插入个新元素的平均时间复杂度为 (25) 。（分数：1.00）A.O(N)B.O(1)C.O(logN)D.O(N2)16.下面的排序方法中，平均时间性能为 O(nlogn)且空间性能最好的是 (26) 。（分数：1.00）
8、A.基数排序B.堆排序C.归并排序D.快速排序17.已知一组关键字为 18，48，36，72，79，82，23，40，16，35，其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是 (27) 。（分数：1.00）A.18，36，48，72，23，40，79，82，16，35B.18，36，48，72，16，23，40，79，82，35C.18，36，48，72，16，23，35，40，79，82D.16，23，18，35，36，40，48，72，79，8218.设顺序存储的线性表共有 287个元素，按分块查找的要求等分成 7块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺
9、序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为 (28) 。（分数：1.00）A.41B.25C.45D.6219.在一个单链表中，q 结点是 p结点的前驱结点，若在 q与 p之间插入结点 s，则执行 (29) 。（分数：1.00）A.slink=plink；plink=s；B.plink=s；slink=q；C.plink=slink；slink=p；D.qlink=s；slink=p；20.一个栈的人栈序列为 a，b，c，则出栈序列不可能的是 (30) 。（分数：1.00）A.c，b，aB.b，a，cC.c，a，bD.a，c，b21.栈的数组表示中，top 为栈顶指针，栈
10、空的条件是 (31) 。（分数：1.00）A.top=0B.top=maxSizeC.top=maxSizeD.top=-122.栈和队列的共同特点是 (32) 。（分数：1.00）A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除D.没有共同点23.当利用大小为 n的数组顺序存储一个队列时，该队列的最大长度为 (33) 。（分数：1.00）A.n-2B.n-1C.nD.n+124.当利用大小为 n的数组顺序存储一个栈时，假定用 top= =n表示栈空，则向这个栈插入一个元素时，首先应执行 (34) 语句修改 top指针。（分数：1.00）A.top+；B.top-；C.top=0；
11、D.top=0；二维数组 F的行下标为 2至 6，列下标为 1至 8，F 的每个数据元素均占 4个字节。在按列存贮的情况下，已知数据元素 F3，2的第一个字节是 2054，则 F3，4和 F4，3的第一个字节的地址分别为 (35) 和 (36) ，而数组的第一个数据元素的第一个字节和数组最后一个元素的最后一个字节的地址分别为 (37) 和 (38) 。对一般的二维数组 G而言，当 (39) 时，共按行存储的 GI，J的地址与按列存储的 GJ，I的地址相同。（分数：5.00）A.2056B.2094C.2092D.2120A.2092B.2088C.2078D.2124A.2004B.2044C
12、.2030D.1984A.2183B.2189C.2161D.2187A.C的列数与行数相同B.G的列的上界与 G的行的上界相同C.G的列的下界与 G的行的下界相同D.G的列的上下界与 G的行的上下界相同树是由结点构成的，其中根结点数目为 (40) 。二叉树有 (41) 个根结点，按一定的转换规则，任一树都可以转换成唯一对应的二叉树。二叉树的查找有深度优先和广度优先二类，深度优先包括 (42) 。当一棵二叉树的前序序列和中序序列分别是 HCZDBPCA和 ECBDHFAC时，其后序序列必是 (43) ，层次序列为 (44) 。（分数：5.00）A.只有 1个B.1或多于 1个C.0或 1个D.
13、至少 2个A.只有 1个B.1或多于 1个C.0或 1个D.至少 2个A.前序遍历后序遍历中序遍历B.前序遍历后序遍历层次遍历C.前序遍历中序遍历层次遍历D.中序遍历后序遍历层次遍历A.BDEAGFHCB.EBDGACFHC.HCFEDCBAD.HFGDEABCA.BDEACGFHB.EBDGACFHC.HCFEDCBAD.HFCCDEAB数值数据在机器中的表示法有原码、反码、补码(又称增码)等方法。定点数真值。表示法唯一的表示法是 (45) ；在 (46) 表示方式中最高位为“0”表示负号而为“1”表示正号；机器码为 n位时，采用反码、补码和移码来表示小数点固定在符号位与最高有效位之间的定点
14、数时所可表示的真值 X的范围分别为 (47) 、 (48) 和 (49) 。（分数：5.00）A.反码B.移码C.原码D.补码A.反码B.移码C.原码D.补码A.-(1-2-(n-1)X(1-2 -(n-1)B.-(1-2-(n-1)X1C.-1X(1-2 -(n-1)D.-1X1A.-(1-2-(n-1)X(1-2 -(n-1)B.-(1-2-(n-1)X1C.-1X(1-2 -(n-1)D.-1X1A.-(1-2-(n-1)X(1-2 -(n-1)B.-(1-2-(n-1)X1C.-1X(1-2 -(n-1)D.-1X1若一个二义树具有下列性质：除叶子结点外，每个结点的值都大于其左子树上的
15、一切结点的值，并小于等于其右子树上一切结点的值。这是一棵 (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) 增加一个结点。（分数：5.00）A.B-树B.最佳查找树C.穿线树D.查找树A.深度优先B.中序C.后序D.前序A.13B.8C.21D.57A.8B.21C
16、.34D.66A.n2与 n4之间B.n6下C.n5与 n9之间D.n9下堆是一种特殊的数据结构，选项 (55) 是一个最大堆。堆排序是一种 (56) 排序，其时间复杂性为 (57) 。 (58) 是不稳定的排序算法。外排序是指 (59) 。（分数：5.00）A.19，75，34，26，97，56B.97，75，34，56，19，26C.97，56，26，19，34，75D.19，34，26，97，56，75A.归并B.交换C.选择D.插入A.0(n)B.0(n2)C.D.0(nlogn)A.直接插入排序B.归并排序C.冒泡排序D.希尔(shell)排序A.用机器指令直接对硬盘中需排序数据排序
17、B.把需排序数据，用其他大容量机器排序C.把外存中需排序数据一次性调入内存，排好序后，再输回外存D.对外存中大于内存允许空间的需排序的数据，通过多次内外存问的交换实现排序。计算机中十六位浮点数的表示格式为图 1.4（分数：5.00）A.0.00000001012B.2010C.1.2510D.20.96937510A.0.00000001012B.2010C.1.2510D.20.96937510A.0.00000001012B.2010C.1.2510D.20.96937510A.0.00000001012B.2010C.1.2510D.20.96937510A.10100010100000
18、00B.10010101000000C.1101010100000000D.11110001010000全加器是由两个加数 Xi和 Yi以及低位来的进位 Ci-1作为输入，产生向高位的进位 Ci以及本位利 Si的逻辑电路。 (65) 和 (66) 分别是进位和本位和的正确逻辑表达式。全加器亦可通过半加器来实现，此时Si= (67) 。若某计算机采用 8位带符号补码表示整数，则可由 8个全加器(i =1，2，8，i=8 为最高位，即符号位)串接构成 8位加法器，CO=0。该加法器有一个状态寄存器，记录运算结果的状态。其中，N和 V分别表示符号位与溢出标志位，则其逻辑表达式分别为 (68) 和 (
19、69) 。（分数：5.00）A.XiYi+XiCi-1+YiCi-1B.XiYi+XiSj+YiSiC.XiYi+XiCi-1+YiCi-1D.(XiYi+XiYi)Ci-1A.XiYiCi-1+XiYiCi-1+XiYiCi-1+XIYiCi-1B.Ci-1(XiYi+XiYi)+Ci-1(XiYi+XiYi)C.Ci(XiYi+XiYi)+Ci(XiYi+XiYi)D.Ci(Xi+Yi+Ci-1)+XiYiCi-1(3). （分数：1.00）A.B.C.D.A.X8Y8+X8C7+Y8C7B.C7C.C8 X8D.C7(X8Y8+X8Y8)+C7(X8Y8+X8Y8)A.X8Y8+X8C7
20、+Y8C7B.C7C.C8 X8D.C7(X8Y8+X8Y8)+C7(X8Y8+X8Y8)任一棵树均可唯一地转换成与它对应的二叉树。由树转换成的二叉树中，结点 N的左子结点是 N在原树里对应结点的 (70) ，而 N的右子女是原树里对应结点的 (71) 。在下列二叉树中，图 1.4为 (72) 树，图 1.5为 (73) 树，图 1.6为 (74) 树。（分数：5.00）A.最左边的子结点B.最右边的子结C.最邻近的右兄弟D.最邻近的左兄弟A.最左边的兄弟B.最右边的兄弟C.最邻近的右兄弟D.最邻近的左兄弟A.查找树B.满二叉树C.平衡树但不是满二叉树D.B+树A.查找树B.满二叉树C.平衡树
21、但不是满二叉树D.B+树A.查找树B.满二叉树C.平衡树但不是满二叉捌D.B+树二维数组 A的行下标范围是 16，列下标范围是 28，每个数组元素占八个字节，则该数组的体积为 (75) 个字节，若已知 x的最后一个元素的起始字节地址为 428，则 A的首地址(即第一个元素的起始字节地址)为 (76) ，记为 As。若按行存储，则 A2，5的起始地址是 (77) ，结束字节地址是 (78) 。若按列存储，则 A4，8的起始字节地址为 (79) 。（分数：5.00）A.336B.340C.388D.394A.108B.100C.94D.86A.As+72B.As+80C.As+88D.As+96A
22、.As+79B.As+95C.As+87D.As+143A.As+186B.As+234C.As+270D.As+312下面是某种计算机的 32位短浮点数格式如图 1.7（分数：5.00）A.10000111100001000110000000000000B.00000111100001000101111111111111C.10000111111110000101111111111111D.00000111111110111010000000000000A.10000111100001000110000000000000B.00000111100001000101111111111111C.
23、10000111111110000101111111111111D.00000111111110111010000000000000A.10000111111110111010000000000000B.00000111100001000110000000000000C.10000111100001000110000000000000D.00000111100001000101111111111111A.10000111111110111010000000000000B.00000111100001000110000000000000C.1000011110000100011000000000
24、0000D.00000111100001000101111111111111A.10000111111110111010000000000000B.00000111100001000110000000000000C.00000111111110000101111111111111D.10000111100001000101111111111111后序遍历序列与中序遍历序列相同的二叉树为 (85) ，前序遍历序列与后序遍历序列相同的二叉树为 (86) 。（分数：2.00）A.根结点无左子树的二叉树B.根结点无右子树的二叉树C.只有根结点的二叉树或非叶子结点只有左子树的二叉树D.只有根结点的二叉树
25、或非叶子结点只有右子树的二叉树A.非叶子结点只有左子树的二叉树B.只有根结点的二叉树C.根结点无右子树的二叉树D.非叶子结点只有右子树的二叉树25.一棵二叉树的中序遍历序列为 DBGEUJOCIF，后序遍历序列为 DCJHEBIPCO，则其前序遍历序列为 (87) 。（分数：1.00）A.OBCDEFGHIJB.OBDEGHJCFIC.OBDEGHJPICD.OBDECJHCFI有一个线性表(16，25，70，61，52，45)，采用的散列函数为 H(Key)=Keymod8，将元素散列到表长为 8的哈希表中存储。若采用线性探测的开放定址法解决冲突，则在该散列表上进行等概率成功查找的平均查找长
26、度为 (88) ；若利用拉链法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为 (89) 。（分数：2.00）A.1.25B.1.33C.2.0D.2.3A.1.0B.7/6C.4/3D.3/226.有一颗二叉树有如下特点；不存在子树数目是 1个的结点。这样的一棵二叉树中有 m(m0)个子树为。的结点时，该二又树上的结点总数为 (91) 。（分数：1.00）A.2m+1B.2m-1C.2(m-1)D.2(m+1)27.等式x补+Y补=x+Y补在满足条件 (92) 时成立，其中 X、Y 是用 n个二进制位表示的带符号纯整数。（分数：1.00）A.-2n(X+Y)2 n-1B.-2n-1
27、(X+Y)2n-1C.-2n-1-1(X+Y)2n-1D.-2n-1(X+Y)2n海明码足一种可以纠正一位差错的编码。对于 30位的数据，需要 (93) 个校验位才能构成海明码。在某个海明码的排列方式阴 D8D7D6D5D4D3D2D1P2P3D0P2P1中，其中 Di(0i9)表示数据位，Pj(1j4)表示校验位，数据位 D6由 (94) 进行校验。（分数：2.00）A.3B.4C.5D.6A.P4P2P1B.P4P3P2C.P4P3P1D.P3P2P1F的逻辑表达式为 F=(A+B)X) (AB)Y)，当 (95) 时，F=A （分数：2.00）A.X=0，Y=0B.X=0，Y=1C.X=
28、1，Y=1D.X=1，Y=0A.X=0，Y=1B.X=0，Y=0C.X=1，Y=1D.X=1，Y=028.(XYZ+XYZ+XYZ+XYZ+XYZ+XYZ)=U (97) /U。（分数：1.00）A.YZB.Y+ZC.YZD.Y+Z已知 x，z 为带符号纯整数，y 为带符号纯小数，而且X原=Y补=Z移=11111101，求出 x、y、z 的十进制真值：X= (98) ，Y= (99) ，Z= (100) 。（分数：3.00）A.-127B.125C.-125D.1A.1/128B.-3/128C.-127/128D.125/128A.-1B.125C.-125D.12729.三对角矩阵是一类特
29、殊的矩阵，存储方式也比较特殊。现在将一个三对角矩阵 A1 100，1100中的元素按行存储在一维数组 B1.298中，矩阵 A中的元素 A66，67在数组 B中的下标为 (101) 。（分数：1.00）A.195B.196C.197D.19830.在等概率前提下，向一个采用顺序存储结构的 n个元素线性表插入一个元素需要移动的元素个数平均为 (102) 。（分数：1.00）A.n+1B.n/2C.(n+1)/2D.n31.下列数据结构中属于线性结构的是 (103) 。（分数：1.00）A.双端队列B.高维数组C.列表D.二叉树32.下列结论中正确的是 (104) 。（分数：1.00）A.二叉树的
30、度不为 2B.二叉树中任何一个结点的度都为 2C.二义树中至少有一个结点的度为 2D.树中结点的度可以小于 233.不问的存储结构适用于不同的应用场合。某线性表最常用的运算是插入和删除，删除运算是指删除表头第一个元素，插入运算是指在表尾插入一个新元素，那么采用 (105) 存储方式最好。（分数：1.00）A.仅有头指针的单向循环链表B.仅有尾指针的单向循环链表C.单向链表D.双向链表逆波兰式的特点是：表示时可以不用括号，而且可以用基于 (106) 的求值过程进行计算。与逆波兰式ab-cd+*对应的中缀表达式是 (107) 。（分数：2.00）A.栈B.队列C.符号表D.散列表A.a-b+c*d
31、B.(a-b)*c+dC.(a-b)*(c+d)D.a-b*c+d34.设数组 a520，316的元素以行为主序存放，每个元素占用两个存储单元，则数组元素 ai，j(5i20，3j16)的地址计算公式为 (108) 。（分数：1.00）A.a-146+28i+2jB.a-116+28i+2jC.a-144+28i+2iD.a-118+28i+2j35.若正规表达式 s=(xyz)(10)*，则 L(s)小有 (109) 过个元素。（分数：1.00）A.6B.12C.18D.无穷36.若单精度浮点数用 32位二进制数表示，其中最高位为符号位，后面跟 8位经偏移的阶码移码，偏移量为+127。尾数用
32、原码表示，且把尾数规格化为 1.xxx.x(x为 0或 1)，并将 1去掉，尾数用 23位表示。根据该标准，十进制数-178.125 的规格化表示形式为 (110) 。（分数：1.00）A.110000110 01100100010000000000000B.110000111 01100100010000000000000C.0 10000100 01100100010000000000000D.1 10000110 1110010001000000000000037.将十进制数 126化为二进制数是 (111) 。（分数：1.00）A.1111110B.1101111C.1111011D.
33、110111038.无符号数 X减去无符号数 Y，结果的进位标志为 0表明 (112) 。（分数：1.00）A.XYB.XYC.X=YD.XY39.下列关于链表的说法错误的是 (113) 。（分数：1.00）A.可随机访问任何一个元素B.插入、删除操作不需要移动元素C.无需事先估计存储空间大小D.所需存储空间与线性表长度成正比40.我们对矩阵压缩存储，是为了 (115) 。（分数：1.00）A.提高运算速度B.节省存储空间C.降低计算复杂度D.方便运算41.当 (116) 时，“链式队列为空”(front 为头指针，rear 为尾指针)。（分数：1.00）A.rear=NULLB.front=
34、 NULLC.front= =rearD.front!=rear42.字符串的特点是 (117) 。（分数：1.00）A.字符串是种特殊的线性表B.串的长度必须大于零C.字符申不属于线性表的一种D.空格字符组成的串就是空串43.在具有 200个结点的树中，其边的数目为 (118) 。（分数：1.00）A.201B.200C.199D.19844.在程序的执行过程中，实现嵌套调用函数正确返回可以用 (119) 结构。（分数：1.00）A.队列B.栈C.树D.图45.假设有一维数组 TO.m*n-1，其中 mn。从数组 T的第一个元素(T0)开始，每隔 n个元素取出一个元素依次存入数组 B1.m)
35、中，即 B1=T0，B2=Tn，依此类推，那么放入 Bk(1kn)的元素是 (120) 。（分数：1.00）A.T(K-1)*mB.TK*n)C.T(K-1)*nD.TK*m若码值 PPH是一个整数的补码表示，则该整数的真值为 (121) ：若码值 PPH是一个整数的原码表示，则该整数的真值为 (112) 。（分数：2.00）A.127B.0C.-117D.-1A.127B.0C.-127D.-146.原码乘法中，乘积的符号位是由被乘数的符号位和乘数的符号位通过 (123) 运算来获得的。（分数：1.00）A.异或B.与C.或D.分别取反后再进行或47.在串行同步方式传送数据块中，经常采用的差
36、错校验方法是 (124) 。（分数：1.00）A.偶校验B.奇校验C.海明码校验D.CRC校验程序员-计算机科学基础答案解析(总分：122.00，做题时间：90 分钟)一个非零的无符号二进制整数，将各位依次左移 3位，低位补零，则新的数是原来数的 (1) 倍；在此基础上，再右移 2位，高位补零，则此时的数是原数的 (2) 倍。补码表示中，最高位为符号位，一个以补码表示的正数，经 (3) 后，可扩大 4倍；一个以补码表示的负数，若经 (4) 后，可扩大 4倍，若经 (5) 后，可缩小 4倍。（分数：5.00）A.1000B.50C.8 D.4解析：A.1000B.4C.8D.2 解析：A.左移
37、2位，低位补 0 B.右移 2位，低位补 0C.左移 2位，低位补 1D.右移 2位，低位补 1解析：A.左移 2位，低位补 0 B.右移 2位，低位补 0C.左移 2位，低位补 1D.右移 2位，低位补 1解析：A.左移 2位，高位补 0B.右移 2位，高位补 0C.左移 2位，高位补 1 D.右移 2位，高位补 1解析：解析 无符号数每左移一位相当于乘以 2，新数是原来的 8倍。右移相当于除以 2；正数的补码表示和原码一样，所以，一个以补码表示的正数，经左移 2位，低位补 0后，可扩大 4倍；反码表示的负数，左移加倍时，低位需要补 0；右移缩小时，高位需要补 1。将十进制数-35 化成二进
38、制数原码、补码、反码表示(符号位和数值位共 8位)。二进制数原码为： (6) ，补码为 (7) ；反码为 (8) （分数：3.00）A.1 0100011 B.1 0100001C.1 0110011D.00100011解析：A.1 1010101B.1 101110l C.1 0011101D.0 1011101解析：A.1 1011101B.1 101110lC.1 1011100 D.0 1011100解析：解析 -35=-(32+2+1)，所以二进制原码为 1 0100011，变反加一后得到补码 1 1011101；将原码各位取反，得到反码 1 1011100。1.下面程序段的时间复杂
39、度是 (9) 。for(i=0，k=0；n；1+)k+=Aij；for(j=1；jm；j+)Aij=1（分数：1.00）A.O(n)B.O(m+n+1)C.O(m+n)D.O(m*n) 解析：解析 时间复杂度是解决问题的时间和问题的规模之间的关系，即解决问题所耗费的时间随问题规模增长成怎样的增长对应关系。本题中最内部的循环的执行次数为 m*n，所以整段程序的复杂度为O(m*n)。2.在单链表中，指针 P指向元素为 x的结点，语句 (10) 现“删除 x的后继”（分数：1.00）A.p=pmext；B.pnext=pnextnext； C.pnext=p；D.p=pnextnext；解析：解析
40、“删除 x的后继”只需使 x的指针指向后继的下一个结点。3.某单循环链表头指针为 head且表长大于 1，指针 p指向表中某个结点，若 pnextnext= head，则 (11) 。（分数：1.00）A.p指向头结点B.p指向尾结点C.*p的直接后继是头结点D.*P的直接后继是尾结点 解析：解析 因为 pnextnext=head，所以 pnext 是尾结点，即*P 的直接后继是尾结点。4.判定“带头结点的链队列为空”的条件是 (12) 。（分数：1.00）A.front= =NULLB.rear= =NULLC.front =Q.rear D.front!=Q.rear解析：解析 带头结点
41、的链队列的头指针和尾指针都不会为空，当它们都指向头结点时表示对列为空，即 Q. front= =Q.rear5.在一个单链表 HL中，若要向表头插入一个由指针 P指向的结点，则执行 (13) 。（分数：1.00）A.HL=p；pnext=HL；B.pnext=HL；HL=p；C.pnext=HL；p=HL； D.Pnext=HLnext；HLnext=p；解析：解析 单链表头结点为 HL，向表头插入一个由指针 P指向的结点时，可以先让 p指向 HL，然后再将 p赋给 HL即可。6.n个顶点的强连通图中至少含有 (14) 。（分数：1.00）A.n-1条的向边B.n条有向边 C.n(n-1)/2
42、条有向边D.n(n-1)条有向边解析：解析 n 个顶点的强连通图中边最少的情况是，从一个顶点开始顺序连接各点，最后回到该点，它们整体上恰好构成一个圆环。此时有 n条有向边。7.广义表 A=(a，(h)，()，(c，(d)，e)的深度为 (15) 。（分数：1.00）A.4 B.5C.6D.7解析：解析 广义表的深度定义为广义表中括弧的重数，是广义表的一种量度。本题中 d处的括弧深度最大，为 4。8.一棵含 28个结点的：二叉树的高度至少为 (16) 。（分数：1.00）A.3B.4C.5 D.6解析：解析 对于给定的结点数，当二叉树是满二叉树时，高度最少，为大于*(n 为结点数)的最小整数。本
43、题中，*，所以高度至少为 5。9.已知二叉树的中序序列为 DBEACPC，先序序列为 ABDECPC，则后序序列为 (17) 。（分数：1.00）A.DEBACFCB.DEFCBCAC.DEBCFCAD.DEBCFCA 解析：解析 二叉树的先序序列为 ABDECPG，所以根结点为 A，于是根据中序序列为 DDEAGPC可知，A 前面的 DBE元素是左于树的，右面的 FC是右子树上的，于是可以得到左右子树的中序序列和先序序列。按照此方法进行下去，最终得到树的结构。对树进行后序遍历可得 DEBGPCA。10.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为 (18) 。（分数：1.00）A.O
44、(1)B.O(n)C. D.O(n2)解析：解析 从一棵二叉搜索树中查找一个元素时，大约需要树的寓度次比较，即时间复杂度大致为*。在某关键字互不相同的二叉排序树中，命题：最小元必无左孩子，最大元必无右孩子。是 (19) 。最小元和最大元一定是 (20) 。（分数：2.00）A.不正确B.正确 C.命题错误D.无法确定解析：A.不是叶子节点B.叶子节点C.无法确定 D.以上都错解析：解析 在关键宇互不相同的二叉排序树中，若最小元有左孩子。则左孩子小于 1该结点，与它是最小元矛盾。同理可知，最大元必无右孩子。最大元和最小元不一定是叶子结点，最小元可以有右结点，最大元可以有左孩子。11.由权值分别为
45、 3，8，6，2，5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为 (21) 。（分数：1.00）A.24B.48C.72D.53 解析：解析 构造哈夫曼树后可得 5，6，8 的编码长度为 2，2 和 3的编码长度为 3，所以带权路径长度为(5+6+8) 2+(2+3)3=53。12.无向图中一个顶点的度是指图中 (22) 。（分数：1.00）A.通过该顶点的简单路径数B.与该顶点相邻接的顶点数 C.通过该顶点的回路数D.与该顶点连通的顶点数解析：解析 无向图中一个顶点的度是指与该顶点相连的边的数目，也就是与该顶点相邻接的顶点数。13.已知一个图如图 1.1所示，从顶点 b出发进行广度优先遍
46、历可能得到的序列为 (23) 。（分数：1.00）A.b a c e d fB.b a c d f eC.b a c e f d D.b a c e f d解析：解析 广度优先遍历可以定义为：首先访问出发点 v，接着依次访问 v的所有邻接点w1，w2，wt，然后再依次访问与 w1，w2，wt 邻接的所有未曾访问过的顶点。依此类推，直至图中所有和源点 v有路径相通的顶点都已访问到为止。此时从 v开始的搜索过程结束。14.当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为 (24) 参数，以节省参数值的传输时间和存储参数的空间。（分数：1.00）A.整形B.引用型 C.指
47、针型D.常值引用型解析：解析 把对象说明为引用型参数时，参数值的传输时间和存储参数的空间都比较小。15.向一个长度为 N的顺序表中插入个新元素的平均时间复杂度为 (25) 。（分数：1.00）A.O(N) B.O(1)C.O(logN)D.O(N2)解析：解析 向一个长度为 N的顺序表中插入一个新元素的平均比较次数为 N/2，所以平均时间复杂度为 O(N)。16.下面的排序方法中，平均时间性能为 O(nlogn)且空间性能最好的是 (26) 。（分数：1.00）A.基数排序B.堆排序 C.归并排序D.快速排序解析：解析 快速排序、堆排序、归并排序的平均时间性能均为 O(nlogn)，但是堆排序
48、的空间性能最好。17.已知一组关键字为 18，48，36，72，79，82，23，40，16，35，其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是 (27) 。（分数：1.00）A.18，36，48，72，23，40，79，82，16，35 B.18，36，48，72，16，23，40，79，82，35C.18，36，48，72，16，23，35，40，79，82D.16，23，18，35，36，40，48，72，79，82解析：解析 一趟两两归并是每两组进行一次归并排序，第一组为18，48，36，72，排序后得到18，36，48，72；第二组为79，82，23，40排序后得到23，40,79，82：第三组不变。所以最终结果为18，36，48，72，23，40，79，82，16，35。18.设顺序存储的线性表共有 287个元素，按分块查找的要求等分成 7块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为 (28) 。（分数：1.00）A.41B.25 C.45D.62解析：解析 287 个元素，按分块查找的要求等分成 7块，则每块有 41个元素。于是查找概率相等的情况下，查找确定块需要 4次比较，块中进行顺序查找需要 21次比较，所以查找成功时的平均查找
