一、单项选择题
1.不带头结点的单链表head为空的判断条件是( )。
A.head==NULL B.head->next==NULL C.head->next==head D.head!=NULL 2.链表不具有的特点是( )。
A.可随机访问任一元素 B.插入删除不需要移动元素 C.不必事先估计存储空间 D.所需空间与线性表长度成正比
3. 设输入序列为A,B,C,D,借助一个栈不可以得到的输出序列是( )。 A. A,B,C,D B. A,C,D,B C. D,C,B,A D. D,A,B,C 4.栈和队列都是（ ）。
A.顺序存储的线性表 B.链式存储的线性表
C.限制存取点的线性结构 D.限制存取点的非线性结构 5. 串的长度是（ ）。
A.串中不同字符的个数 B. 串中不同字母的个数 C.串中所含字符的个数且字符个数大于0 D.串中所含字符的个数 6. 栈和队列的主要区别在于（ ）。
A.它们的逻辑结构不一样 B.它们的存储结构不一样 C.所包含的运算个数不一样 D.插入删除运算的限定不一样
7.从具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，平均需比较（ ）个结点。
A.n B.n/2 C.(n-1)/2 D.(n+1)/2 8.线性表是具有n个（ ）的有限序列。
A. 表元素 B. 字符 C. 数据元素 D. 信息项
9.某二叉树的前序和后序序列正好相同，则该二叉树一定是（ ）的二叉树。 A. 空或只有一个结点 B. 高度等于其结点数 C. 任一结点无左孩子 D. 任一结点无右孩子
10.下列排序算法中,第一趟排序完毕后,其最大或最小元素一定在其最终位置上的算法是（ ）。 A. 归并排序 B. 直接插入排序 C. 快速排序 D. 冒泡排序 11.深度为n的二叉树中所含叶子结点的个数最多为（ ）个。
n-1 n
A.2n B.n C.2 D.2-1
12.某数组第一个元素的存储地址为100，每个元素的长度为2，则第五个元素的地址是（ ）。 A.110 B.108 C.100 D.120 13.串是（ ）。
A.一些符号构成的序列 B.一些字母构成的序列 C.一个以上字符构成的序列 D.任意有限个字符构成的序列
14.在一个具有n个顶点的无向图中,要连通全部顶点至少需要（ ）条边。 A.n B.n+1 C.n-1 D.n/2 15.下列四个关键词序列中,（ ）不是堆。
A.{05,23,16,68,94,72,71,73} B.{05,16,23,68,94,72,71,73} C.{05,23,16,73,94,72,71,68} D.{05,23,16,68,73,71,72,94}
16.在一个单链表中，已知(*q)结点是(*p)结点的前驱结点，若在(*q)和(*p)之间插入(*s)结点,则执行（ ）。
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;
17.设输入序列为的1,2,3,4,借助一个栈可以得到的输出序列是（ ）。 A.1,3,4,2 B.3,1,4,2 C.4,3,1,2 D.4,1,2,3
18.二分查找法要求查找表中各元素地键值必须是（ ）排列。 A. 递增或递减 B. 递增 C. 递减 D.无序
19下列排序算法中,某一趟结束后未必能选出一个元素放其最终位置上的是（ ）。 A. 堆排序 B. 冒泡排序 C. 快速排序 D. 直接插入排序
20.设有7000个无序的元素,希望用最快的速度挑选出其中前5个最大的元素,最好选用（ ）法。 A.冒泡排序 B.快速排序 C.堆排序 D.基数排序 21.任何一个无向连通图的最小生成树（ ）。
A. 只有一棵 B. 有一棵或多棵 C. 一定有多棵 D. 可能不存在 22.3个结点可构成（ ）个不同形态的二叉树。
A.2 B.3 C.4 D.5
23.设有6000个无序的元素,希望用最快的速度挑选出其中前6个最大的元 素,最好选用（ ）法。
A.冒泡排序 B.快速排序 C.堆排序 D.基数排序
24.某数组第一个元素的存储地址为200，每个元素的长度为4，则第五个元素的地址是（ ）。 A.210 B.208 C.216 D.220 25.在一个具有n个顶点的完全无向图的边数为 （ ）。 A.n(n+1)/2 B. n(n-1)/2 C.n(n-1) D. n(n+1)
26.将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的右孩子编号为（ ）。 A.98 B.99 C.50 D.48
27.在线索二叉树中,结点(*t)没有左子树的充要条件是（ ）。 A. t->left==NULL B. t->ltag==1 C.t->ltag==1 && t->left==NULL D.以上都不对
28. 设二叉树根结点的层次为0，一棵高度为h 的满二叉树中的结点个数是( )。
hh-1hh+1
A. 2 B. 2 C. 2-1 D. 2-1
29.对于键值序列{72,73,71,23,94,16,5,68,76,103}用筛选法建堆，必须从键值为（ ）的结点开始。
A.103 B. 72 C.94 D.23
30.对有n个记录的有序表采用二分查找，其平均查找长度的量级为（ ）。 A.O(n) B. O(nlog2n) C. O(1) D. O(log2n)
31．若在线性表中采用折半查找法查找元素，该线性表必须满足（ ）。 A．元素按值有序 B．采用顺序存储结构
C．元素按值有序，且采用顺序存储结构 D．元素按值有序，且采用链 式存储结构 32．下面4个序列中，只有（ ）满足堆的定义。
A. 13,27,49,76,76,38,85,97 B. 76,38,27,49,76,85,13,97 C. 13,76,49,76,27,38,85,97 D. 13,27,38,76,49,85,76,97
33．设有50行60列的二维数组A[50][60]，其元素长度为4字节，按行优先顺序存储，基地址为200，则元素A[18][25]的存储地址为（ ）。
A．3700 B．4376 C．3900 D．4620
34．在含n个顶点e条边的无向图的邻接矩阵中，零元素的个数为（ ）。
22
A．e B．2e C．n-e D．n-2e
35．邻接表的存储结构下图的深度优先遍历类似于二叉树的（ ）。 A．先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历
二、填空题
1. 按顺序存储方法存储的线性表称为_______ ，按链式存储方法存储的线性表称为_______。 2. 算法分析的两个主要方面是____________和____________。
3.在n个结点的顺序表中插入一个结点需平均移动 个结点，具体移动次数取决于 。 4.采用二叉链表存储结构，具有n个结点的二叉树一共有 个指针域，其中 指针域为空。 5.在有序表(15,23,24,48,45,62,85)中二分查找关键词23时所需进行的关键词比较次数为______。 6.图的存储结构最常用的有 和邻接表。
7.二叉树的存储结构有 和链式存储结构。
8.对于一棵二叉树，设叶子结点数为n0,度为2的结点数为n2,则n0和n2的关是 。 9.一般树的存储结构有双亲表示法、孩子兄弟表示法和 。 10.每个结点只有 链接域的链表叫做单链表。
11.从逻辑关系上讲，数据结构主要分为两大类：线性结构和 。 12.100个结点的完全二叉树的叶子结点数为 。 13.图的存储结构最常用的有 和邻接矩阵。
14.二叉树的存储结构有顺序存储结构和 。
15.一般树的存储结构有双亲表示法、孩子链表表示法和 。 16.二叉树的遍历方式有三种： 、 和后根遍历。 17.深度为8的（根的层次号为1）满二叉树有 个叶子结点。 18.n个的顶点的连通图的生成树有 条边。
19.如果一个有向图中没有 ，则该图的全部顶点可以排成一个拓扑序列。 20．下面程序段的时间复杂度是_______ 。
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) a[i][j]=0;
三、应用题
1. 有一棵二叉树如下图所示，分别指出其前序、中序遍历的结点序列。
A
B E
F C H
J I G D
2. 有二叉树先序序列为：ABCDEF,中序序列为：CBAEDF,试画出该二叉树。 3. 给定表（45,36,56,6,64,78,8,96），按数据元素在表中的次序构造一棵 二叉排序树。
4. 试分别画出具有3个结点的树和有具有3个结点的二叉树的所有不同形态。 5. 用普里姆算法(Prim)算法求出下图的最小生成树。
6.根据下图给出的二叉树，求出先序、中序和后序遍历的结点序列。
a
b c
d e
f
7. 把下图中的二叉树转化为森林。
8.已知数据序列为{12,5,9,20,6,31,24},对该数据序列进行排序，试写出快速排序每趟的结果。
四、算法设计题
1. 判断单链表head(head指向表头)是否是递增的。
2.试设计一算法，删除单链表head(head指向表头)中数据域data的值为x的结点。 3. 假定一棵二叉树用二叉链表存储，试编写求出二叉树中1度结点个数的算法。
4. 假设线性表用带表头结点的单向链表head表示，试写出删除表中所有data域值为零的元素的算法。
因篇幅问题不能全部显示，请点此查看更多更全内容