99208,99209班《数据结构》补考试卷
班级:____________学号: ____________成绩: ____________
填空题(30分)
1.《数据结构》研究的内容是数据的逻辑结构,存储结构和算法.
2. 数据的存储结构分为顺序存储,链接存储,索引存储和散列存储.
3. 研究数据的逻辑结构是要提高数据的运算效率和节省占用的存储空间.
4. 已知顺序存储的线性表,其存储时表的首地址为Q,表中每个结点占2个字节,则结点i的存储地址是:Q+(i-1)*2
5. 栈的操作原则是先进后出,后进先出.
6. 假溢出现象是随着队列的不断插入和删除,整个队列会沿着一个方向不断移动,结果是队列前面许多单元未被利用,而队尾却因到达存储边缘而无法再往队列中添加数据.
7.查找算法种类有线性表的查找,树的查找,散列的查找和索引查找
8.丰满树必定是(不一定是,必定是)平衡树;平衡树不一定是(不一定是,必定是)丰满树;不是丰满树不一定不是(不一定不是,肯定不是)平衡树;不是平衡树肯定不是(不一定不是,肯定不是)丰满树
9.连通图是:无向图中,如果图中的任意两个顶点之间都存在一条回路,即图中任意一对顶点相互之间是可到达的.
强连通图是:有向图中,图中任意一对顶点相互之间是可到达的.
10.环形队列的队空和队满的判断条件.队满:rear指针下移一个单元与Front指针相等;队空:rear==front.
简答题(40分)
什么是拓扑排序;写出下图的一种拓扑排序
⑤
① ② ④ ⑥
③
结点集合F={25,50,100,150,200,225,250},请用该结点集合构造一棵丰满树,请画出此树.

对于权值W={4,9,8,11,20},试画出其相应的哈夫曼树,并计算其加权路长之和.

已知栈顶指针为top,栈空时top=NULL,结点结构如下:
struct node
{
char info;
struct node *link;
}
请写出链接式栈出栈的操作步骤
判断栈空:top==NULL吗
ptr=top
top=ptr->link
var=ptr->info
free(ptr)

画出 图的先深遍历序列(从结点①开始)
①
② ④
③
⑤ ⑥
1 2 5 6 3 4

编程(30分)
二叉树的树结点定义如下:
typedef struct trnode
{
char info;
struct trnode *llink, *rlink;
} TRNODE;
请写出中根遍历二叉树的子函数inorder(ptr)
见书P109页
List[]数组存放的是有序的数据序列,共有n个数据,x是要查的关键字,请画出折半查找法流程图并写出其程序.
见书P127页
A[ ]和b[ ]分别存放了两组已排好序的数据序列,c[ ]是用来存放它们合并的数据序列,请写出合并程序
见书P228页