南京师范大学GIS专业研究生入学考试题集(C语言)

1、1999年南京师范大学地理信息信息系统C程序设计（含数据结构）二、程序设计1、求下列矩阵的转置，并在屏幕上输出（15分）2、1357926871010842.整数N的阶乘记作N!,他为整数1至N的连续乘积,要求从键盘输入一个正整数N,计算出阶乘的结果，并显示（15分）3、从键盘若干名学生某门课成绩，同几个分数段成绩的人数，程序运行结果如下（20分）Studentsnumber：12inputstudent1sscores:92871006094786552964310089results:100:29099:38089:270,9:16069:2059:2注:口中的为用户输入4、用筛选发求出3

2、”00只见的所有素数，每5个打印一行,并将结果输出到文件result,dal中要求“需用循环赋值初始化数组pn,pLn内存放3200中的奇数2用筛选发筛出pn中的非素数3打印pn并输出到文件中（30分）2.voidJiecheng(intnum)(if(num=0)printf(请输入正整数!);intjc=0;for(inti=1;inum;i+)(jc*=i;printf(%d!=%d,num,jc);2000年南京师范大学地理信息信息系统C程序设计（含数据结构）说明一下二试题可以采用C语言、C+,Pascal.HAS1C或FORTRAN任意一种语言，要求划出算法流程图和写出算法，试卷总分

3、100分）1、有一个函数如下：5X（X1）Y（X）=5X-1（K=X10）3X-1（X二10）编写一个程序，输入X,输出结果.要求：将其显示在屏幕上。用文本格式写入名为HResult,txt,?的文件中口画出流程图0（20分）2、“完数”定义：一个数恰好等于它的因子之和。如6的因子是1、2,3,而6=1+2+3,所以6为完数。编程找出1000以内的所有“完数,要求： 将其显示在屏幕上。 用文本格式写入名为Rcsult.txt”的文件中.画出流程图。（20分）3、数方阵是这样的一个方阵，它的每行、每列和对角线之和均相等，如三阶幻数方阵为以下方阵.编写一个算法，求出3阶方阵的所有形式。要求：将其显

4、示在屏幕上.用文本格式写入名为“Result.txt”的文件中。画出流程图（30分）8163574924、编写一个算法，从键盘输入某年某月某天，计算出该天是星期儿.要求：将其显示在屏幕上。用文本格式写入名为Result.txt的文件中，画出流程图.（30分）（提示：一年12个月，1、3、5、7、8“10、12为大月，每月31天；4、6.9、11为小月，每月30天，2月如是闰年为29天，否则28天。每7天为一周.闰年判别：该年能够被4整除、但不能被100整除，该年为闰年；该年能够被4整除、又能被100整除，如果该年还能被400整除，该年为闰年，否则，该年不为闰年。2001年南京师范大学地理信息信

5、息系统C程序设计（含数据结构）1.设有4行2列的矩阵A和2行3列的矩阵B,求A和B的乘积C.2、输入若干姓名，统计各种姓氏的人数。3、m只蜃子要选大王，选取办法如下:所有猴子按1m编号围坐成一圈，从第号开始按顺序1、2、3、口报数，凡报n号的猴子退出圈外，如此循环报数，直到圈内只剩下一只猴子时，这只缝子就是大王.m和口由键盘输入.4,写出折半查找的递归算法.5,写一个函数，以删除指定的链表结点立6、a和b单项链表的每一个结点中存放个正整数，并在链表中按由小到大的顺序排列，请写一个过程，把b链表合并到b链表中去，合并后的链表仍然有序,2002年南京师范大学地理信息信息系统C程序设计(含数据结构)

6、1、简答题(20分)1)头文件中的ifrulef/definei/enfif干什么用？2)#include和includefilename.!/有什么区别？3)const有什么用途？4)请简述以下两个for循环的优缺点口第一个第二个For(i=0;iN：i+)(If(condition)DoSomething;elseDoOtherthing;If(condition)For(i=0;iN;i+)DoSomething;)Elsefor(i=0:i10(0-1(D)2(2)若已定义：int;并在以后的语句中并未改变P的值，不能表示al的地址的表达式是(A)p+1(B)a+1(C)a+(D)+p

