数据结构期末考试试题及答案

1、试卷一参考答案一、单项选择题1. 【答案】C【解析】数据结构按逻辑结构可以分为集合、线性结构、树形结构以及图状结构，集合不在课程讨论范围之内，树形结构与图状结构可统称为非线性结构，因此答案选C。2【答案】B【解析】P指向x结点，p->next指向x结点的后继结点，p->next->next指向x后继结点的后继结点，因此在删除x的后继结点时,即修改p->next的指向，答案选B。3. 【答案】C【解析】根据二叉树的性质4，具有n个结点的完全二叉树的深度为。而完全二叉树是n个结点所组成的二叉树中具有最小深度的树的形态,所以,答案选C。4【答案】C【解析】栈的基本性质是后进先

2、出，入栈顺序是1，2，3，4，则出栈顺序已定不可能存在答案C的顺序，因为4作为第一个出栈的元素，则1，2，3均已经入栈，因此，出栈顺序只能为4，3，2，1。5. 【答案】B【解析】本题考查循环队列队满的条件，注意该循环队列的数组中MAXSIZE=m，因此，答案选B而不能选择D。6【答案】B【解析】对称矩阵的压缩存储的特点就是存储对角线及其以下的所有元素，a11为第一个元素,且存储地址为1,所以,只要确定a85在所有存储元素中的名次就可以确定其地址。(1+7)*7/2+5=33，因此答案选B7. 【答案】D【解析】根据后序遍历的特点即最后一个元素为根结点，中序遍历的特点即以根为分界点，左边的元素

3、都属于左子树中，右边的所有元素属于右子树中元素，其中，左右子树又满足以上特点，可以构造出二叉树，先序遍历序列为D。8【答案】B【解析】本题考查顶点的度的概念，顶点的度即与该顶点相关联的边的数目，或者选项B，在此，答案A，C，D都是错误的。9. 【答案】B【解析】根据二叉排序树的定义，本题答案选B，这也是二叉排序树的特征。10【答案】A【解析】快速排序的基本思想是通过一趟快速排序，确定出枢轴元素的确定位置，且使得左右两边元素相对均匀，然后可以在两边同时实施快速排序，此时效率最高，当元素基本有序时，大多数元素集中在枢轴元素的一边，反而使得快速排序逐步蜕化为冒泡排序，性能降低。二、填空题1. 【答案

4、】n/2【解析】线性表采用顺序存储，插入位置一共n+1个位置,且等概率,则在最后一个位置插入元素,不需要移动元素,在第n个元素前面插入元素需要移动1个元素,依此类推，在第1个元素前面插入元素，需要移动n个元素，因此，平均一定次数为（0+1+2+n）/( n+1 )=n/2。2【答案】33【解析】根据二叉树的性质3，n0=n2+1，本题中只有度为2的结点和度为0的结点，因此n0=34,n2=33。3. 【答案】n-1【解析】根据图的生成树的定义，包括全部n个顶点，只包含足以连通n个顶点的n-1条边。4【答案】队尾、队头【解析】本题考查队列的基本定义。5. 【答案】4【解析】本题考查树中结点的度、

5、兄弟的定义。6【答案】前驱、后继【解析】线索二叉树的特点就是根据某种遍历顺序，确定出每个结点的前驱与后继，将结点中空的左孩子指针指向结点的前驱，空的右孩子指针指向结点的后继。该过程也称为线索化。7. 【答案】关键路径【解析】AOE网络可以表示工程完成进度图，本题考查关键路径的定义。8【答案】边稠密、边稀疏【解析】根据普里姆算法和克鲁斯卡尔算法的算法思想，Prim算法适合于求边稠密的网的最小生成树，Kruskal算法适于求边稀疏的网的最小生成树9. 【答案】4【解析】根据折半查找的算法思想，可以形成具有11个结点的判定树如下，本题查找元素20，需要与第4及第5个元素比较之后才能确定该元素不存在，

6、因此需要比较4次。10【答案】比较、移动【解析】通过元素之间的比较确定出待排元素的位置，通过元素的移动后，将待排元素插入到恰当的位置。三、综合应用题1答：首先画出哈夫曼树如下图，注意要求树中左孩子结点的权值小于右孩子结点的权值。可以将所有的左分支设为0，右分支设为1，则从树根到每个叶子结点可以形成相应字符的哈夫曼编码a:11;b:1010;c:100;d:01;e:1011;f:002答：V0到其他各顶点的最短路径V1100（v0，v1）25（v0，v1）-V220（v0，v2）-V360（v0，v2，v3）60（v0，v2，v3）55（v0，v4，v3）-V430（v0，v4）30（v0，v4）30（v0，v4）-V580（v0，v5）80（v0，v5）80（v0，v5）80（v0，v5）70（v0，v4，v3，v5）添加顶点V2V1V4V33答：根据关键字序列及处理冲突的方法构造表长为11的哈希表如下：等概率情况下，该哈希表的平均查找长度:(1*3+2*2+3*1+5*1)/7=15/7。四、算法设计题void insert_L(Linklist &L,int n) p=L;while(p->next->data!=x&&p) p=p->next;for(i=