目录 1998年南昌大学信息工程学院数据结构考研真题 1999年南昌大学信息工程学院数据结构考研真题（部分） 2000年南昌大学信息工程学院数据结构考研真题 2001年南昌大学信息工程学院数据结构考研真题及参考答案 2002年南昌大学信息工程学院数据结构考研真题 2003年南昌大学信息工程学院数据结构考研真题 1998年南昌大学信息工程学院数 据结构考研真题 一、简答题（共12分） 1度数为2的树和二叉树的差别？（3分） 2散列存储影响碰撞的因素有哪些？（3分） 3二路归并排序的时空复杂度怎样（比较次数，移动次数，空间 存储）？（3分） 4无根的有向图是否一定存在环？（3分） 二、对于关键码序列：12，26，19，4，7，8，1。（共18分） 1写出快速排序第一趟变换的结果序列；（6分） 2它是否是堆（小根堆）？不是的话，请按照筛选法把它调整为 堆（小根堆）；（6分） 3把它依次插入一颗初始为空的AVL树，分别写出插入19，7，1 后的二叉树。（6分） 三、Josephus问题描述如下（共24分） 设有n个人围坐一个圆桌周围，现从第S人开始报数，数到第m的人 出列，然后从出列的下一个重新开始报数，数列的第m个人又出 列，如此重复，直到所有的人全部出列为止。 1按n个人围坐的顺序建立一个循环单链表，请写出算法1（要求 定义数据结构）；（10分） 2对于给定的S、m，写出算法2，在1的基础上求出列顺序；（10 分） 3分析的算法额的时空复杂度。（4分） 四、已知一颗用标准形式存储的二叉树T，其数据结构定义如下： （共22分） 1写出T进行中序穿线的算法。（12分） 2设P为T的某已知结点，写出栈P后序下前驱的算法。（10 分） 五、已知下列有向图G：（共24分） 1写出此图的表达为边的邻接表表示，并定义邻接表的数据结 构；（6分） 2根据你画的邻接表，写出熊V6开始深度优先遍历的序列；（4 分） 3设计算法，判断是否存在从V4开始的环。（14分） 图G 附：1998年真题原版图片 1999年南昌大学信息工程学院数 据结构考研真题（部分） 二、（15分）若x和y是两个用单链表存储的串，写一个算法找出x 中第一个不在y中出现的字符并输出。 三、（15分）给定整型数组A1.n，写出一个把数组A建成堆的算 法，并分析你的算法的时间复杂度。 四、（15分）写一个在对称穿线树中找指定结点P的前序下后继的 的子算法（函数），利用此子算法写出前序周游对称穿线树的完整算 法。 五、（15分）有向图用相邻矩阵表示，写一个算法找图的拓扑排 序，要求附加空间不大于nc（c是一个常数），时间复杂度不大于 O（n2）。 附：1999年真题原版图片（部分） 2000年南昌大学信息工程学院数 据结构考研真题 报考专业：计算机应用 考试科目：数据结构（A） 一、选择题（每题选择一个答案填入下列横线处，每题2分，共10 分） 1若线性表最常用的操作是存取第i个元素及其前驱的值，则采用 _存储方式节省时间。 A单链表 B双链表 C单循环链表 D顺序表 2下列排序算法中，时间复杂度不受数据初始状态影响，但为 O（nlogn）的是_。 A堆排序 B冒泡排序 C快速排序 D希尔排序 3设循环队列中的数组的下标范围是1，n，其头尾指针分别 是f和r，则队列的元素个数为_。 Arf Brf1 C（rf） mod n1 D（rfn） mod n 4已知某二叉树的后序序列为dabec，中序（即对称序）序列为 debac，则它的前序序列为_。 Adecab Bdeabc Ccedab Dcedba 5用10个权执行哈夫曼算法，得到的哈夫曼树的外部路径的长度 是_。 A此10个权之和 B所有内部结点的值之和 C根结点的值 D以上三者均不是 二、解答下列问题（每题6分，共36分） 1有一组关键码（38，19，65，13，97，49，41，95，1，73）， 采用冒泡方法由小到大排序，请写出每趟的结果。 2设散列函数为H（k）k mode 7，散列表的地址空间为1，2， ，6，0，开始是散列表为空，用线性探测法解决冲突，请画出依次插 入键值23，14，9，6，30，12，18后的散列表。 3试证明一颗非空的满二叉树（即所有分支结点的度数为2）的结 点数为2n1，n为正整数。 4由一颗空的平衡二叉树开始，将关键码10，20，40，80，50依 次插入，画出每插入一个关键码后得到的平衡二叉树。 5二叉树如下图所示。 （1）画出该二叉树的中序线索树（线索由虚线表示）； （2）画出该二叉树对应的森林。 6边权图如下图所示。用Dijksta算法求结点2到其它各结点的最短 路径，写出执行算法中数组dist的会变化状况。 三、算法设计题（共54分） 1已知单循环键链表L中至少有二个结点，每个结点的字段为data 和next，其中data为整数类型。设计算法判断是否L中每个结点的值都小 于其后续结点的值之和。若是，则返回true，否则，返回false。（12 分） 2设有n个人围成一个圈，从第S个人开始报数，数到m的人出 列，然后从这个出列者的下一个人重新开始报数，数到m的人又出列， ，如此重复，直到m个人全部出列。设计一个算法，对给定的n， S，m，求出列的顺序，假定n个人分别用1，n编号，输出出列的顺 序。（14分） 3设有字符数组t1.max（设max100） 试用一种高级语言编写一个函数，把t1.n转换成用标准的二叉链 表示的完全二叉树。例如：当n6时，转换成的完全二叉树是： 其返回的函数值是完全二叉树的根结点的指针。（14分） 编写前先用简洁的语言说明你所用的方法。 4设无向图G有10个结点，采用邻接表存储。 （1）写出该图的数据结构类型说明；（5分） （2）写一个算法，判定该图是否连通。（9分） 附：2000年真题原版图片 2001年南昌大学信息工程学院数 据结构考研真题及参考答案 附：2001年真题原版图片 2002年南昌大学信息工程学院数 据结构考研真题 报考专业：计算机应用 考试科目：数据结构（A） 一、简答题（指出下列各题中2个数据结构或存储结构的主要相同 与不同之处，每题4分，共12分）。 1栈、队列 2树、二叉树 3静态链表、动态链表 二、选择题（每题选择一个答案，每题2分，共10分） 1当待排序元素较多时，（）排序方法平均的键值比较次数 最少。 A直接选择 B直接插入 C二分位插入 D冒泡 2二叉树中序穿线，对找指定结点的（）没有帮助。 A前序前驱 B前序后继 C中序前驱 D中序后继 3在有序表（3，5，6，9，11，12，16，20，24，36），上进行 二分法查找，被依次比较的元素为（）。 A11，20，12，16 B11，20，16 C12，20，16 D12，16 4数组A0.4，1.5的第一个元素存储地址为2050，每个元素占4 个存储单元，则元素A3，4的存储地址为（）。 A2138 B2126 C2122 D2134 5假设循环队列存储在数组a0.n中，f和r分别为队头、队尾指 针，当（）时，该队列溢出。 Arn Br1f C（r1） mod nf D（r1） mod （n1）f 三、填空题（在下划线处填上适当的内容，每题2分，共10分） 1设r指向带有头结点的循环单链表的尾结点，结点的指针域为 next，则在表尾插入新结点s的语句序列如下： _; r*.next:=s; r:=s; 2假定空二叉树的高度为0，则具有256个结点的完全二叉树的高 度是_。 3对_图，拓扑排序算法可以输出其顶点集合的拓扑序列。 4一颗二叉树的前序序列为ABDEFGC，中序（对称序）序列为 DBFEGAC，则后序序列是_。 5设二叉树的结点有两个指针域：lchild，rchild，分别指向它的 左、右孩，根结点指针为t，则下列语句可以把指针P定位到改二叉树的 中序第一个结点。 P:=t;_; 四、画图并回答问题。（共20分） 1设有一颗平衡二叉排序树的根结点为A，A的左孩结点为B，B 的右孩为也叶子结点C，A、B的平衡因子分别是1、0。 （1）请画出次平衡二叉树，其他结点请自己命名； （2）现插入一个新结点X作结点C的左孩，画出重组后的平衡二叉 排序树。（4分） 2对输入序列（13，41，15，44，06，68，12，25，38，64， 19，49）（共12个）用散列方法存储，散列函数为H（k）k mode 13，负载因子取0.8，用线性探测法解决冲突。请写出散列表的状况， 并计算出等概率下查找成功时的平均查找长度。（6分） 3对初始序列（13（1），15，44，06，68，12，25，13（2）用 算法创建一个（小根）堆。 （1）请画出此堆； （2）试问初始序列为什么情况时，建堆算法效率最高？（4分） 4下图是某个图的邻接表，利用该表从结点C开始执行深度优先 和广度优先遍历算法。 （1）写出深度优先和广度优先遍历序列； （2）画出广度优先得到的生成树。（6分） 五、算法填空与设计题（每题12分，共48分） 1算法填空。下列C语言函数huffman对给定的数组w0.N1 （KN）构造哈夫曼树，并返回根结点在数组t中的下标。 2有二个带有头结点的单链表，表头指针分别为a，b，链表的结 点有二个域：key，next，（next指向下一个结点），链表的结点已按 key递增序排列，写一个PASCAL过程，把b表合并到a表中，使合并后 结点仍递增有序，要求利用原有结点，不增加新的结点。 3设待排序的数组为Rl.r，写出快速排序算法。 4在实际应用汇总（如电子表格），有时把稀疏矩阵的非零元素 存储在二叉排序树上，以利查找，例如 假设二叉树的结点有5个域：llink，rlink（指向左、右孩），i，j， val（分别为非零元素的行号、列号和值）。结点的关键字序偶（i， j），二个序偶采用通常方法比较，即i值大的序偶也大，如i值相同则j值 大的序偶大。 设t是二叉排序树的根指针，试写一算法，在该树上插入一个由q指 向的结点q。 附：2002年真题原版图片 2003年南昌大学信息工程学院数 据结构考研真题 附：2003年真题原版图片