数据结构评分标准7.docVIP

数据结构答案与评分标准（7） 一、选择题（每小题2分，共20分） 1-5 BABBD 6-10 DBBDA 二、填空题（每空1分，共10分） 1、数据域 指针域 2、线性表 队列 3、 4、入栈 出栈 5外部排序 6、Loc(a11)+((i-1)*m+j-1)*2 7、n-1 三、填空题（每小题1分，共10分） 1-5 ×××√√ 6-10√×√×√ 四、应用题（40分） 1、（8分） 4分 4分 评分标准：构造出二叉树得4分，二叉树的生成森林得4分。 2、（8分）二叉排序树的构造过程如下： 评分标准：没有过程或过程不全酌情减分 3、（8分）邻接矩阵： 4分 深度优先序列：abcdehf或abche df或abcfdeh或abcfhed（不唯一） 广度优先序列：abfcdhe或afbcdhe或abfchde或afbchde（不唯一）4分 评分标准：写出图的邻接矩阵的4分，深度优先序列得2分，其他酌情给分。 4、（8分） 3． 评分标准：最小生成树给4分，过程给4分，结果正确没有过程或过程不对酌情减分。 5、（8分）哈希表： 0 1 2 3 4 5 6 7 8 9 10 11 12 3 29 200 32 45 58 100 10 126 400 平均查找长度： ASLsc=（7*1+2+3+3）/10=1.5 评分标准：写出哈希表得5分，查找长度3分 四、算法题（20分） 1、（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; } 2、 void createlist(LinkList head, int n) { linklist head, *p; head=(listnode*)malloc(sizeof(listnode)); Head-next=null; for(i=n; i0; --i) { p=(listnode*)malloc(sizeof(listnode)); scanf((〝%d〞，p–data); p–next=head; head-next=p; } } 3、 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分 } 评分标准：答案不唯一，只要思路正确就得分，算法过程不全酌情扣分。