6．循环队列采用数组data[1．．n]来存储元素的值，并用front和rear分别作为其头尾指针。为区分队列的满和

空，约定：队中能够存放的元素个数最大为（n-l），也即至少有一个元素空间不用，则在任意时刻，至少可以知道一个空的元素的下标是（front） ；入队时，可用语句（rear=rear+1%n）求出新元素在数组data中的下标。 7．在含有n个结点的顺序存储的线性表中，在任意一个结点前插入一个结点所需要移动结点的平均次数为（ n/2 ）。在含有n个结点的顺序存储的线性表中，任意删除一个结点所需要移动结点的平均次数为（ n-1/2 ）。对一个线性表分别进行遍历和逆置运算，其最好的时间复杂度量级均为（O(n)）。

8．数组A[l..10，1..10]的每个元素占5个单元，将其按列优先次序存储在起始地址为1000的连续的内存单元中， 则元素A[5，6]的地址为（1270）。

9．两个串相等的充要条件是，两个串的长度相等，且其所对应各个位置的（字符）也相等。稀疏矩阵一般的压缩 存储方法有两种，它们是（三元组顺序表）和十字链表。

10．若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数是（69）。已知二叉树有 50个叶子结点，则该二叉树的度为2的结点数是（51 ），该二叉树的总结点数至少是（99）。一棵二叉树L的高 度为h，所有结点的度或为0，或为2，则这棵二叉树最少的结点数为( 2h-1 )。 11．树t的存储结构为二叉链表bt，树t中的一个叶子结点在bt中满足条件（bt->lchild<>null&& bt->rchild<>null;）。 树t中的非叶子结点在bt中满足条件是（bt->lchild<>null|| bt->rchild<>null）。在有n个结点的二又链表中，值 为非空的链域的个数为（ n-1 ）个。在有n个叶子结点的哈夫曼树中，总结点数是（2n-1）。在树形结构中，根

结点数只有（1个），其余每个结点有且仅有一个元素（前驱）结点。

12．具有10个顶点的无向图，边的总数最多为(45)。有向图G用邻接矩阵A存储，则顶点i的入度等于A中（ 第

2

i列1的元素之和 ）。对于含n个顶点和e条边的图，采用邻接矩阵表示的空间复杂度为（ O(n) ）。连通图 是指图中任意两个顶点之间（都连通的无向图 ）。一个有n个顶点的无向连通图，它所包含的连通分量个数最 多为( 1 )个。任何一个无向连通图的最小生成树（有一棵或多棵）。若含有n个顶点的图形成一个环，则它有 （n）棵生成树。具有n个顶点的强连通有向图G，边的总数至少有（n）条。 13．拓扑排序只能用于（有向无环图）。求图的最小生成树有两种算法，（prim（普里姆））算法适合于求稠密图的

最小生成树，（kruskal（克鲁斯卡尔））算法适合于求稀疏图的最小生成树。设图G用邻接表存储，则拓扑排序的时间复杂度为(O(n+e) )。

14．在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表的长度有关，而且与每一块中

的元素（长度）有关。在有序表A[l..20]中，采用二分查找算法查找元素值等于A[12]的元素，所比较过的元 素的下标依次为（10,15,12 ）。二分查找法要求查找表中各元素的关键字的值得排列必须是（递增或递减或有

序 ）。若一个待散列存储的线性表长度为n，用于散列的散列表长度为m，则m应（小于等于）n，装填因子公式为n/m。散列表的平均查找长度(与处理冲突方法有关而与表的长度有关 )。在平衡二叉树上删除一个结点后可以通过旋转使其平衡，最坏情况下需旋转（O(log2n) ）次。

15．分别采用堆排序、快速排序、插入排序和归并排序算法对初始状态为递增序列的表按递增顺序排序，最省时间

的是（插入排序）算法，最费时问的是（快速排序）算法。直接选择排序算法所执行的元素交换次数最多为（n-1）次，最好情况下所作的交换元素的次数为（0）次。在堆排序，希尔排序，快速排序，归并排序算法中，占用辅助空间最多的是 (归并排序)。从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为( 插入排序 )。对于关键字序列(12，13，11，18，60，15，7，18，25，100)，用筛选法建堆，则开始结点的键值必须为（ 60 ）。

16．贪心算法的基本思想是，逐步构造最优解，每步都按照一定的标准，称为（贪心）准则，做出决策。0/1背包

问题的三种贪婪准则中，相对较优的是(价值密度) 贪婪准则。与分治法不同的是，动态规划是“（自底向上）” 逐级求解子问题。在回溯法和分支限界法的算法分析中，有两种状态空间树，（ 子集树 ）和排列树。分枝定 界的搜索策略与广度优先类似，而回溯方法则采用(深度优先)搜索策略。

三、应用题

1．对于单链表、单循环链表和双向链表，若仅仅知道一个指向链表中某结点的指针p，能否将p所指的结点的数据

元素与它的直接前趋（假设存在）交换？若不可以，说明理由；若可以，写出主要算法。

5

（1）单链表不能，单循环链表和双向链表可以。

