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

中国科学院遥感应用研究所硕士研究生入学考试样题科目：《程序设计与算法语言》一填空题（每空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、inta=2，则执行完表达式a+=a+=a-=a*a;后，a的值是（）A．-4；B．0；C．-8；D．16；4、若有说明：inta[][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]6、已知有下面的三个类(使用C++语言描述)：classA{inta;public:voidfun(){cout”classAfun()iscalled”endl;}……}；classB{inta;public:A*a;……}；classC{inta;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-1B．nC．n+1D．nlogn；13、有关类和对象的说法不正确的是（）。A.类是对于众多对象的归纳；B.类的对象具备该类的所有特征；C.类是抽象的数据结构，而对象是具体的事件或事物等；D.在程序中，我们只能使用对象的成员，而不能直接使用类的成员；14、以下语句或语句组中，能正确进行字符串赋值的是（）。A.char*sp；*sp=right!；B.chars[lO]；s=right!；C.chars[10]；*s=right!；D.char*sp=right!;15、非空的循环单链表head的尾结点p↑满足（）。A．p↑.link=headB．p↑.link=NILC．p=NILD．p=head16、若长度为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.543612；B.453126；C.346521；D.234156；18、软件管理是软件工程化生产的重要环节，以下哪些是软件工程管理应包括的内容？（）。①人员组织；②进度安排；③．质量保证；④成本核算；A.①②；B.②③；C.②④；D.①②③④；19、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9B．11C．15D．不确定20、以下能对二维数组a进行正确初始化的语句是()。A.inta[2][]={{1,0,1},{5,2,3}};B.inta[][3]={{1,2,3},{4,5,6}};C.inta[2][4]={{1,2,3},{4,5},{6}};D.inta[][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层的结点数为（）。35101945608258111315233038414753647073788695A.6；B.7；C.8；D.9；24、以下正确的说法是____A.定义函数时，形参的类型说明可以放在函数体内B.return后边的值不能为表达式C.如果函数值的类型与返回值类型不一致，以函数值类型为准D.如果形参与实参类型不一致，以实参类型为准25、下列说法不正确的是（）。A．图的遍历是从给定的源点出发每一个顶点仅被访问一次B．遍历的基本算法有两种：深度遍历和广度遍历C．图的深度遍历不适用于有向图D．图的深度遍历是一个递归过程26、下面对于数组的定义正确的是（）。intM=10;constintN=9;staticintK=20;#defineJ50main(intargc,char*argv[]){intI;cinI;intarray1[I];———————————————①intarray2[M];———————————————②intarray4[K];———————————————③intarray3[N];———————————————④intarray5[J];——————————————⑤}A.①②③④⑤；B.②③④⑤；C.③④⑤；D.④⑤；27、执行完下列语句段后，i值为：（）intf(intx){return((x0)?x*f(x-1):2);}inti;i=f(f(1));A．2B.4C.8D.无限递归28、一个递归算法必须包括（）。A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分29、适用于折半查找的表的存储方式及元素排列要求为()A．链接方式存储，元素无序B．链接方式存储，元素有序C．顺序方式存储，元素无序D．顺序方式存储，元素有序30、在一棵m阶的B+树中,每个非叶结点的儿子数S应满足().A.21m≤S≤mB.2m≤S≤mC.1≤S≤21mD.1≤S≤2m31、设哈希表长为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）8447251521（2）1547258421（3）1521258447（4）1521254784则采用的排序是()。A.选择B.冒泡C.快速D.插入34、在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（）。A．直接插入排序B.冒泡排序C.快速排序D.直接选择排序35、定义如下结构体，那么以下的变量定义中，不正确的是（）。structnode{intj,k;}x,*p=&x;A．p-k=2；B．(*p).k=2；C．x.k=2；D．x-k=2；