1、软件水平考试（中级）软件设计师上午（基础知识）试题章节练习试卷 10 及答案与解析 1 循环链表的主要优点是 (1)。 （ A）不再需要头指针了 （ B）已知某个节点的位置后，能很容易找到它的直接前驱节点 （ C）在进行删除操作后，能保证链表不断开 （ D）从表中任一节点出发都能遍历整个链表 2 若循环队列以数组 QOm-1作为其存储结构，变量 rear表示循环队列中队尾元素的实际位置，其移动按 rear=(rear+1)mod m进行，变量 length表示当前循环队列中的元素个数，则循环队列的队首元素 的实际位置是 (2)。 （ A） rear-length （ B） (rear-leng
2、th+m) mod m （ C） (1+rear+m-length) mod m （ D） m-length 3 若广义表 L(1， 2， 3)，则 L的长度和深度分别为 (3)。 （ A） 1和 1 （ B） 1和 2 （ C） 1和 3 （ D） 2和 2 4 已知有一维数组 A(0m*n-1，若要对应为 m行、 n列的矩阵，则下面的对应关系 (4)可将元素 Ak(0k m*n)表示成矩阵的第 i行、第 j列的元素 (0i m， 0jn)。 （ A） i=k/n,j=k%m （ B） i=k/m,j=K%m （ C） i=k/n,j=k%n （ D） i=k/m,j=k%n 5 为便于存储
3、和处理一般树结构形式的信息，常采用孩子 -兄弟表示法将其转换成二叉树 (左子关系表示父子、右子关系表示兄弟 )，与图 8-2所示的树对应的二叉树是 (5)。 （ A） （ B） （ C） （ D） 6 在平衡二叉树中， (6)。 （ A）任意节点的左、右子树节点数目相同 （ B）任意节点的左、右子树高度相同 （ C）任意节点的左、右子树高度之差的绝对值不大于 1 （ D）不存在度为 1的节点 7 已知某二叉树的中序、层序序列分别为 DBAFCE， FDEBCA，则该二叉树的后序序列为 (7)。 （ A） BCDEAF （ B） ABDCEF （ C） DBACEF （ D） DABECF 8
4、在二叉树的顺序存储中，每个节点的存储位置与其父节点、左右子树节点的位置都存在一个简单的映射关系，因此可与三叉链表对应。若某二叉树共有 n个节点，采用三叉链表存储时，每个节点的数据域需要 d个字节，每个指针域占用 4个字节，若采用顺序存储，则最后一个节点下标为 k(起始下标为 1)，那么 (8)时采 用顺序存储更节省空间。 （ A） d 12n/(k-n) （ B） d 12n/(k-n) （ C） d 12n/(k+n) （ D） d 12n/(k+n) 9 由元素序列 27， 16， 75， 38， 51构造平衡二叉树，则首次出现的最小不平衡子树的根 (即离插入节点最近且平衡因子的绝对值为
5、2的节点 )为 (9)。 （ A） 27 （ B） 38 （ C） 51 （ D） 75 10 表达式 a*(b+c)-d的后缀表达形式为 (10)。 （ A） abcd*+- （ B） abc+*d- （ C） abc*+d- （ D） -+*abcd 11 若二叉树的先序遍历序列为 ABDECF，中序遍历序列为 DBEAFC，则其后序遍历序列为 (11)。 （ A） DEBAFC （ B） DEFBCA （ C） DEBCFA （ D） DEBFCA 12 在常用的描述二叉排序树的存储结构中，关键字值最大的节点 (12)。 （ A）左指针一定为空 （ B）右指针一定为空 （ C）左右指针均
6、为空 （ D）左右指针均不为空 13 由权值为 9， 2， 5， 7的四个叶子构造一棵哈夫曼树，该树的带权路径长度为(13)。 （ A） 23 （ B） 37 （ C） 44 （ D） 46 14 在一棵完全二叉树中，其根的序号为 1， (14)可判定序号为 p和 q的两个节点是否在同一层。 （ A） logp=log2q) （ B） log2p=log2q （ C） log2p+1=log2q) （ D） log2p=log2q)+1 15 若一棵哈夫曼 (Huffman)树共有 9个顶点，则其叶子节点的个数为 (15)。 （ A） 4 （ B） 5 （ C） 6 （ D） 7 16 在一棵
7、度为 3的树中，若有 2个度为 3的节点，有 1个度为 2的节点，则有 (16)个度为 0的节点。 （ A） 4 （ B） 5 （ C） 6 （ D） 7 17 设节点 x和 y是二叉树中任意的两个节点，在该二叉树的先根遍历序列中 x在y之前，而在其后根遍历序列中 x在 y之后，则 x和 y的关系是 (17)。 （ A） x是 y的左兄弟 （ B） x是 y的右兄弟 （ C） x是 y的祖先 （ D） x是 y的后裔 18 一个具有 767个节点的完全二叉树，其叶子节点个数为 (18)。 （ A） 383 （ B） 384 （ C） 385 （ D） 386 19 若一个具有 n个节点、 k条
8、边的非连通无向图是一个森林 (n k)，则该森林中必有 (19)棵树。 （ A） k （ B） n （ C） n-k （ D） n+k 20 某工程计划图如图 8-6所示，弧上的标记为作业编码及其需要的完成时间 (天 )，作业 E最迟应在第 (25)天开始。 （ A） 7 （ B） 9 （ C） 12 （ D） 13 21 拓扑序列是无环有向图中所有顶点的一个线性序列，图中任意路径中的各个顶点在该图的拓扑序列中保持先后关系， (26)为图 8-7所示有向图的一个拓扑序列。（ A） 1 2 3 4 5 6 7 （ B） 1 5 2 6 3 7 4 （ C） 5 1 2 6 3 4 7 （ D）
9、5 1 2 3 7 6 4 22 无向图中一个顶点的度是指图中 (32)。 （ A）通过该顶点的简单路径数 （ B）通过该顶点的回路数 （ C）与该顶点相邻接的顶点数 （ D）与该顶点连通的顶点数 23 一个具有 n(n 0)个顶点的连通无向图至少有 (33)条边。 （ A） n+1 （ B） n （ C） n/2 （ D） n-1 24 一个含有 n个顶点和 e条边的简单无向图，在其邻接矩阵存储结构中共有 (36)个零元素。 （ A） e （ B） 2e （ C） n2-e （ D） n2-2e 25 若采用邻接矩阵来存 储简单有向图，则其某一个顶点 i的入度等于该矩阵 (37)。 （ A）
10、第 i行中值为 1的元素个数 （ B）所有值为 1的元素总数 （ C）第 i行及第 i列中值为 1的元素总个数 （ D）第 i列中值为 1的元素个数 26 关键路径是指 AOE(Activity On Edge)网中 (38)。 （ A）最长的回路 （ B）最短的回路 （ C）从源点到汇点 (结束顶点 )的最长路径 （ D）从源点到汇点 (结束顶点 )的最短路径 27 若 G是一个具有 36条边的非连通无向图 (不含自回路和多重边 )，则图 G至少有(39)个顶点。 （ A） 11 （ B） 10 （ C） 9 （ D） 8 28 给定一个有 n个元素的有序线性表。若采用顺序存储结构，则在等概
11、率前提下，删除其中的一个元素平均需要移动 (47)个元素。 （ A） (n+1)/2 （ B） n/2 （ C） (n-1)/2 （ D） 1 29 在 (48)存储结构中，数据结构中元素的存储地址与其关键字之间存在某种映射关系。 （ A）顺序 (Sequence) （ B）链表 (Link) （ C）索引 (1ndex) （ D）散列 (Hash) 30 在 11个元素的有序表 A111) 中进行折半查 找 L(low+high)/2，查找元素 A11时，被比较的元素的下标依次是 (49)。 （ A） 6， 8， 10， 11 （ B） 6， 9， 10， 11 （ C） 6， 7， 9，
12、11 （ D） 6， 8， 9， 11 31 已知一个线性表 (38， 25， 74， 63， 52， 48)，假定采用散列函数 h(key)=key%7计算散列地址，并散列存储在散列表 A06 中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为 (50)。 （ A） 1.5 （ B） 1.7 （ C） 2 （ D） 2.3 32 (51)的特点是数据结构中元素的存储地址与其关键字之间存在某种映射关系。 （ A）树形存储结构 （ B）链式存储结构 （ C）索引存储结构 （ D）散列存储结构 33 设顺序存储的某线性表共有 123个元素，按分块查找的要求等分为 3块
13、。若对索引表采用顺序查找方法来确定子块，且在确 (52)。 （ A） 21 （ B） 23 （ C） 41 （ D） 62 34 (55)在其最好情况下的算法时间复杂度为 O(n)。 （ A）插入排序 （ B）归并排序 （ C）快速排序 （ D）堆排序 35 若排序前后关键字相同的 两个元素相对位置不变，则称该排序方法是稳定的。(56)排序是稳定的。 （ A）归并 （ B）快速 （ C）希尔 （ D）堆 36 利用逐点插入建立序列 (50， 72， 43， 85， 75， 20， 35， 45， 65， 30)对应的二叉排序树以后，查找元素 30要进行 (57)次元素间的比较。 （ A） 4
14、（ B） 5 （ C） 6 （ D） 7 37 在最好和最坏情况下的时间复杂度均为 O(nlogn)且稳定的排序方法是 (58)。 （ A）基数排序 （ B）快速排序 （ C）堆排序 （ D）归并排序 38 以比较为基础 的排序算法在最坏情况下的计算时间下界为 (59)。 （ A） O(n) （ B） O(n2) （ C） O(logn) （ D） O(nlogn) 39 堆是一种数据结构， (60)是堆。 （ A） (10， 50， 80， 30， 60， 20， 15， 18) （ B） (10， 18， 15， 20， 50， 80， 30， 60) （ C） (10， 15， 18，
15、50， 80， 30， 60， 20) （ D） (10， 30， 60， 20， 15， 18， 50， 80) 40 (61)从二叉树的任一节点出发到根的路径上，所经过的节点序列必按其关键字降序排列 。 （ A）二叉排序树 （ B）大顶堆 （ C）小顶堆 （ D）平衡二叉树 41 若对 27个元素只进行三趟多路归并排序，则选取的归并路数为 (62)。 （ A） 2 （ B） 3 （ C） 4 （ D） 5 42 以下序列中不符合堆定义的是 (63)。 （ A） (102， 87， 100， 79， 82， 62， 84， 42， 22， 12， 68) （ B） (102， 100， 87
16、， 84， 82， 79， 68， 62， 42， 22， 12) （ C） (12， 22， 42， 62， 68， 79， 82， 84， 87， 100， 102) （ D） (102， 87， 42， 79， 82， 62， 68， 100， 84， 12， 22) 43 将两个长度为 n的递增有序表归并成一个长度为 2n的递增有序表，最少需要进行关键字比较 (64)次。 （ A） 1 （ B） n-1 （ C） n （ D） 2/9 44 对 n个元素进行快速排序时，最坏情况下的时间复杂度为 (65)。 （ A） O(log2n) （ B） O(n) （ C） O(nlog2/t)
17、（ D） O(n2) 45 任何一个基于 “比较 ”的内部排序的算法，若对 6个元素进行排序，则在最坏情况下所需的比较次数至少为 (66)。 （ A） 10 （ B） 11 （ C） 21 （ D） 36 46 假定每一车次具有惟一的始发站和终点站。如果实体 “列车时刻表 ”属性为车次、始发站、发车时间、终点站、到达时间，该实体的主键是 (6)；如果实体 “列车运行表 ”属性为车次、日期、发车时间、到达时间，该实体的主键是 (7)。在通常情况下，上述 “列车时刻表 ”和 “列车运行表 ”两实体型间 (8)联系。 （ A）车次 （ B）始发站 （ C）发车时间 （ D）车次，始发站 （ A）车次
18、 （ B）始发站 （ C）发车时间 （ D）车次，日期 （ A）不存在 （ B）存 在一对一 （ C）存在一对多 （ D）存在多对多 49 设学生 S、课程 C、学生选课 SC的关系模式分别为： S(Sno， Sname， Sage，Saddr)、 C (Cno， Cname， Pcno)以及 SC(Sno， Cno， Grade)，与关系代数表达式Sno， Sname， Grade (Snam=数据库 ， (S|SC|C)等价的元组演算表达式为： _(15)_S(u) SC(v) C(w) _(16)_ _(17)_ （ A） ( u)(3v)(3w) （ B） (3u)( v)(3w) （
19、 C） (3u)(3v)(3w) （ D） (3u)(31/)( w) （ A） u1=v1 v1=w1 w1=数据库 （ B） u1=v2 v2=w1 w3=数据库 （ C） u1=v1 v2=w1 w2=数据库 （ D） u2=v2 v1=w2 w2=数据库 （ A） t1=u1 t2=u2 t3=v3 （ B） t1=u1 t2=u2 t3=v2 （ C） t1=u1 t2=w1 t3=v2 （ D） t1=u1 t2=w2 t3=v3 52 某数据库中有员工关系 E、产品关系 P、仓库关系 W和库存关系 I，其中，员工关系 E (employeeID， name， department
20、)中的属性为：员工编号，姓名，部门；产品关系 P(productID， name， model， size， color)中的属性为：产品编号，产品名称，型号，尺寸，颜色；仓库关系 W (warehouseID， name， address，employeeID)中的属 性为：仓库编号，仓库名称，地址，负责人编号：库存关系I(warehouseID， productID， quantity)中的属性为：仓库编号，产品编号和产品数量。 52 a a若要求仓库关系的负责人引用员工关系的员工编号，员工关系 E的员工编号、仓库关系 W的仓库编号和产品关系 P的产品编号不能为空且惟一标识一个记录，并且仓
21、库的地址不能为空，则依次要满足的完整性约束是 (26)。 （ A）实体完整性、参照完整性、用户定义完整性 （ B）参照完整性、实体完整性、用户定义完整性 （ C）用户定义完整性、实体完整性、 参照完整性 （ D）实体完整性、用户定义完整性、参照完整性 53 b b若需得到每种产品的名称和该产品的总库存量，则对应的查询语句为： SELECT name, SUM (quantity) FROMP, I WHERE(27) （ A） P. productID=I.productID； （ B） P.productID=I.productID ORDER BY name； （ C） P.product
22、ID=I.productID GROUP BY name； （ D） P.productID=I.productID GROUP BY name, quantity； 54 c c若需得到在所有仓库中都存在的产品的名称，则对应的查询语句为： SELECT name FROM P WHERE(28)(SELECT*FROM W WHERE NOT EXISTS(SELECT*FROM I WHERE P.productID=I.productID AND W.warehouseID=I.warehouseID)(28) （ A） EXISTS （ B） NOTEXISTS （ C） IN （ D
23、） NOTm 55 在关系代数运算中，关系 S， SP和 R如表 7-11表 7-13所示。若先 (29)，则可以从 S和 SP获得 R。其对应的关系表达式为 (30)。如下的 SQL语句可以查询销售总量大于 1000的部门号。 Select部门名 From SWhere部门号 in(Select部门号From SP Group by (31)关系表 S关系表 SP关系表R （ A）对 S进行选择运算，再与 S进行自然连接运算 （ B）对 S进行选择运算，再与 SP进行自然连接运算，最后进行投影运算 （ C）对 S和 SP进行笛卡儿积运算，再对运算结果进行投影运算 （ D）分别对 S和 SP进
24、行投影运算，再对运算结果进行笛卡儿积运算 （ A） （ B） （ C） （ D） （ A）部门号 where sum(销售量 ) 1000 （ B）部门号 having sum(销售量 ) 1000 （ C）商品号 where sum(销售量 ) 1000 （ D）商品号 having sum(销售量 ) 1000 58 设供应商供应零件的关系模式为 SP(Sno， Pno， Qty)，其中 Sno表示供应商号， Pno表示零件号， Qty表示零件数量 。查询至少包含了供应商 “168”所供应的全部零件的供应商号的 SQL语句如下： SELECT Sno FROMSP SPX WHERE (3
25、7) (SELECT* FROM SP SPY WHERE (38) ANDNOTEXISTS (SELECT* FROM SP SPZ WHERE (39)； （ A） EXISTS （ B） NOTEXISTS （ C） IN （ D） NOT IN （ A） SPY.Sno=168 （ B） SPY.Sno 168 （ C） SPY.Sno=SPX.Sno （ D） SPY.Sno SPX.Sno （ A） SPZ.Sno=SPY.Sno AND SPZ.Pno=SPY.Pno （ B） SPZ.Sno=SPX.Sno AND SPZ.Pno=SPX.Pno （ C） SPZ.Sno=S
26、PX.Sno AND SPZ.Pno=SPY.Pno （ D） SPY.Sno 168 AND SPZ.Pno=SPY.Pno 软件水平考试（中级）软件设计师 上午（基础知识）试题章节练习试卷 10 答案与解析 1 【正确答案】 D 【试题解析】 链表或设头指针或设尾指针，因此选项 A被排除。选项 B 指的是双向循环链表。由于链表都要保证删除操作后，仍为链表，因此选项 C也被排除。 2 【正确答案】 C 【试题解析】 按照循环队列的定义，因为元素移动按照 rear=(rear+1)mod m进行，则当数组 Qm-1存放了元素之后，下一个入队的元素将存放到 Q0中，因此队列的首元素的实际位置是
27、(regr+1-1ength+m)mod m。 3 【正确答 案】 B 【试题解析】 广义表的长度定义为表中元素的个数，而深度定义为广义表展开后括号的最大嵌套层数。 4 【正确答案】 C 【试题解析】 此题是求一维数组向二维数组转化的问题。最原始的方法就是把数组 A的前 n个元素放到数组 B 的第一行，数组 A的第 n个元素放到数组 B 的第二行中，依次类推，数组 A的最后 n 个元素放到数组 B的最后一行中。求且 幻在数组 B 中的位置，应先确定 Ak处在哪一行，显然应该是 k/n行，然后再确定处在k/n 行的哪一列，显然是 k%n列。 5 【正确答案】 A 【试题解析】 树的孩子兄弟表示法
28、又称二叉链表表示法。在链表的节点中设置两个指针域，分别指向该节点的第一个孩子和下一个兄弟，利用这种存储结构便于实现树的各种操作。 6 【正确答案】 C 【试题解析】 平衡二叉树又称 AVL 树。它或者是一棵空树，或者是具有下列性质的二叉树。 左子树和右子树都是平衡二叉树； 左子树和右子树的深度之差的绝对值不超过 1； 二叉树上节点的平衡因子定义为该节点的左子树的深度减去它的右子树的深度。由此可见，平衡二叉树上所有节点的平衡因子只可能是 -1，0， 1。只要二叉树上有一个节点的平衡因子的绝对值大于 1，则该二叉树就是不平衡的。 7 【正确答案】 B 【试题解析】 按照遍历左子树要在遍历右子树之前
29、进行的原则，根据访问根节点位置的不同，可得到二叉树的前序、中序和后 序 3种遍历方法。层序遍历是从根节点 (第 1层 )出发，首先访问第 1层的树根节点，然后从左到右依次访问第 2层上的节点，再次是第三层上的节点，依次类推，自上而下、自左向右逐层访问各层上的节点。对二叉树而言，第 n 层节点最多为 2n-1。由层序序列可得； F是树根节点， D， E 是第 2层节点；结合中序序列有 DBA构成 F的左子树， CE 构成 F的右子树，进一步有 C是 E 的左节点， E无右节点；这样 A是第 4层节点，据 DBA序列有 B 是 D的右节点， A是 B的右节点。由此易知后序序列为 ABDCEF。 8
30、 【正确答案】 A 【试题解析】 顺序 存储所需空间为 kd，三叉链存储所需空间为 n(d+43)，当 kd n(d+12)，即 时，顺序存储更节省空间。对完全二叉树， k 等于 n，显然不论 d值大小，顺序存储更省空间。 9 【正确答案】 D 【试题解析】 二叉排序树的构造方法如下：每读入一个数据，建立一个新节点，若二叉排序树非空，则将新节点的值与根节点的值比较，。如果小于根节点的值，则插入到左子树中，否则插入到右子树中；若二叉排序树为空，则新节点作为二叉排序树的根节点。节点的平衡因子是指节点右子树深度与左子树深度之差。由数据 27， 16， 75， 38， 51构造平衡二叉树，插入 51后
31、首次出现不平衡子树，易知最小不平衡子树的节点为 75。 10 【正确答案】 B 【试题解析】 一个表达式可用一棵二叉树表示，其中的叶子节点表示操作数，内部节点表示操作符或中间结果，根节点表示整个表达式的值，对此二叉树分别进行前序、中序和后序遍历，恰好为表达式的前缀表示、中缀表示和后缀表示 (逆波兰式 )。其中表达式的前缀和后缀表示均可以将表达式中的括号省去而不影响次序和结果。 11 【正确答案】 D 【试题解析】 由先序遍历序列和中序遍历序列可惟一确定一棵二叉 树。同时，中序序列和后序序列也惟一确定一棵二叉树。本题的二叉树形状如图 8-3所示。12 【正确答案】 B 【试题解析】 在二叉排序树
32、的存储结构中，每节点山三部分构成，其中左 (或右 )指针指向比节点的关键值小 (或大 )的节点。关键字值最大的节点位于二叉排序树的最右位置上，因此它的右指针一定为空。 13 【正确答案】 C 【试题解析】 哈夫曼树的形状如图 8-4所示。 该树的带权路径长度 =91+72+23+53=44 14 【正确答案】 A 【试题解析】 由完全二叉树的性质可知，在一 棵完全二叉树第 h(h1)层上的节点p 和 q，它们的序号范围应是 2h-1p， q2h-1，因此 logp=log2q)成立。 15 【正确答案】 B 【试题解析】 哈夫曼首先给出了对于给定的叶子数目及其权值构造最优二叉树的方法，根据这种
33、方法构造出来的二叉树称为哈夫曼树。假设有 n个权值，则构造出的哈夫曼树有 n个叶子节点。 N个权值分别设为 w1， w2， ， wn，则哈夫曼树的构造规则如下。第一步：将 w1， w2， ， wn看成是有 n 棵树的森林；第二步：在森林中选出两个根节点的权值最小的树合并，作为一棵新 树的左、右子树，且新树的根节点权值为其左右子树根节点权值之和；第三步：从森林中删除选取的两棵树，并将新树加入森林：第四步：重复第二步和第三步，直到森林中只剩一棵树为止，该树即为所求的哈夫曼树。从以上构造过程可知，哈夫曼树是严格的二叉树，没有度数为 1的分支节点。 n个叶子的哈夫曼树要经过 n-1次合并，产生 n-1
34、个新节点，最后求得的哈夫曼树中共有 2n-1个节点。 16 【正确答案】 C 【试题解析】 节点的度是指一个节点子树的个数。度为 3就是这个节点有 3个子树节点，而度为 2是这个节点有 2个子树节点。因此 度为 0的节点有 6个。 17 【正确答案】 C 【试题解析】 先序遍历的递归算法定义为若二叉树非空，则依次执行如下操作：访问根节点，遍历左子树，遍历右子树。后序遍历的递归算法定义为若二叉树非空，则依次执行如下操作：遍历左子树，遍历右子树，访问根节点。 18 【正确答案】 B 【试题解析】 设二叉树中总节点数，以及度为 0、度为 1和度为 2的节点数分别为 n， n0， n1和 n2，依据二
35、叉树的性质可得到下列等式： n=n0+n1+n2 n=768 n-1=n1+2n2 通过化简可得 到 769=2n0+n1 在完全二叉树中，度为 1的节点要么没有，要么有 1个。上面等式左边为一个奇数，等式右边 2n0 是一个偶数，要使等式成立， n1只能为奇数，即是 1，所以叶子节点个数 n0=384。 19 【正确答案】 C 【试题解析】 设该森林共有 m棵树，每棵树有 ni(1im)个节点，依据树的性质有 n=n1+n2+nm k=(n1-1)+(n2-1)+(nm -1) 上面两式相减得 n-k=1+1+1=m 而 m就是树的个数，所以该森林共有 n-k棵树。 20 【正确答案】 D
36、【试题解析】 3+5+5=13 21 【正确答案】 B 【试题解析】 拓扑排序是将 AOV网中所有顶点排成一个线性序列，该序列满足：若在 AOV网中从顶点 vi到 vj有一条路径，则在该线性序列中，顶点 vi必然在顶点 vj之前。拓扑排序即指对 AOV网构造拓扑序列的操作。对 AOV网进行拓扑排序的方法如下。 (1)在 AOV网中选择一个入度为零的顶点且输出它； (2)从网中删除该顶点及与该顶点有关的所有边； (3)重复上述两步，直至网中不存在入度为零的顶点为止。若在 AOV网中 考查各项点的出度，并按下列步骤进行排序，则称为逆拓扑排序。 (1)在 AOV网中选择一个没有后继的顶点且输出它；
37、(2)从网中删除该顶点，并删去所有到达该顶点的弧； (3)重复上述两步，直至网中不存在出度为零的顶点为止。 22 【正确答案】 C 【试题解析】 图中顶点的度定义为与该顶点相关联的边的数目。在无向图中就是与该顶点相邻接的顶点数，而与该顶点连通的顶点数可能就非常多厂。 23 【正确答案】 D 【试题解析】 在无向图中，如果从一个顶点到另一个顶点有路径，则称这两个顶点是连通的。如果图中任 意两个顶点都是连通的，则称该无向图是连通的。因此具有 n个顶点的连通无向图至少有 n-1条边。 24 【正确答案】 D 【试题解析】 邻接矩阵反映顶点间邻接关系。设 G=(V， E)是具有 n 个顶点的图， G的
38、邻接矩阵 M是一个 n 行 n列的矩阵，并有若 (i， j)或 i， j E，则Mij=1。否则 Mij=0。由邻接矩阵的定义可知，无向图的邻接矩阵是对称的，即图中的一条边对应邻接矩阵的两个非零元素。因此在一个含有 n 个顶点和 e条边的简单无向图的邻接矩阵中共有 n2-2e个零元素。 25 【正确答案】 D 【试题解析】 由邻接矩阵的定义可知，对于无向图，其邻接矩阵第 i行元素的和即为顶点 i的度。对于有向图，其邻接矩阵的第 i行元素的和为顶点 i的出度，而邻接矩阵的第 j列元素的和为顶点 j的入度。 26 【正确答案】 C 【试题解析】 在 AOE 网中，用顶点表示活动，用有向边 vi，
39、vi表示活动 vi必须先于活动 vi 进行。如果在有向环的带权有向图中用有向边表示一个工程中的各项活动，用有向边上的权值表示活动的持续时间，用顶点表示事件，则这种有向图叫做用边表示活动的网络，简称 AOE 网络。关键路径是指在 AOE 网络中从源点到汇点的最长路径。拓扑排序、最短路径和计算关键路径都是有向图的重要运算。根据关键路径的定义，正确答案为 C。 27 【正确答案】 B 【试题解析】 根据无向图的定义，有 n个顶点的无向图至多有 n(n-1)/2条边。本题中的图 G共有 36条边，则 n(n-1)/2=36，解这个方程可得 n=9。但这样求得的 9个顶点是连通的，而试题要求是非连通图，
40、因此至少有 10个顶点。 28 【正确答案】 C 【试题解析】 基于顺序存储结构的运算，插入元素前要移动元素以挪出空的存储单元，然后再插入元素；删除元 素时同样需要移动元素，以填充删除而空出来的存储单元。在等概率下平均移动元素的次数分别是：29 【正确答案】 D 【试题解析】 Hash，一般翻译做 “散列 ”，也有直接音译为 “哈希 ”的，就是把任意长度的输入 (又叫做预映射， pre-image)，通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来惟一地确定输入值。 30
41、【正确答案】 B 【试题解析】 折半查找方法：对表 r1n ，首先将待查的 key 值与表 r中间位置(位置 mid)的记录的 key进行比较，若相等，则查找成功：若 key rmid). key，则说明待查记录只可能在后半个子表 rmid+1n( 注意：是 mid+1，而不是mid)，若 key rmid.key，则说明待查记录只可能在后半个子表 r1mid -1(注意：是 mid-1，而不是 mid)。31 【正确答案】 C 【试题解析】 按照散列函数 h(key)： key%7和线性探测方法解决冲突，将线性表(38,25,74,63,52,48)散列存储在 散列表 A06 中，如图 8-
42、10所示。32 【正确答案】 D 【试题解析】 很显然这是散列存储结构。散列存储结构将节点按其关键字的散列地址存储到散列表中。常用的散列函数有除余法、基数转换法、平方取中法、折叠法、移位法和随机数法等。 33 【正确答案】 B 【试题解析】 分块查找成功的平均查找长度为： 在本题中，n=123， s=123/3=41，故平均查找长度为 23。 34 【正确答案】 A 【试题解析】 各种常用排序方法在最好情况下的时间复杂度如表 8-2所示。35 【正确 答案】 A 【试题解析】 排序是将无序的记录序列调整为有序记录序列的一种操作。直接插入排序：插入排序的准则是，在有序序列中插入新的记录以达到扩大
43、有序区的长度的目的。起泡排序：起泡排序是交换类排序方法中的一种简单排序方法。其基本思想为依次比较相邻两个记录的关键字，若和所期望的相反，则互换这两个记录。希尔排序：希尔排序又称 “缩小增量排序 ”，它的基本思想是，先对待排序列进行 “宏观调整 ”，待序列中的记录 “基本有序 ”时再进行直接插入排序。快速排序：起泡排序是通过一趟 “起泡 ”选定关键字最大的记录，所有剩余关键字均 小于它的记录继续进行排序。快速排序则是通过一趟排序选定一个关键字介于 “中间 ”的记录，从而使剩余记录可以分成两个子序列分别继续排序，通常称该记录为 “轴枢 ”。堆排序：利用堆的特性进行的排序方法即为 “堆排序 ”。 “
44、堆排序 ”是一种选择类的排序方法。归并排序：归并排序的基本操作是将两个或两个以上的记录有序序列归并为一个有序序列。最简单的情况是，只含一个记录的序列显然是个有序序列，经过 “逐趟归并 ”使整个序列中的有序子序列的长度逐趟增大，直至整个记录序列为有序序列为止。 2-路归并排序则是归并排序中的一种最简单的情况，它的基 本操作是将两个相邻的有序子序列 “归并 ”为一个有序序列。基数排序：利用多关键字排序的思想。快速排序、堆排序或归并排序平均时间复杂度较低，为O(nlogn)。直接插入排序、起泡排序、归并排序和基数排序是稳定的。 36 【正确答案】 B 【试题解析】 利用逐点插入法建立二叉树是从空树开
45、始，通过查找将每个节点作为一个叶子插入。按上述次序建立的二叉排序树如图 8-11所示。37 【正确答案】 D 【试题解析】 基数排序在最好和最坏情况下的时间复杂度均为 Od(n+rd)，快速排序在最好和最坏情况下的时间 复杂度分别为 O(nlogn)和 O(n2)且不稳定，堆排序在最好和最坏情况下的时间复杂度均为 O(nlogn)但不稳定，归并排序在最好和最坏情况下的时间复杂度均为 O(nlogn)且稳定。 38 【正确答案】 D 【试题解析】 利用二叉树可以证明对任何以关键字比较为基础的排序算法的最坏情况下的时间复杂度都为 O(nlogn)，如归并排序等。 39 【正确答案】 B 【试题解析
46、】 堆的定义：对于 n个元素的关键字序列 K1， K2， ， Kn，当且仅当满足下列关系时，称之为堆。 可将此序列看做一棵完全二叉树， 则堆的定义表明，完全二叉树中所有非终端节点的值均不大于 (或小于 )其左右孩子节点的值。据此可判定上述各序列是否符合堆的定义。 40 【正确答案】 C 【试题解析】 当堆为小顶堆时，任意一棵子树的根点比其左右子节点要小，所以从任意节点出发到根的路径上，所经过的节点序列必按其关键字降序排列。 41 【正确答案】 B 【试题解析】 归并就是将两个或两个以上的有序表组合成一个新的有序表。设三趟归并中每次归并 x个有序表，则第一趟归并后剩余 27/x个表，第二趟归并后
47、剩余 27/(x2)个表，归并三次后剩余 27/(x3)。令 27/(x3)=1，则 x=3。故选取的归并路数为 3。 42 【正确答案】 D 【试题解析】 根据堆的定义， n个关键字序列 k1， k2， ， Kn。称为堆的条件是，当且仅当该序列满足 kik2i且 kik2i+1或 kik2i且 kik2i+1， (1in/2)。当i=1， 2时， 4个选项都满足条件 (其中 A， B， D为大根堆， C为小根堆 )。但当i=3时， D不满足条件。 43 【正确答案】 C 【试题解析】 显然当一个表的所有字符都小于另一个表的所有字符的时候，比较的次数最少。 这时，只需把其中一个表的每个字符与另一个表中的每一个字符比较一次，即共需比较 n次。 44 【正确答案】 D 【试题解析】 比较常用的排序算法的平均时间复杂度，以及最坏情况下的时间复杂度，可以知道快速排序最坏情况下的时间复杂度为 O(n2)。
