南京师范大学GIS专业研究生入学考试题集C语言样本.doc

《C语言程序设计》考试试题( 含数据结构)
南师1999年GIS专业研究生入学《C语言程序设计》考试试题( 含数据结构)

2.
void Jiecheng(int num)
{
if(num <=0)
printf("请输入正整数! ");
int jc = 0;
for(int i =1;i< num; i++)
{
jc *= i;
}
printf("%d!=%d",num,jc);
}

南师 GIS专业研究生入学《C语言程序设计》考试试题( 含数据结构)

南师 GIS专业研究生入学《C语言程序设计》考试试题( 含数据结构)

南师 GIS专业研究生入学《C语言程序设计》考试试题( 含数据结构)

南师 GIS专业研究生入学《C语言程序设计》考试试题( 含数据结构)

南师 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 ",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分)

南师 硕士研究生招生入学考试初试试卷
科目名称: 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="Welcome!";
    printf("%d,_%d,_",sizeof(a1), sizeof(strl));
    printf("%d.",GetSize(a1, strl));
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___。

(4)下面程序的运行结果是____
#include
main()
{ int a=5,  b=4,c=3,rl,r2;
rl=a> b>c;
r2=a>b&&b>C;
printf ("%d    %d\n",rl,r2);
}
A)0 0    B)0 1    C) 1 0  D)1 1   E)有语法错误
三、 程序设计( 共计1l0分, 请书写整洁, 卷面有分)
(1)  设A和B是两个顺序表, 其元素按从小到大的顺序排列。编写一个将A和B中相
同元素组成一个新的从大到小的有序顺序表C的算法, 并分析算法的时间复杂度。
(本题15分)
2) 若线性表用单链表(带表头结点)作为存储结构, 写出其就地逆置算法。(本题15分)
(3)设定串采用顺序存储结构, 求串s1和 s2的一个最长公共子串的长度, 并指出该
最长公共子串分别在sl和s2中的起始位置。( 水题15分)
(4)设单链表中存放 n个字符, 试设计一个算法, 使用栈判断该字符串是否中心对称,
如xyzzyx即为中心对称字符串。( 小题15分)
(5) 编写算法找出从自然数1,2, …．n中任取r个数的所有组合。( 本题15分)
(6) 设计一个计算二叉树各结点的子孙个数的的算法。( 本题15分)
(7) 已知一棵二叉树的先序序列和中序序列, 则可唯一地确定一棵二叉树。( 本题20分)
<1>设计一个算法由先序序列和中序序列构造二叉树
<2>若先序序列为abcdefg．中序序列为cbaefdg, 画图构造对应的二叉树, 并写出该
二叉树的后序序列。

南师 GIS专业研究生入学《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 ) 写出该树的前序遍历序列    

南师 GIS专业研究生入学《C语言程序设计》考试试题

( 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分) 。
①试画出生成之后的二*排序树。
②若该二*排序树作中序编历, 试写出编历序列。
③假设每个元素的查找概率相等, 试计算该二*排序树的平均查找长度。
南师 GIS专业研究生入学《C语言程序设计》考试试题

南范 GIS专业研究生入学《C语言程序设计》考试试题