2014年9月份考试数据结构第三次作业

2014年9月份考试数据结构第三次作业一、填空题（本大题共10分，共5小题，每小题2分）1.数据结构包括数据的______和数据的______。2.在无头结点的单链表中，第1个结点的地址存放在头指针中，其他结点的存储地址存放在______结点的next域中。3.为了实现逐层访问，算法中使用了一个______，以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。4.在一个循环队列中，队首指针指向队首元素的______位置。5.弗洛伊德Floyd算法的时间复杂度为______。二、名词解释题（本大题共10分，共2小题，每小题5分）1.请解释名词“头指针”2.请解释名词“目标串”三、程序阅读题（本大题共20分，共2小题，每小题10分）1.指出下述程序段的功能是什么?voidDemo2(SeqStack*S,intm){//设DataType为int型SeqStackT;inti;InitStack(&T);while(!StackEmpty(S))if((i=Pop(S))!=m)Push(&T,i);while(!StackEmpty(&T)){i=Pop(&T);Push(S,i);}}2.下述算法的功能是什么?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;}//Demo四、简答题（本大题共20分，共4小题，每小题5分）1.如何判别循环队列的空和满?2.实际中，需根据不同的情况采用不同的哈希函数。通常，考虑的因素有那些？3.以关键字序列(265，301，751，129，937，863，742，694，076，438)为例，写出执行直接选择排序算法的各趟排序结束时，关键字序列的状态。4.在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少?五、程序设计题（本大题共40分，共4小题，每小题10分）1.编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。2.编写算法，在串的定长顺序存储结构上实现串的基本操作REPLACE（&S，T，V）3.假设以结点大小为1（且附设头结点）的链表结构表示串。试编写实现下列6种串的基本操作StrAssign,StrCopy,StrCompare,StrLength,Concat和SubString的函数。4.设顺序表中关键字是递增有序的，试写一顺序查找算法，将哨兵设在表的高下标端。然后求出等概率情况下查找成功与失败时的ASL。答案：一、填空题（10分，共5题，每小题2分）1.参考答案：逻辑结构，存储结构解题方案：评分标准：每空2分2.参考答案：前趋解题方案：评分标准：每空2分3.参考答案：队列解题方案：评分标准：每空2分4.参考答案：前一个解题方案：评分标准：每空2分5.参考答案：O（n3）解题方案：评分标准：每空2分二、名词解释题（10分，共2题，每小题5分）1.参考答案：头指针是一指向链表开始结点的指针（没有头结点时）。解题方案：评分标准：2.参考答案：在串匹配运算过程中，将主串称为目标串。解题方案：评分标准：三、程序阅读题（20分，共2题，每小题10分）1.参考答案：程序段的功能是利用栈T，将一个非空栈S中值等于m的元素全部删去。解题方案：评分标准：2.参考答案：答：该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。解题方案：答：该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。评分标准：5四、简答题（20分，共4题，每小题5分）1.参考答案：判别循环队列的空或满不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间,每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。解题方案：评分标准：2.参考答案：答：（1）计算哈希函数所需时间；（2）关键字的长度；哈希表的大小；关键字的分布情况；（5）记录的查找频率；解题方案：答：（1）计算哈希函数所需时间；（2）关键字的长度；哈希表的大小；关键字的分布情况；（5）记录的查找频率；评分标准：211113.参考答案：直接选择排序：(方括号为无序区)初始态[265301751129937863742694076438]第一趟：076[301751129937863742694265438]第二趟：076129[751301937863742694265438]第三趟：076129265[301937863742694751438]第四趟：076129265301[937863742694751438]第五趟：076129265301438[863742694751937]第六趟：076129265301438694[742751863937]第七趟：076129265301438694742[751863937]第八趟：076129265301438694742751[937863]第九趟：076129265301438694742751863937解题方案：评分标准：4.参考答案：答：下面分别讨论三种链表的情况。1）单链表。若指针p指向某结点时，能够根据该指针找到其直接后继，能够顺后继指针链找到*p结点后的结点。但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。2）双链表。由于这样的链表提供双向指针，根据*p结点的前趋指针和后继指针可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。3）单循环链表。根据已知结点位置，可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。解题方案：答：下面分别讨论三种链表的情况。1）单链表。若指针p指向某结点时，能够根据该指针找到其直接后继，能够顺后继指针链找到*p结点后的结点。但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。2）双链表。由于这样的链表提供双向指针，根据*p结点的前趋指针和后继指针可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。3）单循环链表。根据已知结点位置，可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。评分标准：222五、程序设计题（40分，共4题，每小题10分）1.参考答案：解：StatusBuild_AdjList(ALGraph&G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表{InitALGraph(G);scanf(%d,&v);if(vnextarc;q=q-nextarc);q-nextarc=p;}p-adjvex=j;p-nextarc=NULL;}//whilereturnOK;}//Build_AdjList解题方案：解：StatusBuild_AdjList(ALGraph&G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表{InitALGraph(G);scanf(%d,&v);if(v=a;m++){t=getchar();h=getchar();//t为弧尾,h为弧头if((i=LocateVex(G,t))nextarc;q=q-nextarc);q-nextarc=p;}p-adjvex=j;p-nextarc=NULL;}//whilereturnOK;}//Build_AdjList评分标准：222222.参考答案：答：intString_Replace(SString&S,SStringT,SStringV);{//将串S中所有子串T替换为V,并返回置换次数for(n=0,i=1;iT[0])//找到了与T匹配的子串:分三种情况处理{if(T[0]==V[0])for(l=1;l=i+T[0];l--)S[l+V[0]-T[0]]=S[l];for(l=1;l=V[0];l++)S[i+l-1]=V[l];}else//新子串长度小于原子串时:先将后部左移{for(l=i+V[0];l=S[0]+V[0]-T[0];l++)S[l]=S[l-V[0]+T[0]];for(l=1;l=V[0];l++)S[i+l-1]=V[l];}S[0]=S[0]-T[0]+V[0];i+=V[0];n++;}//if}//forreturnn;}//String_Replace解题方案：答：intString_Replace(SString&S,SStringT,SStringV);{//将串S中所有子串T替换为V,并返回置换次数for(n=0,i=1;i=S[0]-T[0]+1;i++){for(j=i,k=1;T[k]&&S[j]==T[k];j++,k++);if(kT[0])//找到了与T匹配的子串:分三种情况处理{if(T[0]==V[0])for(l=1;l=T[0];l++)//新子串长度与原子串相同时:直接替换S[i+l-1]=V[l];elseif(T[0]=i+T[0];l--)S[l+V[0]-T[0]]=S[l];for(l=1;l=V[0];l++)S[i+l-1]=V[l];}else//新子串长度小于原子串时:先将后部左移{for(l=i+V[0];l=S[0]+V[0]-T[0];l++)S[l]=S[l-V[0]+T[0]];for(l=1;l=V[0];l++)S[i+l-1]=V[l];}S[0]=S[0]-T[0]+V[0];i+=V[0];n++;}//if}//forreturnn;}//String_Replace评分标准：222223.参考答案：答：typedefstruct{charch;LStrNode*next;}LStrNode,*LString;//链串结构voidStringAssign(LString&s,LStringt)//把串t赋值给串s{s=malloc(sizeof(LStrNode));for(q=s,p=t-next;p;p=p-next){r=(LStrNode*)malloc(sizeof(LStrNode));r-ch=p-ch;q-next=r;q=r;}q-next=NULL;}//StringAssignvoidStringCopy(LString&s,LStringt)//把串t复制为串s.与前一个程序的区别在于,串s业已存在.{for(p=s-next,q=t-next;p&&q;p=p-next,q=q-next){p-ch=q-ch;pre=p;}while(q){p=(LStrNode*)malloc(sizeof(LStrNode));p-ch=q-ch;pre-next=p;pre=p;}p-next=NULL;}//StringCopycharStringCompare(LStrings,LStringt)//串的比较,st时返回正数,s=t时返回0,snext,q=t-next;p&&q&&p-ch==q-ch;p=p-next,q=q-next);if(!p&&!q)return0;elseif(!p)return-(q-ch);elseif(!q)returnp-ch;else