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

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

《省二级(C语言)考试真题重点题型分类总结.ppt》由会员分享，可在线阅读，更多相关《省二级(C语言)考试真题重点题型分类总结.ppt（72页珍藏版）》请在冰点文库上搜索。

C语言二级真题总结,真题汇总小结,省二级考试C语言真题重点题型分类一、线性表（建立、删除、插入）二、文件操作（文件打开、读、写）三、递归问题四、字符串操作问题五、变量作用域与静态变量问题六、数列或数字处理问题七、排序问题八、上机试题,线性表是n个数据元素的有限序列。

通常记作（a1,a2,a3,an）。

一、线性表,例1、数学中的数列（11，13，15，17，19，21）例2、英文字母表（A,B,C,D,EZ）。

例3、某单位的电话号码簿。

一线性表的逻辑结构,电话号码簿是数据元素的有限序列，每一数据元素包括两个数据项，一个是用户姓名，一个是对应的电话号码。

说明：

设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为数据元素ai的序号，每一个元素在线性表中的位置，仅取决于它的序号；二线性表根据其存储结构不同可分为：

链式存储结构的链表顺序存储结构的顺序表,一线性链表的概念1线性链表,1、线性链表,用一组任意的存储单元存储线性表中的数据元素，对每个数据元素除了保存自身信息外，还保存了直接后继元素的存储位置。

用线性链表存储线性表时，数据元素之间的关系是通过保存直接后继元素的存储位置来表示的,线性链表图示,用线性链表存储线性表时，数据元素之间的关系是通过保存直接后继元素的存储位置来表示的,2线性链表图示一般来说，我们并不需要写出直接后继的实际地址，为直观起见，通常用如下所示的图表示链表，其中，箭头表示相应单元中保存的是它所指向结点的存储地址。

head是头指针,head,结点：

数据元素及直接后继的存储位置（地址）组成一个数据元素的存储结构，称为一个结点；结点的数据域：

结点中用于保存数据元素的部分;结点的指针域：

结点中用于保存数据元素直接后继存储地址的部分;,3线性链表有关术语,存储数据元素,存储后继结点存储地址,头指针：

用于存放线性链表中第一个结点的存储地址;空指针：

不指向任何结点，线性链表最后一个结点的指针通常是空指针，空指针一般用NULL表示;头结点：

线性链表的第一元素结点前面的一个附加结点，称为头结点；带头结点的线性链表：

第一元素结点前面增加一个附加结点的线性链表称为带头结点的线性链表；,带头结点的线性链表图示,head是头指针,头结点,空指针,head,线性链表的每个结点中只有一个指针域故也称为单链表,head是头指针,head,注：

从以往二级考试来看都是用没有附加头结点的链表，如图所示,结点变量图示,structnodeintx；structnode*next；;,node：

结构体类型名；node类型结构变量有两个域：

x：

用于存放线性表的数据元素，next：

用于存放元素直接后继结点的地址；该类型结构变量用于表示线性链表中的一个结点；h和head：

指向结构体结点的指针变量，用于存放node类型结构变量的地址；,xnext,node类型结构变量,结构体结点指针变量h,4线性链表的结点类型定义及指向结点的指针类型定义,structnode*h；或structnode*head；,结构体指针变量定义,结构体类型定义,常用的引用格式（一般格式）：

指针变量名-结构体成员名如：

h-x=10;h=h-next;,注意：

在引用过程中，数据类型还是成员的数据类型。

如：

h-x为成员x的数据类型（即整形）,5怎样利用结构体指针变量来引用结构体成员,structnode*h；或structnode*head；,不常用引用格式：

（*指针变量名）.结构体成员名如：

（*h）.x=10;*h=（*h）.next;,设head是指向链表第一个结点的指针变量，head用来保存线性链表中第一个结点的地址。

Head指向的链表,二线性链表基本操作的算法假设线性表用不带头结点的线性链表head的存储。

下面讨论在这种存储方式下，线性表各种基本操作的算法。

当线性表用线性链表存储时，对线性表各种基本操作实际上就是对存储在内存中的线性链表进行操作。

