Question

大学数据结构题目，懂得进。麻烦详细回答，答得好会加分

1、将两个按递增有序排列的单链表归并成一个按元素值递增有序排列的单链表（写出此算法的伪代码）。

2.写出串abaaabaac的next值。

3．二叉树的中序和后序遍历结果分别为4, 5, 2, 1, 6, 3, 8, 7和5, 4, 2, 6, 8, 7, 3, 1,
（1）画出此二叉树
（2）求其先序遍历的结果

4．给定一组数列（6,5,3,7,9）分别代表字符A，B，C，D，E的权值，
（1）画出Huffman树（要求树中左子树根结点的权值大于右子树根结点的权值）
（2）给出各字符的Huffman编码（左分支编码0，右分支编码1）。

1. 某图的表示意如下，按拓扑排序算法，写出电脑输出的拓扑排序结果。（参照算法7.12）
0: ->5->2->1^
1: ->4->3->2^
2: ->3^
3: ->4^
4: ^
5: ->4^

2. 按顺序输入顶点对：(1,2)，(1,6)，(2,6)，(1,4)，(6,4)，(1,3)，(3,4)，(6,5)，(4,5)，(1,5)，(3,5)，根据建立无向图的邻接表算法CreateALGraph画出相应的邻接表。并写出在该邻接表上，从顶点4开始搜索所得的深度优先遍历序列和广度优先遍历序列。

3．有向网N={V,E}，V={0,1,2,3,4}，E={<0,1,1>，<0,3,3>，<0,4,10>，<1,2,5>，<2,4,1>，<3,2,2>，<3,4,6>}，E中每个元组的第三个元素表示权。
⑴、画出该网。
⑵、用Dijkstra算法求最短路径，写出顶点0到其它各顶点的最短路径长度、路径及产生过程。
⑶、求关键路径，写出计算过程。

4．无向网N={V,E}，V={0,1,2,3,4}，E={(0,1,10)，(0,4,19)，(0,2,1)，(0,3,8)，(1,2,5)，(1,3,6)，(1,4,29),(2,3,6)，(3,4,3}，E中每个元组的第三个元素表示权。
⑴. 画出该网；
⑵. 写出该网的邻接矩阵；
⑶. 用Prim算法(从顶点0开始)求最小生成树，依次写出树的生长过程；
⑷. 用Kruskal算法求最小生成树，依次写出树的生长过程。

5. 往一棵空的AVL树中依次插入关键码2, 1, 3, 5, 8, 4, 7, 6, 分别画出每个关键码插入完成后的AVL树。

6. 画出在初始为空的AVL树中依次插入30, 45, 50, 46, 55, 49, 40时该树的生长全过程，并在有“旋转”时说出“旋转”的类型。

7. 假设关键字输入顺序为80, 20, 10, 8, 27, 32, 68, 95, 87,63, 46，散列函数采用除留余数法，其表达式为：H(Key)=Key%13。
⑴. 用拉链法解决冲突，画出插入所有关键字后的链表结构（假设链表头插入）。
⑵. 计算该表查找成功的平均查找长度。

Answer 1

1.void merge(LinkList *A,LinkList *B,LinkList *&C)
{LinkList *p=A->next, *q=B->next,*r;
C=A,C->next=NULL;r=C;
while(p!=NULL&&q!=NULL)
{ if(p->data<q->data)//将*p链接到C上
{r->next=p;p=p->next;
r=r->next;
}
else if(p->data>q->data)//将*q链接到C上
{ r->next=q;q=q->next;
r=r->next;
}
else
{r->next=p;p=p->next;r=r->next;
r->next=q;q=q->next;r=r->next;
}
}
r->next=NULL;
if(q!=NULL)p=q;
if(p!=NULL)r->next=p;//将余下的结点链接到C上
}