南京师范大学考研C语言程序设计含数据结构历年真题试题.docx

1、南京师范大学考研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、假设以带头节点

2、的循环链表表示队列，并只设一个指针指向对尾元素节点（不设头指针），编写相应的队列初始化、入队列和出队列算法。（本题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

3、),(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、解题思路：如果两条线段平行，则两条线段定不相交；如果不平

4、行，则求两线段所在的直线的交点，再判断该交点是否在线段上，如果在线段上，则表示两线段相交，如果不在线段上，则表示两线段不相交。5、参照严蔚敏的数据结构（C语言版）课本64页 循环队列-队列的顺序存储结构6、参照严蔚敏的数据结构（C语言版）课本31页 算法2.127、参照严蔚敏的数据结构（C语言版）课本170页 算法7.68、对照严蔚敏的数据结构（C语言版）课本149页 例6-32010年南京师范大学考研C语言程序设计（含数据结构）真题1、给出年、月、日，计算该日是该年的第几天。（本题15分）参考解法：#includeint get_days_of_month(int year,int mont

5、h) if(month=1|month=3|month=5|month=7|month=8|month=10|month=12) return 31; else if(month=2) if(year%400=0 | (year%4=0 & year%100!=0) return 29; else return 28; else return 30;void main() int i,year,month,day,sum=0,flag=1; while(flag) printf(please input the date(for example:2005,6,9):); scanf(%d,%d

6、,%d,&year,&month,&day); if(year0) if(month=1 & month=1 & day=get_days_of_month(year,month) flag = 0; for(i=1;imonth;i+) sum +=get_days_of_month(year,i); sum += day; printf(The date is %d day.n,sum);2、有几个学生，每个学生考m门课，要求编一函数，能检查n个学生有无不及格的课程，如果有某一学生有一门或一门以上课程不及格，就输出该学生的学号（学号从0开始）和其全部课程成绩。（本题15分）参考解法：#in

7、clude#define N 100void main() int aNN; int i,j,m,n,flag; printf(please input the number of students:); scanf(%d,&n); printf(please input the number of courses:); scanf(%d,&m); for(i=0;in;i+) printf(please input No.%d scores:,i); for(j=0;jm;j+) scanf(%d,&aij); printf(students who have failed their co

8、urses as follows:); for(i=0;in;i+) flag = 0; for(j=0;jm;j+) if(aij60) flag=1;break; if(flag) printf(No.%d ,i); for(j=0;jm;j+) printf(%d ,aij); printf(n); 3、用二分法求方程“(2*X3)-(4*x2)+(3*x)-6 = 0”在(-10,10)之间的根。（本题20分）#include#includefloat getresult(float x) return (2*x*x*x - 4*x*x + 3*x -6);void main() fl

9、oat x0,x1,x2,y0,y1,y2; do printf(please input x1 and x2:); scanf(%f,%f,&x1,&x2); y1 = getresult(x1); y2 = getresult(x2); while(y1*y20); do x0 = (x1+x2)/2; y0 = getresult(x0); if(y0*y10) x1 = x0; else x2 = x0; while(fabs(y0)1e-5); printf(The root is %f.n,x0);4、请写出判断“点是否在简单多边形内部”的算法。（本题20分）/相对正确的解题思路：

10、从该点向某一个方向做一条射线，如果与多边形相交的点是奇数个，则在多边形内；否则，可能在多边形内。/不太正确的解题思路：如果一个点在一个多边形内，那么从该点向上、向下、向左、向右都应与简单/多边有交点,点在某一条边上算在多边形内（下面的程序代码也有问题）。#include#define N 10typedef struct Node float x; float y;XYNode,NodesN+1;void main() int i,up=0,down=0,left=0,right=0; int x0,x1,x2,y0,y1,y2; char flag = Y; XYNode point; No

11、des a; for(i=0;iN;i+) printf(please input the %dst coordinate:,i+1); scanf(%f,%f,&ai.x,&ai.y); aN.x = a0.x; /使起点和终点的坐标相同 aN.y = a0.y; while(flag!=n & flag !=N) printf(Now, please input the Points coordinate:); scanf(%f,%f,&point.x,&point.y); for(i=0;ipoint.x & ai+1.x=point.x)|(ai.x=point.x) x1 = ai.

12、x; y1 = ai.y; x2 = ai+1.x; y2 = ai+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; else if(y0point.y) up = 1; else down = 1; /if if(ai.ypoint.y & ai+1.y=point.y)|(ai.y=point.y) x1 = ai.x; y1 = ai.y; x2 = ai+1.x; y2 = ai+1.y; y0 = poin

13、t.y; x0 = (x1-x2)*(y0-y1)/(y1-y2) + x1; if(x0=point.x) up =1; down = 1; left = 1; right = 1; break; else if(x0point.y) right = 1; else left = 1; /if /for if(up & down & left & right) printf(Yes,the point is in the polygon.n); else printf(No,the point is not in the polygon.n); while(getchar()!=n); /接

14、收多余的字符 printf(would you like to go on?); flag = getchar(); /flag只接收第一个字符 while(getchar()!=n); /接收多余的字符 /while5、从平均时间、最坏情况，辅助存储和稳定性的角度，对各种内部排序方法进行比较。（建议用表格方式进行比较，本题20分）严蔚敏数据结构289页6、定义一个双向循环链表，并写出其定位、插入和删除算法。（本题20分）#include#include#define OK 1#define ERROR 0typedef int Status;typedef int ElemType;type

15、def struct DuLNode ElemType data; struct DuLNode *prior; struct DuLNode *next;DuLNode,*DuLinkList;Status GetElem_DuL(DuLinkList L,int i,ElemType *e) int j = 1; DuLNode *p; p = L-next; while(p!=L & jnext; j+; if(p=L | j!=i) return ERROR; *e = p-data; return OK;Status ListInsert_DuL(DuLinkList &L,int

16、i,ElemType e)/在带头结点的双链循环链表L中第i个位置之前插入元素e /i的合法位置为1=i=表长+1 int j; DuLNode *p,*s; if(inext; while(p!= L & jnext; j+; if(ji) /查找完循环链表后，如果jdata = e; s-prior = p-prior; p-prior-next = s; s-next = p; p-prior = s; return OK;Status ListDelete_DuL(DuLinkList &L,int i,ElemType *e)/删除带头结点的双链循环线性表L的第i个元素，i的合法位置

17、为1=i=表长 int j; DuLNode *p; if(inext; while(p!=L & jnext; j+; if(p=L) return ERROR; *e = p-data; p-prior-next = p-next; p-next-prior = p-prior; free(p); return OK;void print(DuLinkList L) DuLNode *p; p = L-next; while(p!=L) printf(%d ,p-data); p = p-next; printf(n);void main() int i; ElemType e; DuLi

18、nkList L; if(!(L=(DuLNode *)malloc(sizeof(DuLNode) exit(0); L-next = L; L-prior = L; for(i=1;i10;i+) e = (ElemType)i; if(!(ListInsert_DuL(L,i,e) printf(No.%d is wrong!n,i); print(L); ListInsert_DuL(L,5,(ElemType)10); print(L); ListDelete_DuL(L,1,&e); print(L); printf(please input a number:); scanf(%

19、d,&i); if(GetElem_DuL(L,i,&e) printf(L%d=%dn,i,e); else printf(%d is illegal!n,i);7、编制一个程序以模拟银行窗口接待客户的排队业务活动（每个窗口在某个时刻只能接待一个客户；窗口空闲，则可上前办理业务；窗口均被占，则新客户便会排在人数最少的队伍前面），并计算一天中客户在银行逗留的平均时间。（本题20分）#include#include#include#define MAX 10000#define OK 1#define ERROR 0/*数据类型定义(Start)*/typedef int Status;type

20、def struct int OccurTime; /事件发生时刻 int NType; /事件类型，05Event,ElemType; /事件类型，有序链表LinkList的数据元素类型typedef struct LNode ElemType data; struct LNode *next;LNode,*LinkList;typedef LinkList EventList; /事件链表类型，定义为有序链表typedef struct int ArrivalTime; /到达时间 int Duration; /办理事务所需时间QElemType; /队列的数据元素类型typedef st

21、ruct QNode QElemType data; struct QNode *next;QNode,*QueuePtr;typedef struct QueuePtr front; QueuePtr rear;LinkQueue;/*数据类型定义(Over)*/*程序中用到的主要变量(Start)*/EventList ev; /事件表Event en; /事件LinkQueue q5; /4个客户队列QElemType customer; /客户记录long TotalTime,CustomerNum; /累计客户逗留时间，客户数/*程序中用到的主要变量(Over)*/*自定义函数部分(

22、Start)*/*链表操作部分(start)*/int cmp(ElemType a,ElemType b) if(a.OccurTimeb.OccurTime) return 1; else if(a.OccurTime=b.OccurTime) return 0; else return -1;void InitList(LinkList &L) L = (LNode *)malloc(sizeof(LNode); if(!L) printf(EVENTLIST INIT ERROR!n); else L-next = NULL; void OrderInsert(LinkList L,E

23、lemType en) 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;int ListEmpty(LinkList L) if(L-next!=NULL) return 0; else return 1;void DelFirst(LinkLis

24、t L,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)*/void InitQueue(LinkQueue *Q) Q-front = Q-rear = (QNode *)malloc(sizeof(QNode); if(!(Q-front) printf(LinkQueue INIT ERROR!n); Q-front-next = NULL;Sta

25、tus DelQueue(LinkQueue *Q,QElemType *e) QNode *p; if(Q-front=Q-rear) return ERROR; 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); return OK;Status EnQueue(LinkQueue *Q,QElemType e) QNode *p; p = (QN

26、ode *)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; return OK;int QueueLength(LinkQueue *Q) int i=0; QNode *p; if(Q-front=Q-rear) i = 0; else p = Q-front; while(p!=Q-rear) p = p-next; i+; return i;/*队列操作部分(over)*/*业务操作部分(start)*/void Random(long *durtime,long *intertime) srand(time(NULL); *durtime = rand(); *intertime = rand();int Minimum(LinkQueue q) int i,j,k=0