样题中国科学院遥感与数字地球研究所

1、中国科学院遥感应用研究所 硕士研究生入学考试样题科目：程序设计与算法语言一 填空题 （每空 2 分，共 30 分）1、对于一个具有 n 个结点的二元树，当它为一棵 二元树时具有最小高度，当它为一棵 时，具有最大高度。2、设数组 a1.50,1.80的基地址为 2000，每个元素占 2 个存储单元，若以行序 为主序顺序存储，则元素 a45,68的存储地址为 ;若以列序为主序顺序存储，则元素 a45,68的存储地址为 。3、对于一个具有 n个结点的单链表，在已知的结点 *p 后插入一个新结点的时间复杂度为 ,在给定值为 x 的结点后插入一个新结点的时间复杂度为4、已知 int*p（）,（*q）（）

2、;则 p 是, 而 q 是。5、已知一棵二叉树的前序序列为 abdecfhg, 中序序列为 dbeahfcg ，则该二叉树 的根为，左子树中有 ， 右子树中有 。6、己知有序表为 （12,18,24,35,47,50,62,83,90,115，134） 当用二分法查找 90时，需次查找成功，47时成功，查 100时，需次才能确定不成功。7、XML 在地理空间信息领域的应用是 。利用它可以存储和发布各种特征的地理信息，并控制地理信息在 Web 浏览器中的显示。选择题 （每小题 2分，共 70分）1、用来表示一个变量的地址或者表示另一变量的地址的变量是（）A. 函数； B. 指针； C.数组； D

3、.结构体；2、在 C 语言中，若函数调用时实参是数组名，则传递给对应形参的是（）A数组空间的首地址；C数组中元素的个数；B数组的第一个元素值；D数组中所有的元素；3、int a = 2 ，则执行完表达式 a+=a+=a-=a*a;后， a 的值是（ ）A-4；B 0 ；C-8 ；D16；4、若有说明： int a3=1,2,3,4,5,6,7;则 a 数组第一维的大小是（ ）A. 2 B. 3 C. 4 D. 无确定值5、二维数组 A的每个元素是由 6 个字符组成的串，其行下标 i=0,1, ,8, 列下标 j=1,2, ,10 。若 A按行先存储，元素 A8,5 的起始地址与当 A按列先存

4、储时的元素（ ）的起始地址相同。设每个字符占一个字节。A. A8,5 B. A0,9C. A5,8 D. A3,106、已知有下面的三个类 （ 使用 C+语言描述 ） ：class A int a;public:void fun（） cout ” class A fun（）is called ”b-a-fun（） ； B. obj.b-a.fun（） ；C. obj-b.a-fun（） ； D. obj.b.a-fun（） ；7、对稀疏矩阵进行压缩存储目的是（）。A便于进行矩阵运算 B 便于输入和输出C节省存储空间D 降低运算的时间复杂度8、链表所具备的特点是（）可随机访问任何一个元素； 插入

5、、删除操作不需要移动元素； 无需事先估计存储空间大小；所需存储空间与线性表长度成正比； A.； B.； C. ； D. ；9、计算机算法是指（）A 数值计算方法；B对抽象数据结构的操作方法；C非数值计算方法；D解决问题的有限运算序列；10、已知 L 是无表头结点的单链表， 试从下面的语句中选出在表首插入 S结点的语句（）。（1）Lnext=S；（2）Snext=L ；（3）Snext=L next ；（4）Lnext=Snext ；（5）L=S ；（6）S=L ；A（1）（6）；B（3）（5）；C（ 4）（6）；D（2）（5）；11、一组记录的关键码为（ 46，79，56，38，40，84），

6、则利用快速排序的方法， 以第一个记录为基准得到的一次划分结果为（ ）。A（38,40,46,56,79,84）B. （40,38,46,79,56,84）C（40,38,46,56,79,84）D. （40,38,46,84,56,79）12、一个 n 个顶点的连通无向图，其边的个数至少为（）。A n-1B nC n+1 Dnlogn ；13、有关类和对象的说法不正确的是（）。A. 类是对于众多对象的归纳；B. 类的对象具备该类的所有特征；C. 类是抽象的数据结构，而对象是具体的事件或事物等；D. 在程序中，我们只能使用对象的成员，而不能直接使用类的成员；14、以下语句或语句组中，能正确进行字

7、符串赋值的是（）。A. char*sp ； *sp=right! ；B. char slO；s=right! ；C. char s10 ；*s=right! ； D. char*sp=right! ;15、非空的循环单链表 head 的尾结点 p满足（）。Ap.link=head Bp.link=NILCp=NIL D p= head16、若长度为 n 的线性表采用顺序存储结构， 在其第 i 个位置插入一个新元素的 算法的时间复杂度为（） （1=iI;int array1I; int array2M;int array4K;int array3N;int array5J;A. ； B. ； C

8、. ； D. ；27、执行完下列语句段后， i 值为：（）int f(int x) return (x0) ? x* f(x-1):2);int i ;i =f(f(1);A2B. 4 C. 8 D. 无限递归28、一个递归算法必须包括()。A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D. 终 止条件和迭代部分29、适用于折半查找的表的存储方式及元素排列要求为 ( )A 链接方式存储，元素无序B 链接方式存储，元素有序C顺序方式存储，元素无序D 顺序方式存储，元素有序30、在一棵 m阶的 B+树中 , 每个非叶结点的儿子数 S 应满足 ( ).m1A. 2 S mmB. 2 S

9、mm1C. 1 S 2D. 1m S 231、设哈希表长为 14，哈希函数是 H(key)=key%11, 表中已有数据的关键字为 15， 38，61，84 共四个，现要将关键字为 49的结点加到表中，用二次探测再 散列法解决冲突，则放入的位置是 ( )A 8B 3 C 5 D932、如果待排序序列中两个数据元素具有相同的值， 在排序前后它们的相互位置 发生颠倒，则称该排序算法是不稳定的。 ( )就是不稳定的排序方法。A起泡排序 B 归并排序 C 希尔排序 D 直接插入排序33、对一组数据( 84，47，25，15，21)排序，数据的排列次序在排序的过程中 的变化为(1) 84 47 25 15 21 (2) 15 47 25 84 21(3) 15 21 25 84 47 (4) 15 21 25 47 84则采用的排序是 ( ) 。A. 选择 B. 冒泡 C. 快速 D. 插入34、在下列排序算法中 , 哪一个