上海交通大学数据结构与C语言程序设计习题及答案

《上海交通大学数据结构与C语言程序设计习题及答案》由会员分享，可在线阅读，更多相关《上海交通大学数据结构与C语言程序设计习题及答案（7页珍藏版）》请在金锄头文库上搜索。

1、专业课复习资料（最新版）专业课复习资料（最新版） 封封 面面 1 数据结构与 C 语言程序设计 数据结构与 C 语言程序设计 一一. 是非题（210） 是非题（210） （ ）1、 队列逻辑上是一个表头和表尾既能插入又能删除的线性表。 （ ）2、 任何一个递归过程都可以转换成非递归过程。 （ ）3、 与 n 个键值的集合k1,k2,kn相对应的堆是唯一的。 （ ）4、 在索引顺序表上实现分块查找，在等概率查找情况下，其查找长度只 与表中元素个数有关，而与每块中元素个数无关。 （ ）5、 所谓加权无向图 G 的最小生成树 T 就是将 G 中各结点间的最短路径作 为边所构造出来的 G 的子图。 （

2、 ）6、 在 10 万个随机排列的数据中，要选出 5 个最小的数，采用快速排序 比采用 Shell 排序、堆排序及各种直接排序法都快。 （ ）7、 B 树查找算法的时间复杂性为 O（n） 。 （ ）8、 哈希表查找无需进行关键字的比较。 （ ）9、 在执行某个排序过程中，出现排序码朝着最终位置相反方向移动，则 该算法是不稳定的。 （ ）10、任何有向图的顶点都可以按拓扑序排序。 （ ）1、 队列逻辑上是一个表头和表尾既能插入又能删除的线性表。 （ ）2、 任何一个递归过程都可以转换成非递归过程。 （ ）3、 与 n 个键值的集合k1,k2,kn相对应的堆是唯一的。 （ ）4、 在索引顺序表上实

3、现分块查找，在等概率查找情况下，其查找长度只 与表中元素个数有关，而与每块中元素个数无关。 （ ）5、 所谓加权无向图 G 的最小生成树 T 就是将 G 中各结点间的最短路径作 为边所构造出来的 G 的子图。 （ ）6、 在 10 万个随机排列的数据中，要选出 5 个最小的数，采用快速排序 比采用 Shell 排序、堆排序及各种直接排序法都快。 （ ）7、 B 树查找算法的时间复杂性为 O（n） 。 （ ）8、 哈希表查找无需进行关键字的比较。 （ ）9、 在执行某个排序过程中，出现排序码朝着最终位置相反方向移动，则 该算法是不稳定的。 （ ）10、任何有向图的顶点都可以按拓扑序排序。 二.

4、填空题（26） 二. 填空题（26） 11 假设用于通信的电文由8个字母组成， 其频率分别为0.07， 0.19,0.02,0.06, 0.32,0.03,0.21,0.10, 为这 8 个字母设计哈夫曼编码，其中编码长度最大 的字母的编码是 位。 假设用于通信的电文由8个字母组成， 其频率分别为0.07， 0.19,0.02,0.06, 0.32,0.03,0.21,0.10, 为这 8 个字母设计哈夫曼编码，其中编码长度最大 的字母的编码是 位。 2已知二叉树按中序遍历所得到的结点序列为 DCBGEAHFIJK， 按后序遍历所 得到的结点序列为 DCEGBFHKJIA， 按先序遍历所得到的

