南师大2009 年硕士研究生招生入学考试初试试题

C 语言程序设计（含数据结构）

程序设计（共 150 分，请书写整洁，卷面有分）
（1）、设计一个程序，找出 1～200 之间的所有水仙花数。所谓水仙花数是指一个数的各位 数字的立方和恰好等于该数本身。例如：153=13+33+53。（本题 15 分）
（2）、设计一个程序，实现输入一个给定的正整数 N,打印出所有不超过 N 的，其平方为回 文（回文是指字符串两半的字符左右对称，例如 1，22，121，4224 等均是回文）的数。（本 题 15 分）
（3）、编写程序用于统计字符串中最长单词的长度和在字符串中的位置，其中单词全有字母 组成。（本题 20 分）
（4）、编写算法输出从 n 个自然数中取 k 个（k<=n）的所有组合。例如，当 n=5，k=3 时， 你的算法应该输出：543，542，541，532，531，521，432，431，421，321。（本题 20 分）
（5）、试采用递归函数实现将任意位数的整数转换成字符串输出，要求在主函数中输入整数 并调用递归函数实现转换并输出结果，对于负数也能处理。（本题 20 分）
（6）、假设有两个按元素值递增有序排列的线性表 A 和 B，均以单链表作存储结构，请编写 算法将表 A 和 B 归并成一个按元素值非递减有序（允许相同）排列的线性表 C，并要求利用 原表（即表 A 和表 B）的节点空间存放表。（本题 20 分）
（7）、如果一颗 Huffman 树 T 有 n 个叶子结点，那么树 T 有多少个结点，要求给出详细的算 法，然后再写出程序。（本题 20 分）
（8）、对于二叉树 T 的两个结点 N1 和 N2，我们应该选择树 T 结点的前序、中序和后序中哪 两个序列来判定结点 N1 必定是结点 N2 的祖先，并给出判断的方法。要求给出详细的算法， 然后再写出程序。（本题 20 分）

南师大 C 语言（含数据结构）试卷---2008
1．一个数如果恰好等于它的因子之和，这个数就称为“完数”。例如，6 的因子是 1，2，3， 而 6=1+2+3，因此 6 是“完数”。编写程序找出 1000 之内的所有“完数”。
2．采用顺序结构存储串，编写一个函数 Substring(s1,s2)，用于判定 s2 是否是 s1 的字串

3.请用链表编程实现：从键盘读入整数，并按从大到小的顺序输出输入整数中互不相等的那 些整数。
 
4.将一个 5*5 的矩阵中最大的元素放在中心，四个角分别放四个最小的元素（按从左到右， 从上到下的顺序依次从小到大存放），写一个函数实现之。
5.设 A 是有 n 个元素的整型数组（n>=1），试写一个求 A 中 n 个整数的平均值的递归程序。

6.假设由终端输入集合元素，先建立表示集合 X 的静态链表 P1，而后在输入集合 Y 的元素 同时查找 P1 表，若存在和 Y 相同的元素，则从 P1 表中删除之，否则将此元素插入 P1。
7.请写出用二叉树计算英文文献中单词使用频度的算法。 单词的频度=该单词的使用次数 / 文献中单词的总数
8.请写出如图所示的树向二叉树转换的算法，并用中序遍历给出转换后二叉树的节点序列和

树的深度。（图是一棵树，我给描述下吧，自己画出来看吧，呵呵）

A 的孩子：B,C,D    B 的孩子：E,F    C 的孩子：G,H,I    D 的孩子：J
F 的孩子：K,L    H 的孩子：M,N       

南师大 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 分）