省二级(C语言)考试真题重点题型分类总结!2

1、C语言二级真题总结真题汇总小结省二级考试C语言真题重点题型分类 一、线性表建立、删除、插入 二、文件操作文件翻开、读、写 三、递归问题 四、字符串操作问题 五、变量作用域与静态变量问题 六、数列或数字处理问题 七、排序问题 八、上机试题 线性表是n 个数据元素的有限序列。通常记作a1, a2, a3, , an 。 姓名 电话号码 蔡颖 63214444 陈红 63217777 刘建平 63216666 王小林 63218888 张力 63215555 .一、线 性 表例1、数学中的数列11，13，15，17，19，21例2、英文字母表A, B, C, D, E Z 。例3、某单位的 号码簿。

2、一 线性表的逻辑结构 号码簿是数据元素的有限序列，每一数据元素包括两个数据项，一个是用户姓名，一个是对应的 号码。说明：设 A=a1, a2, . , ai -1, ai , ai+1, , an 是一线性表1 均匀性：线性表的数据元素可以是各种各样的，但同一线性表中的元素必须是同一类型的；2 相邻性：每个元素至少有一个元素与之相邻。在表中 ai-1 领先于ai ，ai 领先于ai+1 ，称ai-1 是ai 的直接前趋，ai+1 是ai 的直接后继； a1,无前驱，an无后继。3 有限性：线性表中元素的个数n称为线性表的长度，n=0时称为空表4 有序性：ai是线性表的第i 个元素，称i 为数据

3、元素ai 的序号，每一个元素在线性表中的位置，仅取决于它的序号；二 线性表根据其存储结构不同可分为： 链式存储结构的链表 顺序存储结构的顺序表一 线性链表的概念1 线性链表1、 线性链表a4a3a1a2 0101010241014101010121014101610181020102210241026 用一组任意的存储单元存储线性表中的数据元素，对每个数据元素除了保存自身信息外，还保存了直接后继元素的存储位置。 用线性链表存储线性表时，数据元素之间的关系 是通过保存直接后继元素的存储位置来表示的线性链表图示ai-1aia2a1ai+1nan 用线性链表存储线性表时，数据元素之间的关系 是通过保

4、存直接后继元素的存储位置来表示的2 线性链表图示 一般来说，我们并不需要写出直接后继的实际地址，为直观起见，通常用如下所示的图表示链表，其中，箭头表示相应单元中保存的是它所指向结点的存储地址。head是头指针head结点：数据元素及直接后继的存储位置地址组成一个数据元素的存储结构，称为一个结点；结点的数据域 ：结点中用于保存数据元素的局部;结点的指针域 ：结点中用于保存数据元素直接后继存储地址的局部;3 线性链表有关术语存储数据元素存储后继结点 存储地址结点数据域指针域头指针：用于存放线性链表中第一个结点的存储地址;空指针：不指向任何结点，线性链表最后一个结点的指针通常是空指针，空指针一般用N

5、ULL表示;头结点：线性链表的第一元素结点前面的一个附加结点，称为头结点；带头结点的线性链表：第一元素结点前面增加一个附加结点的线性链表称为 带头结点的线性链表；带头结点的线性链表图示head是头指针ai-1aia2a1ai+1nan 头结点 空指针head线性链表的每个结点中只有一个指针域故也称为单链表ai-1aia2a1ai+1nanhead是头指针head注：从以往二级考试来看都是用没有附加头结点的链表，如下图结点变量图示struct node int x； struct node *next； ; node：结构体类型名； node类型结构变量有两个域： x：用于存放线性表的数据元素，

6、 next：用于存放元素直接后继结点的地址； 该类型结构变量用于表示线性链表中的一个结点； h和head：指向结构体结点的指针变量，用于存放node类型结构变量的地址； 数据域指针域 x next node类型 结构变量h结构体结点 指针变量h4 线性链表的结点类型定义及指向结点的指针类型定义struct node *h；或struct node *head；结构体指针变量定义结构体类型定义常用的引用格式(一般格式)： 指针变量名-结构体成员名如： h-x=10; h=h-next;注意：在引用过程中，数据类型还是成员的数据类型。 如：h-x为成员x的数据类型即整形5 怎样利用结构体指针变量来

