中南大学2002年数据结构
填空(20分)
1.分别采用堆排序、快速排序、插入排序和归并排序对初始状态为递增序列的表排序，最省时间的是 算法，最费时间的是 算法。
2.在有n个顶点的有向图中，每个顶点的度最大可达 。
3.二叉树中叶结点数为50，仅有一个孩子的结点数为30，则总结点数为 。
4.已知栈的输入序列为1，2，3，…，n，输出序列为a1，a2，…an，a2=n的输出序列共有 种。
5.直接选择排序算法在最好情况下所作的交换元素的次数为 。
6.如果有n个顶点的图是一个环，则它有 棵生成树。
7.数组A[1…10，-2…6，2…8]的元素按行顺序存储，第一个元素的首地址为100，每个元素的长度为3，则元素A[5，0，7]的存储地址为 。
8.已知二叉树如左图，则：
其中序遍历的序列为
单项选择题(15分)
若单链表中最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用( )存储方式最节省时间。
A、单链表 B、双向链表
C、单循环链表 D、带头结点的双循环链表
2.在有n个叶子结点的Huffman树中，其结点总数为( )
A、n B、2n
C、2n-1 D、2n+1
3.对于关键字系列{12，13，11，18，60，15，7，18，25，100}，用筛选法建堆，必须从关键字为( )的结点开始。
A、100 B、12
C、60 D、15
4.若某二叉树的前序序列和后序序列正好相反，则该二叉树一定是( )二叉树。
A、空或只有一个结点 B、高度等于其结点树
C、任一结点无左孩子 D、任一结点无右孩子
5.设循环队列中数组的下标范围是0…m-1，已知其队头指针front指向当前队头元素，队尾指针rear指向队尾元素的下一个位置，则当前队列中的元素个数为( )
A、(rear-front+m) mod m B、(rear-front+1) mod m
C、rear-front D、rear-front+1
6.下列排序算法中，( )每一趟都能选出一个元素放在其最终位置少年宫，并且是不稳定的。
A、快速排序 B、希尔排序
C、直接插入排序 D、直接选择排序
7.已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( )。
A、-A+B*C/DE B、-A+B*CD/E
C、-+*ABC/DE D、-+A*BC/DE
8.广义表A=(a,b,(c,d),(e,(f,g)))，则下面式子的值为( )Head(Tail(Head(Tail(Tail(A)))))，其中Head(L)，Tail(L)分别取广义表L的表头和表尾。
A、(g) B、(d)
C、c D、d
9.一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是( )
A、23415 B、54132
B、23145 D、15432
10.数据表中有10000个元素，如果仅要求求出其中最大的10个元素，则采用()排序算法最节省时间。
A、堆 B、希尔
C、快速 D、直接选择
11.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为( )。
A、2h B、2h-1
C、2h+1 D、h+1
12.在一个具有n个顶点的无向图中，要连通全部顶点至少需要( )条边。
A、n B、n+1
C、n-1 D、n/2
13.设HASH表长m=14，HASH函数为key MOD 11(MOD为求模运算)，在存放完关键字15，38，61，84后，存放关键字49，若采用线性探测法解决冲突时的地址为( )。
A、8 B、3
C、5 D、9
14.非空的循环单链表head的尾结点*p满足( )
A、p->next= =NULL B、p= =NULL
C、p->next=head D、p=head
15.在事件网络中关键路径是( )
A、从源点到汇点的最短路径 B、从源点到汇点的最长路径
C、最长的回路 D、最短的回路
三、设有一段正文：CAST，CATS，SAT，AT，A，TASA，其中使用的字符集set={C，A，S，T}。请用哈夫曼算法设计一套set中字符的二进制编码，使上述正文的二进制内部表示最短，并且采用这种编码时，字符间不用分割符就能识别。要求：(10分)
1)画出哈夫曼树，并求其WPL;
2)给出set中字符的编码表。
3)将上述正文译成二进制编码。
四、一个连通图表示一个通信网络，如右图所示。其中，顶点表示网络中的通信站点，边表示网络中的通信线路，则(16分)
1)从顶点①出发的深度优先生成树;
2)设每条边延迟时间为a,每中间结点的延迟时间为b,求从结点①至其它各点中的最 长和最短时间
3)在原来的图中至少补充几条边，使其中某一站点失效时整个通信网络仍然保持畅通
4)指出图中哪几个顶点是关结点(即万一它失效则通讯网络发生故障)
五、设有序顺序表中的元素依次为017，094，154，170，275，503，509，512，553，612，677，765，897，908。试分别画出对其进行顺序查找和折半查找时的判定树，并分别计算查找成功的平均查找长度(10分)。
六、已知有n个选手P1，P2，Pn参加一项比赛，每对选手之间非胜即负，试设计算法求出一个选手系列P1′，P2′，...，Pn′，使得Pi+1′(1≤i
七、试设计一个查找算法Locate实现下述要求。设有一个带表头结点的双向链表L，每个结点有4个数据成员：指向前驱结点的指针prior，指向后继结点的指针next，存放数据的成员data和访问频度freq。所有结点的freq初始时都为0。每当在链表上进行一次Locate(L,x)操作时，令元素值为x的结点的访问频度freq加1，并将该结点前移，链接到与它的访问频度大于或相等的结点后面，使的链表中所有结点保持按访问频度递减的顺序排列，以使访问频度的结点总靠近表头。(14分) | 
