南师地理信息系统专业01方向真题C语言

南师大考研

南师大C语言（含数据结构）试卷---2007

（1）设S为一个长度为n的字符串，其中串的字符各不相同，写出具体程序并计算出S中互异的非平凡子串，非空且不同于S本身的个数。（本题15分）。

（2）编写一个程序，对输入的任意正整数n，打印出集合{0，1，2，3，...，n-1}的所有子集。（本题15分）。

（3）已知非空线性链表第一个节点由list指出，请写一个算法交换P所指的节点与其下一个节点在链表中的位置(设P指向的不是链表最后那个结点）。（本题20分）。

（4）对给定的n（n≤10)计算并输出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）中的元素，生成一棵二叉排序树。（本题20分）。

①试画出生成之后的二叉排序树。

②若该二叉排序树作中序编历，试写出编历序列。

③假设每个元素的查找概率相等，试计算该二叉排序树的平均查找长度

南师大2006 C语言（含数据结构）

1. 设计一个程序，将任何输入的字符串中的最长单词输出，并计算出其在字符串中的位置。（15分）

2. 试采用递归函数实现将任意位数的整数转换为字符串输出，要求在主函数中输入整数并调用递归函数实现转换并输出结果，对于负数也能处理（15分）

3. 以顺序存储结构表示串，设计算法，求串S中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。（20分）

4. 利用2个栈S1和S2模拟一个队列，写出入队和出队的算法（可用栈的基本操作）（20分）

5．编写一算法，以完成在带头节点单链表M中第n个位置前插入元素X的操作。（20分）

6．编写一个利用二分法查找某值X是否存在于一组已知数据X1、X2、X3、 Xn中的程序。（20分）

7．试设计一个算法解决地图着色判断问题。设一地图有n个区域，用不多于4种颜色对这些区域进行着色，着色应满足的要求是相邻的区域颜色不可以相同。你的算法以一种着色方案（即哪一个区域着什么颜色）为输入，算法对该着色方案进行考察，若满足着色要求，则输出true,否则则输出false。（20分）

（1）用C语言描述你为解决问题而设计的数据结构（逻辑结构，存储结构）。数据结构的设计应考虑对问题的清楚描述和算法的效率；

（2）用C语言写出你的算法。算法应简洁、高效。对算法中的参数、变量、语句做必要的注释，以增加可读性；

（3）简单分析你的算法的空间开销和时间开销。

8．已知一棵树的边的结合为

{(I,M),(I,N),(E,I),(B,E),(B,D),(C,B),(G,J),(G,K),(A,G),(A,F),(H,L),(A,H),(C,A)},试画出这棵树，并回答下列问题：（20分）

南师大考研

（1）哪个是根节点？

（2）哪些是叶子节点？

（3）树的深度是多少？

（4）写出该树的前序遍历序列

2004年南京师范大学地理信息信息系统 C程序设计（含数据结构）

一、填空题（每题5分，共20分）

（1）数据结构是数据的（ ）和（ ），以及它们之间的相互联系，并对这种结构定义相应的（ ），设计出相应的（ ），而确保经过这些运算后所得到的新结构是（ ）结构类型。

（2）“4：30'40''”（ ）；0.01E-20（ ）；‘\101’（ ）；0x3c0（ ）；-0.5F（ ）；

A:合法的字符常量 B:合法的整形常量 C:合法的浮点数常量

D:合法的字符串常量 E:非法表示 请在括号内填入A、B、C、D、E

（3）本题程序输出结果是：（ ）

#include<stdio.h>

#degine N 5

void main(void)

{

int i;

double x, s=0;

for(i=1,x=1;i<=N;i++,x+=0.5)

s+=1/x;

printf("s=%.2f\n",s);

}

（4）根据线性表的链式存储结构形式，每个结点所含指针的个数，链表可分为（ ）和（ ）；而根据指针的联接方式，链表又可分为（ ）和（ ）；栈的特点是（ ），队列的特点是

