数据结构课本习题答案.doc

数据结构数据结构 第一章第一章绪论绪论 一 一 单项选择题单项选择题 1 1 A 2 B 2 1 B 2 D 3 C 4 A 5 A 6 1 C 2 A 7 1 C 2 A 8 C 9 C 10 B 11 D 二 填空题二 填空题 1 存储结构 存储结构 算法 算法 2 非线性结构 非线性结构 3 线性 树型 线性 树型 图形图形 4 映射 映射 5 线性结构 树型结构 线性结构 树型结构 图形结构 图形结构 6 有穷性 确定性 有穷性 确定性 可行性 可行性 7 错误 错误 三 算法分析三 算法分析 1 1 O n 2 O n 3 O n 4 O n 5 O 6 n O O log3n 7 7 O O log2n 2 1 order 函数是一个递归排序过程 设函数是一个递归排序过程 设 T n 是排序 是排序 n 个元素所需要的时间 在排序个元素所需要的时间 在排序 n 个元素时 算法的计算时间主要花费在递归调用个元素时 算法的计算时间主要花费在递归调用 order 上 第一调用时 处理的元素序上 第一调用时 处理的元素序 列个数为列个数为 n 1 也就是对余下的 也就是对余下的 n 1 个元素进行排序 所需要的计算时间应为个元素进行排序 所需要的计算时间应为 T n 1 又因 又因 为在其中的循环中 需要为在其中的循环中 需要 n 1 次比较 所以排序次比较 所以排序 n 个元素所需要的时间为 个元素所需要的时间为 T n T n 1 n 1 n 1n 1 据此可得 据此可得 T 1 0 T 2 T 1 1 0 1 1 T n T n 1 n 1 n 1n 1 求解过程为 求解过程为 T n T n 2 n 2 n 1 T n 3 n 3 n 2 n 1 T 1 1 2 T 1 1 2 n 1n 1 0 1 2 0 1 2 n 1n 1 n n 1 n n 1 2 2 O n2 故故 order 函数的时间复杂度为函数的时间复杂度为 O n2 2 解 设 解 设 fact n 数是数是 T n 该函数中语句 该函数中语句 If n 1n 1 return1 的运行时间是的运行时间是 O 1 语句 语句 return n fact n 1 运行时间是运行时间是 T n 1 O 1 其中其中 O 1 为乘法运算的时间 为乘法运算的时间 因此因此 T n O 1 n 1n 1 T n T n 1 O 1 n n 1 1 则则 T n O 1 T n 1 2 O 1 T n 2 n 1 O 1 T 1 n 1 O 1 T 1 n O 1 n O 1 O n O n 即即 fact n 的时间复杂度为的时间复杂度为 O n O n 3 3 解 设 解 设 FnFn 的时间复杂度为的时间复杂度为 T n T n 有 有 T n T n 1 T n 2 2T2T n 1 2 2 T T n 2 2 2 2 T T 0 n O 2 n 又 又 T n T n 1 T n 2 2T2T n 2 2 2 T T n 4 2 2 2T T 1 n 为奇数时 或为奇数时 或 2 2T T 0 n 为偶数时 为偶数时 2 n 2 n 即 即 T n O 2 2 2 n 则 则 O 2 2 T n T n O O 2 2 n n 取最坏情况上限 即取最坏情况上限 即 T n T n O O 2 n 第二章 线性表第二章 线性表 一 单项选择题一 单项选择题 1 A 2 B 3 C 4 A 5 D 6 D 7 D 8 B 9 B 10 C 11 A 12 A 13 A 14 D 15 C 16 B 17 B 18 D 二 判断题二 判断题 1 F 2 T 3 F 4 F 5 F 6 F 7 F 8 F 9 F 10 F 三 填空题三 填空题 1 顺序 顺序 2 n 1 1 2 2 3 py next px next y next px next px next py px next py 4 n i 1 5 1 便于处理首元结点 使得在创建链表和删除结点时 可以将首元结点与其他结点同 便于处理首元结点 使得在创建链表和删除结点时 可以将首元结点与其他结点同 等对待 等对待 2 利用头结点的数据域存储链表的相关信息 利用头结点的数据域存储链表的相关信息 6 O 1 O n 7 单链表和多重链表 单链表和多重链表 动态链表和静态链表动态链表和静态链表 8 f next p next next p next f prior p prior p p next prior f p next prior f p next f p next f 9 指针 指针 10 物理上相邻 物理上相邻 指针指针 四 简答题四 简答题 1 1 由于链式存储结构可以用任意的存储空间来存储线性表中的各数据元素 且其存储 由于链式存储结构可以用任意的存储空间来存储线性表中的各数据元素 且其存储 空间可以是连续的 也可以是不连续 此外 这种存储结构对元素进行插入和删除操作时空间可以是连续的 也可以是不连续 此外 这种存储结构对元素进行插入和删除操作时 都无需移动元素 而仅仅修改指针即可 所以很适用于线性表容量变化的情况 都无需移动元素 而仅仅修改指针即可 所以很适用于线性表容量变化的情况 2 由于顺序存储结构一旦确定了起始位置 线性表中的任何一个元素都可以进行随机 由于顺序存储结构一旦确定了起始位置 线性表中的任何一个元素都可以进行随机 存取 即存取速度较高 并且 由于线性表的总数基本稳定 且很少进行插入和删除 故存取 即存取速度较高 并且 由于线性表的总数基本稳定 且很少进行插入和删除 故 这一特点恰好避开了顺序存储结构的缺点 因此 应选用顺序存储结构 这一特点恰好避开了顺序存储结构的缺点 因此 应选用顺序存储结构 2 不一定 由于链式存储需要额外的空间来存储指针 所以要比顺序存储多占用空间 在 不一定 由于链式存储需要额外的空间来存储指针 所以要比顺序存储多占用空间 在 空间允许的情况下 链式存储结构可以克服顺序存储结构弱点 但空间不允许时 链表存空间允许的情况下 链式存储结构可以克服顺序存储结构弱点 但空间不允许时 链表存 储结构会出现新的问题 储结构会出现新的问题 3 该线性表宜采用链表存储结构 因为采用链式存储结构的线性表 插入和删除操作只需 该线性表宜采用链表存储结构 因为采用链式存储结构的线性表 插入和删除操作只需 要改变指针 时间复杂度为要改变指针 时间复杂度为 O 1 而采用顺序存储结构的线性表插入和删除涉及到数据 而采用顺序存储结构的线性表插入和删除涉及到数据 的大量移动 时间复杂度为的大量移动 时间复杂度为 O n 4 线性结构包括线性表 栈 队列 串 线性表的存储结构又分成顺序存储和链式存储 线性结构包括线性表 栈 队列 串 线性表的存储结构又分成顺序存储和链式存储 用用 C 语言描述语言描述 顺序存储类型 顺序存储类型 Typedef struct ElemType data maxlen 存放元素存放元素 int len 存放长度存放长度 Sqlist 链式存储类型 链式存储类型 Typedef struct node ElemType data 数据域数据域 struct node next 指针域指针域 SNode 5 先找到值为 先找到值为 23 和和 15 的两个结点 的两个结点 q 指向值为指向值为 23 的结点 的结点 p 指向值为指向值为 15 的结点 的结点 p 和和 q 结点互换 结点互换 q llink rlink p llink rlink p p llink q llink p llink q llink p rlink q q llink p rlink q q llink p q rlink null q rlink null 6 1 p rlink llink p llink rlink llink p llink p llink rlink p llink rlink p rlink rlink disposedispose p p 2 2 newnew q q q llink p q llink p q rlink p rlink q rlink p rlink p rlink llink q p rlink llink q p rlink q p rlink q 五 算法分析五 算法分析 1 1 VoidVoid InsertInsert Lnode Lnode head head ElemType x ElemType y LnodeLnode q q p p q q head head p p q next q next while p data xwhile p data x p p p nextp next if p null p next s next s else s LnodeLnode malloc sizeof LnodeLnode s data x data x s next p next p q next s next s 2 Void getVoionList SqList pa A next next pb B next pb B next C C A A A next null next null while pa null pa pa next q next C next next q next C next C next q C next q elseelse q pb q pb pb pb next q next C next pb pb next q next C next C next q C next q ifif pa pa null null whilewhile pa pa null null q pa q pa pa pa next q next C next next q next C next C next q C next q ifif pb null pb null whilewhile pb null pb null q pb q pb pb pb nextpb pb next q next q next C next C next C next C next q q 3 3 StateState changeListchangeList SqList SqList q a a headaheada b b headb headb count 1 count 1 if i if i 1 1 for for k 1 k 1 k len k len k k q q headaheada ifif q q NULL NULL returnreturn Error Error heada heada heada next heada next free q free q else else whilewhile a a null null a a next count count ifif a a NULL NULL returnreturn Error Error forfor k 1 k 1 k len k len k k q a next q a next ifif q q NULL NULL returnreturn Error Error a next q next a next q next free q free q ifif pa pa NULL NULL returnreturn ok ok p pa p pa while p next NULL while p next NULL p p next p p next if jif j 1 1 p next p next headb headb headb heada headb heada elseelse q q headb headb count 1 count 1 whilewhile q null q null count count If q If q NULL NULL returnreturn Error Error p next q next p next q next q next heada q next heada returnreturn ok ok 4 4 在递增有序的顺序表中插入一个元素 在递增有序的顺序表中插入一个元素 x x 首先应查找待插入元素的位置 因顺序表元素 首先应查找待插入元素的位置 因顺序表元素 递增有序 采用折半查找法比顺序查找效率高 查到插入位置后 从此位置直到线性表递增有序 采用折半查找法比顺序查找效率高 查到插入位置后 从此位置直到线性表 尾依次向后移动一个元素位置 之后将元素尾依次向后移动一个元素位置 之后将元素 X X 插入即可 查找算法的时间复杂度为插入即可 查找算法的时间复杂度为 O O loglog n n 而插入时的移动操作的时间复杂度为 而插入时的移动操作的时间复杂度为 O O n n 若用顺序查找 则查找的时间 若用顺序查找 则查找的时间 复杂度为复杂度为 O O n n VoidVoid Insert ElemTypeInsert ElemType A intA int size size ElemTypeElemType x x low low 1 1 high high num num while low high while lowx high mid 1 if A mid x high mid 1 elseelse low mid 1 low mid 1 for i num for i num i low i low i i A i 1 A i A i 1 A i A i 1 x A i 1 x 5 5 StructStruct pnodepnode intint coef coef 系数系数 intint exp exp 指数指数 StructStruct pnodepnode Link Link StructStruct pnodepnode padd Struct padd Struct pnodepnode heada heada StructStruct pnodepnode headb headb StructStruct pnodepnode headc headc p p q q r r s s intint x x p headap heada q headb q headb headc headc StructStruct pnodepnode malloc sizeof malloc sizeof Struct Struct pnodepnode r headc r headc R R 始终指向新链表中的最后一个节点始终指向新链表中的最后一个节点 whilewhile p NULL p NULL q coef if x 0 if x 0 s s StructStruct pnodepnode malloc sizeof malloc sizeof Struct Struct pnodepnode s coef x s coef x s exp p exp s exp p exp r Link s r s r Link s r s p p Link p p Link q q Link q q Link p p Link p p Link q q Link q q Link elseelse if p exp if p exp q exp q exp s s StructStruct pnodepnode malloc sizeof malloc sizeof Struct Struct pnodepnode s coef s coef q coef q coef s exp p exp s exp p exp r Link s r s r Link s r s q q Link q q Link elseelse s s StructStruct pnodepnode malloc sizeof malloc sizeof Struct Struct pnodepnode s coef s coef q coef q coef s exp p exp s exp p exp r Link s r s r Link s r s p p Link p p Link if p NULL if p NULL q p q p while q NULL while q NULL s s StructStruct pnodepnode malloc sizeof malloc sizeof Struct Struct pnodepnode r Link s r Link s r s r s q q Link q q Link r Link NULL r Link NULL s headc s headc headc headc headc Link headc Link free s free s return headc return headc 第三章 栈和队列第三章 栈和队列 一 单项选择题一 单项选择题 1 C 2 B 3 D 4 C 5 D 6 A 7 B 8 C 9 B 10 D 11 C 12 D 13 B 14 C 15 A 16 A 17 A 18 C 19 A 20 D 二 填空题二 填空题 1 栈 栈 2 队尾 队尾 队首 队首 栈顶 栈顶 栈顶栈顶 3 删除运算的不同 删除运算的不同 4 先移动栈顶指针 后存入元素 先移动栈顶指针 后存入元素 5 先取出元素 后移动栈顶指针 先取出元素 后移动栈顶指针 6 不可能的 不可能的 7 可能的 可能的 8 O 1 9 S NULL 10 先取出元素 后移动队尾指针 先取出元素 后移动队尾指针 11 先存放元素 后移动队尾指针 先存放元素 后移动队尾指针 12 MAX 1 13 ST front front ST rear rear 三 简答题三 简答题 1 解 解 Initstack st 空栈空栈 Push st A 栈内容栈内容 A Push st B 栈内容栈内容 A B Push st C 栈内容栈内容 A B C Pop st x 栈内容栈内容 A B Pop st x 栈内容栈内容 A Push st D 栈内容栈内容 A D Push st E 栈内容栈内容 A D E Push st F 栈内容栈内容 A D E F Pop st x 栈内容栈内容 A D E Push st G 栈内容栈内容 A D E G Pop st x 栈内容栈内容 A D E Pop st x 栈内容栈内容 A D Pop st x 栈内容栈内容 A 2 解 本题利用栈的 解 本题利用栈的 后进先出后进先出 的特点 有如下几点情况 的特点 有如下几点情况 A 进 进 A 出 出 B 进 进 B 出 出 C 进 进 C 出 产生输出序列出 产生输出序列 ABC A 进 进 A 出 出 B 进 进 C 进 进 C 出 出 B 出 产生输出序列出 产生输出序列 ACB A 进 进 B 进 进 B 出 出 A 出 出 C 进 进 C 出 产生输出序列出 产生输出序列 BAC A 进 进 B 进 进 B 出 出 C 进 进 C 出 出 A 出 产生输出序列出 产生输出序列 BCA A 进 进 B 进 进 C 进 进 C 出 出 B 出 出 A 出 产生输出序列出 产生输出序列 CBA 不可能的输出序列不可能的输出序列 CAB 3 解显示队列中的内容如下 解显示队列中的内容如下 InitQueue Q 空队列空队列 Add Q Q A 队中内容 队中内容 A Add Q Q B 队中内容 队中内容 A B Add Q Q C 队中内容 队中内容 A B C Del Q 队中内容 队中内容 B C Del Q 队中内容 队中内容 C Add Q Q D 队中内容 队中内容 C D Add Q Q E 队中内容 队中内容 C D E Add Q Q F 队中内容 队中内容 C D E F Del Q 队中内容 队中内容 D E F Add Q Q G 队中内容 队中内容 D E F G Del Q 队中内容 队中内容 E F G Del Q 队中内容 队中内容 F G Del Q 队中内容 队中内容 G 4 当元素 当元素 d e b g h 入队后 入队后 rear 5 front 0 元素元素 d e 出队 出队 rear 5 front 2 元素元素 i j k l m 入队后 入队后 rear 10 front 2 元素元素 b 出队 出队 rear 10 front 3 此时若再此时若再 让让 n o p 入队 由于入队 由于 rear 10 故队列溢出 入队和出队的变化函数如下图所示 故队列溢出 入队和出队的变化函数如下图所示 a 初始状态 b 元素 d e b g h 入队 c 元素 d e 出队 d 元素 i j k l m 入队 e 元素 b 出队 5 解当元素 解当元素 d e b g h 入队后 入队后 rear 5 front 0 元素元素 d e 出队 出队 rear 5 front 2 元素元素 i j k l m 入队后 入队后 rear 10 front 2 元素元素 b 出队 出队 rear 10 front 3 此时若再此时若再 让让 n o p 入队 入队 rear 2 front 3 队列不会溢出 队列不会溢出 a 初始状态 b 元素 d e b g h 入队 c 元素 d e 出队 d 元素 i j k l m 入队 e 元素 b 出队 f 元素 n o p 入队 四 算法分析四 算法分析 1 解假设采用顺序栈结构 先退栈 解假设采用顺序栈结构 先退栈 ST 中所有元素 利用一个临时栈中所有元素 利用一个临时栈 tmpst 存放从存放从 ST 栈栈 中退出的元素 最后的一个元素即为所求 然后将临时栈中退出的元素 最后的一个元素即为所求 然后将临时栈 tmpst 中的元素逐一出栈并进栈中的元素逐一出栈并进栈 到到 ST 中 这样恢复中 这样恢复 ST 栈中原来的元素 算法如下 栈中原来的元素 算法如下 ElemType bottom stack ST ElemType X Y Stack tmpst InitStack tmpst 初始化临时栈初始化临时栈 while Stack Empty ST 临时栈临时栈 tmpst 中包含中包含 ST 栈中逆转元素栈中逆转元素 pop ST x push tmpst x While Stack Empty tmpst 恢复恢复 ST 栈中原来的内容栈中原来的内容 pop tmpst y push ST y return x 2 解 假设栈不带头结点 求栈中元素个数算法如下 解 假设栈不带头结点 求栈中元素个数算法如下 Int count SNode top SNode p top int n 0 while NULL n p p next next return n 3 解 假设是循环顺序队列 建立一个临时栈 解 假设是循环顺序队列 建立一个临时栈 tmpst 将指定队列 将指定队列 Q 中的所有元素出中的所有元素出 队并入栈到队并入栈到 tmpst 栈中 这样栈中 这样Q 中队列为空 再将栈中队列为空 再将栈 tmpst 中的所有元素出栈并入队中的所有元素出栈并入队 Q 中 这样中 这样 Q 队列中的内容发生了反转 算法如下 队列中的内容发生了反转 算法如下 Viod reverse Queue Stack tmpst InitStack tmpst 初始化栈初始化栈 tmpst while QueueEmpty Q DeQueue Q x push tmpst x while Queue Empty tmpst pop tmpst x EnQueue Q x 4 解 假设是循环顺序队列 没有取队尾元素的基本运算 建立一个临时队列 解 假设是循环顺序队列 没有取队尾元素的基本运算 建立一个临时队列 tmpqu 将将 指定队列指定队列 qu 的所有元素出队并如队到的所有元素出队并如队到 tmpqu 这样这样 qu 队列为空 再将队列队列为空 再将队列 tmpqu 中的所中的所 有元素出队并入队到有元素出队并入队到 qu 队中 最后的一个元素即为所求 算法如下 队中 最后的一个元素即为所求 算法如下 ElemType last Queue qu ElemType x queue tmpqu initQueue tmpqu while QueueEmpty qu DeQueue qu x EnQueue tmpqu x while QueueEmpty tmpqu DeQueue tmpqu x EnQueue qu x return x 5 解 该共享栈的结构如下图所示 解 该共享栈的结构如下图所示 两栈的最多元素个数为两栈的最多元素个数为 m top1 是栈是栈 1 的栈指针 的栈指针 top2 是栈是栈 2 的栈指针 当的栈指针 当 top2 top1 1 时出现上溢出 当时出现上溢出 当 top1 0 时栈时栈 1 出现下溢出 当出现下溢出 当 top2 m 1 时栈时栈 2 出现下溢出 算法如下 出现下溢出 算法如下 top1 top2 和和 m 均为已赋初值的均为已赋初值的 int 全局变量全局变量 Int push ElemType x int i if top1 top2 1 上溢出上溢出 return 0 返回出错信息返回出错信息 else if i 1 对第一个栈进行进栈操作对第一个栈进行进栈操作 top1 C top1 x else 对第二个栈进行进栈操作对第二个栈进行进栈操作 top2 C top2 x return 1 返回成功信息返回成功信息 int pop int i ElemType 返回出错信息返回出错信息 else x c top1 top1 else 对第二个栈进行出栈操作对第二个栈进行出栈操作 if top2 m 1 栈栈 2 下溢出下溢出 return 0 返回出错信息返回出错信息 else x c top2 top2 return 1 返回成功信息返回成功信息 Void set null int i if i 1 top1 0 else top2 m 1 6 解 定义队列类型如下 解 定义队列类型如下 Typedef struct SNode rear QType 2 1 队列插入一个结点的操作是在队尾进行的 所以应在该循环链队的尾部插入一个结点 队列插入一个结点的操作是在队尾进行的 所以应在该循环链队的尾部插入一个结点 算法如下 算法如下 EnQueue QType 2 s s SNodeSNode malloc sizeof malloc sizeof SNode SNode 建立一个新结点建立一个新结点 s data x s data x if qu rearif qu rear NULL NULL 循环队列为空 则建立一个结点的循环队列循环队列为空 则建立一个结点的循环队列 qu rear s qu rear s qu rear next s qu rear next s elseelse 循环队列不为空 则将循环队列不为空 则将 S S 插到后面插到后面 s next s next qu rear next qu rear next qu rear next s qu rear next s qu rear nextqu rear next rear s rear s qu rearqu rear 始终指向最后一个结点始终指向最后一个结点 2 2 队列的删除结点是在队头进行的 所以删除该循环链表的第一个结点 算法如下 队列的删除结点是在队头进行的 所以删除该循环链表的第一个结点 算法如下 Int DeQueue QType 2 ifif qu rear qu rear NULL NULL 队列下溢出队列下溢出 returnreturn 0 0 返回出错信息返回出错信息 elseelse p qu rear next p qu rear next p p 指向队头结点指向队头结点 x p data x p data if p if p qu rear qu rear 队列只有一个结点 则直接删除该结点队列只有一个结点 则直接删除该结点 qu rearqu rear NULL NULL elseelse qu rear nextqu rear next p next p next 否则删除第一个结点否则删除第一个结点 free p free p 释放队头结点释放队头结点 returnreturn 1 1 返回成功信息返回成功信息 7 7 解 求该链队中结点个数实际上是计算以 解 求该链队中结点个数实际上是计算以 top top frontfront 为头指针的单链表中结点个数 为头指针的单链表中结点个数 算法如下 算法如下 IntInt QucountQucount LQueue LQueue top top SNodeSNode p p top front top front intint n 0 n 0 whilewhile p p NULL NULL n n p p next p p next returnreturn n n 8 8 解 写递归函数要清楚结束递归的条件是什么 在此处已知 解 写递归函数要清楚结束递归的条件是什么 在此处已知 n n 为大于等于零的正整数 为大于等于零的正整数 递归算法如下 递归算法如下 IntInt f f int int n n ifif n 0 n 0 returnreturn 0 0 ifif n n 0 0 returnreturn 1 1 elseelse returnreturn n fn f n 2 n 2 9 9 解 解 voidvoid tranftranf int int a a int int r r a a 是十进制 是十进制 r r 是任意进制数是任意进制数 SeqStrackSeqStrack s s intint m m intint x x InitStrackInitStrack s top s top 0 0 whilewhile a 0 a 0 m m a a r r 进行求余运算进行求余运算 pushpush m 把取得的的余数进栈把取得的的余数进栈 a aa a r r 进行取整运算进行取整运算 WhileWhile s top s top 0 0 当栈不空 依次出栈当栈不空 依次出栈 pop printfprintf d d x x 第四章第四章串串 一 单项选择题一 单项选择题 1 C 2 D 3 D 4 B 5 C 6 28 7 8 B 9 B 二 填空题二 填空题 1 顺序存储方式和链式存储方式 顺序存储方式和链式存储方式 2 两个串的长度相等且对应位置的字符相 两个串的长度相等且对应位置的字符相 3 由一个或多个空格字符组成的串 由一个或多个空格字符组成的串 其包含的空格个数其包含的空格个数 4 不相同的 不相同的 5 19 6 7 01122312 三 算法分析三 算法分析 1 2 void strcopy Stringtype s Stringtype t 串复制串复制 int i for i 0 i0 s j stk i 将第偶数个字符逆序填入原字符数组将第偶数个字符逆序填入原字符数组 第五章 数组和广义表第五章 数组和广义表 一 单项选择题一 单项选择题 1 B 2 1 L 2 J 3 C 4 I 5 C 3 B 4 B 5 A 6 H C E A F 7 B 8 B 9 B 10 B 11 B 12 A 13 B 14 B 15 D 16 C B 17 A 二 判断题二 判断题 1 F 2 T 3 T 4 F 5 F 6 F 7 T 8 F 9 F 10 F 三 填空题三 填空题 1 顺序 顺序 2 9572 1228 3 9174 8788 4 其余元素组成的表 其余元素组成的表 5 1 原子是结构上不可再分的 可以是一个数或一个结构 而表带结构本质上就是广义 原子是结构上不可再分的 可以是一个数或一个结构 而表带结构本质上就是广义 表 因作为广义表的元素故称为子表 表 因作为广义表的元素故称为子表 2 大写字母 大写字母 3 小写字母 小写字母 4 表中元素个数 表中元素个数 5 表展开后所含括号的层数 表展开后所含括号的层数 6 深度 深度 7 1 2 3 2 4 2 8 head tail head tail H 9 b 10 x y z 四 简答题四 简答题 1 答 元素 答 元素 A 4 2 3 的存储首地址为的存储首地址为 958 三维数组以行为主序存储 其地址公式 三维数组以行为主序存储 其地址公式 loc Aijk loc Aclc2c3 i C1 V2V3 j C2 V3 k C3 其中其中 Ci di 是各维的下界和上界 是各维的下界和上界 vi di ci 1 是元素个数 是元素个数 L 是一个元素所占的存储单元数 是一个元素所占的存储单元数 2 答 答 b 对角矩阵的对角矩阵的 b 条对角线在主对角线上方和下方各有条对角线在主对角线上方和下方各有 b 2 条对角线 从第条对角线 从第 1 行至第行至第 a a 行 每行上的元素依次是行 每行上的元素依次是 a 1a 1 a 2a 2 b 2 b 1 最后的最后的 a a 行上的元素个数是行上的元素个数是 b 1 b 2 a 1a 1 中间的 中间的 n 2a a 行 每行的元素个数是 行 每行的元素个数是 b 故 故 b 条对角线上的个数为 条对角线上的个数为 n 2a a b a a a a b 存放在一维数组存放在一维数组 V 1 nb a a b a a 中中 其下标其下标 k 与元素在二维数组中的下标与元素在二维数组中的下标 i 和和 j 的关系为的关系为 k 时当11 2 2 1 aij aii k a 2i a j 当当 a 1 i n a 1i n a 1 时时 k a 2i a 当当 n a 1 i ni n 时时j aniani 2 1 3 答 答 1784 公式 公式 loc Aijkl 100 基地址基地址 Ci C1 V2V3V4 j C2 V3V4 k C3 V4 1 C4 4 4 答 答 1210 108L 公式 公式 loc A 1 3 2 1210 k C3 V2V1 j C2 V1 i C1 L 设每个元设每个元 素占素占 L 个存储单元个存储单元 5 答 数组占的存储字节数 答 数组占的存储字节数 10 9 7 4 2520 A 5 0 7 的存储地址的存储地址 100 4 9 7 2 7 5 4 1184 6 答 广义表的第一种存储结构的理论基础是 非空广义表可唯一分解成表头和表尾两部 答 广义表的第一种存储结构的理论基础是 非空广义表可唯一分解成表头和表尾两部 分 而由表头和表尾可唯一构成一个广义表 在这种存储结构中 原子和表采用不同的结分 而由表头和表尾可唯一构成一个广义表 在这种存储结构中 原子和表采用不同的结 点结构 原子结点两个域 子表结点三个域 对非空广义表不断进行表头和表尾的分解 点结构 原子结点两个域 子表结点三个域 对非空广义表不断进行表头和表尾的分解 表头可以是原子也可以是子表 而表尾一定是表 下面是本题的第一种存储结构图 表头可以是原子也可以是子表 而表尾一定是表 下面是本题的第一种存储结构图 111 1 1 0 A AA 1 1 1 1 0 B 1 1 0 F0 D 广义表的第二种存储结构的理论基础是 非空广义表最高层元素间具有逻辑关系 第广义表的第二种存储结构的理论基础是 非空广义表最高层元素间具有逻辑关系 第 一个元素无前驱有后继 最后一个元素无后继有前驱 其余元素有唯一前驱和唯一后继 一个元素无前驱有后继 最后一个元素无后继有前驱 其余元素有唯一前驱和唯一后继 在这种存储结构中 原子和表均采用三个域的结点结构 结点中都有一个指针指向后继结在这种存储结构中 原子和表均采用三个域的结点结构 结点中都有一个指针指向后继结 点 在画这种存储时 从左往右一个元素一个元素地画 直至最后一个元素 点 在画这种存储时 从左往右一个元素一个元素地画 直至最后一个元素 0 E 0 C 1 1 0 A 1 1 0 B 1 0 E 0 F 0 C 0 D 五 算法分析五 算法分析 1 本题要求从 本题要求从 n 个数中 取出所有个数中 取出所有 k 个数的所有组合 设数已存于数组个数的所有组合 设数已存于数组 A 1 A 中中 为使为使 结果唯一结果唯一 可以分别求出包括可以分别求出包括 A n 和不包括和不包括 A n 的所有组合的所有组合 即包括即包括 A n 时时 求出从求出从 A 1 n 1 中中 取出取出 k 1 个元素的所有组合个元素的所有组合 不包括不包括 A n 时时 求出从求出从 A 1 n 1 中取出中取出 k 个元素的所有组合个元素的所有组合 Const n 10 k 3 Type Arr Array 1 n of integer VAR A B ARR PROC outresult 输出结果输出结果 FOR j 1 TO k DO write B j write n ENDP PROC nkcombination i j k integer IF k 0 THEN outresult ELSE IF j k 0 THEN B j A i j j 1 nkcombination i 1 k 1 j nkcombination i 1 k j 1 ENDP 2 void Translation float matrix int n int i j k 1 f loat sum min float p pi pk for i 0 i n i sum 0 0 pk matrix i n for j 0 j n j sum pk pk p i sum for i for i 0 i n 1 i min p i k I for j i 1 j n j if p j min k j min p j if i k pk matrix n k pi matrix n I for j 0 j n j sum pk j pk j pi j pi j sum Sum p i p i p k p k sum if for i free p TranSlation 3 1 int BiForm int n k if n 0 k n printf 参数错误参数错误 n exit 0 if k 0 k n return 1 else return BiForm n 1 k BiForm n 1 k 1 2 C 6 4 的递归树的递归树 C 6 4 C 5 4 C 5 3 C 4 4 C 4 3 C 4 3 C 4 2 C 3 3 C 3 2 C 3 3 C 3 2 C 3 2 C 3 1 C 2 2 C 2 1 C 2 2 C 2 1 C 2 2 C 2 1 C 2 1 C 2 0 C 1 1 C 1 0 C 1 1 C 1 0 C 1 1 C 1 0 C 1 1 C 1 0 3 计算计算 C n k 0 k n0 k n 的非递归算法的非递归算法 int cnk int n int k int i long x 1 y 1 for i 1 i k i x i for i n k 1 idep2 return dep 1 else return dep2 1 2 解答 使用一个栈 stack 首先将根节点入栈 开始循环 从栈中退出当前节点 p 先 访问它 然后将其右节点入栈 再将其左节点入栈 如此直到栈空为止 算法如下 void porder BTree b BTree stack Maxsize p int top 1 if b NULL top stack top b while top 1 P stack top top cout data right NULL top stack top p right if p left NULL top stack top p left 3 根据后序遍历二叉树的递归定义 转换成非递归函数时采用一个栈保存返回的节点 先 扫描根节点的所有左节点并入栈 出栈一个节点 然后扫描该节点的右节点并入栈 再扫 描该右节点的所有左节点并入栈 当一个节点的左右子树均访问后再访问该节点 如此这 样 直到栈空为止 其中的难点是如何判断一个节点 t 的右节点已访问过 为此用 p 保存 刚访问过的节点 初值为 NULL 若 t right p 成立 在后序遍历中 t 的右节点一定刚 好在 t 之前访问 说明 t 的左右子树均已访问 现在应访问 t 算法如下 void psorder BTree t BTree stack Maxsize BTree p int flag top 1 do while t top stack top t t t left p NULL flag 1 while top 1 if t right p cout data right flag 0 while top 1 4 解析 本题采用递归算法 设 h 指定 p 所指结点的高度 其初值为 1 找到指定的结点 返回其层次 否则返回 1 作为一个中间变量在计算其搜索层次时使用 其初值为 1 算 法如下 void level Btree p int Int f r q q f 0 q r 0 if b NULL cout data q vec q r b q r q r 1 while q fleft NULL cout left data left q r q r 1 if b right NULL cout right data right q r q r 1 cout left b2 left Like2 like b1 right b2 right return like1 7 解析 算法 1 若二叉树采用链式存储结构 根据完全二叉树的定义 对完全二叉树 按照从上到下 从左到右的次序遍历应该满足 某节点没有左孩子 则一定无右孩子 若某节点缺左或右孩子 则其所有后继一定无孩子 若不满足上述任何一条 均不为完全二叉树 对应的算法如下 define Max 100 int fullbtree1 BTree b BTree queue Max p int first 0 rear 0 bj 1 cm 1 if b NULL rear queue rear b while first rear first p queue first if p left NULL bj 0 if p right NULL cm 0 else c