资源描述：
《数据结构考试资料》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、一、判断正误1、线性表釆用链式存储，则链表中结点总数一定等于元素总数。2、栈是一种后进先出的线性表，因此，元素的进栈序列和出栈序列不可能相同。3、无论采用何种存储结构，队列的入队、出队次序一定相同。4、由三个不同关键字构造的二叉排序树的基本形态共有五种。5、若非空二叉树的先序、屮序遍历序列相同，则必为仅有一个根的二叉树。6、二叉链表存储的二叉树中结点总数为n,则空指针域总数必为n+1。7、n(>0)个权值作为叶子构造的哈夫曼树中结点总数为2n-1o8、森林的后序遍历与它对应的二叉树的中序遍历相同。9、折半查找的平均查找效率高于顺序查找，因此，查找某一元素时，折半查找所
2、需与关键字的比较次数一定少于顺序查找。10、二叉排序树的中序遍历序列按关键字递增有序。11、有向图的邻接表的第i个链表中表结点总数为该顶点的度。12、顺序表，链表，二叉链表，邻接表，散列表均为存储结构。13、选取散列函数时，冲突越少越好。14、冒泡，直接插入，归并，基数排序均为稳定排序。15、快速排序最坏的时间复杂度为O(N*logN)016、不稳定排序后，相同关键字元素的相对位置一定发生改变。17、直接插入排序适用于元素个数较少或初始序列基本有序情况。18、对称矩阵压缩存储后不具备随机存取的特点。19、在考虑存储结构的前提下，有向图的拓扑排序序列一定唯一。20、折半
3、查找要求元素必须按关键字有序，且只能釆用顺序存储结构。二、填空题1、数据的基本单位是,数据结构常见的逻辑结构有,存储结构有。2、数据结构的逻辑结构可视为一个二元组Data_Structure=(D,S),其中D是,S是O3、数据结构的抽象数据类型ADT是指一个数学模型及定义在该模型上的一组操作。它可用三元组(D,S,P)表示，其中D是数据对象，S是,P是4、设计一个好的算法应达到的目标是正确性、、和高效率低存储量。算法时间效率、空间效率的度量分别称为、。5、顺序表、链表分别通过、体现元素的前驱、后继的逻辑关系。6、在表长为n的顺序表中插入、删除元素时，在等概率条件下平
4、均移动元素的次数分别为、，具体移动的元素个数与有关。7、已知L为头指针的带头结点的单循坏链表(指针域为next),a.若R为尾指针，则满足的条件为,b.若该表为空表，则满足的条件是o8、已知五个元素ABCDE的进栈次序为ABCDE,a.若C为第一个出栈元素，则下一个出栈的元素可能是；b.能否得到出栈序列CDBEA、CEDAB?9、若三个元素ABC的进栈次序为ABC,则借助栈一共可以得到屮出栈序列？10、已知顺序存储的循坏队列中，f,r分别为队头、队尾指针，MAX为队列中存储单元的最大个数。若当队列中仅有一个空闲单元时视为队满，则队空、队满条件分别为、；一般情况下，队列
5、中元素个数可表示为o11>广义表A=((a,(b),c),(d),(e,f,g))的表长为，深度为,利用取表头、表尾运算表示原子e的表达式为o12、广义表中元素既可以是单原子，也可以是,广义表的两个基本操作是和13、10个结点二叉树至多有个叶子，最低高度为o14、83个结点的完全二叉树高度为,其中叶子个数为,一度结点个数为o15、n(n＞0)个结点的完全二叉树叶子个数为,一度结点个数为。16、高度为5的BST树结点总数至多，至少为,o17、n个叶子的哈夫曼树最高高度为,结点总数为o18、从本质上而言，森林的孩子兄弟链表与它转换所对应的二叉树的存储结构一致。19、n个顶
6、点的无向、有向完全图的边数分别是、,n个顶点的强连通图至少有条边。20、无向网的最小生成树的构造算法是和；n个顶点的无向网构造的最小生成树中边的条数为o21、构造散列表要解决的两个问题是；若将关键字序列的散列地址定位在100至110之间，则散列函数可表示为H(key)=。22＞从理论上讲，散列查找的算法效率为,但实际应用时，常常因为使查找速度有所降低。23、若关键字序列为正序，则直接插入、冒泡、简单选择、归并、快速、堆排序中排序效率最高的是和，此吋吋间复杂度为O24、希尔排序每趟的排序方法是,平均时间复杂度为;快速排序的平均时间复杂度为，最坏时间复杂度为o25、排序时
7、所需与关键字的比较次数仅与元素个数有关而与关键字的初始序列无关的排序方法是,若关键字个数为n个，则第一趟的比较次数为Q26、写出三种不稳定的排序方法的名称、和o27、n个元素进行起泡排序时，最好情况下只需进行次比较和次交换，最坏情况需进行次比较和次交换。三、综合题仁已知线性链表中结点的数据域、指针域依次为data、next,写出在表中删除*p结点的语句(设该结点存在后继)及p结点前插入爼结点语句。2、简述顺序表、链表的各自特点。3、简述链式存储中头结点、头指针；结点、元素的区别。4、n阶矩阵Aij(1Wi,jWn)或Aij(OWi,j^n-1)的上三
