中科院样题试题.docVIP

中国科学院遥感应用研究所 硕士研究生入学考试样题 科目：《程序设计与算法语言》 一 填空题 （每空2分，共30分） 1、对于一个具有n个结点的二元树，当它为一棵_满_二元树时具有最小高度，当它为一棵_ 斜二元树_时，具有最大高度。 2、设数组a[1..50,1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45,68]的存储地址为_9174_;若以列序为主序顺序存储，则元素a[45,68]的存储地址为_8788_。 3、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为_O(1)_,在给定值为x的结点后插入一个新结点的时间复杂度为_O(n)_。 4、已知int*p(),(*q)();则p是_返回值为指针的函数_,而q是_指向函数的指针_。 5、已知一棵二叉树的前序序列为abdecfhg,中序序列为dbeahfcg，则该二叉树的根为_a_，左子树中有_bde_， 右子树中有_cfgh_。 6、己知有序表为(12,18,24,35,47,50,62,83,90,115，134)当用二分法查找90时，需_2_次查找成功，47时_4_成功，查100时，需_4_次才能确定不成功。 7、XML在地理空间信息领域的应用是____________。利用它可以存储和发布各种特征的地理信息，并控制地理信息在Web浏览器中的显示。 二 选择题 （每小题2分，共70分） 1、用来表示一个变量的地址或者表示另一变量的地址的变量是（B）。 A.函数；　B.指针；　C.数组；　D.结构体； 2、在C语言中，若函数调用时实参是数组名，则传递给对应形参的是（A）。 A．数组空间的首地址；　　B．数组的第一个元素值；C．数组中元素的个数；　　D．数组中所有的元素； 3、int a = 2，则执行完表达式a+=a+=a-=a*a;后，a的值是（C） A．-4； B． 0； C．-8； D．16； 4、若有说明：int a[][3]={1,2,3,4,5,6,7};则a数组第一维的大小是（B）。 A. 2 B. 3 C. 4 D. 无确定值 5、二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,…,8,列下标j=1,2,…,10。若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素（B）的起始地址相同。设每个字符占一个字节。 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）。 A. obj-b-a-fun()； B. obj.b-a.fun()； C. obj-b.a-fun()； D. obj.b.a-fun()； 7、对稀疏矩阵进行压缩存储目的是（C）。 A．便于进行矩阵运算 B．便于输入和输出 C．节省存储空间 D．降低运算的时间复杂度 8、链表所具备的特点是（B） ①可随机访问任何一个元素； ②插入、删除操作不需要移动元素； ③无需事先估计存储空间大小；④所需存储空间与线性表长度成正比； A.①②③； B.②③④； C. ①②④； D. ①③④； 9、计算机算法是指（D） A．数值计算方法； B．对抽象数据结构的操作方法； C．非数值计算方法； D．解决问题的有限运算序列； 10、已知L是无表头结点的单链表，试从下面的语句中选出在表首插入S结点的语句（D）。 L－next=S； S－next=L； S－next=L－next； L－next=S－next； L=S； S=L； A．（1）（6）； B．（3）（5）； C．（4）（6）； D．（2）（5）； 11、一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（C）。 A．(38,40,46,56,79,84) B. (40,38,46,79,56,84) C．(40,38,46,56,79,84)