A.39 B.52 C.111 D.119 解析 C 根据完全二叉树的定义, 此树的前 6 层应该是满二叉树, 共有 = 63 个结点第 6 层有 8 个叶子结点, 说明另外 32-8=24 个结点不是叶子结点, 最多各有 2 个孩子结点而该树不可能有第 8 层存在, 所以结点总数最

Size: px

Start display at page:

Download "A.39 B.52 C.111 D.119 解析 C 根据完全二叉树的定义, 此树的前 6 层应该是满二叉树, 共有 = 63 个结点第 6 层有 8 个叶子结点, 说明另外 32-8=24 个结点不是叶子结点, 最多各有 2 个孩子结点而该树不可能有第 8 层存在, 所以结点总数最"

坂底沈
7 years ago
Views:

1 09 年真题 1 为解决计算机与打印机之间速度不匹配的问题, 通常设置一个打印数据缓冲区, 主机将要输出的数据依次写入该缓冲区, 而打印机则依次从该缓冲区中取出数据该缓冲区的逻辑结构应该是 ( ) A. 栈 B. 队列 C. 树 D. 图解析 B 打印机取出数据的顺序与数据被写入缓冲区的顺序相同, 为先进先出结构, 即队列 2 设栈 S 和队列 Q 的初始状态均为空, 元素 a,b,c,d,e,f,g 依次进入栈 S 若每个元素出栈后立即进入队列 Q, 且 7 个元素出队的顺序是 b,d,c,f,e,a,g, 则栈 S 的容量至少是 ( ) A.1 B.2 C.3 D.4 解析 C 当 a,c,d 同时在 S 中及 a,e,f 同时在 S 中时, 栈的存储量达到最大值, 因此容量至少为 3 3 给定二叉树图所示设 N 代表二叉树的根,L 代表根结点的左子树,R 代表根结点的右子树若遍历后的结点序列为 3,1,7,5,6,2,4, 则其遍历方式是 ( ) A.LRN B.NRL C.RLN D.RNL 解析 D 根据遍历结果, 很容易看出右子树先被访问, 相当于左右颠倒的中序遍历 4 下列二叉排序树中, 满足平衡二叉树定义的是 ( ) 解析 B 根据平衡二叉树的定义, 任意结点左右子树的高度差的绝对值不超过 1 选项 A,C,D 的根结点左右子树差都不满足定义 5 已知一棵完全二叉树的第 6 层 ( 设根为第 1 层 ) 有 8 个叶结点, 则该完全二叉树的结点个数最多是 ( )

2 A.39 B.52 C.111 D.119 解析 C 根据完全二叉树的定义, 此树的前 6 层应该是满二叉树, 共有 = 63 个结点第 6 层有 8 个叶子结点, 说明另外 32-8=24 个结点不是叶子结点, 最多各有 2 个孩子结点而该树不可能有第 8 层存在, 所以结点总数最多时 =111 个结点 6 将森林转换为对应的二叉树, 若在二叉树中, 结点 u 是结点 v 的父结点的父结点, 则在原来的森林中,u 和 v 可能具有的关系是 ( ) I. 父子关系 II. 兄弟关系 III.u 的父结点与 v 的父结点是兄弟关系 A. 只有 II B.I 和 II C.I 和 III D.I II 和 III 解析 B 若 u 和 v 的关系如图 a 所示, 则根据左孩子右兄弟原则,v 跟自己的父结点是兄弟关系, 都是 u 的孩子所以图 a 对应的是 I: 父子关系若 u 和 v 的关系如图 b 所示, 则根据左孩子右兄弟原则,v 跟自己的父结点以及 u 是兄弟关系, 都是 u 的父结点的孩子所以图 b 对应的是 II 兄弟关系若在森林中 ( 注意不是在二叉树中 )u 的父结点与 v 的父结点是兄弟关系则转换成二叉树后, 它们形成单边右斜的关系, 而 u 和 v 分别在他们各自的左子树内, 不可能在同一条路径上, 所以 III 是不可能的 7 下列关于无向连通图特性的叙述中, 正确的是 ( ) I. 所有顶点的度之和为偶数 II. 边数大于顶点个数减 1 III. 至少有一个顶点的度为 1 A. 只有 I B. 只有 II C.I 和 II D.I 和 III 解析 A 三个命题中,II 显然不对, 当图是一棵树的时候, 正好有边数等于顶点个数减 1 III 也不对, 例如一个连接所有顶点的环, 边数等于顶点个数, 每个顶点的度都是 2 8 下列叙述中, 不符合 m 阶 B 树定义要求的是 ( ) A. 根节点最多有 m 棵子树 B. 所有叶结点都在同一层上 C. 各结点内关键字均升序或降序排列 D. 叶结点之间通过指针链接解析 D D 项是 B+ 树的特点, 而不是 B 树的特点 9 已知关键序列 5,8,12,19,28,20,15,22 是小根堆 ( 最小堆 ), 插入关键字 3, 调整后得

