26-27-1-数据结构-期中

一、选择题(每空 3 分,共 30 分)

  1. 下列程序的时间复杂度是 ( )。

    int i=0;
    while( i*i*i <= n) i++;
  2. 在存储数据时,不仅要存储各数据元素的值,还要存储 ( )。

  3. 用栈求表达式的值时,顺序存储的运算数栈 OPND。假设 OPND 只有两个存储单元,最多同时放两个运算数。不会发生溢出的是 ( )。

  4. 高为 hh 的二叉树上只有度为 00 和度为 22 的结点,结点数至少为 ( )。

  5. 二维数组 A 按行优先方式存储,每个元素占用 1 个存储单元。A[0][0] 的地址是 100(十进制表示),A[3][3] 的地址是 220,元素 A[5][5] 的地址是 ( )。

  6. 已知 L 是带头结点的非空单链表,P 结点既不是首结点,也不是尾结点。

    • a. 删除 P 结点的直接后继结点的语句序列是 【暂无答案】。
    • b. 删除 P 结点的直接前驱结点的语句序列是 【暂无答案】。
    • c. 删除 P 结点的语句序列是 【暂无答案】。
    • d. 删除首结点的语句序列是 【暂无答案】。
    • e. 删除尾结点的语句序列是 【暂无答案】。

    备选语句序列:

    • (1) P=P->next;
    • (2) P->next = P;
    • (3) P->next = P->next->next;
    • (4) P = P->next->next;
    • (5) While (P != NULL) P=P->next;
    • (6) While (Q->next != NULL) Q = Q->next;
    • (7) While (P->next != Q) P = P->next;
    • (8) While (P->next->next != Q) P = P->next;
    • (9) While (P->next->next != NULL) P = P->next;
    • (10) Q = P;
    • (11) Q = P->next;
    • (12) P = L;
    • (13) L = L->next;
    • (14) free(Q);

二、判断题(每题 2 分,共 20 分)

  1. 在相同规模 nn 下,复杂度为 O(n)O(n) 的算法在时间上总是优于复杂度为 O(2n)O(2^n) 的算法。【暂无答案】
  2. 若广义表 LL 的表头和表尾均为广义表,则 LL 的长度一定为 2。【暂无答案】
  3. 在完全二叉树中,若一个结点没有左孩子,则它必是叶结点。【暂无答案】
  4. 在中序线索树中,若某结点有左孩子,则其前驱结点是它的左子树的最左下结点。【暂无答案】
  5. 对于一个线性表,既要能够进行较快速的插入和删除,又要求存储结构能反映数据之间的逻辑关系,则选用链式存储结构比选用顺序存储结构更合适。【暂无答案】
  6. 给链表加上头结点的目的是为了起到标识的作用。【暂无答案】
  7. 只有那种使用了全局变量的递归过程在转换成非递归过程时才必须使用栈。【暂无答案】
  8. 深度为 kk 具有 nn 个结点的完全二叉树,其编号最小的叶子结点序号为 ⌊2k−2⌋+1\lfloor 2^{k-2} \rfloor + 1。【暂无答案】
  9. 稀疏矩阵以三元组压缩存储后,必会失去随机存取功能。【暂无答案】
  10. 用六叉链表表示 30 个结点的六叉树,则树中共有 151 个空指针。【暂无答案】

三、(15 分)

在线性表的顺序存储中,编写一个辅助函数 MoveElements,用于完成插入和删除的数据移动工作,自行设计函数参数,返回值用 ture 表示成功,false 表示失败。

typedef struct {
    ElemType *data;
    int length;   // 线性表当前长度(元素个数)
    int maxsize;
} SqList;

bool MoveElements(               )

四、(15 分)

某老旧的权限管理系统,采用“左孩子右兄弟”的规则存储部门组织结构在一棵二叉树中。该二叉树的原始结构丢失了,只剩下两份由监控日志生成的遍历序列(注:字母代表部门 ID):

  • 先序遍历序列:A, B, D, F, C, E, G, H
  • 中序遍历序列:B, F, D, A, G, E, H, C
  1. 还原二叉树逻辑结构图。
  2. 根据“左孩子右兄弟”转换规则,将二叉树转换回原始的多级部门管理结构(即原始的多叉树或森林),并画出结构图。
  3. 原系统将多叉树转为二叉树存储有何优势?

五、(10 分)

一张 4×44 \times 4 的灰度图像,每个像素取值为 {0,1,2,3}\{0, 1, 2, 3\},共 4 种灰度值,各灰度出现频次统计如下:灰度值 0、1、2、3 出现次数分别为 6、5、3、2。

  1. 以灰度值频次作为权值,构造哈夫曼树。(要求:画出哈夫曼树)
  2. 给出每个灰度对应的哈夫曼编码。
  3. 计算压缩比:原始总比特/压缩后总比特\text{原始总比特} / \text{压缩后总比特}。(原始总比特为等长编码下,整张图一共需要的比特数,其中每个灰度用等长二进制编码)

六、(10 分)

服务器不断产生访问日志,每条日志包含访问 IP 和时间戳。用带头结点的单链表缓存最近访问过的 IP,实现 IP 去重:同一个 IP 只保留最新一条记录,旧记录删掉。链表规则:带头结点;新成功插入的 IP 放在链表头部(最近访问的 IP 在最前面)。

typedef struct LNode {
    char ip[16]; // IPv4 地址字符串
    int ts;      // 时间戳
    struct LNode *next;
} LNode, *LinkList;
  1. 实现插入日志操作,如果日志已存在,删除原来这条 IP 的旧结点,再新建结点插入链表头部。如果不存在,直接新建结点,插入链表头部。
  2. 这个方案适用于什么场景?有什么缺陷?如果日志量很大,怎么优化?
void Insert(LinkList &h, char * ip, int ts) // h 为头指针