内容发布更新时间 : 2024/10/19 21:20:02星期一 下面是文章的全部内容请认真阅读。

2．设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。

Λ

2．void converse(Linklist &h) { Linknode *p,*q; p=h->next; h->next=NULL; while(p) { q=p->next; p->next=h->next; h->next=p; p=q; } }

p h Λ

Λ h 3．设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表

的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A的元素类型为整型，要求B、C表利用A表的结点）。

3．void decompose(Linklist La,Linklist &Lb,Linklist &Lc) { Linknode *p; Lc=(Linknode *)malloc(sizeof(Linknode)); Lc->next=NULL; p=La->next; Lb=La; Lb->next=NULL; while(p) { La=p->next; if(p->data>0) { p->next=Lc->next; Lc->next=p; } else {

}

}

p->next=Lb->next; Lb->next=p; } p=La;

4. 假设链表A、B分别表示一个集合，试设计算法以判断集合A是否是集合B的子集，若

是，则返回1，否则返回0，并分析算法的时间复杂度。 4．int subset(LinkList la, LinkList lb) { LinkNode * pa,*pb; pa=la->next; while(pa)

{ pb=lb->next;

while(pb&&(pb->data!=pa->data)) pb=pb->next; if(!pb) return 0; pa=pa->next; } return 1;

}算法时间复杂度O（A.Length*B.Length）

5．设有一单循环链表la，其结点有三个域：prior、data与next，其中data为数据域,，next域指向直接后继，prior域应指向直接前驱，但目前空着。试写一算法将此单循环链表改造为双向循环链表。

5．void priorset(DuLinkList &la) { p=la;q=la->next;

while(q!=la){q->prior=p; p=q;q=q->next;} q->prior=p; }

第三章 栈和队列

一、选择题

1．已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（ C）

A.5，4，3，2，1，6 B.2，3，5，6，1，4 C.3，2，5，4，1，6 D.1，4，6，5，2，3

设有一个栈，元素的进栈次序为A, B, C, D, E,下列是不可能的出栈序列（C ） A．A, B, C, D, E B．B, C, D, E, A C．E, A, B, C, D D．E, D, C, B, A

2．在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为（C ） A．top不变 B．top=0 C．top-- D．top++

3．向一个栈顶指针为hs的链栈中插入一个s结点时，应执行（B ） A．hs->next=s;

B．s->next=hs; hs=s;

C．s->next=hs->next;hs->next=s; D．s->next=hs; hs=hs->next; 4．在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为（ D） A．rear％n= = front B．（front+l）％n= = rear C．rear％n -1= = front D．(rear+l)％n= = front 5．在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为（ C）

A．rear％n= = front B．front+l= rear C．rear= = front D．(rear+l)％n= front

6．在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为（ A）

A．front=front->next B．rear=rear->next C．rear=front->next D．front=rear->next

7．某堆栈的输入序列为1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素为（ C）

A．i B．n-i C．n-i+1 D．哪个元素无所谓

8．用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( D )。

A．仅修改队头指针 B. 仅修改队尾指针

C. 队头、队尾指针都要修改 D. 队头,队尾指针都可能要修改

二、解答题

1．一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。 试为此双向栈设计初始化InitStack ( S ) 、入栈Push( S , i , x) 和出栈Pop( S , i )等算法， 其中i为0 或1， 用以表示栈号。

1．双向栈 栈底1 ………. ……… 栈底2

//双向栈类型定义 #define STACK_SIZE 100; Typedef struct {

SElemType * base_one, * base_two;//栈底指针 SElemType * top_one, * top_two;//栈顶指针 int stacksize; } SqStack;

Status InitStack ( SqStack &S) { //初始化双向栈

S.base_one=S.top_one=( SElemType *)malloc(STACK_SIZE * sizeof(SElemType));//第一个栈底和栈顶指向数组起点

S.base_two=S.top_two=S.base_one +STACK_SIZE-1;// 第二个栈底和栈顶指向数组终点 S.stacksize= STACK_SIZE ; return OK; }//InitStack

Status Push ( SqStack &S, int i, SElemType e){

//入栈操作，i=0时将e存入前栈，i=1时将e存入后栈

if( S.top_two < S.top_one) return OVERFLOW;//栈满，不考虑追加空间 if( i = = 0 )

*S.top_one++ = e; else

*S.top_two-- = e; return OK; }//Push

SElemType Pop ( SqStack &S, int i){ //出栈操作，i=0出前栈，i=1出后栈 if( i==0 ) {

if ( S.top_one==S.base_one) return ERROR; S.top_one--; e=*S.top_one; } else {

if ( S.top_two==S.base_two) return ERROR; S.top_two++; e=*S.top_two; } return e; }//Pop

2．利用两个栈S1、S2模拟一个队列时，如何使用栈的运输实现队列的插入、删除运算。

2．#define M 3 struct Stack{ Qelemtype data[M]; int top; };

struct Queue{ Stack s1; Stack s2; };