外语外贸大学研究生入学考试初试试题样卷.docVIP

PAGE2

外语外贸大学研究生入学考试初试试题样卷

专业：网络空间安全/电子信息考试科目：846《数据结构》

考生注意：本试卷共4大题，满分150分。考试时间为3小时

所有答案均写在答题纸上，在此答题无效。

一、选择题（15小题，每题2分，共30分）

1.栈和队列的共同特点是()。

A.只允许在端点处插入和删除元素

B.都是先进后出

C.都是先进先出

D.没有共同点

2.用链接方式存储的队列，在进行插入运算时()。

A.仅修改头指针B.头、尾指针都要修改

C.仅修改尾指针D.头、尾指针可能都要修改

3.树最适合用来表示()。

A.有序数据元素B.无序数据元素

C.元素之间具有分支层次关系的数据D.元素之间无联系的数据

4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10进制)，A[2][2]存放位置在676，每个元素占一个空间，问A[3][3]存放在什么位置？（）。

A．688B．678C．692D．696

5．下列四种排序中（）的空间复杂度最大。

A.快速排序B.冒泡排序C.希尔排序D.堆

6.设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）

A.BADCB.BCDAC.CDABD.CBDA

7.设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）。

A.9B.10C.11D.12

8.下面程序的时间复杂为（）

for（i=1，s=0；i=n；i++）{t=1；for(j=1；j=i；j++)t=t*j；s=s+t；}

A.O(n)B.O(n2)C.O(n3)D.O(n4)

9．设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为

A.2，3，5，8，6B.3，2，5，8，6

C.3，2，5，6，8D.2，3，6，5，8

10.设某强连通图中有n个顶点，则该强连通图中至少有（）条边。

A.n(n-1)B.n+1C.nD.n(n+1)

11.一个栈的入栈序列是：a,b,c,d,e,则栈的不可能的输出序列是（）

A.edcbaB.decbaC.dceabD.abcde

12.若存储图G的邻接矩阵是对称矩阵，则G（）

A.一定是无向图B.一定是连通无向图C.可能是无向图D.一定是有向图

13.一个链栈的栈顶指针是topNode，则执行出栈操作时（栈非空），用topElement保存被删除结点的数据元素，则执行（）

A.topElement=top;top=topNode.next;

B.topElement=topNode.element;

C.topNode=topNode.next;topElement=topNode.element;

D.topElement=topNode.element;topNode=topNode.next;

14.下列说法正确的是（）

A.数据元素是具有独立意义的最小标识单位

B.原子类型的值不可再分解

C.原子类型的值由若干个数据段组成

D.结构类型的值不可再分解

15.设哈希表长为20，待哈希的关键字个数小于20个。若采用除留余数法H(key)=key%p来设计哈希函数，按照课本建议，下列最合适的p值是（）。

A．17B．18C．19D．20

二、简答题（4小题，每题10分，共40分）

1.评价一个好的算法，您是从哪几方面来考虑的？

2.试比较顺序表和链表的优缺点和适用情况。

3.什么是递归？递归定义包含哪些要素？递归程序在执行时，应借助于什么数据结构来完成？

4.列举5种以上