一.填空题
1. _集合__、线性结构、__树形结构____ 、图形结构
2.p->next!=NULL
3.时间复杂度和空间复杂度
4.随机存取
5..队尾
6. n-1
二、单选题、
1-5DAACC 6-10DBDDB 11-15DCABD
三，简答题
1、
2、数据是对客观事物的描述形式和编码形式的统称，是算法和程序的处理对象和计算结构。

数据元素又称数据结点，简称结点，通常一个数据结点由用来描述一个独立事的名称、数量、特性、性质的一组相关信息。

多数情况下，一个结点包含有多个数据项，每个数据项是结点的一个域，能够用来唯一标识结点的域称为关键字域。

算法：有穷规则的集合，而规则规定了解决某一特定问题的运算序列。

有穷性：必须在执行有穷步后终止。

确定性：每一步必须具有确定的定义，不能含糊不清，不带二义性。

可行性：所有运算都可以精确地实现。

输出数据：必须有输出数据，包括输出某种动作或控制信号。

输入数据：作为执行前的初始量。

不是必须。

算法有两种表现形式：描述形式和程序形式。

计算时间复杂的的方法：
•支配性语句度量法：在一段程序中，往往有一条语句执行次数最多，话费时间也就是最多，其他语句执行次数的和将不超过这套语句执行次数的常数倍，那么就称这条语句在话费时间上是起支配性作用的典型语句，于是可选这条语句的执行次数作为度量这段程序花费时间的阶。

•
四、应用题
1、
2、、对给定的n个权值bai{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn}，其中du每棵二叉树Ti中只有一个权值zhi为Wi的根结点，
它的左右子树均为空。

（为方便在计算机上实现算法，一般还要求以Ti的权值Wi的
升序排列。

）二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。

三、从F中删除这
两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。

四、重复二和三两步，直到集合F中只有一棵二叉树为止。

树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL
WPL=∑Wi*Li (i=1到n)
WPL=(2+4)*3+(6+8+10)*2
=66。