南京师范大学2004年攻读硕士研究生入学考试试题
考试专业：GIS
考试科目：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
#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分) | 
