《算法与数据结构》模拟试题8--答案.doc
文本预览下载声明
《算法与数据结构》模拟试题8参考答案及评分标准
一、填空题（每小题2分，共20分）
1、 线性结构 树（形）结构 图（网）状结构
2、 可读性 健壮性
3、 队尾 队首
4、 1170
5、 先序遍历 中序遍历
6、 n 2e
7、最佳拟合法 最差拟合法
8、（记录）关键字的比较 (记录)存储位置的移动
9、关键字 存储地址 或 存储地址 关键字
10、操作系统 数据库
二、单项选择题（请将答案写在题目后的括号中。每题2分，共18分）
题号 1 2 3 4 5 6 7 8 9 答案 D B C A B C B D A 三、分析题（每题6分，共30分）
图1分A (1分)
3、 解：⑴ 该图的邻接链表如下图所示：(3分)→V1→V2→V4→V5→V3 (1分)(Prime)算法从顶点V2出发的最小生成树如下：(2分)(4分)(1分)(1分)
四、算法填空（每空2分，共20分）
请在下面各算法的空白处填上相应语句实现算法功能。每个空白处只能填一个语句。
1、头插入法创建单循环链表，以整数的最大值(32767)作为输入结束，链表的头结点head作为返回值。
p=(LNode *)malloc(sizeof(LNode))
head-next =p
2、非递归先序遍历二叉树。
q=p-Rchild
p=p-Lchild
while (p!=NULL)
3、用折半查找法从表ST中查找关键字为key的数据元素。
LowHigh
High=Mid-1
4、。LQ(L-R[0].key, L-R[j].key)
i++
L-R[i]=L-R[0]
五、编写算法（12分）
解：
⑴ 输出树中度为2及度为1的结点数的算法。（6分）
#define MAXNODE 50
void count_nodes( BTNode *T)
{ BTNode *Stack[MAXNODE] ,*p=T;
int top=0, num1=0, num2=0 ;
if (T=NULL) printf(“Binary Tree is Empty!\n”) ;
else
{ stack[++top]=p ;
while (top0) （循环及控制1分）
{ p=stack[top--] ;
if ( p-Lchild!=NULLp-Rchild!=NULL) num2++ ; （1分）
else if (p-Lchild!=NULL||p-Rchild!=NULL) num1++ ; （1分）
if (p-Rchild!=NULL ) stack[++top]=p-Rchild; （1分）
if (p-Lchild!=NULL ) stack[++top]=p-Lchild; （1分）
}
printf(“\n The node’s number of degree equal 2 is: \n”,num2) ; （输出1分）
printf(“\n The node’s number of degree equal 1 is: \n”,num1) ;
}
}
⑵ 从根结点开始按层次次序“自上而下，从左至右”输出树中的各结点的算法。（6分）
#define MAXNODE 50
void Levelorder_output( BTNode *T)
{ BTNode *Queue[MAXNODE] , *p=T ;
int front=0 , rear=0 ; （初始化部分1分）
if (p!=NULL) （判断及入对1分）
{ Queue[++rear]=p; /* 根结点入队 */
while (frontrear) （循环及控制1分）
{ p=Queue[++front]; printf(“%4c”,p-data ); （1分）
if (p-Lchild!=NULL) Queue[++rear]=p-Lchild;
/* 左子结点入队 */ （1分）
if (p-Rchild!=NULL) Qu
显示全部