数据结构练习1-09答案.doc

09数据结构练习一参考
一、填空题：
1
直接前驱
2
直接后继
3
元素个数
4
一个指针域
5
前驱
6
后继
7
指针域
8
next(指针域)
9
头结点
10
相互间存在一种或多种特定关系

11
结构
12
集合 线性结构 树形结构 图形结构
13
逻辑结构 物理结构 操作（运算）

14
逻辑结构
15
物理结构
16
顺序印象和非顺序印象
17
顺序印象的特点是用元素在存储器中的相对位置表示数据元素之间的逻辑关系，非顺序印象的特点借助于指针表示数据元素之间的逻辑关系
18
顺序存储结构和链式存储结构
19
s->next=p->next;p->next=s;
20
q=p->next;p->next=q->next;
free(q);
21
t->prior=p->prior;
p->prior->next=t;
t->next=p; p->prior=t;
22
q=p->next;q->next->prior=p;
p->next=q->next; free(q);
23
往前挪
24
被删除元素后面一个元素
25
n/2
26
O(1)
27
O(n)
28
操作受限制
29
Q.front==(Q.rear+1)%MaxQueueSize
30
Q.front==Q.rear
31
最后一个
32
第一个
33
最后一个
34
O（n）
35
O(1)
36
O(n)
37
q->next 或p->next->next
38
零个字符的串
39
零
40
任意个连续字符组成的子序列
41

42
12000

二、选择题
1
A
2
C
3
C
4
B
5
A
6
D
7
C
8
C
9
A
10
A
11
A
12
B
13
A
14
B
15
D
16
D
17
B
18
B
19
B
20
D
21
A
22
C
23
D
24
C
25
D
26
A
27
A
28
C
29
D
30
D
31
C
32
C
33
A
34
B
35
A
36
D
37
B
38
B
39
D
40
C
41
D
42
B
43
B
44
C
45
D
46
B
47
A
48
D
49
D
50
B
51
D
52
B
53
B
54
B
55
C
56
B
57
C
58
D
59
B
60

三、判断题
1
否
2
否
3
否
4
是
5
否
6
否
7
是
8
否
9
否
10
否
11
否
12
否
13
否
14
是
15
是
16
否
17
否
18
是
19
是
20
否
21
否
22
是
23
否
24
否
25
是
26
否
27
是
28
是
29
是
30
是

