中第一个结点(又称首元)，当进行查找运算时，必须从头指针开始去顺次访问表中每一个元素。
头结点是另设一个结点，其指针域指向存放表中第一个元素的结点，设置头结点的好处是：无需对在第一个结点前插入一个结点或删除一个结点时进行特殊处理，也可以对空表和非空表的运算进行统一处理。
四、算法设计题
1． 先判断表满否，若表未满，则从最后一个元素an开始，逐个与x进行比较，若ai>x(1≤i≤n)，则将ai后移一个位置，直到ai≤x，最后把x插入到这个位置，表长+1。算法描述如下：
#define M 100
int insort(Slist *L，int z) {int i；
if(L->n>=M)
{printf(“overflow\； return 0；} else
for(i=L->n;i>=0;i--) if(L->data[i]>x
L->data[i+1]=L->data[i]; else break； L->data[i+1]=x； L->n++； return 1； }
2．逐个查找单链表中的结点x，并计数。 int number(lnode *h,int x) { int n=0； while(h)
{if(h->data==x) n++；
h=h->next； }
return s； }
3．前插法建立带表头结点的单链表算法中的tag为输人数据结束标志。 Lnode *createhh(int tag) { int x；
Lnode *p，*h=(Lnode *)malloc(sizeof(Lnode))； h->next=NULL；
printf(“input x:”)； scanf(“%d”,&x); while(x!=tag)
{p=(Lnode*)malloc(sizeof(Lnode)); p->data=x;
p->next=h->next; h->next=p;
scanf(“%d”,&x); }
return h; }
4.先建立一个表头结点，用尾插法建立该单链表。然后将尾结点的指针域值置为表中第一个结点的首地址，最后释放表头结点。算法描述如下：
Lnode *createht(int tag) { int x；
21
Lnode *p，*r,*h=(Lnode *)malloc(sizeof(Lnode))； r=h;
printf(“input x:”)； scanf(“%d”,&x); while(x!=tag)
{p=(Lnode*)malloc(sizeof(Lnode)); p->data=x; r->next=p; r=p;
scanf(“%d”,&x); }
r->next=h->next; free(h); return r; }
5．设p指向待逆置链表中的第一个结点，先将表头结点的链域置空。顺次取出待逆置链表中的第一个结点，用前插法插入到带表头结点的单链表中。
Void reverseh(Lnode *h) { Lnode *s,*p=h->next; h->next=NULL; while(p)
{s=p;p=p->next; s->next=h->next; h->next=s; } }
6.逐个检测顺序表中其值在x和y之间的元素，并计数k,再将其值大于y的元素向前移动k个元素。算法描述如下：
void deletexy(Slist *a,int x,int y) { int i,k=0;
for(i=0;i
if(a->data[i]>=x&&a->data[i]<=y) k++; else
a->data[i-k]=a->data[i]; a->n=a->n-k;} 第三章
一、单项选择题
(1)-(5) CACCB (6)-(7)BC 二、填空题
(1)栈顶 (2)栈底 (3)队尾 (4)队首 (5)O(n) (6)O(1) (7)O(1)
(8)O(1) (9)front=rear (10)(rear+1)％m=front (11)(rear-front+m)％m (12) 向是的两端 三、应用题
1．栈和队列是操作位置受限的线性表，即对插入和删除运算的位置加以限制。栈是仅允许在表的一端进行插入和删除运算的线性表，因而是后进先出表。而队列是只允许在表的一端插入，另一端进行删除运算的线性表，因而是先进先出表。 2．循环队列的优点是解决了“假上溢”问题。
设用数组A[m]来存放循环队列，设front指向实际队首，rear指向新元素应插入的位置时，front=rear即可能是队空，又可能是队满，为了区分队空和队满可采用下列三种方案：
(1)用“少用一个元素空间”的方案，初态fron=rear=0，判断队空的条件是fron=rear，判断队满的条件是(reaf+1)％m=front。
(2)用“设队空标志”的方法，如设front=-1时为队空标志，初态是front=-1，rear=0。当
22
front=rear时则队满。
(3)用count存放表中元素个数，当count=0时为队空，当count=m时为队满。 3．若进栈序列为a，b，c，d，全部可能的出栈序列是：
abcd，abdc，acbd，acdb，adcb，bacd，badc，bcad，bcda，bdca，cbad， cbda，cdba，dcba，
不可能的出栈序列为：adbc，bdac，cdab，cadb，cadb，dabc，dacb， dbac，dbca，dcab。
4．由于队列中操作遵循的原则是先进先出，出队元素的顺序是bdcfea，故元素进队的顺序也是bdcfea，元素进队的顺序与元素出栈的顺序相同，在栈中存取数据遵循的原则是后进先出，要得到出栈序列bdcfea，栈的容量至少是应该存放3个元素的空间。
5. 3 4 25 6 15+-/8*+ 四、算法设计题
1．解本题的基本思想是：先将顺序队列q中所有元素出队，并依次进入顺序栈s中，然后出栈，再依次入队。设队列中的元素为a1,a2,…,an，出队并进栈的序列为a1，a2，…，an，出栈并入队的序列为an，an-1，…，a1，可见顺序队列q中所有元素已逆置了。顺序队列的类型定义为：
#define MAX 100 typedef struct {int data[MAX]；
int front,rear；
}Squeue；
算法描述如下：
void invert(Squeue *q) {int s[MAX],top=0;
while(q->front
s[top++]=q->data[++q->front]; q->front=-1;q->rear=0; while(top>0)
q->data[q->rear++]=s[--top]; } 2.
(1)递归算法： int f1(int n) { int f;
if(n==0) return (1); else
return(n*f1(n/2)); }
(2)将上述递归函数转换成非递归函数时，使用了一个栈，用于存储调用参数和函数值，这里采用一维数组s[n]作为栈，用一个栈顶指针top。算法如下：
#define maxlen 200; int f2(int n) { int s[maxlen]; int top=0,fval=1; while(n!=0) {s[top]=n; n=n/2; top++; }
while(top>=0)
{fval=fval*s[top]; top--; }
return fval;
23
}
3.仅设队尾指针的带表头结点的循环链表,找队首结点为rear->next->next。 (1)初始化
Lnode *int queue() {Lnode *rear;
rear=(Lnode*)malloc(sizeof(Lnode)); rear->next=rear; return rear; }
(2)入队算法
Lnode *enqueue(Lnode *rear,int x)
{ Lnode *p=(Lnode*)malloc(sizeof(Lnode)); p->data=x;
p->next=rear->next; rear->next=p; return p; }
(3)出队算法
int outqueue(Lnode *rear,int *x) { Londe *p;
if(rear->next=rear)
{printf(“queue is empty”); return 0; }
p=rear->next->next; *x=p->data;
rear->next->next=p->next; free(p); return 1; }
第四章
一、单项选择题
(1)一(5)DBDBD (6)-(10)BDBBA (11)-(13)CAA 二、填空题
(1)两个串的长度相等且对应位置上的字符相同。 (2)是由零个字符组成的串 (3)0
(4)”goodmorning” (5)”nin” (6)4 (7)”goto” (8)m (9)m(n-m+1) (10)Loc(a[0][0])=1000-88=912
(11)n(n+1)/2+1 (12) n(n+1)/2 (13)i(i-1)/2+j-1
(14)(2n-j+2)(j-1)/2+i-j (15)3 (16)4 (17)a(18)((b),((c,(d)))) (19)三元组表 （20）十字链表 （21）子表 (22)子表 三、应用题
1．用联接、取子串、置换运算将串S=”(xyz)+*”转化为T=”(x+z)*y”。 C1=substr(S,3,1)=”y” C2=substr(S,6,1)=”+” C3=substr(S,7,1)=”*” C4=concat(C3,c11)=”*y”
T=replace(S,3,1,C2)=replace(S,3,1,substr(S,6,1))=”(x+z)+x”
T=replace(T,6,2,concat(C3,C1))=replace(T,6,2,concat(substr(S,7,1)),substr(S,3,1)))=”(x+z)*y”。
若只用取子串和联接操作进行的转换过程是：
C1=concat(substr(S,1,2),substr(S,6,1))=”(x+” C2=concat(substr(S,7,1),substr(S,3,1))=”*y”
T=concat(concat(concat(substr(S,1,2),substr(S,6,1)),substr(S,4,2)),concat(substr(S,
24