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