数据结构(第3次)

第3次作业一、填空题（本大题共10分，共5小题，每小题2分）1.多重表文件和倒排文件都归属于______文件。2.数据结构被形式地定义为（D,R），其中D是______的有限集合，R是D上的______有限集合。3.在栈的出栈操作中，要先判断栈是否空，否则会产生______现象。4.在n个结点的单链表中要删除已知结点*p，需找到它的______，其时间复杂度为______。5.已知一个图的广度优先生成树如右图所示，则与此相应的广度优先遍历序列为______。二、程序阅读题（本大题共40分，共5小题，每小题8分）1.求下列广义表运算的结果：head((p,h,w))。2.指出下述程序段的功能是什么?SeqStackS1,S2,tmp;DataTypex;...//假设栈tmp和S2已做过初始化while(!StackEmpty(&S1)){x=Pop(&S1);Push(&tmp,x);}while(!StackEmpty(&tmp)){x=Pop(&tmp);Push(&S1,x);Push(&S2,x);}3.写出下列程序段的输出结果（栈的元素类型SElemType为char）。voidmain(){StackS;Charx,y;InitStack(S);X=’c’;y=’k’;Push(S,x);Push(S,’a’);Push(S,y);Pop(S,x);Push(S,’t’);Push(S,x);Pop(S,x);Push(S,’s’);while(!StackEmpty(S)){Pop(S,y);printf(y);};Printf(x);}4.下述算法的功能是什么?LinkListDemo(LinkListL){//L是无头结点单链表ListNode*Q,*P;if(L&&L-next){Q=L;L=L-next;P=L;while(P-next)P=P-next;P-next=Q;Q-next=NULL;}returnL;}//Demo5.阅读下列C程序段，写出相应的执行结果题目：longintfact(n)intn;{longf;if(n1)f=n*fact(n-1);elsef=1;return(f);}main(){intn;longy;n=5;y=fact(n);printf(“%d,%ld\n”,n,y);}三、简答题（本大题共20分，共4小题，每小题5分）1.链栈中为何不设置头结点?2.什么是程序的空间复杂度？3.以关键字序列(265，301，751，129，937，863，742，694，076，438)为例，写出执行快速排序算法的各趟排序结束时，关键字序列的状态。4.一棵度为2的有序树与一棵二叉树有何区别?四、程序设计题（本大题共20分，共2小题，每小题10分）1.试按照带头结点的线性链表写一算法实现在线性链表L中查找给定元素的操作。2.写出求BFS生成树的算法。五、名词解释题（本大题共10分，共2小题，每小题5分）1.请解释名词“开始结点”2.请解释名词“数据类型”答案：一、填空题（10分，共5题，每小题2分）1.参考答案：多关键字解题方案：评分标准：每空2分2.参考答案：数据元素，关系解题方案：评分标准：每空2分3.参考答案：下溢解题方案：评分标准：每空2分4.参考答案：前驱结点的地址，O（n）解题方案：评分标准：每空2分5.参考答案：Abefcdg解题方案：评分标准：每空2分二、程序阅读题（40分，共5题，每小题8分）1.参考答案：head((p,h,w))=p。解题方案：评分标准：2.参考答案：程序段的功能是利用tmp栈将一个非空栈s1的所有元素按原样复制到一个栈s2当中去。解题方案：评分标准：3.参考答案：答：输出为“stack”。解题方案：答：输出为“stack”。评分标准：54.参考答案：答：该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。解题方案：答：该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。评分标准：55.参考答案：答：运行结果为：5，120解题方案：答：运行结果为：5，120评分标准：5三、简答题（20分，共4题，每小题5分）1.参考答案：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。解题方案：评分标准：2.参考答案：答：一个程序的空间复杂度是指程序运行从开始到结束所需的存储量。定义算法空间复杂度为S(n)=O(g(n))表示随着问题规模n的增大，算法运行所需辅助存储量的增长率与g(n)的增长率相同。解题方案：答：一个程序的空间复杂度是指程序运行从开始到结束所需的存储量。定义算法空间复杂度为S(n)=O(g(n))表示随着问题规模n的增大，算法运行所需辅助存储量的增长率与g(n)的增长率相同。评分标准：2223.参考答案：快速排序：（方括号表示无序区，层表示对应的递归树的层数）初始态：[265301751129937863742694076438]第二层：[076129]265[751937863742694301438]第三层：076[129]265[438301694742]751[863937]第四层：076129265[301]438[694742]751863[937]第五层：076129265301438694[742]751863937第六层：076129265301438694742751863937解题方案：评分标准：4.参考答案：答：一棵度为二的有序树与一棵二叉树的区别在于:有序树的结点次序是相对于另一结点而言的，如果有序树中的子树只有一个孩子时，这个孩子结点就无须区分其左右次序，而二叉树无论其孩子数是否为2，均需确定其左右次序，也就是说二叉树的结点次序不是相对于另一结点而言而是确定的。解题方案：答：一棵度为二的有序树与一棵二叉树的区别在于:有序树的结点次序是相对于另一结点而言的，如果有序树中的子树只有一个孩子时，这个孩子结点就无须区分其左右次序，而二叉树无论其孩子数是否为2，均需确定其左右次序，也就是说二叉树的结点次序不是相对于另一结点而言而是确定的。评分标准：33四、程序设计题（20分，共2题，每小题10分）1.参考答案：答：boolLocateElem(OrderedLinkListL,ElemTypee,int(*compare)(ElemType,ElemType)){//若有序链表L中存在和e相同的数据元素，则当前指针指向第1个和e相同的结点，//并返回TRUE，否则当前指针指向第一个大于e的元素的前驱，并返回FALSE。L.current=L.head;L.curPos=0;while(L.current-next&&compare(e,L.current-next-data)0){L.current=L.current-next;//指针后移，继续查询L.curPos++;}if(L.current-next&&compare(e,L.current-next-data)==0){//查到和e相同元素，当前指针后移L.current=L.current-next;L.curPos++;returnTRUE;}elsereturnFALSE;//当前指针所指后继元素大于e}//LocateElem解题方案：答：boolLocateElem(OrderedLinkListL,ElemTypee,int(*compare)(ElemType,ElemType)){//若有序链表L中存在和e相同的数据元素，则当前指针指向第1个和e相同的结点，//并返回TRUE，否则当前指针指向第一个大于e的元素的前驱，并返回FALSE。L.current=L.head;L.curPos=0;while(L.current-next&&compare(e,L.current-next-data)0){L.current=L.current-next;//指针后移，继续查询L.curPos++;}if(L.current-next&&compare(e,L.current-next-data)==0){//查到和e相同元素，当前指针后移L.current=L.current-next;L.curPos++;returnTRUE;}elsereturnFALSE;//当前指针所指后继元素大于e}//LocateElem评分标准：3342.参考答案：求BFS生成树typedefenum{FALSE，TRUE}Boolean；//FALSE为0，TRUE为1Booleanvisited[MaxVertexNum]；//访问标志向量是全局量voidBFSTraverseTREE(ALGraph*G){//求广度优先生成树(以邻接表表示的图G)，而以邻接矩阵表示G时，//算法完全与此相同,只要将BFSTree(G，i)改为BFSMTree(G，i)即可inti；for(i=0;in;i++)visited[i]=FALSE；//标志向量初始化for(i=0;in；i++)if(!visited[i])//vi未访问过BFSTree(G，i)；//以vi为源点开始BFS搜索,求BFS生成树的边}//BFSTraversevoidBFSTree(ALGraph*G，intk){//以vk为源点对用邻接表表示的图G进行广度优先搜索,并求出BFS生成树边inti；CirQueueQ；//须将队列定义中DataType改为intEdgeNode*p；InitQueue(&Q)；//队列初始化visited[k]=TRUE；EnQueue(&Q，k)；//vk已访问，将其人队。（实际上是将其序号人队）while(!QueueEmpty(&Q)){//队非空则执行i=DeQueue(&Q)；//相当于vi出队p=G-adjlist[i].firstedge；//取vi的边表头指针while(p){//依次搜索vi的邻接点vj(令p-adjvex=j)if(!visited[p-adivex]){//若vj未访问过printf((%c,%c)\n，G-adjlist[i].vertex,G-adjlist[p-adjvex].vertex)；//打印边visited[P-adjvex]=TRUE；EnQueue(&Q，p-adjvex)；／/访问过的vj人队}//endifp=p-next；//找vi的下一邻接点}//endwhile}//endwhile}//endofBFSTreevoidBFSMTree(MGraph*G，intk){//以vk为源点对用邻接矩阵表示的图G进行广度优先搜索,并求出BFS生成树边inti，j；CirQueueQ；InitQueue(&Q)；visited[k]=TRUE；EnQueue(&Q，k)；while(!QueueEmpty(&Q)){i=DeQueue(&Q)；//vi出队for(j=0;jn;j++)//依次搜索vi的邻接点vjif(G-edges[i][j]==1&&!visited[j]){//vi未访问printf((%c,%c)\n，G-vexs[i],G-vexs[j])；//打印边visited[j]=TRUE；EnQueue(&Q，j)；//访问过的vj人队}}//endwhile}//BFSMTree解题方案：评分标准：五、名词解释题（10分，共2题，每小题5分）1.参考答案：开始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。解题方案：评分标准：2.参考答案：数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以看作是程序设计语言中已实现的数据结构。解