数据结构考试资料.docVIP

一、判断正误 1、线性表采用链式存储，则链表中结点总数一定等于元素总数。 2、栈是一种后进先出的线性表，因此，元素的进栈序列和出栈序列不可能相同。 3、无论采用何种存储结构，队列的入队、出队次序一定相同。 4、由三个不同关键字构造的二叉排序树的基本形态共有五种。 5、若非空二叉树的先序、中序遍历序列相同，则必为仅有一个根的二叉树。 6、二叉链表存储的二叉树中结点总数为n，则空指针域总数必为n+1。 7、n(0)个权值作为叶子构造的哈夫曼树中结点总数为2n-1。 8、森林的后序遍历与它对应的二叉树的中序遍历相同。 9、折半查找的平均查找效率高于顺序查找，因此，查找某一元素时，折半查找所需与关键字的比较次数一定少于顺序查找。 10、二叉排序树的中序遍历序列按关键字递增有序。 11、有向图的邻接表的第i个链表中表结点总数为该顶点的度。 12、顺序表，链表，二叉链表，邻接表，散列表均为存储结构。 13、选取散列函数时，冲突越少越好。 14、冒泡，直接插入，归并，基数排序均为稳定排序。 15、快速排序最坏的时间复杂度为O（N*logN）。 16、不稳定排序后，相同关键字元素的相对位置一定发生改变。 17、直接插入排序适用于元素个数较少或初始序列基本有序情况。 18、对称矩阵压缩存储后不具备随机存取的特点。 19、在考虑存储结构的前提下，有向图的拓扑排序序列一定唯一。 20、折半查找要求元素必须按关键字有序，且只能采用顺序存储结构。 二、填空题 数据的基本单位是_____，数据结构常见的逻辑结构有_____，存储结构有____。 数据结构的逻辑结构可视为一个二元组Data_Structure=（D，S），其中D是_____，S是_____。 数据结构的抽象数据类型ADT是指一个数学模型及定义在该模型上的一组操作。它可用三元组（D，S，P）表示，其中D是数据对象，S是_____，P是_____ 设计一个好的算法应达到的目标是正确性、_____、_____和高效率低存储量。算法时间效率、空间效率的度量分别称为_____、_____。 5、顺序表、链表分别通过_____、_____体现元素的前驱、后继的逻辑关系。 6、在表长为n的顺序表中插入、删除元素时，在等概率条件下平均移动元素的次数分别为_____、_____，具体移动的元素个数与_____有关。 7、已知L为头指针的带头结点的单循环链表（指针域为next），a．若R为尾指针，则满足的条件为______，b．若该表为空表，则满足的条件是______。 8、已知五个元素ABCDE的进栈次序为ABCDE，a．若C为第一个出栈元素，则下一个出栈的元素可能是_____；b．能否得到出栈序列CDBEA______、CEDAB______？ 9、若三个元素ABC的进栈次序为ABC，则借助栈一共可以得到______中出栈序列？ 10、已知顺序存储的循环队列中，f，r分别为队头、队尾指针，MAX为队列中存储单元的最大个数。若当队列中仅有一个空闲单元时视为队满，则队空、队满条件分别为_____、_____；一般情况下，队列中元素个数可表示为_____ 。 11、广义表A=((a，(b)，c)，(d)，(e，f，g))的表长为_____，深度为_____，利用取表头、表尾运算表示原子e的表达式为_____。 12、广义表中元素既可以是单原子，也可以是_____，广义表的两个基本操作是_____和_____。 13、10个结点二叉树至多有_____个叶子，最低高度为_____。 14、83个结点的完全二叉树高度为_____，其中叶子个数为_____，一度结点个数为_____。 15、n(n0)个结点的完全二叉树叶子个数为_____，一度结点个数为_____。 16、高度为5的BST树结点总数至多，至少为_____，_____。 17、n个叶子的哈夫曼树最高高度为_____，结点总数为_____。 18、从本质上而言，森林的孩子兄弟链表与它转换所对应的二叉树的_____存储结构一致。 19、n个顶点的无向、有向完全图的边数分别是_____、_____，n个顶点的强连通图至少有_____条边。 20、无向网的最小生成树的构造算法是_____和_____；n个顶点的无向网构造的最小生成树中边的条数为_____。 21、构造散列表要解决的两个问题是_____；若将关键字序列的散列地址定位在100至110之间，则散列函数可表示为H（key）=_____。 22、从理论上讲，散列查找的算法效率为_____，但实际应用时，常常因为_____使查找速度有所降低。 23、若关键字序列为正序，则直接插入、冒泡、简单选择、归并、快速、堆排序中排序效率最高的是_____和_____，此时时间复杂度为__________。 24