湖南工学院《程序设计综合》27年模拟卷

一、选择题（共15题，每题3分，共45分）

1.以下关于C语言指针的叙述中，错误的是（ ）。

A. 指针变量可以指向同类型的不同变量
B. 指针变量可以指向数组元素
C. 指针变量可以指向函数，但该函数返回值必须是指针类型
D. 指针变量可以指向结构体变量

2.若有定义 int a[5] = {1, 2, 3, 4, 5}, *p = a + 2; 则表达式 *(p + 1) 的值是（ ）。
A. 3  B. 4  C. 5  D. 随机值

3.已知二叉树的前序遍历序列为 ABDEGCFH，中序遍历序列为 DBGEACHF，则该二叉树的后序遍历序列为（ ）。
A. DGEBHFCA B. DGEBHFCA C. DGEBHFCA D. 以上都不对（需自行计算）

4.下列排序算法中，最坏情况下时间复杂度最低的是（ ）。
A. 直接插入排序 B. 冒泡排序 C. 堆排序 D. 快速排序

5.关于递归函数，以下说法正确的是（ ）。
A. 递归函数必须包含循环语句
B. 递归函数能解决的问题，循环一定能解决，且效率一定更高
C. 递归函数必须有终止条件，否则会导致栈溢出
D. 递归函数的调用开销总是小于非递归函数

6.在单链表中，删除 p 指针指向结点的后继结点（假设存在），正确的操作是（ ）。
A. p = p->next; free(p);
B. q = p->next; p->next = q->next; free(q);
C. p->next = p->next->next; free(p);
D. free(p->next); p->next = p->next->next;

7.已知哈希函数 H(key) = key % 11，采用线性探测法解决冲突。现有关键字序列 {22, 41, 53, 8, 10, 30} 依次插入长度为11的哈希表，则关键字30的存放位置下标是（ ）。
A. 3  B. 4  C. 5  D. 6

8.循环队列存储在数组 A[0..m] 中，已知队头指针 front 指向队头元素，队尾指针 rear 指向队尾元素的下一个位置，则队列中元素个数为（ ）。
A. (rear - front + m + 1) % (m + 1)
B. (rear - front + m) % m
C. (rear - front + 1) % m
D. (rear - front) % (m + 1)

9.以下关于 const 和指针的描述，正确的是（ ）。
A. const int *p 表示 p 本身不能被修改
B. int * const p 表示 p 指向的内容不能被修改
C. const int * const p 表示 p 和 p 指向的内容都不能被修改
D. 以上都不正确.

10.对于广义表 L = (a, (b, c), d)，取表头 head(L) 和表尾 tail(L) 的结果分别是（ ）。
A. a 和 ((b, c), d) B. (a) 和 ((b, c), d)
C. a 和 (b, c, d) D. (a) 和 (b, c, d)

11.若图 G 有 n 个顶点，采用邻接矩阵存储，其非零元素个数为 e，则图 G 的边数（无向图）为（ ）。
A. e  B. e/2  C. n+e  D. 2e

12.执行以下程序段后，a 的值是（ ）。

int a = 5, b = 2;a = a ^ b;b = a ^ b;a = a ^ b;

A. 2  B. 5  C. 7  D. 3

13.在 KMP 模式匹配算法中，模式串 "ababaab" 的 next 数组值（默认 next[1]=0）为（ ）。
A. 0 1 1 2 3 4 2 B. 0 1 1 2 3 4 5
C. 0 1 1 2 3 1 2 D. 0 1 2 3 4 5 6

14.以下关于分治算法的描述，错误的是（ ）。
A. 分治法将原问题分解为若干规模较小的子问题
B. 子问题之间通常相互独立
C. 快速排序和归并排序都是分治算法的典型应用
D. 分治法一定比动态规划效率高

15.已知有向图的邻接表如下所示（如图，略），从顶点 V1 出发进行深度优先搜索（DFS），得到的顶点序列可能是（ ）。（此处假设邻接表按升序排列）
A. V1, V2, V3, V4 B. V1, V3, V2, V4 C. V1, V2, V4, V3 D. V1, V4, V2, V3

二、填空题（共15空，每空2分，共30分）

16. 若某算法的时间复杂度递推式为 T(n) = 2T(n/2) + n，且 T(1)=1，则 T(n) 的时间复杂度为 ______（用大O表示）。

    
    

17. 在C语言中，语句 printf("%d", sizeof(struct { char c; int i; double d; })); 在 64 位系统下通常输出 ______（假设对齐规则为自然对齐）。

    
    

18. 栈的插入操作也称为 ______，删除操作也称为 ______。

    
    

19. 对于顺序存储的线性表，插入一个元素平均需要移动 ______ 个元素（设表长为 n）。

    
    

20. 下面程序段的输出结果是 ______。

    c

    char *s = "CProgram";printf("%c", *(s + strlen(s) - 3));
    

21. 一棵完全二叉树有 500 个结点，则叶子结点的个数为 ______。

    
    

22. 已知一个图使用 Prim 算法从顶点 A 开始构造最小生成树，已选顶点集为 {A, C, D}，当前候选边的权值分别为 (A-B,5)，(C-E,3)，(D-F,4)，(C-B,2)，则下一条被选中的边是 ______（写出顶点对和权值）。

    
    