7、引用结构体成员struct node *h；或struct node *head；不常用引用格式： *指针变量名. 结构体成员名如： (*h). x=10; *h=(*h).next; 设head是指向链表第一个结点的指针变量，head用来保存线性链表中第一个结点的地址。ai-1aia2a1ai+1nanheadHead指向的链表二 线性链表根本操作的算法 假设线性表用不带头结点的线性链表head的存储。下面讨论在这种存储方式下，线性表各种根本操作的算法。当线性表用线性链表存储时，对线性表各种根本操作实际上就是对存储在内存中的线性链表进行操作。如何在线性链表head上实现线性表的根本操作？如何

8、建空表？如何插入？删除？1 取元素操作 从链表中找到与输入的值m相等的元素功能：1、将线性链表中第i 个元素赋值给 e 2、从链表中找到与输入的值m相等的元素，并将其指针返回取元素操作主要步骤：1查找链表的第 i个元素结点；2) 将第i个元素结点中的数据元素赋值给e;或将其指针返回; 取元素操作图示ai-1aia2a1ai+1nanheadp1p注：p、p1为工作指针2 插入操作 功能：在线性链表head的第i个元素结点之前插入一个新元素结点； 插入操作图示：插入前插入后 ai-1aia2a1ai+1nanheadai-1aia2a1ai+1nanehead插入操作主要步骤：1查找链表L的第

9、i-1个元素结点；2为新元素建立结点；3修改第 i-1个元素结点的指针域和新元素结点指针域，从而完成插入；3 删除操作 功能：在线性链表L中删除第i个元素，并且用e 返回其值 删除操作图示： 删除前删除后ai-1aia2a1ai+1nanheadai-1aia2a1ai+1nanhead删除操作主要步骤：1查找链表的第 i-1个元素结点；2修改第 i-1个元素结点指针域，使其指向第i+1个结点，从而删除第i个元素结点；3) 将第i个元素结点中的数据元素赋值给e;4回收被删除结点空间；用free(指针变量)函数释放删除结点的空间4 线性链表归并操作图示131n542n6papb归并31n6pap

10、cpb524以前考过的线性链表的题目P10 13题即2000年秋的填空题中的13题此题是链表归并问题： 首先要搞清楚每个指针的用途。 如pt指针变量就是用来指向建立的新结点； pc为新链表的头结点； pcr为工作结点，也是新链表的尾结点指针，即它始终指针新链表的最后一个结点。P60 13题即2000年秋的填空题中的13题PNODE *paddPNODE *pa, PNODE *pb)PNODE *pcr , *pt , *pc; pc=NULL; while( (23) ) if(pa-y=pb-y) pt=( (24) )malloc(sizeof(PNODE); pt-x=pa-x+pb-

11、x; pt-y=pa-y; pt-next=NULL; if (pc=NULL) pc=pcr=pt; else pcr-next=pt; (25) ; pa=pa-next; pb=pb-next; else if( (26) ) pb=pb-next; else pa=pa-next; Return pc;本空显然是控制结束的，只有当pa、pb两个链表中都没有元素时才会结束分配的空间类型判断papb中当前元素y成员的值谁大将新增的结点连到工作指针pcr上P10 13题答案PNODE *paddPNODE *pa, PNODE *pb)PNODE *pcr , *pt , *pc; pc=N

12、ULL; while( (23) ) if(pa-y=pb-y) pt=( (24) )malloc(sizeof(PNODE); pt-x=pa-x+pb-x; pt-y=pa-y; pt-next=NULL; if (pc=NULL) pc=pcr=pt; else pcr-next=pt; (25) ; pa=pa-next; pb=pb-next; else if( (26) ) pb=pb-next; else pa=pa-next; Return pc;pa&pbPNODE *pa-ypb-ypcr=ptP21 14题即2001年春的填空题中的14题PNODE *paddPNODE

13、 *pa)PNODE *p1 , *p2, *p; p1=p2=pa; while(p1) if(p1-x%2=0& (27) ) p=p1; p1=p1-next; (28) =p1; P-next=pa; (29) else p2=p1; p1=p1-next; Main() PNODE a10=1,2,3,4,5,6,7,8,9,10, *ha=a, *p; int i; for(i=0; i, p-x); p=p-next; 链表结尾的指针NULL如果p1指向的结点就是第一个结点，那么不用移本行是从链表中删除结点将p指向的结点插到链表的头部没找着偶数值结点时，指针向后移，P2一直在P1