3 到的小根堆是 ( ) A.3,5,12,8,28,20,15,22,19 C.3,8,12,5,20,15,22,28,19 解析 A B.3,5,12,19,20,15,22,8,28 D.3,12,5,8,28,20,15,22,19 10 若数据元素序列 11,12,13,7,8,9,23,4,5 是采用下列排序方法之一得到的第二趟排序后的结果, 则该排序算法只能是 ( ) A. 起泡排序 B. 插入排序 C. 选择排序 D. 二路归并排序解析 B 若是起泡排序或者选择排序, 则第二趟后应有 2 个最大或者最小的元素正确排列, 而结果不符二路归并排序第二趟后, 应形成 2 个长度为 4 的有序子序列, 结果也不符合所以答案只能是插入排序两次插入后, 前 3 个数子的顺序是对的 41 带权图( 权值非负, 表示边连接的两顶点间的距离 ) 的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径假定从初始顶点到目标顶点之间存在路径, 现有一种解决该问题的方法 : 1 设最短路径初始时仅包含初始顶点, 令当前顶点 u 为初始顶点 ; 2 选择离 u 最近且尚未在最短路径中的一个顶点 v, 加入到最短路径中, 修改当前顶点 u=v; 3 重复步骤 2, 直到 u 是目标顶点时为止请问上述方法能否求得最短路径? 若该方法可行, 请证明之 ; 否则, 请举例说明解析该方法求得的路径不一定是最短路径例如, 对于下图所示的带权图, 如果按照题中的原则, 从 A 到 C 的最短路径为 A B C, 事实上其最短路径为 A D C 42 已知一个带有表头结点的单链表, 结点结构为, 假设该链表只给出了头指针 list 在不改变链表的前提下, 请设计一个尽可能高效的算法, 查找链表中倒数第 k 个位置上的结点 (k 为正整数 ) 若查找成功, 算法输出该结点的 data 值, 并返回 1; 否则, 只返回 0 要求 :

4 (1) 描述算法的基本设计思想 ; (2) 描述算法的详细实现步骤 ; (3) 根据设计思想和实现步骤, 采用程序设计语言描述算法 ( 使用 C 或 C++ 或 JAVA 语言实现 ), 关键之处请给出简要注释解析 (1) 算法基本思想如下 : 从头至尾遍历单链表, 并用指针 p 指向当前结点的前 k 个结点当遍历到链表的最后一个结点时, 指针 p 所指向的结点即为所查找的结点 (2) 详细实现步骤 : 增加两个指针变量和一个整型变量, 从链表头向后遍历, 其中指针 p1 指向当前遍历的结点, 指针 p 指向 p1 所指向结点的前 k 个结点, 如果 p1 之前没有 k 个结点, 那么 p 指向表头结点用整型变量 i 表示当前遍历了多少个结点, 当 i>k 时, 指针 p 随着每次遍历, 也向前移动一个结点当遍历完成时,p 或者指向表头结点, 或者指向链表中倒数第 k 个位置上的结点 (3) 算法描述 : int LocateElement(Linklist list,int k) p1=list->link; p=list; i=1; while(p1) p1=p1->link; i++; if(i>k) p=p->next; // 如果 i>k, 则 p 也往后移 if(p==list) return 0; // 说明链表没有 k 个结点 else printf( %d\n,p->data); return 1;

