数据结构习题集

数据结构数据结构 习题与上机实验指导习题与上机实验指导 数据结构 课程组编 江江苏苏技技术师术师范学院范学院 目录目录 1 线性表 1 2 栈和队列 7 3 串 12 4 数组和广义表 5 递归 6 树形结构 7 图 19 8 查找 25 9 内排序 10 外排序 一 填空题一 填空题 1 数据结构是一门研究非数值计算的程序设计问题中计算机的 以及它们之间的 和运算等的学科 2 数据结构被形式地定义为 D R 其中 D 是 的有限集合 R 是 D 上的 有限 集合 3 数据结构包括数据的 数据的 和数据的 这三个方面的内容 4 数据结构按逻辑结构可分为两大类 它们分别是 和 5 线性结构中元素之间存在 关系 树形结构中元素之间存在 关系 图形结 构中元素之间存在 关系 6 在线性结构中 第一个结点 前驱结点 其余每个结点有且只有 1 个前驱结点 最后一个结 点 后续结点 其余每个结点有且只有 1 个后续结点 7 在树形结构中 树根结点没有 结点 其余每个结点有且只有 个前驱结点 叶 子结点没有 结点 其余每个结点的后续结点数可以 8 在图形结构中 每个结点的前驱结点数和后续结点数可以 9 数据的存储结构可用四种基本的存储方法表示 它们分别是 10 数据的运算最常用的有 5 种 它们分别是 11 一个算法的效率可分为 效率和 效率 二 单项选择题二 单项选择题 1 非线性结构是数据元素之间存在 A 一对多关系B 多对多关系C 一对一关系D A 和 B 2 数据结构中 与所使用的计算机无关的是数据的 结构 A 存储B 物理C 逻辑D 物理和存储 3 算法分析的目的是 A 找出数据结构的合理性B 研究算法中的输入和输出的关系 C 分析算法的效率以求改进D 分析算法的易懂性和文档性 4 算法分析的两个主要方面是 A 空间复杂性和时间复杂性B 正确性和简明性 C 可读性和文档性 D 数据复杂性和程序复杂性 5 计算机算法指的是 A 计算方法B 排序方法 C 解决问题的有限运算序列D 调度方法 6 计算机算法必须具备输入 输出和 等 5 个特性 A 可行性 可移植性和可扩充性 B 可行性 确定性和有穷性 C 确定性 有穷性和稳定性D 易读性 稳定性和安全性 三 判断题三 判断题 1 数据元素是数据的最小单位 2 记录是数据处理的最小单位 3 数据的逻辑结构是指数据的各数据项之间的逻辑关系 4 算法的优劣与算法描述语言无关 但与所用计算机有关 5 健壮的算法不会因非法的输入数据而出现莫名其妙的状态 6 算法可以用不同的语言描述 如果用 C 或 PASCAL 等高级语言来描述 则算法实际上就是 程序了 7 程序一定是算法 8 数据的物理结构是指数据在计算机内的实际存储形式 9 数据结构的抽象操作的定义与具体实现有关 10 在顺序存储结构中 有时也存储数据结构中元素之间的关系 11 顺序存储方式的优点是存储密度大 且插入 删除运算效率高 四 简答题四 简答题 1 数据结构和数据类型两个概念之间有区别吗 2 简述线性结构与非线性结构的不同点 数据结构习题与实验指导 2 3 数据结构的主要研究对象是什么 4 数据结构是一门研究什么内容的学科 五 五 设问题的规模为 n 写出下列程序段的渐进时间复杂度 时间复杂度时间复杂度 1 for i 0 i n i for j 0 j m j A i j 0 2 s 0 for i 0 i n i for j 0 j n j s B i j 3 x 0 for i 1 i n i for j 1 j n i j x 4 i 1 while i n i i 3 5 I 1 k 0 while I n k k 10 I I 6 I 0 k 0 do k k 10 I I while I n 7 I 1 j 0 while I j n if I0 if x 100 x x 10 y else x 六 下列二元组表示的数据结构 画出它们的逻辑结构图 并指出各属于何种结构 六 下列二元组表示的数据结构 画出它们的逻辑结构图 并指出各属于何种结构 1 A K R 其中 K a1 a2 a3 an R i 1 2 n 1 2 B K R K a b c d e f R 3 C K R K 1 2 3 4 5 6 R 1 2 2 3 2 4 3 4 3 5 3 6 4 5 4 6 4 D K R K 48 25 64 57 82 36 75 43 R 习题习题 1 参考答案参考答案 一 填空题一 填空题 1 操作对象 关系2 数据元素 关系3 逻辑结构 存储结构 运算 4 线性结构 非线性结构5 一对一 一对多 多对多6 没有 没有 7 前驱 1 后续 任意多个8 任意多个9 顺序 链式 索引 和 散列 10 插入 删除 修改 查找 排序 11 时间 空间 二 单项选择题二 单项选择题 1 D 2 C 3 C4 A 5 C6 B 三 判断题三 判断题 1 2 3 4 5 6 7 8 9 10 11 四 简答题四 简答题 1 数据结构和数据类型两个概念之间有区别吗 答 简单地说 数据结构定义了一组按某些关系结合在一起的数组元素 数据类型不仅定义了一组 带结构的数据元素 而且还在其上定义了一组操作 2 简述线性结构与非线性结构的不同点 答 线性结构反映结点间的逻辑关系是一对一的 非线性结构反映结点间的逻辑关系是多对多 或 一对多的 数据结构习题与实验指导 3 3 3 数据结构的主要研究对象是什么 答 研究数据的组织方式 结构 及相应的抽象操作 4 数据结构是一门研究什么内容的学科 答 数据结构是一门研究在非数值计算的程序设计问题中 计算机的操作对象及对象间的关系和施 加于对象的操作等的学科 五 分析下面各程序段的时间复杂度五 分析下面各程序段的时间复杂度 1 O m n 2 O n2 3 因为 x 共执行了 n 1 n 2 1 n n 1 2 所以执行时间为 O n2 4 O log3n 5 O n 6 O n 7 O n 8 O 1 六 下列二元组表示的数据结构 画出它们的逻辑结构图 并指出各属于何种结构 解 1 线性结构 a1 a2 ai ai 1 an 2 图形结构 3 图形结构 a de f bc Y 1235 46 4 树形结构 25 48 64 365782 4375 习题习题 2 一 填空题一 填空题 1 在顺序表中插入或删除一个元素 需要平均移动 元素 具体移动的元素个数与 有关 2 线性表中结点的集合是 的 结点间的关系是 的 3 向一个长度为 n 的向量的第 i 个元素 1 i n 1 之前插入一个元素时 需向后移动 个 元素 4 向一个长度为 n 的向量中删除第 i 个元素 1 i n 时 需向前移动 个元素 5 在顺序表中访问任意一结点的时间复杂度均为 因此 顺序表也称为 的数 据结构 6 顺序表中逻辑上相邻的元素的物理位置 相邻 单链表中逻辑上相邻的元素的物理位置 相邻 7 在单链表中 除了首元结点外 任一结点的存储位置由 指示 8 在 n 个结点的单链表中要删除已知结点 p 需找到它的 其时间复杂度 为 9 当线性表的元素总数基本稳定 且很少进行插入和删除操作 但要求以最快的速度存取线性表中 的元素时 应采用 存储结构 10 在单链表中设置头结点的作用是 11 链接存储的特点是利用 来表示数据元素之间的逻辑关系 12 对于双向链表 在两个结点之间插入一个新结点需修改的指针共 个 单链表为 个 13 循环单链表的最大优点是 二 单项选择题二 单项选择题 1 数据在计算机存储器内表示时 物理地址与逻辑地址相同并且是连续的 称之为 A 存储结构 B 逻辑结构 C 顺序存储结构 D 链式存储结构 2 一个向量第一个元素的存储地址是 100 每个元素的长度为 2 则第 5 个元素的地址是 A 110 B 108 C 100 D 120 3 在 n 个结点的顺序表中 算法的时间复杂度是 O 1 的操作是 A 访问第 i 个结点 1 i n 和求第 i 个结点的直接前驱 2 i n B 在第 i 个结点后插入一个新结点 1 i n C 删除第 i 个结点 1 i n D 将 n 个结点从小到大排序 4 向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变 平均要移动 个元素 A 8 B 63 5 C 63 D 7 5 链接存储的存储结构所占存储空间 A 分两部分 一部分存放结点值 另一部分存放表示结点间关系的指针 B 只有一部分 存放结点值 C 只有一部分 存储表示结点间关系的指针 D 分两部分 一部分存放结点值 另一部分存放结点所占单元数 6 链表是一种采用 存储结构存储的线性表 A 顺序 B 链式 C 星式 D 网状 7 线性表若采用链式存储结构时 要求内存中可用存储单元的地址 A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 连续或不连续都可以 8 线性表 在 情况下适用于使用链式结构实现 需经常修改 中的结点值 需不断对 进行删除插入 中含有大量的结点 中结点结构复杂 9 单链表的存储密度 数据结构习题与实验指导 5 5 大于 1 等于 1 小于 1 不能确定 10 设 a1 a2 a3 为 3 个结点 整数 P0 3 4 代表地址 则如下的链式存储结构称为 循环链表 B 单链表 双向循环链表 双向链表 11 下述 是顺序存储结构的优点 A 存储密度大 B 插入运算方便 C 删除运算方便 D 可方便地用于各种逻辑结构的存储表示 12 下面关于线性表的叙述中 错误的是 A 线性表采用顺序存储 必须占用一片连续的存储单元 B 线性表采用顺序存储 便于进行插入和删除操作 C 线性表采用链接存储 不必占用一片连续的存储单元 D 线性表采用链接存储 便于插入和删除操作 13 线性表是具有 n 个 的有限序列 n 0 A 表元素 B 字符 C 数据元素 D 数据项 E 信息项 14 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算 则利用 存储方式最节省时间 A 顺序表 B 双链表 C 带头结点的双循环链表 D 单循环链表 15 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素 则采用 存储方式最节省运算时间 A 单链表 B 仅有头指针的单循环链表 C 双链表 D 仅有尾指针的单循环链表 16 链表不具有的特点是 A 插入 删除不需要移动元素 B 可随机访问任一元素 C 不必事先估计存储空间 D 所需空间与线性长度成正比 17 若长度为 n 的线性表采用顺序存储结构 在其第 i 个位置插入一个新元素的算法的时间复杂度为 1 iLlink q q Rlink p p Llink Rlink q q Llink q B p Llink q p Llink Rlink q q Rlink p q Llink p Llink C q Rlink p q Llink p Llink p Llink Rlink q p Llink q D q Llink p Llink q Rlink q p Llink q p Llink q 20 在单链表指针为 p 的结点之后插入指针为 s 的结点 正确的操作是 A p next s s next p next B s next p next p next s C p next s p next s next D p next s next p next s 21 对于一个头指针为 head 的带头结点的单链表 判定该表为空表的条件是 A head NULL B head next NULL C head next head D head NULL 三 判断题三 判断题 1 链表的每个结点中都恰好包含一个指针 2 链表的物理存储结构具有同链表一样的顺序 3 链表的删除算法很简单 因为当删除链中某个结点后 计算机会自动将后续各个单元向前移 动 4 线性表的每个结点只能是一个简单类型 而链表的每个结点可以是一个复杂类型 5 顺序表结构适宜于进行顺序存取 而链表适宜于进行随机存取 6 顺序存储方式的优点是存储密度大 且插入 删除运算效率高 数据结构习题与实验指导 6 6 7 线性表在物理存储空间中也一定是连续的 8 线性表在顺序存储时 逻辑上相邻的元素未必在存储的物理位置次序上相邻 9 顺序存储方式只能用于存储线性结构 10 线性表的逻辑顺序与存储顺序总是一致的 11 链表中的头结点仅起到标识的作用 12 顺序存储结构的主要缺点是不利于插入或删除操作 13 线性表采用链表存储时 结点和结点内部的存储空间可以是不连续的 14 顺序存储方式插入和删除时效率太低 因此它不如链式存储方式好 15 对任何数据结构链式存储结构一定优于顺序存储结构 16 集合与线性表的区别在于是否按关键字排序 17 线性表的特点是每个元素都有一个前驱和一个后继 18 取线性表的第 i 个元素的时间同 i 的大小有关 19 循环链表不是线性表 20 线性表只能用顺序存储结构实现 21 线性表就是顺序存储的表 22 为了很方便的插入和删除数据 可以使用双向链表存放数据 23 链表是采用链式存储结构的线性表 进行插入 删除操作时 在链表中比在顺序存储结构中 效率高 四 问答题四 问答题 1 试比较顺序存储结构和链式存储结构的优缺点 在什么情况下用顺序表比链表好 2 描述以下三个概念的区别 头指针 头结点 首元结点 第一个元素结点 在单链表中设置头 结点的作用是什么 3 线性表有两种存储结构 一是顺序表 二是链表 试问 1 如果有 n 个线性表同时并存 并且在处理过程中各表的长度会动态变化 线性表的总数也会自 动地改变 在此情况下 应选用哪种存储结构 为什么 2 若线性表的总数基本稳定 且很少进行插入和删除 但要求以最快的速度存取线性表中的元素 那么应采用哪种存储结构 为什么 4 线性表的顺序存储结构具有三个弱点 其一 在作插入或删除操作时 需移动大量元素 其二 由于难以估计 必须预先分配较大的空间 往往使存储空间不能得到充分利用 其三 表的容量难以扩 充 线性表的链式存储结构是否一定都能够克服上述三个弱点 试讨论之 5 若较频繁地对一个线性表进行插入和删除操作 该线性表宜采用何种存储结构 为什么 6 线性表 a1 a2 an 用顺序映射表示时 ai和 ai 1 1 inext q p next r q next while q L while p L p next q next free q 2 设 q p llink 则 q rlink p rlink p rlink llink q p llink q llink q llink rlink p p rlink q q llink p 3 在指针 p 所指结点前插入结点 s 的语句如下 s pre p pre s next p p pre next s p pre s 4 1 本算法功能是将双向循环链表结点的数据域按值自小到大排序 成为非递减 可能包括数据 域值相等的结点 有序双向循环链表 2 1 r prior q prior 将 q 结点摘下 以便插入到适当位置 2 p next prior q 2 3 将 q 结点插入 3 p next q 4 r r next 或 r q next 后移指针 再将新结点插入到适当位置 六 算法设计题六 算法设计题 1 题目分析 因为两链表已按元素值递增次序排列 将其合并时 均从第一个结点起进行比较 将 小的链入链表中 同时后移链表工作指针 该问题要求结果链表按元素值递减次序排列 故在合并的同 时 将链表结点逆置 LinkedList Union LinkedList la lb la lb 分别是带头结点的两个单链表的头指针 链表中的元素值按递增序排列 本算法将两链表合并 成一个按元素值递减次序排列的单链表 pa la next pb lb next pa pb 分别是链表 la 和 lb 的工作指针 la next null la 作结果链表的头指针 先将结果链表初始化为空 whilewhile pa null 将 pa 的后继结点暂存于 r pa next la next 将 pa 结点链于结果表中 同时逆置 la next pa pa r 恢复 pa 为当前待比较结点 elseelse r pb next 将 pb 的后继结点暂存于 r pb next la next 将 pb 结点链于结果表中 同时逆置 la next pb pb r 恢复 pb 为当前待比较结点 whilewhile pa null 将 la 表的剩余部分链入结果表 并逆置 r pa next pa next la next la next pa pa r whilewhile pb null r pb next pb next la next la next pb pb r 算法 Union 结束 算法讨论 上面两链表均不为空的表达式也可简写为 whilewhile pa n r f n 5 在作进栈运算时 应先判别栈是否 在作退栈运算时应先判别栈是否 当栈中元 素为 n 个 作进栈运算时发生上溢 则说明该栈的最大容量为 为了增加内存空间的利用率和减少溢出的可能性 由两个栈共享一片连续的内存空间时 应将两栈的 分别设在这片内存空间的两端 这样 当 时 才产生上溢 A 空 B 满 C 上溢 D 下溢 A n 1 B n C n 1 D n 2 A 长度 B 深度 C 栈顶 D 栈底 A 两个栈的栈顶同时到达栈空间的中心点 B 其中一个栈的栈顶到达栈空间的中心点 C 两个栈的栈顶在栈空间的某一位置相遇 D 两个栈均不空 且一个栈的栈顶到达另一个栈的栈底 6 若一个栈的输入序列为 1 2 3 n 输出序列的第一个元素是 i 则第 j 个输出元素是 A i j 1 B i j C j i 1 D 不确定的 7 若已知一个栈的入栈序列是 1 2 3 n 其输出序列为 p1 p2 p3 pN 若 pN是 n 则 pi是 A i B n i C n i 1 D 不确定 8 一个栈的输入序列为 1 2 3 4 5 则下列序列中不可能是栈的输出序列的是 A 2 3 4 1 5 B 5 4 1 3 2 C 2 3 1 4 5 D 1 5 4 3 2 9 设一个栈的输入序列是 1 2 3 4 5 则下列序列中 是栈的合法输出序列的是 A 5 1 2 3 4 B 4 5 1 3 2 C 4 3 1 2 5 D 3 2 1 5 4 10 输入序列为 ABC 可以变为 CBA 时 经过的栈操作为 A push pop push pop push pop B push push push pop pop pop C push push pop pop push pop D push pop push push pop pop 11 若一个栈以数组 V 1 n 存储 初始栈顶指针 top 为 n 1 则下面 x 进栈的正确操作是 A top top 1 V top x B V top x top top 1 C top top 1 V top x D V top x top top 1 12 执行完下列语句段后 i 值为 int f int x return x 0 x f x 1 2 int i 数据结构习题与实验指导 11 11 i f f 1 A 2 B 4 C 8 D 无限递归 13 表达式 a b c d 的后缀表达式是 A abcd B abc d C abc d D abcd 14 表达式 3 2 4 2 2 6 3 5 求值过程中当扫描到 6 时 操作数栈和算符栈为 其中 为乘幂 A 3 2 4 1 1 B 3 2 8 C 3 2 4 2 2 D 3 2 8 15 设计一个判别表达式中左 右括号是否配对出现的算法 采用 数据结构最佳 A 线性表的顺序存储结构 B 队列 C 线性表的链式存储结构 D 栈 16 用链接方式存储的队列 在进行删除运算时 A 仅修改头指针 B 仅修改尾指针 C 头 尾指针都要修改 D 头 尾指针可能都要修改 17 用不带头结点的单链表存储队列时 其队头指针指向队头结点 其队尾指针指向队尾结点 则在 进行删除操作时 A 仅修改队头指针 B 仅修改队尾指针 C 队头 队尾指针都要修改 D 队头 队尾指针都可能要修改 18 递归过程或函数调用时 处理参数及返回地址 要用一种称为 的数据结构 A 队列 B 多维数组 C 栈 D 线性表 19 若用一个大小为 6 的数组来实现循环队列 且当前 rear 和 front 的值分别为 0 和 3 当从队列 中删除一个元素 再加入两个元素后 rear 和 front 的值分别为多少 A 1 和 5 B 2 和 4 C 4 和 2 D 5 和 1 三 判断题三 判断题 1 线性表的每个结点只能是一个简单类型 而链表的每个结点可以是一个复杂类型 2 在表结构中最常用的是线性表 栈和队列不太常用 3 栈是一种对所有插入 删除操作限于在表的一端进行的线性表 是一种后进先出型结构 4 栈和链表是两种不同的数据结构 5 栈和队列是一种非线性数据结构 6 栈和队列的存储方式既可是顺序方式 也可是链接方式 7 两个栈共享一片连续内存空间时 为提高内存利用率 减少溢出机会 应把两个栈的栈底分别 设在这片内存空间的两端 8 队是一种插入与删除操作分别在表的两端进行的线性表 是一种先进后出型结构 9 一个栈的输入序列是 12345 则栈的输出序列不可能是 12345 10 消除递归不一定需要使用栈 11 栈是实现过程和函数等子程序所必需的结构 12 两个栈共用静态存储空间 对头使用也存在空间溢出问题 13 若输入序列为 1 2 3 4 5 6 则通过一个栈可以输出序列 3 2 5 6 4 1 14 栈和队列都是限制存取点的线性结构 15 若输入序列为 1 2 3 4 5 6 则通过一个栈可以输出序列 1 5 4 6 2 3 16 任何一个递归过程都可以转换成非递归过程 17 通常使用队列来处理函数或过程的调用 18 栈和队列的存储方式 既可以是顺序方式 又可以是链式方式 四 问答与应用题四 问答与应用题 1 说明线性表 栈与队的异同点 2 设有编号为 1 2 3 4 的四辆列车 顺序进入一个栈式结构的车站 具体写出这四辆列车开出车 站的所有可能的顺序 3 假设正读和反读都相同的字符序列为 回文 例如 abba 和 abcba 是回文 abcde 和 ababab 则不是回文 假设一字符序列已存入计算机 请分析用线性表 堆栈和队列等方式正确输出其 回文的可能性 4 顺序队的 假溢出 是怎样产生的 如何知道循环队列是空还是满 5 设循环队列的容量为 40 序号从 0 到 39 现经过一系列的入队和出队运算后 有 数据结构习题与实验指导 12 12 front 11 rear 19 front 19 rear 11 问在这两种情况下 循环队列中各有元素多少个 6 什么是循环队列 7 有 5 个元素 其入栈次序为 A B C D E 在各种可能的出栈次序中 以元素 C D 最先出栈 即 C 第一个且 D 第二个出栈 的次序有哪几个 8 如果输入序列为 1 2 3 4 5 6 试问能否通过栈结构得到以下两个序列 4 3 5 6 1 2 和 1 3 5 4 2 6 请说明为什么不能或如何才能得到 9 用一个数组 S 设大小为 MAX 作为两个堆栈的共享空间 请说明共享方法 栈满 栈空的判断条 件 并用 C 设计公用的入栈操作 push i x 其中 i 为 0 或 1 用于表示栈号 x 为入栈值 10 用栈实现将中缀表达式 8 3 5 5 6 2 转换成后缀表达式 画出栈的变化过程图 11 简述顺序存储队列的假溢出的避免方法及队列满和空的条件 12 给出循环队列中元素个数的计算式 设队最大长度为 N 队首指针 FRONT 队尾指针 REAR 五 算法设计题五 算法设计题 1 假设一个算术表达式中包含圆括弧 方括弧和花括弧三种类型的括弧 编写一个判别表达式中括 弧是否正确配对的函数 correct exp tag 其中 exp 为字符串类型的变量 可理解为每个字符占用一个数 组元素 表示被判别的表达式 tag 为布尔型变量 2 假设一个数组 squ m 存放循环队列的元素 若要使这 m 个分量都得到利用 则需另一个标志 tag 以 tag 为 0 或 1 来区分尾指针和头指针值相同时队列的状态是 空 还是 满 试编写相应的入队 和出队的算法 3 试写一个算法 判别读入的一个以 为结束符的字符序列是否是 回文 习题习题 3 参考答案参考答案 一 填空题一 填空题 1 线性 任何 栈顶 队尾 队首2 栈顶 栈底3 队列 4 S SS S 5 23 12 3 2 4 34 5 7 108 9 注 表达式中的点 表示将数隔开 如 23 12 3 是三个数 6 假溢出时大量移动数据元素 7 队列8 先进先出 9 栈10 rear front m m 二 单项选择题二 单项选择题 1 B 2 C 3 B 4 D5 1 B5 2 A 5 3 B5 4 D 5 5 C 6 D7 D8 B 9 D10 B11 C12 B13 B14 D 15 D16 D17 D18 C19 B 三 判断题三 判断题 1 错 线性表是逻辑结构概念 可以顺序存储或链式存储 与元素数据类型无关 2 错 不一定吧 调用子程序或函数常用 CPU 中也用队列 3 4 错 栈是逻辑结构的概念 是特殊殊线性表 而链表是存储结构概念 二者不是同类项 5 错 他们都是线性逻辑结构 栈和队列其实是特殊的线性表 对运算的定义略有不同而已 6 7 8 错 后半句不对 9 错 有可能 10 11 12 13 14 15 16 17 18 四 问答与应用题四 问答与应用题 1 答 相同点 都是线性结构 都是逻辑结构的概念 都可以用顺序存储或链表存储 栈和队列是 两种特殊的线性表 即受限的线性表 只是对插入 删除运算加以限制 不同点 运算规则不同 线性表为随机存取 而栈是只允许在一端进行插入 删除运算 因而是 后进先出表 LIFO 队列是只允许在一端进行插入 另一端进行删除运算 因而是先进先出表 FIFO 用途不同 堆栈用于子程调用和保护现场 队列用于多道作业处理 指令寄存及其他运算等等 2 答 至少有 14 种 全进之后再出情况 只有 1 种 4 3 2 1 数据结构习题与实验指导 13 13 进 3 个之后再出的情况 有 3 种 3 4 2 1 3 2 4 1 3 2 1 4 进 2 个之后再出的情况 有 5 种 2 4 3 1 2 3 4 1 2 1 3 4 2 1 4 3 2 1 3 4 进 1 个之后再出的情况 有 5 种 1 4 3 2 1 3 2 4 1 3 4 2 1 2 3 4 1 2 4 3 3 答 线性表是随机存储 可以实现 靠循环变量 j 从表尾开始打印输出 堆栈是后进先出 也可以实现 靠正序入栈 逆序出栈即可 队列是先进先出 不易实现 哪种方式最好 要具体情况具体分析 若正文在机内已是顺序存储 则直接用线性表从后往前读取 即可 或将堆栈栈顶开到数组末尾 然后直接用 POP 动作实现 但堆栈是先减后压还是 若正文是单链表形式存储 则等同于队列 需开辅助空间 可以从链首开始入栈 全部压入后再依 次输出 4 答 一般的一维数组队列的尾指针已经到了数组的上界 不能再有入队操作 但其实数组中还有 空位置 这就叫 假溢出 采用循环队列是解决假溢出的途径 另外 解决队满队空的办法有三 设置一个布尔变量以区别队满还是队空 浪费一个元素的空间 用于区别队满还是队空 使用一个计数器记录队列中元素个数 即队列长度 我们常采用法 即队头指针 队尾指针中有一个指向实元素 而另一个指向空闲元素 判断循环队列队空标志是 f rear 队满标志是 f r 1 N 5 答 用队列长度计算公式 N r f N L 40 19 11 40 8 L 40 11 19 40 32 6 用常规意义下顺序存储结构的一维数组表示队列 由于队列的性质 队尾插入和队头删除 容易 造成 假溢出 现象 即队尾已到达一维数组的高下标 不能再插入 然而队中元素个数小于队列的长 度 容量 循环队列是解决 假溢出 的一种方法 通常把一维数组看成首尾相接 在循环队列下 通 常采用 牺牲一个存储单元 或 作标记 的方法解决 队满 和 队空 的判定问题 7 三个 CDEBA CDBEA CDBAE 8 输入序列为 123456 不能得出 435612 其理由是 输出序列最后两元素是 12 前面 4 个元素 4356 得到后 栈中元素剩 12 且 2 在栈顶 不可能栈底元素 1 在栈顶元素 2 之前出栈 得到 135426 的过程如下 1 入栈并出栈 得到部分输出序列 1 然后 2 和 3 入栈 3 出栈 部分输出 序列变为 13 接着 4 和 5 入栈 5 4 和 2 依次出栈 部分输出序列变为 13542 最后 6 入栈并退栈 得最终结果 135426 9 两栈共享一向量空间 一维数组 栈底设在数组的两端 两栈顶相邻时为栈满 设共享数组为 S MAX 则一个栈顶指针为 1 另一个栈顶指针为 MAX 时 栈为空 用 C 写的入栈操作 push i x 如下 const MAX 共享栈可能达到的最大容量 typedeftypedef structstruct node elemtype s MAX intint top 2 anode anode ds intint push intint i elemtype x ds 为容量有 MAX 个类型为 elemtype 的元素的一维数组 由两个栈共享其空间 i 的值为 0 或 1 x 为类型为 elemtype 的元素 本算法将 x 压入栈中 如压栈成功 返回 1 否则 返回 0 ifif ds top 1 ds top 0 1 printf 栈满 n returnreturn 0 switchswitch i casecase 0 ds s ds top i x breakbreak casecase 1 ds s ds top i x returnreturn 1 入栈成功 10 中缀表达式 8 3 5 5 6 2 的后缀表达式是 8 3 5 5 6 2 栈的变化过程图略 表达式生成过程为 数据结构习题与实验指导 14 14 中缀表达式 exp1 转为后缀表达式 exp2 的规则如下 设操作符栈 s 初始为空栈后 压入优先级最低的操作符 对中缀表达式从左向右扫描 遇操 作数 直接写入 exp2 若是操作符 记为 w 分如下情况处理 直至表达式 exp1 扫描完毕 1 w 为一般操作符 等 要与栈顶操作符比较优先级 若 w 优先级高于栈顶操作 符 则入栈 否则 栈顶运算符退栈到 exp2 w 再与新栈顶操作符作上述比较处理 直至 w 入栈 2 w 为左括号 w 入栈 3 w 为右括号 操作符栈退栈并进入 exp2 直到碰到左括号为止 左括号退栈 不能进入 exp2 右括号也丢掉 达到 exp2 中消除括号的目的 4 w 为 表示中缀表达式 exp1 结束 操作符栈退栈到 exp2 直至碰到 退栈 整个操 作结束 这里 再介绍一种简单方法 中缀表达式转为后缀表达式有三步 首先 将中缀表达式中所有的子 表达式按计算规则用嵌套括号括起来 接着 顺序将每对括号中的运算符移到相应括号的后面 最后 删除所有括号 例如 将中缀表达式 8 3 5 5 6 2 转为后缀表达式 按如上步骤 执行完上面第一步后为 8 3 5 5 6 2 执行完上面第二步后为 8 35 5 62 执行完上面第三步后为 8 3 5 5 6 2 可用类似方法将中缀表达式转为前缀表达式 11 设顺序存储队列用一维数组 q m 表示 其中 m 为队列中元素个数 队列中元素在向量中的下标 从 0 到 m 1 设队头指针为 front 队尾指针是 rear 约定 front 指向队头元素的前一位置 rear 指向 队尾元素 当 front 等于 1 时队空 rear 等于 m 1 时为队满 由于队列的性质 删除 在队头而 插 入 在队尾 所以当队尾指针 rear 等于 m 1 时 若 front 不等于 1 则队列中仍有空闲单元 所以队 列并不是真满 这时若再有入队操作 会造成假 溢出 其解决办法有二 一是将队列元素向前 平移 占用 0 至 rear front 1 二是将队列看成首尾相连 即循环队列 0 m 1 在循环队列下 仍定义 front rear 时为队空 而判断队满则用两种办法 一是用 牺牲一个单元 即 rear 1 front 准确记 是 rear 1 m front m 是队列容量 时为队满 另一种解法是 设标记 方法 如设标记 tag tag 等于 0 情况下 若删除时导致 front rear 为队空 tag 1 情况下 若因插入导致 front rear 则为队满 12 循环队列中元素个数为 REAR FRONT N N 其中 FRONT 是队首指针 指向队首元素的前一位 置 REAR 是队尾指针 指向队尾元素 N 是队列最大长度 五 算法设计题五 算法设计题 1 答 用堆栈 st 进行判定 将 或 入栈 当遇到 或 时 检查当前栈顶元素 是否是对应的 或 若是则退栈 否则返回表示不配对 当整个算术表达式检查完毕时 若栈为 空表示括号正确配对 否则不配对 define m0 100 m0 为算术表达式中最多字符个数 correct exp tag char exp m0 int tag char st m0 int top 0 i 1 tag 1 while i0 tag 0 若栈不空 则不配对 2 解 这就是解决队满队空的三种办法之 设置一个布尔变量以区别队满还是队空 其他两种见简 答题 思路 一开始队空 设 tag 0 若从 rear 一端加到与 front 指针相同时 表示入队已满 则令 tag 1 若从 front 一端加到与 rear 指针相同时 则令 tag 0 表示出队已空 3 答 编程如下 int Palindrome Test 判别输入的字符串是否回文序列 是则返回 1 否则返回 0 InitStack S InitQueue Q while c getchar Push S c EnQueue Q c 同时使用栈和队列两种结构 while StackEmpty S Pop S a DeQueue Q b if a b return ERROR return OK Palindrome Test 习题习题 4 一 填空题一 填空题 1 称为空串 称为空白串 2 设 S A document Mary doc 则 strlen s 的字符定位的位置为 3 子串的定位运算称为串的模式匹配 称为目标串 称为模式 4 设目标 T abccdcdccbaa 模式 P cdcc 则第 次匹配成功 5 组成串的数据元素只能是 6 一个字符串中 称为该串的子串 7 设 T 和 P 是两个给定的串 在 T 中寻找等于 P 的子串的过程称为 1 又称 P 为 2 8 串是一种特殊的线性表 其特殊性表现在 1 串的两种最基本的存储方式是 2 3 两个串相等的充分必要条件是 4 二 单项选择题二 单项选择题 1 串是一种特殊的线性表 其特殊性体现在 可以顺序存储 数据元素是一个字符 可以链式存储 数据元素可以是多个字符 2 设有两个串 p 和 q 求 q 在 p 中首次出现的位置的运算称作 连接 模式匹配 求子串 求串长 3 设串 s1 ABCDEFG s2 PQRST 函数 con x y 返回 x 和 y 串的连接串 subs s i j 返回串 s 的 从序号 i 开始的 j 个字符组成的子串 len s 返回串 s 的长度 则 con subs s1 2 len s2 subs s1 len s2 2 的结果串是 数据结构习题与实验指导 16 16 BCDEF BCDEFG BCPQRST D BCDEFEF 4 下面关于串的的叙述中 哪一个是不正确的 A 串是字符的有限序列 B 空串是由空格构成的串 C 模式匹配是串的一种重要运算 D 串既可以采用顺序存储 也可以采用链式存储 5 若串 S software 其子串的数目是 A 8 B 37 C 36 D 9 6 串的长度是指 A 串中所含不同字母的个数 B 串中所含字符的个数 C 串中所含不同字符的个数 D 串中所含非空格字符的个数 三 问答与应用题三 问答与应用题 1 描述以下概念的区别 空格串与空串 2 如果两个串含有相等的字符 能否说它们相等 习题习题 4 参考答案参考答案 一 填空题一 填空题 1 不包含任何字符 长度为 0 的串 由一个或多个空格 仅由空格符 组成的串 2 20 3 3 被匹配的主串 子串 4 6 5 字符 6 任意个连续的字符组成的子序列7 1 模式匹配 2 模式串 8 1 其数据元素都是字符 2 顺序存储 3 和链式存储 4 串的长度相等且两串中对应位置的字符也相等 二 单项选择题二 单项选择题 1 B2 B3 D4 B5 B6 B 三 问答与应用题三 问答与应用题 1 空格是一个字符 其 ASCII 码值是 32 空格串是由空格组成的串 其长度等于空格的个数 空 串是不含任何字符的串 即空串的长度是零 2 仅从两串含有相等的字符 不能判定两串是否相等 两串相等的充分必要条件是两串长度相等且 对应位置上的字符相同 即两串串值相等 习题习题 5 一 填空题一 填空题 1 假设有二维数组 A6 8 每个元素用相邻的 6 个字节存储 存储器按字节编址 已知 A 的起始存 储位置 基地址 为 1000 则数组 A 的体积 存储量 为 末尾元素 A57的第一个字节地 址为 若按行存储时 元素 A14的第一个字节地址为 若按列存储时 元素 A47的 第一个字节地址为 2 设数组 a 1 60 1 70 的基地址为 2048 每个元素占 2 个存储单元 若以列序为主序顺序存储 则元素 a 32 58 的存储地址为 3 三元组表中的每个结点对应于稀疏矩阵的一个非零元素 它包含有三个数据项 分别表示该元素 的 和 4 求下列广义表操作的结果 1 Head a b c d 2 Head Tail a b c d 3 Head Tail Head a b c d 4 Tail Head Tail a b c d 5 设数组 a 1 50 1 80 的基地址为 2000 每个元素占 2 个存储单元 若以行序为主序顺序存储 则元素 a 45 68 的存储地址为 1 若以列序为主序顺序存储 则元素 a 45 68 的存储地址为 2 6 将整型数组 A 1 8 1 8 按行优先次序存储在起始地址为 1000 的连续的内存单元中 则元素 A 7 3 的地址是 7 二维数组 a 4 5 6 下标从 0 开始计 a 有 4 5 6 个元素 每个元素的长度是 2 则 a 2 3 数据结构习题与实验指导 17 17 4 的地址是 设 a 0 0 0 的地址是 1000 数据以行为主方式存储 8 设有二维数组 A 0 9 0 19 其每个元素占两个字节 第一个元素的存储地址为 100 若按列优 先顺序存储 则元素 A 6 6 存储地址为 9 已知数组 A 0 9 0 9 的每个元素占 5 个存储单元 将其按行优先次序存储在起始地址为 1000 的连续的内存单元中 则元素 A 6 8 的地址为 10 设 n 行 n 列的下三角矩阵 A 已压缩到一维数组 B 1 n n 1 2 中 若按行为主序存储 则 A i j 对应的 B 中存储位置为 11 己知三对角矩阵 A 1 9 1 9 的每个元素占 2 个单元 现将其三条对角线上的元素逐行存储 在起始地址为 1000 的连续的内存单元中 则元素 A 7 8 的地址为 12 所谓稀疏矩阵指的是 13 对矩阵压缩是为了 14 当广义表中的每个元素都是原子时 广义表便成了 15 广义表的表尾是指除第一个元素之外 16 广义表 A a b c d e 取出 A 中的原子 e 的操作是 17 设某广义表 H A a b c 运用 head 函数和 tail 函数求出广义表 H 中某元素 b 的运算 式 18 广义表 A a b c head tail head tail head A 等于 19 广义表运算式 HEAD TAIL a b c x y z 的结果是 20 已知广义表 A a b c d e head tail tail head A 的结果是 二 单项选择题二 单项选择题 1 假设有 60 行 70 列的二维数组 a 1 60 1 70 以列序为主序顺序存储 其基地址为 10000 每个 元素占 2 个存储单元 那么第 32 行第 58 列的元素 a 32 58 的存储地址为 无第 0 行第 0 列元素 16902 16904 14454 答案 A B C 均不对 2 设矩阵 A 是一个对称矩阵 为了节省存储 将其下三角部分 如右图所示 按行序存放在一维数 组 B 1 n n 1 2 中 对下三角部分中任一元素 ai j i j 在一维数组 B 中下标 k 的值是 6 数组 A 0 5 0 6 的每个元素占五个字节 将其按列优先次序存储在起始地址为 1000 的内存单 元中 则元素 A 5 5 的地址是 A 1175 B 1180 C 1205 D 1210 7 将一个 A 1 100 1 100 的三对角矩阵 按行优先存入一维数组 B 1 298 中 A 中元素 A6665 即该 元素下标 i 66 j 65 在 B 数组中的位置 K 为 供选择的答案 A 198 B 195 C 197 数据结构习题与实验指导 18 18 8 二维数组 A 的每个元素是由 6 个字符组成的串 其行下标 i 0 1 8 列下标 j 1 2 10 若 A 按行先存储 元素 A 8 5 的起始地址与当 A 按列先存储时的元素 的起始地址相同 设每个字 符占一个字节 A A 8 5 B A 3 10 C A 5 8 D A 0 9 9 若对 n 阶对称矩阵 A 以行序为主序方式将其下三角形的元素 包括主对角线上所有元素 依次存放 于一维数组 B 1 n n 1 2 中 则在 B 中确定 aij i j 的位置 k 的关系为 A i i 1 2 j B j j 1 2 i C i i 1 2 j D j j 1 2 i 10 有一个 100 90 的稀疏矩阵 非 0 元素有 10 个 设每个整型数占 2 字节 则用三元组表示该矩阵 时 所需的字节数是 A 60 B 66 C 18000 D 33 11 对稀疏矩阵进行压缩存储目的是 A 便于进行矩阵运算 B 便于输入和输出 C 节省存储空间 D 降低运算的时间复杂度 12 已知广义表 L x y z a u t w 从 L 表中取出原子项 t 的运算是 A head tail tail L B tail head head