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

《《数据结构》复习题_基本.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

3、e[6];floatprice;}datatype;单链表类型定义为：typedefstructnode{datatypedata;structnode*next;}linklist;）。15、队列是特殊的线性表，进队只能在（）进行；出队只能在（）进行。16、栈是特殊的线性表，也称为操作或运算（）的线性表，它的操作只能在（）进行。二、填空21排序算法的稳定性是指关键字值（相同）的记录，经过排序后它们的相对位置是否发生变化。相对位置发生变化的算法称为（）算法，这类算法包括（）等。2、对于有N个数据的待排序表，用选择排序法进行排序时，需要进行（）轮

4、（遍）。3、排序算法中的基本操作是（）和移动。4、对于有m个数据的待排序表，用冒泡排序法进行排序时，最多需要进行（）轮（遍），最少可能需要进行（）轮（遍）。5、查找算法中的基本操作是（）.6、哈希函数是指().7在有序顺序表（1,2,3,4,5,6）中，用二分法查找数据0，依次比较的关键字值为____________，用二分法查找数据1，依次比较的关键字值为_________________。8、树的深度是指树中（结点层数的最大值）.9、深度为h的满二叉树结点数是(2h-1)，第i(1<=i<=h)层上的结点数是(2i-1)。10、深度为h的满

5、二叉树就是()的树.11、树的度是指树中结点（）。12、深度为h（h>1）的满二叉树的度为()。三、选择题11一个算法至少要有（C）个输入和（）个输出。A0、0B1，1C0，1D1，02渐进时间复杂度为O(1)的算法的时间效率（A）渐进时间复杂度为O(log2(n))的算法。A优于B不优于3对整数序列（3，2，6，4，5，1，7）进行快速排序，第一轮排序需要比较（D）次。A2B3C5D64对整数序列（1，2，3，4，5，6，7）进行二分查找，查找2的比较次数为（B），查找8的比较次数为（B）。A2、6B2、3C3、4D5、65二叉树的顺序存储结

6、构仅适用于（A）；顺序存储结构中，每个结点至少有（）。A完全二叉树、1B满二叉树、1C完全二叉树、3D满二叉树、36交换排序方法有（B）。A直接选择排序、起泡排序B快速排序、起泡排序C快速排序、归并排序D堆排序、快速排序7数据的运算是定义在数据的（A）结构，在数据的（）结构上实现的。A逻辑、存储B存储、逻辑C逻辑、逻辑D存储、存储8数据结构是一门研究（C）中计算机的操作对象以及它们之间的（）和（）等的学科。A计算机、相对位置、关系B数据、关系、操作C程序设计、关系、操作D程序设计、运算、操作9循环队列sq中，其队列满的条件为（B），队列空的条件

7、为（）。Asq->rear+1==sq->front、sq->rear==sq->frontB(sq->rear+1)%Max==sq->front、sq->rear==sq->frontC(sq->front+1)%Max==sq->rear、sq->rear==sq->frontDsq->rear==sq->front、(sq->rear-1)%Max==sq->front10顺序队列和链式队列的（A）结构相同，（）结构不同。A逻辑、存储B存储、逻辑11如果结点A有三个兄弟，B是A的双亲，则结点B的度为（C）。A2B3C4D112算法的时间

8、复杂度是通过算法的（C）来度量的。A平均执行时间B执行时间C基本操作的次数D程序执行的平均时间13对序列（3，5，7，8，9）利用直接插入排序法插入6