南京师范大学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: 3040”( ) ; 0.01E-20( ) ; 101( ) ; 0x3c0( ) ; -0.5F( ) ; A:合法的字符常量 B:合法的整形常量 C:合法的浮点数常量 D:合法的字符串常量 E:非法表示 请在括号内填入A、 B、 C、 D、 E( 3) 本题程序输出结果是: ( ) #include #degine N 5void 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)存储 物理 逻辑 物理和逻辑 B)顺序 网状 星式 链式C)顺序 二分法 顺序, 也能二分法 随机 D)二分法查找 快速查找 顺序查找 查找E)只适用于链表 只适用于顺序 即适用于顺序, 也适用于链表 即不适用于顺序, 也不适用于链表( 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) 已知R0n-1为整型数组, 试设计实现下列运算的递归算法( 本题15分) 求数组R中的最大整数 求n个整数之和 求n各整数的平均值( 7) 分别写出下图树的先序遍历、 中序遍历和后序遍历的结果。写出中序遍历算法, 算法中root指向二叉树的根。( 本题20分) 南师 硕士研究生招生入学考试初试试卷科目名称: C语言程序设计( 含数据结构) 考生注意: 所有答案必须写在答题纸上, 否则无效, 后果自负。一、 填空题( 每题5舒, 共计20分) (1)每次从无序表中取出一个元素, 把它插入有序表中的适当位置, 此种排序法叫做_排序: 每次从无序表中挑选出一个最小或最大元素, 把它交换到有序表的一端, 此种排序方法叫做_排序;每次直接或经过基准元素间接比较两个元素, 若出现逆序排列时就交换它们的位置, 此种排序方法叫做_排序: 每次使两个相邻的有序表合并成一个有序表的排序方法叫做_排序。快速排序在平均情况下的时间复杂度为_。( 2) 设输入元素为1,2,3, P和A, 输入次序为123PA, 元素经过栈后到达输出序列。当因此元素均到达输出序列后_序列能够作为C语言的标识符(3)己知sizeof(int)=4, 请分析下面代码的运行过程并写出输出结果unsignedintGetSize(inta,char*strl) returnsizeof(a)+Sizeof(strl); intmain()inta1100;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_, 设循环队列用qn来存放, 其头尾指针分别为f和r, 则队满条件是_B_,队列中的元素个数为 C 。A 先进先出 后进先出只进不出 只出不进 Br=f r=(f+1)%nf=(r+1)%nf=r+1%n C r-f r-f+1 (r_f)%n (r-f+n)%n(3)下图是带权的有向图G的邻接表示法。从结点V1出发深度遍历图G所得的结点序列为_A_: 广度遍历图G所得的结点序列为_B_;G的一个拓扑序列是_C_从结点V1到V8的最短路径是_D_, 从结点V1到V8的关键路径是_E_。 (4)下面程序的运行结果是_#includemain()inta=5,b=4,c=3,rl,r2;rl=abc;r2=ab&bC;printf(%d%dn,rl,r2);A)00B)01C)1 0D)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分) 设计一个算法由先序序列和中序序列构造二叉树若先序序列为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( n10)计算并输出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语言程序设计考试试题