如何在线性链表head上实现线性表的基本操作？

如何建空表？

如何插入？

删除？

？

1取元素操作（从链表中找到与输入的值m相等的元素）功能：

1、将线性链表中第i个元素赋值给e2、从链表中找到与输入的值m相等的元素，并将其指针返回取元素操作主要步骤：

1）查找链表的第i个元素结点；2）将第i个元素结点中的数据元素赋值给e;（或将其指针返回;）,取元素操作图示,注：

p、p1为工作指针,2插入操作功能：

在线性链表head的第i个元素结点之前插入一个新元素结点；插入操作图示：

插入前,插入后,插入操作主要步骤：

1）查找链表L的第i-1个元素结点；2）为新元素建立结点；3）修改第i-1个元素结点的指针域和新元素结点指针域，从而完成插入；,3删除操作功能：

在线性链表L中删除第i个元素，并且用e返回其值删除操作图示：

删除前,删除后,删除操作主要步骤：

1）查找链表的第i-1个元素结点；2）修改第i-1个元素结点指针域，使其指向第i+1个结点，从而删除第i个元素结点；3）将第i个元素结点中的数据元素赋值给e;4）回收被删除结点空间；用free（指针变量）函数释放删除结点的空间,4线性链表归并操作图示,1,3,1,n,5,4,2,n,6,3,1,5,以前考过的线性链表的题目,P1013题（即2000年秋的填空题中的13题）,此题是链表归并问题：

首先要搞清楚每个指针的用途。

如pt指针变量就是用来指向建立的新结点；pc为新链表的头结点；pcr为工作结点，也是新链表的尾结点指针，即它始终指针新链表的最后一个结点。

P6013题（即2000年秋的填空题中的13题）,PNODE*padd（PNODE*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-x;pt-y=pa-y;pt-next=NULL;if（pc=NULL）pc=pcr=pt;elsepcr-next=pt;（25）;pa=pa-next;pb=pb-next;elseif（26）pb=pb-next;elsepa=pa-next;Returnpc;,本空显然是控制结束的，只有当pa、pb两个链表中都没有元素时才会结束,分配的空间类型,判断papb中当前元素y成员的值谁大,将新增的结点连到工作指针pcr上,P1013题（答案）,PNODE*padd（PNODE*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-x;pt-y=pa-y;pt-next=NULL;if（pc=NULL）pc=pcr=pt;elsepcr-next=pt;（25）;pa=pa-next;pb=pb-next;elseif（26）pb=pb-next;elsepa=pa-next;Returnpc;,pa&pb,PNODE*,pa-ypb-y,pcr=pt,P2114题（即2001年春的填空题中的14题）,PNODE*padd（PNODE*pa）PNODE*p1,*p2,*p;p1=p2=pa;while（p1）if（p1-x%2=0,链表结尾的指针（NULL）,如果p1指向的结点就是第一个结点，则不用移,本行是从链表中删除结点,将p指向的结点插到链表的头部,没找着偶数值结点时，指针向后移，P2一直在P1的前一个结点,P2114题（答案）,PNODE*padd（PNODE*pa）PNODE*p1,*p2,*p;p1=p2=pa;while（p1）if（p1-x%2=0,NULL,p1!

