《计算机软件技术基础》课后题VIP

1 数据结构习题答案数据结构习题答案 第一节第一节 概概 论论 一 选择题 1 要求同一逻辑结构的所有数据元素具有相同的特性 这意味着 A 数据元素具有同一的特点 B 不仅数据元素包含的数据项的个数要相同 而且对应数据项的类型要一致 C 每个数据元素都一样 D 数据元素所包含的数据项的个数要相等 2 数据结构是一门研究非数值计算的程序设计问题中计算机的 1 以及它们之间的 2 和运算的学科 1 A 操作对象 B 计算方法 C 物理存储 D 数据映像 2 A 结构 B 关系 C 运算 D 算法 3 数据结构被形式地定义为 D R 其中 D 是 1 的有限集合 R 是 D 上 2 的有限集合 1 A 算法 B 数据元素 C 数据操作 D 逻辑结构 2 A 操作 B 映像 C 存储 D 关系 4 在数据结构中 从逻辑上可以把数据结构分为 A 动态结构和静态结构 B 紧凑结构和非紧凑结构 C 线性结构和非线性结构 D 内部结构和外部结构 5 线性表的顺序存储结构是一种 的存储结构 A 随机存取 B 顺序存取 C 索引存取 D Hash 存取 6 算法分析的目的是 A 找出数据结构的合理性 B 研究算法中的输入和输出的关系 C 分析算法的效率以求改进 D 分析 算法的易懂性和文档性 7 计算机算法指的是 1 它必须具备输入 输出和 2 等五个特征 1 A 计算方法 B 排序方法 C 解决某一问题的有限运算序列 D 调度方法 2 A 可行性 可移植性和可扩充性 B 可行性 确定性和有穷性 C 确定性 有穷性和稳定性 D 易读 性 稳定性和安全性 8 线性表若采用链表存储结构 要求内存中可用存储单元的地址 A 必须是连续的 B 部分必须是连续的 C 一定是不连续的 D 连续不连续都可以 9 在以下的叙述中 正确的是 A 线性表的线性存储结构优于链式存储结构 B 二维数组是它的每个数据元素为一个线性表的线性表 C 栈的操作方式是先进先出 D 队列的操作方式是先进后出 10 根据数据元素之间关系的不同特性 以下四类基本的逻辑结构反映了四类基本的数据组织形式 其中解释错 误的是 A 集合中任何两个结点之间都有逻辑关系但组织形式松散 B 线性结构中结点按逻辑关系依次排列形成一 条 锁链 C 树形结构具有分支 层次特性 其形态有点像自然界中的树 D 图状结构中的各个结点按 逻辑关系互相缠绕 任何两个结点都可以邻接 11 以下说法正确的是 A 数据元素是数据的最小单位 B 数据项是数据的基本单位 C 数据结构是带有结构的各数据项的集合 D 数据结构是带有结构的数据元素的集合 二 判断题 1 数据元素是数据的最小单位 2 数据结构是带有结构的数据元素的集合 3 数据结构 数据元素 数据项在计算机中的映像分别称为存储结构 结点 数据域 4 数据项是数据的基本单位 5 数据的逻辑结构是指各数据元素之间的逻辑关系 是用户按使用需要建立的 6 数据的物理结构是数据在计算机中实际的存储形式 7 算法和程序没有区别 所以在数据结构中二者是通用的 8 顺序存储结构属于静态结构 链式存储结构属于动态结构 三 填空题 1 所谓数据的逻辑结构指的是数据元素之间的 2 数据结构是相互之间存在一种或多种特定关系的数据元素的集合 它包括三方面的内容 2 3 数据的逻辑结构包括 和 四种类型 4 在线性结构中 开始结点 前驱结点 其余每个结点有且只有 个前驱结点 5 在树形结构中 根结点只有 其余每个结点有且只有 前驱结点 叶结点没有 结点 其余每个结点的后继结点可以有 6 在图形结构中 每个结点的前驱结点和后继结点可以有 7 算法的五个重要特性是 8 下列程序段的时间复杂度是 for i 1 i n i A i i 0 9 下列程序段的时间复杂度是 S 0 for i 1 i n i for j 1 j n j s s B i j sum s 10 存储结构是逻辑结构的 实现 11 从数据结构的观点看 通常所说的 数据 应分成三个不同的层次 即 和 12 根据需要 数据元素又被称为 或 13 通常 存储结点之间可以有 四种关联方式 称 为四种基本存储方式 14 通常从 等几方面评价算法 包括程序 的质量 15 一个算法的时空性能是指该算法的 和 前者是算法包含的 后者是算法 需要的 16 在一般情况下 一个算法的时间复杂度是 的函数 17 常见时间复杂度的量级有 常数阶 O 对数阶 O 线性阶 O 平方阶 O 和指 数阶 O 通常认为 具有指数阶量级的算法是 的 18 数据结构的基本任务是数据结构的 和 19 数据对象是性质相同的 的集合 20 抽象数据类型是指一个 以及定义在该模型上的一组操作 四 应用题 1 分析下列程序段的时间复杂度 i 1 WHILE i n i i 2 2 叙述算法的定义及其重要特性 3 简述下列术语 数据 数据元素 数据结构 数据对象 4 逻辑结构与存储结构是什么关系 5 将数量级 210 n n2 n3 nlog2n log2n 2n n 2 3 n n2 3按增长率进行排列 6 设有数据逻辑结构为 D k1 k2 k3 k9 R 画出这个逻辑结构的图示 并确定相对于关系 R 哪些结点是开始结点 哪些结点是终端结点 7 设有如图 1 1 所示的逻辑结构图 给出它的逻辑结构 并说出它是什么类型的逻辑结构 3 8 分析下列程序的时间复杂度 设 n 为正整数 1 int rec int n if n 1 return 1 else return n rec n 1 2 x 91 y 100 While y 0 if x 10 y 3 i 1 j 0 while i jj j else i 4 x n y 0 while x y 1 y 1 y 答 9 设 n 为正数 试确定下列各程序段中前面加记号 的语句的频度 1 i 1 k 0 while i n 1 k 10 i i 2 k 0 for i 1 i n i for j i jnext NULL C head next head D head NULL 10 非空单循环链表 head 的尾结点 p 满足 A p next NULL B p NULL C p next head D p head 11 在双循环链表的 p 结点之后插入 s 结点的操作是 A p next s s prior p p next prior s s next p next B p next s p next prior s s prior p s next p next C s prior p s next p next p next s p next prior s D s prior p s next p next p next pror s p next s 12 在一个单链表中 已知 q 结点是 p 结点的前驱结点 若在 q 和 p 之间插入结点 s 则执行 A s next p next p next s B p next s next s next p C q next s s next p D p next s s next q 13 在一个单链表中 若 p 结点不是最后结点 在 p 之后插入结点 s 则执行 A s next p p next s B s next p next p next s C s next p next p s D p next s s next p 14 若某线性表中最常用的操作是取第 i 个元素和找第 i 个元素的前驱元素 则采用 存储方式最节省时间 A 顺序表 B 单链表 C 双链表 D 单循环链表 15 设 rear 是指向非空带头结点的单循环链表的尾指针 则删除表头结点的操作可表示为 A p rear rear rear next free p B rear rear next free rear C rear rear next next free rear D p rear next next rear next next p next free p 16 在一个单链表中 若删除 p 结点的后继结点 则执行 A q p next p next q next free q B p p next p next p next next free p C p next p next free p next D p p next next free p next 17 设指针 p 指向双链表的某一结点 则双链表结构的对称性可用 式来刻画 A p prior next p next next B p prior prior p next prior C p prior next p next prior D p next next p prior prior 18 在循环链表中 将头指针改设为尾指针 rear 后 其头结点和尾结点的存储位置分别是 A rear 和 rear next next B rear next 和 rear C rear next next 和 rear D rear 和 rear next 19 循环链表的主要优点是 A 不再需要头指针了 B 已知某个结点的位置后 容易找到它的直接前驱 C 在进行插入 删除操作 时 能更好地保证链表不断开 D 从表中任一结点出发都能扫描到整个链表 20 在线性表的下列存储结构中 读取元素花费时间最少的是 A 单链表 B 双链表 C 循环链表 D 顺序表 二 判断题 1 顺序存储的线性表可以随机存取 2 顺序存储的线性表的插入和删除操作不需要付出很大的代价 因为平均每次操作只有近一半的元素需要移动 3 线性表中的元素可以是各种各样的 但同一线性表中的数据元素具有相同的特性 因此是属于同一数据对象 4 在线性表的顺序存储结构中 逻辑上相邻的两个元素在物理位置上不一定相邻 5 在线性表的链式存储结构中 逻辑上相邻的元素在物理位置上不一定相邻 6 在单链表中 可以从头结点开始查找任何一个元素 7 线性表的链式存储结构优于顺序存储结构 8 在线性表的顺序存储结构中 插入和删除元素时 移动元素的个数与该元素的位置有关 9 在单链表中 要取得某个元素 只要知道该元素的指针即可 因此 单链表是随机存取的存储结构 10 顺序存储方式只能用于存储线性结构 三 填空题 1 为了便于讨论 有时将含 n n 0 个结点的线性结构表示成 a1 a2 an 其中每个 ai 代表一个 结点 5 a1 称为 结点 an 称为 结点 i 称为 ai 在线性表中的 对任意一对相邻结点 ai ai 1 1 inext q next free q 6 非空的单循环链表 head 的尾结点 由指针 p 所指 满足 7 rear 是指向非空带头结点的单循环链表的尾指针 则删除起始结点的操作可表示为 q p next p next q next free q 8 对于一个具有 n 个结点的单链表 在 p 所指结点后插入一个结点的时间复杂度为 在给定值为 x 的 结点后插入新结点的时间复杂度为 9 单链表表示法的基本思想是用 表示结点间的逻辑关系 10 在顺序表中插入或删除一个元素 平均需要移动 元素 具体移动的元素个数与 有关 11 在一个长度为 n 的向量的第 i 1 i n 1 个元素之前插入一个元素时 需向后移动 个元素 12 在一个长度为 n 的向量中删除第 i 1 i n 个元素时 需向前移动 个元素 13 在双链表中 每个结点有两个指针域 一个指向 另一个指向 14 在一个带头结点的单循环链表中 p 指向尾结点的直接前驱 则指向头结点的指针 head 可用 p 表示为 head 15 设 head 指向单链表的表头 p 指向单链表的表尾结点 则执行 p next head 后 该单链表构成 16 在单链表中 若 p 和 s 是两个指针 且满足 p next 与 s 相同 则语句 p next s next 的作用是 s 指向的结点 17 设 r 指向单循环链表的最后一个结点 要在最后一个结点之后插入 s 所指的结点 需执行的三条语句是 r next s r s 18 在单链表中 指针 p 所指结点为最后一个结点的条件是 19 在双循环链表中 若要在指 p 所指结点前插入 s 所指的结点 则需执行下列语句 s next p s prior p prior s p prior s 20 在单链表中 若要在 p 所指结点之前插入 s 所指的结点 可进行下列操作 s next p next s temp p data p data s data 四 应用题 1 描述以下三个概念的区别 头指针 头结点 首元结点 第一个元素结点 答 2 何时选用顺序表 何时选用链表作为线性表的存储结构为宜 答 3 在顺序表中插入和删除一个结点需平均移动多少个结点 具体的移动次数取决于哪两个因素 答 4 为什么在单循环链表中设置尾指针比设置头指针更好 答 5 双链表和单循环链表中 若仅知道指针 p 指向某个结点 不知道头指针 能否将结点 p 从相应的链表中删 除 若可以 其时间复杂度各为多少 答 6 下列算法的功能是什么 LinkList testl LinkList L L 是无头结点的单链表 LinkList q p if L 6 while p next p p next p next q q next NULL return L 答 7 如果有 n 个线性表同时共存 并且在处理过程中各表的长度会发生动态变化 线性表的总长度也会自动地改 变 在此情况下 应选择哪一种存储结构 为什么 答 8 若线性表的总数基本稳定 且很少进行插入 删除操作 但要求以最快的方式存取线性表的元素 应该用哪 种存储结构 为什么 答 五 算法设计题 假设算法中用到的顺序表和链表结构如下 define maxsize 100 Typedef struct node1 datatype data maxsize int length SeqList Typedef struct node2 datatype data struct node2 next LinkedList 1 试用顺序表作为存储结构 实现将线性表 a0 a1 a2 an 1 就地逆置的操作 所谓 就地 是指辅助空间为 O 1 答 1 顺序表的就地逆置 2 链表的就地逆置 2 设顺序表 L 是一个递增 允许有相同的值 有序表 试写一算法将 x 插入 L 中 并使 L 仍为一个有序表 答 3 设单链表 L 是一个递减有序表 试写一个算法将 x 插入其中后仍保持 L 的有序性 答 4 试写出在不带头结点的单链表的第 i 个元素之前插入一个元素的算法 答 5 设 A B 是两个线性表 其表中元素递增有序 长度分别为 m 和 n 试写一算法分别以顺序存储和链式存储 将 A 和 B 归并成一个仍按元素值递增有序的线性表 C 答 6 设指针 la 和 lb 分别指向两个不带头结点的单链表的首结点 设计从表 la 中删除第 i 个元素起共 len 个元素 并将这些元素插入到 lb 中第 j 个结点之前的算法 7 单链表 L 是一个递减有序表 试写一高效算法 删除表中值大于 min 且小于 max 的结点 若表中有这样的结 点 同时释放被删结点空间 这里 min 和 max 是两个给定的参数 8 编写一个算法将一个头结点指针为 pa 的单链表 A 分解成两个单链表 A 和 B 其头结点指针分别为 pa 和 pb 使得 A 链表中含有原链表 A 中序号为奇数的元素 而 B 链表中含有原链表 A 中序号为偶数的元素 且保持原来 的相对顺序 9 假设以两个元素值递增有序排列的线性表 A B 分别表示两个集合 要求另辟空间构造一个线性表 C 其元 素为两集合的交集 且表 C 中的元素值也递增有序排列 用顺序表实现并写出 C 的算法 11 假设在长度大于 1 的单循环链表中 既无头结点也无头指针 s 为指向链表中某个结点的指针 试编写算法 删除结点 s 的直接前驱结点 12 计算带头结点的循环链表的结点个数 7 13 已知由单链表表示的线性表中 含有三类字符的数据元素 如 字母字符 数字字符和其他字符 试编写算 法构造三个以循环链表表示的线性表 使得每个表中只含有同一类的字符 且利用原表中的结点空间作为这三个 表的结点空间 头结点可另辟空间 14 己知 A B 和 C 为三个递增有序的线性表 现要求对 A 表进行如下操作 删去那些既在 B 表中出现又在 C 表中出现的元素 试对顺序表编写实现上述操作的算法 注 题中未特别指明同一表中的元素值各不相同 15 双循环链表中 设计满足下列条件的算法 1 在值为 x 的结点之前插入值为 y 的结点 2 删除值为 x 的结点 16 设有一个双循环链表 其中有一结点的指针为 p 编写算法将 p 与其右边的一个结点进行交换 17 设有一个双链表 每个结点中除有 prior data 和 next 三个域外 还有一个可访问频度域 freq 在链表启用 之前 其初始值均为 0 每当链表进行一次 LocateNode L x 操作时令元素值为 x 的结点中 freq 域的值加 l 并 调整表中结点的次序 使其按访问频度的递减次序排列 以便使频繁访问的结点总是靠近表头 试写一符合上述 要求的 LocateNode 操作的算法 18 给出用单链表存储多项式的结构 并编写一个按指数值递增次序输入所产生的多项式链表的过程 19 根据上题的多项式链表结构 编写一个过程实现两个多项式相加的运算 20 约瑟夫环问题 任给正整数 n k 按下述方法可得排列 1 2 n 的一个置换 将数字 l 2 n 环形 排列 按顺时针方向从 1 开始计数 计满 k 时输出该位置上的数字 并从环中删去该数字 然后从下一个数字开 始继续计数 直到环中所有数字均被输出为止 例如 n 10 k 3 时 输出的置换是 3 6 9 2 7 1 8 5 10 分别以数组和以不带头结点的 已知尾指针的单循环链表为存储结构解决上述问 题 第三节第三节 栈和队列栈和队列 一 选择题 1 设有一顺序栈 s 元素 s1 s2 s3 s4 s5 s6 依次入栈 如果 6 个元素出栈的顺序是 s2 s3 s4 s6 s5 s1 则栈的容量至少应该是 A 2 B 3 C 5 D 6 2 若一个栈的输入序列是 a b c 则通过入栈 出栈操作可能得到 a b c 的不同排列个数为 A 4 B 5 C 6 D 7 3 设有一顺序栈已经含有 3 个元素 如图 3 1 所示 元素 a4 正等待入栈 以下序列中不可能出现的出栈序列是 A a3 a1 a4 a2 B a3 a2 a4 a1 C a3 a4 a2 a1 D a4 a3 a2 a1 4 和顺序栈相比 链栈有一个比较明显的优势是 A 通常不会出现栈满的情况 B 通常不会出现栈空的情况 C 插入操作更容易实现 D 删除操作 更容易实现 5 若一个栈的输入序列是 1 2 3 4 n 输出序列的第一个元素是 n 则第 i 个输出元素是 A 不确定 B n i C n i 1 D n i 1 8 6 以下说法正确的是 A 因链栈本身没有容量限制 故在用户内存空间的范围内不会出现栈满情况 B 因顺序栈本身没有容量 限制 故在用户内存空间的范围内不会出现栈满情况 C 对于链栈而言 在栈满状态下 如果再进行入栈操 作 则会发生 上溢 D 对于顺序栈而言 在栈满状态下 如果再进行入栈操作 则会发生 下溢 7 顺序队列的入队操作应为 sq rear 初值为 1 A sq rear sq rear 1 sq data sq rear x B sq data sq rear x sq rear sq rear 1 C sq rear sq rear 1 maxsize sq data sq rear 1 x D sq data sq rear x sq rear x sq rear sq rear 1 maxslze 8 循环队列的入队操作应为 sq rear 初值为 1 A sq rear sq rear 1 sq data sq rear x B sq data sq rear x sq rear sq rear l C sq rear sq rear 1 maxsize sq data sq rear x D sq data sq rear x sq rear sq rear 1 maxsize 9 顺序队列的出队操作为 sq front 初值为 1 A sq front sq front 1 maxsize B sq front sq front 1 C sq rear sq rear 1 maxsize D sq rear sq rear 1 10 循环队列的出队操作为 sq front 初值为 1 A sq front sq front 1 maxsize B sq front sq front 1 C sq rear sq rear 1 maxsize D sq rear sq rear l 11 循环队列的队满条件为 A sq rear 1 maxsize sq front 1 maxsize B sq rear 1 maxsize sq front 1 C sq rear 1 maxsize sq front D sq rear sq front 12 循环队列的队空条件为 A sq rear 1 maxsize sq front 1 maxsize B sq rear 1 maxsize sq front 1 C sq rear 1 maxsize sq front D sq rear sq front 13 如果以链表作为栈的存储结构 则出栈操作时 A 必须判别栈是否满 B 判别栈元素的类型 C 必须判别栈是否空 D 对栈不做任何判别 14 向一个栈顶指针为 Top 的链栈中插入一个 s 所指结点时 其操作步骤为 A Top next s B s next Top next Top next s C s next Top Top s D s next Top Top Top next 15 从栈顶指针为 Top 的链栈中删除一个结点 并将被删结点的值保存到 x 中 其操作步骤为 A x Top data Top Top next B Top Top next x Top data C x Top Top Top next D x Top data 16 在一个链队中 苕 f r 分别为队头 队尾指针 则插入 s 所指结点的操作为 A f next s f s B r next s r s C s next r r s D s next f f s 17 一个栈的入栈序列是 a b c d e 则栈的不可能的输出序列是 A e d c b a B d e c b a C d c e a b D a b c d e 18 一个队列的入队序列是 1 2 3 4 则队列可能的输出序列是 A 4 3 2 1 B 1 2 3 4 C 1 4 3 2 D 3 2 4 1 19 设计一个判别表达式中左 右括号是否配对出现的算法 采用 数据结构最佳 A 线性表的顺序存储结构 B 栈 C 队列 D 线性表的链式存储结构 二 判断题 1 在顺序栈栈满情况下 不能再入栈 否则会产生 上溢 2 与顺序栈相比 链栈的一个优点是插入和删除操作更加方便 3 若一个栈的输入序列为 1 2 3 n 其输出序列的第一个元素为 n 则其输出序列的每个元素 ai 一定满 足 ai i 1 i 1 2 n 4 在链队中 即使不设置尾指针也能进行入队操作 5 在对链队 带头指针 做出队操作时 不会改变 front 指针的值 6 循环队列中元素个数为 rear front 7 一个栈的输入序列是 1 2 3 4 则在栈的输出序列中可以得到 4 3 1 2 8 一个栈的输入序列是 1 2 3 4 则在栈的输出序列中可以得到 1 2 3 4 9 9 若以链表作为栈的存储结构 则入栈需要判断栈是否满 10 若以链表作为栈的存储结构 则出栈需要判断栈是否空 三 填空题 1 向一个栈顶指针为 Top 的链栈中插入一个 s 所指的结点时 其进行的操作是 Top s 2 从栈顶指针为 Top 的链栈中删除一个结点 并将结点保存在 x 中 进行的操作是 Top Top next 3 在具有 n 个单元的循环队列中 队满时共有 n 1 个元素 4 假设以 S 和 X 分别表示入栈和出栈操作 则对输入序列 a b c d e 进行一系列栈操作 SSXSXSSXXX 之 后 得到的输出序列为 5 设有数组 A m 作为循环队列的存储空间 front 为队头指针 rear 为队尾指针 则元素 x 执行入队操作的语句 是 A rear x 6 在一个链队中 如果 f r 分别为队头 队尾指针 则插入 s 所指结点的操作是 7 栈的逻辑特点是 队列的逻辑特点是 二者的共同特点是 8 可以作为实现递归函数调用的一种数据结构 9 在队列中 新插入的结点只能添加到 10 链队在一定范围内不会出现 的情况 当 lq front lq rear 时 队中无元素 此时 11 设一个链栈的栈顶指针为 ls 栈中结点的格式为 data next 栈空的条件是 如果栈不为空 则 出栈操作为 p ls free p 12 对带有头结点的链队 lq 判定队列中只有一个数据元素的条件是 13 设有一个空栈 现在输入序列为 1 2 3 4 5 经过 push push pop push pop push 后 栈顶指针所 指元素是 14 设用一维数组 A n 来表示一个栈 令 A 0 为栈底 用整型变量 t 来指示当前栈顶的位置 A t 为栈顶元素 往栈中压入一个新元素时 变量 t 的值 从栈中弹出一个元素时 变量 t 的值 设 空栈时 输入序列 a b c 经过 push pop push push pop 操作后 从栈中弹出的元素是 四 应用题 2 设有字符串为 3 y a y 2 试利用栈写出将其转换为 3y ay2 的操作过程 假定用 X 代表扫描该字符串过程 中顺序取一个字符入栈的操作 用 S 代表从栈中取出一个字符加入到新字符串尾的出栈操作 例如 ABC 变为 BCA 的操作步骤为 XXSXSS 答 3 设有一个输入序列 a b c d 元素经过一个栈到达输出序列 而且元素一旦离开输入序列就不能再回到输 入序列 试问经过这个栈后可以得到多少种输出序列 答 4 按照运算符优先法 画出对下面算术表达式求值时 操作数栈和运算符栈的变化过程 9 2 4 8 1 3 答 5 链栈中为何不设置头结点 答 第四节第四节 数组数组 一 选择题 1 数组通常具有的两种基本操作是 A 建立和删除 B 索引和修改 C 查找和修改 D 查找和索引 2 二维数组 A 11 6 采用行序为主序方式存储 每个数据元素占 4 个存储单元 且 A 0 0 的存储地址是 1000 则 A 8 4 的存储地址是 A 1208 B 1212 C 1368 D 1364 3 对矩阵压缩存储是为了 A 方便运算 B 节省空间 C 方便存储 D 提高运算速度 4 稀疏矩阵的压缩存储方法通常有两种 即 A 二元数组和三元数组 B 三元组和散列 C 三元组和十字链表 D 散列和十字链表 10 二 判断题 1 数组是同类型值的集合 2 数组是一组连续的内存单元 3 数组是一种复杂的数据结构 数组元素之间的关系既不是线性的也不是树形的 4 插入和删除操作是数据结构中最基本的两种操作 所以这两种操作在数组中也经常使用 5 使用三元组表示稀疏矩阵的元素 有时并不能节省存储空间 三 填空题 1 二维数组 A 10 20 采用列序为主序方式存储 每个元素占一个存储单元 并且 A 1 1 的存储地址是 200 则 A 6 12 的地址是 2 有一个 10 阶对称矩阵 A 采用压缩存储方式 以行序为主序方式 存储其下三角元素 且第一个元素 A 0 0 的 存储地址为 1 则 A 4 5 的地址是 A 8 3 的地址是 3 下三角矩阵 A N N 的下三角元素已压缩到一维数组 S N N 1 2 中 若按行序为主序存储 则 A i j 对应 的 S 中的存储位置是 四 应用题 1 假设有二维数组 A 6 8 每个元素用相邻的 6 个字节存储 存储器按字节编址 已知 A 的起始地址 基地址 为 1000 计算 1 数组 A 的容量 2 按行优先方式存储时 元素 A 1 4 的地址 3 按列优先方式存储时 元 素 A 4 7 的地址 答 2 设有三对角矩阵 A n n 将其三条对角线上的元素逐行存放于数组 B 3n 3 中 使得 B k A i j 求 1 用 i j 表示 k 的下标变换公式 2 用 k 表示 i j 的下标变换公式 答 3 画出图 5 2 所示的稀疏矩阵 A 的三元组表和十字链表 答 4 用三元组表表示图 5 3 所示的稀疏矩阵的转置矩阵 答 第五节 树 树根结点的高度为 1 一 选择题 1 以下说法错误的是 A 树形结构的特点是一个结点可以有多个直接前驱 B 线性结构中的一个结点至多只有一个直接后继 C 二叉树与树是两种不同的数据结构 D 树 及一切树形结构 是一种 分支层次 结构 2 以下说法错误的是 A 二叉树可以是空集 B 二叉树的任一结点都有两棵子树 C 二叉树与树具有相同的树形结构 D 二叉 树中任一结点的两棵子树有次序之分 11 3 以下说法错误的是 A 完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达 B 在三叉链表上 二叉树的求双亲 操作很容易实现 C 在二叉链表上 求根以及求左 右孩子等操作很容易实现 D 在二叉链表上 求双亲操 作的时间性能很好 4 以下说法错误的是 A 一般在哈夫曼树中 权值越大的叶子离根结点越近 B 哈夫曼树中没有度数为 1 的分支结点 C 若初 始森林中共有 n 棵二叉树 最终求得的哈夫曼树共有 2n 1 个结点 D 若初始森林中共有 n 棵二叉树 进行 2n 1 次合并后才能剩下一棵最终的哈夫曼树 5 深度为 6 的二叉树最多有 个结点 A 64 B 63 C 32 D 31 6 将含有 41 个结点的完全二叉树从根结点开始编号 根为 1 号 后面按从上到下 从左到右的顺序对结点编号 那么编号为 21 的双亲结点编号为 A 10 B 11 C 41 D 20 7 任何一棵二叉树的叶结点在其前序 中序 后序遍历序列中的相对位置 A 肯定发生变化 B 有时发生变化 C 肯定不发生变化 D 无法确定 8 设二叉树有 n 个结点 则其深度为 A n 1 B n C log2n 1 D 无法确定 9 设深度为 k 的二叉树上只有度为 0 和度为 2 的结点 则这类二叉树上所含结点总数最少 个 A k l B 2k C 2k 1 D 2k 1 10 下列说法正确的是 A 树的前序遍历序列与其对应的二叉树的前序遍历序列相同 B 树的前序遍历序列与其对应的二叉树的 后序遍历序列相同 C 树的后序遍历序列与其对应的二叉树的前序遍历序列相同 D 树的后序遍历序列 与其对应的二叉树的后序遍历序列相同 11 下列说法中正确的是 A 任何一棵二叉树中至少有一个结点的度为 2 B 任何一棵二叉树中每个结点的度都为 2 C 任何一棵 二叉树中的每个结点的度肯定等于 2 D 任何一棵二叉树中的每个结点的度都可以小于 2 12 一棵二叉树满足下列条件 对任意结点 若存在左 右子树 则其值都小于它的左子树上所有结点的值 而 大于右子树上所有结点的值 现采用 遍历方式就可以得到这棵二叉树所有结点的递减序列 A 前序 B 中序 C 后序 D 层次 13 设森林 T 中有 4 棵树 结点个数分别是 n1 n2 n3 n4 当把森林 T 转换成一棵二叉树后 根结点的右子 树上有 个结点 A n1 1 B n1 C n1 n2 n3 D n2 n3 n4 14 对含有 个结点的非空二叉树 采用任何一种遍历方式 其结点访问序列均相同 A 0 B 1 C 2 D 不存在这样的二叉树 15 如图 6 1 所示的二叉树的中序遍历序列是 A abcdgef B dfebagc C dbaefcg D defbagc 16 已知某二叉树的后序遍历序列是 deacb 中序遍历序列是 deabc 它的前序遍历序列是 A acbed B baedc C dceab D cedba 17 如果 T1 是由有序树转化而来的二叉树 那么 T 中结点的前序就是 T1 中结点的 12 A 前序 B 中序 C 后序 D 层次序 18 某二叉树的前序遍历的结点访问顺序是 abdgcefh 中序遍历的结点访问顺序是 dgbaechf 则其后序遍历的结 点访问顺序是 A bdgcefha B gdbecfha C bdgechfa D gdbehfca 19 在图 6 2 中的二叉树中 不是完全二叉树 20 树最适合用来表示 A 有序数据元素 B 无序数据元素 C 元素之间具有分支层次关系的数据 D 元素之间无联系的 数据 21 在计算递归函数时 如不使用递归过程 则一般情况下必须借助于 数据结构 A 栈 B 树 C 双向队列 D 顺序表 22 设二叉树根结点的层次为 0 一棵高度为 h 的满二叉树中的结点个数是 A 2h B 2h 1 C 2h 1 D 2h 1 1 23 以下说法错误的是 A 存在这样的二叉树 对它采用任何次序的遍历 其结点访问序列均相同 B 二叉树是树的特殊情形 C 由树转换成二叉树 其根结点的右子树总是空的 D 在二叉树只有一棵子树的情况下也要明确指出该子 树是左子树还是右子树 24 已知一个算式的中缀表达式为 a b c d 则其后缀表达式是 A a b c d B abc d C bc d a D a bc d 25 按照二叉树的定义 具有 4 个结点所能构造的不同的二叉树的个数是 A 4 B 8 C 12 D 14 26 在一棵度为 3 的树中 度为 3 的结点的个数为 2 度为 2 的结点的个数为 1 则度为 0 的结点的个数为 A 4 B 5 C 6 D 7 27 3 个结点可构成 棵不同形态的二叉树 A 2 B 3 C 4 D 5 28 哈夫曼树的带权路径长度是 A 所有结点权值之和 B 所有叶结点带权路径长度之和 C 带权结点的值 D 除根以外所有结点权 值之和 29 设有一棵 22 个结点的完全二叉树 那么整棵二叉树有 个度为 0 的结点 A 6 B 7 C 8 D 11 30 已知完全二叉树有 26 个结点 则整棵二叉树有 个度为 1 的结点 A 0 B 1 C 2 D 13 31 在树的孩子兄弟表示法中 操作花时间最多 A 求某结点的兄弟 B 求某结点的第 i 个孩子 C 求某结点的父结点 D 求树的根结点 32 已知如图 6 3 所示的哈夫曼树 那么电文 CDAA 的编码是 A 110100 B 11011100 C 010110111 D 11111100 13 33 在 n 个结点的完全二叉树中 对任一结点 i 1 i n i 的左孩子可能是 A i 2 B 2i 1 C 2i D 都不是 34 已给出图 6 3 所示的二叉树 A B C D 的权值分别为 7 5 2 4 则该树的带权路径长度为 A 46 B 36 C 35 D 都不是 35 下列叙述中不正确的是 A 二叉树是度为 2 的有序树 B 二叉树中结点只有一个孩子时有左右之分 C 二叉树中必有度为 2 的结 点 D 二叉树中结点最多有两棵子树 并且有左右之分 36 图 6 4 所示的几种结构中属于树形结构的是 二 判断题 1 二叉树是树的特殊形式 2 树和二叉树之间最主要的差别是 二叉树的结点的子树要区分为左右子树 即使在结点只有一棵子树的情况 下也要明确指出该子树是左子树还是右子树 3 一棵有 n 个结点的 d 度树 若用多重链表表示 树中每个结点都有 d 个链域 则在树的 n d 个链域中 有 n d 1 1 个是空链域 只有 n 1 个是非空的 4 前序遍历树和前序遍历与该树对应的二叉树 其结果相同 5 中序遍历树和中序遍历与该树对应的二叉树 其结果不同 6 前序遍历森林和前序遍历与该森林对应的二叉树 其结果相同 7 中序遍历森林和中序遍历与该森林对应的二叉树 其结果不同 8 若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点 则它必须是该子树的前序遍历序列中的最 后一个结点 9 二叉树中具有两个子女的父结点 在中序遍历序列中 它的后继结点最多只能有一个子女 10 在二叉树中 具有一个子女的父结点 在中序遍历中 它没有后继的子女结点 11 在二叉树中插入结点 该二叉树便不再是二叉树 12 用一维数组存储二叉树时 总是以前序遍历存储结点 13 已知二叉树的前序遍历和后序遍历序列不能惟一地确定这棵树 14 不使用递归 也可以实现二叉树的前序 中序 后序遍历 15 在前序遍历二叉树的序列中 任何结点的子树的所有结点都是直接跟在该结点之后 16 有 n 个结点的不同二叉树有 n 棵 17 在哈夫曼编码中 当两个字符出现的频率相同时 其编码也相同 对于这种情况应做特殊处理 三 填空题 1 树 及一切树形结构 是一种 结构 在树中 结点没有直接前驱 对树上任一结点 x 来 说 x 是它的任一子树的根结点惟一的 2 一棵树上的任何结点 不包括根本身 称为根的 若 B 是 A 的子孙 则称 A 是 B 的 3 二叉树第 i i 0 层上至多有 个结点 4 深度为 k k 0 的二叉树至多有 个结点 5 对任何二叉树 若度为 2 的节点数为 n2 则叶子数 n0 14 6 满二叉树上各层的节点数已达到了二叉树可以容纳的 满二叉树也是 二叉树 但反之 不然 7 具有 n 个结点的完全二叉树的深度为 8 在顺序存储的二叉树中 编号为 i 和 j 的两个结点处在同一层的条件是 9 如果将一棵有 n 个结点的完全二叉树按层编号 则对任一编号为 i 0 il 则 X 的双亲 PARENT X 的编号为 2 若 2i n 则结点 x 无 且无 否则 X 的左孩子 LCHILD X 的编号为 3 若 2i 1 n 则结点 X 无 否则 X 的右孩子 RCHILD X 的编号为 10 二叉树通常有 存储结构和 存储结构两类存储结构 11 每个二叉链表还必须有一个指向 结点的指针 该指针具有标识二叉链表的作用 12 对二叉链表的访问只能从 指针开始 13 具有 n 个结点的二叉树中 一共有 个指针域 其中只有 个用来指向结点的左右孩子 其余的 个指针域为 NULL 14 已知二叉树中叶子数为 40 仅有一个孩子的结点数为 20 则总结点数为 15 二叉树有不同的链式存储结构 其中最常用的是 与 16 可通过在非完全二叉树的 残缺 位置上增设 将其转化为完全二叉树 17 具有 100 个结点的完全二叉树的深度是 18 深度为 90 的满二叉树上 第 10 层有 个结点 19 在 遍历二叉树的序列中 任何结点的子树上的所有结点都是直接跟在该结点之后 20 具有 n 个结点的完全二叉树 若按层次从上到下 从左到右对其编号 根结点为 1 号 则编号最大的分支结 点序号是 编号最小的分支结点序号是 编号最大的叶结点序号是 编号最 小的叶结点序号是 21 若一棵二叉树的叶子数为 n 则该二叉树中左 右子树皆非空的结点个数为 22 任意一棵具有 n 个结点的二叉树 若它有 m 个叶子 则该二叉树上度数为 1 的结点为 n 个 23 设有 30 个值 用它们构造一棵哈夫曼树 则该哈夫曼树中共有 个结点 24 现有按中序遍历二叉树的结果为 ABC 有 种不同形态的二叉树可以得到这一遍历结果 25 以数据集 4 5 6 7 10 为叶结点的权值所构造的哈夫曼树的带权路径长度为 26 已知一棵度为 3 的树有 2 个度为 1 的结点 3 个度为 2 的结点 4 个度为 3 的结点 则该树中有 个叶结点 27 设树 T 的度为 4 其中度为 1 2 3 和 4 的结点个数分别是 4 2 1 和 1 则 T 中叶结点的个数是 28 如果结点 a 有三个兄弟 而 b 是 a 的双亲 则 b 的度是 29 一棵树的形状如图 6 5 所示 它的根结点是 叶结点是 结点 H 的度是 这棵树的度是 这棵树的深度是 结点 F 的儿子结点是 结点 G 的父结 点是 30 设结点 x 有左孩子结点 y 右孩子结点 z 用三种基本遍历方法得到的遍历序列中 x 是 y 的前 15 驱 x 是 z 的后继 y 是 z 的前驱 填 一定 不 不一定 31 在树结构里 有且仅有一个结点没有前驱 称为根 非根结点有且仅有一个 且存在一条从根 到该结点的 32 含有 2n个结点的二叉树高度至少是 至多是 仅含根结点的二叉树高度为 1 33 设高度为 h 的二叉树只有度为 0 和 2 的结点 则此类二叉树的结点数至少为 至多为 四 应用题 1 分别画出含 3 个结点的树与二叉树的所有不同形态 答 2 设在树中 结点 x 是结点 y 的双亲 用来表示边 已知一棵树边的集合为 用树形表示法画出 此树 并回答下列问题 1 哪个是根结点 2 哪些是叶结点 3 哪个是 g 的双亲 4 哪些是 g 的祖先 5 哪些是 e 的子孙 6 哪 些是 f 的兄弟 7 结点 b 和 j 的层次各是多少 8 树的深度是多少 9 树的度数是多少 答 3 任意一个有 n n 0 个结点的二叉树 已知它有 m 个叶结点 试证明非叶结点有 m 1 个度为 2 其余度为 1 答 4 分别画出图 6 6 所示二叉树的二叉链表 三叉链表和顺序存储结构 答 5 分别写出图 6 7 所示二叉树的前序 中序和后序序列 答 6 已知一棵二叉树的中序序列和后序序列分别为 BDCEAFHG 和 DECBHGFA 试画出这棵二叉树 并写出其前 序遍历序列 答 7 二叉树中的结点进行按层次顺序 每层自左到右 的访问操作称为二叉树的层次遍历 遍历所得到的结点序列 称为二叉树的层次序列 现已知一棵二叉树的层次序列为 ABCDEFGHIJ 中序序列为 DBGEHJACIF 请画出该 二又树 答 8 将图 6 9 所示的森林转换成二叉树 16 答 9 分别画出图 6 10 所示二叉树对应的森林 并写出森林的前序和后序遍历序列 答 10 设某密码电文由 8 个字母组成 每个字母在电文中的出现频率分别是 7 19 2 6 32 3 21 10 试为 这 8 个字母设计相应的哈夫曼编码 答 11 将代数式 y 3 x a a x2描述成表达式树 并写出前缀式和后缀式 答 13 试证明 任一棵高度为 h 1 的二叉树 其内部结点 除根 叶子之外的结点 的数目小于 2h 1 1 而叶结点数 目小于或等于 2h 1 答 15 一棵度为 k 的树有 n1 个度为 1 的结点 n2 个度为 2 的结点 nk 个度为 k 的结点 问该树中有多少个 叶结点 16 一棵含有 n 个结点的 k 叉树 可能达到的最大深度和最小深度各是多少 答 17