数据结构03-04期末考试B答案.doc

四川大学期末考试题解答
(2003-2004学年第二学期)
课程名: 数据结构(B) 计算机科学与技术专业适用 人数:
学院: 专业: 教师姓名:
姓名: 学号: 成绩:
一、 设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，……，如此反复直到所有的人全部出局为止。下面要解决的Josephus问题是对于任意给定的n, s和m，求出这n个人的出局序列。请以n = 9, s = 1, m = 5为例，人工模拟Josephus的求解过程以求得问题的解。（9分）
【解答】
出局人的顺序为5, 1, 7, 4, 3, 6, 9, 2, 8。

二、 列出右图所示二叉树的叶结点、分支结点和每个结点的层次。（9分）
【解答】
二叉树的叶结点有⑥、⑧、⑨。分支结点有①、②、③、④、⑤、⑦。 结点①的层次为0；结点②、③的层次为1；结点④、⑤、⑥的层次为2；结点⑦、⑧的层次为3；结点⑨的层次为4。

三.线性表可用顺序表或链表存储。试问：（9分）
(1) 两种存储表示各有哪些主要优缺点?（3分）
(2) 如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？（3分）
(3) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？（3分）
【解答】
(1) 顺序存储表示是将数据元素存放于一个连续的存储空间中，实现顺序存取或(按下标)直接存取。它的存储效率高，存取速度快。但它的空间大小一经定义，在程序整个运行期间不会发生改变，因此，不易扩充。同时，由于在插入或删除时，为保持原有次序，平均需要移动一半(或近一半)元素，修改效率不高。
链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要存储器中还有空间，就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理顺序，只需要保持原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针，修改效率较高。但存取表中的数据元素时，只能循链顺序访问，因此存取效率不高。
(2) 如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用链接存储表示。
如果采用顺序存储表示，必须在一个连续的可用空间中为这n个表分配空间。初始时因不知道哪个表增长得快，必须平均分配空间。在程序运行过程中，有的表占用的空间增长得快，有的表占用的空间增长得慢；有的表很快就用完了分配给它的空间，有的表才用了少量的空间，在进行元素的插入时就必须成片地移动其他的表的空间，以空出位置进行插入；在元素删除时，为填补空白，也可能移动许多元素。这个处理过程极其繁琐和低效。
如果采用链接存储表示，一个表的存储空间可以连续，可以不连续。表的增长通过动态存储分配解决，只要存储器未满，就不会有表溢出的问题；表的收缩可以通过动态存储释放实现，释放的空间还可以在以后动态分配给其他的存储申请要求，非常灵活方便。对于n个表(包括表的总数可能变化)共存的情形，处理十分简便和快捷。所以选用链接存储表示较好。
(3) 应采用顺序存储表示。因为顺序存储表示的存取速度快，但修改效率低。若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时采用顺序存储表示较好。

四、 设有一个双端队列，元素进入该队列的顺序是1, 2, 3, 4。试分别求出满足下列条件的输出序列。（9分）
(1) 能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列；（3分）
(2) 能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列；（3分）
(3) 既不能由输入受限的双端队列得到，又不能由输出受限的双端队列得到的输出序列。（3分）
【解答】
允许在一端进行插入和删除，但在另一端只允许插入的双端队列叫做输出受限的双端队列，允许在一端进行插入和删除，但在另一端只允许删除的双端队列叫做输入受限的双端队列。
end1 end2

输出受限的双端队列
end1 end2

输入受限的双端队列

输出受限双端队列不能得到的输出序列有：
4 1 3 2 4 2 3 1
输人受限双端队列不能得到的输出序列有：
4 2 1 3 4 2 3 1
所以有：
(1) 4 1 3 2
(2) 4 2 1 3
(3) 4 2 3 1
五、 使用 (1) 顺序表示和 (2) 二叉链表表示法，
分别画出右图所示二叉树的存储表示。（9分）

【解答】
0 1 2 3 4 5 6 7 8 9
①

① ② ③ ④ ⑤ ⑥ ⑦
∧
③
②

10 11 12 13 14 15 16 17 18
∧
⑤
∧
⑥
∧
∧
④

⑧ ⑨
∧
∧
∧
⑧
⑦

顺序表示

二叉链表表示
∧
∧
⑨

六、 试分别找出满足以下条件的所有二叉树:（9分）
(1) 二叉树的前序序列与中序序列相同;(3分)
(2) 二叉树的中序序列与后序序列相同;（3分）
(3) 二叉树的前序序列与后序序列相同。（3分）
【解答】
(1) 二叉树的前序序列与中序序列相同：空树或缺左子树的单支树；
(2) 二叉树的中序序列与后序序列相同：空树或缺右子树的单支树；
(3) 二叉树的前序序列与后序序列相同：空树或只有根结点的二叉树。

