数据结构(本科)形成性考核册答案

1 作业 1 一 单项选择题 1 C 2 D 3 B 4 C 5 D 6 C 7 B 8 C 9 A 10 B 11 C 12 D 13 C 14 A 15 B 16 C 17 C 18 B 19 B 20 D 二 填空题 1 n i 1 2 n i 3 集合 线性结构 树形结构 图状结构 4 物理结构 存储结构 5 线性结构 非线性结构 6 有穷性 确定性 可形性 有零个或多个输入 有零个或多个输出 7 图状结构 8 树形结构 9 线性结构 10 n 1 O n 11 s next p next 12 head 13 q next p next 14 p next head 15 单链表 16 顺序存储 链式存储 17 存储结构 18 两个 直接后继 直接前驱 尾结点 头结点 19 头结点的指针 指向第一个结点的指针 20 链式 链表 三 问答题 1 简述数据的逻辑结构和存储结构的区别与联系 它们如何影响算法的设计与实现 答 若用结点表示某个数据元素 则结点与结点之间的逻辑关系就称为数据的逻辑结构 数据在计算机 中的存储表示称为数据的存储结构 可见 数据的逻辑结构是反映数据之间的固有关系 而数据的存储 结构是数据在计算机中的存储表示 尽管因采用的存储结构不同 逻辑上相邻的结点 其物理地址未必 相同 但可通过结点的内部信息 找到其相邻的结点 从而保留了逻辑结构的特点 采用的存储结构不 同 对数据的操作在灵活性 算法复杂度等方面差别较大 2 解释顺序存储结构和链式存储结构的特点 并比较顺序存储结构和链式存储结构的优缺点 答 顺序结构存储时 相邻数据元素的存放地址也相邻 即逻辑结构和存储结构是统一的 要求内存中存储 单元的地址必须是连续的 优点 一般情况下 存储密度大 存储空间利用率高 缺点 1 在做插入和删除操作时 需移动大量元素 2 由于难以估计 必须预先分配较大的空间 往往使存储空间不能得到充分利用 3 表的容量难以扩充 链式结构存储时 相邻数据元素可随意存放 所占空间分为两部分 一部分存放结点值 另一部分存放 表示结点间关系的指针 优点 插入和删除元素时很方便 使用灵活 缺点 存储密度小 存储空间利用率低 2 3 什么情况下用顺序表比链表好 答 顺序表适于做查找这样的静态操作 链表适于做插入和删除这样的动态操作 如果线性表的变化长 度变化不大 且其主要操作是查找 则采用顺序表 如果线性表的长度变化较大 且其主要操作是插入 删除操作 则采用链表 4 解释头结点 第一个结点 或称首元结点 头指针这三个概念的区别 答 头结点是在链表的开始结点之前附加的一个结点 第一个结点 或称首元结点 是链表中存储第一个数 据元素的结点 头指针是指向链表中第一个结点 或为头结点或为首元结点 的指针 5 解释带头结点的单链表和不带头结点的单链表的区别 答 带头结点的单链表和不带头结点的单链表的区别主要体现在其结构上和算法操作上 在结构上 带头结点的单链表 不管链表是否为空 均含有一个头结点 不带头结点的单链表不含头结 点 在操作上 带头结点的单链表的初始化为申请一个头结点 无论插入或删除的位置是地第一个结点还是 其他结点 算法步骤都相同 不带头结点的单链表 其算法步骤要分别考虑插入或删除的位置是第一个 结点还是其他结点 因为两种情况的算法步骤不同 四 程序填空题 1 1 p data i 2 p next NULL 3 q next p 4 q p 2 1 head p 2 q p 3 p next NULL 4 p next q next 5 q next p 3 1 p q next 2 q next p next 作业 2 一 单选 CBAAC AACCC BCBBC CBAAD BAABD ACDCA D 二 填空 1 堆栈 2 加 1 3 rear 值 1 fear 值 1 3 4 假上溢 5 队列是否已满 sq MaxSize 尾指针的值 尾指针指向的数据单元 队列是否为空 sq sq front 队头指针加 1 返回 front 所指位置的元素 6 bceda 7 终止条件 递归条件 8 LU rear Lu front 9 ab c fdc 10 s next h 11 h h next 12 r next s 13 f f next 14 字符 15 顺序存储 链接存储 16 0 1 17 特殊 稀疏 18 2 19 d e f 20 两串的长度相等 且对应位置上的字符相同 21 i i 1 2 j 22 行号 列号 元素值 三 简答 1 一般线性表使用数组来表示的 线性表一般有插入 删除 读取等对于任意元素的操作 而栈只是一种特殊的线性表 栈只能在线性表的一端插入 称为入栈 push 或者读取栈顶 元素或者称为 弹出 出栈 pop 栈在数组的基础上可以用一个指向栈顶的标识符来表 示 如 a 表示栈 则 a top 就表示栈顶元素 2 队列是一种运算受限的线性表 它的运算限制与栈不同 是两头都有限制 插入只能在表的一端进行 只进不出 而删除只能在表的另一端进行 只出不进 而一般线性表是用数组来表示的 线性表一般有插入 删除 读取等对于任意元素的操作 3 如果你的栈有头结点且头结点不存储有效数据 且 sq 指向栈顶的有效数据 那么 sq next NULL 表示栈空 如果你的栈有头结点且头结点存储有效数据 且 sq 指向栈顶的有效数据 那么 sq NULL 表示栈空 4 1 CBA ABC BAC BCA ACB 可根据栈的特点 后进先出 来的出结果 不可能的是 CAB 2 可能的输出序列 ABCD ABDC ACBD ACDB ADCB BACD BADC BCAD BCDA BDCA CBAD CBDA CDBA DCBA 共 14 种 不可能的输出序列 ADBC BDAC CDAB CABD CADB DCAB DABC DACB DBCA DBAC 共 10 种 5 SXSSXSXX 6 以元素 C 开头的有 CBADE CBAED CBDAE CBDEA CDBAE CDBEA CDEBA CEDBA 以元素 D 开头的有 DCBAE DCEBA DCBEA DECBA 7 第一个有问题 3x2x 1x 5 AB C DEF G 8 一般线性表使用数组来表示的 线性表一般有插入 删除 读取等对于任意元素的操作 广义表是线性表的推广 也称为列表 也是一种线性结构 任何一个非空表 表头可能是原子 也可能是列表 但表尾一定是列表 广义表中元素既可以是原子类型 也可以是列表 当每个元素都为原子且类型相同时 就是线性表 四 1 这个题目拿不准 4 1 q front p next 2 free p 3 else front rear p 五 1 栈的特点是先进后出 而出队的序列 e2 首 即 e1 肯定在栈中 然后是 e4 这样 e1 e3 e4 必须同时在栈中 才能保证 e4 出栈 然后是 e3 出栈 此时只有 e1 在栈中 然后是 e6 出栈 这样 必须保证 e1 e5 e6 同时在栈中 因此 此栈容量最小为 3 2 不会 作业 3 一 单选 BBBCB ABCAD ACCBB C1CAB BBBBD DAC 17 题答案 好像是 1 倍 二 填空 1 非空子树 2 树中所有结点的度的最大值 3 分支结点 非终端结点 4 叶子结点 分支结点 5 后继 孩子结点 6 祖先 7 树中结点的最大层数 8 n 1 2 9 根结点 左子树 右子树 10 左子树 根结点 右子树 11 第一个空不填 左子树 右子树 根结点 12 权 13 带权路径长度之和 14 最优二叉树 最小的二叉树 15 76 16 2n 1 个 17 多对多 18 所有的顶点 一次 19 先序 20 按层 21 n 22 邻接矩阵 邻接表 23 2 n 1 24 n 1 25 一维数组 三 综合 1 1 先序 fdbacegihj 2 中序 abcdefghij 3 后序 acbedhjigf 2 此树如下 表示分隔 表示靠左边的距离 只要斜线 其它不要画 A B C D e f 5 G H I J L K M 其后序遍历 GDBLHKMIEJFCA 3 1 树高为 X 则 2 x 892 2 x 1 表示乘方 则 X 应为 10 即树高为 10 2 叶子结点数为结点数一半 即 892 2 446 个 3 因为这是一棵完全二叉树 有 892 个结点 892 1 891 为单数 故单支结点数为 1 个 4 最后一个非终端结点的序号为 892 2 446 4 1 A B C 2 A B C 3 A 5 不会 6 不会 7 1 V1 V2 V5 本题目有错误 多了个 V3 V4 划去一个 V4 V3 只画线 不要 2 邻接矩阵为 大括号要画到最后一行 v1 v2 v3 v4 v5 a1 0 1