中国科学技术大学1995年考研试题.doc

Size: px

Start display at page:

Download "中国科学技术大学1995年考研试题.doc"

融执聂
7 years ago
Views:

1 中国科学技术大学一九九五年招收硕士学位研究生入学考试试题试题名称 : 程序设计一选择题 1. 一颗深度为 6 的平衡二叉树, 其每个非终端节点的平衡因子均为 1, 则该树共有个节点.(2 分 ) a) 14; b) 16; c) 18; d) 20; e) 22; f) 一个有 28 条边的非连通无向图, 至少应有个节点.(2 分 ) a) 6; b) 7; c) 8; d) 9; e) 10; f) 一颗 124 个叶节点的完全二叉树, 最多有个节点.(2 分 ) a) 247; b) 248; c) 249; d) 250; e) 按锦标赛排序的方法, 决定出 8 位运动员之间的名次顺序排列, 至少需编排场次的比赛.( 考虑最坏情况 ) (2 分 ) a) 13; b) 14; c) 15; d) 16; e) 已知 Head(Tail([Head(S),Head(Tail(Tail(S)))]))=[a], 广义表 S 满足上式, 则 S 为.( 其中, 方括号表示广义表, 圆括号表示函数, 如 [a,b] 表示由 a,b 构成的广义表, 而 Head() 表示取广义表的头部.) (2 分 ) a) [[a,b],b,a] b) [[b,a],[a],[b]] c) [[a],[a,b],[b]] d) [b,[a],[a,b]] e) [[a],[b],[b,a]] f) [[b],[b,a],[a]] 6. 在下列三种次序的线索二叉树中, 对查找指定节点在该次序下的后继效果较差. (2 分 ) a) 前序线索树 b) 中序线索树 c) 后序线索树 7. 有二叉树的前序和后序遍历序列唯一的确定这颗二叉树. (2 分 ) a) 能 b) 不能 8. 在下列两种求图的最小生成树的算法中, 算法适合于求边稀疏的网的最小生成树. (2 分 ) a) Prim; b) Kruskal 9. 下列无向图的存储结构中, 在对无向图的边进行操作时 ( 如删除一条边 ) 存储结构更为合适 a) 邻接表 b) 邻接多重表 10. 在下述几中树中, 可以表示静态查找表. (2 分 ) a) 次优查找树 ; b) 二叉排序树 ; c) B- 树 d) 平衡二叉树 11. 答案写在填空的字母后面 (1) 在文件局部有序或文件长度较小的情况下, 最佳内部排序的方法是 A (2) 快速排序在最坏情况下, 时间复杂度是 B, 比 C 的性能差 (3) 就平均时间而言, D 最佳 ( 共 4 分 ) A: a) 直接插入排序 ; b) 起泡排序 ; c) 简单选择排序 ; B: a) O(n log n); 2 b) O( n ); 3 c) O( n ) C: a) 堆排序 ; b) 起泡排序 ; c) 选择排序 D: a) 堆排序 ; b) 快速排序 ; c) 归并排序 12. 一程序规定的职能是 : 输入三个整数作为三边的边长构成三角形, 判别是等腰三角形, 等边三角形, 或是一般三角形, 再做计算.. 若用等价类划分方法对该程序做功能测试, 至少应对该程序的输入数据考虑 A 个等价类, 其中包括 B 个有效等价和 C 个无效等价类.A,B,C: ( 答案写在填空的字母后面 )

