《算法与数据结构》模拟试题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