23. 若需要频繁地在表尾插入和删除元素，应选用 ______（填“顺序表”或“链表”），理由是 ______。

    
    

24. 执行下列语句后，*p 的值是 ______，**q 的值是 ______。

    c

    int a = 8, b = 12, *p = &a, **q = &p;*p = b;q = &p;**q = 20;
    

25. 希尔排序是一种不稳定的排序算法，其不稳定性主要来源于 ______。

    
    

26. 广义表 A = ((), (a, b), (c, (d, e))) 的长度为 ______，深度为 ______。

    
    

27. 递归函数求斐波那契数列的第 n 项，当 n=5 时，函数被调用的总次数（含外部首次调用）为 ______ 次（假设 fib(0)=0, fib(1)=1）。

三、函数题（共2题，每题20分，共40分）

请按要求编写C语言函数，不写完整程序（除非要求主函数）。

28. （20分）
    编写函数 void reverseK(struct Node *head, int k)，该函数对单链表的每 k 个结点进行反转（不足 k 个的保持原样）。

• 链表结点定义为：

  c

  struct Node {
      int data;
      struct Node *next;};
  

• 要求：只能遍历链表一次，空间复杂度 O(1)。

• 例如：链表为 1→2→3→4→5→6→7，k=3，反转后应为 3→2→1→6→5→4→7。

• 说明：函数参数 head 为头指针，反转后头指针可能改变，函数无需返回新头指针（可通过返回值或其他方式，请自行定义）。建议函数原型为 struct Node* reverseK(struct Node* head, int k)。

29. （20分）
    编写递归函数 int isBalance(struct TreeNode *root)，判断一棵二叉树是否为 平衡二叉树（任意结点的左右子树高度差的绝对值 ≤ 1）。

• 结点定义：

  c

  struct TreeNode {
      int val;
      struct TreeNode *left;
      struct TreeNode *right;};
  

• 函数返回 1 表示平衡，0 表示不平衡。要求同时计算高度，避免重复遍历。

• 提示：可编写辅助函数 int heightAndBalance(struct TreeNode *root, int *balanced) 或返回特殊值（如高度为负数表示不平衡）。

四、应用题（共3题，共50分）

需写出详细步骤或构造过程。

30. （15分）
    已知关键字序列为 {12, 2, 16, 30, 8, 28, 4, 10, 20, 6, 18}，哈希表长度为 13，哈希函数为 H(key) = key % 11，采用 二次探测再散列 处理冲突（di = 1², -1², 2², -2², …）。
    （1）依次插入所有关键字，画出最终的哈希表（下标 0~12，空缺处填“空”）。
    （2）计算等概率查找成功时的平均查找长度 ASL（保留两位小数）。

31. （15分）
    已知带权有向图 G 的邻接矩阵如下（∞表示不可达）：

（1）使用 Dijkstra 算法，求从 V1 到其余各顶点的最短路径长度及路径（写出每一步的 S 集合和 dist 数组变化）。
（2）若要求任意两点间最短路径，可否用 Floyd 算法？请简述 Floyd 的核心思想。

32. （20分）
    设计算法：将一个中缀表达式（只含个位数整数、运算符 + - * / 和括号 ( )）转换为后缀表达式，并计算后缀表达式的值。
    （1）请写出中缀转后缀的核心算法步骤（利用栈，无需代码）。
    （2）对于中缀表达式 (8-3)* (4+2)/2，写出转换后的后缀表达式，并计算最终结果。
    （3）如果表达式中出现多位数（如 123）或负数（如 -5），原有的算法需要做哪些修改？简要说明。

五、程序设计题（共2题，共35分）

要求编写完整的C程序，包括必要的头文件、主函数和清晰的注释。

33. （17.5分）
    编写一个程序，实现以下功能：

• 定义一个结构体 Student，包含学号（int）、姓名（char[20]）、C语言成绩（int）、数据结构成绩（int）。

• 从键盘输入 n（n≤100）个学生的信息。

• 使用指向结构体的指针作为函数参数，编写一个函数 void sortByTotal(Student *arr, int n)，按总分（C语言+数据结构）从高到低排序，若总分相同则按学号升序。

• 输出排序后的学生信息（学号、姓名、总分）。

• 要求：排序算法需自行实现（不可用 qsort），但可以是任何一种稳定排序（如冒泡、插入等）。

• 额外要求：在主函数中动态分配存储学生信息的数组。

34. （17.5分）
    编写一个程序，实现深度优先搜索（DFS）遍历无向图并判断图中是否存在回路。

• 采用邻接表存储图。

• 图由用户输入：第一行两个整数 n, m（顶点数 1≤n≤20，边数 m）；接下来 m 行，每行两个顶点 u, v（1-based）。

• 功能1：从顶点 1 开始 DFS 输出遍历序列（要求非递归或递归均可，但写出清晰代码）。

• 功能2：判断图是否含有回路（环）。若有，输出 "YES"；否则输出 "NO"。

• 提示：可用 visited 数组和 parent 数组，或基于 DFS 的递归栈中的状态（正在访问/已访问完）来判断回路。

• 要求：编写完整程序，包含必要的注释。