《数据结构》复习题_基本

1、数据结构复习题一、 填空 11、（数据元素）是数据的（基本）单位，也称（结点、元素、顶点、记录等）。2、线性表的链式存储结构是指用地址（ ）的存储单元来存放线性表中的数据元素。 3、数据结构是研究程序设计中计算机的（操作对象）及其它们之间的（关系 ）等的学科. 4、（数据项）是数据的（最小）单位，一个数据元素由（若干个）（数据项）组成。 5、线性表的（顺序存储结构）是指用地址（连续）的存储单元来存放线性表中的数据元素。 6、学习数据结构的目的是，在处理实际问题时，能选择一种好的（数据结构）。7、栈是（操作受限）的线性表。 8、数据的运算是通过（算法）来描述的，（算法）是由若干条（指令）组成的有

2、穷序列，通俗地说，（算法）就是求解问题的（步骤）。 9、线性表中的元素之间的关系是一种（简单的邻接）关系。10、线性表中的（开始）结点只有一个直接后继，没有直接前驱。11、线性表中的（终端）结点只有一个直接前驱，没有直接后继。12、顺序表中结点间的邻接关系是通过（存储位置）来反映的。13、单链表中结点间的邻接关系是利用（指针）来表示的。14、商品价目表中一种商品的信息（名称、价格）为一个数据元素，用单链表保存商品价目表时，该单链表的类型定义为（数据元素类型定义： typedef struct good char name6;float price; datatype; 单链表类型定义为： ty

3、pedef struct node datatype data;struct node * next; linklist; ）。15、队列是特殊的线性表，进队只能在（ ）进行；出队只能在（ ）进行。16、栈是特殊的线性表，也称为操作或运算（ ）的线性表，它的操作只能在（ ）进行。二、 填空 21 排序算法的稳定性是指关键字值（相同 ）的记录，经过排序后它们的相对位置是否发生变化。相对位置发生变化的算法称为（）算法，这类算法包括（）等。2、对于有 N 个数据的待排序表，用选择排序法进行排序时，需要进行（ ）轮（遍）。3、排序算法中的基本操作是（ ）和移动。4、对于有 m 个数据的待排序表，用冒泡

4、排序法进行排序时，最多需要进行（ ）轮（遍），最少可能需要进行（ ）轮（遍）。5、查找算法中的基本操作是（ ）.6、哈希函数是指( ).7 在有序顺序表（1,2,3,4,5,6）中，用二分法查找数据0，依次比较的关键字值为_，用二分法查找数据1，依次比较的关键字值为_。8、树的深度是指树中（ 结点层数的最大值 ）.9、深度为 h 的满二叉树结点数是( 2h-1 )，第i(1=i1） 的满二叉树的度为( )。三、 选择题 11一个算法至少要有（ C ）个输入和（ ）个输出。A 0 、0 B 1，1 C 0，1 D 1，02 渐进时间复杂度为O(1)的算法的时间效率（ A ）渐进时间复杂度为O(l

5、og2(n) 的算法。 A 优于 B 不优于3 对整数序列（3，2，6，4，5，1，7）进行快速排序，第一轮排序需要比较（ D ）次。 A 2 B 3 C 5 D 64 对整数序列（1，2，3，4，5，6，7）进行二分查找，查找2的比较次数为（ B ），查找8的比较次数为（ B ）。 A 2、6 B 2、3 C 3、4 D 5、65 二叉树的顺序存储结构仅适用于（ A ）；顺序存储结构中，每个结点至少有（ ）。A 完全二叉树 、 1 B 满二叉树 、 1 C 完全二叉树 、 3 D 满二叉树 、 36 交换排序方法有（ B ）。 A 直接选择排序、起泡排序 B 快速排序、起泡排序 C 快速排序

6、、 归并排序 D 堆排序、快速排序7 数据的运算是定义在数据的（ A ）结构，在数据的（ ）结构上实现的。A 逻辑、存储 B 存储、逻辑 C 逻辑、逻辑 D 存储、存储8 数据结构是一门研究（ C ）中计算机的操作对象以及它们之间的（ ）和（ ）等的学科。A 计算机、相对位置、关系 B 数据、关系、操作 C 程序设计、关系、操作 D 程序设计、运算、操作9 循环队列sq中，其队列满的条件为（ B ），队列空的条件为（ ）。A sq-rear+1=sq-front 、sq-rear =sq-front B (sq-rear+1)% Max=sq-front 、sq-rear =sq-front

7、C (sq-front+1)% Max=sq-rear 、sq-rear =sq-front D sq-rear =sq-front 、(sq-rear-1)% Max=sq-front10 顺序队列和链式队列的（ A ）结构相同，（ ）结构不同。A 逻辑、存储 B 存储、逻辑 11 如果结点A有三个兄弟，B是A的双亲，则结点B的度为（ C ）。 A 2 B 3 C 4 D 112 算法的时间复杂度是通过算法的（ C ）来度量的。A 平均执行时间 B 执行时间 C 基本操作的次数 D 程序执行的平均时间13 对序列（3，5，7，8，9）利用直接插入排序法插入6，使插入后仍然有序，则需移动记录的

8、次数为（ A ）。A 3 B 4 C 5 D 6四、 选择题 21、 对整数序列（1，3，5，7，9，11，13）进行二分查找，查找1的比较次数为（ ），查找2的比较次数为（ ）。 A 2、3 B 3、3 C 3、4 D 2、42、 渐进时间复杂度为O(n)的算法的时间效率（ ）渐进时间复杂度为O(log2(n) 的算法。 A 优于 B 不优于3、 对整数序列（1，2，3，4，5，6）进行快速排序，第一轮以1为轴排序时，需要比较（ ）次。 A 4 B 3 C 5 D 64、 对序列（1，3，5，7）利用直接插入排序法插入6，使插入后仍然有序，则需移动记录的次数为（ ）。A 1 B 2 C 3

9、D 4五、 解答题 二叉树遍历、顺序和链式存储结构。已知两个遍历序列，如何得到二叉树？哈夫曼树的建立、WPL.二叉排序树的建立哈希函数、哈希表的建立、计算ASL（成功、不成功）图的邻接表、邻接矩阵。深度优先和广度优先搜索遍历序列（生成树）。对关键字序列排序，写出直接选择排序、2路归并排序、快速排序、堆排序、冒泡排序算法进行排序的各趟结果。1 对整数序列（11，01，36，89，87，43，87）依次进行直接选择排序、2路归并排序、快速排序、堆排序、冒泡排序，分别写出排序过程。2、请画出输入序列为（21，01，26，99，87，43，17）时，建立的二叉排序树，并写出前序、中序、后序的遍历结果.3 在初始为空的散列表中依次插入关键字序列（2，5，4，3，1，6，7），散列函数为 H(K)=K mod 7，分别用线性再散列法（设表的长度为9）、链地址法（拉链法）处理冲突，给出建立的散列表并计算成功和不成功时的平均查找长度。4 二叉树如图一，请写出该二叉树中序、和后序遍历结果。若已知两个遍历序列，如何得到二叉树？ 5 已知如图2所示的无向图，给出该图的邻接表、邻接矩阵。给出从顶点A开始按深度优先和广度优先搜索遍历得到的序列。6给定一组权值1、2、3、4、5、8，构造以这些权值为叶子结点的哈夫曼树,要