电大资源网《数据结构（本）》形成性考核册作业2答案
最近更新：2020-04-14
【数据结构】形考作业二：
（本部分作业覆盖教材第3-5章的内容）
一、单项选择题
1．C 2．B 3．A 4．C 5．B 6．A 7．B 8．C 9．A 10．C
11．B 12．C 13．B 14．B 15．A 16．C 17．B 18．A 19．C 20．D
21．B 22．D 23．C 24．B 25．D 26．A 27．C 28．D 29．D 30．C 31．A 32．D
二、填空题
1．后进先出
2．下一个
3．增1 增1
4．假上溢
5．
栈是否满 s->top=MAXSIZE-1 栈顶指针 栈顶对应的数组元素 栈是否空 s->top=-1 栈顶元素 修改栈顶指针
6．bceda
7．终止条件 递归部分
8．LU->front==LU->rear
9．运算符 操作数 ab+c/fde/--
10．s->next=h;
11．h=h->next;
12．r->next=s;
13．f=f->next;
14．字符
15．顺序存储方式 链式存储方式
16．0 空格字符的个数
17．特殊 稀疏
18．（） （（）） 2
19．（（d,e,f））
20．串长度相等且对应位置的字符相等
21．i(i-1)/2+j
22．行下标、列下标、非零元素值
三、问答题
1．简述栈和一般线性表的区别。
答：栈是一种先进后出的线性表，栈的插入和删除操作都只能在栈顶进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。
2．简述队列和一般线性表的区别。
队列是一种先进先出的线性表，队列的插入只能在队尾进行，队列的删除只能在队头进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。
3．链栈中为何不设头结点？
答：因为链栈只在链头插入和删除结点，不可能在链表中间插入和删除结点，算法实现很简单，所以一般不设置头结点。
4．利用一个栈，则：
（1）如果输入序列由A，B，C组成，试给出全部可能的输出序列和不可能的输出序列。
（2）如果输入序列由A，B，C，D组成，试给出全部可能的输出序列和不可能的输出序列。
答：
（1）栈的操作特点是后进先出，因此输出序列有：
A入，A出，B入，B出，C入C出，输出序列为ABC。
A入，A出，B入，C入，C出，B出，输出序列为ACB。
A入，B入，B出，A出，C入，C出，输出序列为BAC。
A入，B入，B出，C入，C出，A出，输出序列为BCA。
A入，B入，C入，C出，B出，A出，输出序列为CBA。
由A，B，C组成的数据项，除上述五个不同的组合外，还有一个C，A，B组合。但不可能先把C出栈，再把A出栈，（A不在栈顶位置），最后把B出栈，所以序列CAB不可能由输入序列A，B，C 通过栈得到。
（2）按照上述方法，可能的输出序列有：
ABCD，ABDC，ACBD，ACDB，ADCB，BACD，BADC，BCAD，BCDA，BDCA，CBAD，CBDA，CDBA，DCBA。
不可能的输出序列有：
DABC，ADBC，DACB，DBAC，BDAC，DBCA，DCAB，CDAB，CADB，CABD
5．用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到1342出栈顺序，相应的S和X操作串是什么？
答：应是SXSSXSXX。各操作结果如下：
S 1入栈
X 1出栈 输出序列：1
S 2入栈
S 3入栈
X 3出栈 输出序列：13
S 4入栈
X 4出栈 输出序列：134
X 2出栈 输出序列：1342
6．有5个元素，其入栈次序为：A、B、C、D、E，在各种可能的出栈次序中，以元素C、D最先的次序有哪几个？
答：从题中可知，要使C第一个且D第二个出栈，应是A入栈，B入栈，C入栈，C出栈，D入栈。之后可以有以下几种情况：
（1）B出栈，A出栈，E入栈，E出栈，输出序列为：CDBAE。
（2）B出栈，E入栈，E出栈，A 出栈，输出序列为CDBEA。
（3）E入栈，E出栈，B出栈，A出栈，输出序列为CDEBA
所以可能的次序有：CDBAE，CDBEA，CDEBA
7．写出以下运算式的后缀算术运算式
⑴ 3x2+x-1/x+5
⑵ (A+B)*C-D/(E+F)+G
答；对应的后缀算术运算式
⑴ 3x2^*x+1x/-5+
⑵ AB+C*DEF+/-G+
8． 简述广义表和线性表的区别和联系。
答：广义表是线性表的的推广，它也是n(n>0)个元素a1 ,a2…ai… an的有限序列，其中ai或者是原子或者是一个广义表。所以，广义表是一种递归数据结构，而线性表没有这种特性，线性表可以看成广义表的特殊情况，当ai都是原子时，广义表退化成线性表。
四、程序填空题
1．
（1）q->front->next=p->next;
（2）free(p);
（3）q->rear=q->front
五、综合题
1．
答：出队序列是e2,e4,e3,e6,e5,e1的过程：
⑴ e1入栈（栈底到栈顶元素是e1）
⑵ e2入栈（栈底到栈顶元素是e1,e2）
⑶ e2出栈（栈底到栈顶元素是e1）
⑷ e3入栈（栈底到栈顶元素是e1,e3）
⑸ e4入栈（栈底到栈顶元素是e1,e3,e4）
⑹ e4出栈（栈底到栈顶元素是e1,e3）
⑺ e3出栈（栈底到栈顶元素是e1）
⑻ e5入栈（栈底到栈顶元素是e1,e5）
⑼ e6入栈（栈底到栈顶元素是e1,e5,e6）
⑽ e6出栈（栈底到栈顶元素是e1,e5）
⑾ e5出栈（栈底到栈顶元素是e1）
⑿ e1出栈（栈底到栈顶元素是空）
栈中最多时有3个元素，所以栈S的容量至少是3。
2．
算法设计如下：
/*只有一个指针rear的链式队的基本操作*/
#include <stdio.h>
typedef char elemtype;
struct node /*定义链队列结点*/
{
elemtype data;
struct node *next;
};
typedef struct queue /*定义链队列数据类型*/
{
struct node *rear;
} LinkQueue;
void initqueue(LinkQueue *Q)/*初始化队列*/
{
Q=(struct queue *)malloc(sizeof(struct queue));
Q->rear=NULL;
}
void enqueue(LinkQueue *Q,elemtype x) /*入队算法*/
{
struct node *s,*p;
s=(struct node *)malloc(sizeof(struct node));
s->data=x;
if (Q->rear==NULL) /*原为空队时*/
{
Q->rear=s;
s->next=s;
}
else /*原队不为空时*/
{
p=Q->rear->next; /*p指向第一个结点*/
Q->rear->next=s; /*将s链接到队尾*/
Q->rear=s; /*Q->rear指向队尾*/
s->next=p;
}
}
void delqueue(LinkQueue *Q) /*出队算法*/
{
struct node *t;
if (Q->rear==NULL)
{
printf("队列为空!\n");
return(0);
}
else if (Q->rear->next==Q->rear) /*只有一个结点时*/
{
t=Q->rear;
Q->rear=NULL;
}
else /*有多个结点时*/
{
t=Q->rear->next; /*t指向第一个结点*/
Q->rear->next=t->next; /*引成循环链*/
}
free(t);
}
elemtype gethead(LinkQueue *Q) /*取队首元素算法*/
{
if (Q->rear==NULL)
printf("队列为空!\n");
else
return(Q->rear->next->data);
}
int emptyqueue(LinkQueue *Q) /*判断队列是否为空算法*/
{
if (Q->rear==NULL) return(1); /*为空,则返回true*/
else return(0); /*不为空,则返回flase*/
}
void dispqueue(LinkQueue *Q) /*显示队列中元素算法*/
{
struct node *p=Q->rear->next;
printf("队列元素:");
while (p!=Q->rear)
{
printf("%c ",p->data);
p=p->next;
}
printf("%c\n",p->data);
}
六、完成：实验2――栈、队列、递归程序设计
根据实验要求（见教材P203）认真完成本实验，并提交实验报告。