14、的前一个结点P21 14题答案PNODE *paddPNODE *pa)PNODE *p1 , *p2, *p; p1=p2=pa; while(p1) if(p1-x%2=0& (27) ) p=p1; p1=p1-next; (28) =p1; P-next=pa; (29) else p2=p1; p1=p1-next; Main() PNODE a10=1,2,3,4,5,6,7,8,9,10, *ha=a, *p; int i; for(i=0; i, p-x); p=p-next; NULLp1!=pap2-next=p1pa=pP31 14题即2001年秋的填空题中的14题Str

15、uct node *deladdstruct node *h, int value)struct node *p1 , *p2; int flage=0; p1=p2=h; while(p1&flage=0) if(p1-x=value) flage=1; if(p1=h) h= (27) ; free(p1); else p2-next= (28) ; free(p1); else p2=p1; p1= (29) ; If(flage=0) p1=(struct node *)malloc(sizeof(struct node); p1-x=value; p1-next=0; if(h=0)

16、 h=p1; else (30) ; 链表结束或找到结点不执行循环Flage是一个标志变量用来标志是否找到结点如果找到符合每件的结点，就删除结点如果没找到适合每件的结点，那么指针后移如果没找到结点构造一个新结点如果链表为空就直接将构造的结点作为链表的第一个结点，否那么将其插入到链表最后P31 14题答案Struct node *deladdstruct node *h, int value)struct node *p1 , *p2; int flage=0; p1=p2=h; while(p1&flage=0) if(p1-x=value) flage=1; if(p1=h) h= (27)

17、 ; free(p1); else p2-next= (28) ; free(p1); else p2=p1; p1= (29) ; If(flage=0) p1=(struct node *)malloc(sizeof(struct node); p1-x=value; p1-next=0; if(h=0) h=p1; else (30) ; p1-nextp1-nextp1-nextp2-next=p1P42 14题即2002年春的填空题中的14题 (27) createint n)struct node *p, *p1 , *p2, *h=NULL; int i=0; if(nx); p

18、-next=NULL; if(h=NULL) (29) ; else p1=p2=h; while(p2&p-x=p2-x) p1=p2; p2=p2-next; if(p2=h) (30) ; h=p; else p-next=p2; p1-next=p; i+; Return h;函数返回值类型如果找到的插入位置是第一个结点创立结点个数的控制如果链表为空，直接插入结点作为首结点如果找到的插入位置不是第一个结点就在找到的位置插入P42 14题答案 (27) createint n)struct node *p, *p1 , *p2, *h=NULL; int i=0; if(nx); p-n

19、ext=NULL; if(h=NULL) (29) ; else p1=p2=h; while(p2&p-x=p2-x) p1=p2; p2=p2-next; if(p2=h) (30) ; h=p; else p-next=p2; p1-next=p; i+; Return h;struct node *p-next=p2inext=NULL) return head; if(dir=0) while(p1-next) p2=p1; p1= p1-next ; (23) =NULL; p1-next= (24) ; head=p1; else head= (25) ; p2=head; wh

20、ile(p2-next) p2=p2-next; (26) ; p1-next=NULL; return head;右移一次如果是空链表或只有一个结点的链表左移一次找到最后一个结点使得p1指向最后一个结点P2指向倒数第二个结点将最后一个结点p1指向的移到链表头找到最后一个结点P2指向最后一个结点P51 14题答案Struct node *loopstruct node *head, int dir)struct node *p1 , *p2; p1=head; if(p1=NULL|p1-next=NULL) return head; if(dir=0) while(p1-next) p2=p

21、1; p1= p1-next ; (23) =NULL; p1-next= (24) ; head=p1; else head= (25) ; p2=head; while(p2-next) p2=p2-next; (26) ; p1-next=NULL; return head;p1-nextp2-nextheadp2-next=p1P60 14题即2003年春的填空题中的14题Struct node *find_delstruct node *head, int *pm)struct node *p1 , *p2 , *pmax , *pre; if(head=NULL) return N

