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 -