数据结构考试题Word文档下载推荐.docx
- 文档编号:4279325
- 上传时间:2023-05-03
- 格式:DOCX
- 页数:43
- 大小:25.09KB
数据结构考试题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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 考试题