2 (1) 3; (2) 5; (3) 7; (4) 12; (5) 15; (6) 18; (7) 21; (8) 25 (9) 33; (10) 二叉树如图所示 (1) 给出先序遍历的节点的顺序 ; (2) 给出中序遍历的节点的顺序 ; (3) 给出后序遍历的节点的顺序 ; (4) 用二叉链表作为存储结构, 将出现多少个空指针 (nil) 域? ( 共 4 分 ) 14. 下列函数 (6 分 ) function calc(x,y:integer) : integer; if y=1 then calc := x else calc := calc ( x, y-1 ) + x end; a,b 均为正整数, 则 calc (a,b) = 1) a*(b-1); 2) a*b; 3) a + b 4) a+a 15. 程序段 read (a,b); c := 3.0 * a + b; if c=0 then a := 1 else a := / c / b 保证该程序段运行不出错的必要条件是 :. (4 分 ) (1) b>0 (2) a>0 and b>0 (3) b 0 (4) b 0 and c 0 二程序改错与填空 1. 指出下列程序段中的错误位置, 对错误编号, 说明理由 : 程序段一 : (8 分 ) label 1; const max=50; type day = { Mon, Tue, Wed, Thu, Fri, Sat, Sun; var date:day; N:integer; a: N:=N-ord('0'); b: for date :=Mon to Sun do N := ord(succ(date)) 1; c: for n := 1 to 10 do

3 1: 语句 ; end; goto 1; end. 答 : 程序段二. (8 分 ) program type(input,output); var R:real; procedure print(var x:integer, y:real); var z:real; procedure sum(x:integer, y:real); var k:real; z:= x+y; k:= 3*z; x:= x+y; end; {sum sum(x,y); writeln(x,y,z,k) end; {print { 主程序 readln(r); print(15,r); print(r,r) end. 答 :. 2. 阅读下列程序, 填空使之成为一个完整的程序. 该程序输出 N 个元素的全排列. 例如 N=3 时, 程序输出为 : (12 分 ) 程序 : program pic(input,output); const n=10; var A:array[1..n] of integer; i,k:integer; procedure output1; for i := 1 to n do write(a[i]:3);

4 writeln; end; {output1 procedure permute(k:integer); var i,t:integer; if k=1 then output1 else ; for i:=1 to do t:=a[k]; A[k]:=A[i]; A[i]:=t; ; t:= ; A[k]:= ; ; end {for end {else end; { permute k:=n; for i:=1 to k do A[i]:=i; permute(k) end. 三编程题 : ( 语言可任选, 要求思路清晰, 书写工整 ) 1. 编写程序将一个循环队列的内容倒置, 该循环队列存储在一个数组 A[1..n] 中, 例如图 a 中为倒置前的队列, 图 b 中为倒置后的队列. 要求倒置后的队列从数组的第一个元素开始存储, 整个程序的运行时间为 O(n). (15 分 ) 2. 设计一个程序, 使输入的句子按如下方式改造之后输出 : (1) 单词之间只留一个空格做间隔 ;

5 (2) 句子结束后必须紧跟句号 ; (3) 如果把句子的单词从左到右依次编号为 1,2,3, 则对于第奇数个单词, 只要直接复制就行了, 而对于第偶数个单词, 应按反序打印.(15 分 ) 例如 : 输入句子是 : this is a silly program ; 改造后的输出是 : this si a yllis program.

6 中国科学技术大学一九九六年招收硕士学位研究生入学考试试题试题名称 : 程序设计一单项选择 : (20 分 ) 1. 具有几个节点的完全二叉树的深度是 :. 1) log 2 n 2) log 2 n + 1 3) log 2 (n + 1) 4) n 2. 用单循环链表表示队列, 正确的说法是 : 1) 可设一个头指针使入队出队都方便 2) 可设一个尾指针使入队出队都方便 3) 必须设头尾指针才能使入队出队都方便 ; 4) 无论如何, 只可能使入队方便. log 对无向图而言, 同一条边在邻接表中用两个节点表示而在邻接多重表中只用一个节点表示, 因此邻接多重表所需存储量比邻接表. 1) 少一半 2) 多, 但差异不大 3) 少, 但差异不大 4. 一个哈希函数被认为是好的, 如果它满足条件. 1) 哈希地址分布均匀 2) 保证不产生冲突 3) 所有哈希地址在表长范围内 4) 满足 2) 和 3) 5.ISAM 文件和 VSAM 文件属于. 1) 索引非顺序文件 2) 索引顺序文件 3) 顺序文件 4) 散列文件 6. 在下述排序算法中算法是稳定的排序算法. 1) 希尔排序 2) 冒泡排序 3) 快速排序 7. 平衡二叉树中, 若某个节点在左右子节点的平衡因子为零, 则该节点的平衡因子也一定是零, 这种说法. 1) 不正确 2) 正确 8. 在下属三种排序算法中, 所需辅助存储量最多的是, 所需存储量最少的是, 平均速度最快的是. 1) 堆排序 2) 快速排序 3) 归并排序二问答题 (25 分 ) 1. 已知某电文中共出现 10 种不同的字母, 各个字母出现的频率分别为 A:8, B:5, C:3, D:2, E:7, F:23, G:9, H:15, I:3, J:35, 现在对这段电文用三进制进行编码 ( 即码字由 0,1,2 组成 ), 问电文编码总长度最少有多少位? 并画出图 2.A 是一个三对角矩阵, 行数与列数相等, 用压缩存储的方法将其压缩存储到一维的数组 SA[ 1.. 3n 2 ] 中 ( 按行序顺序存储 ), 则 SA[ k ] 对应的矩阵元素的下标为 : 行值 i =, 列值 j =. 反过来, 若知道 A 中元素的下标 i, j, 则其存储位置 k=.( 写出表达式 ) 3. 设 A 是一个栈, 栈中共有 n 各元素, 依次为 : a1,a 2, L, a n, 栈顶元素为 a n,b 是一个循环队列, 队列中 n 各元素依次为 b1, b2, L, bn, 队头元素为 b 1, A B 均采用顺序存储结构且存储空间足够大, 现要将栈中元素全部移到队列中, 使得队列中元素与栈中元素交替排列, 即 B 中元素为 b L, 问至少需要多少次基本操作才能完成上述工作, 请写出具体步骤 ( 要 1,a1, b2,a 2, b3, a 3,, bn, a n

7 求除 A B 外所用的其他附加存储量为 1, 每次出栈入栈出队列入队列均看作一次基本操作 ). 4. 试为下列二叉树建立后序线索, 画出相应的后序线索二叉树. 三算法描述 (15 分 ) 以二叉链表作存储结构, 编写按层次顺序 ( 从根节点开始 ) 遍历二叉树的算法. 四阅读下列程序, 并回答 : 下列程序是否正确? 为什么? 如何修改? (5 分 ) var a,b,c,d,e,f:integer; procedure mult(var x,y,z:integer); z:=0; while x<>0 do if odd(x) then z:=z+y; y:=y*z; z:=x div 2 ; end; end; a:=5; b:=7; d:=11; e:=13; mult(a,b,c); /* 要求输出 c=15 */ mult(d b, e a, f ); /* 要求输出 f=32 */ end. 五阅读下列程序说明和 C 程序, 把应填入其中处的字句, 写在答卷的对应栏内. [ 程序说明 ] 对于正整数 n, 输出其和等于 n 且满足以下限制条件的所有正整数的和式, 即组成和式的数字自左至右构成一个非递增的序列. 如 n = 4, 程序输出为 4 = 4 4 = = = = 程序中给出了分别采用递归和非递归解法的两个函数 rd() 和 nd(). 函数 rd() 采用递归解法, 它有两个参数 a 和 k. 其意义分别是被分解和式的数 n, 及当前第 k 深度分解. 算法思想是对 n 的所有合理的和式分解, 将分解出的数 ( 称为和数 ) 存于数组 a[ ] 中. 当其中一个分解已不再需要进一步分解时, 即找到一个解, 将存于数组 a[ ] 中的一个完整和式的和数输出. 当还需要进一部分解时, 以要进一部分解的数及分解深度为参数, 递归调用分解和式函数. 函数 nd() 以要分解的数为参数, 另开设一个数组 r[ ], 用于存储当前还未分解的余数. 在求一个解的第 k

