《南师大地图学与地理信息系统C语言程序设计考研真题(2003-2012)》由会员分享，可在线阅读，更多相关《南师大地图学与地理信息系统C语言程序设计考研真题(2003-2012)（7页珍藏版）》请在金锄头文库上搜索。
1、GISGIS 论坛论坛 1 南师大南师大 GIS 考研考研 2012 年年 C 语言程序设计语言程序设计(含数据结构含数据结构)考研真题考研真题 1、编写程序实现对一循环队列中所有元素的逆转。 （15 分） 2、素数就是仅能被 1 和它自身整除的整数。判定一个整数 N 是否为素数就是要判定整数 N 能否被除 1 和它自身之外的任意整数整除，若都不能整除，则 N 为素数。编写程序，计算 100 以内的所有素数。 （15 分） 3、已知 strcmp 的函数原型。该函数的功能为比较字符串 s1 和 s2，当 s10；编写程序实现函数 strcmp，不允许调用 C 语言 库函数。 （15 分） 4、
2、已知线性表中的元素以值递增有序排列，并以单链表作存储结构。编写程序删除表中所 有值大于 mink 且小于 maxk 的元素，同时释放被删除的结点空间。 （15 分） 5、编写程序，判断多边形是否在圆内部。 （20 分） 6、编写程序根据二叉树的前序序列和中序序列建立该二叉树。假设二叉树的前序序列存放 在一维数组 pren中，中序序列存放在一维数组 pinn中，n 为二叉树的结点个数。 （20 分） 7、已知数据序列为（12，5，9，20，6，31，24） ，对该数据序列进行排序，分别写出冒泡 排序、快速排序、选择排序、堆排序、基数排序这五种排序算法和各趟排序结果。 （25 分） 8、已知一有向
3、图的邻接矩阵如下图所示，需在其中一个结点建立医院，要求该结点距其他 各个结点的最长往返路径最短， 相同条件下总的往返路程越短越好， 医院应当选址何处？请 给出分析过程与具体程序。 （25 分） 0 13 4 13 0 15 5 0 12 4 12 0 6 3 0 南师大南师大 GIS 考研考研 2011 年年 C 语言程序设计语言程序设计(含数据结构含数据结构)考研真题考研真题 1、编写一个程序，求用户输入的开始时间到终止时间之间相距的天数。 （本题 15 分） 2、编写一个程序，利用递归法实现将用户输入的字符串逆序排列。 （本题 15 分） 3、找出所有 200 以内（含 200）满足 I，
4、I+4，I+10 都是素数的整数 I（I+10 也在 200 以内） GISGIS 论坛论坛 2 的个数以及这些数之和 sum。并把所有这些数、个数和 sum 按文本文件输出到文件 out.dat 中。 （本题 20 分） 4、编写程序，判断两线段是否相交。 （本题 20 分） 5、 假设以带头节点的循环链表表示队列， 并只设一个指针指向对尾元素节点 （不设头指针） ， 编写相应的队列初始化、入队列和出队列算法。 （本题 20 分） 6、假设有两个按元素值递增有序排列的线性表 A 和 B，均以单链表作存储结构，请编写算 法将表 A 和表 B 归并成一个按元素值非递减有序（允许值相同）排列的线性
5、表 C，并要求利 用原表（即表 A 和表 B）的结点空间存放表。 （本题 20 分） 7、给定一棵树用二叉链表表示的二叉树，其中的指针 t 指向根结点，试写出从根开始，按 层次遍历二叉树的算法，周层的结点按从左到右的次序访问。 （本题 20 分） 8、若 S 是 n 个元素的集合，则 S 的幂集 P(S)定义为 S 的所有子集的集合。例如， S=(a,b,c),P(S)=(),(a),(b),(c),(a,b),(a,c),(b,c),(a,b,c)。 给定 S， 写一递归算法求 P(S)。（本题 20 分） 南师大南师大 GIS 考研考研 2010 年年 C 语言程序设计语言程序设计(含数据
6、结构含数据结构)考研真题考研真题 1、给出年、月、日，计算该日是该年的第几天。 （本题 15 分） 2、有几个学生，每个学生考 m 门课，要求编一函数，能检查 n 个学生有无不及格的课程， 如果有某一学生有一门或一门以上课程不及格，就输出该学生的学号（学号从 0 开始）和其 全部课程成绩。 （本题 15 分） 3、用二分法求方程“(2*X3)-(4*x2)+(3*x)-6 = 0”在(-10,10)之间的根。 （本题 20 分） 4、请写出判断“点是否在简单多边形内部”的算法。 （本题 20 分） 5、从平均时间、最坏情况，辅助存储和稳定性的角度，对各种内部排序方法进行比较。 （建 议用表格方
7、式进行比较，本题 20 分） 6、定义一个双向循环链表，并写出其定位、插入和删除算法。 （本题 20 分） 7、编制一个程序以模拟银行窗口接待客户的排队业务活动（每个窗口在某个时刻只能接待 一个客户；窗口空闲，则可上前办理业务；窗口均被占，则新客户便会排在人数最少的队伍 前面） ，并计算一天中客户在银行逗留的平均时间。 （本题 20 分） 8、设 T 是正则二叉树（若根树 T 的每个结点都恰有左右两个二则，则该树 T 被称为正则二 叉树）它具有 6 片树叶，那么树 T 的高度最多可以是多少，最小可以是多 少；树 T 的内结 点数是多少，如果 T 又是 Huffman 最优树，且各片树叶的数分别
8、是 1，2，3，4，4，6，则 最优树 T 的非树叶结点的数之和是多少，数为 1 的树叶的高度是多少。 （注：树的根结点高 GISGIS 论坛论坛 3 度为 1；本题写出答案即可；本题 20 分） 南师大南师大 GIS 考研考研 2009 年年 C 语言程序设计语言程序设计(含数据结构含数据结构)考研真题考研真题 程序设计（共 150 分，请书写整洁，卷面有分） （1） 、设计一个程序，找出 1200 之间的所有水仙花数。所谓水仙花数是指一个数的各位 数字的立方和恰好等于该数本身。例如：153=13+33+53。 （本题 15 分） （2） 、设计一个程序，实现输入一个给定的正整数 N,打印出
9、所有不超过 N 的，其平方为回 文（回文是指字符串两半的字符左右对称，例如 1，22，121，4224 等均是回文）的数。 （本 题 15 分） （3） 、 编写程序用于统计字符串中最长单词的长度和在字符串中的位置， 其中单词全有字母 组成。 （本题 20 分） （4） 、编写算法输出从 n 个自然数中取 k 个（k=1） ，试写一个求 A 中 n 个整数的平均值的递归程序。 6.假设由终端输入集合元素， 先建立表示集合 X 的静态链表 P1， 而后在输入集合 Y 的元素同 时查找 P1 表，若存在和 Y 相同的元素，则从 P1 表中删除之，否则将此元素插入 P1。 7.请写出用二叉树计算英文
10、文献中单词使用频度的算法。 单词的频度=该单词的使用次数 / 文献中单词的总数 8.请写出如图所示的树向二叉树转换的算法， 并用中序遍历给出转换后二叉树的节点序列和 树的深度。 （图是一棵树，我给描述下吧，自己画出来看吧，呵呵） A 的孩子：B,C,D B 的孩子：E,F C 的孩子：G,H,I D 的孩子：J F 的孩子：K,L H 的孩子：M,N 南师大南师大 GIS 考研考研 2007 年年 C 语言程序设计语言程序设计(含数据结构含数据结构)考研真题考研真题 （1）设 S 为一个长度为 n 的字符串，其中串的字符各不相同，写出具体程序并计算出 S 中 互异的非平凡子串，非空且不同于 S
11、 本身的个数。 （本题 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）已知平面上（直角坐标系
12、）的 m 个点，请编写一个函数，求同一条直线所能通过的最 多点数。 （本题 20 分） 。 （7）用程序设计有 n 个叶子结点的 Huffman 树的结点个数。 （本题 20 分） 。 （8）依次输入表（30，15，28，20，24，10，12，68，35，50，46，55）中的元素，生成 一棵二叉排序树。 （本题 20 分） 。 试画出生成之后的二叉排序树。 若该二叉排序树作中序编历，试写出编历序列。 假设每个元素的查找概率相等，试计算该二叉排序树的平均查找长度。 南师大南师大 GIS 考研考研 2006 年年 C 语言程序设计语言程序设计(含数据结构含数据结构)考研真题考研真题 1.设计一
13、个程序，将任何输入的字符串中的最长单词输出，并计算出其在字符串中的位置。 GISGIS 论坛论坛 5 （15 分） 2. 试采用递归函数实现将任意位数的整数转换为字符串输出，要求在主函数中输入整数并 调用递归函数实现转换并输出结果，对于负数也能处理（15 分） 3. 以顺序存储结构表示串，设计算法，求串 S 中出现的第一个最长重复子串及其位置并分 析算法的时间复杂度。 （20 分） 4.利用 2 个栈 S1 和 S2 模拟一个队列， 写出入队和出队的算法 （可用栈的基本操作）（20 分） 5编写一算法，以完成在带头节点单链表 M 中第 n 个位置前插入元素 X 的操作。 （20 分） 6编写一
14、个利用二分法查找某值 X 是否存在于一组已知数据 X1、X2、X3、Xn 中的程序。 （20 分） 7试设计一个算法解决地图着色判断问题。设一地图有 n 个区域，用不多于 4 种颜色对这 些区域进行着色，着色应满足的要求是相邻的区域颜色不可以相同。你的 算法以一种着色 方案（即哪一个区域着什么颜色）为输入，算法对该着色方案进行考察，若满足着色要求， 则输出 true,否则则输出 false。 （20 分） （1）用 C 语言描述你为解决问题而设计的数据结构（逻辑结构，存储结构） 。数据结构的设 计应考虑对问题的清楚描述和算法的效率； （2）用 C 语言写出你的算法。算法应简洁、高效。对算法中的
15、参数、变量、语句做必要的 注释，以增加可读性； （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 考研考研 2005 年年 C 语言程序设计语言程序设计(含数据结构含数据结构)考研真题考研真题 （1）设 A 和 B 是两个顺序表，其元素按从小到大的顺
16、序排列。编写一个将 A 和 B 中相同元 素组成一个新的从大到小的有序顺序表 C 的算法，并分析算法的时间复杂度。 （本题 15 分） （2）若线性表用单链表（带表头结点）作为存储结构，写出其就地逆置算法。 （本题 15 分） （3）设定串采用顺序存储结构，求串 s1 和串 s2 的一个最长公共子串的长度，并指出该最 长公共子串分别在 s1 和 s2 中的起始位置。 （本题 15 分） （4）设单链表中存放 n 个字符，试设计一个算法，使用栈判断该字符串是否中心对称，如 GISGIS 论坛论坛 6 xyzzyx 即为中心对称字符串。 （本题 15 分） （5）编写算法找出从自然数 1,2,.,n 中任取 r 个数的所有组合。 （本题 15 分） （6）设计一个计算二叉树各结点的子孙个数的算法。 （7）已知一棵二叉树的先序序列和中序序列，则可唯一确定一棵二叉树。 （本题 20 分） 设计一个算法由先序序列和中序序列构造二叉
