样题-中国科学院遥感与数字地球研究所汇编

学习-----好资料 更多精品文档 中国科学院遥感应用研究所 硕士研究生入学考试样题 科目：《程序设计与算法语言》

一 填空题 （每空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. 2 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”< …… }； 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层的结点数为（ ）。 35

10 19 45 60 82 5 8 11 13 15 23 30 38 41 47 53 64 70 73 78 86 95 学习-----好资料 更多精品文档 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 50 main(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值为：（ ）