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

2、在顺序线性表下，根据位置来进行元素的插入和删除，主要的时间花费在 移动后续元素位置 ；在单链表下进行元素的插入和删除，主要时间花费在 找到目标元素位置 。

3、 具有n 个顶点的无向图，至少要有 n-1 条边，才能保证该图是连通图。

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

5、在哈希查找中，评判一个哈希函数优劣的两个主要指标是： 散列分布均匀性和冲突解决方法。

6、由三个结点构成的二叉树，共有 5 种不同的形状。

7、高度为h (h ≥ 1)的完全二叉树的结点数在2n-1和 2n -1之间。

(设只有1个根结点的二叉树高度为1)8、对于有n (n ≥ 1)个顶点的连通图，其生成树有 n-1 条无向边。

n(n ≥ 1)个顶点的有向完全图有 n(n-1) 条有向边。

9、图的深度优先搜索遍历类似于树的 先序 遍历。

图的广度优先搜索遍历需要用到的辅助数据结构是 队列 。

10、以关键字比较为基础的排序方法所能达到的最好时间复杂度为 n 。

排序过程中总的关键字比较次数与记录的初始排列顺序无关的排序方法有 选择排序 。

稳定的算法有 冒泡排序、插入排序 。

二、应用题1、简述拓扑排序的实际意义，并写出下图的1个深度优先拓扑序列和1个广度优先拓扑序列。

拓扑排序的实际意义:如果按照拓扑排序的顶点次序，在开始每一项活动时，能够保证它的所有前驱活动都已经完成，从而使整个工程顺序进行，不会出现冲突情况。

DFS:acfhdgbeBFS:acdfhbeg2、已知一个无向连通图如图所示： 134ab d ec f 222g h212111) 请用Prim 算法构造该无向图的最小生成树，给出详细求解过程。

2) 分别用邻接矩阵和邻接表这两种存储结构表示该无向图。

3) 请写出一个合理的从顶点a 出发得到的DFS 序列(假设邻接表中边表按照递增序)。

4) 请写出一个合理的从顶点a 出发得到的BFS 序列(假设邻接表中边表按照递增序)。

3、简述插入排序的基本思想，并对以下关键字集合，{72，73，71，23，94，16，05，68}进行插入排序，计算总的比较次数。

1:72 73 71 23 94 16 05 682:71 72 73 23 94 16 05 683:23 71 72 73 94 16 05 684:23 71 72 73 94 16 05 685:16 23 71 72 73 94 05 686:05 16 23 71 72 73 94 687:05 16 23 68 71 72 73 944、已知如下所示长度为12的表(Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)，试按表中元素的字符串大小顺序依次插入一棵初始为空的二叉查找树。

二叉查找树是如下定义的：(1) 左子树不空，则左子树上的所有结点的值均小于根结点的值(2) 右子树不空，则右子树上的所有结点的值均大于根结点的值在二叉查找树中删除一个给定的结点p有三种情况(1) 结点p无左右子树，则直接删除该结点，修改父节点相应指针(2) 结点p有左子树（右子树），则把p的左子树（右子树）接到p的父节点上(3) 左右子树同时存在，则有三种处理方式a. 找到结点p的中序直接前驱结点s，把结点s的数据转移到结点p，然后删除结点s，由于结点s为p的左子树中最右的结点，因而s无右子树，删除结点s可以归结到情况(2)。

严蔚敏数据结构P230-231就是该处理方式。

b. 找到结点p的中序直接后继结点s，把结点s的数据转移到结点p，然后删除结点s，由于结点s为p的右子树总最左的结点，因而s无左子树，删除结点s可以归结到情况(2)。

算法导论第2版P156-157该是该处理方式。

c. 找到p的中序直接前驱s，将p的左子树接到父节点上，将p的右子树接到s的右子树上，然后删除结点p。

（1）画出插入完成之后的二叉查找树；（2） 1+2*2+3*3+4*3+5*2+6*1）/12=42/12=3.5（3）画出删除Jan后的二叉查找树。

三、算法设计题1、设计一个递归算法，判断二叉树中是否含有度为1的结点。

template<class Entry>bool Binary_tree<entry>::recurisive_has_degree1(Binary_node<Entry>*sub_root){if (sub_root==NULL)return false;if (sub_root->left==NULL && sub_root->right==NULL)return false;if (sub_root->left!=NULL && sub_root->right!=NULL)returnrecursive_has_degree1(sub_root->left)||recursive_has_degree1(sub_root->right);elsereturn true;}2、已知线性表以带头结点的单链表作为存储结构。

试编写算法删除原表中所有值大于min且小于max的元素（若表中存在这样的元素），并将被删结点形成一个新链表返回的算法。

template<class List_entry>nod<List_entry> *List<List_entry>::deletemintomax(List_entry &min, List_entry& max){Node<List_entry>*p,*q;Node<List_entry>*New_head,*r;New_head=new Node<List_entry>();r=new_head;p = head;while(p&&(p->next){if(p->next->entry>min&&p->next->next->entry<max){q=p->next;;p->next=q->next;r->next=q; r=q;}else{p=p->next}}r->next=null;return new_head;}单链表int Stack :: size() const{Node *temp = top_node;int count = 0;while (temp != NULL) {temp = temp ->next;count++;}return count;}int Stack :: size() const{return recursive_size(top_node);}int Stack :: recursive_size ( Node *L ) const{if (L==NULL)return 0;elsereturn 1+recursive_size(L->next);}二叉树二叉链表template <class Entry>int Binary_tree<Entry> :: recursive_size2(Binary_node<Entry> *sub_root) const {int l,r;if(sub_root ==NULL) return 0;l= recursive_size2 (sub_root->left);r= recursive_size2 (sub_root->right);if (sub_root->left!=NULL&& sub_root-> right!=NULL)return l+r+1;elsereturn l+r;}2、template <class Entry>Binary_node<Entry>* Binary_tree<Entry> :: findbrother(Binary_node<Entry> *sub_root,Binary_node<Entry> *p){if (sub_root ==NULL || p==NULL)return NULL;if (sub_root ==p)return NULL;if (sub_root->left==p)return sub_root->right;if (sub_root->right==p)return sub_root->left;Binary_node<Entry> *q=findbrother(sub_root->left, p);return findbrother(sub_root->right,p);}}template <class Entry>bool Binary_tree<Entry> :: ismorphic(Binary_node<Entry> * T1, Binary_node<Entry> *T2){if (T1==NULL&&T2==NULL)return true;if (T1!=NULL&&T2!=NULL)if (ismorphic (T1->left,T2->left))if (ismorphic (T1->right,T2->right))return true;return false;}排序作业一设待排序数据的关键字为（2667359-643821054）（1）画出直接插入排序数据表的变化过程，并计算出总的关键字比较次数和记录的移动次数（记录的赋值即认为一次移动)。

（2）以首元素为枢轴元素进行快速排序，画出排序过程的递归调用树，并计算出总的比较次数。

插入排序过程趟数26 67 35 9 -6 43 82 10 54 插入比较次数移动次数1 26 67 67 1 02 26 67 35 35 2 33 26 35 67 9 9 3 54 9 26 35 67 -6 -6 4 65 -6 9 26 35 67 43 43 2 36 -6 9 26 35 43 67 82 82 1 07 -6 9 26 35 43 67 82 10 10 6 78 -6 9 10 26 35 43 67 82 54 54 3 4结果-6 9 10 26 35 43 54 67 82 22总比较次数=8+2+1+4+3+2+1=21二、画出对序列（512,275,908,677,503,765,612,897,170 ）进行归并排序的递归树，并计算出总的比较次数。