=pa,p2-next=p1,pa=p,P3114题（即2001年秋的填空题中的14题）,Structnode*deladd（structnode*h,intvalue）structnode*p1,*p2;intflage=0;p1=p2=h;while（p1,链表结束或找到结点不执行循环,Flage是一个标志变量用来标志是否找到结点,如果找到符合每件的结点，就删除结点,如果没找到适合每件的结点，则指针后移,如果没找到结点构造一个新结点,如果链表为空就直接将构造的结点作为链表的第一个结点，否则将其插入到链表最后,P3114题（答案）,Structnode*deladd（structnode*h,intvalue）structnode*p1,*p2;intflage=0;p1=p2=h;while（p1,p1-next,p1-next,p1-next,p2-next=p1,P4214题（即2002年春的填空题中的14题）,（27）create（intn）structnode*p,*p1,*p2,*h=NULL;inti=0;if（nx）;p-next=NULL;if（h=NULL）（29）;elsep1=p2=h;while（p2,函数返回值类型,如果找到的插入位置是第一个结点,创建结点个数的控制,如果链表为空，直接插入结点作为首结点,如果找到的插入位置不是第一个结点就在找到的位置插入,P4214题（答案）,（27）create（intn）structnode*p,*p1,*p2,*h=NULL;inti=0;if（nx）;p-next=NULL;if（h=NULL）（29）;elsep1=p2=h;while（p2,structnode*,p-next=p2,in,h=p,P5114题（即2002年秋的填空题中的14题）,Structnode*loop（structnode*head,intdir）structnode*p1,*p2;p1=head;if（p1=NULL|p1-next=NULL）returnhead;if（dir=0）while（p1-next）p2=p1;p1=p1-next;（23）=NULL;p1-next=（24）;head=p1;elsehead=（25）;p2=head;while（p2-next）p2=p2-next;（26）;p1-next=NULL;returnhead;,右移一次,如果是空链表或只有一个结点的链表,左移一次,找到最后一个结点使得p1指向最后一个结点P2指向倒数第二个结点,将最后一个结点（p1指向的）移到链表头,找到最后一个结点P2指向最后一个结点,P5114题（答案）,Structnode*loop（structnode*head,intdir）structnode*p1,*p2;p1=head;if（p1=NULL|p1-next=NULL）returnhead;if（dir=0）while（p1-next）p2=p1;p1=p1-next;（23）=NULL;p1-next=（24）;head=p1;elsehead=（25）;p2=head;while（p2-next）p2=p2-next;（26）;p1-next=NULL;returnhead;,p1-next,p2-next,head,p2-next=p1,P6014题（即2003年春的填空题中的14题）,Structnode*find_del（structnode*head,int*pm）structnode*p1,*p2,*pmax,*pre;if（head=NULL）returnNULL;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;Returnhead;,如果是空链表就结束函数，并返回空指针,首先认为第一个结点是x值最大的结点,Pmax始终指向当前x值最大的结点,P1为工作指针（活动指针）,如果首结点的x值最大就删除首结点,删除pmax指向的结点,将x值最大的结点地址保存到pm指向的指针变量中,P6014题（即2003年春的填空题中的14题）,Structnode*find_del（structnode*head,int*pm）structnode*p1,*p2,*pmax,*pre;if（head=NULL）returnNULL;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;Returnhead;,head,pmax-x,pre-next,*pm,c,2.2线性表的顺序表示和实现一线性表的顺序存储结构顺序表1线性表的顺序存储结构2顺序表的类型定义二顺序表的基本操作算法三利用基本操作实现线性表的其他操作,2、顺序链表,2、顺序链表,为了存储线性表，至少要保存两类信息：

1）线性表中的数据元素；2）线性表中数据元素的顺序关系；,在计算机内部可以采用不同的方式来存储一个线性表，其中最简单的方式就是本节要讲的线性表的顺序存储结构。

线性表的顺序存储结构，就是用一组连续的内存单元依次存放线性表的数据元素。

用顺序表存储线性表时，数据元素之间的逻辑关系，是通过数据元素的存储顺序反映出来的,线性表（a1,a2,a3,.an）的顺序存储结构,用顺序存储结构存储的线性表称为顺序表,一线性表的顺序存储结构顺序表,1线性表的顺序存储结构,说明：

在顺序存储结构下，线性表元素之间的逻辑关系，可通过元素的存储顺序反映（表示）出来，所以只需存储数据元素的信息；假没线性表中每个数据元素占用k个存储单元，那么，在顺序存储结构中，线性表的第i个元素的存储位置与第1个元素的存储位置的关系是：

Loc（ai）=Loc（a1）+（i1）k这里Loc（ai）是第i个元素的存储位置,Loc（a1）是第1个元素的存储位置，也称为线性表的基址；,2、顺序表的类型定义以上用自然语言描述了线性表的顺序存储结构，怎样将这种存储方式在计算机上实现？

