数据结构精选考研试题

注：编写程序可选用任一种高语言，算法描述可采用类语言，必要时加上注释 一、 回答下列问题：20分 1、 算法的定义和性质 2、 为什么说数组与广义表是线性表的推广？ 3、 什么是结构化程序设计？ 4、 哈希方法的基本思想 5、 给出一不稳定排序方法名称与实例 二、 构造结果：24分 （1） 确定 x:=x+1语句在下面程序段中的频率，要求写出分析过程。 for i:=1 to n do for j:=1 to I do for k:=1 to j do x:=x+1 （2） 画出对长度为8的有序表进行折半查找的判定树，并求其在等概率时查找成功的平均 查找长度。 （3） 已知一棵二叉树如右图，给出对这棵二叉树进行前序、中序、后序遍历的结果序列 （4） 假设用于通讯的电文仅由 8 个字母组成，字母在电文中出现的频率分别为2，3，5， 7，11，4，13，15，试为这 8 个字母设计哈夫曼编码 （5） 在地址空间为 015 的散列区中，对以下关键字序列构 G 造哈希表，关键字序列为 （Jan,Feb,Mar, Apr,May,Jun,Jul Aug,Sep,Oct,Nov,Dec） ，H(x)=i/2 ，其中 i 为关键字中第一 字母在字母表中的序号。 要求用线性探测开放定址法处理冲突， 并求出在等概率情况下查找 成功的平均查找长度。 （6） 构造有 7 个元素组成的线性表一实例，是进行快速排序时比较次数最少的初始排序。 三、 写一算法，完成对这棵二叉树的左右子树的交换，设二叉树以二叉链表作存储结构。 15 分 四、 编写一非递归算法，对一棵二叉排序树实现中序遍历。15 分 五、 编写程序，完成下列功能：15 分 1 读入整数序列，以整数 0 作为序列的结束标志（0 不作为序列元素） ，建立一个单链表。 2实现单链表原地逆转， 即单链表中结点指针方向反转， 反转操作不使用额外的链表结点， 可使用临时工作单元。 例：输入序列为：1，8，4，3，0 六、 给出有向图 G 的邻接表表示。找出其一棵最小生成树。11 分 注：编写程序可选用任一种高语言，算法描述可采用类语言，必要时加上注释 一、 回答下列问题：20分 1、 算法的定义和性质 2、 为什么说数组与广义表是线性表的推广？ 3、 什么是结构化程序设计？ 4、 哈希方法的基本思想 5、 给出一不稳定排序方法名称与实例 二、 构造结果：24分 （1） 确定 x:=x+1语句在下面程序段中的频率，要求写出分析过程。 for i:=1 to n do for j:=1 to I do for k:=1 to j do x:=x+1 （2） 画出对长度为8的有序表进行折半查找的判定树，并求其在等概率时查找成功的平均 查找长度。 （3） 已知一棵二叉树如右图，给出对这棵二叉树进行前序、中序、后序遍历的结果序列 （4） 假设用于通讯的电文仅由 8 个字母组成，字母在电文中出现的频率分别为2，3，5， 7，11，4，13，15，试为这 8 个字母设计哈夫曼编码 （5） 在地址空间为 015 的散列区中，对以下关键字序列构 G 造哈希表，关键字序列为 （Jan,Feb,Mar, Apr,May,Jun,Jul Aug,Sep,Oct,Nov,Dec） ，H(x)=i/2 ，其中 i 为关键字中第一 字母在字母表中的序号。 要求用线性探测开放定址法处理冲突， 并求出在等概率情况下查找 成功的平均查找长度。 （6） 构造有 7 个元素组成的线性表一实例，是进行快速排序时比较次数最少的初始排序。 三、 写一算法，完成对这棵二叉树的左右子树的交换，设二叉树以二叉链表作存储结构。 15 分 四、 编写一非递归算法，对一棵二叉排序树实现中序遍历。15 分 五、 编写程序，完成下列功能：15 分 1 读入整数序列，以整数 0 作为序列的结束标志（0 不作为序列元素） ，建立一个单链表。 2实现单链表原地逆转， 即单链表中结点指针方向反转， 反转操作不使用额外的链表结点， 可使用临时工作单元。 例：输入序列为：1，8，4，3，0 六、 给出有向图 G 的邻接表表示。找出其一棵最小生成树。11 分 注 编写程序可选用 PASCAL 或 C 语言 算法描述采用类语言，应加上必要的注释 所有答案均要求写在答题纸上 一、 回答问题 15分 1结构化程序设计 2面向对象开发方法与面向过程开发方法的不同之处 3数据类型含义与作用 4稳定排序与不稳定排序 二、简述方法与原因 20分 1分别采用堆排序、快速排序、直接插入排序、归并排序算法对初始状态为递 增序列的表按递增顺序排序，给出最省时间与最费时间的算法名称，简述原 因。 2实现有向图的拓扑排序能否用图的深度搜索模式来查找？若能请简述方法， 若不能，请简述原因。 3.有 n 个非零的数，仅要求将负数排列在正数的前面，但并不要求对其排序，简 述处理方法。 4说明在图的遍历中，设置访问标志数组的作用。 5.在一个连通无向图上，欲求从一点 VI到另一点 VJ（VIVJ）所经结点数目最少 的路径，在深度优先搜索、广度优先搜索、从一点到其余各顶点的最短路径或图 的其它算法中，你认为最好选择那种方法为基础，简述原因。 三、构造结果 25分 1. 二叉树按二叉链表方式存放，其中的 data 域为 char 类型，已 有按前序方式构造二叉树的算法，若输入序列为 ABCDEDG，请给 出构造的相应二叉树。 2.已知 Ackerman 函数定义如下： n+1 当 m=0时 akm(m,n) = akm(m-1,1) 当 m0,n=0时 akm(m-1, akm(m,n-1) 当 m0,n0时 写出 akm(2,1)时调用时变化过程与执行结果。 3. 对于正整数 A、B，说明下面程序段定义了什么函数功能，要求重写程序段， 使之完成原函数功能，且执行时间仅可能短。 Unsigned int f(a,b) int a,b; if (a*b=0) return (a+b) else return(f(b-(b/a)*a,a); (注：b/a 相当整除) 4. 写出在中序线索树 BT 中找结点 X 的后继结点的函数过程。 5.对以下关键字序列建立哈希表（jan,feb,mar,apr,may,jun,jul） ，哈希函数为 H（K）=关键字中第一个字母在字母表中的序号）MOD 7，用线性探测再散列法或 链地址法之一处理冲突，要求构造一个装填因子为0.7的哈希表，并求出等概率 情况下查找成功与不成功的平均查找长度。 四、有二叉排序树采用二叉链表方式存放，树中结点值各不相同，欲 得到一个由大到小的结点值递减序列，简述处理方法思路，用非递归 形式写出算法。10分 1 一棵树采用孩子-兄弟方式存放，结点结构为 fc h da ta ns ib le ve l 其中 fch 表示指向第一个孩子，nisib 表示指向下一个兄弟, level 表示结点层 次。 设根结点层次为1，其它以此类推，编写一算法，将树中所有结点层 次值置入相应 level 域。10分 六、 以顺序存储结构表示串,设计算法,求串 S 中出现的第一个最长重 复子串及其位置并分析算法的时间复杂度. 10分 七、 编写程序，要求完成： 建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每 个结点的 data 域存放一个二进制位。 在此链表上实现对二进制数加1的运算，并输出运算结果。10分 注：编写程序可用 PASCAL 或 C 语言；算法描述可采用类语言，加上必要注释； 一、解释和简答下列问题： （20分） 1） 算法的定义和特性 2） 抽象数据类型 3） 广义表与字符串属于线性表的理由 4） 封装 5） 排序算法的稳定性 6） 结构化程序设计 二、写出要求结果： （30分） 1 已知一二叉树中序序列为 DBGEAFC， 后序序列为 DGEBFCA， 给出其对应的二叉树。 2给定权值8，12，4，5，26，16，9，构造一棵带权路径长度最短的二叉树，并计 算其带权路径长度。 1 有一线性表，要求重新排列，使所有的正数均在非正数之前，要求用最小交换次数 实现，你认为应采用什么方法？ 4只想得到 N 个元素序列中第 K 个最大元素之前的部分递减有序序列（K=2; i-) For i=n downto 2 do bi= bi+ bi-1 bi= bi+ bi-1 END 若调用 bin(A, 5), 给出 A 数组中第1个至第6个数组元素的输出结果。 2给出求 N 阶 hanoi 塔的函数定义如下： hanoi(int n，char x, char y, char z)； if (n=1) move(x,1,z) else hanoi(n-1,x,z,y)； move(x,n,z)； hanoi(n-1,y,x,z) 请写出执行 hanoi(3,a,b,c)时递归函数的实在参量变化及 move 的搬动过程。 3已知一个循环单链表 la,av 是可利用栈的头指针，请用3个赋值语句，完成将 整个循环单链表释放的功能（即将 la 表整个归还到可用空间栈） 。 4. 在 地 址 空 间 为 0-12 的 散 列 区 中 ， 对 以 下 关 键 字 序 列 ： （Jan,Feb,Apr,May,Jun,Jul,Aug,Sep,Oct）建哈希表，设哈希函数为 H（X）=i/2， 其中 i 为关键字中的第一个字母在字母表中的序号，处理冲突可选用线性探测法 或链地址法之一，要求构造哈希表，并求出在等概率的情况下查找成功与不成功 的平均查找长度。 5在排序连续顺序文件中采用折半查找方法查找记录存在与否的过程可以借助 于一棵折半判定树来模拟，树中结点的值为记录在文件中的位置序号。 若文件中有 l 7个记录，请画出这棵折半判定树； 当文件中有 n 个记录时，给出该判定树的深度。 6设某城市有 N 个车站，并有 M 条公交线路连接这些车站，设这些公交车都是 单向的，这 N 个车站顺序编号为0至 N-1，要求输入该城市的公交线路数、车站 个数以及各公交线路上各站编号，要求从站0出发乘公交车至站 N-1的最少换车 次数，简述应如何设置数据结构、应当采用的基本处理方法。 7下图是带 权的有向图 G 的邻接表表示法。给出从结点 V1到结点 V8的最短路径。 8在后序线索树中，要找出 X 结点的前趋结点，请写出相关语句 LtagLcDataRtagRc 四编写程序，实现在链式存储方式下的模式匹配。 设主串 s 和子串 t 分别以单链表存储，t 和 s 中每个字符均用一结点表示： dataNext 实现在链式存储方式下的模式匹配，即求子串 t 在主串 s 中第一次出现的位置指 针。12分 五、编写算法： 已知二叉树采用二叉链表方式存放，其中要求对二叉树从1开始进行连续编号， 要求每个结点 v 的编号等于其左子树上最小编号加1，结点 v 的编号等于其右子 树结点中最大编号加1，请回答采用什么次序的遍历方式实现编号？并给出在二 叉树中结点的数据域部分填写实现如上要求编号的非递归算法。13分 六、编写算法： 已知深度为 h 的二叉树采用顺序存储结构已存放于数组 BT1：2 h1中，请写 一算法，产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为 根结点所在链结点的指针由 BT 给出。13分 七、编写程序： 已知全省有 m 个学生参加计算机等级考试， 其成绩值均为界于0100之间的整数 值，且成绩中有许多值重复出现多次，请按下列方法进行排序：另设数组 num0:100，且令 numi计算统计整数 i 在成绩数组中重复出现的次数，之后 按 num 重排成绩数组，以达成绩数组递增有序。编写程序实现上述要求。12分 （2） 写一个判别给定的二叉树是否是完全二叉树的算法。 完全二叉树定义为：深度为 K、具有 N 个结点的二叉树的每一个结点都与深度为 K 的满二叉树中编号从1至 N 的结点一一对应（此题以此定义为准） 。12分 六、给定一公园的导游图，自给适当的数据结构，编写算法实现下列要求： 游客从大门进入，选择一条最佳路线，使游客可以不重复的游览各景点，最后回到大 门。10分 答案请答在答题纸上，答在本试题上的答案一律无效答案请答在答题纸上，答在本试题上的答案一律无效 注 编写程序可选用 PASCAL 或 C 语言 算法描述采用类语言，算法应加上必要的注释，所有答案均要求写在答题纸上 一、简答问题：30分 1结构化程序设计（目的、构成与方法） 2简述栈、队列、串、数组的共同点和不同点，它们属于线性表原因 3简述面向对象方法的特点 4线性结构与非线性结构的差别 5算法特性与算法时间复杂度 二、选择题： 20分 1 已知一算术表达式的中缀形式为 AB *C-D/E，后缀形式为 ABC *+DE/-，其 前缀形式为( )。 A. A+B*C/DE B. A+B*CD/E C.-+*ABC/DE D.-+A*BC/DE 2 利用逐点插入法建立序列(50，72，43，85，75，20，35，45，65，30)对应 的二叉排序树以后，查找元素35要进行（ ）元素间的比较。 A4次 B5次 C. 7次 D10次 3在有 n 个叶子结点的哈夫曼树中，其结点总数为 ( ) 。 A、不确定 B、2n C、2n+1 D、2n-1 4 若需在 O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则 可选择的排序方法是: A快速排序 B.堆排序 C.归并排序 D.直接插入排序 5若一个有向图的邻接矩阵中，主对角线以下的元素均为零，则该图的拓扑有 序序列( ) A. 存在 B. 不存在 6 将两个各有 n 个元素的有序表归并成一个有序表，其最少的比较次数是 ( ) A. n B. 2n1 C. 2n D. n-1 7 下述二叉树中，哪一种满足性质：从任一节点出发到根的路径上所经过的节 点序列按其关键字有序 ( ) A.二叉排序树 B. 哈夫曼树 C. AVL 树 D. 堆 8 已知待排序的 n 个元素可分为 n/k 个组，每个组包含 k 个元素，且任一组内 的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素， 若采用基 于比较的排序，其时间下界应为( ) A. O（nlog2n） B. O(nlog2k) C. O(klog2n) D. O(klog2k) 9数组 A1.5,1.6的每个元素占5个单元， 将其按行优先次序存储在起始地址 为1000的连续内存单元中，则 A5，5的地址是 ( )。 A、1140 B、1145 C、1120 D、1125 10. 在有 n 个叶子结点的哈夫曼树中，其结点总数为( )。 A、不确定 B、2n C、2n+1 D、2n-1 三、写出要求结果：50分 1下列 C 与 PASCAL 函数的功能相同 有 C 函数定义如下： 有 PASCAL 过程定义如下： int gc(:int m, n) FUNCTION GC(M,N:INTEGER);INTEGER BEGIN if (n=0 ) return(m); I F N=0 THEN GC:=M else retun (n，m /n); ELSE GC:=GC(N，M MOD N) END 写出此函数功能，并改写它，使其执行速度仅可能的短。 2给出求 N 阶 hanoi 塔的函数定义如下： hanoi(int n，char x, char y, char z)； if (n=1) move(x,1,z) else hanoi(n-1,x,z,y)； move(x,n,z)； hanoi(n-1,y,x,z)； 请写出执行 hanoi(3,a,b,c)时递归函数的实在参量变化及 move 的搬动过程。 3在前序线索树中，要找出 X 结点的后继结点，请写出相关语句 LtagLcDataRtagRc 4 一棵非空的二叉树其前序序列与后序序列正好相反，给出满足条件的二叉树。 5在数轴上有 n 个彼此不交的相邻区间，每个区间下、上界都是整数，按区间 位置从左到右依次编号为1N。试问：要查找某个给定值 x 所在区间，你认为应 选择什么方法查找最快，简述原因。 6已知关键字序列为： （75, 33, 52, 41, 12, 88, 66, 27）哈希表长为10，哈