发布时间 : 星期三 文章南京师范大学GIS专业历年真题汇总(C语言)更新完毕开始阅读
南师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
void main(void) { int i;
double x, s=0;
for(i=1,x=1;i<=N;i++,x+=0.5) s+=1/x;
printf(\}
（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(\
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分）
南师2005年硕士研究生招生入学考试初试试卷
科目名称：C语言程序设计（含数据结构）
考生注意：所有答案必须写在答题纸上，否则无效，后果自负。
一、填空题（每题5舒，共计20分）
(1) 每次从无序表中取出一个元素，把它插入有序表中的适当位置，此种排序法叫做____排序：每次从无序表中
挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做____排序;每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做_______排序：每次使两个相邻的有序表合并成一个有序表的排序方法叫做________排序。快速排序在平均情况下的时间复杂度为____。 （2）设输入元素为1,2,3，P和A，输入次序为123PA，元素经过栈后到达输出序列。当所以元素均到达输出序列
后_____________________________________序列可以作为C语言的标识符． (3) 己知sizeof(int)==4，请分析下面代码的运行过程并写出输出结果 unsigned int GetSize(int a[],char *strl) {
return sizeof(a) + Sizeof(strl); }
int main() {
int a1[100];
char * strl=\
printf(\ printf(\return 0;
}
输出：________________________。
(4) T是正则二叉树，即只有度为2和度为O的结点，它具有6个叶结点，那么树T的高度最多可以是____；
最小可以是_____;树T的分支结点数是_____。如果T又是Huffman最优二叉树且各叶结点的权分别是
1、2、3、4、5、6，则最优二叉树T的非叶结点的权之和是_____；权为1的叶结点所处层次是____。 【注：树的根结点高度为O】
二、选择题【每题5分．共计20分】
(1) 下列说法中错误的是____。
A)数据结构是指相互之间存在-种或多种关系的数据元素的全体， B)数据的逻辑结构与数据元索本身的内容和形式无关。
C)在索引顺序结构上实施分块查找，在等概率情况下，其平均查找长度不仅与子表 个数有关，而且与每一个子表中的记录个数有关。
D)每种数据结构都应具备三种基本运算：插入，删除，搜索。
2)队列的特点是__A__，设循环队列用q[n]来存放，其头尾指针分别为f和r，则队满 条件是__B__,队列中的元素个数为 C 。
A <1>先进先出 <2>后进先出 <3>只进不出 <4>只出不进 B <1>r=f <2>r=(f+1)%n <3>f=(r+1)%n <4>f=r+1%n C <1>r-f <2>r-f+1 <3>(r_f)%n <4>(r-f+n)%n
(3) 下图是带权的有向图G的邻接表示法。从结点V1出发深度遍历图G所得的结点 序列为__A__：广度遍历图G所得的结点序列为__B__;G的一个拓扑序列是__C__ 从结点V1到V8的最短路径是__D__，从结点V1到V8的关键路径是___E___。