p=p->next; i++; } if(p){ *e=p->next->data; q=p->next;
p->next=q->next; free(q); } else
printf(“ERROR k”); }
2.写一算法将单链表倒置。
Void ResList(LinkList L) {
LinkList p,q; P=L->next; If(!p)
{ printf(“empty list”); return; } else {
q=p->next;
p->next=NULL;//新表的表尾
while(q)//从第二个元素开始头插法加入元素 {
p=q->next;
q->next=L->next; L->next=q; q=p; }
} }
第八周作业
1.按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答： 1）如进站的车厢序列为123，则可能得到的出站车厢序列是什么？ 解答：可能得到的序列有：123 132 213 231 321
2）如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因。（即写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。
解答：435612不能得到，第一个出栈的是4,则须1S2S3S4S4X3X，后5S5X6S6X，栈里只有1 2，但1在栈底，不能先于2出栈；135426可得到，进行下列操作：1S1X2S3S3X4S5S5X4X2X6S6X 2.试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1 & 序列2’模式的字符序列。其中序列1和序列2 中都不含字符’&’，且序列2 是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘１+３&３－１’则不是。 解答：
int ResList( ) {
Char *str,ch; Stack S; IniStack(S);
Scanf(“%c”,&ch) While(ch!=’&’) {
Push(S,ch);
Scanf(“%c”,&ch); }
Scanf(“%c”,ch);
While(ch!=’@’&& !EmptyStack(S)) {
If(ch==GetTop(S)) {
Pop(S,&ch);
Scanf(“%c”,ch); } Else
Return 0; }
If(ch==’@’&& EmptyStack(S)) Return 1; Else
Return 0;
}
3.简述以下算法的功能（其中栈和队列的元素类型均为int）： （1）void proc_1(Stack S) { int i, n, A[255]; n=0;
while(!EmptyStack(S)) {n++; Pop(&S, &A[n]);} for(i=1; i<=n; i++) Push(&S, A[i]); }
解答：通过数组A将栈S置逆 （2）void proc_2(Stack S, int e) { Stack T; int d; InitStack(&T);
while(!EmptyStack(S)) { Pop(&S, &d);
if (d!=e) Push( &T, d); }
while(!EmptyStack(T)) { Pop(&T, &d); Push( &S, d); } }
解答：借助栈T将栈S中所有值为e的数据元素删除且S中元素次序不变 （3）void proc_3(Queue *Q) { Stack S; int d; InitStack(&S);
while(!EmptyQueue(*Q)) {
DeleteQueue(Q, &d); Push( &S, d); }
while(!EmptyStack(S)) { Pop(&S, &d); EnterQueue(Q，d) } }
解答：通过栈S将队列Q置逆
第九周作业
1.画出下面广义表的两种存储结构图示： ((((a), b)), ((( ), d), (e, f)))
解答：第一种存储结构
第二种存储结构（线性扩展）
2.求下列广义表运算的结果： 解答： 1）HEAD[((a,b),(c,d))];
2）TAIL[ ((a,b),(c,d)) ];
3）TAIL[HEAD[((a,b),(c,d)) ]]
4）HEAD[TAIL[HEAD[((a,b),(c,d)) ]]] 5）TAIL[HEAD[TAIL[((a,b),(c,d)) ]]]
已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，nk个度为k的结点，则该树中有多少个叶子结点？
解答:
已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？
解答:
5.计算：1） n个结点的k叉树，若用具有k个child域的等长链结点存储树的一个结点，则空的child域有多少个？2） 一棵完全二叉树共有520个结点，该完全二叉树共有多少个叶子结点、度为1的结点和度为2的结点？3） 已知完全二叉树的第7层有10个结点，则整个二叉树的结点数为多少个？ 解答：
第十周作业
1.假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。 解答1
2.给出满足下列条件的所有二叉树：解答2 ① 前序和后序相同 ② 中序和后序相同 ③ 前序和中序相同 ① 前序和后序相同
答：有二种，空二叉树、只含根结点的二叉树 ② 中序和后序相同
答：有三种，空二叉树、只含根结点的二叉树、不含右子树的二叉树 ③ 前序和中序相同
答：有三种，空二叉树、只含根结点的二叉树、不含左子树的二叉树
写一个算法求二叉树中度为2的结点的个数 int count2(BitTree t) {
int count=0;
if(!t) return count;
else if(t->LChild && t->RChild) count=1;
count=count+count2(t->LChild)+count2(t->RChild); return count; }
第十一周
画出和下列树对应的二叉树：解答
解答：
(a) (b) (c) (d)
2.假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为： 0.07，0.17，0.02，0.06，0.32，0.03，0.23，0.10
请为这8个字母设计哈夫曼编码（先建哈夫曼树再编码） 解答：哈夫曼树：
频率 编码 0.07 0.17 0.02 0.06 0.32 0.03 0.23 0.10 000 101 10000 1001 11 10001 01 001
编码：
第十二周
已知如图所示的有向图，请给出该图的：
（1） 每个顶点的入度、出度；（2） 邻接矩阵；
（3） 邻接表；（4） 逆邻接表；
（5）十字链表
解答
第十三周
第一题解答
第二题解答
第十四周作业
1.对有19个数据的有序表进行折半查找,画出其判定树并计算平均 2.查找长度
3.已知长度为12的表：
（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）。
1）试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树并求其等概率的情况下查找成功的平均查找长度。
2）若对表中元素先进行排序构成有序表，求其等概率的情况下对此有序表进行折半查找成功的平均查找长度。
3）按表中元素的顺序依次构造一棵平衡二叉树，并求其等概率的情况下查找成功的平均查找长度。
3.设有一组关键字为：(13,29,01,23,44,55,20,84,27,68,11,10,79,14)，n=14，选取a=0.75, 则哈希表长m=19，哈希表为T[0..18]，用除留余数法构造哈希函数，选p=17，分别用平方探测再散列和随机探测再散列解决冲突,并计算平均查找长度。其中随机数序列为：3,16,55,44,...
倚窗远眺，目光目光尽处必有一座山，那影影绰
绰的黛绿色的影，是春天的颜色。周遭流岚升腾，没露出那真实的面孔。面对那流转的薄雾，我会幻想，那里有一个世外桃源。在天阶夜色凉如水的夏夜，我会静静地，静静地，等待一场流星雨的来临…
许下一个愿望，不乞求去实现，至少，曾经，有那么一刻，我那还未枯萎的，青春的，诗意的心，在我最美的年华里，同星空做了一次灵魂的交流…
秋日里，阳光并不刺眼，天空是一碧如洗的蓝，点缀着飘逸的流云。偶尔，一片飞舞的落叶，会飘到我的窗前。斑驳的印迹里，携刻着深秋的颜色。在一个落雪的晨，这纷纷扬扬的雪，飘落着一如千年前的洁白。窗外，是未被污染的银
白色世界。我会去迎接，这人间的圣洁。在这流转的岁月里，有着流转的四季，还有一颗流转的心，亘古不变的心。
