西华大学课程考试参考答案（B卷）课程名称：课程代码：
线数据结构8401801
考试时间：110分钟试卷总分：100
分
一、单项选择题参考答案及评分标准：（本大题共20个小题，每小题2分，共40分）评分标准：选对一题得2分，不选或选错得0分。1-5：ABDBB6-10：CABDC11-15：BABCB16-20：CABCC二、算法理解题参考答案及评分标准：（本大题共3个小题，第1、2小题各7分，第3小题6分，共20分）评分标准：请根据各解答步骤酌情给分。2.解：设权w=(5,10,15,30,40)，可构造一棵赫夫曼树如下图所示。ww装所得赫夫曼编码为：A:1110B:1111C:110D:10E:03.解：（1）希尔排序第一趟（增量d=5）排序后170、087、275、061、426、503、897、512、653、908第二趟（增量d=3）排序后061、087、275、170、426、503、897、512、653、908第三趟（增量d=1）排序后061、087、170、275、426、503、512、653、897、908（2）基数排序第一趟排序后170、061、512、503、653、275、426、087、897、908第一趟排序后503、908、512、426、653、061、170、275、087、897第1页共3页w.zhinanch订e.com1.解答：构造过程各图（略），最后结果为：第三趟排序后061、087、170、275、426、503、512、653、897、908三、算法设计题参考答案及评分标准：（本大题共4个小题，每小题10分，共40分）评分标准：请根据编程情况酌情给分。1.参考答案示例：LinkListDelete(LinkListL）∥L是带头结点的单链表，本算法删除其最小值结点。p=L->next；∥p是链表的工作指针pre=L；∥pre指向链表中数据域最小值结点的前驱。q=p；∥q指向数据域最小值结点，初始假定是首元结点while（p->next!=NULL）{if（p->next->datadata）{pre=p；q=p->next；}∥找到新的最小值结点p=p->next；ww4.参考答案示例：intPartition(SqList&L,intlow,inthigh){//快速排序的一趟划分算法。L.r[0]=L.r[low];//用子表的第一个记录作基准记录pivotkey=L.r[low].key;//基准记录关键字第2页共3页w.visited[vi]=1;InitQueue(Q);while(!QueueEmpty(Q)){DeQueue(Q,k);zhintPath_BFS(ALGraphG,intvi,intvj){//以邻接表为存储结构的有向图G，广度优先判断G中vi到vj间是否有通路。//返回1或0表示有或无。假设顶点的信息就是顶点编号。EnQueue(Q,vi);for(p=G.vertices[k].firstarc;p;p=p->nextarc){if(p->adjvex==vj)return1;else{if(!visited[p->adjvex]){visited[p->adjvex]=1;EnQueue(Q,p->adjvex);}}//endelse}//endfor}//endwhilereturn0;}//Path_BFSin}//BTreeEqual3.参考答案示例：intvisited[]=0;//全局变量，访问数组初始化anelseif((T1->data==T2->data)&&BTreeEqual(T1->lchild,T2->lchild)&&BTreeEqual(T1->rchild,T2->rchild))return1;elsereturn0;//若根结点值不等或左、右子树对应不等则两棵树不等ch{//判断两棵二叉树是否相等，若相等则返回1否则返回0。if(T1==NULL&&T2==NULL)return1;elseif(T1==NULL||T2==NULL)return0;e.c}∥Delete2.参考答案示例：intBTreeEqual(BiTNode*T1,BiTNode*T2)om}pre->next=q->next；∥将最小值结点从链表上去掉free（q）；∥释放最小值结点空间while(low=pivotkey)high--;L.r[low]=L.r[high];while(low
