《数据结构》模拟试卷er及答案.doc

模拟试卷一 单选题（每题 2 分，共20分） 以下数据结构中哪一个是线性结构？( ) A. 有向图 　　 B. 队列 C. 线索二叉树 　　 D. B树 在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下( )语句序列。 A. p=q; p-next=q; B. p-next=q; q-next=p; C. p-next=q-next; p=q; D. q-next=p-next; p-next=q; 以下哪一个不是队列的基本运算？（ ） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成( )个不同的字符串？ A.14 B.5 　　 C.6 　　 D.8 由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 A． 11 B.35 C. 19 D. 53 图一 该二叉树结点的前序遍历的序列为( )。 E、G、F、A、C、D、B B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. E、G、A、C、D、F、B 该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F　　　　　　 B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. B、D、C、A、F、G、E 该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B 　　　 B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D 　　　　 D. E、G、A、C、D、F、B 下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建堆的结果?( ) A. a，g，h，m，n，p，q，x，z 　 B. a，g，m，h，q，n，p，x，z C. g，m，q，a，n，p，x，h，z D. h，g，m，p，a，n，q，x，z 填空题（每空1分，共26分） 数据的物理结构被分为_________、________、__________和___________四种。 对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_________，在表尾插入元素的时间复杂度为____________。 向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是________________;删除一个结点时，需要执行的操作是______________________________（假设栈不空而且无需回收被删除结点）。 对于一棵具有n个结点的二叉树，一个结点的编号为i(1≤i≤n)，若它有左孩子则左孩子结点的编号为________，若它有右孩子，则右孩子结点的编号为________，若它有双亲，则双亲结点的编号为________。 当向一个大根堆插入一个具有最大值的元素时，需要逐层_________调整，直到被调整到____________位置为止。 以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为________。 表示图的三种常用的存储结构为_____________、____________和_______________。 对于线性表（70，34，55，23，65，41，20）进行散列存储时，若选用H（K）=K %7作为散列函数，则散列地址为0的元素有________个，散列地址为6的有_______个。 在归并排序中，进行每趟归并的时间复杂度为______，整个排序过程的时间复杂度为____________，空间复杂度为___________。 在一