资源描述：
《数据结构考试重点题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、问答题：1.简述逻辑结构与存储结构的关系.答：数据的逻辑结构反映数据元素之间的逻辑关系（即数据元素之间的关联方式或“邻接关系”），数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。2.在什么情况下使用顺序表比链表好？答：若线性表的总长度基本稳定，且很少进行插入和删除操作，但要以最快的速度存取线性表中的元素。3.简述二路归并排序思想.？答：将两个有序表合并为一个有序表。1个元素的表总是有序的，所以对n个元素的待排序列，每个元素可看成1个有序子表。对子表两两合并生成个子表，所得子表除最后一个子表长度
2、可能为1外，其余子表长度均为2。再进行两两合并，直到生成n个元素按关键码有序的表。4.在单链表和双向表中，能否从当前结点出发访问到任一结点?答：在单链表中只能由当前结点访问其后的任一结点，因为没有指向其前驱结点的指针。而在双向链表中，既有指向后继结点的指针又有指向前驱结点的指针，故可由当前结点出发访问链表中任一结点。5.简述线性表，栈和队列的异同？答：栈和队列是操作位置受限的线性表，即对插入和删除的位置加以限制，栈是仅允许在表的一端进行插入和删除的线性表，因而是后进先出表，队列是只允许在表的一端进行插入，另一端进行删除的
3、线性表，因而是先进先出表。6.已知一组元素（46,25,78,62,18,34,12,40,73），试画出按元素排列顺序输出而生成的二叉排序树？答：4625781834621240737．画出对长度为10的有序表进行二分查找的一棵判断树，并求其等概率时查找成功的平均查找长度？答：判断树52813694710ASL=（1+2+2+3+3+3+3+4+4+4）/10=2.98.“数据结构”这一术语有两种含义，一是操作为一门课程的名称，二是作为一个科学的概念，作为科学概念，且目前尚无公认定义，一般认为，讨论数据结构要包括三个方
4、面，一是数据的逻辑结构，二是数据的存储结构，三是对数据进行操作（运算），而数据类型是值的集合和操作的集合，可以看作是已实现了的数据结构，后者是前者的一种简化情况。9.简述顺序表和链表存储方式的特点？答：顺序表可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率；而链表内存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序表方便，但结点的插入、删除操作较简单。10.为什么说栈是一种后进先出表?答：栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插
5、入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为后进先出表（LIFO--LastINFirstOut表）。11.判断下列序列是否是堆。若不是堆，则把它们依次调整为堆。(1)(100，85，98，77，80，60，82，40，20，10，66)。(2)(100，98，85，82，80，77，66，60，40，20，10)。(3)(100，85，40，77，80，60，66，98，82，10，
6、20)。(4)(10，20，40，60，66，77，80，82，85，98，100)。答：根据堆的定义可知堆中元素满足下面中的某一个式子的关系，┌≤k2i┌≥k2i①ki或②ki└≤k2i＋1└≥k2i＋1因此(1)、(2)和(4)序列是堆。(3)不是堆。(3)调整为100,98,66,85,80,60,40,77,82,10,20后成为堆。12.有5个元素,其进栈次序为A、B、C、D、E,在各种可能的出栈次序中,以元素C、D最先出栈(即C第一个且D第一个出栈)的次序有哪几个?答：三个：CDEBA，CDBEA，CDBAE
7、13．试述栈的基本性质?答：由栈的定义可知，这种结构的基本性质综述如下：(1)集合性。栈是由若干个元素集合而成，当没有元素的空集合称为空栈；(2)线性结构。除栈底元素和栈顶元素外，栈中任一元素均有唯一的前驱元素和后继元素；(3)受限制的运算。只允许在栈顶实施压入或弹出操作，且栈顶位置由栈指针所指示；(4)数学性质。当多个编号元素依某种顺序压入，且可任意时刻弹出时，所获得的编号元素排列的数目，恰好满足卡塔南数列的计算，即：Ｃn＝Ｃn2n/(n＋1)其中，n为编号元素的个数，Cn是可能的排列数目。14.对链表设置头结点的作用
8、是什么?答：(1)对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，所要做的都是修改前一结点的指针域，因为任何元素结点都有前驱结点。若链表没有头结点，则首元素结点没有前驱结点，在其前插入结点或删除该结点时操作会复杂些。(2)对带头结点的链表，表头指针是指向头结点的非空指针，因此空表与非空表的处理是一样的