为此，我们用C语言对这种存储方式进行描述，我们知道C语言一维数组的机内表示也是顺序结构，因此，可借用C语言的一维数组实现线性表的顺序存储。

顺序表的类型定义#defineLIST_INIT_SIZE100/线性表存储空间的初始分配量#defineLISTINCREMENT10/线性表存储空间的分配增量typedefstructElemType*elem;/线性表存储空间基址intlength;/当前线性表长度intlistsize;/当前分配的线性表存储空间大小/（以sizeof（ElemType）为单位）SqList;,SqList：

类型名，SqList类型的变量是结构变量，它的三个域分别是：

*elem：

存放线性表元素的一维数组基址；其存储空间在初始化操作（建空表）时动态分配；length：

存放线性表的表长；listsize：

用于存放当前分配（存放线性表元素）的存储空间的大小。

顺序表图示,存放线性表元素的一维数组,设A=（a1,a2,a3,.an）是一线性表，L是SqList类型的结构变量，用于存放线性表A，则L在内存中的状态如图所示：

如何在顺序表上实现线性表的基本操作？

如何建空表？

如何求表长？

如何插入？

删除？

？

设线性表用顺序表L存储，下面我们介绍用顺序表存储线性表时，各种基本操作的算法。

当线性表用顺序表存储时，对线性表各种基本操作实际上就是对存储在内存中的顺序表进行操作。

二、顺序表的基本操作算法,取元素操作图示,1取元素操作GetElem_Sq（SqListL,inti,ElemType/GetElem_Sq算法2.4由于C语言的一维数组下标从0开始,故线性表的第一个元素放在L.elem0，第i个素放L.elemi-1中，最后一个元素放在L.elemL.length-1中。

取元素操作,nLIST_INIT_SIZE-1,ai,再演示一次,2插入操作ListInsert_Sq（插入操作示意图：

插入操作图示,插入操作主要步骤：

1）i是否合法，若合法转2），否则算法结束，并返回ERROR；2）L是否已满，若未满转3），否则算法结束，并返回ERROR；3）将顺序表ai及之后的所有元素后移一个位置；4）将新元素写入空出的位置；5）表长+1；,用鼠标单击图中的绿字,插入元素操作,nLIST_INIT_SIZE-1,插入元素操作,n+1LIST_INIT_SIZE-1,StatusListInsert_Sq（SqList/ListInsert_Sq算法2.5a,插入操作算法,为初学者易于理解插入算法，这里通过下标引用L.elem中的元素。

3删除操作ListDelete_sq（SqList&L,inti,ElemType&e）功能：

删除顺序表L的第i个元素，并用e返回删除操作图示,删除操作主要步骤：

1）i不合法或表空，算法结束，并返回ERROR；否则转2）2）将ai赋值给e;3）将顺序表中ai后面的元素依次向前移动一个位置;4）表长-1,删除操作图示,用鼠标单击图中的绿字,删除元素操作,nLIST_INIT_SIZE-1,删除元素操作,n-1LIST_INIT_SIZE-1,删除操作算法,StatusListDelete_Sq（SqList/ListDelete_Sq算法2.56a,为初学者易于理解插入算法，这里通过下标引用L.elem中的元素。

二级考试以往出现的顺序表试题,P612003春15题顺序表排序P492002秋12题顺序表插入元素P402002春11题顺序表处理P292001秋12题顺序表处理P202001春12题顺序表排序,二、文件操作,1、文件类型指针变量的定义格式：

FILE如：

FILE*fp；、文件打开与关闭）打开文件-fopen（）函数如：

FILE*fp;if（fp=fopen（“c:

tc2example1.txt”,”w”）=NULL）printf（“Filecannoetbeopened!

n”）;exit（0）;,文件打开方式：

）关闭文件-fclose（）函数关闭文件的功能：

是将写入到内容文件指针位置的内容存储到硬盘上的文件中，并关闭文件，释放文件指针。

在程序终止前必须关闭文件。

否则，向文件中存入的内容全部没有存入。

使用格式：

fclose（文件指针）；,文件的相关函数,文件所有的读写，输入输出函数在使用时，必须包含头文件：

stdio.h即：

