数据结构A参考答案

湖州师范学院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 && idata[j]>=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

/*从前向后找正数*/ /*从后向前找负数*/