8 步时,a[k] 为第 k 个和数,r[k] 为相应的余数. 当找到一个分解后 ( 此步 r[k] 等于 0, 给出解, 并做回溯处理, 从当前 k 退回到第一个不为 1 的和数, 将其减 1, 并将其余数加 1, 准备去找另一个解 ; 否则, 生成下一步的分解和数与余数.(15 分 ) 答 : 1) 2) 3) 4) 5) 6) [ 程序 ] #define MAXN 100 int a[maxn], r[maxn]; rd(int n, int k) { int j,i; for( j= 1 ; j >= 1 ; j ) { a[k]=j; if ( 2 ) { printf("%d = %d",a[0],a[1]); for ( i = 2; i <= k; i ++ ) printf(" + %d",a[i]); printf("\n"); else 3 ; nd(int n) { int i,k; k=0; r[0]=n; do { if ( 4 ) { printf("%d = %d",a[0],a[1]); for ( i=2; i <= k; i + +) printf(" + %d",a[i]); printf("\n"); while ( k > 0 && 5 ) k ; if ( k > 0) { a[k] ; r[k] + + ; else { a[k+1] = 6 ; r[k+1] = r[k] a[k+1]; k + +; /* else */ while ( k > 0 ); int test_data[] = { 3, 4, 5 ; main()

