数据结构简答题

1、试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？答：顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。优点：存储密度大（=1）,存储空间利用率高。缺点：插入或删除元素时不方便。链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值， 另一部分存放表示结点间关系的指针优点：插入或删除元素时很方便， 使用灵活。缺点：存储密度小（1）,存储空间利用率低。 顺 序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较

2、大，且其主要操作是插入、删除操作，则采用链表。作拘绒性嶷的两种基本的存储结构；顺序裘和错表。它们在存龍和提作上各賞优缺!顺序表链表1，方法简单，各种高级直亶中咅E 有数组，容易实现V2不用为衰乔结点用的逻辑关系,而噌加额外的存储开销，萍储密度 大了 3.具有按元素序号陋机谊间 的持点，査找連彥快.1.插入、删除时，貝 裝找到对应前驱结点. 修改指针麗可，无需移2.釆用珂态存储分 配，不会适成内存浪费 和淙出.缺点.h插入删除撓作眄需碧移动元 翥平垛移动大釣袁中一半的元 靶 对元薰较多的顺序表散率低.Z米用静态空1可分配，需要预先 分配足够大的存储空麻含造成内 存胡浪费和隘出.1. 在有些唐言中

3、，不 支持指計，不容易实2、需要用额外空闾存 储建注恚的关系，存储 密度小沃不能腿机访 问、查扶时要从头培针遍历.一棵度为2的有序树与一棵二叉树有何区别 ？答：一棵度为二的有序树与一棵二叉树的区别在于：有序树的结点次序是相对于另一结点而言的，如果有序树中的子树只有一个孩子时，这个孩子结点就无须区分其左右次序而二叉树无论其孩子数是否为 2，均需确定其左右次序，也就是说二叉树的结点次序不是相 对于另一结点而言而是确定的。三. 算法的度仅与诃題的规模梱关吟？不，事实上，算肚的时间复杂度不仅与问題的熾模相关，还与输入丈例中的兀素取值等相关， 但在最坏的情况匸 其时何复杂度就是只与求解问题的规模相关的况

4、们在讨论时间良朵度 时，一股就是以最坏情况下的时何疑杂度为准的。四、常用的存储裘爪方袪有唧儿种？常 舟 的 存 储 表 亦 方 法 有 四 种： 顺序存储方注：它是把遐辑I"相嘟的结电存储在物理位置相如的存储单兀里皓方風的逻 再关.系由存简甲兀的邻按天薈来休规口由此得到的存備義不称为顺房存猪结构 讎接存储方法它不耍求暹辑上相觀的结点在物理位置上亦相鄭"结办创的還辑关系悬由 附加的折计宇段表亦的.由此得到的存碎表示称为叢式存蒔結构n 累引存箭方也土除锂丈存曾结点忙息外.还建立帽加的當廟表来标识结点加地址 做列存砖方注：就是很据結臨的关键字直接汁第出该结点的存储地址"

