中国科学院遥感应用研究所硕士研究生入学考试样题科目：《程序设计与算法语言》一填空题（每空2分，共30分）1、对于一个具有n个结点的二元树，当它为一棵________二元树时具有最小高度，当它为一棵________时，具有最大高度。

2、设数组a[1..50,1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45,68]的存储地址为_________;若以列序为主序顺序存储，则元素a[45,68]的存储地址为____________。

3、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为________,在给定值为x的结点后插入一个新结点的时间复杂度为______________。

4、已知int*p(),(*q)();则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.结构体；2、在C语言中，若函数调用时实参是数组名，则传递给对应形参的是（）。

A．数组空间的首地址；B．数组的第一个元素值；C．数组中元素的个数；D．数组中所有的元素；3、int a = 2，则执行完表达式a+=a+=a-=a*a;后，a的值是（）A．-4；B．0；C．-8；D．16；4、若有说明：int a[][3]={1,2,3,4,5,6,7};则a数组第一维的大小是（）。

A. 2B. 3C. 4D. 无确定值5、二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,…,8,列下标j=1,2,…,10。

若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素（）的起始地址相同。

设每个字符占一个字节。

A. A[8,5]B. A[0,9]C. A[5,8]D. A[3,10]6、已知有下面的三个类(使用C++语言描述)：class A{ int a;public:void fun(){ cout<<”class A fun() is called”<<endl;}……}；class B{ int a;public:A *a;……}；class C{ int a;public:B *b;……}；在主程序中，定义一个类C的对象指针C *obj。

则下面的引用正确的是（）。

A. obj->b->a->fun()；B. obj.b->a.fun()；C. obj->b.a->fun()；D. obj.b.a->fun()；7、对稀疏矩阵进行压缩存储目的是（）。

A．便于进行矩阵运算 B．便于输入和输出C．节省存储空间 D．降低运算的时间复杂度8、链表所具备的特点是（）①可随机访问任何一个元素；②插入、删除操作不需要移动元素；③无需事先估计存储空间大小；④所需存储空间与线性表长度成正比；A.①②③；B.②③④；C. ①②④；D. ①③④；9、计算机算法是指（）A．数值计算方法；B．对抽象数据结构的操作方法；C．非数值计算方法；D．解决问题的有限运算序列；10、已知L是无表头结点的单链表，试从下面的语句中选出在表首插入S结点的语句（）。

（1） L－>next=S；（2） S－>next=L；（3） S－>next=L－>next；（4） L－>next=S－>next；（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），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。

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-1 B．n C．n+1 D．nlogn；13、有关类和对象的说法不正确的是（）。

A. 类是对于众多对象的归纳；B. 类的对象具备该类的所有特征；C. 类是抽象的数据结构，而对象是具体的事件或事物等；D. 在程序中，我们只能使用对象的成员，而不能直接使用类的成员；14、以下语句或语句组中，能正确进行字符串赋值的是（）。

A. char*sp； *sp="right!"；B. char s[lO]；s="right! "；C. char s[10]；*s="right! "；D. char*sp="right! ";15、非空的循环单链表head的尾结点p↑满足（）。

A．p↑.link=head B．p↑.link=NIL C．p=NIL D．p= head 16、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。

A. O(0)B. O(1)C. O(n)D. O(n2)17、有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（）。

A. 5 4 3 6 1 2；B. 4 5 3 1 2 6；C. 3 4 6 5 2 1；D. 2 3 4 1 5 6 ；18、软件管理是软件工程化生产的重要环节，以下哪些是软件工程管理应包括的内容？（）。

①人员组织；②进度安排；③．质量保证；④成本核算；A.①②；B.②③；C.②④；D.①②③④；19、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9 B．11 C．15 D．不确定20、以下能对二维数组a进行正确初始化的语句是( )。

A.int a[2][]={{1,0,1},{5,2,3}};B.int a[][3]={{1,2,3},{4,5,6}};C.int a[2][4]={{1,2,3},{4,5},{6}};D.int a[][3]={{1,0,1},{},{1,1}};21、以下正确的说法是( )。

` 在C语言中A.实参和与其对应的形参各占用独立的存储单元B.实参和与其对应的形参共占用一个存储单元C.只有当实参和与其对应的形参同名时才共占用存储单元D.形参是虚拟的，不占用存储单元22、对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。

A．先序 B. 中序 C. 后序 D. 从根开始按层次遍历23、如下所示是一棵5阶B树，该B树现在的层数为2。

从该B树中删除关键码38后，该B树的第2层的结点数为（）。

A. 6；B. 7 ；C. 8；D. 9；24、以下正确的说法是____A. 定义函数时，形参的类型说明可以放在函数体内B. return后边的值不能为表达式C. 如果函数值的类型与返回值类型不一致，以函数值类型为准D. 如果形参与实参类型不一致，以实参类型为准25、下列说法不正确的是（）。

A．图的遍历是从给定的源点出发每一个顶点仅被访问一次B．遍历的基本算法有两种：深度遍历和广度遍历C．图的深度遍历不适用于有向图D．图的深度遍历是一个递归过程26、下面对于数组的定义正确的是（）。

int M=10;const int N=9;static int K=20;#define J 50main(int argc, char* argv[]){int I;cin>>I;int array1[I]; ———————————————①int array2[M]; ———————————————②int array4[K]; ———————————————③int array3[N]; ———————————————④int array5[J]; ——————————————⑤}A.①②③④⑤；B.②③④⑤；C.③④⑤；D. ④⑤；27、执行完下列语句段后，i值为：（）int f(int x){ return ((x>0) ? x* f(x-1):2);}int i ;i =f(f(1));A．2 B. 4 C. 8 D. 无限递归28、一个递归算法必须包括（）。

A. 递归部分B. 终止条件和递归部分C. 迭代部分D.终止条件和迭代部分29、适用于折半查找的表的存储方式及元素排列要求为( )A．链接方式存储，元素无序 B．链接方式存储，元素有序C．顺序方式存储，元素无序 D．顺序方式存储，元素有序30、在一棵m阶的B+树中, 每个非叶结点的儿子数S 应满足 ( ).A.⎥⎦⎥⎢⎣⎢+21m≤S≤m B.⎥⎦⎥⎢⎣⎢2m≤S≤mC. 1≤S≤⎥⎦⎥⎢⎣⎢+21mD. 1≤S≤⎥⎦⎥⎢⎣⎢2m31、设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( )A．8 B．3 C．5 D．932、如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。

（）就是不稳定的排序方法。

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、在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（）。

A．直接插入排序 B. 冒泡排序 C. 快速排序 D. 直接选择排序35、定义如下结构体，那么以下的变量定义中，不正确的是（）。