北京理工大学2013级数据结构B(A卷)_范例.doc

一、选择题 1、从逻辑结构上可以把数据结构分为【 C 】。 A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 2、在一个长度为n的顺序存储的线性表中，向第i个元素（1(i(n+1）之前插入一个新元素时，需要从后向前依次后移【 B 】个元素。 A、n-i B、n-i+1 C、n-i-1 D、i 3、链表结构不具有下列【 B 】特点。 A、插入和删除无需移动元素 B、可随机访问链表中的任意元素 C、无需实现分配存储空间 D、所需空间与结点个数成正比。 4、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行【 C 】。 A、s-next = p-next; p-next = s; B、p-next = s-next; s-next = p; C、q-next = s; s-next = p; D、p-next = s; s-next = q; 5、一个栈的入栈序列是1，2，3，4，5，则栈不可能输出的序列是【 C 】。 A、54321 B、45321 C、43512 D、12345 6、判断一个队列Q（元素最多为M个）为空的条件是【 C 】。 A、Q-rear – Q-front = M B、Q-rear – Q-front -1 ==M C、Q-rear == Q-front D、Q-rear + 1 == Q-front 7、在一个链队列中，假设f和r分别指向队首和队尾，则插入s所指结点的运算是【 A 】。 A、r-next = s; r=s; B、f-next = s; f=s; C、s-next = r; r=s; D、s-next = f; f=s; 8、深度为5的二叉树至多有【 A 】个结点。 A、31 B、32 C、16 D、10 9、在一非空二叉树的中序遍历序列中，根结点的右边【 A 】。 A、只有右子树上的所有结点 B、只有右子树上的部分结点 C、只有左子树上的所有结点 B、只有左子树上的部分结点 10、如果一棵完全二叉树有1001个结点，则其叶子结点个数为【 D 】。 A、250 B、500 C、502 D、490 11、在一个图中，所有顶点的度数之和是所有边数的【 C 】倍。 A、1/2 B、1 C、2 D、4 12、采用邻接表存储的图的深度优先遍历算法类似于二叉树的【 A 】。 A、先序遍历 B、中序遍历 C、后序遍历 D、按层遍历 13、一个有n个顶点的无向图最多有【 D 】条边。 A、n B、n(n-1) C、2n D、n(n-1)/2 14、静态查找表与动态查找表的根本区别在于【 B 】。 A、它们的逻辑结构不同 B、施加在其上的操作不同 C、所包含的数据元素类型不同 D、存储实现不一样 15、顺序查找适用于存储结构为【 C 】的线性表。 A、哈希存储 B、压缩存储 C、顺序存储或链式存储 D、索引存储 16、若一颗二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足【 B 】。 A、所有结点均无孩子 B、所有结点均无右孩子 C、只有一个叶子结点 D、是一颗满二叉树 17、二叉排序树是【 B 】。 A、每一分支结点的度均为2的二叉树 B、中序遍历得到一升序序列的二叉树 C、按从左到右顺序编号的二叉树 D、每一分支结点的值均小于左子树上所有结点的值，又大于右子树上所有结点的值 18、具有12个记录的序列，采用冒泡排序最少的比较次数是【 C 】。 A、1 B、144 C、11 D、66 19、堆的形状是一棵【 C 】。 A、二叉排序树 B、满二叉树 C、完全二叉树 D、平衡二叉树 20、在一个包含n个顶点e条边的无向图的邻接矩阵中，零元素的个数为【 D 】。 A、e B、2e C、n2-e D、n2-2e 二、判断对错 【 x 】1、具有n个顶点的连通图至少有n条边。 【 x 】2、链表的单个结点内部的存储空间可以是不连续的。 【 ( 】3、栈和队列的共同点是只允许在端点处插入和删除元素。 【 ( 】4、使用循环队列可以解决队列顺序存储时的假溢出问题。 【 x 】5、要想通过遍历序列还原为惟一二叉树，应当知道其先序序列和后序序列。 【 ( 】6、若一个结点是某二叉树子树的中序遍历序列的第一个结点，则它也必是该子树的后序遍历序列的第一个结点。 【 x 】7、完全二叉树可采用顺序存储结构存储，非完全二叉树则不能。 【 ( 】8、对于一棵含有n个结点的完全二叉树，将其结点按从上到下且从