贵州大学2014-2015学年第一学期考试试卷 B
数据结构与算法
注意事项：
1. 请考生按要求在试卷装订线内填写姓名. 学号和年级专业。 2. 请仔细阅读各种题目的回答要求，在规定的位置填写答案。 3. 不要在试卷上乱写乱画，不要在装订线内填写无关的内容。 4. 满分100分，考试时间为120分钟。 题 号 得 分 得 分 评分人
一 二 三 四 总 分 统分人 一. 选择题（共10分,每题1分）
1. 在数据结构中，从逻辑上可以把数据结构分成( C )。
A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构
2．对顺序存储的线性表，设其长度为n，在任何位置上删除操作都是等概率的，则删除一个元素大约要移动表中元素的个数是( D )。 A．n∕2 B．(n+1)∕2 C．n-1 D．(n-1)∕2 3．以下的叙述中，正确的是(B )。
A.线性表的顺序存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表
C.栈的操作方式是先进先出 D.队列的操作方式是先进后出 4．在表达式中进行括号匹配检验时，采用( B )数据结构最佳。
A．线性表的顺序存储结构 B．栈 C．线性表的链式存储结构 D．队列
5．循环队列的最大容量为MAXSIZE，队尾指针是rear，对头指针是front，则队空的条件是 ( B )。
A. Q. front=maxsize B. Q. rear=Q. front
C. Q. rear=maxsize D. (Q. rear+1)%maxsize=Q. front
第 1 页 共 9 页
6．在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行（ C ） 。
A. s->next = p->next; p->next=s; B. p->next = s->next; s->next = p; C. q->next = s; s->next = p; D. p->next = s; s->next = q; 7．AOE网是一种（ D ）
A．有向图 B．无向图 C．无向无环图 D．有向无环图
8．一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有（ B ）个结点。 A.2k-1-1 B.2k-1 C.2k-1+1 D.2k-1
9．先将整个待排序元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的），分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序( A )。
A．快速排序 B．起泡排序 C．直接选择排序 D．希尔排序
10．采用折半查找方法进行查找，数据文件应为（ D ），且限于（ ）。 A．随机表 顺序存储结构 B．有序表 链式存储结构
C．有序表 顺序存储结构 D．随机表 链式存储结构
得 分 评分人
二. 填空题（共15分,每空1分）
1. 栈和队列都是一种 _特殊_ 的线性表，栈的插入和删除只能在_栈顶 进行。 2. 对一棵二叉排序树进行中序遍历时，得到的结点序列是一个_有序序列_。对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式 、后缀表达式_。
3. 已知二叉树有45个叶子结点，则该二叉树的总结点数至少是 89 。
4. n个结点无向完全图的的边数为 n（n-1）/2 ， n个结点的生成树的边数为 n-1 。
5. 队列的插入操作是在队列的 队尾 进行，删除操作是在队列的__队头_进行。 6. 若对一棵完全二叉树从1开始进行结点的编号，并按此编号把它顺序存储到一维数组A中，即编号为2的结点存储到A[1]中。其余类推，则A[ i ]元素的左孩子元素为2i+2_，右孩子元素为__2i+3__，双亲元素为__i+1__。
7. 从顶点V1出发，对如下无向图进行遍历深度优先遍历(Depth-First Search)序列为 ALBECDWX ，广度优先遍历(Breadth-First Search)序列为 ALCBERWX 。
第 2 页 共 9 页
V1V2V4V5V3V6V8V7
8. 在有序表（12,24,36,48,60,72,84）中二分查找关键字24时所需进行的关键字比较次数为___2___。
得 分 评分人 三. 应用题（共55分）
1. 已知数据8个字母及在通信中出现频率如下表：（10分） A B C D E F G 0.07 0.08 0.29 0.11 0.23 0.03 0.05 把这些字母和频率作为叶子结点及其权值，完成如下工作： （1）画出对应的Huffman树； （2）计算带权路径长度WPL；
（3）求A、B、C、D、E、F、G、H的Huffman编码。
(1) 哈夫曼树如下，每画对一个叶子，给0.5分，结构1分，共5分
H 0.14 EDFGABHC
（2）WPL=0.02*5+ 0.04*5+0.06*4+0.08*4+0.1*4+0.3*2+0.4*1=2.26（1分） （3）A: 1000 B:1001 C:11 D:001 E:01 F:0000 G:0001 H:101（每个0.5分，共4分）
2. 设散列函数H(k)=k % 13，设关键字序列为{22,12,24,6,45,7,8,13,21}。（9分） (1) 请画出所构造的散列表。
第 3 页 共 9 页
(2) 在(1)的基础上，请画出用链地址法处理冲突的哈希表；
(3) 利用性探测法处理冲突，在记录查找等概率情况下，分别计算查找成功和
查找不成功的平均查找长度。
（1）Hash表（2分） 地址 关键字 比较次数 0 1 1 7 2 3 4 5 6 1 7 2 8 2 9 1 10 11 12 8 3 24 12 1 1 13 21 6 45 7 22 （2）链地址法处理冲突的哈希表（3分）
1212?1124?10?922?8821?77?6645?5?4?3?2?1?013? (3)
地址 关键字 查找成功次数次数 查找不成功次数 0 1 3 1 7 2 2 3 4 5 6 6 1 7 2 9 8 2 8 9 1 7 10 11 12 8 3 6 24 12 1 5 1 4 13 21 45 7 22 1 1 1 1 10 查找成功的平均查找长度：（2分） （5*1+2*2+1*3+1*7）/9=19/9
查找不成功的平均查找长度：（2分）
（3+2+1+1+1+1+10+9+8+7+6+5+4）/13=58/13
3. 给定表（19,14,22,15,20,21,56,10）.（9分） (1)按元素在表中的次序，建立一棵二叉排序树
(2)对(1)中所建立的二叉排序树进行中序遍历，写出遍历序列。 (3)画出对(2)中的遍历序列进行折半查找过程的判定树。
第 4 页 共 9 页
ABCDLEFGHI
（1）、构造（3分）
19 14 22 10 15 20 56 21
(2)、10 14 15 19 20 21 22 56（3分） （3）、折半查找过程的判定树（3分）
4. 如图所示AOV有向网G：（10分） 1V1V5003060V4102040V010550V2V3
第 5 页 共 9 页
贵州大学2014-2015学年第一学期《数据结构与算法》B卷