5、结点序列为 。 2已知二叉树按中序遍历所得到的结点序列为 DCBGEAHFIJK， 按后序遍历所 得到的结点序列为 DCEGBFHKJIA， 按先序遍历所得到的结点序列为 。 3. 设哈希表长度为 11 ， 散列函数 H(k)=k MOD 11, 若输入顺序为 （18,10,21,9,6,3,16,25,7）,处理冲突方法为线性探测再散列，请构造哈 希表 。 3. 设哈希表长度为 11 ， 散列函数 H(k)=k MOD 11, 若输入顺序为 （18,10,21,9,6,3,16,25,7）,处理冲突方法为线性探测再散列，请构造哈 希表 。 4给出一组关键字 T=(20，4，34，5，16，3

6、3，18，29，2，40，7)，要求从 小到大进行排序，试给出快速排序(选第一个记录为枢轴)第一趟排序结 果 。 4给出一组关键字 T=(20，4，34，5，16，33，18，29，2，40，7)，要求从 小到大进行排序，试给出快速排序(选第一个记录为枢轴)第一趟排序结 果 。 5已知模式匹配的 KMP 算法中模式串5已知模式匹配的 KMP 算法中模式串 t=adabbadada，其，其 next 函数的值 为 。 函数的值 为 。 6在置换-选择排序中，假设工作区的容量为 w，若不计输入、输出的时间， 则对 n 个记录的文件而言， 生成所有初始归并段所需时间为 。 6在置换-选择排序中，假设

7、工作区的容量为 w，若不计输入、输出的时间， 则对 n 个记录的文件而言， 生成所有初始归并段所需时间为 。 三. 简答题（65） 三. 简答题（65） 11 有 n 个不同的英文单词，它们的长度相等，均为 m，若 n50，m50，m1 aT(n/b)+c n1 2 其中 a1, b1, aN, bN 为简单起见，设 n 为 b 的整数幂。 5快速排序的时间复杂度是多少？试推导之。 其中 a1, b1, aN, bN 为简单起见，设 n 为 b 的整数幂。 5快速排序的时间复杂度是多少？试推导之。 四. 程序设计题（ 38） 四. 程序设计题（ 38） 1假设有两个集合假设有两个集合 A 和和

8、 B，均以元素值递增有序排列的带头结点的单链表作 为存储结构。请编写算法求 ，均以元素值递增有序排列的带头结点的单链表作 为存储结构。请编写算法求 C=A B，要求，要求 C 按元素值递增有序排列，并要 求利用原表（即表 按元素值递增有序排列，并要 求利用原表（即表 A 和表和表 B）的结点空间存放表）的结点空间存放表 C。(12) 。(12) 2 从键盘上输入一串正整数，以从键盘上输入一串正整数，以1 为输入结束的标志，试设计一个算法， 生成一棵二叉排序树（即依次把该序列中的结点插入二叉排序树） 。(12) 为输入结束的标志，试设计一个算法， 生成一棵二叉排序树（即依次把该序列中的结点插入二

9、叉排序树） 。(12) 3 试设计一个算法，在中序线索二叉树中求指定结点试设计一个算法，在中序线索二叉树中求指定结点 P 在后序遍历序列中的 前驱结点。要求算法为非递归的，空间复杂度为 在后序遍历序列中的 前驱结点。要求算法为非递归的，空间复杂度为 O（1） 。(14)） 。(14) 1 数据结构与 C 语言程序设计答案 数据结构与 C 语言程序设计答案 一一. 是非题（210） 是非题（210） （ ）1、 队列逻辑上是一个表头和表尾既能插入又能删除 的线性表。 （ ）1、 队列逻辑上是一个表头和表尾既能插入又能删除 的线性表。 （）2、任何一个递归过程都可以转换成非递归过程。 （ ）2、任

10、何一个递归过程都可以转换成非递归过程。 （ ） 3、 与 n 个键值的集合k1,k2,kn相对应的堆是唯 一的。 （ ） 3、 与 n 个键值的集合k1,k2,kn相对应的堆是唯 一的。 （ ）4、 在索引顺序表上实现分块查找，在等概率查找情 况下，其查找长度只与表中元素个数有关，而与 每块中元素个数无关。 （ ）4、 在索引顺序表上实现分块查找，在等概率查找情 况下，其查找长度只与表中元素个数有关，而与 每块中元素个数无关。 （ ）5、 所谓加权无向图 G 的最小生成树 T 就是将 G 中各 结点间的最短路径作为边所构造出来的 G 的子图。 （ ）5、 所谓加权无向图 G 的最小生成树 T