7、(3)若有以下的说明和语句，则在执行for语句后，*(*(pt+l+2)表示的数组元素是(A)t2H0(B)t22(01121(D)t21(4)ttincludestudio,h”mairf?)inta口二1,2,3,4,5,6,7,8,9,10,11,12);intpf+5,q=NULL：*q=*(p+5);printf(*q);输出结果是(A)运行后报错(5)以下不正确的说法是(A)实参可以是常量、变量或表达式(C)实参可以为任意类型二、程序填空(每题5分，共计20分，请将答案写在答题卡的相应位置)(1)函数yanghui能够按以下方式构成一个杨辉三角形t1111 21133114641d

8、efineN11yanghui(intaN)inti,j;for(i=l;iN;i+)66(C)612(D)55(B)形参应与其对应的实参类型一致形参可以是常量、变量或表达式al=l;a=l;for(A;iN;i+)for(j=2;j+)aj=C+ai-lj;)(2)条件2x=0;-i)(d=c;printf(=0&m=0)|(n=0&m=n)return(1);else(if(nm&n=0&m=0)return(comb(n-l,m)+comb(n-l,m-1);else(printf(n,m值不正确n);return(-1);)一、填空题（每题 5 分，共

9、20 分）（1）数据结构是数据的（）和（），以及它们之间的相互联系，并对这种结构定义相应的（）,设计出相应的（），而确保经过这些运算后所得到的新结构是（）结构类型。（2）“43040（）;0.01E-20（）;101（）;0 x3c0（）;-0.5F（）;A:合法的字符常量 B:合法的整形常量 C:合法的浮点数常量D:合法的字符串常量 E:非法表示请在括号内填入 A、B、C、D、E（3）本题程序输出结果是：（）#includestdio.h#degineN5voidmain（void）inti;doublex,s=0;for（i=1,x=1;i=N;i+,x+=0.5）s+=1/x;print

10、f（s=%.2f,s）;（4）根据线性表的链式存储结构形式，每个结点所含指针的个数，链表可分为（）和（）；而根据指针的联接方式，链表又可分为（）和（）；栈的特点是（），队列的特点是（）。二、选择题（每题 5 分，共 20 分）（1）在数据结构中，与所有的计算机无关的数据叫（A）结构；链表是一种采用（B）存储结构存储的线性表；链表适用于（C）查找；在链表中进行（D）操作的效率比在顺序存储结构中进行（D）操作效率高；二分法查找（E）存储结构。人）1存储2物理3逻辑4物理和逻辑8）1顺序2网状3星式4链式31顺序2二分法3顺序，也能二分法4随机D）1二分法查找2快速查找3顺序查找4查找E)只适用于链

11、表只适用于顺序即适用于顺序,也适用于链表即不适用于顺序，也不适用于链表(2)若一个栈的输入序列是 1、2、3、n,输出序列的第一个元素是 n,则第 i 个输出元素是()A)n-iB)n-i+1C)iD)n+i-1(3)若用 S=NjnuGisc,其子用的数目是()A)8B)37C)36D)9(4)下列程序段的运行结构是()intn=0;while(n+=2);printf(%d,n);A)2B)3C)4D)有语法错误三、程序设计(共计 110 分，请书写整洁，卷面有分)(1)利用用的基本运算，编写一个算法删除用 S1 中所有 S2 子用。(本题 15 分)(2)编写一程序，判断一个字符串是不是

12、回文数”。所谓回文数是从左至右或从右至左读起来都是一样的字符串。(本题 15 分)(3)设计一个统计选票的算法，输出每个候选人的得票结果(假定采用单链表存放选票，候选人编号依次为 1,2,3,N,且每张选票选且只选一人)(本题 15 分)(4)有几个人围成一圈，顺序排号。从第一个开始报数，凡报到 4 的人退出圈子，问最后留下的是几号。(本题 15 分)(5)假设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号，编写一个算法判断其中的括号是否匹配。(本题 15 分)(6)已知 R0n-1为整型数组，试设计实现下列运算的递归算法(本题 15 分)求数组 R 中的最大整数求 n 个整数之和求

13、 n 各整数的平均值(7)分别写出下图树的先序遍历、中序遍历和后序遍历的结果。写出中序遍历算法，算法中 root 指向二叉树的根。(本题 20 分)南师 2005 年硕士研究生招生入学考试初试试卷科目名称：C语言程序设计(含数据结构)考生注意：所有答案必须写在答题纸上，否则无效，后果自负。一、填空题(每题 5 舒，共计 20 分)(1)每次从无序表中取出一个元素，把它插入有序表中的适当位置，此种排序法叫做排序：每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做排序；每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做排序：每次

