7.假设通信电文使用的字符集为{a,b,c,d,e,f,g}，字符的哈夫曼编码依次为：0110，10，110，111，00，0111和010。
(1)请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应字符；
(2)若这些字符在电文中出现的频度分别为：3，35，13，15，20，5和9，求该哈夫曼树的带权路径长度。
8．已知带权图的邻接表如下所示，其中边表结点的结构为：
依此邻接表从顶点C出发进行深度优先遍历。 （1）画出由此得到的深度优先生成树；
（2）写出遍历过程中得到的从顶点C到其它各顶点的带权路径及其长度。
9.假设用迪杰斯特拉(Dijkstra)算法求下列图中从顶点a到其余各顶点的最短路径，按求解过程依次写出各条最短路径及其长度。
10.试给出下图的邻接矩阵和邻接表表示。
11.已知如图所示，用普里姆（prim）算法从顶点A开始求最小生成树。在算法执行之初，顶点的集合U={A，B}，边的集合TE={（A，B）}。试按照最小生成树的生成过程，分步给出加入顶点和边以后的集合U和TE的值。
12．用二分查找法对一个长度为10的有序表进行查找，填写查找每一元素需要的比较次数。（8分）
11
元素下标 比较次数
1 2 3 4 5 6 7 8 9 10
13．从空树起，依次插入关键字37，50，42，18，48，12，56，30，23，构造一棵二叉排序树。
（1）画出该二叉排序树；
（2）画出从（1）所得树中删除关键字为37的结点之后的二叉排序树。 14.已知某二叉排序树10个结点的值依次为1~10，其结构如图所示，试标出该二叉树各结点所对应的具体值。
15．上图所示二叉树是否为平衡二叉树？若是，说明理由；若不是，将其转换为平衡二叉树。
16．对下列关键字序列（33，25，48，59，36，72，46，07，65，20）构造表长为19的散列表。假设散列函数为h(key)=key,用开放地址法解决冲突，探查序列为d=h(key),d+12,d-12，d+2 2,d-2 2,d+32，d-32，?，等等。 （1）画出该散列表；
（2）计算该散列表的装填因子α；
（3）求出等概率情况下查找成功的平均查找长度ASL。
17.已知散列函数为H(key)=key%7，散列表长度为7(散列地址空间为0..6)，待散列序列为：(25，48，32，50，68)。要求：
(1)根据以上条件构造一散列表，并用线性探测法解决有关地址冲突； (2)若要用该散列表查找元素68，给出所需的比较次数。
18.已知一组键值序列（22，24，26，25，27，29，21，28），试给出采用直接插入排序法对该组序列作升序排序的每一趟结果。
19.已知一组键值序列为(38，64，73，52，40，37，56，43)，试采用快速排序法对该组序列 作升序排序，并给出每一趟的排序结果。
20.已知一组键值序列(26，21，32，56，78，89，90)，试采用二路归并排序法对该组序列 作升序排序，并给出每一趟的排序结果。
21.画出对应于序列{10，20，7，75，41，67，3，9，30，45}的初始堆（堆顶元素取最小值）。
22．L为一个带头结点的循环链表。函数f30的功能是删除L中数据域data的值大于c的所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。请在空缺处填入合适的内容，使其成为一个完整的算法。 LinkList f30(LinkList L, int c) {
LinkList Lc,p,pre; pre=L;
12
p= (1) ;
Lc=(LinkList) malloc(sizeof(ListNode)); Lc->next=Lc; while(p!=L) if(p->data>c) {
pre->next=p->next; (2) ; Lc->next=p; p=pre->next; } else {
pre=p;
(3) ; }
return Lc; }
23.已知head为带头结点的单循环链表的头指针，链表中的数据元素依次为（a1，a2,a3,a4,?,an）,A为指向空的顺序表的指针。阅读以下程序段，并回答问题： （1）写出执行下列程序段后的顺序表A中的数据元素； （2）简要叙述该程序段的功能。 if(head->next!=head) {
p=head->next; A->length=0;
while(p->next!=head) {
p=p->next;
A->data[A->length ++]=p->data; if(p->next!=head)p=p->next; } }
24．假设线性表采用顺序存储结构，表中元素值为整型。阅读算法f 30，并回答下列问题： （1）设顺序表L=(3,7,3,2,1,1,8,7,3),写出执行算法f 30后的L; （2）简述算法f 30的功能。 void f 30(SeqList *L) { int i,j,k;
k=0;
for(i=0;i
{ for(j=0;j
{ if(k!=i)L->data[k]=L->data[i]; k++; } }
L->length=k;
13
}
25．阅读算法f 31,并回答下列问题： （1）设队列Q=（1，3，5，2，4，6）。写出执行算法f 31后的队列Q; （2）简述算法f 31的功能。 void f 31(Queue *Q){ DataType e;
if (!QueueEmpty(Q)){ e=DeQueue(Q); f 31(Q);
EnQueue(Q,e); } }
五、算法设计题
1．设单链表的结点结构如下： struct node{datatype data; struct node*next; }
试编写一个函数int count(struct node *head,datatype x)统计单链表中数据域为x的结点个数。 2．假设以带头结点的单链表表示有序表，单链表的类型定义如下： typedef struct node{ DataType data; struct node *next }LinkNode, *LinkList;
编写算法，从有序表A中删除所有和有序表B中元素相同的结点。
3.二叉树是由所有度数不大于2的结点构成的一种特定树，若某结点度为2，则该结点有左 右两个孩子，请编写算法计算一二叉树所有度数为2的结点个数。
4.若二叉树存储结构采用二叉链表表示，试编写一算法，计算一棵二叉树的所有结点数。
14