五、算法设计
1．设有一个顺序表L，其元素为整形数据，设计一个算法将L中所有小于0的整数放在前半部分，大于等于0的整数放在后半部分。
void tiaozheng(SqList &L)
{ i=1; j=L.Length;
while(i<j)
{ GetElem(L,i,lefte);
if(lefte<0) { i++; GetElem(L,i,lefte);} //找到左边第一个大于0的元素
GetElem(L,j,righte);
if(righte>0) { i--; GetElem(L,i,righte);} //找到右边第一个小于0的元素
e=L.elem[i-1]; L.elem[i-1]=L.elem[j-1]; L.elem[j-1]=e;
}
}
2．设计一个算法从顺序表中删除重复的元素，并使剩余元素间的相对次序保持不变。
//思路：设a[0]..a[j]是没有重复元素的顺序表，检查a[i]是否在这个顺序表中，不在就存入a[j+1]
void shanchu(SqList &A)
{ j=0;
for(i=1; i<L.length; i++)
{k=0;
while(k<=j&&L.elem[i]!=L.elem[k]) k++; //查L.elem[0..j]中是否有L.elem[i]
if(k>j) L.elem[++j]=L.elem[i];
}
L.length=j+1; //注意j是从0开始的
}
3．用顺序表A和B表示的两个线性表，元素的个数分别为m和n，若表中数据都是由小到大顺序排列的，且这（m+n）个数据中没有重复的。
（1）设计一个算法将此两个线性表合并成一个，仍是数据由小到大排列的线性表，存储到另一个顺序表C中。
（2）如果顺序表B的大小为（m+n）个单元，是否可不利用顺序表C而合并成的线性表存放于顺序表B中？试设计此算法。
（3）设顺序表A有m+n个元素，且前m个有序，后n个有序，设计一个算法，使得整个顺序表有序。
void Merge1(SqList A,SqList B,SqList &C)
{ InitList_sq(C);
i=j=1;k=0;
a_len=ListLength_sq(A);
b_len=ListLength_sq(B);
while((i<=a_len)&&(j<=b_len)) ∥A和A均为非空
{ GetElem_sq(A,i,ai);GetElem_sq(B,j,bj);
if(ai<=bj) {ListInsert_sq(C,++k,ai);++i;}
else{ListInsert_sq(C,++k,bj);++j;}
}
while(i<=a_len)
{ GetElem_sq(A,i++,a);ListInsert_sq(C,++k,a);}
while(j<=Lb_len)
{ GetElem(B,j++,b);ListInsert_sq(C,++k,b); }
}∥Merge1
}
void Merge2(SqList A,SqList &B)
{
for(i=1; i<= B.length; i++)
{ GetElem_sq(A,i,ai);
j=B.length;
while(j>0&&B.elem[j-1]>ai)
{ B.elem[j]=B.elem[j-1]; j--;}
B.elem[j]=ai;
B.length++;
}
void Merge3(SqList &A)
{ j =1;
for(i=m; i< A.length; i++)
{ ai=A.elem[i-1]; // GetElem_sq(A,i,ai);
j=i;
while(j>0&&a.elem[j-1]>ai)
{ A.elem[j]=A.elem[j-1]; j--;}
A.elem[j]=ai;
}
}
4．有一个递增单链表（允许出现值域重复的结点），设计一个算法删除值域重复的结点。并分析算法的时间复杂度。
void DelList(LinkList &L)
{ p=L->next;
while(p->next)
if(p->data==p->next->data)
{q=p->next;
p->next=q->next;
free(q);
}
else p=p->next;
}
5．设计一个带头结点的单链表L中删除一个最小值结点的算法。
Status DelMin(LinkList &L)
{ if(L->next) return ERROR;
minpre=ppre=L; minp=p=L->next;
while(p)
{if(p->data<minp->data)
{ minp=p; minpre=ppre;}
ppre=p; p=p->next;
}
minpre->next=minp->next;
free(minp);
}
6．已知3个单链表A、B、C中的结点均依元素值自小至大非递减排列（可能存在两个以上值相同的结点），设计一个算法使链表A中仅留下3个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为O（m+n+p），其中m、n、和p分别为3个表的长度。
7．两个整数序列A=（a1，a2，…，am）和B=（b1，b2，…，bn）用两个单链表存储，设计一个算法，判断序列B是否是序列A的子序列。
Status SubList(LinkList A,LinkList B)
{ pa=A->next;
while(pa)
{ pb=B->next;
while(pa&&pa->data!=pb->data) pa=pa->next; //找到第一个元素相同的结点
ta=pa;
while(ta&&pb&&ta->data==pb->data)
{ ta=ta->next; pb=pb->next;}
if(!pb) return TRUE;
if(pa) pa=pa->next;
}
return FALSE;
}
8．假设表达式中允许包含3种括号：圆括号、方括号、大括号。设计一个算法采用顺序栈判断表达式中的括号是否正确配对。
9．设以整数序列1，2，3，4作为顺序栈st的输入，利用push（进栈）和pop（出栈）操作，写出所有可能的输出并编程实现算法。
void p(SqStack &S,int k,int *out,int i)//从k开始的可能的出栈序列放到out[i]中
{ int x;
if(k<=n) //第一种情况：如果站外有车,那么车k入站.
{ Push(S,k);
p(S,k+1,out,i);
Pop(S,x); //恢复为原来的状态,即把车k恢复在站外的位置(回溯)
}
if(!StackEmpty(S)) //第二种情况：如果站内有车,车m出站;
{ Pop(S,x);
out[i++]=x;
if(i>=n&&StackEmpty(S)) //判断如果已经全部出站,那么我们可以打印了.
print(out,i);
p(S,k,out,i);
Push(S,x); i--; //恢复站内的状态，即把车m退回到站内;(这里也是回溯)
}
}

10．设计一个算法，利用栈的InitStack（）、Push（）、Pop（）和StackEmpty( )等基本运算返回指定栈中栈底元素。
Status GetBase(Stack S, SElemType &e)
{ InitStack(T);
while(!StackEmpty (S))
{Pop(S,e); Push(T,e);}
while(!StackEmpty (T))
{Pop(T,e); Push(S,e);}
return OK;
}

11．假设I和O分别表示入栈和出栈操作，栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列。
（1）下面所示的序列中那些是合法的？
A．IOIIOIOO
B．IOOIOIIO
C．IIIOIOIO
D．IIIOOIOO
（2）通过对（1）的分析，写出一个算法判定所给的操作序列是否合法。若合法返回1，否则返回0（假设被判定的操作序列已存入一维数组中）
Status Panduan(char *t)
{ InitStack(S);
while(*t)
{switch(*t)
{case ‘I’: Push(S,*t); break;
case ‘O’:if(!StackEmpty (S)) { Pop(S,e); break;} else return 0;
}
t++;
}
if(!EmptyStack(T))
return 1;
return 0;
}
12．设计一个算法，利用队列的基本运算返回指定队列中的队尾元素。
Status GeTail(Queue Q, QElemType &e)
{ InitQueue(T);
while(!QueueEmpty (Q))
{DeQueue(Q,e); EnQueue(T,e);}
while(!QueueEmpty (T))
{DeQueue(T,e); EnQueue(Q,e);}
return OK;
}
13．设计一个环形队列，用front和rear分别作为队头和队尾指针，另外用一个标志tag表示队列是空（0）还是不空（1），这样就可以用front=rear作为队满的条件，要求设计队列的相关基本运算方法
#define MAXQSIZE 100 ∥最大队列长度
typedef struct
{QElemType *base; ∥初始化的动态分配存储空间
int front; ∥头指针,若队列不空,指向队列头元素
int rear; ∥尾指针,若队列不空,指向队列尾元素的下一个位置
int tag; //队列是否满的标识
}SqQueue;
Statue InitQueue(SqQueue &Q)
{∥ 构造一个空队列Q
Q.base = (QElemType *)malloc(MAXQSIZE *
sizeof(QElemType));
if (!Q.base) exit(OVERFLOW); ∥存储分配失败
Q.front = Q.rear = 0;
Q.tag=0; //不满
return OK;
}
Status EnQueue(SqQueue &Q,QElemType e)
{∥ 插入元素e为Q的新的队尾元素
if(Q.tag==1) return ERROR; ∥队列满
Q.base[Q.rear] = e;
Q.rear = (Q.rear+1)% MAXQSIZE;
if(Q.rear == Q.front) Q.tag=1;
return OK;
}
Status DeQueue(SqQueue &Q, QElemType &e)
{∥ 删除队头元素，送给变量e
if(Q.tag==0) return ERROR; ∥队列空
e=Q.base[Q.front];
Q.front = (Q.front+1)% MAXQSIZE;
if(Q.front= =Q.rear) Q.tag=0;
return OK;
}