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

《数据结构》复习题一、填空11、（数据元素）是数据的（基本）单位，也称（结点、元素、顶点、记录等）。2、线性表的链式存储结构是指用地址（）的存储单元来存放线性表中的数据元素。3、数据结构是研究程序设计中计算机的（操作对象）及其它们之间的（关系）等的学科.4、（数据项）是数据的（最小）单位，一个数据元素由（若干个）（数据项）组成。5、线性表的（顺序存储结构）是指用地址（连续）的存储单元来存放线性表中的数据元素。6、学习数据结构的目的是，在处理实际问题时，能选择一种好的（数据结构）。7、栈是（操作受限）的线性表。8、数据的运算是通过（算法）来描述的，（算法）是由若干条（指令）组成的有穷序列，通俗地说，（算法）就是求解问题的（步骤）。9、线性表中的元素之间的关系是一种（简单的邻接）关系。10、线性表中的（开始）结点只有一个直接后继，没有直接前驱。11、线性表中的（终端）结点只有一个直接前驱，没有直接后继。12、顺序表中结点间的邻接关系是通过（存储位置）来反映的。13、单链表中结点间的邻接关系是利用（指针）来表示的。14、商品价目表中一种商品的信息（名称、价格）为一个数据元素，用单链表保存商品价目表时，该单链表的类型定义为（数据元素类型定义：typedefstructgood{charname[6];floatprice;}datatype;单链表类型定义为：typedefstructnode{datatypedata;structnode*next;}linklist;）。15、队列是特殊的线性表，进队只能在（）进行；出队只能在（）进行。16、栈是特殊的线性表，也称为操作或运算（）的线性表，它的操作只能在（）进行。二、填空21排序算法的稳定性是指关键字值（相同）的记录，经过排序后它们的相对位置是否发生变化。相对位置发生变化的算法称为（）算法，这类算法包括（）等。2、对于有N个数据的待排序表，用选择排序法进行排序时，需要进行（）轮（遍）。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的满二叉树就是()的树.11、树的度是指树中结点（）。12、深度为h（h1）的满二叉树的度为()。三、选择题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二叉树的顺序存储结构仅适用于（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），队列空的条件为（）。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算法的时间复杂度是通过算法的（C）来度量的。A平均执行时间B执行时间C基本操作的次数D程序执行的平均时间13对序列（3，5，7，8，9）利用直接插入排序法插入6，使插入后仍然有序，则需移动记录的次数为（A）。A3B4C5D6四、选择题21、对整数序列（1，3，5，7，9，11，13）进行二分查找，查找1的比较次数为（），查找2的比较次数为（）。A2、3B3、3C3、4D2、42、渐进时间复杂度为O(n)的算法的时间效率（）渐进时间复杂度为O(log2(n))的算法。A优于B不优于3、对整数序列（1，2，3，4，5，6）进行快速排序，第一轮以1为轴排序时，需要比较（）次。A4B3C5D64、对序列（1，3，5，7）利用直接插入排序法插入6，使插入后仍然有序，则需移动记录的次数为（）。A1B2C3D4五、解答题二叉树遍历、顺序和链式存储结构。已知两个遍历序列，如何得到二叉树？哈夫曼树的建立、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)=Kmod7，分别用线性再散列法（设表的长度为9）、链地址法（拉链法）处理冲突，给出建立的散列表并计算成功和不成功时的平均查找长度。4二叉树如图一，请写出该二叉树中序、和后序遍历结果。若已知两个遍历序列，如何得到二叉树？5已知如图2所示的无向图，给出该图的邻接表、邻接矩阵。给出从顶点A开始按深度优先和广度优先搜索遍历得到的序列。BCAD图2E6给定一组权值1、2、3、4、5、8，构造以这些权值为叶子结点的哈夫曼树,要求左孩子的权值不大于右孩子的权值。并计算该二叉树的带权路径长度WPL。六、编写算法/算法理解1、顺序表的操作：插入、删除、查找、有序表的插入等2、单链表的操作：建立、插入、删除、查找、求长度、有序表的插入等3、二叉树的建立、遍历算法，递归和非递归。4、二分查找算法，递归和非递归。应用算法设计与分析。CABDFGHE