南京师范大学考研C语言程序设计含数据结构历年真题试题.docx
《南京师范大学考研C语言程序设计含数据结构历年真题试题.docx》由会员分享，可在线阅读，更多相关《南京师范大学考研C语言程序设计含数据结构历年真题试题.docx（94页珍藏版）》请在冰点文库上搜索。
南京师范大学考研C语言程序设计含数据结构历年真题试题
南京师范大学考研C语言程序设计试题
历年真题（2003-2011）
2011年南京师范大学考研C语言程序设计（含数据结构）真题
1、编写一个程序，求用户输入的开始时间到终止时间之间相距的天数。
（本题15分）
2、编写一个程序，利用递归法实现将用户输入的字符串逆序排列。
（本题15分）
3、找出所有200以内（含200）满足I，I+4，I+10都是素数的整数I（I+10也在200以内）的个数以及这些数之和sum。
并把所有这些数、个数和sum按文本文件输出到文件out.dat中。
（本题20分）
4、编写程序，判断两线段是否相交。
（本题20分）
5、假设以带头节点的循环链表表示队列，并只设一个指针指向对尾元素节点（不设头指针），编写相应的队列初始化、入队列和出队列算法。
（本题20分）
6、假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将表A和表B归并成一个按元素值非递减有序（允许值相同）排列的线性表C，并要求利用原表（即表A和表B）的结点空间存放表。
（本题20分）
7、给定一棵树用二叉链表表示的二叉树，其中的指针t指向根结点，试写出从根开始，按层次遍历二叉树的算法，周层的结点按从左到右的次序访问。
（本题20分）
8、若S是n个元素的集合，则S的幂集P（S）定义为S的所有子集的集合。
例如，S=（a,b,c）,P（S）={（）,（a）,（b）,（c）,（a,b）,（a,c）,（b,c）,（a,b,c）}。
给定S，写一递归算法求P（S）。
（本题20分）
1、解题思路：
假如计算2005年5月20日至2008年9月12日之间经过的天数，则以2005年1月1日为起点，分别计算2005年5月20日和2008年9月12日至2005年1月1日的天数，两者天数相减，则可以求出两者相距的天数。
2、解题思路：
假如一个字符串有n个字符，用递归方法进行第1与第n字符交换、第2与第n-1个字符交换...直到字符串的中间位置。
3、解题思路：
将符合条件的所有元素I存入一个数组中，并记录个数，再求和
4、解题思路：
如果两条线段平行，则两条线段定不相交；如果不平行，则求两线段所在的直线的交点，再判断该交点是否在线段上，如果在线段上，则表示两线段相交，如果不在线段上，则表示两线段不相交。
5、参照严蔚敏的数据结构（C语言版）课本64页循环队列-队列的顺序存储结构
6、参照严蔚敏的数据结构（C语言版）课本31页算法2.12
7、参照严蔚敏的数据结构（C语言版）课本170页算法7.6
8、对照严蔚敏的数据结构（C语言版）课本149页例6-3
2010年南京师范大学考研C语言程序设计（含数据结构）真题
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
#include
floatgetresult（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;
else
x2=x0;
}while（fabs（y0）>1e-5）;
printf（"Therootis%f.\n",x0）;
}
4、请写出判断“点是否在简单多边形内部”的算法。
（本题20分）
//相对正确的解题思路：
从该点向某一个方向做一条射线，如果与多边形相交的点是奇数个，则在多边形内；否则，可能在多边形内。
//不太正确的解题思路：
如果一个点在一个多边形内，那么从该点向上、向下、向左、向右都应与简单
//多边有交点,点在某一条边上算在多边形内（下面的程序代码也有问题）。
#include
#defineN10
typedefstructNode
{
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;
else
down=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;
else
left=1;
}//if
}//for
if（up&&down&&left&&right）
printf（"Yes,thepointisinthepolygon.\n"）;
else
printf（"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）;
else
printf（"%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
升级会员 