与图的边数无关。Yxm:正确
广度遍历生成树描述了从起点到各顶点的最短路径。Yxm：错误 连通图上各边权值均不相同，则该图的最小生成树是唯一的。Yxm:正确 一个有向图的邻接表和逆邻接表中结点的个数可能不等。Yxm：错误
4、如下所示的是一个带权无向图，带框的数字表示相应边的权，不带框的数字表示顶点号。用prime 算法求最小生成树时，如果已确定的边为(5,4),则，下一条边应在哪几条边中选取？选取哪一条？
1 7 2 5 3 8 6 4 4 5 1 3 5 2 4 3
yxh：（4,6）
5、如何衡量hash函数的优劣？简要叙述hash表技术中的冲突概念，并指出三种解决冲突的方法。
评价哈希函数优劣的因素有：能否将关键字均匀影射到哈希空间上，有无好的解决冲突的方法，计算哈希函数是否简单高效。由于哈希函数是压缩映像，冲突难以避免。 散列表存储中解决碰撞的基本方法：
① 开放定址法 形成地址序列的公式是：Hi=（H（key）+di）% m，其中m是表长，di是增量。根据di取法不同，又分为三种：
a．di =1，2，?，m-1 称为线性探测再散列，其特点是逐个探测表空间，只要散列表中有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一散列地址。
b．di =1，-1，2，-2，? ，?k（k≤m/2） 称为二次探测再散列，它减少了聚集，但不容易探测到全部表空间，只有当表长为形如4j+3（j为整数）的素数时才有可能。
c．di =伪随机数序列，称为随机探测再散列。
② 再散列法 Hi=RHi（key） i=1，2，?，k，是不同的散列函数，即在同义词产生碰撞时，用另一散列函数计算散列地址，直到解决碰撞。该方法不易产生“聚集”，但增加了计算时间。
③ 链地址法 将关键字为同义词的记录存储在同一链表中，散列表地址区间用H[0..m-1]表示，分量初始值为空指针。凡散列地址为i（0≤i≤m-1）的记录均插在以H[i]为头指针的链表中。这种解决方法中数据元素个数不受表长限制，插入和删除操作方便，但增加了指针的空间开销。这种散列表常称为开散列表，而①中的散列表称闭散列表，含义是元素个数受表长限制。
④ 建立公共溢出区 设H[0..m-1]为基本表，凡关键字为同义词的记录，都填入溢出区 O[0..m-1]。
2
2
2
2
2
6、有一棵哈夫曼树共有5 个叶子结点其权值分别为0.1,0.25,0.08,0.21,0.9,试画出该哈夫曼树。假设该叶子分别表示a,b,c,d,e，分别给出五个叶子对应的哈夫曼编码。 yxh：a(1110),b(10),c(1111),d(110)，e(0)
7、采用哈希函数Ｈ（k）=3*k mod 13并用线性探测开放地址法处理冲突，在数列地址空间［0..12］中对关键字序列22,41,53,46,30,13,1,67,51 （1）构造哈希表（画示意图）；（2）装填因子；等概率下（3）成功的和（4）不成功的平均查找长度。 （1）
散列地址 关键字 比较次数 0 13 1 1 22 1 2 3 53 1 4 1 2 5 6 41 1 7 67 2 8 46 1 9 10 51 1 11 12 30 1 （2）装填因子=9/13=0.7 （3）ASLsucc =11/9 （4）ASLunsucc =29/13
8、已知一个图如下，试画出其逆邻接链表。
1 2 3 4
9、若一个栈的输入序列是1,2,3??，n, 其输出序列为p1,p2,??pn, 若 p1=n，则pi为多少？ yxh：i=n-i+1
10、非空的二叉树的中根遍历序列中，根的右子树的所有结点都在根结点的后边，这说法对吗？
11、已知二叉树的中根遍历序列为abc，试画出该二叉树的所有可能的形态。
12、已知一个图如图所示，如从顶点a出发进行按深度优先遍历，可否得到序列acebdf ?为什么？若按广度优先遍历，能否得到序列abedfc?为什么？
a c b e f d
13、栈的存储方式有哪两种？
14、对于单链表、单循环链表和双向链表，如果仅仅知道一个指向链表中某结点的指针p，能否将p所指结点的数据元素与其确实存在的直接前驱交换?请对每一种链表作出判断，若可以，写出程序段；否则说明理由。其中：
单链表和单循环链表的结点结构为 双向链表的结点结构为
15、假设通信电文使用的字符集为{a,b,c,d,e,f,g}，字符的哈夫曼编码依次为：0110，10，110，111，00，0111和010。
(1)请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应字符；
(2)若这些字符在电文中出现的频度分别为：3，35，13，15，20，5和9，求该哈夫曼树的带权路径长度。
16、试为下列关键字设计哈希表，要求所设计的表在查找成功时的平均查找长度不超过2.0。并请验证你造
设用线性探测再散列解决冲突，根据公式Snl≈（1+1/（1-α）） /2 。可求出负载因子为α=0.67。再根据数据个数和装载因子，可求出表长m=15/0.67，取m=23。设哈希函数H（key）=（关键字首尾字母在字母表中序号之和）MOD 23。
从上表求出查找成功时的平均查找长度为ASLsucc=19/15<2.0，满足要求。
17、用链表表示的数据的简单选择排序，结点的域为数据域data ，指针域 next ；链表首指针为head ，链表无头结点。 selectsort(head) p=head;
while (p(1)_______) {q=p; r=(2)_______ while((3)______ )
{if ((4)_______ ) q=r;
r=(5)_______ ;
}
tmp=q->data; q->data=p->data; p->data=tmp; p= (6)_______ ; }
题中p指向无序区第一个记录，q指向最小值结点，一趟排序结束，p和q所指结点值交换，同时向后移p指针。(1)!=null (2)p->next (3)r!=null (4)r->data
18、设某二叉树的前序遍历序列为：ABCDEFGHI，中序遍历序列为：BCAEDGHFI。（1）试画出该二叉树；（2）画出该二叉树后序线索化图。（3）试画出该二叉树对应的森林。
19、 一棵二叉排序树结构如下,各结点的值从小到大依次为1-9，请标出各结点的值。
的
哈
希
表
的
实
际
平
均
查
找
长
度
是
否
满
足
要
求
。
（CHA,CAI,LAN,WEN,LONG,ZHAO,WU,LIU,CHEN,LI,WANG,CAO,YUN,CHANG,YANG）
date next prior date next
20、下面的排序算法的思想是：第一趟比较将最小的元素放在r[1]中，最大的元素放在r[n]中，第二趟比较将次小的放在r[2]中，将次大的放在r[n-1]中，?,依次下去，直到待排序列为递增序。（注：<-->）代表两个变量的数据交换）。
void sort(SqList &r,int n) { i=1;
while((1)__) { min=max=1;
for (j=i+1;(2)____ ;++j)
{if((3)____) min=j; else if(r[j].key>r[max].key) max=j; } if((4)_____) r[min] < ---- >r[j];
if(max!=n-i+1){if ((5)___) r[min] < ---- > r[n-i+1]; else ((6)__); } i++; } }//sort
(1)i
堆是一种有用的数据结构. 堆排序是一种_(1)_排序，堆实质上是一棵_(2)_结点的层次序列。对含有N个元素的序列进行排序时，堆排序的时间复杂度是_(3)_，所需的附加存储结点是_(4)_。关键码序列05，23，16，68，94，72，71，73是否满足堆的性质_(5)_。
(1) 选择 (2)完全二叉树 (3)O(Nlog2N) (4)O(1) (5)满足堆的性质
22、在堆排序、快速排序和合并排序中：
(1)．若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选取哪种排序方法？ (2)．若只从排序结果的稳定性考虑，则应选取哪种排序方法？ (3)．若只从平均情况下排序最快考虑，则应选取哪种排序方法？
(4)．若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？
(1)堆排序，快速排序，归并排序 (2)归并排序 (3)快速排序 (4)堆排序 23、 算法模拟
设待排序的记录共7个，排序码分别为8，3，2，5，9，1，6。
(1) 用直接插入排序。试以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排序。
(2) 用直接选择排序。试以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排序。
(3) 直接插入排序算法和直接选择排序算法的稳定性如何？
(1)直接插入排序 第一趟 第四趟 第一趟 第四趟
四 算法阅读
(3)[8,3],2,5,9,1,6 第二趟 (2)[8,3,2],5,9,1,6 第三趟 (5)[8,5,3,2],9,1,6 (9)[9,8,5,3,2],1,6 第五趟 (1)[9,8,5,3,2,1],6 第六趟 (6)[9,8,6,5,3,2,1] (9)[9],3,2,5,8,1,6 第二趟 (8)[9,8],2,5,3,1,6 第三趟 (6)[9,8,6],5,3,1,2 (5)[9,8,6,5],3,1,2 第五趟 (3)[9,8,6,5,3],1,2 第六趟 (2)[9,8,6,5,3,2],1
(2)直接选择排序（第六趟后仅剩一个元素，是最小的，直接选择排序结束）
(3)直接插入排序是稳定排序，直接选择排序是不稳定排序。
1、void AE(Stack& S){ InitStack(S); Push(S,3); Push(S,4); int x=Pop(S)+2*Pop(S); Push(S,x); int i,a[5]={1,5,8,12,15}; for(i=0;i<5;i++) Push(S,2*a[i]); while(!StackEmpty(S)) print(Pop(S)); }
该算法被调用后得到的输出结果为：
2、 void ABC (BTNode *BT,int &c1,int &c2) { if (BT !=NULL )
{ ABC(BT->left,c1,c2); c1++; if (BT->left==NULL&&BT->right==NULL) c2++; ABC(BT->right,c1,c2); }//if }
该函数执行的功能是什么？
3、在下面的每个程序段中，假定线性表La的类型为List，e的类型为ElemType,元素类型ElemType为int，
并假定每个程序段是连续执行的。试写出每个程序段执行后所得到的线性表La。
（1）InitList(La);
Int a[]={100,26,57,34,79}; For (i=0;i<5;i++)
ListInsert(La,1,a[i]); （2）ListDelete(La,1,e);
ListInsert(La,ListLength(La)+1,e); （3）ClearList(La); For (i=0;i<5;i++)
ListInsert(La,i+1,a[i]);
4、int Prime(int n) {
int i=1;
int x=(int) sqrt(n);