2016期末复习题（一）
数据结构
一、单项选择题（在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。每小题2分，共40分）
1、串的长度是（ ）。
A、串中不同字母的个数 B、串中不同字符的个数
C、串中所含字符的个数，且大于0 D、串中所含字符的个数
2、若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。 A、S1的栈底位置为0，S2的栈底位置为n+1 B、S1的栈底位置为0，S2的栈底位置为n/2 C、S1的栈底位置为1，S2的栈底位置为n D、S1的栈底位置为1，S2的栈底位置为n/2
3、队列操作的原则是（）。 A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除
4、有64个结点的完全二叉树的深度为（）（根的层次为1）。 A、8 B、7 C、6 D、5
5、在有n个结点的二叉链表中，值为非空的链域的个数为（）。 A、n-1 B、2n-1 C、n+1 D、2n+1
6、带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（）。 A、第i行非∞的元素之和 B、第i列非∞的元素之和
C、第i行非∞且非0的元素个数 D、第i列非∞且非0的元素个数
7、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级
1
为（）。 A、0(n) B、0(log2n) C、0(nolg2n) D、0(n2)
8、若表R在排序前已按键值递增顺序排列，则（）算法的比较次数最少。 A、直接插入排序 B、快速排序 C、归并排序 D、选择排序
9、下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。 A、选择 B、冒泡 C、归并 D、堆
10、若线性表最常用的操作是存取第i个元素及其前趋的值，则采用（）存储方式节省时间。 A、单链表 B、双链表 C、单循环链表 D、顺序表
11、对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（）遍历实现编号。 A、无序 B、中序 C、后序
D、从根开始的层次遍历
12、某二叉树的中序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。 A、空或只有一个结点 B、高度等于其结点数 C、任一结点无左孩子 D、任一结点无右孩子
13、下列排序算法中，时间复杂度不受数据初始状态影响，恒为0（nlog2n）的是（） A、堆排序 B、冒泡排序 C、直接选择排序 D、快速排序
14、下列排序算法中，（）算法可能会出现下面情况：初始数据有序时，花费的时间反而最
2
多。
A、堆排序 B、冒泡排序 C、快速排序 D、SHELL排序
15、一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（）。 A、2 3 4 1 5 B、5 4 1 3 2 C、2 3 1 4 5 D、1 5 4 3 2
16、设循环队列中数组的下标范围是1-n，其头尾指针分别为f和r，则其元素个数为（）。 A、r-f B、r-f+1
C、(r-f) mod n+1 D、(r-f+n) mod n 17、若某链表最常用的操作是在最后一个结点之后插入一个结点删除最后一个结点，则采用（）存储方式最节省时间。 A、单链表 B、双链表
C、带头结点的双循环链表 D、单循环链表
18、一棵非空的二叉树的先序序列和后序序列正好相同，则该二叉树一定满足（）。 A、其中任意一结点均无左孩子 B、其中任意一结点均无右孩子 C、其中只有一个结点 D、是任意一棵二叉树
19、一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为（）。 A、0 B、1 C、2 D、不确定
20、数组A[1..5,1..6]每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[5,5]的地址为（）。
A、1140 B、1145 C、1120 D、1125
二、判断题（对的打“√”，错的打“×”。每小题1分，共10分） 1、线性表的唯一存储形式是链表。（）
2、已知指针P指向链表L中的某结点，执行语句P：=P∧.next不会删除该链表中的结点。（）
3、在链队列中，即使不设置尾指针也能进行入队操作。（）
3