一、选择题 1.d2.d3.d4.b5.b6.b7.c,8.a9.c10.c,d,f11.1d,c11.2a,d,f

顺序查找是一种最基本和最简单的查找方法。它 的思路是,从表中的第一个元素开始,将给定 的值与表中逐个元素的关键字进行比较,直到 两者相符,查到所要找的元素为止。否则就是 表中没有要找的元素,查找不成功。对于表中 记录的关键字是无序的表,只能采用这种方法 。描述顺序查找的算法见框图8-1其中n是表r 的长度,k是要查的元素的关键字,i查到的元 素的序号

第一节树的类型定义 A为“根” T1、T2和T3都是一棵树,称为A的子树。 称根和子树根之间的连线为“分支” 结点分支的个数定义为“结点的度”,如结点B 的度为2,D的度为3

9-1 什么是内排序? 什么是外排序? 什么排序方法是稳定的? 什么排序方法是不稳定的? 【解答】 9-2 设待排序的关键码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试分别写出使用以下排序方法每趟排序后的结果。并说明做了多少次关键码比较

◼ 分治算法的原理 ◼ 大整数乘法 ◼ 矩阵乘法 ◼ 求第k小元素问题 ◼ 寻找最近点对 ◼ 快速傅立叶变换 ◼ 寻找凸包

8-1 画出 1 个顶点、2 个顶点、3 个顶点、4 个顶点和 5 个顶点的无向完全图。试证明在 n 个顶点的无向完全图中，边的条数为 n(n-1)/2。 8-2 右边的有向图是强连通的吗？请列出所有的简单路径。 8-3 给出右图的邻接矩阵、邻接表和邻接多重表表示

1999年试题答案: 1. void MergeList_(LinkList &La, LinkList &Lb, LinkList &Lc) /已知单链线性表La和Lb的元素按值非递减排列 /归并La和Lb得到新的单链线性表Lc,Lc的元素也按值非递减排列

6-1 写出用广义表表示法表示的树的类声明，并给出如下成员函数的实现： (1) operator >> ( ) 接收用广义表表示的树作为输入，建立广义表的存储表示； (2) 复制构造函数 用另一棵表示为广义表的树初始化一棵树； (3) operator == ( ) 测试用广义表表示的两棵树是否相等； (4) operator << ( ) 用广义表的形式输出一棵树； (5) 析构函数 清除一棵用广义表表示的树

5-1 已知 A[n]为整数数组，试写出实现下列运算的递归算法： (1) 求数组 A 中的最大整数。 (2) 求 n 个整数的和。 (3) 求 n 个整数的平均值

4-2 改写顺序栈的进栈成员函数 Push (x )，要求当栈满时执行一个 stackFull ( )操作进行栈满处理。其功能 是：动态创建一个比原来的栈数组大二倍的新数组，代替原来的栈数组，原来栈数组中的元素占据新数组 的前 MaxSize 位置