2、在一份电文中共使用五种字符：A，G，F，U，Y，Z，它们的出现频率依次为12,9,18,7,14，11，求出每个字符的哈夫曼编码。
四、阅读算法，回答问题（每小题5分，共20分）
1、void AA (LNode * HL,const ElemType & item) {
LNode * newptr=new Lnode ; newptr->data=item; LNode *p=HL;
while ( p->next!=HL ) p=p->next;
newptr->next=HL; p->next=newptr; }
对于结点类型为LNode的单链表，以上算法的功能为：
2、void BB(List &L) {
int i=0;
while (i int j=i+1; while (j if(L.list[j] = =L.list) { for (int k=j+1;k else j++; } i++; } } 以上算法的功能为： 3、void CC(BTreeNode * & BST ) { ElemType a[6 ]={45，23，78，35，77，25}； BST=NULL； for( int i=0,i<6;i++) Insert(BST , a[i]); } 调用该算法后，生成的二叉搜索数的中序序列为： 4、void DD ( ) { ElemType A[ ]={1,3,5,7,9,2,4,6,8,10},B[10]; TwoMerge(A, B,0,4,9); for ( int i=0; i<10; i++) cout< 调用该算法后，输出结果为： 五、算法填空，在画有横线的地方填写合适的内容(10分)。 利用单链表进行数据排序。 void LinkSort (ElemType a[ ],int n) { LNode * head=new LNode; InitList (head); int i; for (i=0;i while ( ) { a[i++]=p->data; } ClearList (head); } 六、编写算法(10分) 编写一个非递归算法，在稀疏有序索引表中二分查找出给定值K所对应的索引项，即索引值刚好大于等于K的索引项，返回该索引项的start域的值，若查找失败则返回-1。 答案 一、单选题 （每空2分，共10分） 1、A 2、 A 3、A 4、 B 5 、A 二、填空题（每空1分，共20分） 1、顺序结构、链接结构、索引结构、散列结构 2、2i+1、2i+2、?(i-1)/2? 3、栈顶元素、栈顶指针 4、6 5、2、2、0、7 6、n(n-1)/2 、n(n-1) 7、稠密、稀疏 8、二叉搜索树、理想平衡树 三、运算题（每小题5分，共10分） 1、（64） （52，64） （12，64，52） （12，48，52，64） （12，45，52，64，48） （12，45，26，64，48，52） 2、 A：111 G：011 F：10 U：010 Y：00 Z：110 （或0、1 相反） 四、阅读算法，回答问题（每小题5分，共20分） 1、向单链表的末尾添加一个元素。 2、删除线性表中所有重复的元素。 3、23 25 35 45 77 78 4、 1 2 3 4 5 6 7 8 9 10 五、算法填空，在画有横线的地方填写合适的内容(10分)。 p!=NULL p=p->next; delete head; 六、编写算法(10分) int Binsch(IndexList B, int m, IndexKeyType K) { int low=0, high=m-1; while (low<= high) { int mid=(low+high)/2; if (K= =B[mid]. index ) return B[mid].start; else if (K low=mid+1; } if (low 《数据结构》模拟题（三） 一、单选题 （每空2分，共10分） 1、在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）之前插入一个新元 素时，需要从后向前依次后移（ ）个元素。 A．n-i B．n-i+1 C．n-i-1 D．i 2、在线性表的散列存储中，若用m表示散列表的长度，n表示待散列存储的元素的个数， 则装填因子?等于（ ）。 A．n/m B．m/n C．n/(n+m) D．m/(n+m) 3、从一棵B_树删除元素的过程中，若最终引起树根结点的合并，则新树高度是（ ）。 A．原树高度加1 B．原树高度减1 C．原树高度 D．不确定 4、在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的（ ）。 A．行号 B．列号 C．元素值 D．地址 5、在一个具有n个顶点的无向图中，要连通所有顶点则至少需要（ ）条边。 A．n B．2n C．n-1 D．n+1 二、填空题（每空1分，共20分） 1、 对于双目操作符，其重载函数带有__________个参数，其中至少有一个为____________ 的类型。 2、 从一维数组a[n]中顺序查找出一个最大值元素的时间复杂度为________，输出一个二维 数组b[m][n]中所有元素值的时间复杂度为________。 3、在归并排序中，进行每趟归并的时间复杂度为________，整个排序过程的时间复杂度为 ________，空间复杂度为________。 4、在一棵m阶B_树上，每个非树根结点的关键字数目最少为________个，最多为________ 个，其子树数目最少为________，最多为________。 5、当从一个小根堆中删除一个元素时，需要把________元素填补到________位置，然后再 按条件把它逐层________调整。 6、快速排序在平均情况下的时间复杂度为________，在最坏情况下的时间复杂度为 ________。 7、从一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明_______，若 元素的值小于根结点的值，则继续向________查找，若元素的大于根结点的值，则继续向________查找。 8、在一个单链表HL 中，若要向表头插入一个由指针p指向的结点，则应执行语句：