5、 为什么在取循环链表屮设置尾指件比设置化摘廿更好？答主甩指计是指向経端第点的指针.用它廉春审单餚环进表可以便得査找谜表的开怕结虑 利塔瑞结点都很方Wb设一帯头结贞的单猫坏链表.具尾猜廿为皿雷.则卄始第点科缆瑞 結点的位置分别 rear-ncxt-cxi和盹嗽査找时闾都是0(1).若用头折针來表莎该谜表， 则査找终端结点的时间为0(心何时选用嗽序表、何时选用能表作为能性表的存福第构为宜°答：在丈际战用中，血很据冥体阿题的要*和性JE来选样顾序我或僅覆作対线性競的存储 垢构， 通 常有以 卞 几方而的 考 虑 】基哩间的考虑L出耍求存槪的线性表畏度亜化不大，易F事先确定其大小时.为1 存

6、需空闻，立采用顺序義反乙十线性表长度变化大莽以估计英存踊现模时.来用动 盡 惟 表 作 为 存 皤 结 构 为 好. 2基于时间的考虑若线性表的操杵主婆是进行在找，很少做捕入利制除操作时，采用咂序 表歎存篠第构为宜；反之，科需耍对纸性芸竝柑嗾繁地播入咸珮除等的操作时，宜采用链 表做存需箱陶“并且，若漣表的插入利韵除主要发上在表前首尾两端，則采川凰指併表耶的 单循外诜表为宜口简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据 类型。数据是对客观事物的符号表示。 在计算机科学中是指所有能输入到计算机中并被计算机程序 处理的符号的总称。数据元素是数据的基本单位， 在计算机

7、程序中通常作为一个整体进行考虑和处理。数据对象是性质相同的数据元素的集合，是数据的一个子集。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。存储结构是数据结构在计算机中的表示。数据类型是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩 展。试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。解：抽象数据类型包含一般数据类型的概念， 但含义比一般数据类型更广、 更抽象。一般数 据类型由具体语言系统内部定义， 直接提供给编程者定义用户数据， 因此称它们为预定义数据类型。抽象数据类型通常由编程者

8、定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高， 更能为其他用户提供良好的使用接口。描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一处理。线性表的两种存储结构各有哪些优缺点？ 线性表具有两种存

9、储结构即顺序存储结构和链接存储结构。线性表的顺序存储结构可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降 低效率：而在链接存储结构中内存采用动态分配， 利用率高，但需增设指示结点之间关系的 指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作较简单。对于线性表的两种存储结构，如果有n个线性表同时并存，而且在处理过程中各表的长度会动态发生变化，线性表的总数也会自动改变，在此情况下，应选用哪一种存储结构？为 什么？应选用链接存储结构，因为链式存储结构是用一组任意的存储单元依次存储线性表中的各元 素，这里存储单元可以是连续的，也可以是不连续的： 这种存

10、储结构对于元素的删除或插入运算是不需要移动元素的，只需修改指针即可，所以很容易实现表的容量的扩充。对于线性表的两种存储结构，若线性表的总数基本稳定，且很少进行插入和删除操作，但 要求以最快的速度存取线性表中的元素，应选用何种存储结构？试说明理由。应选用顺序存储结构，因为每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。 因此，只要确定了其起始位置，线性表中的任一个数据 元素都可随机存取，因此，线性表的顺序存储结构是一种随机存取的存储结构，而链表则是一种顺序存取的存储结构。在单循环链表中设置尾指针比设置头指针好吗？为什么？设尾指针比设头指针好。尾指针是指向终

11、端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear-next-next和rear,查找时间都是 0（1）。若用头指针来表示该链表，则查找终端结点的时间为0（ n）。假定有四个元素 A, B, C, D依次进栈，进栈过程中允许出栈，试写出所有可能的出栈序列。共有14种可能的出栈序列，即为：ABCD, ABDC ACBD, ACDB BACD, ADCB, BADC, BCAD, BCDA BDCA,CBAD, CBDACDBA, DCBA什么是队列的上溢现象？ 一般有几种解决方法，

12、试简述之。在队列的顺序存储结构中，设队头指针为front，队尾指针为rear，队列的容量（即存储的空间大小）为 max num。当有元素要加入队列（即入队）时，若rear=max num，则会发生队 列的上溢现象，此时就不能将该元素加入队列。对于队列，还有一种“假溢出”现象，队列 中尚余有足够的空间，但元素却不能入队，一般是由于队列的存储结构或操作方式的选择不 当所致，可以用循环队列解决。一般地，要解决队列的上溢现象可有以下几种方法：（1）可建立一个足够大的存储空间以避免溢出，但这样做往往会造成空间使用率低，浪费 存储空间。（2）要避免出现“假溢出”现象可用以下方法解决：第一种：采用移动元素的

13、方法。 每当有一个新元素入队， 就将队列中已有的元素向队头移动 一个位置，假定空余空间足够。第二种：每当删去一个队头元素，则可依次移动队列中的元素总是使front指针指向队列中的第一个位置。第三种：采用循环队列方式。将队头、队尾看作是一个首尾相接的循环队列，即用循环数组 实现，此时队首仍在队尾之前，作插入和删除运算时仍遵循“先进先出”的原则。如何知道循环队列是空还是满 ？第一，采用计数器来判断，空时，计数器为0,满时，计数器为 maxsize;第二，另设一个布尔变量以匹别队列的空和满； 第三，少用一个元素的空间，约定入队前，测试尾指针在循 环意义下加1后是否等于头指针，若相等则认为队满（注意：

14、rear所指的单元始终为空）；1. 数据結构和数摇类空胸个概倉之何有区别吗？苓：简单地说，敬据结构定义了一组按某些关系结含在一起的数组元索. 数裾类型不仅苣茨了一组带皓构的数据元素，而且还在算上定义了一组操 虹2. 简述线性给构与非戏性結构的不同点.答：线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的 逻辑关系是多对多的.说明线性表，栈，队列的异同点相同点：都是线性结构，都是逻辑结构的概念，都可以用顺序存储或者链表存储 栈和队列两种 特殊的线性表，即受限的线性表，只是对插入，删除运算加以限制.不同点：1运算规则不同：线性表为随机存取栈只允许在一端进行插入 删除运算列队只 允许在一

15、端进行插入，另一端进行删除运算2用途不同，堆栈用于子程序调用和保护现场，队列用于多道作业处理，指令存储及其他运算当你为解决某一问题而选择数据结构时，应从哪些方面考虑？通常从两方面考虑：第一是算法所需的存储空间量；第二是算法所需的时间。 对算法所需的时间又涉及以下三点：（1）程序运行时所需输入的数据总量。（2）计算机执行每条指令所需的时间。（3）程序中指令重复执行的次数简述逻辑结构与存储结构的关系答：数据的逻辑结构反映数据元素之间的逻辑关系（即数据元素之间的关联方式或“邻接关系”），数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。数据运算是数据结构的一个重要方面，试举

16、例说明两个数据结构的逻辑结构和存储方式完全相同，只是对于运算的定义不同，因而两个结构具有显著不同的特性，则这两个数据结构是不同的答：栈和队列的逻辑结构相同，其存储表示也可相同（顺序存储和链式存储），但由于其运算集合不同而成为不同的数据结构。线性表有两种存储结构：一是顺序表，二是链表。试问：（1）两种存储表示各有哪些主要优缺点？（2）如果有n个线性表同时并存， 并且在处理过程中各表的长度会动态发生变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？（3）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么，应采用哪种存储结构？为什么？解答

17、：（1）顺序存储是按索引（隐含的）直接存取数据元素，方便灵活，效率高，但插入、删除操作时将引起元素移动，因而降低效率；链接存储内存采用动态分配，利用率高，但需增设指示结点之间有序关系的指针域， 存取数据元素不如顺序存储方便， 但结点的插入、删 除操作十分简单。（2）应选用链接表存储结构。其理由是，链式存储结构用一组任意的存储单元依次存储线性表里各元素，这里存储单元可以是连续的，也可以是不连续的。 这种存储结构，在对元素作插入或删除运算时，不需要移动元素，仅修改指针即可。所以很容易实现表的容量扩充。（3）应选用顺序存储结构。其理由是，每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线

18、性表中的序号成正比的常数。由此，只要确定了起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。而链表则是一种顺序存取的存储结构。2、用线性表的顺序结构来描述一个城市的设计和规划合适吗?为什么？不合适。因为一个城市的设计和规划涉及非常多的项目，很复杂，经常需要修改、扩充和删除各种信息，才能适应不断发展的需要。有鉴于此，顺序线性表不能很好适应其需要，故是不合适的。3、在单链表和双向表中，能否从当前结点出发访问到任一结点？在单链表中只能由当前结点访问其后的任一结点，因为没有指向其前驱结点的指针。而在双向链表中，既有指向后继结点的指针又有指向前驱结点的指针，故可由当前结点出发访问链表中任一结点。对链表设置头结点的作用是什么 ？（至少说出两条好处）（1）对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，所要做的都是修改前一结点的指针域，因为任何元素结点都有前驱结点。若链表没有头结点， 则首元素结点没有前驱结点，在其前插入结点或删除该结点时操作会复杂些。（2）对带头结点的链表，表头指针是指向头结点的非空指针，因此空表与非空表的处理是 一样的。在单链表、双链表和单循环表中， 若仅知道指针p指向