发布时间 : 星期一 文章数据结构A参考答案更新完毕开始阅读8daa430f76c66137ee06195c
湖州师范学院2005—2006学年第一学期 《数据结构》期末考试试卷(A)参考答案
（ 适用班级040821）
一、 1
单项选择题（每题1分，共15分） 2 3 4 5 6 7 8 9 10 11 12 13 14 15 D Ｂ A C A C A C B C D A C D D 二、判断题（每题1分，共10分） 1 √ 2 × 3 √ 4 × 5 √ 6 × 7 × 8 × 9 √ 10 √
三、应用题（每题6分，共30分）
1）前序序列ABDECFG，后序序列DEBGFCA。其后序线索树如下：
A
B C
D E F G
(注：该线索树中的线索需用笔另勾划出来)
2）34215
5 ^ 1 ^
1 5 ^
2 5 ^
^
1
3）
0 1 2 3 4 5 6 14 18 23 9 30 12 6
4)答： 89，67， 34，90， 11，33， 29，83， 74 [89，67] [ 34，90] [ 11，33] [ 29，83] [ 74] 第一趟[67，89] [ 34，90] [ 11，33] [ 29，83] [ 74] 第二趟 [34，67，89，90] [ 11，29，33，83] [ 74] 第三趟 [11，29，33，34，67，83，89，90] [ 74] 第四趟 [11，29，33，34，67，74，83，89，90]
5) 如果模式串为t=”abcabaa”,则其模式匹配函数next[j]（0≤j≤7）的值分别是多少？
解： 位置j 模式串 next[j]
1 a 0 2 b 1 3 c 1 4 a 1 5 b 2 6 a 3 7 a 2 四、算法填空题，在下面程序的空格处填入适当的内容，使其完成指定的功能。(每小题9分，共18分)
1．p->next->data = = b，q->next，p = p->next， 2．i=2，i< n，i++，A[0] 五、算法设计题参考答案（每题9分，共27分）。 １．int DLDelete(DLinkList *DL, int i ) {/*在双向链表DL中删除第i个结点，若成功，则返回1；否则，返回0 */ int j =1; DLinkList *temp; temp = DL->next; /*工作指针temp指向被删结点*/ while (j { /*在双向链表DL中找第i个结点,*/ /*使指针temp指向第i个结点*/ j++; temp= temp->next; } if (j return 0 ; 2 /* 删除第i个结点 */ temp->prior->next=temp->next; if(temp->next!=NULL) /* 表示被删结点不是表尾 */ temp->next->prior=temp->prior; free(temp); return 1 ; } 2．解：双向扫描：从前向后找一个正数，再从后向前找一个负数，然后交换两者位置。 void moves(sqlist *L) { int i,j; datatype x; i =1;j = L->n; /*线性表中结点的实际个数,设数组下标从1开始*/ while(i while(L->data[i]<0 && i x=L->data[i];L->data[i]=L->data[j];L->data[j]=x; /*交换*/ i++;j??; } } } 3．在中根遍历的线索树中查找后继结点的算法 对于二叉树中任意结点p，若要找其后继结点，当p->Rtag=1时，p->Rchild即为p的后继结点；当p->Rtag=0时，说明p有右子树，此时p的中根遍历下的后继结点即为其右子树左链下的最后一个结点。因此，其查找算法如下： Void Succedent(ThreadTnode *p, ThreadTnode *succ) { ThreadTnode *q; if (p->Rtag==1) succ= p-> RChild; else { for(q= p->RChild; q->Ltag==0 ;q=q->LChild ); succ=q; } } 3 /*从前向后找正数*/ /*从后向前找负数*/