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

《数据结构》复习题 填空 1 1、（数据元素）是数据的（基本）单位，也称（结点、元素、顶点、记录等）。 2、线性表的链式存储结构是指用地址（ ）的存储单元来存放线性表中的数据元素。 3、数据结构是研究程序设计中计算机的（操作对象）及其它们之间的（关系 ）等的学科. 4、（数据项）是数据的（最小）单位，一个数据元素由（若干个）（数据项）组成。 5、线性表的（顺序存储结构）是指用地址（连续）的存储单元来存放线性表中的数据元素。 6、学习数据结构的目的是，在处理实际问题时，能选择一种好的（数据结构）。 7、栈是（操作受限）的线性表。 8、数据的运算是通过（算法）来描述的，（算法）是由若干条（指令）组成的有穷序列，通俗地说，（算法）就是求解问题的（步骤）。 9、线性表中的元素之间的关系是一种（简单的邻接）关系。 10、线性表中的（开始）结点只有一个直接后继，没有直接前驱。 11、线性表中的（终端）结点只有一个直接前驱，没有直接后继。 12、顺序表中结点间的邻接关系是通过（存储位置）来反映的。 13、单链表中结点间的邻接关系是利用（指针）来表示的。 14、商品价目表中一种商品的信息（名称、价格）为一个数据元素，用单链表保存商品价目表时，该单链表的类型定义为（数据元素类型定义： typedef struct good char name[6];float price; datatype; 单链表类型定义为： typedef struct node datatype data;struct node * next; linklist; ）。 15、队列是特殊的线性表，进队只能在（ ）进行；出队只能在（ ）进行。 16、栈是特殊的线性表，也称为操作或运算（ ）的线性表，它的操作只能在（ ）进行。 填空 2 1 排序算法的稳定性是指关键字值（相同 ）的记录，经过排序后它们的相对位置是否发生变化。相对位置发生变化的算法称为（）算法，这类算法包括（）等。 2、对于有 N 个数据的待排序表，用选择排序法进行排序时，需要进行（ ）轮（遍）。 3、排序算法中的基本操作是（ ）和移动。 4、对于有 m 个数据的待排序表，用冒泡排序法进行排序时，最多需要进行（ ）轮（遍），最少可能需要进行（ ）轮（遍）。 5、查找算法中的基本操作是（ ）. 6、哈希函数是指 . 7 在顺序表中，用二分法查找数据0用二分法查找数据1 8、树的深度是指树中（ 结点层数的最大值 ）. 9、深度为 h 的满二叉树结点数是 2h-1 ，第i 1 i h 层上的结点数是 2i-1 。 10、深度为 h 的满二叉树就是 的树. 11、树的度是指树中结点（ ）。 12、深度为 h（h 1） 的满二叉树的度为 。 选择题 1 1一个算法至少要有（ C ）个输入和（ ）个输出。 A 0 、0 B 1，1 C 0，1 D 1，0 2 渐进时间复杂度为O 1 的算法的时间效率（ A ）渐进时间复杂度为O log2 n 的算法。 A 优于 B 不优于 3 对整数序列（3，2，6，4，5，1，7）进行快速排序，第一轮排序需要比较（ D ）次。 A 2 B 3 C 5 D 6 4 对整数序列（1，2，3，4，5，6，7）进行二分查找，查找2的比较次数为（ B ），查找8的比较次数为（ B ）。 A 2、6 B 2、3 C 3、4 D 5、6 5 二叉树的顺序存储结构仅适用于（ A ）；顺序存储结构中，每个结点至少有（ ）。 A 完全二叉树 、 1 B 满二叉树 、 1 C 完全二叉树 、 3 D 满二叉树 、 3 6 交换排序方法有（ B ）。 A 直接选择排序、起泡排序 B 快速排序、起泡排序 C 快速排序、 归并排序 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 C sq- front+1 % Max sq- rear 、sq- rear sq- front D sq-