11、就是将 G 中各 结点间的最短路径作为边所构造出来的 G 的子图。 （ ）6、 在 10 万个随机排列的数据中，要选出 5 个最小的 数，采用快速排序比采用 Shell 排序、堆排序及 各种直接排序法都快。 （ ）6、 在 10 万个随机排列的数据中，要选出 5 个最小的 数，采用快速排序比采用 Shell 排序、堆排序及 各种直接排序法都快。 （ ）7、 B 树查找算法的时间复杂性为 O（n） 。 （ ）7、 B 树查找算法的时间复杂性为 O（n） 。 （ ）8、 哈希表查找无需进行关键字的比较。 （ ）8、 哈希表查找无需进行关键字的比较。 （ ）9、 在执行某个排序过程中，出现排序码朝着

12、最终位 置相反方向移动，则该算法是不稳定的。 （ ）9、 在执行某个排序过程中，出现排序码朝着最终位 置相反方向移动，则该算法是不稳定的。 （ ）10、任何有向图的顶点都可以按拓扑序排序。 ）10、任何有向图的顶点都可以按拓扑序排序。 二. 填空题（26） 二. 填空题（26） 11 假设用于通信的电文由 8 个字母组成，其频率分别为 0.07，0.19,0.02,0.06, 0.32,0.03,0.21,0.10, 为这 8 个字母设计哈夫曼编码，其中编码长度最大的字母的编 码是 5 位。 假设用于通信的电文由 8 个字母组成，其频率分别为 0.07，0.19,0.02,0.06, 0.32

13、,0.03,0.21,0.10, 为这 8 个字母设计哈夫曼编码，其中编码长度最大的字母的编 码是 5 位。 2 已 知 二 叉 树 按 中 序 遍 历 所 得 到 的 结 点 序 列 为 DCBGEAHFIJK， 按后序遍历所得到的结点序列为 DCEGBFHKJIA， 按先序遍历所得到的结点序列为 ABCDGEIHFJK 。 2 已 知 二 叉 树 按 中 序 遍 历 所 得 到 的 结 点 序 列 为 DCBGEAHFIJK， 按后序遍历所得到的结点序列为 DCEGBFHKJIA， 按先序遍历所得到的结点序列为 ABCDGEIHFJK 。 3. 设哈希表长度为 11， 哈希函数 H(k)=

14、k MOD 11, 若输 入顺序为（18,10,21,9,6,3,16,25,7）,处理冲突方法 为线性探测再散列，请构造哈希表 。 3. 设哈希表长度为 11， 哈希函数 H(k)=k MOD 11, 若输 入顺序为（18,10,21,9,6,3,16,25,7）,处理冲突方法 为线性探测再散列，请构造哈希表 。 0 1 2 3 4 5 6 7 8 9 10 21 3 25 16 6 18 7 9 10 4给出一组关键字 T=(20，4，34，5，16，33，18，29，2， 40，7)，要求从小到大进行排序，试给出快速排序(选 第 一 个 记 录 为 枢 轴 ) 第 一 趟 排 序 结 果

15、 7,4,2,5,16,18,20,29,33,40,34 。 0 1 2 3 4 5 6 7 8 9 10 21 3 25 16 6 18 7 9 10 4给出一组关键字 T=(20，4，34，5，16，33，18，29，2， 40，7)，要求从小到大进行排序，试给出快速排序(选 第 一 个 记 录 为 枢 轴 ) 第 一 趟 排 序 结 果 7,4,2,5,16,18,20,29,33,40,34 。 5已知模式匹配的 KMP 算法中模式串5已知模式匹配的 KMP 算法中模式串 t=adabbadada，其，其 next 函数的值为 0112112343 。 函数的值为 0112112343 。 6在置换-选择排序中，假设工作区的容量为 w，若不计输 入、输出的时间，则对 n 个记录的文件而言，生成所有 6在置换-选择排序中，假设工作区的容量为 w，若不计输 入、输出的时间，则对 n 个记录的文件而言，生成所有 2 初始归并段所需时间为 O(n log w) 。 初始归并段所需时间为 O(n log w) 。 三. 简答题（65） 三. 简答题（65） 11 有 n 个不同的英文单词，它们的长度相等，均为 m，若 n50，m50，m1 其中 a1, b1, aN, bN 为简单起见，设 n 为 b 的整数幂。 T(n)= aT(