第二章线性表 线性结构特点:在数据元素的非空有限集中 一、存在唯一的一个被称作第一个”的数据元素 二、存在唯一的一个被称作“最后一个”的数据元素 三、除第一个外,集合中的每个数据元素均只有一个前驱 四、除最后一个外集合中的勺每个数据元素均只有一个后继

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

4-2改写顺序栈的进栈成员函数push(x),要求当栈满时执行一个 stackFull()操作进行栈满处理。其功能 是:动态创建一个比原来的栈数组大二倍的新数组,代替原来的栈数组,原来栈数组中的元素占据新数组 的前 MaxSize位置。 【解答】 templatepush( const Type&item)

2-1设n个人围坐在一个圆桌周围,现在从第s个人开始报数,数到第m个人,让他出局;然后从出局的下一个人重新开始报数,数到第m个人,再让他出局,…,如此反复直到所有的人全部出局为止。下面要解决的 Josephus问题是:对于任意给定的n,s和m,求出这n个人的出局序列。请以n=9,s=1,m=5为例,人工模拟 Josephus的求解过程以求得问题的解。 【解答】 出局人的顺序为5,1,7,4,3,6,9,2,8

1-4.什么是抽象数据类型?试用C++的类声明定义“复数”的抽象数据类型。要求 (1)在复数内部用浮点数定义它的实部和虚部。 (2)实现3个构造函数:缺省的构造函数没有参数;第二个构造函数将双精度浮点数赋给复数的实部,虚部置为0;第三个构造函数将两个双精度浮点数分别赋给复数的实部和虚部

一、插入排序 二、交换排序 三、选择排序 四、归并排序 五、基数排序 六、外排序

10-1什么是静态索引结构?什么是动态索引结构?它们各有哪些优缺点? 【解答】 静态索引结构指这种索引结构在初始创建数据装入时就已经定型,而且在整个系 运行期间,树的结构不发生变化,只是数据在更新。动态索引结构是指在整个系统运行期 间,树的结构随数据的增删及时调整,以保持最佳的搜索效率。静态索引结构的优点是结 构定型,建立方法简单,存取方便;缺点是不利于更新,插入或删除时效率低

8-1画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。试证 明在n个顶点的无向完全图中,边的条数为n(n-1)/2。 8-2右边的有向图是强连通的吗?请列出所有的简单路径

第七章集合与搜索 一、集合及其表示 二、等价类与并查集 三、静态搜索表 四、二叉搜索树 五、最优二叉搜索树 六、AVL树 七、小结

第五章递归 一、递归(Recurve)的概念 二、迷宫Maze问题 三、递归过程与递归工作栈 四、广义表(General Lists)