南师大
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分）
相关评论
