1、1 套题 1 一、 选择题（每题 2 分，共 15 题，总计 30 分） 1 以下叙述中正确的是 _。 A 数组是数据的最小单位 B 数据对象就是一组数据元素的集合 C 顺序存储方式只能用于存储线形结构 D 树对应到的二叉树其根结点的右子树总是空的 2 一个数组的第一个元素的存储地址是 100，每个元素长度为 2，则第 5 个元素的存储地址是 _。 A 110 B 108 C 100 D 120 3 一个栈的入栈顺序是 a,b,c,d,e，则其出栈顺序不可能是 _。 A a,b,c,d,e B e,d,c,b,a C d,c,e,a,b D d,e,c,b,a 4 栈的特点是 _。 A 先进先
2、出 B 先进后出 C 随 即存取 D 链式实现 5 一个队列的入队顺序是 1， 2， 3， 4， 5，那么出队顺序是 _。 A 5， 4， 3， 2， 1 B 1， 2， 3， 5， 4 C 1， 2， 3， 4， 5 D 1， 3， 2， 4， 5 6 向一个长度为 10 的数组的第 5 个元素之前插入一个元素时，需向后移动 _个元素。 A 3B 5C 6 D7 7 若一棵二叉树有 101 个结点，且无度为 1 的结点，则叶结点的个数为 _。 A 48 B 49 C 50 D 51 8 高度为 6 的完全二叉树中第 4 层结点的个数为 _。 A 2 B 4 C 8 D 16 9 具有 n 个
3、顶点的无向完全图，其边数为 _。 A n B n(n-1) C n(n-1)/2 D n2 10 具有 n 个顶点的有向完全图，其边数为 _。 A n B n(n-1) C n(n-1)/2 D n2 11 在有 7 个顶点的无向图中至少有 _条边才能确保该图连通。 A 1 B 6 C 7 D 21 12 对于一个有 n 个顶点的无向图，若采用邻接矩阵表示法，则该矩阵的大小是 _。 A n-1 B n C (n-1)2 D n2 13 在序列 1， 10， 12， 15， 23， 40， 66， 77， 85 中利用直接查找，查找 15 所需的比较次数为 _。 A 2 B 3 C 4 D 6
4、14 采用顺序查找方法查找长度为 n 的线性表时，每个元素的平均查找长度为 _。 AO( n) B O(nlogn) C O(n2) D O(logn) 15 在待排序元素基本有序的前提下，效率最高的排序方法是 _。 A 插入排序 B 选择排序 C 快速排序 D 归并排序 二、 填空 题（每空 2 分，共 20 空，总计 40 分） 1 判定下列程序段的时间复杂度为 _，其中语句 Aij频度为 _ for(i=0;inext=_; p-next=s; t=p-data; p-data=_; s-data=_; 3 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较
5、次数最少的排序是 _，需要内存容量最多的排序是 _。 4 对线性表进行二分查找时，要求线性表必须 _。 5 对于一个头指针为 head 的带头结点的单链表，判定该链表为空的条件是 _，对于一个不带头指针的单链表，判定该链表为空的条件是 _。 6 数据的存储结构 是指 ，设有一批数据元素，为了方便地定位和读取某特定元素，数据结构宜采用_形式，为了方便地进行数据元素的插入删除操作，数据结构宜采用 _形式。 7 已知一棵二叉树，其先序序列为 ABCDE，中序序列为 CDBEA，则其后序序列为 _。 8 高度为 6 的二叉树，其结点个数最多为 _个，最少为 _个。 9 在线索二叉树中，若以 ltag
6、表示某结点的左标志域，以 lch 表示某结点的左孩子域，则结点 t 没有左子树的条件是。 5 10 在含有个 20 结点的二叉链表中有 _个空链域。 11 有 _个结点的二叉树将会呈现 5种不同的表现形式。 12如下图所示的 AOE网，其关键路径为 。 D F E C B A 3 5 2 1 2 3 2 3 三、 算法题（每题 8 分，共 2 题，总计 16分） 1、关键字序列 a,b,c， d 的链式存储如下，编写算法，通过更改指针实现关键字序列 a， d， c,b 的链式存储。 2、设计算法，现有一字符串“ 12468”（即该变量为字符数组，每个单元存放一个 char 型的值，分别为 1，
7、2， 4， 6， 8），若该字符串表示的是数值型的八进制数值，即（ 12468） 8，设计算法将它转换为十进制数并输出。 四、 操作题（每题 6 分，共 4 题，总计 24分） 1、 已知一棵树如下图所示，要求： 给出树的先根遍历序列和后根遍历序列（ 3 分） 将该树转化为二叉树（ 3分） 2、 设有一组关键字为 8,7,13,10,9,23,15，哈希函数为 H(key)=key MOD 7，按开放定址的线性探测再散列解决冲突，即增量序列为 1， 2， 3，构造表地址空间为 0-9 的哈希表。 a b c d head A B C D E F G H I J K 6 请画出该哈希表（ 3分）
8、 0 1 2 3 4 5 6 7 8 9 计算对关键字 23 进行查找时的查找长度并写出计算过程（ 3分） 3、下图为一个无向图 G 请给出该图的邻接表表示 (3 分 ) 依据你所作的邻接表，从 A 出发，给出该图的深度优先遍历序列（ 3 分） 4、下图所示为一棵 3 阶 B-树 请给出删除元素 25 之后的 3 阶 B-树 (3 分 ) 在的基础上，给出 插入 15 之后的 3 阶 B-树 （ 3分） A B C D E F 7 套题 3 一、选择题（共 10 题，每题 2 分，共 20 分） ： 1、 从逻辑上可以把数据结构分为（）两大类。 A） 动态结构、静态结构 B） 顺序结构、链式结
9、构 C） 线性结构、非线性结构 D） 初等结构、构造型结构 2、 下面关于线性表的叙述中，错误的是哪一个？（ ） A） 线性表采用顺序存储，必须占用一片连续的存储单元。 B） 线性表采用顺序存储，便于进行插入和删除操作。 C） 线性表采用链接存储，不必占用一片连续的存储单元。 D） 线性表采用链接存储，便于插入和删除操作。 3、 设无向图的顶点个数为 n，则该图最多有（ ）条边。 A) n-1 B) n(n-1)/2 C) n(n+1)/2 D) 0 4、对线性表进行二分查找时，要求线性表必须 （ ） A) 以顺序方式存储 B) 以顺序方式存储且元素有序 C) 以链式方式存储 D) 以链式方式
10、存储且元素有序 12 16 21 23 10 8 24 25 28 20 8 5、 下面给出的四种排序法中 ( )排序法是不稳定性排序法。 A) 插入 B) 冒泡 C) 二路归并 D) 堆 6、以下说法正确的是 _。 A) 数据元素是数据的最小单位 B) 数据项是数据的最小单位 C) 数据结构是带有结构的各数据项的集合 D) 数据结构是带有结构的数据元素的集合 7、 下列说法不正确的是（） A） 图的遍历是从给定的源点出发每一个顶点仅被访问一次 B） 遍历的基本算法有两种：深度遍历和广度遍历 C） 图的深度遍历不适用于有向图 D） 图的深度遍历是一个递归过程 8、 若一棵二叉树具有 10 个度
11、为 2 的结点， 5 个度为 1 的结点，则度为 0 的结点个数是（） A) 9 B) 11 C) 15 D) 不确定 9、栈和队列的共同点是 （） A) 都是先进先出 B) 都是先进后出 C) 只允许在端点处插入和删除元素 D) 没有共同点 10、有关二叉树下列说法正确的是 （） A） 二叉树的度为 2 B） 一棵二叉树的度可以小于 2 C） 二叉树中至少有一个结点的度为 2 D) 二叉树中任何一个结点的度都为 2 二、 填空题 （ 共 15 空，每空 2 分，共 30 分 ） 1、 当一个 AOV 网用邻接表表示时，可按下列方法进行拓扑排序。 1）查邻接表中入度为 _的顶点，并进栈； 2）
12、若栈不空，则 输出栈顶元素 Vj，并退栈； 查 Vj 的直接后继 Vk，对 Vk 进行 入度处理，处理方法是_ _； 3）若栈空时，输出顶点数小于图的顶点数，说明有 _，否则拓扑排序完成。 2、 给定一组数据 6， 2， 7， 10， 3， 12以它构造一棵哈夫曼树，则树 深度 为 _，带权路径长度WPL 的值为 _。 9 3、 在单链表 p 结点之后插入 s 结点的操作是： _ 。 4、设有一批数据元素，为了最快地存取某元素，数据结构宜采用 _结构，为了方便地插入一个数据元素，数据结构宜采用 _结构。 5、 在一个无向图中，所有顶点的度数之和等于所有边数倍，在一个有向图中，所有顶点的入度之和
13、等于所有顶点出度之和的倍。 6、对于一个头指针为 head 的带头结点的单链表，判定该表为空表的条件是 _。 7、 二叉树的第 i层上最多含有结点数为 。 8、 具有 N 个结点的二叉树，采用二叉链表存储，共有 _个空链域。 9、 一个有 n(n0)个结点的图，最少有个连通分量，最多有个连通分量。 三、 算法题（共 3题，每题 5 分，共 15 分） 1、 写一算法， 求带有头结点的单链表的表长。 2、请用非递归算法写出 折半查找的算法。 3、请写出 直接插入排序的算法。 四、操作题（共 6 题，第 1 题 10 分，其余每题 5 分，共 35 分） 1、输入一个正整数序列（ 53， 17，
14、12， 66， 58， 70， 87， 25， 56， 60），试完成下列各题。（ 1）按次序构造一棵二叉排序树 BS。 (2) 依此二叉排序树，如何得到一个从大到小的有序序列？（ 3）画出在此二叉排序树中删除 结点 66 后的树结构。（ 10 分） 2、 已知一组关键字为（ 19， 14， 23， 01， 68， 20， 84， 27， 55， 11， 10， 79） ， 则按哈希函数 H(key)=key mod 13 和链地址法处理冲突构造哈希表。（ 5 分） 3、 对于下面的有向图 G，请写出所有可能的拓扑序列。（ 5 分） 4、 已知 一棵 二叉树前序为 ABDEGCF，中序为 DB
15、GEACF，画出这棵二叉树 。 （ 5分） B A C D E 10 5、写出对 数据（ 15， 9， 7， 8， 20， -1， 7， 4） 进行快速排序中第一趟的序列。（ 5分） 6、 无向图 G=(V， E)， 其中： V=a， b， c， d， e， f， E=(a， b)， (a， e)， (a， c)， (b， e)， (c， f)， (f， d)， (e，d)， 写出 对该图进行深度优先遍历 的一个序列。 （ 5分） 套题 4 一、选择题（共 10 题，每题 2 分，共 20 分） ： 1、 以下属于逻辑结构的是（） 。 A） 顺序表 B） 哈希表 C） 有序表 D） 单链表 2
16、、 下面关于线性表的叙述中，错误的是哪一个？（ ） 。 A） 线性表采用顺序存储，必须占用一片连续的存储单元。 B） 线性表采用顺序存储，便于进行插入和删除操作。 C） 线性表采用链接存储，不必占用一片连续的存储单元。 D） 线性表采用链接存储，便于插入和删除操作。 3、 设无向图的顶点个数为 n，则该图最多有（）条边。 A) n-1 B) n(n-1)/2 C) n(n+1)/2 D) 0 4、 线性表是具有 n 个（ ）的有限序列（ n0）。 A) 表元素 B) 字符 C) 数据元素 D) 数据项 5、 下面给出的四种排序法中 ( )排序法是稳定性排序法。 A) 希尔 B) 快速 C) 二
17、路归并 D) 堆 6、 若需在 O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ） 。 A) 快速排序 B) 堆排序 C) 归并排序 D) 直接插入排序 7、 下列说法不正确的是（） 。 A） 图的遍历是从给定的源点出发每一个顶点仅被访问一次 B） 遍历的基本算法有两种：深度遍历和广度遍历 C） 图的深度遍历不适用于有向图 D） 图的深度遍历是一个递归过程 8、 若一棵二叉树具有 14 个度为 2 的结点， 5 个度为 1 的结点，则度为 0 的结点个数是（） 。 A) 9 B) 11 C) 15 D) 不确定 9、 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储
