遥感所复试《程序》样题.doc

中国科学院遥感应用研究所 硕士研究生入学考试样题 科目：《程序设计与算法语言》 一 填空题 （每空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浏览器中的显示。 1、用来表示一个变量的地址或者表示另一变量的地址的变量是（ ）。 A.函数；　B　C　 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数组第一维的大小是（ ）。 B. 3 C. 4 D. 无确定值 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。则下面的引用正确的是（ ）。 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结点的语句（ ）。 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），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。 A．(38,40,46,56,79,84) B. (40,38,46,79,56,84) C．(40,38,46,56,79,84) D. (40,38