1、在任何需要数据反转的问题里，首先应考虑用来保存数据。

2、在顺序线性表下，根据位置position来进行元素的插入和删除，主要的时间花费在；在单链表下进行元素的插入和删除，主要时间花费在。

3、一个10×10的矩阵，如果以行为主序存入内存，则其容量为。

设a11是第一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为。

4、在线性表改进的单链表实现方法中，我们定义了一个current指针指向最近访问过的结点，定义的方法是：mutable Node<List_entry> *current；请解释这里mutable的作用：。

5、用二分查找方法进行查找，要求数据文件应为，且限于存储结构。

6、在哈希查找中，评判一个哈希函数优劣的两个主要指标是：______________ 和。

7、快速排序的最坏时间复杂度为；平均时间复杂度为。

8、图的遍历算法有两种：和。

9、由三个结点构成的二叉树，共有种不同的结构。

二、应用题(40分)1、设有n个无序记录的顺序表（每一条记录由一个对应的关键字），简述利用二叉查找树对此记录表进行树排序的方法。

（10分）2、队列采用顺序结构实现（linear implementation）时，随着元素的出队，数组开始处的空间不能再次利用。

如何解决这个问题？（10分）（10分）KG4、简述堆排序的基本方法，并对键值集合，{72，73，71，23，94，16，05，68}对应的二叉树建大顶堆。

（10分）三、算法设计题（30分）1、设计一个递归算法，计算二叉树叶结点数目。

（10分）template <class Entry>int Binary_tree<Entry> :: recursive_leafcount(Binary_node<Entry> *sub_root) const 2、以顺序存储结构实现两个有序表A、B的合并，合并结果放在A中。

不可采用另外的辅助数组空间。

（10分）Error_code connect(List &a , const List &b)3、已知线性表的元素按递增顺序排列，并以带头结点的单链表作为存储结构。

试编写算法删除表中所有值大于min且小于max的元素（若表中存在这样的元素）的算法。

（10分）template <class List_entry>Error_code List<List_entry> :: delete_min_max (List_entry min, List_entry max ) 1、下面程序段中带下划线的语句的执行次数的数量级是。

i=1;while (i<n)for (j=1 ;j<=n; j++){x=x+1;i=i*2;}2、线性结构是一种一对一的结构，元素之间的关系是一对一的；树形结构是一种的结构。

3、若某个线性表的最常用的操作是存取第i个元素及其前驱的值，则采用_______________存储方式比较好。

4、在双向循环链表中，设指针p指向待删除的结点，则删除结点*p需执行的语句为：。

5、设有一个空栈，栈顶指针为1000H，现有输入序列为1，2，3，4，5，经过push、push、pop、push、pop、push、push操作，输出的序列为。

6、对一棵完全2-树的每个结点从1开始进行编号，编号的方法是从根开始，从左到右，从上到下。

则编号为k的结点，其左孩子如果存在则编号为，右孩子如果存在编号为。

7、按遍历二叉排序树，可以得到按值递增的关键字序列，在图中所示的二叉树中，查找关键字85的过程中，需与85进行比较的关键字序列为。

8、哈希查找中解决冲突的方法主要有：、。

9、判断一个有向图是否存在回路，可以采用方法。

10、二维表格在计算中的存储表示的实质即是把二维的表格一维化，通常采用的方法有：和方式。

11、对记录进行顺序查找时，有时我们可以先把待查记录插入到查找表的尾部，然后再从头到尾进行查找，这种做法称为采用监视哨的方法。

该方法的优点是：。

二、应用题（40分）1、已知一组元素为（45，25，80，60，18，30，12，40，70），试画出按元素输入排列顺序而生成的二叉排序树，求出等概率情况下查找成功与不成功时的平均查找长度。

（10分）2、已知一个图G=(V,E)，其中：（10分）V={a,b,c,d,e,f}E={<a,b>,<a,d>,<a,e>,<d,e><e,b>,<c,b>,<c,e>,<c,f>,<f,e>}(1)请画出该图，并写出邻接矩阵。

(2)根据邻接矩阵，分别给出从顶点a出发的深度优先和优先遍历序列。

(3)画出由此得到的深度优先和广度优先生成树。

3、已知一棵二叉树的中序序列为：BAFDJGCKHLEIM，后序序列为：BFJGDKLHMIECA。

请完成：（10分）（1）构造这棵二叉树。

（2）将这棵二叉树转化成树或森林。

4、一项工程P由P1、P2、P3…P6六项子工程组成，这些工程之间有下列关系，P1<P2,P3<P6,P4<P3,P2<P6,P4<P5,P1<P3,P5<P6，符号“<”表示“先于”关系，例如P2<P6，表示P2完成后P6才能开始。

