湖南工业大学科技学院《计算机科学》27年模拟卷

一、判断题（每小题2分，共10小题，20分。正确打√，错误打×）

1. 算法的时间复杂度取决于问题规模和输入数据的初始状态。 （　）

2. 在单链表中，删除某个给定结点（已知结点指针）的时间复杂度为O(1)。 （　）

3. 循环队列中，队空的条件是 rear == front，队满的条件是 (rear+1) % maxsize == front。 （　）

4. 已知一棵二叉树的前序遍历序列和后序遍历序列，可以唯一确定这棵二叉树。 （　）

5. 在哈夫曼树中，权值最小的两个结点一定是兄弟结点。 （　）

6. 对同一个有向图，若采用邻接表存储，则拓扑排序的结果序列是唯一的。 （　）

7. 折半查找的判定树一定是平衡二叉树。 （　）

8. 希尔排序过程中，整个序列的“逆序对”数量会逐渐减少，但最后一趟排序前序列不一定完全有序。 （　）

9. 稀疏矩阵的三元组表示法中，每个非零元素用一个三元组 (row, col, value) 表示，且所有三元组按行优先（或列优先）存放。 （　）

10. 基数排序的时间复杂度与关键字位数和基数有关，是一种稳定的排序算法。 （　）

二、单选题（每小题4分，共10小题，40分）

1. 下列程序段的时间复杂度为（　）。

   c

   for(i=1; i<=n; i*=2)
       for(j=1; j<=i; j++)
           sum++;

   A. O(n) B. O(n log n) C. O(log n) D. O(n²)

2. 一个栈的入栈序列为1,2,3,...,n，其出栈序列的第一个元素是n，则第i个出栈元素是（　）。
   A. n-i B. n-i+1 C. i D. 不确定

3. 用带头结点的单链表表示队列（队尾插入，队头删除），则判断队空的条件是（　）。
   A. front == rear B. front->next == NULL C. rear->next == NULL D. front == rear->next

4. 一棵完全二叉树有1000个结点，则叶子结点的个数为（　）。
   A. 500 B. 501 C. 499 D. 无法确定

5. 已知一棵二叉树的中序遍历序列为 DBEAFCG，后序遍历序列为 DEBFGCA，则其前序遍历序列为（　）。
   A. ABCDEFG B. ABDECFG C. ABDCEFG D. ABDCFEG

6. 在图的邻接表表示中，每个顶点链表中结点的个数等于该顶点的（　）。
   A. 入度 B. 出度 C. 度数 D. 边数

7. 用Dijkstra算法求从某个源点到其余各顶点的最短路径时，当所有边权值均相等时，该算法等同于（　）。
   A. 深度优先遍历 B. 广度优先遍历 C. Prim算法 D. 拓扑排序

8. 对关键字序列 {49, 38, 65, 97, 76, 13, 27, 49} 进行快速排序，以第一个关键字为枢轴，则第一趟排序后的结果为（　）。
   A. {13,27,38,49,49,65,76,97} B. {27,38,13,49,76,97,65,49} C. {38,27,13,49,49,65,97,76} D. {13,27,38,49,76,97,65,49}

9. 下列排序算法中，每趟都能确定一个元素在其最终位置上的算法是（　）。
   I. 直接插入排序 II. 冒泡排序 III. 快速排序 IV. 简单选择排序
   A. II、IV B. II、III、IV C. I、III D. I、II、IV

10. 设哈希表长为11，哈希函数 H(key)=key%11，采用线性探测再散列解决冲突。依次插入关键字 {19, 14, 23, 1, 68, 20, 84, 27, 55, 11}，则查找失败的平均查找长度为（　）。
    A. 6.0 B. 6.2 C. 6.5 D. 6.8

三、填空题（每空4分，共10空，40分）

1. 在长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个元素，需要移动________个元素；删除第i个元素需要移动________个元素。

2. 已知广义表 L = (a, (b, c, d), e)，则 head(tail(tail(L))) 的结果为________。

3. 一棵深度为k的满二叉树，其叶子结点个数为________，所有结点总数为________。

