上海交通大学：《数据结构考研试题》数据结构与C语言程序设计试题

数据结构与G语言程序设计 是非题(2’×10) ()1、队列逻辑上是一个表头和表尾既能插入又能删除的线性表。 ()2、任何一个递归过程都可以转换成非递归过程。 ()3、与n个键值的集合k1,k2,…,kn}相对应的堆是唯一的 ()4、在索引顺序表上实现分块查找,在等概率查找情况下,其查找长度只 与表中元素个数有关,而与每块中元素个数无关。 ()5、所谓加权无向图G的最小生成树T就是将G中各结点间的最短路径作 为边所构造出来的G的子图。 ()6、在10万个随机排列的数据中,要选出5个最小的数,采用快速排序比 采用Shel1排序、堆排序及各种直接排序法都快 ()7、B树查找算法的时间复杂性为0(n) ()8、哈希表查找无需进行关键字的比较。 ()9、在执行某个排序过程中,出现排序码朝着最终位置相反方向移动,则 该算法是不稳定的。 )10、任何有向图的顶点都可以按拓扑序排序 填空题(2’×6) 1.假设用于通信的电文由8个字母组成,其频率分别为0.07,0.19,0.02,0.06, 0.32,0.03,0.21,0.10,为这8个字母设计哈夫曼编码,其中编码长度最大 的字母的编码是位。 2.已知二叉树按中序遍历所得到的结点序列为 DCBGEAHFIJK,按后序遍历所得 到的结点序列为 DCEGBFHKJIA,按先序遍历所得到的结点序列为 3.设哈希表长度为11,散列函数H(k)-kMoD11,若输入顺序为 (18,10,21,9,6,3,16,25,7),处理冲突方法为线性探测再散列,请构造哈 希表 给出 求从 小到大进行排序,试结出快速排序(近第一个记录为枢轴)第一题开序结 果_ 5.已知模式匹配的P算法中模式串口 adabbadada',其next函数的值 为 6.在置换选择排序中,假设工作区的容量为w,若不计输入、输出的时间,则 对n个记录的文件而言,生成所有初始归并段所需时间为 简答题(6,×5) 1.有n个不同的英文单词,它们的长度相等,均为皿,若n>50,m1

1 数据结构与 C 语言程序设计 一. 是非题（2’10） （ ）1、 队列逻辑上是一个表头和表尾既能插入又能删除的线性表。 （ ）2、 任何一个递归过程都可以转换成非递归过程。 （ ）3、 与 n 个键值的集合{k1,k2,…,kn}相对应的堆是唯一的。 （ ）4、 在索引顺序表上实现分块查找，在等概率查找情况下，其查找长度只 与表中元素个数有关，而与每块中元素个数无关。 （ ）5、 所谓加权无向图 G 的最小生成树 T 就是将 G 中各结点间的最短路径作 为边所构造出来的 G 的子图。 （ ）6、 在 10 万个随机排列的数据中，要选出 5 个最小的数，采用快速排序比 采用 Shell 排序、堆排序及各种直接排序法都快。 （ ）7、 B 树查找算法的时间复杂性为 O（n）。 （ ）8、 哈希表查找无需进行关键字的比较。 （ ）9、 在执行某个排序过程中，出现排序码朝着最终位置相反方向移动，则 该算法是不稳定的。 （ ）10、任何有向图的顶点都可以按拓扑序排序。 二. 填空题（2’6） 1． 假设用于通信的电文由 8 个字母组成，其频率分别为 0.07，0.19,0.02,0.06, 0.32,0.03,0.21,0.10, 为这 8 个字母设计哈夫曼编码，其中编码长度最大 的字母的编码是 位。 2．已知二叉树按中序遍历所得到的结点序列为 DCBGEAHFIJK， 按后序遍历所得 到的结点序列为 DCEGBFHKJIA， 按先序遍历所得到的结点序列为 。 3. 设 哈 希 表 长 度为 11 ， 散列 函 数 H(k)=k MOD 11, 若 输 入顺 序 为 （18,10,21,9,6,3,16,25,7）,处理冲突方法为线性探测再散列，请构造哈 希表 。 4．给出一组关键字 T=(20，4，34，5，16，33，18，29，2，40，7)，要求从 小到大进行排序，试给出快速排序(选第一个记录为枢轴)第一趟排序结 果 。 5．已知模式匹配的 KMP 算法中模式串 t=’adabbadada’，其 next 函数的值 为 。 6．在置换-选择排序中，假设工作区的容量为 w，若不计输入、输出的时间，则 对 n 个记录的文件而言，生成所有初始归并段所需时间为 。 三. 简答题（6’5） 1． 有 n 个不同的英文单词，它们的长度相等，均为 m，若 n>>50，m1

其中a>1,b>1,a∈N,b∈N 为简单起见,设n为b的整数幂 5.快速排序的时间复杂度是多少?试推导之。 四.程序设计题(38) 1.假设有两个集合A和B,均以元素值递增有序排列的带头结点的单链表作 为存储结构。请编写算法求C=A∩B,要求C按元素值递增有序排列,并要 求利用原表(即表A和表B)的结点空间存放表C。(12) 2.从键盘上输入一串正整数,以一1为输入结束的标志,试设计一个算法,生 成一棵二叉排序树(即依次把该序列中的结点插入二叉排序树)。(12) 3.试设计一个算法,在中序线索二叉树中求指定结点P在后序遍历序列中的 前驱结点。要求算法为非递归的,空间复杂度为O(1)。(14)

2 其中 a>1, b>1, aN, bN 为简单起见，设 n 为 b 的整数幂。 5．快速排序的时间复杂度是多少？试推导之。 四. 程序设计题（ 38’） 1．假设有两个集合 A 和 B，均以元素值递增有序排列的带头结点的单链表作 为存储结构。请编写算法求 C=AB，要求 C 按元素值递增有序排列，并要 求利用原表（即表 A 和表 B）的结点空间存放表 C。(12’) 2．从键盘上输入一串正整数，以—1 为输入结束的标志，试设计一个算法，生 成一棵二叉排序树（即依次把该序列中的结点插入二叉排序树）。(12’) 3．试设计一个算法，在中序线索二叉树中求指定结点 P 在后序遍历序列中的 前驱结点。要求算法为非递归的，空间复杂度为 O（1）。(14’)