数据结构考试题Word文档下载推荐.docx
《数据结构考试题Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《数据结构考试题Word文档下载推荐.docx（43页珍藏版）》请在冰点文库上搜索。
{
C.data[k]=A->
data[i];
k++;
}
C.length=k;
returnC;
seqlistdelet（seqlist*A,seqlist*B）
inti,j,k;
for（k=i;
k<
length-1;
k++）
A->
data[k]=A->
data[k+1];
A->
length--;
return*A;
voiddsip（seqlist*L）
printf（"
%d"
L->
intmain（）
seqlistA,B,C;
createlist（&
A）;
B）;
C）;
before:
dsip（&
C=same（&
B,&
A=delet（&
A,&
after:
2、已知线性表A,B,C是递增有序的线性表。
线性表A中出现的元素，在线性表B中也出现，则将A中该元素删除。
A，B以顺序表存储。
seqlistA,B;
删除后：
"
3、顺序表A和顺序表B的元素都是非递减排列，利用线性表的基本运算，将它们合并成一个顺序表C，要求C也是非递减排列。
A，B表的值可以自行设计。
#include<
#defineListSize100
#defineOVERFLOW-1
#defineERROR0
#defineOK1
#defineDataTypeint
typedefintstatus;
DataType*list;
intlistSize;
intlength;
}SeqList;
intInitList（SeqList*L）
（*L）.list=（DataType*）malloc（ListSize*sizeof（DataType））;
if（!
（*L）.list）
exit（OVERFLOW）;
（*L）.length=0;
（*L）.listSize=ListSize;
returnOK;
//线性表的初始化
voidmergelist（SeqListla,SeqListlb,SeqListlc）
int*pa,*pb,*pc,*pa_last,*pb_last;
pa=la.list;
pb=lb.list;
lc.listSize=la.length+lb.length;
pc=lc.list=（DataType*）malloc（lc.listSize*sizeof（DataType））;
if（!
lc.list）
exit（0）;
pa_last=la.list+la.length-1;
pb_last=lb.list+lb.length-1;
while（pa<
=pa_last&
&
pb<
=pb_last）
{
if（*pa<
=*pb）
*pc++=*pa++;
else*pc++=*pb++;
}
=pa_last）
*pc++=*pa++;
while（pb<
*pc++=*pb++;
lc.listSize;
lc.list[i]）;
SeqListla,lb,lc;
la.length=0;
lb.length=0;
if（InitList（&
la））
输入顺序表la:
5;
{
scanf（"
la.list[i]）;
la.length++;
}
lb））
输入顺序表lb:
{
lb.list[i]）;
lb.length++;
mergelist（la,lb,lc）;
4、已知线性表La和Lb的元素按值非递减排列。
归并La和Lb得到新的线性表Lc，Lc的元素也按值非递减排列。
采用链式结构来实现。
La、Lb表的值可以自行设计。
typedefintElemType;
//定义ElemType为整型
typedefstructLNode
{
ElemTypedata;
structLNode*next;
}LNode,*LinkList;
voidCreateList（LinkList&
L,intn）
{//正位序（结点插在表尾）输入n个元素的值，建立带表头结点的单链线性表L
LinkListp,q;
L=（LinkList）malloc（sizeof（LNode））;
//生成头结点
L->
next=NULL;
//先建立一个带头结点的空单链表
q=L;
//q指向空表的头结点（相当于尾结点）
请输入%d个数据\n"
n）;
for（i=1;
=n;
i++）
{
p=（LinkList）malloc（sizeof（LNode））;
//生成新结点
p->
data）;
//给新结点输入元素值
q->
next=p;
//将新结点插在表尾
q=q->
next;
//q指向尾结点
}
p->
//最后一个结点的指针域为空
}
voidMergeList（LinkListLa,LinkList&
Lb,LinkList&
Lc）//算法2.12
{//已知单链线性表La和Lb的元素按值非递减排列。
//归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。
（销毁Lb，Lc即新的La）
LinkListpa=La->
next,pb=Lb->
next,pc;
//pa、pb分别指向La、Lb的首元结点（待比较结点）
Lc=pc=La;
//用La的头结点作为Lc的头结点，pc指向La的头结点（Lc的尾结点）
while（pa&
pb）//La和Lb中的元素都未比较完
if（pa->
data<
=pb->
data）//La的当前元素不大于Lb的当前元素
pc->
next=pa;
//将pa所指结点归并到Lc中
pc=pa;
//pc指向表Lc的最后一个结点
pa=pa->
//表La的下一个结点成为待比较结点
else//Lb的当前元素小于La的当前元素
next=pb;
//pb所指结点归并到Lc中
pc=pb;
pb=pb->
//表Lb的下一个结点成为待比较结点
next=pa?
pa:
pb;
//插入剩余段
free（Lb）;
//释放Lb的头结点
Lb=NULL;
//Lb不再指向任何结点
voidPrintf_L（LinkList&
L）
LNode*p;
p=L->
while（p!
=NULL）
p->
p=p->
voidmain（）
intn=5;
LinkListLa,Lb,Lc;
按非递减顺序，"
CreateList（La,n）;
//根据输入顺序，正位序建立线性表
CreateList（Lb,n）;
//根据输入顺序，逆位序建立线性表
La="
Printf_L（La）;
//输出链表La的内容
Lb="
Printf_L（Lb）;
//输出链表Lb的内容
MergeList（La,Lb,Lc）;
//按非递减顺序归并La和Lb，得到新表Lc
Lc="
Printf_L（Lc）;
//输出链表Lc的内容
6、编写一个程序，实现双链表的各种基本运算（双链表的元素类型为char），并在此基础上设计一个程序，完成如下功能：
（1）初始化双链表h；
（2）采用尾插法依次插入元素a，b，c，d，e；
（3）删除h的第3个元素；
#include"
stdio.h"
malloc.h"
typedefcharElemType;
typedefstructDNode//定义双链表结点类型
structDNode*prior;
//指向前驱结点
structDNode*next;
//指向后继结点
}DLinkList;
/*初始化双链表*/
voidInitList（DLinkList*&
L）
L=（DLinkList*）malloc（sizeof（DLinkList））;
prior=L->
/*向双链表L的第i个位置插入数据e*/
intListInsert（DLinkList*&
L,inti,ElemTypee）
intj=0;
DLinkList*p=L,*s;
while（j<
i-1&
p!
=NULL）
j++;
if（p==NULL）
return0;
else
s=（DLinkList*）malloc（sizeof（DLinkList））;
s->
data=e;
next=p->
if（p->
next!
p->
next->
prior=s;
prior=p;
p->
next=s;
return1;
/*释放双链表*/
voidDestroyList（DLinkList*&
L）
DLinkList*p=L,*q=p->
while（q!
free（p）;
p=q;
q=q->
free（p）;
/*从双链表L的第i个位置删除数据e*/
intListDelete（DLinkList*&
L,inti,ElemType&
e）
DLinkList*p=L,*q;
q=p->
if（q==NULL）
return0;
e=q->
data;
next=q->
free（q）;
/*打印双链表*/
voidDispList（DLinkList*L）
DLinkList*p=L->
%c"
p=p->
voidmain（）
DLinkList*h;
ElemTypee;
双链表的基本运算如下:
（1）初始化双链表h\n"
InitList（h）;
（2）依次采用尾插法插入a,b,c,d,e元素\n"
ListInsert（h,1,'
a'
ListInsert（h,2,'
b'
ListInsert（h,3,'
c'
ListInsert（h,4,'
d'
ListInsert（h,5,'
e'
（3）输出双链表h:
DispList（h）;
（4）删除h的第3个元素\n"
ListDelete（h,3,e）;
（5）输出双链表h:
（6）释放双链表h\n"
DestroyList（h）;
7、利用堆栈实现进制转换，如10进制到8进制的转换（1348）10=（2504）8
malloc.h>
#defineSTACK_INIT_SIZE100//存储空间的初始分配量
#defineSTACKINCREMENT10//存储空间分配增量
structSqStack
int*base;
int*top;
intstacksize;
//当前已分配的存储空间
};
/*构造一个空栈*/
voidInitStack（structSqStack*S）
S->
base=（int*）malloc（STACK_INIT_SIZE*sizeof（int））;
（S->
base））//存储分配失败
exit（0）;
内存分配错误!
top=S->
base;
stacksize=STACKINCREMENT;
/*入栈*/
voidPush（structSqStack*S,inte）
if（S->
top-S->
base>
=S->
stacksize）//栈满溢出
base=（int*）realloc（S->
base,（STACKINCREMENT+STACK_INIT_SIZE）*sizeof（int））;
//重新分配存储空间
base））
存储失败\n"
base+S->
stacksize;
stacksize=S->
stacksize+STACKINCREMENT;
*（S->
top++）=e;
/*出栈*/
intPop（structSqStack*S,inte）
top==S->
base）//空栈
此栈为空栈\n"
e=*（--S->
top）;
return（e）;
/*判断栈是否为空*/
intStackEmpty（structSqStack*S）
base）
return1;
/*主函数*/
intmain（intargc,char*argv[]）
intn=0;
inte=1;
structSqStack*Change;
Change=（structSqStack*）malloc（sizeof（structSqStack））;
InitStack（Change）;
PleaseinputthePrimitivenum（十进制数）:
n）;
while（n）
Push（Change,n%8）;
n=n/8;
Theresultis（八进制数）:
while（!
StackEmpty（Change））
e=Pop（Change,e）;
e）;
if（e/8==0）
此栈已经为空了\n"
system（"
PAUSE"
8、实现链栈的基本操作，然后利用堆栈将一个线性表中的元素按逆序重新存放。
例如原来的顺序为12，8，6，4，2，要求改为2，4，6，8，12。
#defineSTACK_INIT_SIZE10/*存储空间初始分配量*/
#defineSTACKINCREMENT2/*存储空间分配增量*/
typedefintStatus;
typedefintSElemType;
typedefintDataType;
DataTypelist[ListSize];
/*顺序表*/
typedefstructSqStack
SElemType*base;
/*在栈构造之前和销毁之后，base的值为NULL*/
SElemType*top;
/*栈顶指针*/
/*当前已分配的存储空间，以元素为单位*/
}SqStack;
/*顺序栈*/
/*初始化顺序表*/
SeqListInitList（）
DataTypevalue[]={12,8,6,4,2};
SeqListL;
L.length=0;
L.list[i]=value[i];
L.length++;
returnL;
/*顺序表输出函数*/
voiddisplayList（SeqList*sq）
intindex;
if（sq->
length==0）return;
for（index=0;
index<
sq->
index++）
%4d"
sq->
list[index]）;
printf
升级会员 