数据结构简答题.doc

试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？答：顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。优点：存储密度大（1），存储空间利用率高。缺点：插入或删除元素时不方便。链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（next-next 和 rear, 查找时间都是O(1)。若用头指针来表示该链表，则查找终端结点的时间为O(n)。假定有四个元素A, B, C, D依次进栈，进栈过程中允许出栈，试写出所有可能的出栈序列。共有14种可能的出栈序列，即为：ABCD, ABDC，ACBD, ACDB，BACD，ADCB，BADC，BCAD, BCDA，BDCA,CBAD, CBDA，CDBA, DCBA什么是队列的上溢现象？一般有几种解决方法，试简述之。在队列的顺序存储结构中，设队头指针为front，队尾指针为rear，队列的容量（即存储的空间大小）为maxnum。当有元素要加入队列（即入队）时，若rear=maxnum，则会发生队列的上溢现象，此时就不能将该元素加入队列。对于队列，还有一种“假溢出”现象，队列中尚余有足够的空间，但元素却不能入队，一般是由于队列的存储结构或操作方式的选择不当所致，可以用循环队列解决。一般地，要解决队列的上溢现象可有以下几种方法：（1）可建立一个足够大的存储空间以避免溢出，但这样做往往会造成空间使用率低，浪费存储空间。（2）要避免出现“假溢出”现象可用以下方法解决：第一种：采用移动元素的方法。每当有一个新元素入队，就将队列中已有的元素向队头移动一个位置，假定空余空间足够。第二种：每当删去一个队头元素，则可依次移动队列中的元素总是使front指针指向队列中的第一个位置。第三种：采用循环队列方式。将队头、队尾看作是一个首尾相接的循环队列，即用循环数组实现，此时队首仍在队尾之前，作插入和删除运算时仍遵循“先进先出”的原则。如何知道循环队列是空还是满?第一，采用计数器来判断，空时，计数器为0，满时，计数器为maxsize；第二，另设一个布尔变量以匹别队列的空和满；第三，少用一个元素的空间，约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；说明线性表,栈,队列的异同点相同点:都是线性结构,都是逻辑结构的概念,都可以用顺序存储或者链表存储. 栈和队列两种特殊的线性表,即受限的线性表,只是对插入, 删除运算加以限制.不同点:1 运算规则不同: 线性表为随机存取. 栈只允许在一端进行插入.删除运算. 列队只允许在一端进行插入,另一端进行删除运算.2 用途不同,堆栈用于子程序调用和保护现场,队列用于多道作业处理,指令存储及其他运算等等.当你为解决某一问题而选择数据结构时,应从哪些方面考虑?通常从两方面考虑：第一是算法所需的存储空间量；第二是算法所需的时间。对算法所需的时间又涉及以下三点：（1）程序运行时所需输入的数据总量。（2）计算机执行每条指令所需的时间。（3）程序中指令重复执行的次数简述逻辑结构与存储结构的关系答：数据的逻辑结构反映数据元素之间的逻辑关系（即数据元素之间的关联方式或“邻接关系”），数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。数据运算是数据结构的一个重要方面,试举例说明两个数据结构的逻辑结构和存储方式完全相同,只是对于运算的定义不同,因而两个结构具有显著不同的特性,则这两个数据结构是不同的.答：栈和队列的逻辑结构相同，其存储表示也可相同（顺序存储和链式存储），但由于其运算集合不同而成为不同的数据结构。线性表有两种存储结构：一是顺序表，二是链表。试问：(1)两种存储表示各有哪些主要优缺点?(2)如果有n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构?为什么?(3)若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么，应采用哪种存储结构?为什么?解答：(1)顺序存储是按索引（隐含的）直接存取数据元素，方便灵活，效率高，但插入、删除操作时将引起元素移动，因而降低效率；链接存储内存采用动态分配，利用率高，但需增设指示结点之间有序关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作十分简单。(2)应选用链接表存储结构。其理由是，链式存储结构用一组任意的存储单元依次存储线性表里各元素，这里存储单元可以是连续的，也可以是不连续的。这种存储结构，在对元素作插入或删除运算时，不需要移动元素，仅修改指针即可。所以很容易实现表的容量扩充。(3)应选用顺序存储结构。其理由是，每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。由此，只要确定了起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。而链表则是一种顺序存取的存储结构。2、用线性表的顺序结构来描述一个城市的设计和规划合适吗?为什么?不合适。因为一个城市的设计和规划涉及非常多的项目，很复杂，经常需要修改、扩充和删除各种信息，才能适应不断发展的需要。有鉴于此，顺序线性表不能很好适应其需要，故是不合适的。3、在单链表和双向表中，能否从当前结点出发访问到任一结点?在单链表中只能由当前结点访问其后的任一结点，因为没有指向其前驱结点的指针。而在双向链表中，既有指向后继结点的指针又有指向前驱结点的指针，故可由当前结点出发访问链表中任一结点。对链表设置头结点的作用是什么?(至少说出两条好处)(1)对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，所要做的都是修改前一结点的指针域，因为任何元素结点都有前驱结点。若链表没有头结点，则首元素结点没有前驱结点，在其前插入结点或删除该结点时操作会复杂些。(2)对带头结点的链表，表头指针是指向头结点的非空指针，因此空表与非空表的处理是一样的。在单链表、双链表和单循环表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去？若可以，其时间复杂度各为多少？1.单链表。当我们知道指针p指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。2.双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。3.单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。