学海网

湖南工学院2008-2009年度第二学期数据结构模拟试卷
一、填空题(每小题 2 分，共 20 分)
1、设二叉树结点的先序序列为ABDECFGH，中序序列为DEBAFCHG,则二叉树的后序序列是 EDBFHGCA 。
2、一个哈夫曼(Huffman)树有19个结点，则其叶结点的个数是 10 。
3、线性表L=(a1,a2,…,an)采用顺序结构存储,假定在不同的位置上插入的概率相同，则插入一个新元素平均需要移动的元素个数是 n/2 。
4、栈S和队列Q的初始状态皆为空,元素a1,a2,a3,a4,a5和a6依次通过S栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a1,a4,a5,a6,a3,a2，则栈S至少应该容纳
3 个元素。
5、在一个无向图的邻接表中，若表结点的个数是m，则图中边的条数是 m/2 。
6、一棵二叉树有67个结点,这些结点的度要么是0，要么是2。这棵二叉树中度数为2的结点有
33 个
7、采用堆排序、快速排序、冒泡排序，对初态有序的表，最省时间的是 冒泡排序 。
8、设有一个10阶的对称矩阵，采用压缩存储方式、以行序为主序存储，a11为第一个元素，其存储地址为1，每个元素占1个地址空间，则a65的地址为 　10+9+8+7+2　 。
9、设串S1=’ABCDEFG’，S2=’PQRST’，函数con(X,Y)返回X和Y串的连结串，sub(S,i,j) 返回串S的从序号i的字符开始的j个字符组成的子串，lens(S)返回串S的长度，则con(sub(S1,2,lens(S2)))的结果串是CDEFG　。
10、图常用四种存储结构来表示图的各种形态，这四种存储结构分别为：数组表示法、邻接表法、　十字链表法　和邻接多重表法。
.......