数据结构（本）形成性考核作业答案。
作业2答案。
本部分作业覆盖教材第3-5章的内容）
一、单项选择题。
1．c 2．b 3．a 4．c 5．d 6．a 7．b 8．c 9．c 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．假上溢。
栈是否满 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．特殊稀疏。
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）q->front->next=p->next;
2）free(p);
3）q->rear=q->front
五、综合题。
答：出队序列是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。
算法设计如下：
*只有一个指针rear的链式队的基本操作*/
#include <>
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原为空队时*/
else原队不为空时*/
void delqueue(linkqueue *q) /出队算法*/
struct node *t;
if (q->rear==null)
else if (q->rear->next==q->rear) /只有一个结点时*/
else /*有多个结点时*/
free(t);
elemtype gethead(linkqueue *q) /取队首元素算法*/
int emptyqueue(linkqueue *q) /判断队列是否为空算法*/
void dispqueue(linkqueue *q显示队列中元素算法*/
struct node *p=q->rear->next;
printf("队列元素：")
while (p!=q->rear)
printf("%c",p->data);
形成性考核作业答案
建筑结构试验 形成性考核作业答案。建筑结构试验 第一次形成性考核解析。说明 本次形成性考核是针对教材第一章和第二章的内容编写的。一 选择题。1b 2c 3d 4b 5c 6d 7a 8d 二 填空题。1生产检验科学研究 2振动疲劳 3实测值设计值 4周期性的反复的 5容重获得。6均布集中 7拉力压力...
地域文化 本 形成性考核作业 三
一 判断题 根据题意判断正误，并在括号中打 或 每小题2分，共20分 先秦时期，浙江地区就已经有了春节这项民间节日。清明节又叫踏青节。南宋时，浙江已经有了庆祝中秋节的习俗。九姓渔民水上婚礼是杭州钱塘江上流行的一种婚俗。浙江的火葬习俗始于唐朝。社戏 是浙江绍兴地区民间祭社时的一种文化活动。普陀山是我国...
地域文化 本 形成性考核作业 三
一 判断题 根据题意判断正误，并在括号中打 或 每小题2分，共20分 先秦时期，浙江地区就已经有了春节这项民间节日。清明节又叫踏青节。南宋时，浙江已经有了庆祝中秋节的习俗。九姓渔民水上婚礼是杭州钱塘江上流行的一种婚俗。浙江的火葬习俗始于唐朝。社戏 是浙江绍兴地区民间祭社时的一种文化活动。普陀山是我国...