#include1、feof（文件指针变量）本函数是判断文件是否结束。

如果返回值为：

（真），则表示已到文件尾；如果返回值为：

（假），则表示未到文件尾。

、fgetc（文件指针变量）从文件中读出一个字符，并将文件当前位置移到下一位置。

返回值：

读出的值；EOF读出出错、fputc（字符，文件指针变量）将字符（常量或变量）写入文件指针指向的文件当前位置。

返回值：

写入的值；EOF写入出错,字符串输入输出函数,、fgets（字符串变量名，n，文件指针变量）从文件中读出一个长度为n-1的字符串，放到字符串变量。

返回值：

读出字符串的长度；EOF读出出错、fputs（字符串，文件指针变量）将字符串（常量或变量）写入文件指针指向的文件当前位置。

返回值：

写入的字符数；EOF写入出错,格式化输入输出函数,6、fscanf（fp，“输入格式串”，输入项）完成从文件中读入操作的函数。

7、fprintf（fp，“输出格式串”，输出项）向文件输出数据的函数。

向fp指向的文件按“输出格式串”中规定，输出到文件中。

块输入输出函数,8、fread（buffer，size，count，fp）9、fwrite（buffer，size，count，fp）参数说明：

buffer是一个指针，对于fread来说是读入数据块的存放地址；对fwrite来说，它是输出数据块的地址。

这里的地址是指数据块的首地址，通常用数据名（或数组指针或结构体数组）来代表。

size是要读/写数据块的字节数count的值是要读/写多少个size字节的数据块fp是一个文件指针，指示已经打开的文件（由fopen（）函数打开的）,文件定位函数,8、rewind（fp）将文件读写位置重新设置在文件头部。

9、fseek（fp，longoffset，intorigin）参数说明：

1）fp是指向要进行读写操作的文件结构指针，该文件已由fopen（）函数打开；2）origin是计算文件指针位置的起始点；文件指针的起始点可以设置在三个不同的位置上，用三个符号常量或数字代表：

SEEK_SET或0代表文件头SEEK_CUR或1代表文件当前位置SEEK_END或2代表文件尾3）offset是距起始点的偏移位置，以字节为单位。

二级考试以往出现的文件操作试题,P102000秋14题在文件中查找并替换P192001春10题从文件读入/向文件输出P29、302001秋11、13题从文件读入P402002春11题从文件读入在每次的上机题中，编写的程序输出内容必须输出到文件中,三、递归问题,P7、P82000秋5题、8题P202001春12题用递归实现排序（冒泡排序）P282001秋8题P492002秋11题P592003春11题,四、字符串操作问题,P92000秋12题从字符串中删除子串P202001春13题插入子串P302001秋13题读子串P392002春10题字符串加密P512002秋15题在字符串中查找子串P592003春12题字符串处理,五、变量作用域与静态变量问题,P62000秋3题变量作用域P272001秋7题静态变量P382002春8题变量作用域与静态变量P472002秋8题变量作用域P572003春8题变量作用域,六、数列或数字处理问题,P92000秋11题P202001春11题P282001秋10题P502002秋13题P602003春13题,七、排序问题,共出现三次排序问题：

使用了1次冒泡排序，2次选择排序P412002春13题,上机考试-改错题,第一：

看函数返回值类型是否正确,03年春06第二个错误03年春01第一个错误02年秋06第一个错误02年秋04第二个错误,第二：

看函数形参与实参的对应关系（个数、顺序、类型是否相同）,03年春05第三个错误03年春03第一个错误03年春04第二个错误03年春02第一个错误03年春01第四个错误02年秋05第四个错误02年秋04第二个错误02年秋03第一个错误02年秋02第一个错误02年秋01第一个错误,等,等,上机考试-改错题,第三：

看是否少头文件,03年春06第一个错误02年秋04第一个错误02年春04第一个错误02年春01第一个错误01年秋03第一个错误01年秋02第一个错误01年秋01第一个错误00年秋03第一个错误00年秋01第一个错误,1、stdio.h当用到文件输入/输出函数及常量值NULL时，如：

fread（）,f