22、ULL; pmax= (23) ; p2=p1=pmax; while(p1) if(p1-x (24) ) pre=p2; pmax=p1; p2=p1; p1=p1-next; if(pmax=head ) head =pmax-next; else (25) =pmax-next; (26) =pmax;Return head; 如果是空链表就结束函数，并返回空指针首先认为第一个结点是x值最大的结点Pmax始终指向当前x值最大的结点P1为工作指针活动指针如果首结点的x值最大就删除首结点删除pmax指向的结点将x值最大的结点地址保存到pm指向的指针变量中P60 14题即2003年春的填空题

23、中的14题Struct node *find_delstruct node *head, int *pm)struct node *p1 , *p2 , *pmax , *pre; if(head=NULL) return NULL; pmax= (23) ; p2=p1=pmax; while(p1) if(p1-x (24) ) pre=p2; pmax=p1; p2=p1; p1=p1-next; if(pmax=head ) head =pmax-next; else (25) =pmax-next; (26) =pmax;Return head; headpmax-xpre-next

24、*pmc 2.2 线性表的顺序表示和实现 一 线性表的顺序存储结构顺序表 1 线性表的顺序存储结构 2 顺序表的类型定义 二 顺序表的根本操作算法 三 利用根本操作实现线性表的其他操作2、顺序链表2、顺序链表为了存储线性表，至少要保存两类信息：1线性表中的数据元素；2线性表中数据元素的顺序关系； 在计算机内部可以采用不同的方式来存储一个线性表，其中最简单的方式就是本节要讲的线性表的顺序存储结构。 线性表的顺序存储结构，就是用一组连续的内存单元依次存放线性表的数据元素。用顺序表存储线性表时，数据元素之间的逻辑关系， 是通过数据元素的存储顺序反映出来的a1a2ai-1aiai+1an 线性表a1,

25、a2, a3, . an 的顺序存储结构用顺序存储结构存储的线性表称为顺序表一 线性表的顺序存储结构顺序表1 线性表的顺序存储结构说明： 在顺序存储结构下，线性表元素之间的逻辑关系，可通过元素的存储顺序反映表示出来，所以只需存储数据元素的信息； 假没线性表中每个数据元素占用 k 个存储单元，那么，在顺序存储结构中，线性表的第i个元素的存储位置与第1个元素的存储位置的关系是： Loc(ai ) = Loc( a1 )+ ( i 1) k 这里 Loc(ai)是第 i 个元素的存储位置, Loc( a1 ) 是第1个元素的存储位置，也称为线性表的基址；怎样在计算机上实现线性表的顺序存储结构？2、顺

26、序表的类型定义 以上用自然语言描述了线性表的顺序存储结构，怎样将这种存储方式在计算机上实现？为此，我们用C语言对这种存储方式进行描述，我们知道C语言一维数组的机内表示也是顺序结构，因此，可借用C语言的一维数组实现线性表的顺序存储。顺序表的类型定义#define LIST_INIT_SIZE 100 / 线性表存储空间的初始分配量#define LISTINCREMENT 10 / 线性表存储空间的分配增量typedef structElemType * elem; /线性表存储空间基址int length; /当前线性表长度int listsize; /当前分配的线性表存储空间大小 /以siz

27、eof(ElemType)为单位SqList;SqList ：类型名，SqList类型的变量是结构变量，它的三个域分别是： *elem：存放线性表元素的一维数组基址；其存储空间在初始化操作建空表时动态分配； length：存放线性表的表长； listsize：用于存放当前分配存放线性表元素的存储空间的大小。顺序表图示a1a2ai-1aiai+1anL.lengthL.listsizeL.elemnLIST_INIT_SIZE存放线性表元素 的一维数组设 A = a1,a2 , a3 , . an 是一线性表，L是SqList 类型的结构变量，用于存放线性表A，那么L在内存中的状态如下图：如何在

28、顺序表上实现线性表的根本操作？如何建空表？如何求表长？如何插入？删除？ 设线性表用顺序表L存储，下面我们介绍用顺序表存储线性表时，各种根本操作的算法。当线性表用顺序表存储时，对线性表各种根本操作实际上就是对存储在内存中的顺序表进行操作。二、顺序表的根本操作算法取元素操作图示 1 取元素操作 GetElem_Sq ( SqList L, int i, ElemType &e )功能：将顺序表中第i 个元素赋值给 e算法：Status GetElem_Sq ( SqList &L, int i, ElemType &e ) If (i L.length -1) return ERROR; / i

