第十一章 内排序 11.1排序的基本概念 11.2插入排序 11.3交换排序 11.4选择排序 11.5归并排序 11.6基数排序 11.7各种内排序方法的比较和选择

计算机是用来处理数据的,而且它是 用来处理大批量的数据。这些数据决不是 杂乱无章的,而是有着某种内在联系的 只有分清数据的内在联系,合理地组织数 据,才能对其进行有效管理。如何合理组 织数据,高效率地处理数据,正是本门课 需要解决的问题

栈与队列是两种特殊的线性表。即:在一般线性表 的操作时,插入或删除结点的位置是任意的,在表的 中间或两端都可以进行插入或删除操作,这样,每进 行一个结点的插入或删除时必须先要定位(确定其被 执行操作结点的地址),因此实现操作比较费时。 而作为限定性的线性表一栈和队列,其主要特点 是限定了操作位置,即不能随意在表的任意结点上进 行插入或删除操作而只能在表的一端或两端进行操作 ,这样节省了定位时间并有特定规则

树形结构是一种非线性结 构,其特点是:树中有且仅有 个无前驱的结点,其余每个 结点最多只有一个前驱,但可 以有多个后继

第三章链表 一、单链表(Singly Linked List） 二、循环链表(Circular List） 三、多项式及其相加 四、双向链表(Doubly Linked List） 五、稀疏矩阵

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

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

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

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

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