中国科学院遥感应用研究所硕士研究生入学考试样题《程序设计与算法语言》科目：一填空题（每空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）（）; _________________ 贝U p 是____________ 而q 是。
5、已知一棵二叉树的前序序列为abdecfhg,中序序列为dbeahfcg，则该二叉树的根为__________ 左子树中有_____________ ，右子树中有 ___________ 。
& 己知有序表为（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]&已知有下面的三个类（使用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 T满足（）。
A. p T」ink=head B .p T」ink=NIL C . p=NIL D .p= head16、若长度为n 的线性表采用顺序存储结构，在其第i 个位置插入一个新元素的算法的时间复杂度为（）（1<=i<=n+1）。
2A. O（0）B. O（1）C. O（n）D. O（n 2）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. 2B. 4C. 8D. 无限递归28、一个递归算法必须包括（）。
A.递归部分B. 终止条件和递归部分C. 迭代部分D. 终止条件和迭代部分29、适用于折半查找的表的存储方式及元素排列要求为（）A .链接方式存储，元素无序B .链接方式存储，元素有序C. 顺序方式存储，元素无序D .顺序方式存储，元素有序30、在一棵m阶的B+树中,每个非叶结点的儿子数S应满足（）.A. 2< S< mB.C. 1 < S< 2D. 131、设哈希表长为14,哈希函数是H（key）=key%11,表中已有数据的关键字为15,38, 61, 84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是（）A . 8B . 3C . 5D . 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、在下列排序算法中，哪一个算法的时间复杂度与初始排序无关（）。