《数据结构》
Part1
一．选择
1. 组成数据的基本单位是（）
A）数据项 B）数据类型 C）数据元素 D）数据变量
2．算法分析的目的是（）
A）找出数据结构的合理性 B）研究算法的输入/输出关系
C）分析算法的效率以求改进 D）分析算法的易读性
3．在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（） A）O(1) B）0(n) C）O(n^2) D）O(nlog2n)
4．若线性表采用顺序存储结构，每个元素占用4个存储单元，第一个元素的存储地址为100，则第12个元素的存储地址是（）
A）112 B）144 C）148 D）412
5．下面关于线性表的叙述中，错误的是（）
A）顺序表使用一维数组实现的线性表 B）顺序表必须占用一片连续的存储单元.
C）顺序表的空间利用率高于链表 D）在单链表中,每个结点只有一个链域. 6．在需要经常查找结点的前驱与后继的情况下，使用（）比较合适
A）单链表 B）双链表 C）顺序表 D）循环链表
7．队列通常采用的两种存储结构是（）
A）顺序存储结构和链式存储结构 B）散列方式和索引方式
C）链表存储结构和线性存储结构 D）线性存储结构和非线性存储结构
8．在一个单链表中，若删除p所指结点的后继结点，则执行（）
A）p->next=p->next->next；B）p=p->next；p->nex=p->next->next；
C）p->next=p->next； D）p=p->next->next；
9．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间
A）单链表 B）仅有头指针的单循环链表 C）双链表 D）仅有尾指针的单循环链表
10．按二叉树的定义，具有三个结点的二元树共有（）种形态。
A）3 B）4 C）5 D）6
11．任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）A）发生改变 B）不发生改变 C）不能确定 D）以上都不对
12．深度为5的二叉树至多有（）个结点
A）16 B）32 C）31 D）10
13．在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，那么度为0的结点数为（）个。
A）4 B）5 C）6 D）7
14．对于一个具有n个顶点的无向图，若采用邻接表表示，则存放表头结点的数组(顶点表)的大小为（）
A）n B）n+1 C）n-1 D）n/2
15．静态查找表和动态查找表二者的根本差别在于（）
A）它们的逻辑结构不同 B）施加在其上的操作不同
C）所包含的数据元素的类型不一样 D）存储实现不一样
二．填空
1．某程序的时间复杂性为(3n+nlog2n+n2+8),其数量级表示为________。
2．线性表L=(a1,a2,…,an)采用顺序结构存储,假定在不同的位置上插入的概率相同，则插入一个新元素平均需要移动的元素个数是_________ 。
3. 对于一株具有n个结点的树，该树中所有结点的度数之和为______。
4. 在一个图中,所有顶点的度数之和等于所有边数的______________倍。
5. 一棵二叉树有67个结点,这些结点的度要么是0，要么是2。这棵二元树中度数为2的结点有______________个。
6．在一个无向图的邻接表中，若表结点的个数是m，则图中边的条数是_____。
7．采用堆排序、快速排序、冒泡排序，对初态有序的表，最省时间的是______ 。
8．设二叉树结点的先根序列为ABDECFGH，中根序列为DEBAFCHG,则二元树中叶结点是_________.
9．一个哈夫曼(Huffman)树有19个结点，则其叶结点的个数是______。
10.栈S和队列Q的初始状态皆为空,元素a1,a2,a3,a4,a5和a6依次通过S栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3,a5,a4,a6,a2,a1，则栈S至少应该容纳_______ 个元素。
三．判断
1．线性表的链式存储结构优于顺序行储结构。（）
2．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（）
3．对于n个记录的集合进行归并排序，存最坏的情况下所需要的时间是O(n^2)。（）4．表中的每一个元素都有一个前驱和后继元素。（）
5．进栈操作push(x，s)作用于链接栈时，无须判满。（）
6．只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。（）
7．在索引顺序表查找方法中，对索引顺序表可以使用顺序表查找方法，也可以使用二分查找方法。（）
8．数据元素是数据的最小单位。（）
9．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（）
10．按中序遍历一棵二叉排序树所得到的中序遍历序列是一个递增序列。（）
四．简答
1. 对于下图所示的树：
(1) 写出先序遍历得到的结点序列；(2) 画出转换后得到的二叉树。
2．请画出与下列二元树对应的森林。
五．算法设计
1．已知一个int类型的数组arra，其长度为n，要求用冒泡排序算法对其从小到大排序，请实现该算法，（要求后面开始循环，大的数值下沉）。
2．利用一个栈实现以下递归函数的非递归计算：
P n (x)=
⎪
⎩
⎪
⎨
⎧
>
=
=
-
-
-
-
1
1
)
(
)1
(2
)
(
2
2
1
2
1
n
n
n
x
P
n
x
xP
x
n
n