9 { int i; for ( i=0; i < sizeof test_data/sizeof (int) ; i ++) { a[0] = test_data[i]; rd(test_data[i],1); printf("\n \n\n"); nd(test_data[i]); printf("\n \n\n"); 六设计一个程序读入一个字符串, 统计该字符串中出现的字符及其次数, 然后仪表的形式输出结果. 要求用一个二叉树来保存处理结果, 字符串中的每个不同的字符用数中不同的节点描述, 每个节点包含四个域, 格式为 : 字符该字符的出现次数指向 ASCII 码小于该字符的左子树指针指向 ASCII 码小于该字符的右子树指针因此程序的功能是依次从输入字符串中取出一个字符, 把它们插入到树中 ( 新出现字符 ) 或修改原树中相应节点的出现次数域 ( 已出现字符 ). (20 分 )

10 中国科学技术大学一九九七年招收硕士研究生入学考试试题试题名称 : 程序设计一选择填空 ( 每空 1 分, 共 10 分 ) 1. 查找几个元素的有序表时, 最有效的查找方法是. a: 数序查找 ; b: 分块查找 ; c: 二分查找 ; d: 二叉排序树 2. 对一般二叉树而言, 求节点按某种序列的前趋节点变得容易的线索二叉树是和. a: 前序线索二叉树 ; b: 中序线索二叉树 ; c: 后序线索二叉树 3. 若一个有向图具有拓扑排序序列, 那么它的邻接矩阵必定为. a: 对称矩阵 ; b: 稀疏矩阵 ; c: 三角矩阵 ; d: 一般矩阵 4. 采用开址定址法解决冲突的哈希查找中, 发生集聚的原因主要是. a: 数据元素过多 ; b: 负载因子过大 ; c: 哈希函数选择不当 ; d: 解决冲突的算法选择不好. 5. 对 n 个关键字的文件进行内部排序, 在最好情况下, 最快的排序方法是 ; 相应的时间复杂度为 ; 该算法的稳定性是. A: 1 快速排序 ; 2 插入排序 ; 3 归并排序 ; 4 选择排序 2 B: 1 O( n ); 2 O(n); 3 O(n log2 n); 4 O(n ln n) C: 1 稳定 ; 2 不稳定 6. 在 K 路平衡归并的外部排序中, 如果内部选择算法采用堆排序, 则总的排序时间与 K. a: 有关 ; b: 无关 7. 哈夫曼编码树是一种. a: 最优查找树 ; b: 最优二叉树 ; c: 平衡二叉树 d: B+ 树二填空 ( 每空 2 分, 共 20 分 ) 1. 已知一颗二叉树的前序序列和中序序列分别为 : ABCDEFG ; CBDEAFG ; 它的后序序列是 ; 它的层次序列是. 2. 对 8 个节点的无向图, 若确保其为连通图, 至少需要条边. 若确保其为重连通图, 至少需条边. 3. 采用败者树进行 K 路归并时, 所需工作空间至少为个, 选取一个当前最小关键字需进行此比较. 4. 一颗含有 15 个关键字的 4 阶 B 树, 其非叶节点数最少不能少于个, 最多可以为个. 5. 高度为 5 的平衡二叉树 ; 其节点数最多可以有个 ; 最少可以是个. 三程序阅读 ( 共 20 分 ) 1. 对于正整数 n, 输出其和等于 n 且满足以下限制条件的所有正整数的和式, 组成和式的数字自左至右构成一个非递增的序列. 如 n = 4, 程序输出为 : 4 = 4 4 = = = = test 是实现该功能的 C 程序段, 请将未完成的部分补足, 使之完整. Test 函数为一递归函数, 参数 n 为被分解和式的数, k 为当前的分解深度. 算法思想是对 n 的所有合理的和式分解, 将分解出的数 ( 称为和

11 数 ) 存于数组 a[ ] 中. 当其中一个分解已不再需要进一步进行时, 即找到一个解, 将存于 a[ ] 中的一个完整和式的和数输出. 当还需要进一部分解时, 以要进一部分解的数及分解深度为参数, 递归调用 test 函数. #define MAXN 100 int a[maxn]; test(int n, int k) { int i,j; for( j= ; j >= 1 ; j ) (3 分 ) { a[k]=j; if ( ) (3 分 ) { printf("%d = %d",a[0],a[1]); for ( i = 2; i <= k; i ++ ) printf(" + %d",a[i]); printf("\n"); else test( ; k+1); (4 分 ) main() { test(4,1); 2. 设输入为整数数组 A[1..n], 其中 1 A[i] k (1 i n); 输出数组为 B[1..n]; C[1..k] 是临时工作空间 ; 阅读下属算法后, 回答下列问题 : proc Demo(A,B,k) { (1) for i:=1 to k do C[i]:=0; (2) for j:=1 to n do C[A[j]]:= C[A[j]]+1; (3) for i:=2 to k do C[i]:= C[i]+ C[i-1]; (4) for j:=n downto 1 do{ (5) B[C[A[j]]]:=A[j]; (6) C[A[j]]:=C[A[j]]-1; (a) 当标号 (2) 行的循环执行完后,C[i] ( 1 i n ) 的值有何意义? (3 分 ) (b) 当标号 (3) 行的循环执行完后,C[i] ( 1 i n ) 的值有何意义? (3 分 ) (c) 算法执行后,B 的内容有和特点? (d) 当 k=o(n) 时, 算法的时间复杂度是多少? 四程序设计 (20 分 ) 1. 已知一个 n n 的上三角矩阵 a 的上三角元素已按行主序连续存放在数组 b 中. 请设计一个函数 trans 将 b 中元素按列主序连续存放至数组 c 中. (15 分 ) 例 : 设 n=5;

12 1 0 a = b=(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15) c=(1,2,6,3,7,10,14,8,11,13,5,9,12,14,15) 2. 设二叉排序树的存储结构为 : type bitree = ^ node; node = record key:keytype; size:int; lchild,rchild:bitree end; 其中一个节点 x 的 size 域的值为以 x 为根的子树中节点的总数 ( 包括 x 本身 ). 例如下一颗二叉排序树 : 每个节点图示为若设该二叉排序树高为 h, 试写一个时间为 O(h) 的算法 Select(T:bitree;i:int), 要求该算法返回一个指向二叉排序树 T 的中根序列里第 i 个最小元素的指针. 若 i 值非法, 返回空指针. 例如对上图调用 Select(T,7) 时返回指向 key 为 16 的节点指针. 注意 : 不允许用中序遍历的方法完成. 需要利用节点的 Size 信息. (15 分 ) 3. 请写一个算法求无环连通图 T 的中心. ( 提示 : 首先将 T 中度为 1 的节点 ( 叶子 ) 删去得到子图 T1, 然后再删去 T 的叶子, 如此反复, 直到某个子图 Tk 为止.Tk 或者只含一个节点, 它即是 T 的唯一中心 ; 或者 Tk 含有两个节点, 它们都是 T 的中心 ). 若图有两个中心, 求出任意一个即可. 存储结构均采用邻接表. 在顶点表中可加一个度数域. data degree firstadj

14 中国科学技术大学一九九八年招收硕士学位研究生入学考试试题试题名称 : 程序设计要求 : 算法设计题目要求写注解, 否则扣分. 写出正确的设计思想和伪代码给分. 一填空 (15 分, 每空 1 分 ) 1.n 个顶点的无向图的邻接矩阵至少有非零元素 ;n 个顶点的有向图是强连通图至少有条边. 2. 折半查找的存储结构必须是, 并且其中存储的关键字必须 ; 查找成功与不成功的最大比较次数是.( 设关键字总数为 n) 3. 设广义表 L=( ( ),( (y), B), L), 则 L 的长度是, 深度是,head(L) 是, tail(l) 是. 4. 设高度为 h 的二叉树无度为 1 的结点, 则此类二叉树至少有个结点, 至多有个结点. 5. 若要将内存中建立的二叉树 ( 不一定是完全二叉树 ), 写到磁盘文件中, 则采用表示为宜. 6. 假定有 k 个关键字互为同义词, 若用线性探测法把这 k 个关键字存入散列表中, 至少要进行次探测. 7. 在基于关键字比较且时间为 O( nlog2 n) 的排序中, 若要求排序是稳定的, 则可选用排序 ; 若要求就地排序 ( 及辅助空间为 O(1)), 则可选用排序. 二请在下列各题中选择一个正确的答案 ( 每个选择 2 分, 共 20 分 ) 1. 在一颗 m 阶的 B 树中 : (1) 若在某结点中插入一个新关键字而引起结点的分裂, 则该结点中原有关键字的个数是 : (a) m 个 (b) m 1 个 (c) m 2 个 (2) 若在某结点中删除一个新关键字而导致结点的合并, 则该结点中原有关键字的个数是 : (a) m/2 1个 (b) m/2 个 (c) m/2 + 1个 2. 用 ISAM 组织文件适合于 (a) 磁带机 (b) 磁盘 3. 是否存在这样的二叉树, 对它采用任何次序的遍历, 其遍历产生的节点序列相同? (a) 存在 (b) 不存在 4. 若一个有向图的邻接矩阵中, 主对角线以下的元素均为零, 则该图的拓扑有序序列 : (a) 不存在 (b) 存在 5. 对外部排序的 k 路平衡归并, 采用败者树时, 归并效率与 k (a) 有关 (b) 无关 6. 设二叉排序树中关键字由 1 至 1000 的整数构成, 现要检索关键字为 363 的结点, 下述关键字序列哪一个不可能是二叉排序树上搜索到的序列? (a) 2, 252, 401, 398, 330, 344, 397, 363 (b) 924, 220, 911, 244, 898, 258, 362, 363 (c) 952, 202, 911, 240, 912, 245, 363 (d) 2, 399, 387, 219, 266, 382, 381, 278, 已知待排序的 n 个元素可分为 n/k 个组, 每个组包含 k 个元素, 且任一组内的各元素均分别大于前一组的所有元素并小于后一组内的所有元素, 若采用基于比较的排序, 其时间下界应为 : (a) O(nlog2 n) (b) O(nlog2 k) (c) O(klog2 n) (d) O(klog2 k) 8. 下述二叉树中, 哪一种满足性质 : 从任一结点出发到根的路径上所经过的结点序列按其关键字有序 : (a) 二叉排序树 (b) 哈夫曼树 (c) AVL 树 (d) 堆

15 9. 将两个各有 n 个元素的有序表归并成一个有序表, 其最多的比较次数是 : (a) 2n (b) n (c) 2n 1 三 ( 共 15 分 )Fibonacci 树是一种特殊的二叉树, 下面给出构造该树的一种算法 : procedure FibonacciTree(d:integer ; Var T:binarytree) { //d 是 Fibonacci 树的深度 if d=0 then T := nil else { new(t); if d=1 then { T^.leftptr:=nil; T^.rightptr:=nil else { // d>=2 FibonacciTree(d 2, T^.leftptr); FibonacciTree(d 1, T^.rightptr); 1. 画出深度为 4 的 Fibonacci 树 ( 即用 d=4 调用上述算法的结果 ) (7 分 ) 2. 从你画的树中分析深度 d 的 Fibonacci 树中结点总数和 Fibonacci 数的关系.Fibonacci 数定义如下 : F 0 = 1, F 1 = 1 F n = n-1 F + F n-2 n>1 3. 你所画出的 Fibonacci 树是否为平衡二叉树? 若是, 它是否为同样深度的平衡二叉树中节点数目最少的一种? (4 分 ) 四证明若二叉排序数中的一个结点存在两个孩子, 则它的中序后继节点没有左孩子, 则它的中序前趋节点没有右孩子. (10 分 ) 五 ( 共 25 分 ) 设数组 A[1..n] 含有 n 个互不相同的数, 若 i<j 且 A[i] > A[j], 则偶对 (i,j) 称为 A 的一个逆. 1. 列出数组 [3, 4, 9, 7, 1] 的五个逆 ; (2 分 ) 2. 元素取自集合 {1, 2, 3, n 的所有数组中, 哪一个数组具有最多的逆, 其中数是多少? (3 分 ) 3. 插入排序的运行时间和数组中逆的数目有何关系? (3 分 ) 4. 写一个算法将两个有序段 r[low..mid] 和 r[mid + 1..high] 归并成一个有序段, 并要求在归并的同时求出归并前 r[low..high] 中逆的总数. (15 分 ) 5. 利用 (4) 中的归并算法来对 r[1..n] 进行归并排序, 并同时求出原数组 r[1..n] 中逆的总数, 其时间复杂度是多少? (2 分 ) 六 ( 共 15 分 ) 一个有向图 G=(V,E) 的平方图满足下述性质 : (u,w) 当且仅当存在某个顶点 v V, 使得 (u,v) E 且 (v,w) E. 写一个算法从给定的 G 求出, G 和可分别用两个邻接表表示.

台湾项目书

台湾项目书两岸医学人文交流项目 Cross-Taiwan Straits Medical Humanity Exchange Program 2016 年寒假台湾交流团步入大学课堂学习深度认识台湾医疗两岸医学生互动交流项目简介台湾的医疗服务水平在亚洲居于领先地位 2012 年, 全球