数据结构简答题

试比较顺序存储结构和链式存储结构的优缺点 在什么情况下用顺序表比链表好 试比较顺序存储结构和链式存储结构的优缺点 在什么情况下用顺序表比链表好 答 顺序存储时 相邻数据元素的存放地址也相邻 逻辑与物理统一 要求内存中可 用存储单元的地址必须是连续的 优点 存储密度大 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 指针指向的结点的直接前趋 因此无法删去该结点