七、 已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAFHIGJ, 试画出这棵二叉树。（9分）
【解答】
当前序序列为ABECDFGHIJ，中序序列为EBCDAFHIGJ时，逐步形成二叉树的过程如下图所示：
A
A
A
A

F
B
B
F
F
B

G
E
C
G
E
C
HIGJ
CD
E
FHIGJ

H
D
J
HI
J
D

I
EBCD

八、给定权值集合{15, 03, 14, 02, 06, 09, 16, 17}, 构造相应的霍夫曼树, 并计算它的带权外部路径长度。（9分）

【解答】
(Ⅰ)
05
17
16
09
06
14
15
F：
17
16
09
06
02
14
15

02
03
03

(Ⅱ)
17
16
09
14
15

20
16
14
15
(Ⅲ)
17
11

09
11
06
05

02
03

06
05

(Ⅴ)
33
20
29
02
03
29
16
17
20
(Ⅳ)

16
17
11
09
15
14
14
11
09
15

05
06

06
05

02
03
02
03

(Ⅰ)
05
17
16
09
06
14
15
F：
17
16
09
06
02
14
15

02
03
03

(Ⅱ)
17
16
09
14
15

20
16
14
15
(Ⅲ)
17
11

09
11
06
05

02
03

06
05

(Ⅴ)
33
20
29
02
03
29
16
17
20
(Ⅳ)

16
17
11
09
15
14
14
11
09
15

05
06

06
05

02
03
02
03

82

(Ⅶ)
49
33
(Ⅵ)
49
33

17
29
20
16
17
16
29
20

14
11
09
15
11
09
15
14

06
05

06
05

03
02
03
02

此树的带权路径长度WPL = 229。

九、 画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。试证明在n个顶点的无向完全图中，边的条数为n(n-1)/2。（9分）
【解答】

2个顶点的
无向完全图

1个顶点的
无向完全图

5个顶点的
无向完全图

4个顶点的
无向完全图

3个顶点的
无向完全图

【证明】
在有n个顶点的无向完全图中，每一个顶点都有一条边与其它某一顶点相连，所以每一个顶点有n-1条边与其他n-1个顶点相连，总计n个顶点有n(n-1)条边。但在无向图中，顶点i到顶点j与顶点j到顶点i是同一条边，所以总共有n(n-1)/2条边。

十、 有n个顶点的无向连通图至少有多少条边？有n个顶点的有向强连通图至少有多少条边？试举例说明。（9分）
【解答】
n个顶点的无向连通图至少有n-1条边，n个顶点的有向强连通图至少有n条边。例如：

特例情况是当n = 1时，此时至少有0条边。

十一、以邻接表为存储结构，写一个基于DFS遍历策略的算法，求图中通过某顶点vk的简单回路（若存在）。（10分）
解：
算法思想，从给定顶点v4出发进行深度优先搜索，在搜索过程中判断当前访问的顶点是否为v4。若是，则找到一条回路。否则继续搜索。为此设一个顺序栈cycle记录构成回路的顶点序列，把访问顶点的操作改为将当前访问的顶点入栈；相应地，若从某一顶点出发搜索完再回溯，则做退栈操作，同时要求找到的回路的路径应大于2。另外还设置一个found，出值为0，当找到回路后为1。
Void dfscycle (ALGrph *G,int V4)
{int i,j,top=0,V=V4,found=0,w;
int Visitde[100],cycle[100];
EdgeNode *P;
i=1;
cycle[i]=Vi /*从V是开始搜索*/
Visitde[v]==1;
P=G[v]->firstedge;
While(p!=NULL!!top>0)&&!found)
{ while(p!=NULL&&!found)
if(p->adjvex==V4&&i<2)found=1; /*找到回路*/
else if(visited[p->adjvex]==0)p=p->next; /*找到下一个邻接点*/
elst
{w=p->adjvex; /*记下路径，继续搜索*/
visited[w]=1;
i++;
cycle[i]=w;
top++;
stack[top]=p;
p=G[w]->firstedge;
}
if(!found&&top>0) /*沿原路径退回后，另选路径进行搜索*/
{ p=attack[top];
top--;
p=p->next;
i--;
}
} /*end while*/
if(found)
{for(j=1;j<=i;j++)
printf(“%d,”,cycle[j]); /*打印回路的顶点序列*/
printf(“%d,\n”,V);
}
else printf(“设有通过点V4的回路！\n”)
}