（ ）。

二、选择题（每题5分，共20分）

（1）在数据结构中，与所有的计算机无关的数据叫（A）结构；链表是一种采用（B）存储结构存储的线性表；链表适用于（C）查找；在链表中进行（D）操作的效率比在顺序存储结构中进行（D）操作效率高；二分法查找（E）存储结构。

A)<1>存储 <2>物理 <3>逻辑 <4>物理和逻辑

B)<1>顺序 <2>网状 <3>星式 <4>链式

C)<1>顺序 <2>二分法 <3>顺序，也能二分法 <4>随机

D)<1>二分法查找 <2>快速查找 <3>顺序查找 <4>查找

E)<1>只适用于链表 <2>只适用于顺序 <3>即适用于顺序，也适用于链

表 <4>即不适用于顺序，也不适用于链表

（2）若一个栈的输入序列是1、2、3、 、n,输出序列的第一个元素是n，则第i个输出元素是（ ）

A) n-i B) n-i+1 C) i D) n+i-1

（3）若串S='NjnuGisc',其子串的数目是（ ）

南师大考研

A) 8 B) 37 C) 36 D) 9

（4）下列程序段的运行结构是（ ）

int n=0;

while(n++<=2);

printf("%d",n);

A) 2 B) 3 C) 4 D)有语法错误

三、 程序设计（共计110分，请书写整洁，卷面有分）

（1） 利用串的基本运算，编写一个算法删除串S1中所有S2子串。（本题15分）

（2） 编写一程序，判断一个字符串是不是“回文数”。所谓回文数是从左至右或从右至左读起来都是一样的字符串。（本题15分）

（3） 设计一个统计选票的算法，输出每个候选人的得票结果（假定采用单链表存放选票，候选人编号依次为1，2，3， N,且每张选票选且只选一人）（本题15分）

（4） 有几个人围成一圈，顺序排号。从第一个开始报数，凡报到4的人退出圈子，问最后留下的是几号。（本题15分）

（5） 假设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号，编写一个 算法判断其中的括号是否匹配。（本题15分）

（6） 已知R[0 n-1]为整型数组，试设计实现下列运算的递归算法（本题15分）

<1> 求数组R中的最大整数

<2> 求n个整数之和

<3> 求n各整数的平均值

（7） 分别写出下图树的先序遍历、中序遍历和后序遍历的结果。写出中序遍历算法，算法中root指向二叉树的根。（本题20分）

2003年南京师范大学地理信息信息系统 C程序设计（含数据结构）

一、 选择题（每题4分，共20分）

（1） 设有如下定义：int x=1,y=1;则语句printf(“d%/n”,(x--&++y));的输出结果是 （A）1 (B)0 (C)-1 (D)2

（2） 若已定义：int a[9],*p=a;并在以后的语句中并未改变P的值，不能表示a[1]的地址的表达式是 (A)p+1 (B)a+1 (C)a++ (D)++p

（3） 若有以下的说明和语句，则在执行for语句后，*(*(pt+1+2))表示的数组元素是

(A)t[2][0] (B)t[2][2] (C)t[1][2] (D)t[2][1]

（4） #include“studio.h”

main()

{

int a[]={1,2,3,4,5,6,7,8,9,10,11,12};

int p=a+5,q=NULL;

*q=*(p+5);

printf(“%d%d\n”,*p,*q);

}

输出结果是 (A)运行后报错 (B)6 6 (C)6 12 (D)5 5

（5）以下不正确的说法是

(A)实参可以是常量、变量或表达式 (B)形参应与其对应的实参类型一致

(C)实参可以为任意类型 (D)形参可以是常量、变量或表达式

南师大考研

二、 程序填空（每题5分，共计20分，请将答案写在答题卡的相应位置）

（1）函数yanghui能够按以下方式构成一个杨辉三角形：

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

#define N 11

yanghui(int a[][N])