4. 有n个顶点的连通无向图，至少需要________条边才能保证是连通的；若图是强连通有向图，则至少需要________条边。

5. 对包含n个元素的有序顺序表进行折半查找，其最大比较次数为________，平均查找长度约为________（用n表示近似值）。

6. 对数字序列 {3, 1, 4, 1, 5, 9, 2, 6} 进行希尔排序，第一趟增量d=3，则排序后结果为________。

四、应用题（共5小题，每小题10分，50分）

1. （10分） 给定权值集合 {2, 3, 5, 7, 11, 13}，构造一棵哈夫曼树，并计算其加权路径长度（WPL）。要求画出构造过程中的每一步。

2. （10分） 已知有向图G的邻接矩阵如下（顶点编号A~E，0表示无直接边，数字表示权值）：

   text

   A B C D E

A 0 6 1 5 0
B 0 0 0 2 0
C 0 0 0 4 3
D 0 0 0 0 2
E 0 0 0 0 0

（1）画出该有向图；  
（2）求顶点A到其余各顶点的最短路径（写出Dijkstra算法的详细过程，包括每一步的dist数组和已选顶点集合）。

3. （10分） 一棵二叉树的先序遍历序列为 `ABDGCEHIF`，中序遍历序列为 `DGBAHEICF`。  
（1）画出这棵二叉树；  
（2）写出其后序遍历序列；  
（3）将该二叉树转换为对应的森林（或树）。

4. （10分）已知记录的关键字序列为 `{50, 26, 38, 80, 70, 90, 10, 60, 45, 35}`，请采用**快速排序**（以第一个元素为枢轴，每趟递归以左右子序列的第一个元素为枢轴）手工模拟整个排序过程，写出每一趟排序后的序列状态。

5. （10分） 设一个有序表 `{5, 10, 19, 21, 31, 37, 42, 48, 50, 52}`，采用折半查找算法：  
（1）画出折半查找的判定树；  
（2）求等概率下查找成功的平均查找长度（ASL）；  
（3）查找关键字50的过程需要比较哪些元素？依次写出。


五、编程题（共2小题，每小题25分，50分）

注意：所有代码使用C语言编写，要求结构清晰，关键步骤注释。

 1. 链式队列的实现与应用（25分）

假设用带头结点的单链表实现队列，结点定义如下：
```c
typedef struct QNode {
 int data;
 struct QNode *next;
} QNode, *QueuePtr;

typedef struct {
 QueuePtr front;  // 队头指针（指向头结点）
 QueuePtr rear;   // 队尾指针
} LinkQueue;

请编写函数实现以下功能，并写出完整的测试代码（在主函数中调用）：

• void InitQueue(LinkQueue *Q)：初始化一个空队列；

• void EnQueue(LinkQueue *Q, int e)：入队操作；

• int DeQueue(LinkQueue *Q, int *e)：出队操作，成功返回1，失败返回0；

• 应用要求：使用上述队列，模拟“约瑟夫环”问题：n个人编号1~n围成一圈，从第1个人开始报数，数到m的人出列，然后从下一个人继续报数，直到全部出列。请利用队列（将编号依次入队，然后循环出队再入队的方式） 输出出队顺序。函数原型：void Josephus(int n, int m)。

要求：分析时间复杂度，并给出运行示例（n=7，m=3，输出应为 3 6 2 7 5 1 4）。

2. 二叉树的递归与非递归遍历（25分）

已知二叉树的结点结构：

typedef struct BiTNode {
    char data;
    struct BiTNode *lchild, *rchild;} BiTNode, *BiTree;

（1）编写递归函数 void PreOrder(BiTree T) 实现先序遍历；
（2）编写非递归函数 void InOrderNR(BiTree T) 利用栈实现中序遍历（栈类型可自行定义，说明栈的基本操作即可）；
（3）编写函数 int LeafCount(BiTree T) 递归计算二叉树中叶子的个数；
（4）在主函数中，根据以下扩展先序序列创建二叉树（其中 # 表示空结点）： ABD##E##CF#G###，
分别调用（1）（2）（3）中的函数，并输出结果（先序递归序列、中序非递归序列、叶子个数）。