2、 下列序列中，满足堆定义的是

A．（100，86，48，73，35，39，42，57，66，21） B．（12，70，33，65，24，56，48，92，86，33） C．（103，97，56，38，66，23，42，12，30，52，6，26） D．（5，56，20，23，40，38，29，61，35，76，28，100）

二、综合应用题：41~47小题，共70分。 试题示例：

41．（10分）设无向图G=（V，E），其中V={1，2，3，4，5}，E={（1，2，4），（2，5，5），（1，3，2），（2，4，4），（3，4，1），（4，5，3），（1，5，8）}，每条边由一个三元组表示，三元组中前两个元素为与该边关联的顶点，第三个元素为该边的权。请写出图G中从顶点1到其余各点的了短路径的求解过程。要求列出最短路径上的顶点，并计算路径长度。

42.(15分)已知一棵二叉树采用二叉链表存储,结点构造为:

LeftChild Data RightChild ,root指向根结点。现定义二叉树中结点X0 的根路径为从根结点到X0 结点的一条路径，请编写算法输出该二叉树中最长的根路径（多条最长根路径中只输出一条即可。算法可使用C或C + +或JAVA语言实现）。

- 5 -

第 1 章 绪论

一、单选题

1、在数据结构中，从逻辑上可以把数据结构分成

A、动态结构和静态结构

B、紧凑结构和非紧凑结构 D、内部结构和外部结构

C、线性结构和非线性结构 2、算法分析的两个主要方面是

A、空间复杂性和时间复杂性 C、可读性和文档性

B、正确性和简明性

D、数据复杂性和程序复杂性

3、数据的不可分割的最小单位是

A、结点

B、数据元素

C、数据项

D、数据对象

4、在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为

A、规则

B、集合

C、结构

D、运算

5、与程序运行时间有关的因素主要有以下四方面，其中与算法关系密切的是

A、问题的规模

B、机器代码质量的优劣 D、语句的执行次数

C、机器执行速度 二、判断题

1、数据结构是带有结构的数据元素的集合。 2、程序越短，运行的时间就越少。 3、处理同一问题的算法是唯一的。

4、一个完整算法可以没有输入，但必须有输出。 三、填空题

1、______________是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 2、______________结构的数据元素之间存在一对多的关系。

3、数据结构的形式化定义为 (D，S)，其中 D 是______________的有限集，S 是 D 上关系的有限集。

4、数据结构在计算机中的______________称为存储结构。

5、数据元素之间的关系在计算机中有两种不同的表示方法：顺序映象和非顺序映象，由此

- 6 -

得到两种不同的存储结构是______________存储结构和______________存储结构。 6、一个算法具有五个特性：______________、______________、______________、有零个或多个输入、有一个或多个输出。

7、评价一个算法的好坏应该从算法的正确性、可读性、___________和_________________等几方面进行。 四、解答题

1、设n为正整数。试确定下列各程序段中前置以记号@的语句的频度： ⑴ i=1；

k=0； while (i<=n-1) {

@ k+=10*i； i++； } ⑵ i=1；

k=0； do {

@ k+=10*i； i++； } while (i<=n-1)； ⑶ i=1；

k=0； while (i<=n-1) { i++； @ k+=10*i； } ⑷ k=0；

for (i=1；i<=n；i++) {

for (j=i；j<=n；j++) @ k++；

- 7 -

}

2、阅读以下算法： void fun(int n) {

int i，j，k，s，x； for (s=0，i=0；i

j=n； x=0； while (i

printf(\，x=%d\\n\，s，x)； }

⑴分析算法中语句“s++；”的执行次数； ⑵分析算法中语句“x+=2；”的执行次数； ⑶分析算法的时间复杂度。

五、算法设计题

编程实现课本例1-7所描述的抽象数据类型Triplet，并完成以下功能，要求有菜单提示： ⑴初始化三元组为 (100，200，300)； ⑵获取第二个元素值并输出； ⑶置第三个元素值为 150； ⑷获取第三个元素值并输出； ⑸获取最大元素值并输出； ⑹获取最小元素值并输出； ⑺撤销三元组。

- 8 -