（2）单循环链表 q=p;while(q－>next!=p) q=q－>next;temp=p－>data; p－>data=q－>data;q－>data=temp; （3）双向链表：q=p－>prior; temp=q－>data; q－>data=p－>data;p－>data=temp; 2．内存中一片连续空间（不妨设地址从1到m），提供给两个栈S1和S2使用，怎样分配这部分存储空间，使得对

任意一个栈，仅当这部分全满时才发生上溢。(为了尽量利用空间，减少溢出的可能，可采用栈顶相向，栈底分设两端的存储方式，这样，对任何一个栈，仅当整个空间全满时才会发生上溢。) 3．有字符串次序为3*-y-a/y^2，利用栈，给出将次序改为3y-*ay2^/-的操作步骤。（可用X代表扫描改字符串过 程中顺序取一个字符进栈的操作，用S代表从栈中取出一个字符加入到新字符串尾的出栈操作。例如，ABC变为 BCA的操作步骤为XXSXSS）。（操作步骤为：XSXXXSSSXXSXXSXXSSSS ）

4．有一棵n个结点的树，其中所有分支结点的度均为k，求该树中叶子结点的个数。 （1）设no为叶子结点数，nk为度为k的结点数，n为结点总数。 （2）依题意：n=no+nk 1) n= knk+1 2) 综合1) 和2)得： no=n-(n-1)/k

5．有一个二叉树按顺序存储结构存放在一维数组中，如下图所示：

A C B E D

试求：（1）该树的先序遍历序列。

（2）画出该树的先序线索树。

（1）先序序列 A-C-E-B-D （2）先序线索树

A C B E D 6. 已知一棵二叉树的先序序列和中序序列分别为：abdgicefhj及bgidaecfjh，画出该的二叉树的不带头结点的后序

线索二叉树。

a b c

i

j d g e f h

7．按顺序输入下列顶点对: (1,2)、(1,6)、(2,6)、(1,4)、(6,4)、(1,3)、(3,4)、(6,5)、(4,5)、(1,5)、(3,5)，

6

（1）画出相应的邻接表。

（2）写出在邻接表上，从顶点3开始（表下标从0开始）的DFS序列。

（1）邻接表

4 2 3 5 1 ∧ 0 V1 V2 1 5 0 ∧ 2 V3 4 3 0 ∧ 3 V4 4 2 5 0 ∧ 4 V5 2 0 3 5 ∧

5 V6 4 3 1 0 ∧

（2）DFS序列 2-4-0-3-5-1

8. 假设通信电文使用的字符集为{a,b,c,d,e,f,g}，字符的哈夫曼编码依次为：0110，10，110，111，00，0111

和010。

（1）画出此哈夫曼树。

（2）若这些字符在电文中出现的频度分别为3、35、13、15、20、5、9，求哈夫曼树的带权路径长度。 （1）哈夫曼树

0 1 （２）带权路径长度

WPL=4*0.03+2*0.35+3*0.13+3*0.15+2*0.20+4*0.05+3*0.09=2.53

9. 已知有一个10个顶点的无向连通图，顶点编号为1至10，其边的关系集合表示为{（1，2）（1，3），（1，8），

（2，4），（3，9），（3，10），（5，7），（6，7），（7，8），（8，9）}，试求：画出该连通图及以顶点1为根的深度优先生成树。

（1）连通图 （2）深度优先生成树 1 1 2 3 0 1 0 1 e 0 1 b 0 1 g 0 1 c d a f 2 3 8 4 10 9 7

10．一个AOE网络如图所示。ve[i]和vl[i]分别表示每个事件（顶点）的最早开始时间和最迟开始时间，e[j]和l[j] 分别表示每个活动（边）的最早开始时间和最迟开始时间。试求：求这个工程的最早结束时间和关键路径。

（1）最早结束时间为43 （2）关键路径: <1,3><3,2><2,5><5,6> 11．写出对关键字序列

{503,087,512,061,908,124,897,275,653,426}建立一棵平衡二叉排序树的过程，并写出调整平衡时的旋转类型。

503 503 087 512 RL 087 897 061 124 908 061 124 512 908 897 503 503 087 897 RR 087 897 061 124 512 908 061 275 512 908 275 653 124 426 653 426 12．设二叉排序树中关键字由1至1000的整数组成，现要查找关键字为363的结点，下述关键字序列哪一个不可

能是在二叉排序树中查到的序列？说明原因。 ⑴ 51,250,501,390,320,340,382,363; ⑵ 24,877,125,342,501,623,421,363; （1）⑴ 是；⑵不是。

（2）因为查询序列 24,877,125,342,501,623，再查421时，其623左、右两个区间[502-622]623[624-876]， 都不存在，查找失败。

13．对下面的关键字集（30，15，21，40，25，26，36，37），若查找表的装填因子为0.8，采用线性探测再散列解决冲突。试求：

（1）设计哈希函数；（2）画出哈希表。

（1）表长: m=n/α=8/0.8 =10 哈希函数： H(key)=key%7

（2） 哈希表

0 1 2 3 4 5 6 7 8 9

8