发布时间 : 星期六 文章数据结构习题及答案2009年12月14日更新完毕开始阅读0948a4f7ba0d4a7302763aad
参考答案
第1章 绪论
一、选择题
1.B 二、判断题
1.× 2.× 3.× 4.√ 5.× 6.×
2.B 3.C
三、填空题
1.数据逻辑关系；2.线性结构和树形结构；3.数据间的逻辑关系；4.映射(或表示)； 5.时间复杂度和空间复杂度；6.有穷性、确定性、可执行性；7.n(n+1)/2-3; 8.O(n) 四、应用题
1.数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象及对象间的关系和施加于对象的操作等的学科。 2．（1）数据的逻辑结构反映数据元素之间的逻辑关系（即数据元素之间的关联方式或“邻接关系”），数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。数据的运算是对数据定义的一组操作，运算是定义在逻辑结构上的，和存储结构无关，而运算的实现则是依赖于存储结构。
（2）逻辑结构相同但存储不同，可以是不同的数据结构。例如，线性表的逻辑结构属于线性结构，采用顺序存储结构为顺序表，而采用链式存储结构称为线性链表。 3．“数据结构”这一术语有两种含义，一是作为一门课程的名称；二是作为一个科学的概念。作为科学概念，目前尚无公认定义，一般认为，讨论数据结构要包括三个方面，一是数据的逻辑结构，二是数据的存储结构，三是对数据进行的操作（运算）。而数据类型是值的集合和操作的集合，可以看作是已实现了的数据结构，后者是前者的一种简化情况。
23
4.(1)O(1) (2)O(n) (3)O(n)
第2章 线性表
一、选择题
1.A 2.B 3.C 4.A 5.B 6.C 7.C 8.C 9.B 10.B
二、判断题
1.× 2.× 3.× 4.× 5.× 6.×
三、填空题
1.(n-1)/2； 2.n-i+1； 3.O(1)； ４.O(n)； 5.数据元素的的存储位置相邻； 6.q=p->next;p->next=q->next;free(q); 7.p->next!=NULL 四、应用题
1. [题目分析]因为两链表已按元素值递增次序排列，将其合并时，均从第一个结点起进行比较，将小的链入链表中，同时后移链表工作指针。该问题要求结果链表按元素值递减
17
次序排列。故在合并的同时，将链表结点逆置。 LinkList Union(LinkList la,lb)
∥la,lb分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列，本算法
将两链表合并成一个按元素值递减次序排列的单链表。
{ pa=la->next; pb=lb->next;∥pa，pb分别是链表la和lb的工作指针
la->next=null; ∥la作结果链表的头指针，先将结果链表初始化为空。
while(pa!=null && pb!=null) ∥当两链表均不为空时作 if(pa->data<=pb->data)
{ r=pa->next; ∥将pa 的后继结点暂存于r。
pa->next=la->next; ∥将pa结点链于结果表中，同时逆置。
la->next=pa;
pa=r; ∥恢复pa为当前待比较结点。 }
else
{r=pb->next;∥ 将pb 的后继结点暂存于r。
pb->next=la->next; ∥将pb结点链于结果表中，同时逆置。 la->next=pb;
pb=r; ∥恢复pb为当前待比较结点。 }
while(pa!=null) ∥将la表的剩余部分链入结果表，并逆置。 {r=pa->next; pa->next=la->next; la->next=pa; pa=r; } while(pb!=null)
{r=pb->next; pb->next=la->next; la->next=pb; pb=r; } }∥算法Union结束。
［算法讨论］上面两链表均不为空的表达式也可简写为while(pa&&pb),两递增有序表合并成递减有序表时，上述算法是边合并边逆置。也可先合并完，再作链表逆置。后者不如前者优化。算法中最后两个while语句，不可能执行两个，只能二者取一，即哪个表尚未到尾，就将其逆置到结果表中，即将剩余结点依次前插入到结果表的头结点后面。
2. [题目分析] 本题要求将链表中数据域值最小的结点移到链表的最前面。首先要查找最小值结点。将其移到链表最前面，实质上是将该结点从链表上摘下（不是删除并回收空间），再插入到链表的最前面。
void delinsert（LinkList &list）
∥list是非空线性链表，链结点结构是（data，next），data是数据域，next是链域。
∥本算法将链表中数据域值最小的那个结点移到链表的最前面。 {p=list->next；∥p是链表的工作指针
pre=list； ∥pre指向链表中数据域最小值结点的前驱。 q=p； ∥q指向数据域最小值结点，初始假定是第一结点 while （p->next!=null）
{if（p->next->data
if (q!=list->next) ∥若最小值是第一元素结点，则不需再操作
18
{pre->next=q->next； ∥将最小值结点从链表上摘下； q->next= list->next；∥将q结点插到链表最前面。 list->next=q；
}
}∥算法结束
[算法讨论] 算法中假定list带有头结点，否则，插入操作变为q->next=list；list=q。 3. [题目分析] 在无序的单链表上，查找最小值结点，要查遍整个链表，初始假定第一结点是最小值结点。当找到最小值结点后，判断数据域的值是否是奇数，若是，则“与其后继结点的值相交换”即仅仅交换数据域的值，用三个赋值语句即可交换。若与后继结点交换位置，则需交换指针，这时应知道最小值结点的前驱。至于删除后继结点，则通过修改最小值结点的指针域即可。
[算法设计]
void MiniValue（LinkList la）
∥la是数据域为正整数且无序的单链表，本算法查找最小值结点且打印。若最小值结点的数值是奇数，则与后继结点值交换；否则，就删除其直接后继结点。
{p=la->next； ∥设la是头结点的头指针，p为工作指针。
pre=p； ∥pre指向最小值结点，初始假定首元结点值最小。 while（p->next!=null） ∥p->next是待比较的当前结点。 {if（p->next->data
p=p->next； ∥后移指针 }
printf（“最小值=%d\\n”，pre->data）； if（pre->data%2!=0） ∥处理奇数
if（pre->next!=null）∥若该结点没有后继，则不必交换
{t= pre->data；pre->data=pre->next->data；pre->next->data=t；}∥交换完毕
else∥处理偶数情况
if（pre->next!=null）∥若最小值结点是最后一个结点，则无后继 {u=pre->next；pre->next=u->next；free（u）；} ∥释放后继结点空间
第3章 栈与队列
一、选择题 1.B 2.B 3.D 4.C 5.B 6.C 7.B 8.D 9.D 10.D 11.A 12.B 13.C 14.B 二、判断题 1.√ 2.× 3.√ 4.√ 5.√ 6.× 7.× 三、填空题
1.栈； 2.3 1 2； 3.100Ch; 4.IOIIOIOO; 5.假溢出；6.（rear+1）%M==front; 7.e=sq.data[sq.front];sq.front=(sq.front+1)%(M+1) 四、应用题
1.三个：CDEBA，CDBEA，CDBAE
2.1）能得到325641。在123依次进栈后，3和2出栈，得部分输出序列32；然后4，5入栈，5出栈，得部分出栈序列325；6入栈并出栈，得部分输出序列3256；最后退栈，直到栈空。得输出序列325641。其操作序列为IIIOOIIOIOOO。
（2）不能得到输出顺序为154623的序列。部分合法操作序列为IOIIIIOOIO，得到部分
19
输出序列1546后，栈中元素为23，3在栈顶，故不可能2先出栈，得不到输出序列154623。
3.两栈共享一向量空间（一维数组），栈底设在数组的两端，两栈顶相邻时为栈满。设共享数组为S[MAX]，则一个栈顶指针为-1，另一个栈顶指针为MAX时，栈为空。
用C写的入栈操作push（i，x）如下： const MAX=共享栈可能达到的最大容量 typedef struct node {elemtype s[MAX]； int top[2]； }anode； anode ds;
int push(int i,elemtype x)
//ds为容量有MAX个类型为elemtype的元素的一维数组，由两个栈共享其空间。
i的值为0或1，x为类型为elemtype的元素。本算法将x压入栈中。如压栈成功，返回1；否则，返回0。
{if（ds.top[1]-ds.top[0]==1）{printf（“栈满\\n”）；return（0）；} switch（i）
{case 0：ds.s[++ds.top[i]]=x；break； case 1：ds.s[--ds.top[i]]=x； return（1）；}//入栈成功。 }
五、算法设计题
1. （1）A和D是合法序列，B和C 是非法序列。 （2）设被判定的操作序列已存入一维数组A中。 int Judge(char A[])
//判断字符数组A中的输入输出序列是否是合法序列。如是，返回true，否则返
回false。
{i=0; //i为下标。
j=k=0; //j和k分别为I和字母O的的个数。 while(A[i]!=‘\\0’) //当未到字符数组尾就作。 {switch(A[i])
{case‘I’: j++; break; //入栈次数增1。
case‘O’: k++; if(k>j){printf(“序列非法\\n”)；exit(0);} }
i++; //不论A[i]是‘I’或‘O’，指针i均后移。}
if(j!=k) {printf(“序列非法\\n”)；return(false);} else {printf(“序列合法\\n”)；return(true);} }//算法结束。
[算法讨论]在入栈出栈序列（即由‘I’和‘O’组成的字符串）的任一位置，入栈次数（‘I’的个数）都必须大于等于出栈次数（即‘O’的个数），否则视作非法序列，立即给出信息，退出算法。整个序列（即读到字符数组中字符串的结束标记‘\\0’），入栈次数必须等于出栈次数（题目中要求栈的初态和终态都为空），否则视为非法序列。
2. [题目分析]栈的特点是后进先出，队列的特点是先进先出。所以，用两个栈s1和s2模拟一个队列时，s1作输入栈，逐个元素压栈，以此模拟队列元素的入队。当需要出队时，将栈s1退栈并逐个压入栈s2中，s1中最先入栈的元素，在s2中处于栈顶。s2退栈，
20