一、选择题
1、从逻辑结构上可以把数据结构分为【 C 】。 A、动态结构和静态结构
B、紧凑结构和非紧凑结构 D、内部结构和外部结构
C、线性结构和非线性结构
2、在一个长度为n的顺序存储的线性表中，向第i个元素（1?i?n+1）之前插入一个新元素时，需要从后向前依次后移【 B 】个元素。 A、n-i
B、n-i+1
C、n-i-1
D、i
3、链表结构不具有下列【 B 】特点。 A、插入和删除无需移动元素 C、无需实现分配存储空间
B、可随机访问链表中的任意元素 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 C、Q->rear == Q->front
B、Q->rear – Q->front -1 ==M D、Q->rear + 1 == Q->front
7、在一个链队列中，假设f和r分别指向队首和队尾，则插入s所指结点的运算是【 A 】。
A、r->next = s; r=s; C、s->next = r; r=s;
B、f->next = s; f=s; D、s->next = f; f=s;
8、深度为5的二叉树至多有【 A 】个结点。
A、31
B、32
C、16
D、10
9、在一非空二叉树的中序遍历序列中，根结点的右边【 A 】。
A、只有右子树上的所有结点 C、只有左子树上的所有结点
B、只有右子树上的部分结点 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 】。
1
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、压缩存储 D、索引存储
C、顺序存储或链式存储
16、若一颗二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足【 B 】。
A、所有结点均无孩子 C、只有一个叶子结点
B、所有结点均无右孩子 D、是一颗满二叉树
17、二叉排序树是【 B 】。
A、每一分支结点的度均为2的二叉树 B、中序遍历得到一升序序列的二叉树 C、按从左到右顺序编号的二叉树
D、每一分支结点的值均小于左子树上所有结点的值，又大于右子树上所有结点的值
18、具有12个记录的序列，采用冒泡排序最少的比较次数是【 C 】。
A、1
B、144
C、11
D、66
19、堆的形状是一棵【 C 】。
A、二叉排序树 C、完全二叉树
B、满二叉树 D、平衡二叉树
C、n2-e
D、n2-2e
20、在一个包含n个顶点e条边的无向图的邻接矩阵中，零元素的个数为【 D 】。
二、判断对错
【 x 】1、具有n个顶点的连通图至少有n条边。
【 x 】2、链表的单个结点内部的存储空间可以是不连续的。 【 ? 】3、栈和队列的共同点是只允许在端点处插入和删除元素。 【 ? 】4、使用循环队列可以解决队列顺序存储时的假溢出问题。
【 x 】5、要想通过遍历序列还原为惟一二叉树，应当知道其先序序列和后序序列。 【 ? 】6、若一个结点是某二叉树子树的中序遍历序列的第一个结点，则它也必是该
子树的后序遍历序列的第一个结点。 【 x 】7、完全二叉树可采用顺序存储结构存储，非完全二叉树则不能。
2
A、e B、2e
【 ? 】8、对于一棵含有n个结点的完全二叉树，将其结点按从上到下且从左至右按1
至n进行编号，则对其任意一个编号为i的结点，如果它有左孩子，则其左孩子结点的编号为2i。 【 ? 】9、哈夫曼树的所有子树也都是哈夫曼树。
【 x 】10、当图的边较少而结点较多时，求其最小生成树用Prim算法比用Kruskal算
法效率更高。
三、 填空题
1、向量的第一个元素的存储地址是200，每个元素的长度是3，那么第6个元素的存储地址是 。 答案：215
2、在一个带头结点的单链表中，p所指结点既不是首元结点，也不是尾元结点，删除p结点的语句序列是 、 、 。 答案: q=p，p=p->next，free(q)
3、设堆栈有足够的存储空间，那么向堆栈中插入一个数据元素，即入栈的操作过程是 、 。 答案: 存入数据元素，栈顶指针加1
4、一般情况下，向循环队列中插入数据元素时，需要判满队列是否已经满了，判断条件是： 。 答案: (rear+1)%MaxSize == front
6、已知循环队列用数组data[1…n]存储元素值，front和rear分别表示队头和队尾指针，则当前队列中元素的个数为 。 答案: (n+rear-frone)%n或(n+rear-frone) mod n
7、深度为k的二叉树最多有 个结点，深度为k的完全二叉树最少有 个结点（k≥1）。 答案: 2k-1，2k-1
8、如以{2,3,6,7,9}作为叶子结点的权值构造哈夫曼树，则其最短带权路径长度为 。 答案: 55
10、已知某二叉树的中序序列和前序序列分别为42758136、12457836，则它的后序序列为 。
3
北京理工大学2013级数据结构B试题(A卷)_答案
