875
华南理工大学
2012年攻读硕士学位研究生入学考试试卷（请在答题纸上做答，试卷上做答无效，试后本卷必须与答题纸一同交回）
科目名称：数据结构
适用专业：软件工程(专硕)
本卷满分：150分共 3 页一、填空题(30分)
1.在2n2，30 log n，5n，2n中，当n变大时所对应的增长率最有效率的算法是
________。
2.数据结构中评价算法的两个重要指标是_______和_______。
数据结构与算法考研真题
3.设三位数组a【4】【5】【6】（下标从0开始）每个元素长度为2，则a【2】【3】
【4】的地址是__________（设首元素地址为1000，数据以行优先存储）。
4.在双向链表结构中，若要求在p指针所指借点之前插入指针为s所指的借点，需
执行下列语句_________；s^.prior:=p^.prior；_________；__________。
5.设有一个空栈，栈顶指针为1000H（十六进制），现有输入序列为1，2，3，4，
5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后输出序列为________，栈顶
指针的值是_______，设栈为顺序栈，每个元素占四个字节。
6.快速排序算法的平均情形的算法时间复杂度是________。
7.设n0为哈夫曼输的叶子节点数目，则该哈夫曼树共有_______个节点。
8.一棵高度为5的完全二叉树，最少有____个结点。
9.3个节点的二叉树有____种不同形状。
10.具有n个顶点的有向连通简单平面图最少有_____条边，最多有_________条边。
二、判断题(20分)
1.快速排序是一种交换排序。
2.抽象数据类型与计算机内部表示和实现无关。
3.顺序存方式的优点是存储密度大，且插入，删除运算效率高。
4.数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构。
5.一个带权的无向连通图的最小生成树不一定唯一。
6.由二叉树的前序序列和中序序列可以唯一确定一棵二叉树。
7.在选择排序方法中，关键字比较的次数与记录的初始排列次序无关。
8.线性表就是顺序存储的表。
9.完全树的叶结点都在层数最大的一层。
10.在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同。
三、计算题（60分）
1．给出关键字34, 13, 5, 7, 90, 45, 4, 85, 33，请用起泡排序法对其升序排序，写出每
趟结果，分析时间复杂度，并说明该排序算法是否为稳定的排序算法。
2．若已知学生某科目的考试分数分布的规律（如下表所示），请设计高效率算法将百
分制分数转换为五分制（ABCDE分别对应>=90,80-90,70-80,60-70,<60)。可以使用决
策树描述该算法。
A    B    C    D    E
10%  30% 40%  15%  5%
3．已知二叉树的后序序列为EDCBIHJGFA，中序序列为EBCDAFHIGJ，是否能确
定唯一二叉树？如果可以，请画出这棵二叉树并给出其前序序列。
4．已知世界六大城市北京、纽约、巴黎、伦敦、东京、墨西哥之间的交通里程，画
出交通网络图并构造最小生成树
Pe N Pa L T M
Pe 109 82 81 21 124
32
108 N
109
82 58  97 92
Pa
L 81 55    3 95 89
21 108 97 95  113
T
124 32 92 89 113 M
5．合并两个递增次序排列的线性表（单链表形式存储）为一个递减次序的单链表。6．设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让
他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，……，
如此反复直到所有的人全部出局为止。下面要解决的Josephus问题是：对于任意给
定的n, s和m，求出这n个人的出局序列。请以n = 9, s = 1, m = 5为例，人工模拟Josephus的求解过程以求得问题的解。
四、 简答题（20分）
1．当你为解决某实际问题而选择数据结构时，应从哪些方面考虑？假设是要编制管
理通讯录的程序，选择什么样的数据结构?
2．举出你所知的各种内排序算法，根据算法复杂度对内排序算法进行分类，并说明归类原因。
五、程序设计（20分）
1．已知A[n]为整数数组，试写出实现下列运算的递归算法：
(1) 求数组A 中的最小整数。
(2) 求n 个整数的平方和。
(3) 求n 个整数的平均值。
2． 设有一个背包可以放入的物品的重量为s ，现有n 件物品，重量分别为w[1],
w[2], …, w[n]。问能否从这n 件物品中选择若干件放入此背包中，使得放入的重量之和正好为s 。如果存在一种符合上述要求的选择，则称此背包问题有解(或称其解为真)；否则称此背包问题无解(或称其解为假)。试用递归方法设计求解背包问题的算法。（提示：此背包问题的递归定义如下：）
⎪⎪⎪⎩⎪⎪⎪⎨⎧−−≥>−<><==    ][)1],[(][10      )1,(      1
0False                      0False              0True ),(时所选物品中包括时所选物品中不包括且或物品件数不能为负数且总重量不能为负数此时背包问题一定有解n w n n w s KNAP n w n s n s KNAP n s s s n s KNAP

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。