14、使两个相邻的有序表合并成一个有序表的排序方法叫做排序。快速排序在平均情况下的时间复杂度为。(2)设输入元素为 1,2,3,P 和 A,输入次序为 123PA,元素经过栈后到达输出序列。当所以元素均到达输出序列后序列可以作为 C 语言的标识符.己知 sizeof(int)=4，请分析下面代码的运行过程并写出输出结果unsignedintGetSize(inta,char*strl)(returnsizeof(a)+Sizeof(strl);intmain()(inta1100;char*strl=Welcome!;printf(%d,_%d,_,sizeof(a1),sizeof(strl);p

15、rintf(%d.,GetSize(a1,strl);return0;输出：。(4)T 是正则二叉树，即只有度为 2 和度为。的结点，它具有 6 个叶结点，那么树 T 的高度最多可以是;最小可以是;机丁的分支结点数是。如果 T 又是 Huffman 最优二叉树且各叶结点的权分别是 1、2、3、4、5、6,则最优二叉树 T 的非叶结点的权之和是;权为 1 的叶结点所处层次是。【注：树的根结点高度为 O二、选择题【每题 5 分.共计 20 分】(1)下列说法中错误的是。A)数据结构是指相互之间存在-种或多种关系的数据元素的全体，B)数据的逻辑结构与数据元索本身的内容和形式无关。C)在索引顺序结构上

16、实施分块查找，在等概率情况下，其平均查找长度不仅与子表个数有关，而且与每一个子表中的记录个数有关。D)每种数据结构都应具备三种基本运算：插入，删除，搜索。2)队列的特点是_A_,设循环队列用 qn来存放，其头尾指针分别为 f 和 r,则队满条件是_B_,队列中的元素个数为 C。A先进先出后进先出只进不出只出不进Br=fr=(f+1)%nf=(r+1)%nf=r+1%nCr-fr-f+1(r_f)%n(r-f+n)%n(3)下图是带权的有向图 G 的邻接表示法。 从结点 V1 出发深度遍历图 G 所得的结点序列为_A_:广度遍历图 G 所得的结点序列为_B_;G 的一个拓扑序列是_C_从结点 V

17、1 到 V8 的最短路径是_D_,从结点 V1 到 V8 的关键路径是E。AC：:VP.:V5，V九VBa：V4.6；V5r声；V7s.yP*5$,；,V?,V4，V曲V，0V7.VSjjV；,V、V4，V6，V7,V3-V5-V8V!,V2rU九V&V4,V5，76、V7VI，VLV3,V8tV4,V5,V7,V6VrV2,V3.V8，V5.V7.V4-V6D、E（V!.V2，事*V5fVJ.VS,（VLV&V5;V3-UKjV6.V.笃沿.1V8）（4）下面程序的运行结果是#includemain（）inta=5,b=4,c=3,rl,r2;rl=abc;r2=ab&

18、;bC;printf（%d%dn,rl,r2）;A）00B）01C）10D）11E）有语法错误三、程序设计（共计 1l0 分，请书写整洁，卷面有分）设 A 和 B 是两个顺序表，其元素按从小到大的顺序排列。编写一个将 A 和 B 中相同元素组成一个新的从大到小的有序顺序表 C 的算法，并分析算法的时间复杂度。（本题 15 分）2）若线性表用单链表（带表头结点）作为存储结构，写出其就地逆置算法。（本题 15 分）设定串采用顺序存储结构，求串 s1 和 s2 的一个最长公共子串的长度，并指出该最长公共子串分别在 sl 和 s2 中的起始位置。（水题 15 分）（4）设单链表中存放 n 个字符，试设

19、计一个算法，使用栈判断该字符串是否中心对称，如 xyzzyx 即为中心对称字符串。（小题 15 分）编写算法找出从自然数 1,2,n 中任取 r 个数的所有组合。（本题 15 分）（6）设计一个计算二叉树各结点的子孙个数的的算法。（本题 15 分）已知一棵二叉树的先序序列和中序序列，则可唯一地确定一棵二叉树。（本题 20 分）设计一个算法由先序序列和中序序列构造二叉树若先序序列为 abcdefg.中序序列为 cbaefdg,画图构造对应的二叉树，并写出该二叉树的后序序列。1.设计一个程序，将任何输入的字符串中的最长单词输出，并计算出其在字符串中的位置。(15 分)2,试采用递归函数实现将任意位