29、非法 e = L.elem i-1 ; /将顺序表中第i 个元素赋值给 e return OK;/ GetElem_Sq 算法2.4 由于C语言的一维数组下标从0开始, 故线性表的第一个元素放在L.elem0，第i个素放L.elemi-1中，最后一个元素放在 L.elemL.length-1中。 取元素操作 nLIST_INIT_SIZEL.lengthL.listsizeL.elem01LIST_INIT_SIZE-1a1a2ai-1aiai+1ann LIST_INIT_SIZE-1eai 再演示一次2 插入操作 ListInsert_Sq ( &L, i, e ) 参数：L ：顺序表 ，

30、 i 插入位置， e 被插入元素; 因为插入操作对顺序表进行修改,所以用了引用参数&L; 功能：在顺序表L的第i个元素之前插入一个新元素e; 插入操作示意图： 插入操作图示插入操作主要步骤：1i 是否合法，假设合法转2，否那么算法结束，并返回ERROR；2L是否已满， 假设未满转3，否那么算法结束，并返回ERROR；3将顺序表ai 及之后的所有元素后移一个位置；4) 将新元素写入空出的位置；5表长+1 ； 用鼠标单击图中的绿字 插入元素操作eL.lengthL.listsizeL.elem01LIST_INIT_SIZE-1a1a2ai-1aiai+1ann LIST_INIT_SIZE-1

31、插入元素操作L.lengthL.listsizeL.elem01LIST_INIT_SIZE-1a1a2ai-1eaiann+1 LIST_INIT_SIZE-1Status ListInsert_Sq(SqList &L, int i , ElemType e) /在顺序表L中第i个位置之前插入新的元素e,/ i的合法值为1iL.length+1,当i =L.length+1时/ e插在表尾if (iL.length+1) return ERROR; / i值不合法if (L.length=L.listsize) return ERROR; /顺序表已满for ( j=L.length-1

32、; j= i-1; -j) L.elemj+1= L.elem j; /插入位置及之后的元素后移一个位置 L.elemi-1 =e; /插入e+L.length; /表长增1return OK;/ListInsert_Sq 算法2.5a 插入操作算法为初学者易于理解插入算法，这里通过下标引用L.elem中的元素。3 删除操作 ListDelete_sq ( SqList &L, int i, ElemType &e ) 功能：删除顺序表L的第i个元素，并用e返回删除操作图示 删除操作主要步骤 ：1i 不合法或表空，算法结束，并返回ERROR；否那么转22将ai赋值给e; 3将顺序表中ai后面的

33、元素依次向前移动一个位置;4表长-1 删除操作图示用鼠标单击图中的绿字 删除元素操作L.lengthL.listsizeL.elem01LIST_INIT_SIZE-1a1a2ai-1aiai+1ann LIST_INIT_SIZE-1 删除元素操作L.lengthL.listsizeL.elem01LIST_INIT_SIZE-1a1a2ai-1ai+1ann-1 LIST_INIT_SIZE-1删除操作算法Status ListDelete_Sq(SqList &L, int i, ElemType &e) /在顺序表L中删除第 i个元素，并用e返回其值 / i的合法值为 1iL.leng

34、th， / 表空L.length=0 那么i L.length if (iL.length) return ERROR; / i值不合法或表空 e = L.elemi-1; / 被删除元素的值赋给e for ( j= i; j= L.length-1; +j) L.elemj-1 = L.elem j /被删除元素之后的元素前移 -L.length; /表长减1 return OK;/ListDelete_Sq 算法2.56a为初学者易于理解插入算法，这里通过下标引用L.elem中的元素。二级考试以往出现的顺序表试题P61 2003春15题 顺序表排序P49 2002秋12题 顺序表插入元素P

