2026 年 4 月高等教育自学考试 《数据结构试题》参考答案 课程代码：13181 一、单项选择题（共 10 小题，每小题 2 分，共 20 分） 题号 答案 解析 1 C 算法至少有一个输出值 带头结点单循环链表，p 指 2 B 向尾结点时 p->next==head 循 环 队 列 空 的 条 件是 3 D rear==front 4 A 三元组表用一维数组存储 n 个结点共有 2n 个指针域， 5 C 非空指针=分支数=79，空指 针=2×80-79=81 图的遍历是从某顶点出发对 6 D 每个顶点访问且仅一次 7 D 生成树边数为 n-1 稳定排序不改变相同元素的 8 B 相对位置 分块查找要求块间有序，块 9 B 内无序 10 A 哈希表采用数组存储结构 二、填空题（共 10 空，每空 2 分，共 20 分） 题号 答案 11 哈希（或：散列） 2（元素 3 在 s 中的下标/位置，根据具体定 12 义填写） 13 入栈 14 空表 15 中序 16 权值 17 对称 18 升序 19 n+m 20 叶子（最底层非叶结点） 三、解答题（共 5 小题，每小题 6 分，共 30 分） 21. 数组地址计算 A[1][4]地址=2000，每个元素 4 字节，行主序地址公式：Loc(A[i][j]) = Loc(A[0][0]) + (i×列数 + j)×4 已 知 ： A[1][4] = Loc(A[0][0]) + (1×5 + 4)×4 = Loc(A[0][0]) + 9×4 = Loc(A[0][0]) + 36 = 2000∴ Loc(A[0][0]) = 1964A[7][3] = 1964 + (7×5 + 3)×4 = 1964 + (35+3)×4 = 1964 + 152 =2116 22. Kruskal 算法求解过程 1. 将图 G 中所有边按权值从小到大排序 2. 初始化生成树边集合 E1 为空 3. 依次取最小权值边，若加入后不形成环则加入 E1 4. 重复直到 E1 包含 n-1 条边 23. 广义表表头和表尾 (1) A=(3,5)：表头=3，表尾=(5)(2) B=(m',(2,3,1))：表头=m'，表尾=((2,3,1))(3) C=(A)：表头=A， 表尾=() 24. 最大堆的构建 初始序列：73,14,21,2,5,34,44,52,61 从最后一个非叶结点开始调整，最终最大堆（层序）： 73├─61│ ├─52│ └─14└─44├─34└─21 25. 二叉查找树平均查找长度 设树 a 查找成功平均长度 = L₁，树 b = L₂，树 c = L₃具体数值需根据图 25 的树形结构计算： 平均查找长度 = Σ(深度×结点数)/总结点数（结果保留 1 位小数，需根据实际树形填入） 四、算法阅读题（共 4 小题，每小题 5 分，共 20 分） 26. 单链表删除后续结点算法 空 白 处 应 填 ： (1) temp = current->next;(2) current->next = temp->next;(3) *x = temp->data; free(temp); 27. 对顶栈出栈算法 空白处应填：(1) flag == -1 && mys->lefttop == -1(2) flag == 1 && mys->righttop == maxSize(3) *x = mys->element[mys->lefttop--]; 28. 二叉树 fun 函数分析 (1)功能：计算二叉树中度为 1 的结点个数（只有一个子树的结点数）(2) 根据题 28 图计算 度为 1 的结点个数，填入数字 29. 二叉树 fun 函数分析 (1)功能：中序遍历二叉树，输出结点数据(2) 根据题 29 图，中序遍历输出序列，如：左边 数据，中间根，右边数据 五、算法设计题（10 分） 30. 删除单链表中元素值重复的结点 void deleteDuplicates(LinkList head) { LinkNode *p, *q, *temp; if (head == NULL || head->next == NULL) return; p = head->next; // 从第一个结点开始 while (p != NULL) { q = p; while (q->next != NULL) { if (q->next->data == p->data) { temp = q->next; q->next = temp->next; free(temp); } else { q = q->next; } } p = p->next; }}