南京师范大学数据结构考研真题.docx
《南京师范大学数据结构考研真题.docx》由会员分享，可在线阅读，更多相关《南京师范大学数据结构考研真题.docx（20页珍藏版）》请在冰点文库上搜索。
南京师范大学数据结构考研真题
1、给出年、月、日，计算该日是该年的第几天。
（本题15分）
#include
Intget_days_of_month（intyear,intmonth）
{
if（month==1||month==3||month==5||month==7||month==8||month==10||month==12）
return31;
elseif（month==2）
if（year%400==0||（year%4==0&&year%100!
=0））
return29;
else
return28;
else
return30;
}
Voidmain（）
{
inti,year,month,day,sum=0,flag=1;
while（flag）
{
printf（"pleaseinputthedate（forexample:
2005,6,9）:
"）;
scanf（"%d,%d,%d",&year,&month,&day）;
if（year>0）
if（month>=1&&month<=12）
if（day>=1&&day<=get_days_of_month（year,month））
flag=0;
}
for（i=1;i{
sum+=get_days_of_month（year,i）;
}
sum+=day;
printf（"Thedateis%dday.\n",sum）;
}
2、有几个学生，每个学生考m门课，要求编一函数，能检查n个学生有无不及格的课程，如果有某一学生有一门或一门以上课程不及格，就输出该学生的学号（学号从0开始）和其全部课程成绩。
（本题15分）
#include
#defineN100
voidmain（）
{
Inta[N][N];
inti,j,m,n,flag;
printf（"pleaseinputthenumberofstudents:
"）;
scanf（"%d",&n）;
printf（"pleaseinputthenumberofcourses:
"）;
scanf（"%d",&m）;
for（i=0;i{
printf（"pleaseinputNo.%dscores:
",i）;
for（j=0;jscanf（"%d",&a[i][j]）;
}
printf（"studentswhohavefailedtheircoursesasfollows:
"）;
for（i=0;i{
flag=0;
for（j=0;j{
if（a[i][j]<60）
{flag=1;break;}
}
if（flag）
{
printf（"No.%d",i）;
for（j=0;jprintf（"%d",a[i][j]）;
}
printf（"\n"）;
}
}
3、用二分法求方程“（2*X^3）-（4*x^2）+（3*x）-6=0”在（-10,10）之间的根。
（本题20分）
#include
#includefloatgetresult（floatx）
{
return（2*x*x*x-4*x*x+3*x-6）;
}
voidmain（）
{
floatx0,x1,x2,y0,y1,y2;
do{
printf（"pleaseinputx1andx2:
"）;
scanf（"%f,%f",&x1,&x2）;
y1=getresult（x1）;
y2=getresult（x2）;
}while（y1*y2>0）;
do{
x0=（x1+x2）/2;
y0=getresult（x0）;
if（y0*y1>0）
x1=x0;
elsex2=x0;
}while（fabs（y0）>1e-5）;
printf（"Therootis%f.\n",x0）;
}
4、请写出判断“点是否在简单多边形内部”的算法。
（本题20分）
解题思路：
如果一个点在一个多边形内，那么从该点向上、向下、向左、向右都应与简单
多边有交点,点在某一条边上算在多边形内。
#include
#defineN10typedefstructNode
{
floatx;
floaty;
}XYNode,Nodes[N+1];
voidmain（）
{
inti,up=0,down=0,left=0,right=0;
intx0,x1,x2,y0,y1,y2;
charflag='Y';
XYNodepoint;
Nodesa;
for（i=0;i{
printf（"pleaseinputthe%dstcoordinate:
",i+1）;
scanf（"%f,%f",&a[i].x,&a[i].y）;
}
a[N].x=a[0].x;//使起点和终点的坐标相同
a[N].y=a[0].y;
while（flag!
='n'&&flag!
='N'）
{
printf（"Now,pleaseinputthePoint'scoordinate:
"）;
scanf（"%f,%f",&point.x,&point.y）;
for（i=0;i{
if（（a[i].x>point.x&&a[i+1].x<=point.x）||（a[i].x=point.x））
{
x1=a[i].x;
y1=a[i].y;
x2=a[i+1].x;
y2=a[i+1].y;
x0=point.x;
y0=（y1-y2）*（x0-x1）/（x1-x2）+y1;
if（y0==point.y）
{
up=1;down=1;left=1;right=1;
break;
}
elseif（y0>point.y）
up=1;
elsedown=1;
}//if
if（（a[i].y>point.y&&a[i+1].y<=point.y）||（a[i].y=point.y））
{
x1=a[i].x;
y1=a[i].y;
x2=a[i+1].x;
y2=a[i+1].y;
y0=point.y;
x0=（x1-x2）*（y0-y1）/（y1-y2）+x1;
if（x0==point.x）
{
up=1;down=1;left=1;right=1;
break;
}
elseif（x0>point.y）
right=1;
elseleft=1;
}//if
}//for
if（up&&down&&left&&right）
printf（"Yes,thepointisinthepolygon.\n"）;
elseprintf（"No,thepointisnotinthepolygon.\n"）;
while（getchar（）!
='\n'）;//接收多余的字符
printf（"wouldyouliketogoon?
"）;
flag=getchar（）;//flag只接收第一个字符
while（getchar（）!
='\n'）;//接收多余的字符
}//while
}
5、从平均时间、最坏情况，辅助存储和稳定性的角度，对各种内部排序方法进行比较。
（建议用表格方式进行比较，本题20分）
严蔚敏数据结构289页
6、定义一个双向循环链表，并写出其定位、插入和删除算法。
（本题20分）
#include
#include
#defineOK1
#defineERROR0
typedefintStatus;
typedefintElemType;
typedefstructDuLNode
{
ElemTypedata;
structDuLNode*prior;
structDuLNode*next;
}DuLNode,*DuLinkList;
StatusGetElem_DuL（DuLinkListL,inti,ElemType*e）
{
intj=1;
DuLNode*p;
p=L->next;
while（p!
=L&&j{
p=p->next;
j++;
}
if（p==L||j!
=i）
returnERROR;
*e=p->data;
returnOK;
}
StatusListInsert_DuL（DuLinkList&L,inti,ElemTypee）
{//在带头结点的双链循环链表L中第i个位置之前插入元素e
//i的合法位置为1<=i<=表长+1
intj;
DuLNode*p,*s;
if（i<1）//如果i的值小于1，则返回错误
returnERROR;
j=1;
p=L->next;
while（p!
=L&&j{
p=p->next;
j++;
}
if（jreturnERROR;
if（!
（s=（DuLNode*）malloc（sizeof（DuLNode））））
returnERROR;
s->data=e;
s->prior=p->prior;
p->prior->next=s;
s->next=p;
p->prior=s;
returnOK;
}
StatusListDelete_DuL（DuLinkList&L,inti,ElemType*e）
{//删除带头结点的双链循环线性表L的第i个元素，i的合法位置为1<=i<=表长
intj;
DuLNode*p;
if（i<1）
returnERROR;
j=1;
p=L->next;
while（p!
=L&&j{
p=p->next;
j++;
}
if（p==L）
returnERROR;
*e=p->data;
p->prior->next=p->next;
p->next->prior=p->prior;
free（p）;
returnOK;
}
voidprint（DuLinkListL）
{
DuLNode*p;
p=L->next;
while（p!
=L）
{
printf（"%d",p->data）;
p=p->next;
}
printf（"\n"）;
}
voidmain（）
{
inti;
ElemTypee;
DuLinkListL;
if（!
（L=（DuLNode*）malloc（sizeof（DuLNode））））
exit（0）;
L->next=L;
L->prior=L;
for（i=1;i<10;i++）
{
e=（ElemType）i;
if（!
（ListInsert_DuL（L,i,e）））
printf（"No.%diswrong!
\n",i）;
}
print（L）;
ListInsert_DuL（L,5,（ElemType）10）;
print（L）;
ListDelete_DuL（L,1,&e）;
print（L）;
printf（"pleaseinputanumber:
"）;
scanf（"%d",&i）;
if（GetElem_DuL（L,i,&e））
printf（"L[%d]=%d\n",i,e）;
elseprintf（"%disillegal!
\n",i）;
}
7、编制一个程序以模拟银行窗口接待客户的排队业务活动（每个窗口在某个时刻只能接待一个客户；窗口空闲，则可上前办理业务；窗口均被占，则新客户便会排在人数最少的队伍前面），并计算一天中客户在银行逗留的平均时间。
（本题20分）
#include
#include
#include
#defineMAX10000
#defineOK1
#defineERROR0/**********数据类型定义（Start）**********/
typedefintStatus;
typedefstruct{
intOccurTime;//事件发生时刻
intNType;//事件类型，0~5
}Event,ElemType;//事件类型，有序链表LinkList的数据元素类型
typedefstructLNode
{
ElemTypedata;
structLNode*next;
}LNode,*LinkList;
typedefLinkListEventList;//事件链表类型，定义为有序链表
typedefstruct{
intArrivalTime;//到达时间
intDuration;//办理事务所需时间
}QElemType;//队列的数据元素类型
typedefstructQNode
{
QElemTypedata;
structQNode*next;
}QNode,*QueuePtr;
typedefstruct{
QueuePtrfront;
QueuePtrrear;
}LinkQueue;
/**********数据类型定义（Over）**********/
/**********程序中用到的主要变量（Start）**********/
EventListev;//事件表
Eventen;//事件
LinkQueueq[5];//4个客户队列
QElemTypecustomer;//客户记录
longTotalTime,CustomerNum;//累计客户逗留时间，客户数
/**********程序中用到的主要变量（Over）**********/
/**********自定义函数部分（Start）**********/
/****链表操作部分（start）****/
intcmp（ElemTypea,ElemTypeb）
{
if（a.OccurTime>b.OccurTime）
return1;
elseif（a.OccurTime==b.OccurTime）
return0;
else
return-1;
}
voidInitList（LinkList&L）
{
L=（LNode*）malloc（sizeof（LNode））;
if（!
L）
printf（"EVENTLISTINITERROR!
\n"）;
else{
L->next=NULL;
}
}
voidOrderInsert（LinkListL,ElemTypeen）
{
LNode*p,*q,*s;
p=L;
q=p->next;
while（q&&（cmp（q->data,en）==-1））
{
p=q;
q=p->next;
}
s=（LNode*）malloc（sizeof（LNode））;
s->data.OccurTime=en.OccurTime;
s->data.NType=en.NType;
p->next=s;
s->next=q;
}
intListEmpty（LinkListL）
{
if（L->next!
=NULL）
return0;
else
return1;
}
voidDelFirst（LinkListL,ElemType*e）
{
LNode*p;
p=L->next;
L->next=p->next;
e->OccurTime=p->data.OccurTime;
e->NType=p->data.NType;
free（p）;
}
/****链表操作部分（over）****/
/****队列操作部分（start）****/
voidInitQueue（LinkQueue*Q）
{
Q->front=Q->rear=（QNode*）malloc（sizeof（QNode））;
if（!
（Q->front））
printf（"LinkQueueINITERROR!
\n"）;
Q->front->next=NULL;
}
StatusDelQueue（LinkQueue*Q,QElemType*e）
{
QNode*p;
if（Q->front==Q->rear）returnERROR;
p=Q->front->next;
e->ArrivalTime=p->data.ArrivalTime;
e->Duration=p->data.Duration;
Q->front->next=p->next;
if（Q->rear==p）Q->rear=Q->front;
free（p）;
returnOK;
}
StatusEnQueue（LinkQueue*Q,QElemTypee）
{
QNode*p;
p=（QNode*）malloc（sizeof（QNode））;
if（!
p）exit（0）;
p->data.ArrivalTime=e.ArrivalTime;
p->data.Duration=e.Duration;
p->next=NULL;
Q->rear->next=p;
Q->rear=p;
returnOK;
}
intQueueLength（LinkQueue*Q）
{
inti=0;
QNode*p;
if（Q->front==Q->rear）i=0;
else{
p=Q->front;
while（p!
=Q->rear）
{
p=p->next;
i++;
}
}
returni;
}
/****队列操作部分（over）****/
/****业务操作部分（start）****/
voidRandom（long*durtime,long*intertime）
{
srand（time（NULL））;
*durtime=rand（）;
*intertime=rand（）;
}
intMinimum（LinkQueueq[]）
{
inti,j,k=0,min=MAX;
QNode*p;
for（i=1;i<=4;i++）
{
if（q[i].front==q[i].rear）
j=0;
else{
p=q[i].front->next;
j=1;
while（p!
=q[i].rear）
{
p=p->next;
j++;
}
}
if（min>j）
{
min=j;
k=i;
}
}
returnk;
}
voidOpenForDay（）
{
inti;
TotalTime=0;CustomerNum=0;
InitList（ev）;
en.OccurTime=0;en.NType=0;
OrderInsert（ev,en）;
for（i=1;i<=4;i++）
InitQueue（&q[i]）;
}
voidCustomerArrived（intCloseTime）
{
longdurtime,intertime,i,t;
++CustomerNum;
Random（&durtime,&intertime）;
printf（"durtime=%ld,intertime=%ld\n",durtime,intertime）;
t=en.OccurTime+intertime;
i=Minimum（q）;
customer.ArrivalTime=en.OccurTime;
customer.Duration=durtime;
EnQueue（&q[i],customer）;
if（QueueLength（&q[i]）==1）
{
en.OccurTime=en.OccurTime+durtime;
en.NType=i;
OrderInsert（ev,en）;
}
if（t{
en.OccurTime=t;
en.NType=0;
OrderInsert（ev,en）;
}
}
voidCustomerDeparture（）
{
inti;
i=en.NType;DelQueue（&q[i],&customer）;
TotalTime+=en.OccurTime-customer.ArrivalTime;
if（QueueLength（&q[i]））
{
QNode*p=q[i].front->next;
QElemTypeqe=p->data;
customer.ArrivalTime=qe.ArrivalTime;
customer.Duration=qe.Duration;
en.OccurTime=en.OccurTime+customer.Duration;
en.NType=i;
OrderInsert（ev,en）;
}
}
voidBank_Simulation（intCloseTime）
{
inti=0;
OpenForDay（）;
while（!
ListEmpty（ev））
{
DelFirst（ev,&en）;
i=en.NType;
if（i==0）
CustomerArrived（Cl
升级会员 