25-26-1-数据结构-期末

判断题

  1. 就地算法的特点是不考虑空间复杂度;
  2. 度为2的有序树是二叉树;
  3. 数据对象可以构成数据结构;
  4. 线性表的深度等于其内原子个数;
  5. 在二叉线索树中，一个结点存在右孩子，则该结点的中序后继结点为右子树的最左下结点;
  6. 增加哈希表的装填因子（装载因子），可以提高哈希表的查找效率;

一、

智能家电有八个事件，概率为

ABCDEFGH
0.320.210.190.100.070.060.030.02
  1. 构建赫夫曼编码（4分）；
  2. 构建等长编码并分析压缩率（4分）；
  3. 如果家电也要向手机发送这些信号，但是每个信号是等概率的，是否还可以用相同的赫夫曼编码？为什么？（2分）

二、

六个数二位数，进行排序。

  1. 写出使用快速排序前两趟的结果（4分）；
  2. 写出使用基于低位的基数排序前两趟排序结果（4分）；
  3. 分析快速排序和基于低位的基数排序的稳定性（2分）。

三、

第三题图

第三题图
  1. 写出拓扑排序序列（度数为 0 时把编号小的节点写在前面）；
  2. 给出关键路径以及工期完成时间，要求写出分析过程。

四、

设计函数 CountDegreeTwoNode 返回度数为2的节点数。

typedef struct Tree{
    int data;
    struct tree *lChild, *rChild;
} BitreeNode, *BTree;

int CountDegreeTwoNode(BTree *T);

五、

已知一个带权有向图（或无向图）采用邻接表存储，请设计一个算法，判断顶点 v_i 到顶点 v_j 之间是否存在路径。若存在，请输出该路径（输出任意一条简单路径即可），并返回 true，否则返回 false。

typedef struct arcnode{
    int adjvex;
    int weight;
} arcnode; //邻接表

typedef struct vertexnode{
    int data; //顶点信息
    arcnode* firstarc;
} vertexnode; // 不是这个名字，忘了

typedef vertexnode AdjList[max_length]; // 忘记 max_length 这个常量叫什么名字了

bool FindPath(AdjList *map, int vi, int vj); // 从 vi 到 vj 的路径

六、

旅游推荐系统需要实现一个旅游日记和推荐功能，每篇日记包含内容、热度、评分等信息。

  1. 请选择合适的数据结构（如线性表、树、图等），用 C 语言结构体定义日记的存储结构存储上述信息；
  2. 请设计一个算法 GetTop10，根据“热度”找出排名前 10 的日记并返回，函数传入参数中需要包括日记的指针，热度计算公式由你自行定义（例如与评分和点赞数相关）。
  3. 分析你第 (2) 问中算法的时间复杂度，并从存储结构改进和算法优化两个方面简述优化方案。