5 10 年真题 1 若元素 a b c d e f 依次进栈, 允许进栈退栈操作交替进行, 但不允许连续三次进行退栈操作, 则不可能得到的出栈序列是 ( ) A.d,c,e,b,f,a B.c,b,d,a,e,f C.b,c,a,e,f,d D.a,f,e,d,c,b 解析 D 快速解题, 选项所给序列中出现长度大于等于 3 的连续逆序子序列, 即为不符合要求的出栈序列四个选项所给序列的进出栈操作序列分别为 : A. Push,Push,Push,Push,Pop,Pop,Push,Pop,Pop,Push,Pop,Pop; B. Push,Push,Push,Pop,Pop,Push,Pop,Pop,Push,Pop,Push,Pop; C. Push,Push,Pop,Push,Pop,Pop,Push,Push,Pop,Push,Pop,Pop; D. Push,Pop,Push,Push,Push,Push,Push,Pop,Pop,Pop,Pop,Pop; 按照题设要求, 选项 D 所给序列即为不可能得到的出栈顺序 2 某队列允许在其两端进行入队操作, 但仅允许在一端进行出队操作, 若元素 a,b,c,d,e 依次入此队列后再进行出队操作, 则不可能得到的出队序列是 ( ) A.b,a,c,d,e B.d,b,a,c,e C.d,b,c,a,e D.e,c,b,a,d 解析 C : 快速解题, 无论哪种入队方式 ( 即先从左边入队还是先从右边入队 ),a 和 b 都应该相邻, 这是出队序列合理的必要条件只有选项 C 所给序列中 a 与 b 不相邻四个选项所给序列的进队操作序列分别为 (L 代表左入,R 代表右入 ): A. al( 或 ar), bl, cr, dr, er B. al( 或 ar), bl, cr, dl, er C. 不可能出现 D. al( 或 ar), bl, cr, dr, el 3 下列线索二叉树中( 用虚线表示线索 ), 符合后序线索树定义的是 ( )

6 解析 D 线索二叉树利用二叉链表的空链域来存放结点的前驱和后继信息题中所给二叉树的后序序列为 d,b,c,a 结点 d 无前驱和左子树, 左链域空, 无右子树, 右链域指向其后继结点 b; 结点 b 无左子树, 左链域指向其前驱结点 d; 结点 c 无左子树, 左链域指向其前驱结点 b, 无右子树, 右链域指向其后继结点 a 4 在下列所示的平衡二叉树中插入关键字 48 后得到一棵新平衡二叉树, 在新平衡二叉树中, 关键字 37 所在结点的左右子结点中保存的关键字分别是 ( ) A.13,48 B.24,48 C.24,53 D.24,90 解析 C 插入 48 以后, 该二叉树根结点的平衡因子由 -1 变为 -2, 失去平衡, 进行平衡调整, 过程如下图 : 5 在一棵度数为 4 的树 T 中, 若有 20 个度为 4 的结点,10 个度为 3 的结点,1 个度为 2 的结点,