35、40 2002春11题 顺序表处理P29 2001秋12题 顺序表处理P20 2001春12题 顺序表排序二、文件操作 1、文件类型指针变量的定义格式： FILE 如：FILE *fp；、文件翻开与关闭翻开文件-fopen()函数如：FILE *fp; if(fp=fopen(“c:tc2example1.txt,w)= =NULL) printf(“File can noet be opened!n); exit(0); 文件翻开方式：MODE文件类型处理方式指定文件不存在时指定文件存在时“r”文本文件读取出错正常打开“r+”文本文件读取/写入出错正常打开“rb”二进制文件读取出错正常打开“

36、rb+”二进制文件读取/写入出错正常打开“w”文本文件写入建立新文件文件原有内容丢失“w+”文本文件写入/读取建立新文件文件原有内容丢失“wb”二进制文件写入建立新文件文件原有内容丢失“wb+”二进制文件写入/读取建立新文件文件原有内容丢失“a”文本文件追加建立新文件在文件原有内容后追加“a+”文本文件读取/追加建立新文件在文件原有内容后追加“ab”二进制文件追加建立新文件在文件原有内容后追加“ab+”二进制文件读取/追加建立新文件在文件原有内容后追加关闭文件-fclose()函数关闭文件的功能：是将写入到内容文件指针位置的内容存储到硬盘上的文件中，并关闭文件，释放文件指针。在程序终止前必须关

37、闭文件。否那么，向文件中存入的内容全部没有存入。使用格式：fclose(文件指针)；文件的相关函数文件所有的读写，输入输出函数在使用时，必须包含头文件：stdio.h 即：#include 1、feof文件指针变量本函数是判断文件是否结束。如果返回值为：真，那么表示已到文件尾；如果返回值为：假，那么表示未到文件尾。、fgetc(文件指针变量从文件中读出一个字符，并将文件当前位置移到下一位置。返回值：读出的值；EOF读出出错、fputc(字符，文件指针变量将字符常量或变量写入文件指针指向的文件当前位置。返回值：写入的值；EOF写入出错字符串输入输出函数、fgets(字符串变量名，n，文件指针变量

38、从文件中读出一个长度为n-1的字符串，放到字符串变量。返回值：读出字符串的长度；EOF读出出错、fputs(字符串，文件指针变量将字符串常量或变量写入文件指针指向的文件当前位置。返回值：写入的字符数；EOF写入出错格式化输入输出函数6、fscanf(fp，“输入格式串，输入项完成从文件中读入操作的函数。7、fprintf(fp，“输出格式串，输出项 向文件输出数据的函数。向fp指向的文件按“输出格式串中规定，输出到文件中。块输入输出函数8、fread(buffer，size，count，fp9、fwrite(buffer，size，count ，fp 参数说明： buffer是一个指针，对于f

39、read来说是读入数据块的存放地址；对fwrite来说，它是输出数据块的地址。这里的地址是指数据块的首地址，通常用数据名或数组指针或结构体数组来代表。 size 是要读/写数据块的字节数 count 的值是要读/写多少个 size 字节的数据块 fp 是一个文件指针，指示已经翻开的文件由fopen()函数翻开的文件定位函数8、rewind(fp)将文件读写位置重新设置在文件头部。9、fseek(fp，long offset ，int origin) 参数说明： 1fp 是指向要进行读写操作的文件结构指针，该文件已由fopen()函数翻开； 2origin是计算文件指针位置的起始点； 文件指针的

40、起始点可以设置在三个不同的位置上，用三个符号常量或数字代表： SEEK_SET 或 0 代表文件头 SEEK_CUR 或 1 代表文件当前位置 SEEK_END 或 2 代表文件尾 3offset是距起始点的偏移位置，以字节为单位。二级考试以往出现的文件操作试题P10 2000秋14题 在文件中查找并替换P19 2001春10题 从文件读入/向文件输出P29、30 2001秋11、13题 从文件读入P40 2002春11题 从文件读入在每次的上机题中，编写的程序输出内容必须输出到文件中三、递归问题P7、 P8 2000秋5题、8题 P20 2001春12题 用递归实现排序冒泡排序P28 2001秋8题P49 2002秋11题P59 2003 春11题四、字符串操作问题P9 2000秋12题 从字符串中删除子串P20 2001春13题 插入子串P30 2001秋13题 读子串P39 2002春10题 字符串加密P51 2002秋15题 在