请给出工程P的三种可能的施工顺序。

（10分）二、算法设计题(30分)1、单链表中存放着n个字符，试设计算法判断该字符串是否中心对称，如xyzzyx即为中心对称的字符串。

(可利用栈作为辅助量)（10分）bool List<char> :: is_ symmetrical ()2、以二叉链表作为存储结构写出求二叉树结点总数的递归算法。

（10分）template <class Entry>int Binary_tree<Entry> :: recursive_nodecount(Binary_node<Entry> *sub_root) const 3、将循环队列类定义为含有一个数组entry[0..maxqueue-1]以存放循环队列中的元素，还含有两个变量rear和len分别指示循环队列中队尾元素的位置和内含元素的个数。

请设计此队列类和相应的出队的算法。

（10分）1、排序算法的性能下限用时间复杂度表示为。

2、在有序表A[1..20]中，采用二分查找算法查找元素值等于A[12]的元素，所比较过的元素的下标依次为：。

4、在有n个顶点的有向图中，每个顶点的度最大可达。

5、在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动个元素。

6、在拓扑排序中，拓扑排序的第一个顶点必定是_________________的顶点。

7、常用图的存储结构有、和。

8、无向图的生成树是指含有图中所有的n个顶点的子图。

9、树的后序序列与对应二叉树的序列相同，任何一棵二叉树是否都能转换成树？。

10、树与二叉树转换的依据是：。

11、限定在线性表的一端进行插入和删除的数据结构是_____________________，满足先进先出原则的数据结构是。

12、设哈希函数H(k)=k mod 7,哈希表的地址空间为0～6，对关键字序列｛32，13，49，55，22，29｝，按线性探测法解决冲突（探测地址按线性递增），产生的哈希表中地址为3处的关键字为：。

二、应用题1、完成下列与队列有关的问题。

（10分）（1）写出队列的类定义。

（2）循环队列不能很好地判断队空和队满，用图示的方法进行举例说明。

2、对于下图所示的带权图，利用Dijkstra算法求出从源点v1到其余各顶点的最短路径及其长度，并写出在算法执行过程中，每求得一条最短路径后，当前从源点v1到其余各顶点的最短路径及其长度的变化。

（10分）3、设待排序文件的关键字为（512,275,908,677,503,765,612,897,154,170）以第一元素为分界元素进行快速排序（按关键字值递增顺序），画出一趟排序过程的示意图，并给出一趟扫描后的结果。

（8分）4、画出对长度为10的有序表进行折半查找的判定树，并求其等概率情况下查找成功与不成功时的平均查找长度。

（10分）三、算法设计题1、有一个带头结点的单链表，写出在其值为x的结点之后插入m个结点的算法。

（10分）Error_code insert_m(const List_entry &x, List a_list, int m)2、设计在二叉排序树下根据关键字进行查找的递归算法。

（10分）template <class Record>Binary_node<Record> * Search_tree<Record>::search_for_node(Binary_node<Record> *subroot,const record &target)const3、用字符串表示一个表达式，利用栈类完成括号匹配算法，允许出现的括号有圆括号和中括号两类，匹配返回true，否则返回false。

bool is_matched(char *s)1、下列算法的时间复杂度是。

x=n;y=0;while ((x>=（y+1）*（y+1）))y=y+1;4、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用______存储结构。

迪杰斯特拉提出了一个按次序产生最短路径的算法。

9、在情况下，链队列的出队操作需要修改尾指针。

2、有向图的称为有向图的强连通图。

5、中序遍历一个二叉排序树所得到的结点访问序列为序列。

6、以关键字序列为{k0,k1,k2,…kn-1}建立一个堆。

首先将该序列中的关键字依次排列到一棵完全二叉树上，然后从最后一个非叶结点开始到根结点为止，依次插入结点至已经完成的部分堆中。

此非叶结点的编号个元素开始筛选。

7、假设二叉树根结点的层次为0，则二叉树的第k层上的结点总数最多为个。

8、假设一个12阶的下三角矩阵A按行优先顺序压缩存储在一维数组B[0..MAX-1]中，则B的容量MAX至少为。

如A矩阵的第一个元素为a00,则非零元素a98在B中的存储位置k= 。

10、n个顶点的无向连通图至少含有条边，无向非连通图的连通分量是指：。

二、应用题1、判别以下说法是否正确，并简单说明原因。

（1）队列是一种先进后出的数据结构。

（2）队列的顺序存储方案通常采用循环队列的方法。

（3）队列的顺序存储结构比链式存储结构更优越。