四川大学期末考试题

(2003-2004学年第二学期)

课程名: 数据结构(A) 计算机科学与技术专业适用 人数: 学院: 专业: 教师姓名: 姓名: 学号: 成绩:

一（9分）、顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下, 对有127个元素的顺序表进行插入, 平均需要移动多少个元素? 删除一个元素, 又平均需要移动多少个元素?

二（9分）、设A和B均为下三角矩阵，每一个都有n行n列。因此在下三角区域中各有n(n+1)/2个元素。另设有一个二维数组C，它有n行n+1列。试设计一个方案，将两个矩阵A和B中的下三角区域元素存放于同一个C中。要求将A的下三角区域中的元素存放于C的下三角区域中，B的下三角区域中的元素转置后存放于C的上三角区域中。并给出计算A的矩阵元素aij和B的矩阵元素bij在C中的存放位置下标的公式。

三（9分）、铁路进行列车调度时, 常把站台设计成栈式结构的站台，如右图所示。试问：

(1) 设有编号为1,2,3,4,5,6的六辆列车, 顺序开入栈式结构的站台, 则可能的出栈序列有多少种?

(2) 若进站的六辆列车顺序如上所述, 那么是否能够得到435612, 325641, 154623和135426的出站序列, 如果不能, 说明为什么不能; 如果能, 说明如何得到(即写出\进栈\或\出栈\的序列)。

四（9分）、列出右图所示二叉树的叶结点、分支结点和每个结点的层次。

五（9分）、在结点个数为n (n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？

六（9分）、试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。

1

七(9分)、写出向堆中加入数据4, 2, 5, 8, 3, 6, 10, 14时，每加入一个数据后堆的变化。

八（9分）、给定一组权值: 23, 15, 66, 07, 11, 45, 33, 52, 39, 26, 58, 试构造一棵具有最小带权外部路径长度的扩充4叉树, 要求该4叉树中所有内部结点的度都是4, 所有外部结点的度都是0。这棵扩充4叉树的带权外部路径长度是多少?

九（9分）、 给出右图的邻接矩阵、邻接表和邻接多重表表示。

A B C D E F 十（9分）、对于如右图所示的有向图，试写出：

① (1) 从顶点①出发进行深度优先搜索所得到的深度优先生成树； ② (2) 从顶点②出发进行广度优先搜索所得到的广度优先生成树；

④ ③ ⑤

十一（10分）、设在4地(A, B, C, D)之间架设有6座桥，如图所示：

A

② ④

⑥

C ①

B ③

⑤

D

要求从某一地出发，经过每座桥恰巧一次，最后仍回到原地。 (1) 试就以上图形说明：此问题有解的条件什么？ (2) 设图中的顶点数为n，试用C描述与求解此问题有关的数据结构并编写

一个算法，找出满足要求的一条回路。

2