{

int i,j;

for(i=1;i<N;i++)

{a[1]=1;a=1;}

for([A];i<N;i++)

for(j=2;;j++)

a[j]=[C]+a[i-1][j];

}

（2） 条件“2<x<3或x<-10”的C语言表达式是[A]

（3） 以下程序的功能是判断输入的年份是不是闰年

main()

{

int y,f;

scanf(“%d”,&y);

if(y%400==0)f=1;

else if([A]) f=1;

else ;

if(f) printf(“%d is”,y);

else printf(“%d is not”,y);

printf(“a leap year\n”);

}

（4） 以下程序可以把从键盘上输入的十进制数（long型）以二到十六进制形式输出，请填空。

（5） #include“studio.h”

main()

{

char b[16]={'0'、'1'、'2'、'3'、'4'、'5'、'6'、'7'、'8'、'9'、'A'、'B'、'C'、'D'、'E'、'F'};

int c[64],d,i=0,base;

long n;

printf(“enter a number:\n”);

scanf(“%1d”,&n);

printf(“enter new base:\n”);

南师大考研

scanf(“%d”,&base);

do{c=[A];

i++;n=n/base;

}while(n!=0);

printf(“transmite new base:\n”);

for(--i;i>=0;--i)

{

d=c;

printf(“%c”,b);

}

}

三、 程序设计题（卷面有分）

（1） 从键盘输入10个数，输出其中最大数和最小数。（本题10分）

（2） 求300以内的双素数，并输出，判断一个数m是否为素数的方法如下：让m被2到 除，当且仅当m不能被2~ 之间的任何一个数所整除，则m为素数，而当m为素数，同时m+2也为素数，则m与m+2就是双素数。（本题15分）

（3） 编写一个子程序能将主程序传过来的数组按行分别进行从小到大的排序，再编写一个二分法查找子程序，判定主函数传过来的待查数是否在已排序的数组中，若查找到则返回它在数组中的位置（可以在多个位置出现），否则返回-1。（本题15分）

（4） 利用递归方法找出从自然数1，2， n中任取r个数的所有组合，并画出程序N-S图，例如n=5，r=3，所有组合为：（本题20分）

5 4 3 5 2 1

5 4 2 4 3 2

5 4 1 4 3 1

5 3 2 4 2 1

5 3 1 3 2 1

（5） 利用单项循环链表和顺序存储结构设计一个算法解决约瑟夫(JOSEHUS)问题。设有N个人围坐一圈，现从某个人开始报数，数到M的人出现，接着从出列的下一个人开始重新报数，数到M的人又出现，如此下去知道所有人都出列为止。试求出他们的出列次序。（本题20分）

（6） 编号为A,B,C,D的四辆列车，顺序开进一个栈式结构的站台。问开出车站的顺序有多少种可能？请具体写出来。

（7） 试将下面的树转换成二叉树，并写出二叉树前序遍历后的结点序列。（本题15分）

2002年南京师范大学地理信息信息系统 C程序设计（含数据结构）

1、简答题（20分）

1)头文件中的ifndef/define/enfif干什么用？

2)#include <filename.h> 和 #include "filename.h" 有什么区别？

3)const 有什么用途？

4)请简述以下两个for 循环的优缺点。

第一个 第二个

For(i=0;i<N;i++)

{

南师大考研

If (condition)

DoSomething;

else

DoOtherthing;

} If(condition)

{ For(i=0;i<N;i++)

DoSomething;

}

Else

{ for(i=0;i<N;i++)

DoOtherthing;

}

优点： 优点：

缺点： 优点：

2、写一个程序（1）实现m×n矩阵的转置；（2）矩阵A（m×n）和矩阵B(n×1)的相乘。

3、利用格利高利公式求Л. Л/4=1-1/3=1/5-1/7+ 直到最后一项的值小于0.000001为 止。（“Л”表示圆周率）