20、数的整数转换为字符串输出，要求在主函数中输入整数并调用递归函数实现转换并输出结果，对于负数也能处理(15 分)3,以顺序存储结构表示用，设计算法，求用 S 中出现的第一个最长重复子用及其位置并分析算法的时间复杂度。(20 分)4,利用 2 个栈 S1 和 S2 模拟一个队列，写出入队和出队的算法(可用栈的基本操作)(20 分)5 .编写一算法，以完成在带头节点单链表 M 中第 n 个位置前插入元素 X 的操作。(20 分)6 .编写一个利用二分法查找某值 X 是否存在于一组已知数据 X1、X2、X3、Xn 中的程序。(20 分)7 .试设计一个算法解决地图着色判断问题。 设一地图有 n 个区域

21、， 用不多于 4 种颜色对这些区域进行着色，着色应满足的要求是相邻的区域颜色不可以相同。 你的算法以一种着色方案(即哪一个区域着什么颜色)为输入，算法对该着色方案进行考察，若满足着色要求，则输出true,否则则输出 false。(20 分)(1)用 C 语言描述你为解决问题而设计的数据结构(逻辑结构，存储结构)。数据结构的设计应考虑对问题的清楚描述和算法的效率；(2)用 C 语言写出你的算法。算法应简洁、高效。对算法中的参数、变量、语句做必要的注释，以增加可读性；(3)简单分析你的算法的空间开销和时间开销。8 .已知一棵树的边的结合为(I,M),(I,N),(E,I),(B,E),(B,D),

22、(C,B),(G,J),(G,K),(A,G),(A,F),(H,L),(A,H),(C,A),试画出这棵树，并回答下列问题：(20 分)(1)哪个是根节点？(2)哪些是叶子节点？(3)树的深度是多少？(4)写出该树的前序遍历序列(1)设 S 为一个长度为 n 的字符串，其中用的字符各不相同，写出具体程序并计算出 S 中互异的非平凡子用，非空且不同于 S 本身的个数。(本题 15 分)。(2)编写一个程序，对输入的任意正整数 n,打印出集合0,1,2,3,.,n-1的所有子集。(本题 15 分)。(3)已知非空线性链表第一个节点由 list 指出，请写一个算法交换 P 所指的节点与其下一个节点

23、在链表中白位置(设 P 指向的不是链表最后那个结点)。(本题 20 分)。(4)对给定的 n(n010)计算并输出 K!(K=1,2,3,.,n)的全部有效数字。(本题 20 分)。(5)用递归算法和栈实现 m 个相异元素构成的有序序列的二分查找，并计算出该栈的最小容量。(本题 20分)。(6)已知平面上(直角坐标系)的 m 个点，请编写一个函数，求同一条直线所能通过的最多点数。(本题 20 分)。(7)用程序设计有 n 个叶子结点的 Huffman 树的结点个数。(本题 20 分)。(8)依次输入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二

24、*排序树。(本题 20 分)。试画出生成之后的二*排序树。若该二*排序树作中序编历，试写出编历序列。假设每个元素的查找概率相等，试计算该二*排序树的平均查找长度。南师大C语言（含数据结构）试卷一2008L一个数如果恰好等于它的因子之和， 这个数就称为“完数二例如，6的因子是1,2,3,而6=1+2+3,因此6是“完数:编写程序找出1000之内的所有“完数二2.采用顺序结构存储串，编写一个函数Substrin虱sl,s2）,用于判定s2是否是的字串3,请用链表编程实现：从键盘读入整数，并按从大到小的顺序输出输入整数中互不相等的那些整数。4.将一个5*5的矩阵中最大的元素放在中心， 四个角分别放四个最小的元素 （按从左到右,从上到下的顺序依次从小到大存放），写一个函数实现之。5.设A是有n个元素的整型数组5二1）,试写一个求A中n个整数的平均值的递归程序口6 .假设由终端输入集合元素， 先建立表示集合X的静态链表P1,而后在输入集合Y的元素同时查找P1表，若存在和丫相同的元素，则从PL表中删除之，否则将此元素插入P1。请写出用二叉树计算英文文献中单词使用频度的算法。单词的频度=该单词的使用次数/文献中单词的总数&请写出如