7 10 个度为 1 的结点, 则树 T 的叶结点个数是 ( ) A.41 B.82 C.113 D.122 解析 B 设树中度为 i(i=0,1,2,3,4) 的结点数分别为 N, 树中结点总数为 N, 则树中各结点的度之和等于 N 1, 即 : N = 1+ N N = N + N + N + N + N 1 + 2N2 + 3N3 + 4 根据题设中的数据, 即可得到 N 0 = 82, 即树 T 的叶结点的个数是对 n(n>=2) 个权值均不相同的字符构成哈夫曼树, 下列关于该哈夫曼树的叙述中, 错误的是 ( ) A. 该树一定是一棵完全二叉树 B. 树中一定没有度为 1 的结点 C. 树中两个权值最小的结点一定是兄弟结点 D. 树中任一非叶结点的权值一定不小于下一层任一结点的权值解析 A 哈夫曼树为带权路径长度最小的二叉树, 不一定是完全二叉树哈夫曼树中没有度为 1 的结点,B 正确 ; 构造哈夫曼树时, 最先选取两个权值最小的结点作为左右子树构造一棵新的二叉树,C 正确 ; 哈夫曼树中任一非叶结点 P 的权值为其左右子树根结点权值之和, 其权值不小于其左右子树根结点的权值, 在与结点 P 的左右子树根结点处于同一层的结点中, 若存在权值大于结点 P 权值的结点 Q, 那么结点 Q 与其兄弟结点中权值较小的一个应该与结点 P 作为左右子树构造新的二叉树, 综上可知, 哈夫曼树中任一非叶结点的权值一定不小于下一层任一结点的权值 7 若无向图 G=(V,E) 中含有 7 个顶点, 则保证图 G 在任何情况下都是连通的, 则需要的边数最少是 ( ) A.6 B.15 C.16 D.21 解析 C 要保证无向图 G 在任何情况下都是连通的, 即任意变动图 G 中的边,G 始终保持连通, 首先需要 G 的任意六个结点构成完全连通子图 G1, 需 15 条边, 然后再添一条边将第 7 个结点与 G1 连接起来, 共需 16 条边 8 对下图进行拓扑排序, 可以得到不同的拓扑序列的个数是 ( ) i 4 A.4 B.3 C.2 D.1 解析 B 拓扑排序的步骤为: (1) 在有向图中选一个没有前驱的顶点并且输出之 ; (2) 从图中删除该顶点和所以以它为尾的弧重复上述两步, 直至全部顶点均已输出由于没有前驱的顶点可能不唯一, 所以拓扑排序的结果也不唯一题中所给图有三个不同的拓扑排序序列, 分别为 a,b,c,e,d;a,b,e,c,d;a,e,b,c,d

8 9 已知一个长度为 16 的顺序表 L, 其元素按关键字有序排列, 若采用折半查找法查找一个 L 中不存在的元素, 则关键字的比较次数最多是 ( ) A.4 B.5 C.6 D.7 解析 B 折半查找法在查找不成功时和给定值进行比较的关键字个数最多为 +1, 即折半查找判定树的高度, 在本题中,n=16, 故比较次数最多为 5 10 采用递归方式对顺序表进行快速排序下列关于递归次数的叙述中, 正确的是 ( ) A. 递归次数与初始数据的排列次数无关 B. 每次划分后, 先处理较长的分区可以减少递归次数 C. 每次划分后, 先处理较短的分区可以减少递归次数 D. 递归次数与每次划分后得到的分区的处理顺序无关解析 D 本题实际考察了快速排序的时间复杂度分析, 快速排序的效率与初始序列有关这是显然的, 因此 A 错对于 B,C,D: 折半查找法的算法可以简写为 : void qicksort(int R[],int l,int r) qicksort(r,l,i-1);//1 qicksort(r,i+1,r);//2 快速排序的递归次数由 l 和 r 决定 (l 和 r 决定了要处理问题的规模 ) 将快速排序的递归次数设为 F(l,r), 则按照上述代码中 12 句的执行次序有 : 递归次数 F(l,r)=F(l,i-1)+F(i+1,r)...3 如果将 12 句颠倒, 则有 : 递归次数 F(l,r)=F(i+1,r)+F(l,i-1)...4 显然 3 和 4 式是相等的, 因此递归次数与每次划分后得到的分区处理顺序无关 11 对一组数据(2,12,16,88,5,10) 进行排序, 若前三趟排序结果如下 : 第一趟 :2,12,16,5,10,88 第二趟 :2,12,5,10,16,88 第三趟 :2,5,10,12,16,88 则采用的排序方法可能是 ( ) A. 起泡排序 B. 希尔排序 C. 归并排序 D. 基数排序解析 A 本题考查起泡排序算法的执行过程 41 将关键字序列( ) 散列存储到散列表中, 散列表的存储空间是一个下标从 0 开始的一维数组, 散列函数为 :H(key)=(key 3) MOD 7, 处理冲突采用线性探测再散列法, 要求装填 ( 载 ) 因子为 0.7 (1) 请画出所构造的散列表

