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);
while (++i<=x)
if (n%i==0) break; if (i>x) return 1; else return 0; }
(1)指出该算法的功能；
(2)该算法的时间复杂度是多少？
5. 写出下述算法A的功能： 其中BiTree定义如下: Typedef struct BiTNode{
TElemType data;
struct BiTNode *LChild, *RChild; }BiTNode, *BiTree;
Status A(BiTree T) {
Queue Q;
InitQueue(Q); ENQueue(Q,T);
While(not QueueEmpty(Q)) { DeQueue(Q,e);
If(e==NULL) break; Else
{ Print(e.data);
ENQueue(Q,e.LChild); ENQueue(Q.e.RChild); }
} }
6.阅读下列函数algo,并回答问题：
(1)假设队列q中的元素为(2,4,5,7,8),其中“2”为队头元素。写出执行函数调用algo(&q)后的队列q； (2)简述算法algo的功能。 void algo(Queue *Q) {
Stack S; InitStack(&S);
while (!QueueEmpty(Q)) Push(&S, DeQueue(Q)); while (! StackEmpty(&S)) ＥnQueue(Q,Pop(&S)); }
yxh：(1)q中的元素为(8,7,5,4,2); (2)把队列q中的元素倒序。 五 算法填空
1、下面是在带表头结点的循环链表表示的队列上，进行出队操作，并将出队元素的值保留在x中的函数，其中rear是指向队尾结点的指针。请在横线空白处填上适当的语句。
typedef struct node { int data; struct node *next;