南京航空航天大学2000--2002年数据结构与程序设计试题
--------------------------------------------------------------------
南京航空航天大学2002年数据结构与程序设计试题
数据结构配程序设计 说明：下列每道题10分，编程题可用任何一种编程语言编写
一、将下列稀疏矩阵的非零元素表示成三元组的形式和十字链表的形式。
二、设一棵二叉树的层次遍历序列为ABDEGHJK，中序遍历序列为GDJHKBEA。
（1）画出这棵二叉树示意图
（2）说明建立这棵二叉树的原理
三、回答下列B树（有些教材中称为B-树）问题：
（1）一棵4阶4层（根为第一层，叶子为第二层）的B树，至少有多少关键字，至多有多少关键字
（2）在含有n个关键字的m阶B树中进行查找时，最多访问多少个结点。
四、哈希表中使用哈希函数H（key）=3 * key % 11,并采用开放定址法处理冲突，随机探测再散列的下一地址公式为：
d1=H (key )
di=( di-1 +7 * key ) % 11 （I=2,3…..）
试在0到10的散列地址空间中对关键字序列（22，41，53，46，30，13，01，67）画出Hash表示意图，并求在等概率情况下查找成功的平均查找长度。
五、求出一棵滿k叉树的叶子结点数n和所有非叶子结点数m之间的关系，给出求解过程。
六、已知两个链表A和B，其元素值递增排列。编程，将A和B合并成一个递减有序（相同值只保留一个）的链表C，并要求利用原表结点。
七、已知一棵二叉树用二叉链表存储，root 指向根结点，p指向树中任一结点。编程，输出从root 到p 之间路径上的结点。
八、已知一棵树用孩子－兄弟链表存储。编程，计算该树的叶子数。
九、设有n 个整数组成的序列，每个整数为－1，0，1之一。编写一个时间复杂度为O（n）的算法，使该序列按负数、零、正数的次序排好。
十、已知n个顶点的带权图用邻接矩阵表示，编写函数，实现用Kruskal算法构造最小生成树，要求对函数中所使用的变量和内容做详细的注释说明。
南京航空航天大学2001年数据结构与程序设计试题
考试科目：数据结构与程序设计 说明：下列每道题10分，编程题可用任何一种编程语言编写
一、根据下图所示广义表的存储结构，写出此图表示的广义表。
二、试找出分别满足下列条件的所有二叉树
（1）先序序列和中序序列相同
（2）中序序列和后序序列相同
（3）先序序列和后序序列相同
三、根据下图所示的一棵3阶B树（有些教材中称为B-树）
（）分别给出插入关键字2，12，16，17和18之后的结果。
（）分别给出在原图上删除8和9之后的结果。
四、对下图所示的有向图
（1）画出它的邻接表示意图
（2）根据邻接表写出其拓扑排序序列
五、用栈实现将中缀表达式8-（3+5）*（5-6/2）转换成后缀表达式，画出栈的变化过程。
六、已知两个链表A和B分别表示两个集合，其元素递增排列。编一函数，求A与B的交集，并存放于A链表中。
七、已知一棵二叉树用二叉链表存储，编写递归函数，判断其是否是平衡二叉树。
八、编写程序将一整数序列中所有负数移到所有正数之前，要求时间复杂度为O（n）
九、已知n个顶点的有向图用邻接矩阵表示，编写函数，计算每对顶点之间的最短路径。
十、编程，判断一棵用二叉链表表示的二叉树是否是完全二叉树。
南京航空航天大学2000年数据结构与程序设计试题
考试科目：数据结构与程序设计 说明：下列每道题10分，编程题可用任何一种编程语言编写
1、 叙述基数排序算法，并对下列整数序列图示其基数排序的全过程。
179，208，93，306，55，859，984，9，271，33
2、 什么是哈夫曼树？试证明有n个叶子的哈夫曼树共有2n-1个结点。
3、 推导并求解n阶Hanoi塔问题至少执行move操作次数。
4、设有三对角矩阵（Aij）n×n，将其三对角线上元素逐行存于数组B［1..m］中，使B[k]=Aij
求： （1）用 i,j 表示k的下标变换公式
（2）用k表示i,j 的下标变换公式
5、输入下列整数序列，画出建立的二叉排序树，最后分别图示将其中50，86删除后的二叉排序树
86，50，78，59，90，64，55，23，100，40，80，45
6、设整数序列a1，a2，… ，an，给出求解最大值的递归程序。
7、编程求解无向图G的所有连通分量。
8、设有带头结点的单链表L，编程对表中任一值只保留一个结点，删除其余值相同的结点。
9、设T是一棵n元树，Tb是T的孩子兄弟表示（二叉链表）的二叉树，试编程由Tb计算T的高度。（要求用非递归方法实现）
10、设以整数序列a1，a2，a3，a4作为栈S的输入，利用push，pop操作，写出所有可能的输出，并编程实现算法。
中国科学院遥感应用研究所四科样题
--------------------------------------------------------------------
中国科学院遥感应用研究所
XXXX年硕士研究生入学考试试卷（共3页）
科目：地理信息系统概论（总分150分） 时间：180分钟
（一名词解释，二填空题，三判断题答在试卷上；四简答题，五论述题答在答题纸上）
一、 名词解释（每题3分，共15分）
1、 地理信息系统
2、 空间信息网格
3、 空间数据挖掘
4、 数据互操作性
5、 空间索引
二、 填空题（每空答对得2分，不答或答错不扣分，共40分）
1、地理信息系统萌芽于（ ）年代。
2、我国的地理信息系统工作起始于（ ）年代，其标志是（ ）。
3、（ ）、（ ）和（ ）是地理空间分析的三大要素。
4、地理信息系统中的数据转换主要包括（ ）和（ ）。
5、地理信息系统的空间分析分为（ ）、（
）和（ ）三个层次。
6、空间关系通常分为（ ）、（ ）和（ ）三类。
7、手扶跟踪数字化的精度受（ ）、 （ ）和（ ）三种条件的影响。
7、空间信息查询方式主要有（ ）、
（ ）和（ ）
三种方式。
三、 判断题（请根据判断在每题的括弧中写入“对”或“错”，每一题答对得4分，答错不扣分，共20分）
1、若某一弧段的左、右多边形分别为A和B，则A、B两个多边形相邻。（ ）
2、若弧段A和多边形P无交点，则A和P是分离关系。（ ）
3、利用游程编码数据结构一定能够减少数据存储空间。（ ）
4、对于等角投影，面积越大，造成的畸变越大，因而大面积的区域制图不适合使用等角投影。（ ）
5、开放式GIS的目的是实现异构分布数据的共享和不同系统之间的互操作。（ ）
四、 简答题（共三题，每题10分，共30分）
1、简述地理空间数据库的特点及发展趋势
2、简述空间数据质量的标准要素
3、简述地理信息系统标准化的内容及意义
五、 论述题（共两题，45分）
1、 长江三峡工程是举世注目的重大水利工程。若根据蓄水前后的水位计算淹没区范围、淹没耕地面积及淹没区移民数量，你需要哪些基本数据？并结合GIS的功能给出详细的技术方案和实现过程。（25分）
2、 给定某一海域的海面观测点分布地图及每个点的海面日平均温度观测数据，现需要计算该海域内某一天的海面温度等值线分布及温度变化梯度分布，请利用GIS的功能给出求解方法和步骤。（20分）
中国科学院遥感应用研究所
XXXX年度硕士生入学考试试题
自 然 地 理
一、名词解释(30分：10×3分)
黄土堆积 季风气候
隐域性植被 干燥度
自然区划原则 土地利用
径流 植被
流域 地下水
二、填空题(30分：20×1.5分)
地貌形成因素包括 、 、 、 等。
气候形成因素包括 、 、 等。
自然地理要素的空间分异规律一般概括为 、 、
等。
地表水主要赋存形式有 、 、 等。
我国海岸基本分为 、 、 等类型。
森林蕴藏着大量的动、植物资源，并且具有 、 、
、 ，以及防治自然灾害的巨大作用。
三、简述题：(60分：3×20分)
1．简述我国第四纪环境演变的主要特点
2．中国自然地理地域分异的特征
3.根据中国土地资源的特征，试述其意义或对策
四、论述题(30分)
试述人类活动与自然地理过程的相互作用？
中国科学院遥感应用研究所
XXXX年硕士研究生入学考试试题
遥感概论
一、 名词解释(每题6分,共60分)
1 地物反射波（光）谱
2 双向反射率分布函数
3 基尔霍夫定律
4 瑞利散射
5 大气窗口
6 分辨率
7 辐射亮度
8 维恩位移定律
9 高光谱
10 小波分析
二、 问答题(每题12分,共60分)：
1. 简述遥感数字影像增强处理的目的，例举一种增强处理方法，说明其原理和步骤。（12分）
2. 比较非监督分类和监督分类方法。（12分）
3. 利用雷达探测地物的机理及其优势。（12分）
4. 光机扫描成像与CCD成像的比较。（12分）
5. 晴空时大气对可见光遥感和红外遥感的影响有何特点？（12分）
三、 论述题（30分）
我国“风云一号”系列气象卫星是极轨气象卫星，其中“风云一号C星”及“风云一号D星”携带的多通道可见红外扫描辐射计(MVISR) 有10个通道，各通道波长如下表。请谈谈这些探测波段在陆地地表遥感中的用途。（30分）
表1：风云1-C、D多通道可见红外扫描辐射计(MVISR)各个波段的波长范围
通道号 波长（微米） 备注
1 0.58-0.68
2 0.84-0.89
3 3.55-3.93
4 10.3-11.3
5 11.5-12.5
6 1.58-1.64
7 0.43-0.48 海洋水色
8 0.48-0.53
9 0.53-0.58
10 0.90-0.965 水汽
中国科学院遥感应用研究所
XXXX年硕士研究生入学考试试卷
科目：程序设计与算法语言（总分150分） 时间：180分钟
一、 填空题（每小题2分，共80分）
1. A node in a tree that does not have any children is called
(a) a leaf； (b) an internal node； (c) a root； (d) an empty node；
2. 对于一棵深度为2的二叉树，它的总节点数：
(a) 至多7个 (b)至多2个 (c) 节点数不限 (d) 至多4个
3. 下面的伪码是对二叉树操作算法的片段：
print( node )
{
if( there is a left child ) print( left child );
print data;
if( there is a right child ) print( right child );
}
这个算法是：
（a）折半查找； （b）前序遍历； （c）中序遍历； （d）后序遍历；
4. 下面哪个序列不是折半查找（二分查找）所访问的数值序列
(a) 10, 20, 30, 40, 50； (b) 50, 40, 30, 20, 10； (c) 10, 20, 30, 15, 18； (d) 30, 50, 40, 45, 42
5. 递归函数可以调用自身多少次?
(a) 只多1次; (b) 任意次数; (c) 0 次; (d) 至多2次;
6. 分析下面函数：
int f( int n )
{
if( n = = 0 ) return 0;
if( (n & 1) = = 0 ) return f(n/2);
return f(n/2) + 1;
}
调用函数f(10)的返回值是：
(a) 1； (b) 3； (c) 5； (d) 2；
7. 假如n,m>=0，那么下面函数的功能是：
int ff( int n, int m )
{
if( n == 0 ) return m;
return ff( n-1, m*n );
}
(a) 计算m * (n!)； (b) 计算最大公约数； (c)计算最小公倍数； (d) 计算(m + n)!；
8. 给定长度为10的数组，归并排序由于对站所需的额外空间是
(a) n+1； (b)n； (c)log n； (d)n2 ；
9. 总的来说，哈希方法（hashing，也称散列方法）的主要问题在于：
(a)哈希函数难以计算； (b)哈希表的存取速度慢；
(c)会发生冲突； (d)哈希表占很多内存；
10. 对于一个大小为m含有n项的哈希表，它的负载(load)因子是：
(a) m - n； (b) n + m； (c) m/n； (d) n/m ；
11. 编译或执行下面C语言条件语句的结果是：
if( x = expr ) ;
(a)expr的值赋给x，然后计算x的值作为if的条件;
(b)当且仅当expr的值为true(真)时,其值付给x;
(c)会出现编译错误;
(d)计算expr,然后与x的值相比较;
12. 下面对p的声明，那一个是指向整数的指针：
(a) int **p； (b) int p[]； (c) int &p； (d) int *p；
13. 假设Thing是一个用户定义的类，B是Thing的一个实例，对于下面的代码段
Thing A = B
用到了类Thing中的哪一个成分：
(a)赋值操作符； (b)析构函数； (c)构造函数； (d)复制构造函数；
14. 下面对类的部分描述用于说明一种用户定义的实数实现：
class RealNumber {
...
RealNumber( float x );
RealNumber( float x, float y=0 );
};
这段代码可能错在哪里?
(a)在构造函数中不允许时有缺省值； (b)没有错误；
(c)第二个构造函数与第一个不一致； (d)用两个实数参数无法创建一个实数；
15. 面向对象的程序设计最适合下面哪一种开发要求:
(a)程序是一个完整的程序模块； (b)提供完善的代码复用；
(c)获得高效率； (d)对封装的需求；
16. 下面哪一条关于继承的叙述是正确的:
(a)它是一种重要的面向对象程序设计思想,但是在程序语言中无法实现；
(b)它提供了由现有类构造新类的完善方法；
(c)提供数据成员保护，阻止非法存取；
(d)使得一种类型表现出多种类型的行为；
17. 在面向对象方法中，多态机制的目的是:
(a)在现有的多个类的上层创建一个新类；(b)在运行时动态地确定一个对象的类型；
(c)保护数据成员，阻止非法存取； (d)根据类的数据成员确定类的方法；
18. 对于有n个节点e条边的图，如果用邻接表表示，则计算全部入度的时间复杂度是:
(a) O(n + e)； (b) O(n^2)； (c) O(n^3)； (d) O(n * e) ；
19. 结定结点的关键字序列（Ｆ、Ｂ、Ｊ、Ｇ、Ｅ、Ａ、Ｉ、Ｄ、Ｃ、Ｈ），对它按字母的字典顺序进行排列， 快速排序的第一趟结果是：
(a)（C、B、D、A、F、E、I、J、G、H） (b)（C、B、D、A、E、F、I、G、J、H）
(c)（B、A、D、E、F、G、I、J、H、C） (d)（B、C、D、A、E、F、I、J、G、H）
20. 在高级程序设计语言中，参数传递方法有传值调用(CALL BY value)、引用调用(CALL BY REFERENCE)、传名调用(CALL BY NAME)和宏扩展(MACRO EXPANSION)，其中，引用调用是指把实在参数的___传递给相应的形式参数：
(a)地址； (b)值； (c)地址和值； (d)名；
21. 设W为一个二维数组，其每个数据元素Wij 占用6个字节，行下标i从0到8，列下标j从2到5，则二维数组W的数据元素共占用___个字节。
(a)480； (b)192； (c)216； (d)144；
22. 堆是一种特殊的数据结构，下面哪一个是堆：
(a)19,75,34,26,97,56；(b)97,26,34,75,19,56；(c)19,56,26,97,34,75；(d)19,34,26,97,56,75；
23. 下面关于B树和B+树的叙述中，不正确的是
(a) B树和B+树都是平衡的多分树； （b）B树和B+树都是可用于文件的索引结构；
(c) B树和B+树都能有效地支持顺序检索；(d) B树和B+树都能有效地支持随机检索；
24. 在数据结构中，从逻辑上可以把数据结构分成：
(a)动态结构和静态结构； (b)紧凑结构和非紧凑结构；
(c)线性结构和非线性结构； (d)内部结构和外部结构；
25. 下面程序段的时间复杂度是
for (i=0;i<n;i++)
for (j=0;j<m;j++)
A[j]=0;
(a)O(m+n)； (b)O(m/2+n/2)； (c)O(m/n)； (d)O(m*n)；
26. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn, 那么p1=n；pi为：
(a)i； (b)n=i； (c)n-i+1； (d)不确定；
27. 判断一个循环队列QU（最多元素m0）为空的条件是：
(a)QU->front = = QU->rear； (b) QU->front! = QU->rear；
(c) QU->front = = (QU->rear+1)%m0； (d) QU->front ! = (QU->rear+1)%m0；
28. 表达式a*(b+c)-d的后缀表达式是
(a)abcd*+-； (b)abc+*d-； (c)abc*+d-； (d)*-a+bc；
29. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行：
(a)s->next = p->next; p->next = s；(b)p ->next = s->next; s->next = p；
(c) q->next =s; s->next = p； (d) p->next =s; s->next = q；
30. 在一个链队中，假设f和r分别为队首和队尾指针，则插入s所指结点的运算是：
(a) f->next = s；f=s；(b) f->next = s；r=s；(c) s->next = r；r=s；(d) s->next = f；f=s；
31. 将一个整数10002存到磁盘上，以ASCII码形式存储和以二进制形式存储，占用的字节数分别是
(a)2和2 (b)2和5
(c)5和2 (d)5和5
32. 计算机算法是指
(a) 数值计算方法 (b) 对抽象数据结构的操作方法
(c) 非数值计算方法 (d) 解决问题的有限运算序列
33. 将递归算法转换成对应的非递归算法时，通常需要使用
(a) 栈 (b) 对列
(c) 链表 (d) 树
34. 树最适合用来表示
(a) 有序数据元素 (b) 无序数据元素
(c) 元素之间具有分支层次关系的数据 (d) 元素之间相关联的数据
35. 分析执行下面程序段后，变量a的值:
a ← 0
i ← 0
j ← 100
WHILE i <= j DO
BEGIN
a ← a + i + j
i ← i + 1
j ← j - 1
END
(a) 5100 (b) 5000
(c) 4900 (d) 5101
36. 要求一个线性表既能较快地查找，又能适应动态变化的要求，则可采用的查找方法是：
(a) 分块查找 (b) 顺序查找
(c) 二分查找 (d) 散列查找
37. 下面哪种技术和分布式的软件体系结构无关
(a) CORBA规范 (b) 中间件
(c) 客户／服务器结构 (d) 主程序／子程序结构
38. 下面哪种说法是不合理的
(a) 程序 = 算法 + 数据结构 (b) 软件 = 程序 + 文档
(c) 对象 = 继承 + 封装 (d) 构件 = 接口 + 实现
39. 被认为最有可能彻底解决“软件危机”的方法是：
(a) 软件复用 (b) 对数据结构的标准化
(c) 面向对象技术 (d) 原型开发模型
40. UML是指
(a) 一种程序设计语言 (b) 一种通用的建模语言
(c) 一种开发工具 (d) 一家著名的软件公司
二、 在联欢会上，M个人围坐一圈，每人准备了一个节目。表演的顺序采用一种游戏的方法产生：从圈内选出1人记为1号，按顺时针方向每人的号数依次记为2号、3号…M号。由1号随机抽出一个号N（1<=N<=M），然后从1号开始顺时针方向1、2、3…顺序报数，每报到N时，这个人就出来表演节目，表演结束后，再从1开始继续向下报数，报到N的人就出来表演。凡是表演过的人，下一次报数时就跳过去，这样继续下去，直到M个人都表演完节目。请你编一个程序，用算法模拟这个过程，要求打印出表演节目人的顺序号。（15分）
三、 有甲、乙、丙三个人和A、B、C三个不同的工作，每人一天只能干一个工作，且一个工作每天必须一个人干。下表表示的是甲、乙、丙三个人在A、B、C三个不同的工作岗位上工作一天所创造的价值：
A B C
甲 30 50 25
乙 35 30 20
丙 45 40 30
说明：甲在A岗位上干一天所创造的价值为30，在B岗位上干一天所创造的价值为50…
请编程确定如何分配工作（甲、乙、丙三人在什么工作岗位），三人一天共同创造的价值最多。（15分）
四、 键盘输入一个高精度的正整数N（N不超过200位），去掉其中任意S个数字后剩下的数字按原左右次序组成一个新的正整数。编程对给定的N和S，寻找一种方案使得剩下的数字组成的新数字最小。（20分）
五、 设G=(V, E)是一无向连通图。如果去掉G的某顶点后，G就不是连通图，这样的顶点称为割点，试用深度优先搜索，编程确定一个无向连通图的所有割点。（20分）
中国科学院地球化学研究所2002地理信息系统 |
收藏
点赞!
反对!
楼主