9 (2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度解析 (1) 因为装填因子为 0.7, 数据总数为 7, 所以存储空间长度为 L = 7/0.7 = 10; 因此可选 T = 10, 构造的散列函数为 : 线性探测再散列函数为 : 因此, 各数据的下标为 : Hi(key)= ( H(key)+ H(key) = (key 3) MOD 10 d i ) MOD 10, ( d i = 1,2,3...9) H(7) = (7 3) MOD 10 = 1 H(8) = (8 3) MOD 10 = 4 H(30) = (30 3) MOD 10 = 0 H(11) = (11 3) MOD 10 = 3 H(18) = (18 3) MOD 10 = 4 H1(18) = (H(18)+1) MOD 10 = 5 H(9) = (9 3) MOD 10 = 7 H(14) = (14 3) MOD 10 = 2 由上述计算所得 Hash 表如下 : (2) 由上表可以得 : 查找成功的平均查找长度为 : ASL1=( )/7=8/7 查找不成功的平均查找长度为 : ASL2=( )= 设将 n(n>1) 个整数存放到一维数组 R 中设计一个在时间和空间两方面尽可能高效的算法将 R 中保存的序列循环左移 P(0<P<n) 个位置, 即将 R 中的数据由 (X0,X1,,Xn-1) 变换为 (Xp,Xp+1,,Xn-1,X0,X1,,Xp-1) 要求: (1) 给出算法的基本设计思想 (2) 根据设计思想, 采用 C 或 C++ 或 Java 语言描述算法, 关键之处给出注释 (3) 说明你所设计算法的时间复杂度和空间复杂度解析 (1) 建立一个可以放下 p 个整数的辅助队列, 将数组 R 中的前 p 个整数依次进入辅助队列, 将 R 中后面的 n-p 个整数依次前移 p 个位置, 将辅助队列中的数据依次出队, 依次放入 R 中第 n-p 个整数开始的位置 (2) 使用 C 语言描述算法如下 : void Shift(int R[],int n,int p)//n 为存放的整数个数,p 为循环左移的个数 int temp[p]; // 辅助数组, 存放要移出的整数 int i=0; while(i<p) // 将 R 中前 p 个数据存入辅助数组中 temp[i]=r[i];

10 i++; i = 0; while(i<n-p) // 将 R 中从第 p 个整数开始的整数前移 p 个位置 R[i]=R[p+i]; i++; i = 0; while(i<p) // 将辅助数组中的 p 个数据放到 R 中第 n-p 个数据的后面 R[n-p+i]=temp[i]; i++; (3) 所设计的算法的时间复杂度为 O(n), 空间复杂度为 O(p)

11 11 年真题 1 设 n 是描述问题规模的非负整数, 下面的程序片段的时间复杂度是 ( ) x=2; while(x<n/2) x=2*x; A.O(log 2 n) B.O(n) C.O(nlog 2 n) D.O(n 2 ) 解析 A 容易看出, 程序基本操作为 x=2*x; 基本操作执行的次数即为程序的时间复杂度, 因此可设基本操作执行 k 次结束, 则有 : 执行第 1 次 :x=2 2=2 1+1 =4; 执行第 2 次 :x=4 2=2 2+1 =8; 执行第 3 次 :x=8 2=2 3+1 =16; 执行第 k 次 :x=2 k+1 由循环结束条件知 :x<n/2, 即 2 k+1 <n/2 时结束, 即 k<log 2 n-2, 即 k=log 2 n+c( 为方便说明, 其中 C 为起修正作用的常数 ) 综上得 : 时间复杂度为 O(log 2 n) 2 元素 a,b,c,d,e 依次进入初始为空的栈中, 若元素进栈后可停留可出栈, 直到所有元素都出栈, 则在所有可能的出栈序列中, 以元素 d 开头的序列个数是 ( ) A.3 B.4 C.5 D.6 解析 B 若要保证出栈序列以 d 开头, 则前三个元素必连续进栈, 中间不能出现出栈的情况, 然后 d 出栈, 此时栈内元素由底到顶为,a,b,c, 栈外元素为 e, 出栈序列中元素为 d 因为 a,b,c 三个元素在栈内的顺序已定, 由栈的先进后出原则, 其在出栈序列中的相对位置必为 c b a ; 加上 d 的位置已定, 所以出栈待定序列必为 d c b a 显然在栈外的 e 可以在任何时候出栈入栈, 即可以出现在以上待定序列中任何一个省略号的位置, 即出栈序列可为 : 1:d,e,c,b,a; 2:d,c,e,b,a; 3:d,c,b,e,a; 4:d,c,b,a,e 3 已知循环队列存储在一维数组 A[0 n-1] 中, 且队列非空时 front 和 rear 分别指向队头和队尾元素若初始时队列为空, 且要求第 1 个进入队列的元素存储在 A[0] 处, 则初始时 front 和 rear 的值分别是 ( ) A.0,0 B.0,n-1 C.n-1,0 D,n-1,n-1 解析 B 插入元素时,front 不变,rear+1. 而插入第一个元素后, 队尾要指向尾元素, 显然,rear 初始应该为 n-1,front 为 0 4 若一棵完全二叉树有 768 个结点, 则该二叉树中叶子结点的个数是 ( ) A.257 B.258 C.384 D.385

12 解析 C 由完全二叉树的高度和结点个数的关系可得本完全二叉树的高度为 10 第 10 层上的结点个数为 768-(2 9-1)=257( 这些全为叶子结点 ); 第 9 层上的非叶结点为 (257-1)/2+1=129; 则第 9 层上的叶子结点个数为 : =127; 则叶子结点总数为 =384 5 若一棵二叉树的前序遍历序列和后序遍历序列分别为 1,2,3,4 和 4,3,2,1, 则该二叉树的中序遍历序列不会是 ( ) A.1,2,3,4 B.2,3,4,1 C.3,2,4,1 D.4,3,2,1 解析 C 满足题干的二叉树必须满足树中不存在双分支结点则可以画出以下二叉树排除选项 : 可以看出 A,B,D 三项都是可以的 6 已知一棵有 2011 个结点的树, 其叶结点个数为 116, 该树对应的二叉树中无右孩子的结点的个数是 ( ) A.115 B.116 C.1895 D.1896 解析 D 可以采用特殊情况法去解可举以下特例: 如上图, 则对应的二叉树中仅有前 115 个结点有右孩子 7 对于下列关键字序列, 不可能构成某二叉排序树中一条查找路径的序列是 ( ) A.95,22,91,24,94,71 B.92,20,91,34,88,35 C.21,89,77,29,36,38 D.12,25,71,68,33,34 解析 A

13 由选项 A 做出查找路径的一部分, 发现在 91 的左子树中出现了大于 91 的 94, 因此 A 选项不可能 8 下列关于图的叙述中, 正确的是 ( ) 1 回路是简单路径 2 存储稀疏图, 用邻接矩阵比邻接表更省空间 3 若有向图中存在拓扑序列, 则该图不存在回路 A. 仅 1 B 仅 1 2 C 仅 3 D 仅 1 3 解析 C (1) 若路径中除了开始点和结束点可以相同以外, 其余顶点均不相同, 则称这条路径为简单路径 (2) 若一条路径中第一个顶点和最后一个顶点相同, 则这条路径是一条回路 ( 回路中可能存在既不是起点也不是终点的相同点 ) (3) 邻接矩阵不图稀疏还是稠密, 都取的是最大的存储空间, 因此不如邻接表更适合存储稀疏矩阵 (4) 用拓扑排序的方法可以判断图中是否存在回路, 如果对一个图可以完成拓扑排序, 则此图不存在回路 9 为提高散列(Hash) 表的查找效率, 可采取的正确措施是 ( ) 1 增大装填因子 2 设计冲突少的散列函数 3 处理冲突时避免产证聚集现象 A. 仅 1 B. 仅 2 C. 仅 12 D. 仅 23 解析 B 要提高查找效率, 就要减少 Hash 表的冲突, 因此 2 是正确的措施对于 1 装填因子增大, 则相应的表中空闲位置就少, 更容易发生冲突, 因此 1 不对聚集现象是不可避免的, 因此 3 不对 10 为实现快速排序算法, 待排序序列宜采用的存储方式是 ( ) A. 顺序存储 B. 散列存储 C 链式存储 D 索引存储解析 A 内部排序均采用顺序结构存储 11 已知序列 25,13,10,12,9 是大根堆, 在序列尾部插入新元素 18, 将其再调整为大根堆, 调整过程中元素之间进行的比较次数是 ( ) A.1 B.2 C.4 D.5 解析 B 在序列尾部插入 18 后当前堆如下 : 可见 10<18( 第一次比较 ), 需要调整, 因此交换 10 和 10 得如下堆 :

14 可见 18<25( 第二次比较 ) 不需要再次调整, 因此只需要调整 2 次 41 已知有一个 6 个顶点 ( 顶点编号 0~5) 的有向带权图 G, 其邻接矩阵 A 为上三角矩阵, 它的压缩存储如下 : 要求 : (1) 写出图 G 的邻接矩阵 A; (2) 画出有向带权图 G; (3) 求图 G 的关键路径, 并计算关键路径的长度解析本题考察图的存储以及关键路径求解的综合知识 (1) 由题可以画出待定上三角矩阵的结构图如下 ( 图中? 为待定元素 ): 可以看出, 第一行至第五行主对角线上方的元素分别为 5,4,3,2,1 个, 由此可以画出压缩存储数组中的元素所属行的情况, 如下图所示 : 将各元素填入各行即得邻接矩阵 :(2 分 ) (2) 根据第一步所得矩阵 A 容易做出有向带权图 G, 如下 :(2 分 )

15 (3) 下图中粗线箭头所标识的 4 个活动组成图 G 的关键路径 (3 分 ) 由上图容易求得图的关键路径长度为 : =16 42 一个长度为 L(L 1) 的升序序列 S, 处在第 L / 2 个位置的数称为 S 的中位数例如, 若序列 S 1 = (11, 13, 15, 17, 19), 则 S 1 的中位数为 15 两个序列的中位数是含它们所有元素的升序序列的中位数例如, 若 S 2 = (2, 4, 6, 8, 10), 则 S 1 和 S 2 的中位数为 11 现有两个等长的升序序列 A 和 B, 试设计一个在时间和空间两方面都尽可能高效的算法, 找出两个序列 A 和 B 的中位数要求 : (1) 给出算法的基本设计思想 ; (2) 根据设计思想, 采用 C 或 C++ 或 JAVA 语言描述算法, 关键之处给出注释 ; (3) 说明你所设计算法的时间复杂度和空间复杂度解析本题考察基本算法的灵活运用 (1) 算法的基本设计思想 :(5 分 ) 1 笨法 : 如果考场紧张, 无奈之下可以写如下算法 ( 虽然不能得全分, 但总比花时间又写错好的多 ) 算法如下 : 将两升序序列归并排序, 然后求其中位数, 时间复杂度为 O(n), 空间复杂度为 O(n) 2 高效方法 : 分别求两个升序序列 A 和 B 的中位数, 设为 a 和 b 1) 若 a = b, 则 a 或 b 即为所求的中位数原因 : 容易验证, 如果将两序列归并排序, 则最终序列中, 排在子序列 ab 前边的元素为先前两序列中排在 a 和 b 前边的元素 ; 排在子序列 ab 后边的元素为先前两序列 a 和 b 后边的元素所以子序列 ab 一定位于最终序列的中间, 又因为 a=b, 显然 a 就是中位数 2) 否则 ( 假设 a<b), 中位数只能出现 (a,b) 范围内原因 : 同样可以用归并排序后的序列来验证, 归并排序后必然有形如 a b 的序列出现, 中位数必出现在 (a,b) 之间因此可以做如下处理 : 舍弃 a 所在序列 A 之较小一半, 同时舍弃 b 所在序列 B 之较大一半在保留的两个升序序列中求出新的中位数 a 和 b, 重复上述过程, 直到两个序列中只

