1、第 1 页 共 4 页 昆明理工大学 2011年硕士研究生招生入学考试试题 (A卷 ) 考试科目代码： 835 考试科目名称 ： 数据结构教程 试题适用招生专业 ： 071101 系统理论、 071102 系统分析与集成 考生答题须知 1 所有题目（包括填空、选择、图表等类型题目）答题答案必须做在考点发给的答题纸上，做在本试题册上无效。请考生务必在答题纸上写清题号。 2 评卷时不评阅本试题册，答题如有做在本试题册上而影响成绩的，后果由考生自己负责。 3 答题时一律使用蓝、黑色墨水笔或圆珠笔作答（画图可用铅笔），用其它笔答题不给分。 4 答题时不准使用涂改液等具有明显标记的涂改用品。 一、单项选
2、择题：（每题 3 分，共 30 分） 1 在数据结构中 ， 从逻辑上可以把数据结构分为 _两类 。 ： 动态结构和静态结构 ： 紧凑结构和非紧凑结构 ： 线性结构和非线性结构 ： 内部结构和外部结构 2 数据采用链式存储结构时 ， 要求 _。 ： 每个结点占用一片连续的存储区域 ： 所有结点占用一片连续的存储区域 ： 结点的最后一个数据域是指针类型 ： 每个结点有多少个后继 ， 就没多少个指针域 3 某算法的时间复杂度为 O（ 2n ） ，表明该算法的 _。 A： 问题规模是 2n B： 执行时间等于 2n C： 执行时间与 2n 成正比 D： 问题规模与 2n 成正比 4. 在一个长度为 n
3、 的顺序表中向第 i 个元素（ 0next=p; p next=s; B： s next=p next; p next=s; C： s next=p next; p=s; D： p next=s; s next=p; 6 设一个 栈的输入序列为 A， B， C， D，则借助栈所得到的输出序列不可能是 。 A： A,B,C,D B： D,C,B,A C： A,C,D,B D： D,A,B,C 7 一个 n n 的对称矩阵 ， 如果以行或列为主序放入内存，则 存储 容量为 _。 A： n2 B： n2/2 C： n(n+1)/2 D： (n+1)2 /2 8. 一棵有 124 个叶结点的完全二叉树
4、，最多有 _个结点。 第 2 页 共 4 页 A： 247 B： 248 C： 249 D： 250 9. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的 _算法。 A：先 序遍历 B： 中序遍历 C： 后序遍历 D：层次 遍历 10. 设哈希表长 m=14，哈希函数 H（ key） =key mod 11。表中已有 4 个结点 addr(15)=4，addr(38)=5， addr(61)=6， addr(84)=7，其余地址为空。如用二次探测再散列法处理冲突，则关键字为 49 的结点地址是 _。 A： 8 B： 3 C： 5 D： 9 二、 判断题（每题 2 分，共 20 分） 1 任
5、何数据结构都具备三个基本运算 ： 插入、删除和查找。 （ ） 2. 在循环单链表中，任何一个结点的指针字段值都不可能为空。 （ ） 3. 顺序队列中有多少元素，可以根据 队 首指针和队尾指针的值来计算。 （ ） 4. 若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算。 （ ） 5. 递归算法的执行效率比功能相同的非递归算法的执行效率高。 （ ） 6. 当二叉树中的结点数多于 1 个 时 ，不可能根据结点的先序序列和后序序列唯一地确定该二叉树的逻辑结构。 （ ） 7. 若一个树叶是某二叉树先序遍历序列中的最后一个结点，则它必是该子树后序遍历序列中的
6、最后一个结点。 （ ） 8. 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。 （ ） 9. 一个广义表的表尾总是一个广义表。 （ ） 10. 连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点。 （ ） 三、简答题（共 60 分） 1 线性表有两种存储结构：一是顺序表，二是链表，试问： （共 12 分） （ 1）如果有 n 个线性表同时共存，并且在处理过程中各表的长度会动态地发生变化，线性表的总数也会自动地改变。 在此情况下应选用哪种存储结构？为什么？ （ 6 分） （ 2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么 应 采用
7、哪种存储结构？为什么？ （ 6 分） 2. 一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来。试求出空格处的内容，并画出该二叉树。 （每个序列 3分，画出二叉树 6 分，共 15分） 先序序列： _B _F_ ICEH_ G 中序序列： D _KFIA _EJC _ 后序序列： _ K _FBHJ _G_ A 3. 有如 下 图 二 所示的带权有向图 G，试回答以下问题 ： （共 18 分） （ 1）给出从顶点 1 出发的深度优先遍历序列和广度优先遍历序列。 （ 6 分） （ 2）给出 G 的一个拓扑序列。 （ 4 分） 第 3 页 共 4 页 （ 3）给出从顶点 1 到顶点
8、8 的最短路径和关键路径。 （ 8 分） 图 二 4. 设用于通讯的电文仅由 8 个字母构成，字母在电文中出现的频率分别为： 7、 19、 2、 6、 32、3、 21、 10。试为这 8 个字母设计哈夫曼编码。 （ 画图 10分 ， 写出编码 5 分 ， 共 15 分 ） 四、 以关键字序列 265， 301， 751， 129， 937， 863， 742， 694， 076， 438为例， 试 写出执行 大根堆 排序算法的各趟排序结果时，关键字序列的状态 。 （ 10 分） 五、 设计一个算法 ， 将一个带头节点的数据域依次为 a1， a2， a3， .， an (n=3)的单链表 中
9、所有节点逆置，即第一个节点的数据域变为 an， 最后一个节点的数据域变为 a1。 算法可用 C 或 pascal语言进行描述。 （ 10 分） 六、 有一种简单的排序算法，叫做计数排序。这种排序算法 对一个待排序 的表（用数组表示）进行排序，并将排序结果存放到另一个新的表中。必须注意 的是，表中所有待排序的关键字互不相同。计数排序算 法针对表中的每 个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小。假设针对某一个记录，统计出的计数为 count，那么，这个纪录在新的有序表中的合适的存放位置为 count。 （共 20 分） (1) 给出适合用于计数排序的数据表定义。 （ 5 分） （ 2）使用 C 或 pascal 语言编写实现计数排序的算法。 （ 10 分） （ 3）对于有 n 个记录的表，关键字比较次数是多少？ （ 5 分） 第 4 页 共 4 页
