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

一、填空题（20分，每题2分）

  1. 已知广义表 A=((1,2),((a,b),c),d,e)，则执行 GetHead(GetHead(GetTail(A))) 操作后，所得结果的深度为 ，宽度为 。

  2. 设有数据结构 (D,R)，其中 D=(d1,d2,d3,d4)，R=(r)，r=((d1,d2),(d2,d3),(d3,d4))，以四种基本结构分类，该结构为 结构。

  3. 已知 L 是带表头结点的非空双向链表，Q 是 P 的直接后继结点，P 和 Q 结点都既不是首元素结点，也不是尾元素结点，则在删除 Q 结点的语句序列是 , Q->next->prior=P, free(Q)。

  4. 分析以下代码段中前置有记号 @ 的语句，按大 O 表示法，其时间复杂度为 。

for(i=1;i<=n;i++){
	for(j=1;j<=i;j++){
		@ x+=delta;
	}
}

  1. 二维数组 A 的下标取值范围分别为 0 到 7，以及 0 到 4，已知数组每个元素占 8 个字节，且已知数组按列优先次序存储在起始地址为 1020 的内存单元中，则元素 A[5][3] 的地址是 。

  2. 设有二叉树的顺序存储结构如下图所示，其中 ∅ 表示该处无节点元素。则节点 d 的双亲是 ，节点 e 的右孩子是 。

1234567891011
Abcde∅∅∅∅fg
  1. 已知图 G 的逆邻接表如下，其中顶点集为 {1,2,3,4,5,6}，顶点序号从 1 开始，则该有向图中含有 【暂无答案】 个强连通分量。

题图1.7

题图1.7
  1. 已知树的双亲表示如下，则树的度为 【暂无答案】，高度为 【暂无答案】。
012345678910
ABCDEFGHIJK
-10001334446

  1. 根据初始关键字序列 (07,22,03,04,38,10) 建立的二叉排序树的高度为 。

  2. 堆排序算法的时间复杂度平均情况下为 【暂无答案】，最坏的情况下为 【暂无答案】。

二、选择题（20分，每题2分）

  1. 为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是 ( )。
  1. 设用链表作为栈的存储结构，则退栈操作 ( )。
  1. 广义表 (a,(b,(c,d,(e,f)),g)) 的深度是 ( )。

题图2.4

题图2.4
  1. 给定二叉树图所示，设 N 代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为 3,1,7,5,6,2,4，则其遍历方式是 ( )。
  1. 将二叉树 T 转换为对应的森林 F，F 中叶结点的个数等于 ( )。
  1. 下列说法不正确的是 ( )。
  1. 下列排序算法中，元素的移动次数与关键字的初始排列次序无关的是 ( )。
  1. 下列查找方法中 ( ) 适用于查找单链表。
  1. 中缀表达式 (A+B)*(C-D)/(E-F*G) 的后缀表达式是 ( )。
  1. 设栈 S 和队列 Q 的初始状态均为空，元素 abcdefg 依次进入栈 S。若每个元素出栈后立即进入队列 Q，且 7 个元素出队的顺序是 bdcfeag，则栈 S 的容量至少是 ( )。

三、简答题（30分，每题6分）

1.

已知一棵二叉树的前序遍历和中序遍历序列分别为：ABCDEFG 和 CBDAEGF。请画出二叉树。

答案 / 解析

2.

题图3.2

题图3.2

已知如图所示的带权无向图，请画出用普里姆算法从顶点 1 开始的最小生成树的构造过程。

3.

题图3.3

题图3.3

设散列函数为 H(key)=key%11，散列地址空间为 HT(11)（第一个元素下标为 O），对关键字序列 (27,13,55,32,18,49,24,38,43) 用线性探查法解决冲突，构建散列表。现在前4个关键字已经插入散列表，如图所示。

  1. 请将剩余5个关键字依次插入散列表中。请写出每个关键字插入的必要步骤，并将关键字填入图中相应位置。
  2. 若查找各关键字的概率相等，请计算该散列表的平均查找长度(ASL)。

4.

设 Q 是有 N 个存储空间的循环队列，定义如下：

#define N 100
typedef struct
{
	char data[N];
	int front, rear;
}CQ;
CQ*Q;

初始状态 Q->front=Q->rear=0，约定指针 Q->rear 指向的单元始终为空（预留最后一个单元来标识队列满）。

  1. 请写出清空队列的语句。
答案 / 解析 
    Q->rear=Q->front
  1. 请写出判断队列为满的表达式。
答案 / 解析 
    (Q->rear+1)%N==Q->front
  1. 请写出计算队列长度的表达式。
答案 / 解析 
    ( Q->rear - Q->front + N)%N

5.

对关键字序列 (26, 18, 60, 14, 7, 45, 13, 32) 进行堆排序，要求从小到大排序，请写出构建的初始堆（大顶堆）及前两趟重建堆之后的堆状态。（用树型结构画出堆的状态，并写出必要的步骤）

  1. 初始堆
  2. 第一趟
  3. 第二趟

四、程序设计（10分）

假设以带头结点的单链表表示有序表，单链表的类型定义如下：

typedef struct node{
	DataType data;
	struct node *next;
}LinkNode, *LinkList;

试编写算法，从有序表 A 中删除所有和有序表 B 中元素相同的结点。

答案 / 解析 
void DeleteCommon(LinkList &A, LinkList B) {
    LinkList pa, pb, prev, tmp;
    pb = B->next;
    while (pb != NULL) {
        prev = A;
        pa = A->next;
        while (pa != NULL) {
            if (pa->data == pb->data) {
                prev->next = pa->next;
                tmp = pa;
                pa = pa->next;
                free(tmp);
            } else {
                prev = pa;
                pa = pa->next;
            }
        }
        pb = pb->next;
    }
}

五、应用题（20分，每题10分）

1.

题图5.1

题图5.1

请根据下图所示森林回答下列问题。

  1. 求树 (a) 的先根序列和后根序列；
答案 / 解析

ABEJKLFMNCGDHOI JKLENMFBGCOHIDA

  1. 求森林先序序列和中序序列；
答案 / 解析

ABEJKLFMNCGDHOIPQRSTU JKLENMFBGCOHIDAQSTURP

  1. 将此森林转换为相应的二叉树。
答案 / 解析

2.

题图5.2

题图5.2

已知图 G 如下图所示，求从顶点 A 到其余各顶点的最短路径。（要求给出迪杰斯特拉算法求解过程）