16 含一个元素时为止, 则较小者即为所求的中位数 (2) 算法实现 ( 高效方法 ):(8 分 ) int Search(int A[], int B[], int n) int s1,e1,mid1,s2,e2,mid2; s1=0;e1=n-1;s2=1;e2=n-1; while(s1!=e1 s2!=e2) mid1=(s1+e1)/2; mid2=(s2+e2)/2; if(a[mid1]==b[mid2]) return A[mid1]; if(a[mid1]<b[mid2]) // 分别考虑奇数和偶数, 保持两个子数组元素个数相等 if ((s1+e1)%2 == 0) // 若元素个数为奇数个 s1=mid1; // 舍弃 A 中间点以前部分且保留中间点 e2=mid2; // 舍弃 B 中间点以后部分且保留中间点 else // 若元素个数为偶数个 s1 = mid1+1; // 舍弃 A 中间点及中间点以前部分 e2 = mid2; // 舍弃 B 中间点以后部分且保留中间点 else if ((s1+e1)%2==0) // 若元素个数为奇数个 e1 = mid1; // 舍弃 A 中间点以后部分且保留中间点 s2 = mid2; // 舍弃 B 中间点以前部分且保留中间点 else // 若元素个数为偶数个 e1 = mid1+1; // 舍弃 A 中间点以后部分且保留中间点 s2 = mid2; // 舍弃 B 中间点及中间点以前的部分

