安徽工业大学工商学院数据结构2011试卷A(储岳中)

课程________________________班级________________________姓名__________________________学号________________________

……………………………… 密……………………………… 封 ………………………………… 线 ………………………………

安    徽    工    业    大    学    工   商   学    院    试    题    纸（二）

二、填空题（每空1分，共12分）

1. 通常是以算法执行所耗费的                   和所占用的                    来判断一个算法的优劣。

2．已知二维数组A[10][20]采用行序优先方式存储，每个元素占2个存储单元。并且A[0][0]的存储地址是1024, 则A[6][18]的地址是                   

3．用带头结点的循环链表表示的队列,若只设尾指针rear, 则队空的条件是                   。

4． 向一个有n个元素的有序表中插入一个新元素并保持原来顺序不变，平均要移动                    个元素。

5．10000个结点构成的二叉排序树，在等概率查找的假设下，查找成功时的平均查找长度的最大值可能达到________________。

6．高度为h的完全二叉树最少有                   个结点。

7．对某二叉树进行前序遍历的结果为EBADCFHGIKJ，中序遍历的结果为ABCDEFGHIJK,则后序遍历的结果为________________ 。

8．线性结构中元素之间存在________关系，树形结构中元素之间存在________关系，图形结构中元素之间存在________关系。

9．在一棵二叉树中，假定双分支结点数为10个，单分支结点数为11个，则叶子结点数为       个。

三、判断题（每题1分，共10分）

（  ）1. 在单链表中，头结点是必不可少的。

 （  ）2. 在一个大根堆中，最小元素不一定在最后。

 （  ）3. 顺序存储结构只能存线性结构，链式存储结构只能存非线性结构。

 （  ）4. 在有向图中，所有顶点的入度之和等于所有顶点的出度之和。

 （  ）5. 内部排序是指排序过程在内存中进行的排序。

 （  ）6. 拓扑排序是指结点的值是有序排列。

 （  ）7. AOE网所示工程至少所需时间等于从源点到汇点最长路径长度。

 （  ）8. 二叉排序树或是一棵空树，或是具有下列性质的二叉树：

        若它的左子树非空，则根结点的值大于其左孩子的值；

        若它的右子树非空，则根结点的值大于其右孩子的值。

 （  ）9.  分块查找的特点是块内可无序，块间要有序。

（  ）10. 快速排序的枢轴元素可以任意选定。

四、应用题（每题8分，共40分）

1．设哈希函数H（K）=（K的第一字母在字母表中的序号）% 11 ，哈希表长度为11，若输入顺序为（D，BA，TN，M，CI，I，K，X，TA），处理冲突方法为线性探测再散列法，要求构造哈希表，并求出等概率情况下查找成功平均查找长度。

2．假设用于通信的电文由10个字母组成，字母A，B，C，D，E，F，G，H，I，J的使用频率分别为5%，12%，4%，7%，9%，12%，10%，8%，13%，20%试为这10个字符设计哈夫曼编码，并计算带权路径长度。

3．给定一组关键码{18，31，16，22，51，30，24，10}，请建大根堆。

4．已知带权的无向图的邻接矩阵如下，画出该图及其最小生成树。

课程________________________班级________________________姓名__________________________学号________________________

……………………………… 密……………………………… 封 ………………………………… 线 ………………………………

安    徽    工    业    大    学    工   商   学    院    试    题    纸（三）

5. 填空完成下面一趟快速排序算法：

int  QKPass ( RecordType  r [ ],  int  low， int  high)

{  x = r [ low ]；        

while ( low < high )

{

while ( low < high && r [          ]. key >= x.key )  

high - -；

if ( low < high )

{ r [          ] = r [ high ]；  low++; }  

while ( low < high && r [          ]. key < x. key )  

low++;

if ( low < high )

{ r [          ] = r [ low ]；  high--; } 

}

r [ low ] = x；   return  low ;      

} 

五、算法设计题（ 28分）

1．假设有一个长度大于1的循环单链表，表中既无头结点也无头指针。已知S为指向链表中某个结点的指针，试编写算法，在链表中删除指针S指向的结点。（ 8分）

结点类型：

typedef struct node

{  datatype data;

   struct node  *next;

}LNode , *LinkList;

2．编写一个建立二叉树的算法，要求采用二叉链表存储结构。（ 8分）

二叉树结点类型：

typedef struct  bnode

{  datatype data;

   struct bnode  *lchild, *rchild;

}BNode , *BTree;

3． 二叉排序树T用二叉链表表示，其中各元素值均不相同。

（1）    写递归算法，按递增顺序输出各元素的值（5分）。

（2）    写出完成上述要求的非递归算法。（7分）

二叉排序树结点类型：

typedef struct  BinSTreeNode

{  datatype data;

   struct BinSTreeNode  *lchild, *rchild;

} *BinSTree;

课程________________________班级________________________姓名__________________________学号________________________

……………………………… 密……………………………… 封 ………………………………… 线 ………………………………

安    徽    工    业    大    学    工   商   学    院    答    题    纸（一）

一、单选题（每小题1分，共10分）

题号