重庆邮电大学2007年数据结构考研试题解析

一、选择题解析

循环队列满队列条件答案：C 循环队列满的条件是队头指针front等于(rear+1)%m，这样可以区分空队列(front=rear)和满队列的情况。
栈的输出序列答案：C 当第一个输出元素为n时，说明所有元素都已入栈，此时输出序列为n, n-1, ..., 1，所以第i个输出元素为n-i+1。
与计算机无关的数据结构答案：A 数据的逻辑结构与计算机无关，存储结构和物理结构都与计算机实现相关。
顺序表插入时间复杂度答案：C 顺序表在第i个位置插入元素需要移动n-i+1个元素，时间复杂度为O(n)。
有序表归并最少比较次数答案：B 最少比较次数为n，当一个表的所有元素都小于另一个表时。
广义表Head(X)=Tail(X)答案：B 只有广义表(())满足Head(X)=()，Tail(X)=()。
二叉树结点关系答案：C 先根序列中x在y前，后根序列中x在y后，说明x是y的祖先。
B-树非终端结点子树数量答案：A m阶B-树非终端结点(除根外)至少有⌈m/2⌉棵子树。
先序序列和后序序列相反答案：B 当二叉树高度等于结点数时(即每个结点只有一个孩子)，先序和后序序列相反。
栈的输出序列答案：A 23415是可能的输出序列，其他选项不符合栈的操作规则。
3个结点的不同形态二叉树答案：D 3个结点可以构成5种不同形态的二叉树。
循环队列长度计算答案：D 循环队列长度为(rear-front+n)%n。
双栈共享空间最优设置答案：B 两个栈分别从数组两端向中间增长可以最大化空间利用率。
打印缓冲区数据结构答案：B 打印缓冲区采用先进先出的队列结构。
括号匹配算法最佳数据结构答案：A 栈是最适合处理括号匹配问题的数据结构。
稳定且O(nlogn)的排序算法答案：C 归并排序时间复杂度为O(nlogn)且稳定。
基本有序序列的最佳排序算法答案：A 插入排序对基本有序序列效率最高，接近O(n)。
二分查找复杂度答案：A 二分查找时间复杂度为O(log₂n)。
无向完全图边数答案：B n个顶点的无向完全图有n(n-1)/2条边。
Dijkstra算法最先求出的最短路径答案：D 根据Dijkstra算法，会先求出1号顶点到其直接邻接点(2号)的最短路径。

二、填空题解析

两个串相等的含义长度相等且对应位置的字符相同。
串存储所需最小数组长度 10(包括结束符'\0')。
矩阵元素地址计算 A[20,2]的地址 = 1000 + [(20-1)*20 + (2-1)]_2 = 1000 + 381_2 = 1762。
完全二叉树右子女下标 2i+1。
17个结点的完全二叉树高度 5(⌊log₂17⌋+1)。
只有度为0和2的二叉树结点数 2h-1。
表达式二叉树求值表达式为a*(b-(c+d))，值为2*(6-(4+2))=0。
AVL树最少结点数高度为5的AVL树最少有12个结点。
树叶子结点在二叉链表中的特征左右指针域均为空。
拓扑序列根据图示，拓扑序列为1,2,3,5,4,6,9,7。
下三角矩阵压缩存储空间 n(n+1)/2+1。
邻接矩阵中计算结点度数统计第j列或第j行中非零元素的个数。
邻接表存储的DFS时间复杂度 O(n+e)，n为顶点数，e为边数。
单次BFS可访问所有顶点的图连通图。
快速排序思想分治法，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小。

三、应用题解析

选择排序过程初始序列：65,38,97,76,13,27 第1趟：13,38,97,76,65,27 第2趟：13,27,97,76,65,38 第3趟：13,27,38,76,65,97 第4趟：13,27,38,65,76,97 第5趟：13,27,38,65,76,97(已有序)
程序段时间复杂度分析 x++语句的执行次数为： Σ(i=1→n-1)(2n+1) = (n-1)(2n+1) ≈ 2n² 时间复杂度为O(n²)。
哈希表构造使用H(K)=K mod 7和二次探测法：
- 23 mod 7=2 → 位置2
- 14 mod 7=0 → 位置0
- 9 mod 7=2 → 冲突，探测2+1²=3 → 位置3
- 6 mod 7=6 → 位置6
- 30 mod 7=2 → 冲突，探测2+1²=3(已占用)，2+2²=6(已占用)，2+3²=11 → 位置1
- 18 mod 7=4 → 位置4 最终哈希表： 0:14, 1:30,2:23, 3:9, 4:18, 6:6
图的遍历和度数从v5出发的DFS序列：v5,v2,v3,v4,v1,BFS序列：v5,v2,v3,v1,v4,V3的度为3
初始堆建立初始序列：Zhao,Qian,Sun,Li,Zhou,Wu,Zheng,Wang 初始堆(小根堆)： Li /

Qian Sun / \ /

Wang Zhao Wu Zheng / Zhou
二叉树构造与遍历根据前序ABCDEGF和中序CBEGDFA构建的二叉树： A /

B D \ /

C E F /

G D 后序遍历序列：C,G,E,F,D,B,A
哈夫曼树与带权路径长度哈夫曼树构造过程：
1. 合并4和5(9)
2. 合并6和7(13)
3. 合并9和12(21)
4. 合并13和21(34) 带权路径长度： 4_3 + 5_3 + 6_2 + 7_2 + 12*2 = 12+15+12+14+24 = 77
Prim算法求最小生成树从顶点1开始：
1. 选择边(1,2)权值1
2. 选择边(2,4)权值2
3. 选择边(4,3)权值1
4. 选择边(3,5)权值4 最小生成树总权值：1+2+1+4=8

四、算法题解析

链表反转算法分析该算法功能：反转单链表。实现方法：
- 使用栈暂存链表所有元素
- 然后依次弹出栈中元素并重新赋值给链表结点时间复杂度O(n)，空间复杂度O(n)

二叉树转换为二叉排序树


typedef struct BiTNode {

    int data;

    struct BiTNode lchild, rchild;

} BiTNode, *BiTree;



void SwapSubtree(BiTree T) {

    if(T) {

        BiTree temp = T->lchild;

        T->lchild = T->rchild;

        T->rchild = temp;

        SwapSubtree(T->lchild);

        SwapSubtree(T->rchild);

    }

}



void TransformToBST(BiTree T) {

    if(T == NULL) return;

    SwapSubtree(T);

}

该算法通过递归交换每个结点的左右子树，将中序遍历递减的二叉树转换为递增的二叉排序树。