17 return (A[s1] < B[s2]? A[s1] : B[s2]); (3) 上述所给算法的时间空间复杂度分别是 O(log2n) 和 O(1) (2 分 ) 1 因为每次总的元素个数变为原来的一半, 所以有 : 第 1 次 : 元素个数为 n/2=n/(2 1 ) 第 2 次 : 元素个数为 n/4=n/(2 2 ) 第 k 次 : 元素个数为 n/(2 k ) 最后元素个数为 2 则有 n/(2 k )=2 解得 k=log 2 n - 1 因此 : 时间复杂度为 O(log 2 n) 2 有程序显而易见空间复杂度为 O(1)

2009

2009 数据结构考研真题及解答目录 2009 年试题... 1 填空题... 1 解答题... 2 2010 年试题... 2 填空题... 2 解答题... 4 2011 年试题... 4 填空题... 4 解答题... 5 2012 年试题... 6 填空题... 6 解答题... 7 2013 年试题... 8 填空题... 8 解答题... 9 2014 年试题... 10 填空题... 10

A.39 B.52 C.111 D.119 解析 C 根据完全二叉树的定义, 此树的前 6 层应该是满二叉树, 共有 = 63 个结点 第 6 层有 8 个叶子结点, 说明另外 32-8=24 个结点不是叶子结点, 最多各有 2 个孩子结点 而该树不可能有第 8 层存在, 所以结点总数最

A.39 B.52 C.111 D.119 解析 C 根据完全二叉树的定义, 此树的前 6 层应该是满二叉树, 共有 = 63 个结点第 6 层有 8 个叶子结点, 说明另外 32-8=24 个结点不是叶子结点, 最多各有 2 个孩子结点而该树不可能有第 8 层存在, 所以结点总数最