样题-科学院遥感与数字地球研究所.doc

。中国科学院遥感应用研究所硕士研究生入学考试样题科目：程序设计与算法语言 一填空题 （每空2分，共30分）1、对于一个具有n个结点的二元树，当它为一棵_二元树时具有最小高度，当它为一棵_时，具有最大高度。2、设数组a1.50,1.80的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a45,68的存储地址为_;若以列序为主序顺序存储，则元素a45,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； 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按列先存储时的元素（ ）的起始地址相同。设每个字符占一个字节。A. A8,5 B. A0,9 C. 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、链表所具备的特点是（ ）可随机访问任何一个元素； 插入、删除操作不需要移动元素；无需事先估计存储空间大小；所需存储空间与线性表长度成正比；A.； B.； C. ； D. ；9、计算机算法是指（ ）A数值计算方法； B对抽象数据结构的操作方法；C非数值计算方法； D解决问题的有限运算序列；10、已知L是无表头结点的单链表，试从下面的语句中选出在表首插入S结点的语句（ ）。 （1） Lnext=S；（2） Snext=L；（3） Snext=Lnext；（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），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。 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个顶点的连通无向图，其边的个数至少为（ ）。An-1 Bn Cn+1 Dnlogn；13、有关类和对象的说法不正确的是（ ）。A. 类是对于众多对象的归纳；B. 类的对象具备该类的所有特征；C. 类是抽象的数据结构，而对象是具体的事件或事物等；D. 在程序中，我们只能使用对象的成员，而不能直接使用类的成员；14、以下语句或语句组中，能正确进行字符串赋值的是（ ）。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=NIL Cp=NIL Dp= head16、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1=iI;int array1I; int array2M; int array4K; int array3N; int array5J; A.； B.； C.； D. ；27、执行完下列语句段后，i值为：（ ） int f(int x) return (x0) ? x* f(x-1):2); int i ; i =f(f(1);A2 B. 4 C. 8 D. 无限递归28、一个递归算法必须包括（ ）。A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D.终止条件和迭代部分29、适用于折半查找的表的存储方式及元素排列要求为( ) A链接方式存储，元素无序 B链接方式存储，元素有序C顺序方式存储，元素无序 D顺序方式存储，元素有序30、在一棵m阶的B+树中, 每个非叶结点的儿子数S 应满足 ( ). A.Sm B. Sm C. 1S D. 1S31、设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( ) A8 B3 C5 D9 32、如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。（ ）就是不稳定的排序方法。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、定义如下结构体