数据结构评分标准10.docVIP

数据结构答案与评分标准（10） 选择题（每小题2分，共20分） 1-5 BABCA 6-10 ADADD 二、判断题（每小题1分，共10分） 1-5 ×√√√× 6-10 ×√×√× 三、解答下列问题（共50分） 1．（5分）二叉排序树或者是一棵空树；或者是具有下列性质的二叉树：（1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；（3）它的左、右子树也分别是二叉排序树。 评分标准：只要基本思想对就可得分。 2．（5分）对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。 证明：设二叉树的结点总数为n，度为1的结点个数为n1，则有： n=n0+n1+n2 （1） 又在二叉树中除了根结点每个结点都有一个分支指向它，这些分支是有度为1和度为2的结点发出的，由此得到： n-1=n1+2*n2 （2） 由式（1）和（2）得n0=n2+1，证毕。 评分标准：叙述定理得1分，证明得4分，其他酌情扣分。 3．（8分） （1）前序：ABDGCEFH 中序：DGBAECHF 后序：GDBEHFCA 层次：ABCDEFGH （2）二叉树所对应的森林： 评分标准：第一小题每个1分，第二小题三棵树，每个2分。 4．（8分） 由C开始的深度优先生成序列：CDEABF 评分标准：画出原图得4分，求出深度优先生成序列得4分，其他情况酌情给分。 5．（8分） 评分标准：结果正确得5分，步骤不全酌情扣分。 6．(8分) 初始堆 30选出后 28选出后 15选出后 12选出后 9选出后 3选出后排序完成 评分标准：结果正确得5分，步骤不全酌情扣分。 7．（8分） （1）由装载因子0.7，数据总数7个，得一维数组大小为7/0.7=10，存储空间长度为10，采用线性探测再散列法处理冲突，所构造的散列表为： 0 1 2 3 4 5 6 7 8 9 30 7 14 11 8 18 . 9 . . （2）查找成功的ASL=(1+1+1+1+2+1+1)/7=8/7 评分标准：构造出哈希表得6分，求出平均查找长度得2分。 四、算法题（20分） 1．void deletelist(linklist head， int i) { listnode * p， *r; p=getnode(head，i-1); if(p= =NULL || p–next= =NULL) return ERROR; r=p–next; p–next=r–next; free( r ) ; } 2、（7分） Status dequeue(SqQueue q,int e) { if(q.front==q.rear)return error; e=q.base[q.front]; q.front=(q.front+1)%MAX; return ok; } 3、（6分） int partition(sqlist L, int low, int high) {L.r[0]=L.r[low]; pivotkey=L.r[low].key; 1分 while(lowhigh) { while(lowhighL.r[high].key=pivotdey) –high; L.r[low]=L.r[high]; 3分 while(lowhighL.r[low].key=pivotkey) ++low; L.r[high]=L.r[low]; 5分 } L.r[low]=L.r[0]; return low; 6分 } 评分标准：答案不唯一，只要思路正确就得分，算法过程不全酌情扣分。