2009年山西太原科技大学数据结构考研真题.doc

发布时间：2022-09-19 发布人：admin 分类：说明书资料大小：0.19M 资料格式：doc 举报版权申诉

第1页 / 共4页

第2页 / 共4页

第3页 / 共4页

第4页 / 共4页

文本预览

2009 年山西太原科技大学数据结构考研真题一.名词解释（每小题 3 分，共 30 分） 1.数据结构 2.算法有穷性 3.单链表 4.广义表 5.线索二叉树 6.强连通图 7.邻接表 8. 哈希表 9.堆 10.索引文件二.单项选择题（每小题 2 分，共 20 分） 1．在长度为 n 的顺序表中第 i 个元素之前插入一个数据元素时，需要将__移动一个位置。 a.第 1 到第 i 个元素向前 b.第 1 到第 i 个元素向后 c.第 n 到第 i 个元素向前 d.第 n 到第 i 个元素向后 2.在带头结点的单链表中第 i 个结点之后插入 s 所指结点，主要步骤是__

3.一个栈的入栈序列是 12345，则栈的不可能出栈序列是__ a.12345 b.12435 c.43512 d.54321 4.在队头 front、队尾 rear 的链队列 Q 中，将 p 所指结点入队的主要操作是 5.中序遍历二叉树可定义为∶若二叉树为空，则空操作∶否则，_ 6.串的模式匹配指的是_ a.子串的定位操作 b.求串长操作 c. 求子串值的操作 d. 串的连接操作 7.广义表（a，b），c，d）的表头和表为表尾分别是__。 a. a 和 d b.（a，b）和 d c. a 和（Cs.d）

d.（a，b）和（c，d） 8.深度为 4 的二叉树最多有__个结点。 a15 b.16 c. 8 d.10 9.具有 5 个顶点的无向完全图有__条边。 a.6 b.8 c. 10 d.12 10.下列排序中要求辅助存储空间最多的是__。 a.插入排序 b.归并排序 c.快速排序 d.堆排序三.综合题（每小题 15 分，共 60 分） 1. （本题 15 分）已知一棵二叉树的中序遍历序列为 RBSCEAFDLKM ，后序遍历序列为 RSBECFKLMDA，试 a.写出分析构造二叉树的过程∶b.画出该二叉树;c.写出其先序遍历序列。 2.（本题 15 分）给定一无向图如图所示，试 a.给出其邻接矩阵表示法;b.给出从 v1 出发的深度优先和广度优先遍历序列;c.若边集{vlv2，v2v4，vlv3，vlv5，3v5，v2v5， v5v6，v4v6，v4v5}的权值分别为{3，3，1，4.5，4，2，5，4}，画出用 Prim 方法从 v1 出发构造最小生成树的生成过程。 3.（本题 15 分）某电文中字符{a，b、c，d，ef，ghi}出现的概率分别为

{0.20，0.19，0.07，0.02，0.12，0.06，0.10，0.03，0.21}，试 a.构造其哈夫曼树∶b. 为各字符设计其哈夫曼编码;c.计算其带权路径长度。 4.（本题 15 分）运用算符优先算法对表达式#8+4*（5-3）#进行求值时，画出每一步操作符栈、操作数栈、输入字符和主要操作的变化过程。四．算法编制题（前 2 小题每题 15 分，后 1 小题每题 10 分，共 40 分） 1.（本题 15 分）在带头结点的非递减有序单链表 L 中，插入一数据 x，并使 L 表仍为有序表，要求 a.编写算法并给予适当的注释说明;b.分析算法的时间复杂度。 2.（本题 15 分）给定一关键字序列 57，23，8，41，27，9，65，19，要求 a 列出直接插入排序每趟排序后的关键字序列;b.给出其算法。 3.（本题 10 分）用线性表存放集合 A、B、C 的数据，求其集合 C=ATB，要求 a 描述数据的存储结构并给出求解的算法思路;b.编写其算法。

分享到：

赞收藏

资料库

2009年山西太原科技大学数据结构考研真题.doc

相关推荐

考研

热门标签

最新资料