4、 用一个程序实现表达式括号匹配的合法性检查；对于输入一个字符串，检查其括号的使用是否合法。表达式中允许出现圆括号（）、[]、{} ，但这些括号的使用必须匹配。假设输入的表达式两端加上#，即以#开始，当再次遇到#表示字符串输入结束。

5、编写函数stringReverse,取包含字符串的字符数组为参数，逆向打印字符串且不返回任何内容。函数在接收到#终止符时停止处理并返回。

6、编写递归程序recursiveMinimum，取数组和长度为参数并返回数组中最小的元素，当函数在接收但长度为1的数组时停止处理并返回。

7、写一个程序，读入全班学生的学号、姓名、成绩，用冒泡法对学生的成绩由小到大排序，将排序的好的学生纪录输出。

2001年南京师范大学地理信息信息系统 C程序设计（含数据结构）

1、设有4行2列的矩阵A和2行3列的矩阵B，求A和B的乘积C.

2、输入若干姓名，统计各种姓氏的人数。

3、m只猴子要选大王，选取办法如下：所有猴子按1 m编号围坐成一圈，从第一号开始按顺序1、2、3、 、n报数，凡报n号的猴子退出圈外，如此循环报数，直到圈内只剩下一只猴子时，这只猴子就是大王。m和n由键盘输入。

4、写出折半查找的递归算法。

5、写一个函数，以删除指定的链表结点。

6、a和b单项链表的每一个结点中存放一个正整数，并在链表中按由小到大的顺序排列，请写一个过程，把b链表合并到b链表中去，合并后的链表仍然有序。

2000年南京师范大学地理信息信息系统 C程序设计（含数据结构）

（说明一下：试题可以采用C语言、C++、Pascal、BASIC或FORTRAN任意一种语言，要求划出算法流程图和写出算法，试卷总分100分）

1、 有一个函数如下：

5X (X<1)

Y(X)= 5X-1 (1<=X<10)

3X-1 (X>=10)

南师大考研

编写一个程序，输入X，输出结果。要求：①将其显示在屏幕上。②用文本格式写入名为“Result.txt”的文件中。③画出流程图。（20分）

2、“完数”定义：一个数恰好等于它的因子之和。如6的因子是1、2、3，而6=1+2+3，所以6为完数。编程找出1000以内的所有“完数”。要求：①将其显示在屏幕上。②用文本格式写入名为“Result.txt”的文件中。③画出流程图。（20分）

3、 数方阵是这样的一个方阵，它的每行、每列和对角线之和均相等，如三阶幻数方阵 为以下方阵。编写一个算法，求出3阶方阵的所有形式。要求：①将其显示在屏幕上。②用文本格式写入名为“Result.txt”的文件中。③画出流程图。（30分）

8 1 6

3 5 7

4 9 2

4、编写一个算法，从键盘输入某年某月某天，计算出该天是星期几。要求：①将其显示在屏幕上。②用文本格式写入名为“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整除，该年为闰年，否则，该年不为闰年。

1999年南京师范大学地理信息信息系统 C程序设计（含数据结构）

二、程序设计

1、 求下列矩阵的转置，并在屏幕上输出（15分）

2、 1 3 5 7 92 6 8 7 10 1 0 8 42。整数N的阶乘记作N!，他为整数1至N的连续乘积，要求从键盘输入一个正整数N，计算出阶乘的结果，并显示（15分）

3、 从键盘若干名学生某门课成绩，同几个分数段成绩的人数，程序运行结果如下（20分）Student's number=[12]input student's scores:[92 87 100 60 94 78 65 52 96 43 100 89]results:100 : 290~99: 380~89: 270~79: 160~69: 20 ~59: 2注：[]中的为用户输入

4、 用筛选发求出3~200只见的所有素数，每5个打印一行，并将结果输出到文件result.dat中要求：1需用循环赋值初始化数组p[n]，p[n]内存放3~200中的奇数2用筛选发筛出p[n]中的非素数3打印p[n]并输出到文件中（30分）

本文来源：https://www.bwwdw.com/article/gwc1.html