1、（3）单链表单链表的每个结点都有两个域，一个数据域和一个指针域，称之为单链表。（4）双链表以链表形式存储的线性表，其结点包含一个数据域和两个指针域，称之为双链表。（5）循环链表若线性链表的最后一个结点的指针指向头结点，使得链表头尾结点相连，就构成了循环链表。（6）存储密度存储密度定义为结点数据本身所占的存储量与结点结构实际分配的存储量的比值。顺序表的存储密度等于1；链表结构存储密度小于1。二判断题（下列各题，正确的请在前面的括号内打；（1） （2） （3） （4） （5）（6） （7） （8） （9） （10）1 一定2 不必 3 有限的 一对一关系 4 节省存储 随机存取 5 插入 删除 小
2、 6 n/2 表长n和插入位置 7 （n-1）/2 表长n和删除位置 8 O （1） 9 直接前驱 10的直接前趋结点的地址 O （n） 11O （1） 12*P的直接前驱结点的地址 O （n） O （1） 13头指针 （1） B （2） A （3） B （4） C （5） A （6） A （7） B （8） B （9） D （10） B五简答题1顺序存储结构的长处是节约存储空间，可以随机存取。（缺点是插入、删除要作大量移动，不易扩充）；链表存储结构优点是插入、删除操作容易，表的扩充方便。（缺点是存储密度低）。2 头指针指向链表中第一个结点（头结点或无头结点时的开始结点）的指针。头结点在开始结
3、点之前附加的一个结点。开始结点在链表中，存储第一个数据元素的结点。3 主要是简化操作。由于表的操作常在表的两端进行，所以对单循环链表，当知道其尾指针rear后，其另一端的头指针是rear-next-next（表中代头结点），仅改变两个指针值即可，运算时间为O（1）。六（1）返回结点*p的直接前趋结点地址。（2）交换结点*p和结点*q（p和q的值不变）。七 程序设计题1解：void Show（ListNode *P） ListNode *t=P; do printf（%c,t-data）; t=t-rear; while（t!=P）;2解：void delete（ListNode *L） Lis
4、tNode *p=L,*q; if（L-data=X） printf（“值为x的结点是第一个结点，没有直接前趋结点可以删除”）; return; for（;p-data!=X;q=p,p=p-next）; /删除指针p所指向的结点 q-next=p-next; delete p;3解void Del（SeqList *L,int i,int k） int j=i-1+k; for（j=0;jdatai-1+j=L-datai+k-2+j; if（i+k-2+jL-last） break; 4 解：本题是遍历该链表的每个结点，每遇到一个结点，结点个数加1，结点个数存储在变量n中。实现本题功能的函
5、数如下：int counter（head）node *head； node *p; int n0; p= head； while（p!=NULL） if（p-data=x） n+；p= p-return（n）;5解：本题的算法思想是：先找到两链表的尾指针，将第一个链表的尾指针与第二个链表的头结点链接起来，使之成为循环的。函数如下：node *link（head1,head2）node *head1, *head2; node *p, *q; p=head1; while（p-next!=head1） p=p- q=head2; while（q-=head2） q=q- p-next=head2
6、;next=head1; return（head1）;6解：假设输入一组多项式的系数和指数，以输入系数为标志结束，在建立多项式链表时，总是按照指数从大到小顺序排列的。两个多项式链表A和B，其头指针分别是heada和headb，这两个多项的多项式链表为C，其头指针为headc。 struct pnode *padd（heada，headb） struct pnode *heada, *headb； struct pnode *headc, *p, *q,*s; int x; p= heada;q=headb; headc（struct pnode *）malloc（sizeof（struct p
7、ndoe）;r=headc;while（p!=NULL&q! if （p-exp=q-exp） /两结点指数相等时，将两系数相加生成新结点插入C中 x=p-coef +q-coef;if（x!=0） s（struct pnode *）malloc（sizeof（struct pnode）; s-coefs;exp=p-exp; r-links; r=s;p=p-link;q=q-else /两结点的指数不相等时，将其中较小系数的结点复制成一新结点插入C中if（p-expexp） s=（struct pnode*）malloc（sizeof（struct pnode）;coef=q-exp=q-
8、link=s; q=q- else s（struct pnode*）malloc（sizeof（struct pnode）;coef=p- p=p-=NULL） / 复制A的余下部分s=（struct pnode *）malloc（sizeof（struct pnode）; / 复制一个结点s / 把s链接到C中 while（q!=NULL） / 复制B的余下部分 / 把s链接到C中r-link=NULL; / 最后结点的link域置空s=headc; / 删除C的头结点headc=headc-free（s）;return（headc）;习题3一. 名词解释（1） 栈 只允许在一端进行插入或删
9、除操作的线性表称为栈。其最大的特点是“后进先出”。（2） 顺序栈采用顺序存储结构的栈称为顺序栈。（3） 链栈采用链式存储结构的栈称为链栈。（1） （2） （3） （4） （5） （6）三. 填空题（1）后进先出（2）栈顶 栈底（3）栈空 栈满（4）O（1） O（1）（5）必须一致（6）栈（7）栈空 （8）p-next=top top=p（9）- - + +（10）LS-next 首 四. 单选题（1）B （2）C （3）A （4）D （5）B（6）C （7）D （8）B （9）A （10）A五. 求下列表达式的后缀表达式（要求写出过程）（1）A B C D / （2）0 A B C * + D
10、 E / +（3）A B C + * D * E -（4）A B + C * E F G H / + / - D -（5）8 5 2 + / 6 -六算法设计题用一整型变量top表示栈顶指针，top为0时表示栈为空。栈中元素从S 1开始存放元素。（1）入栈算法：void push （char x） if （top+M）MAXLEN-1） printf （“堆栈溢出！”）; if （top= =0） top+; S top=x; top=top+M;（2）出栈算法： void pop （char x） printf （“堆栈为空栈！ if （top= =1） x= S top; top; top
11、=topM;设表达式在字符数组a 中，使用一堆栈S来帮助判断。 int correct （char a ）stack s ; InitStack （s）; / 调用初始化栈函数 for （i=0; i strlen（a）;i+） if （ai= =（） Push （s,（）; else if （ai= =） if StackEmpty （s） / 调用判栈空函数 return 0; / 若栈为空返回0；否则出栈 else Pop（s）; if （StackEmpty （s） ） / 调用判栈空函数 printf （“配对正确！ / 若栈空，说明配对正确，并返回1 printf （“配对错误！
12、/ 配对错误返回0习题4一.名词解释（1）队列只允许在一端进行插入，另一端进行删除操作的线性表称为队列。其最大的特点是“先进先出”。（2）顺序队列采用顺序存储结构的队列称为顺序队列。（3）链队列采用链式存储结构的称队列为链队列。（4）循环队列为了解决顺序队列中“假溢出”现象，将队列的存储空间想象为一个首尾相链的环（即把队头元素与对尾元素链结起来），存储在其中的队列称为循环队列。（1） （2） （3） （4） （5） （6）1先进先出 2队尾 队头3队列是否为空 队列是否为满 4可变的 5-1 NULL 6O（n） O（1） O（1） O（1） 7front=rear front=（rear+1
13、）% MAXLEN MAXLEN-front 8空 只含有一个结点 9front=rear & front NULL 10队尾指针 写入 四、单项选择题（1）A （2）C （3）A （4）D （5）A（6）A （7）B （8）A （9）C （10）A答：n个（同类）数据元素的有限序列称为线性表。线性表的特点是数据元素之间存在“一对一”的关系。栈和队列都是操作受限制的线性表，它们和线性表一样，数据元素之间都存在“一对一”的关系。 不同之处是：栈是只允许在一端进行插入或删除操作的线性表，其最大的特点是“后进先出”；队列是只允许在一端进行插入，另一端进行删除操作的线性表，其最大的特点是“先进先出”。
14、用一个循环数组Queue0，n-1表示该循环队列，头指针为front，计数器count用来记录队列中结点的个数。（1）入队算法： void inqueqe（int x） int temp;if（count=n） printf（“队列上溢出n”）;else count+ temp=（front+count）%n; Queuetemp=x（2）出队算法： int outqueue（）if （count=0） printf（“队列下溢出n”）; temp=Queuefront; front=（front+1）%n; count-; return temp;队列为空：count=0,front=1队列
15、为满：count=MAXLEN队列尾的第一个元素位置=（front+count）%MAXLEN队列首的第一个元素位置=（front+1）%MAXLENconst MAXLEN=100;int queueMAXLEN;int front,count; / 定义队头和计算器void init（） / 初始化队列 front=1; count=0;int empty（） / 判定队列是否为空 if（count=0） return（1）; else return（0）; void outqueue（int queue,x） / 取队列头元素给x if（count=0） printf（“下溢出n”）;
16、front=（front+1）%MAXLEN; x=queuefront; void inqueue（int queue,int x） / x入队列 int place; if（count=MAXLEN） printf（“上溢出n”）;count+;place=（front+count）%MAXLEN;queueMAXLEN=x; void outqueue（int queue） / 删除队列头元素 if（count=0） printf（“队列下溢出n”）;front=（front+1）%MAXLEN;count-;3（1）解：定义本题队列的结点类型如下：typedef struct link
17、node int data; struct linknode *next; qu; qu *rear;inqueue（int x） / 向队列插入结点x qu *head, *s; s=（qu *）malloc（size（qu）; / 创建一个新结点data=x; if（rearNUlL） /循环队列为空，则建立一个结点的循环队列 rears; rear-nexts; else / 循环队列不为空，则将s插到后面 head=rear-next； rear=s; / rear始终指向最后一个结点nexthead;（2）解：void delqueue（rear） if（rear=NULL） pri
18、ntf（“下溢出!n”）; else head=rear- /head指向队首结点 if（head=rear） rear=NULL /只有个结点，则直接删除该结点 else rear-next=head-next /否则删除第一个结点 free（head）； / 释放队首结点 习题5串：串（string）是由零个或多个字符组成的有限序列。一般记为S“a1 a2.an”（n0）其中，S是串名，用双引号或单引号括起来的字符序列是串的值，ai（1in）称为串的元素，它可以是字母、数字、空格或其他字符。串中字符的个数n称为串的长度。广义表：广义表（Generalized Lists）是n （n0）个数
19、据元素a1, a2,，ai，an的有序序列，一般记作： ls= （a1，a2,，ai,，an）其中：ls是广义表的名称，n是它的长度。每个ai（1in）是ls的成员，它可以是单个元素，称为广义表ls的原子，也可以是一个广义表，称为广义表的子表。当广义表ls非空时，称第一个元素a1为ls的表头（head），称其余元素组成的表（a2,ai,，an）为ls的表尾（ tail）。广义表的定义是递归的。（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）三填空题（10个）1长度2空串 零3顺序存储4数据 指针 数据 指针5模式匹配6顺序存储和链式存储7（a） （b）,c）,（d）8广义表1B
20、2D 3B 4C 5C 6A 7B 8A 1简述串的存储结构及各自的特点。串的存储方式有主要有顺序存储、堆分配存储和链式存储。顺序结构：用一组地址连续的存储单元存储串的字符序列，构成串的顺序存储，简称为顺序串。特点：这种结构是按照预设大小，为每个定义的串变量分配一个固定长度的存储区。因此存在存储空间的越界或浪费的问题。对于操作如查找但是操作简单方便。堆分配存储结构：在内存中开辟地址连续的存储空间作为串的可利用存储空间，称为堆空间，根据每个串的长度，动态地为每个串在堆空间里申请相应大小的存储区域的一种存储结构。以一组地址连续的存储单元存放串的字符序列，但其存储空间是在算法执行过程中动态分配得到的
21、，串也是顺序存储在所申请的存储区域中。由于堆分配存储结构的串既有顺序存储结构的特点，又没有造成对存储空间的浪费和对串长加以限制，使用非常灵活。链式存储结构：是将存储区域分成一系列大小相同的结点，每个结点有两个域即数据域data和指针域next。其中数据域用于存放字符串元素，指针域用于存放下一个结点的地址。在串中使用链式存储结构同样是在插入、删除等操作中没有移动元素所带来的时间耗费，存储空间的扩展容易；但结点的容量会带来存储空间的利用率降低。2广义表具有哪些性质？（1） 广义表是一种多层次的数据结构。广义表的元素可以是原子，也可以是子表，而子表的元素还可以是子表。（2） 广义表可以是递归的表。广
22、义表的定义并没有限制元素的递归，即广义表也可以是其自身的子表。例如表E就是一个递归的表。（3） 广义表可以为其他表所共享。例如D=（A, B, C）时，表A、B、C是表D的共享子表。在D中可以不必列出子表的值，而用子表的名称来引用。六下述算法的功能是什么（1）实现串S和串T的连接运算。（2）返回串S中从第n1个字符开始取n2个字符组成的子串。七程序设计题1写一个递归算法来实现字符的逆序存储，要求不另设存储空间。#include stdio.h#include MAXSIZE 80char nextMAXSIZE80; /*串的最大长度*/void reverse （ int n） /*递归函数实现逆置*/ if（n=1） nextn=getchar（）; putchar（nextn）;nextn=getchar（）;reverse （n-1）;putchar（nextn）;main（）int i;
