..................... 沈阳工业大学
2017年硕士研究生招生考试题签
(请考生将题答在答题册上，答在题签上无效)
科目名称；数据结构
一. 名词解释(20分，每题4分) 1.
时间复杂度
2.队列 3.二叉排序树 4.图的顶点的度 5.最小生成树
第1页共2页
二. 填空(30分，每空3分)
1. 执行下面程序段时，S语句的执行次数是
for (int i=l; i<=nT ; i++)
for(int j=i+l;j<=n;j++)
S;
2. 在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数是 3. 在一个长度为n的顺序表的表尾插入一个元素的时间复杂度是
o
操作。
4. 在一个表头指针为ph的单链表中，若要向表头插入一个由指针P指向的结点，则应执行 操作是
=
o
。
5.假定利用数组a[N]循环顺序存储一个队列，用f和r分别表示队首和队尾指针，并已知队未满，当元素X进 队时所执行的6.已知一个无向带权图的边集为｛ (0, 1) 3, (0, 2) 6, (0, 3) 9, (1, 4) 10, (2, 3) 2, (2, 4) 5, (3, 4) 4),利用狄克斯特拉算法求从源点0到其余各顶点的最短路径的过程中，到顶点3的最短路径被第 个求出。 7. 一棵树的广义表表示为a(b(c, d(e, f), g(h)), i (j, k(x, y)))，假设根结点为第1层，则结点d在第 ____________ 层。
8. 对数据(18, 25, 63, 50, 42, 32, 90)进行散列储存时，若选用
H(K) = K % 9
作为散列函数，则散列地址是0的元素有 序结束后的结果是 三解答问题(50分)
1. (7分)给定30个字符组成的电文： DDDDDAAABEEAAFCDAACABBCCCBAADD 试为字符A、B、C、D、E、F设计哈夫曼(Huffman)编码。
(1) 画出相应的哈夫曼树；
(2) 分别列出A、B、C、D、E、F的哈夫曼编码； (3) 计算该哈夫曼树的带权路径长度WPL。
2.(7分)试按表(10,8,9,12,20,5,6,15,19,25)中元素的排列次序，将所有元素插入一棵初始为空的二叉 排序树中，使之仍是一棵二叉排序树。
(1) 试画出插入完成之后的二叉排序树；
(2) 若查找元素17,它将依次与二叉排序树中哪些元素比较大小？ (3) 假设每个元素的査找概率相等，试计算该树的平均查找.长度ASL。 (4) 对该树进行中序遍历，试写出中序遍历序列。
个，散列地址是5的元素有
o
个。
9.设一组初始关键字序列为(38, 65, 97, 76, 13, 27, 10),采用冒泡排序法从第1个元素开始按小到大进 行排序，则第3趟冒泡排
.....................
斜国糸钵:数翠凭构
仅用于评估。
由 Foxit PDF Editor
豊枳Kff有（c） by Foxit Software Company, 2003 - 2009
3.（7分）已知一棵二叉树的前序遍历的结果序列为ABECDFGHIJ,中序遍历的结果为EBCDAFHIGJ,画 出这棵二叉树并写出这棵二叉树的后序遍历结果。
（7分）试将森林F={ T1,T2,T3,T4 }转换为一棵二叉树。' 4.
T3
T4
5.（7分）采用普利姆（Prim）算法从A开始求下面网络的最小生成树。要求写出每一步的结果。
（7分）假定一个待散列存储的数据集为{32, 75, 29, 63, 48, 94, 25, 46, 18, 70},散列地址空间为 HTC13],若釆用除6.
留余数法H（K） = K % 13构造散列函数和线性探测法处理冲突，试求出每一元素在散 列表中的初始散列地址和最终散列地址，画出最后得到的散列表。（此题解答只需填写下列两表） 初始散列地址和最终散列地址：（答案写在答题纸上）
8 32 9 18 10 70 75 29 63 48 94 25 46 散列表：（答案写在答题纸上） 0123456789
10
11
12
1 2 3 4 5 6 7
7. （8分）己知一组数据为（46, 74, 53, 14, 26, 38, 86, 65, 27, 34）,给出采用快速排序法进行排序时 第1趟和第2趟划分后的排序结果。
四.编写算法（50分，每题10分）（程序设计语言不限，如果你的程序设计语言不是C或C++请标明） 1. 假设顺序表L中的元素递增排列，设计算法在顺序表中插入元素x,要求插入后仍保持其递增有序性。 2. 设计算法将递增有序顺序表A、B中的元素合并成一个递增有序顺序表C。
3. 已知递增有序链表A、B分别表示集合A、B,设计算法实现集合C=AnB,要求C是链表且仍递增有序。 4. 设计一个递归算法按中序次序输出二叉树T中度为1的结点的值。 5. 写出冒泡（起泡）排序算法的程序代码。
因篇幅问题不能全部显示，请点此查看更多更全内容