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

1、2014年 9月份考试数据结构第三次作业 一、填空题（本大题共 10 分，共 5 小题，每小题 2 分） 1. 数据结构包括数据的 _ 和数据的 _ 。 2. 在无头结点的单链表中，第 1个结点的地址存放在头指针中，其他结点的存储地址存放在 _ 结点的 next 域中。 3. 为了实现逐层访问，算法中使用了一个 _ ，以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。 4. 在一个循环队列中，队首指针指向队首元素的 _ 位置。 5. 弗洛伊德 Floyd 算法的时 间复杂度为 _ 。 二、名词解释题（本大题共 10分，共 2 小题，每小题 5 分） 1. 请解释名词 “ 头指针 ” 2

2、. 请解释名词 “ 目标串 ” 三、程序阅读题（本大题共 20分，共 2 小题，每小题 10 分） 1. 指出下述程序段的功能是什么 ? void Demo2( SeqStack *S, int m) / 设 DataType 为 int 型 SeqStack T; int i; InitStack ( while (! StackEmpty( S) if( i=Pop(S) !=m) Push( while (! StackEmpty( Push(S,i); 2. 下述算法的功能是什么 ? LinkList Demo(LinkList L) / L 是无头结点单链表 ListNode *Q,

3、*P; if(LL=L-next;P=L; while (P-next) P=P-next; P-next=Q; Q-next=NULL; return L; / Demo 四、简答题（本大题共 20 分，共 4 小题，每小题 5 分） 1. 如何判别循环队列的空和满 ? 2. 实际中，需根据不同的情况采用不同的哈希函数。通常，考虑的因素有那些？ 3. 以关键字序列 (265， 301， 751， 129， 937， 863， 742， 694， 076， 438)为例，写出执行直接选择排序算法的各趟排序结束时，关键字序列的状态。 4. 在单链表、双链表和单循环链表中，若仅知道指针 p指向某结

4、点，不知道头指 针，能否将结点 *p从相应的链表中删去 ?若可以，其时间复杂度各为多少 ? 五、程序设计题（本大题共 40分，共 4 小题，每小题 10 分） 1. 编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。 2. 编写算法，在串的定长顺序存储结构上实现串的基本操作 REPLACE（ scanf(“%d“, if(vnextarc;q=q-nextarc); q-nextarc=p; p-adjvex=j;p-nextarc=NULL; /while return OK; /Build_AdjList 解题方案： 解： Status Build_A

5、djList(ALGraph scanf(“%d“, if(vnextarc); q-nextarc=p; p-adjvex=j;p-nextarc=NULL; /while return OK; /Build_AdjList 评分标准： 2 2 2 2 2 2. 参考答案： 答： int String_Replace(SString /将串 S中所有子串 T 替换为 V,并返回置换次数 for(n=0,i=1;iT0) /找到了与 T 匹配的子串 :分三种情况处理 if(T0=V0) for(l=1;l=i+T0;l-) Sl+V0-T0=Sl; for(l=1;lT0) /找到了与 T匹配

6、的子串 :分三种情况处理 if(T0=V0) for(l=1;lnext;p;p=p-next) r=(LStrNode*)malloc(sizeof(LStrNode); r-ch=p-ch; q-next=r;q=r; q-next=NULL; /StringAssign void StringCopy(LString pp=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; /StringCopy

7、 char StringCompare(LString s,LString t)/串的比较 ,st时返回正数 ,s=t时返回0,snext,q=t-next;pp=p-next,q=q-next); if(!p else if(!p) return -(q-ch); else if(!q) return p-ch; else return p-ch-q-ch; /StringCompare int StringLen(LString s)/求串 s的长度 (元素个数 ) for(i=0,p=s-next;p;p=p-next,i+); return i; /StringLen LString

8、* Concat(LString s,LString t)/连接串 s和串 t形成新串 ,并返回指针 p=malloc(sizeof(LStrNode); for(q=p,r=s-next;r;r=r-next) q-next=(LStrNode*)malloc(sizeof(LStrNode); q=q-next; q-ch=r-ch; /for /复制串 s for(r=t-next;r;r=r-next) q-next=(LStrNode*)malloc(sizeof(LStrNode); q=q-next; q-ch=r-ch; /for /复制串 t q-next=NULL; ret

9、urn p; /Concat LString * Sub_String(LString s,int start,int len)/返回一个串 ,其值等于串 s从start 位置起长为 len的子串 p=malloc(sizeof(LStrNode);q=p; for(r=s;start;start-,r=r-next); /找到 start 所对应的结点指针 r for(i=1;inext) q-next=(LStrNode*)malloc(sizeof(LStrNode); q=q-next; q-ch=r-ch; /复制串 t q-next=NULL; return p; /Sub_Str

10、ing 解题方案： 答： typedef struct char ch; LStrNode *next; LStrNode,*LString; /链串结构 void StringAssign(LString 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; /StringAssign void StringCopy(LString pp=p-next,q=q-next) p-ch=q-ch;pre=p; while(q) p=(LStr

11、Node*)malloc(sizeof(LStrNode); p-ch=q-ch; pre-next=p;pre=p; p-next=NULL; /StringCopy char StringCompare(LString s,LString t)/串的比较 ,st时返回正数 ,s=t时返回0,snext,q=t-next;pp=p-next,q=q-next); if(!p else if(!p) return -(q-ch); else if(!q) return p-ch; else return p-ch-q-ch; /StringCompare int StringLen(LStri

12、ng s)/求串 s的长度 (元素个数 ) for(i=0,p=s-next;p;p=p-next,i+); return i; /StringLen LString * Concat(LString s,LString t)/连接串 s和 串 t形成新串 ,并返回指针 p=malloc(sizeof(LStrNode); for(q=p,r=s-next;r;r=r-next) q-next=(LStrNode*)malloc(sizeof(LStrNode); q=q-next; q-ch=r-ch; /for /复制串 s for(r=t-next;r;r=r-next) q-next=

13、(LStrNode*)malloc(sizeof(LStrNode); q=q-next; q-ch=r-ch; /for /复制串 t q-next=NULL; return p; /Concat LString * Sub_String(LString s,int start,int len)/返回一个串 ,其值等于串 s从start 位置起长为 len的子串 p=malloc(sizeof(LStrNode);q=p; for(r=s;start;start-,r=r-next); /找到 start 所对应的结点指针 r for(i=1;inext) q-next=(LStrNode*

14、)malloc(sizeof(LStrNode); q=q-next; q-ch=r-ch; /复制串 t q-next=NULL; return p; /Sub_String 评分标准： 1 2 2 1 2 2 2 4. 参考答案： typedef struct KeyType key； InfoType otherinfo； /此类型依赖于应用 NodeType； typedef NodeType SeqListn+1； /n 号单元 用作哨兵 int SeqSearch(Seqlist R， KeyType K) /在关键字递增有序的顺序表 R0.n-1中顺序查找关键字为 K的结点， /成功时返回找到的结点位置，失败时返回 -1 int i； Rn.key=K； /设置哨兵 for(i=0； Ri.key=K;i-)； /从表前往后找 if (in /Ri是要找的结点 else return -1 /SeqSearch 等概率情况下查找成功 ASL=(1+2+3+n)/n 等概率情况下查找失败时的 ASL=(1+2+3+n+n+1)/(n+1) 解题方案： 评分标准：