IM电竞 IM电竞appIM电竞 IM电竞appIM电竞 电子竞技平台IM电竞 电子竞技平台7、树最适合用来表示 。 A. 有序数据元素 C. 元素之间具有分支层次关系的数据 8、下图所示的 4 棵二叉树中，
A. B. C. D. 9、深度为 5 的二叉树至多有 个结点。 A. 16 B. 32 C. 31 D. 10 10、任何一棵二叉树的叶子结点在先序、中序、和后序遍历序列中的相对次序 A. 不发生改变 B. 发生改变 C. 不能确定 D. 以上都不对
三、简答题（6 分/题，共 36 分） 简答题（ 题 1、有一份电文使用了 5 个字符：a,b,c,d, e。它们出现的频率依次为：4、7、5、2、 9。 （1）画出对应的哈夫曼树。 （2）求出对应的哈夫曼编码。 2、已知一棵二叉树的中序序列为：c b e d a h g f ，后序序列为：c e d b h g f a 。画出这 棵二叉树并写出该树的先序序列。 3、设线123，70，63， 47}，哈希函数 H（key）=key%13。 （1）画出用拉链法处理冲突时所构造的哈希表. （2）求出在等概率情况下成功的平均查找长度。 4、给出一组待排序序列{503，87，512，61，908，170，897，275，653，462}，试写 出用快速排序法按从小到大顺序排序的第一趟排序的过程。 5、写出附图的邻接矩阵和邻接表。 6、求出附图源点 1 的 Dijistra 最短路径。
二、选择题（2 分/题，共 20 分） 选择题（ 题 1、在数据结构中，从逻辑上可以把数据结构分为 。 A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D. 内部结构和外部结构 2、以下叙述正确的是 。 A. 线性表的线性存储结构优于链式存储结构 B. 二维数组是其数据元素为线性表的线性表 C. 栈的操作方式是先进先出 D. 队列的操作方式是先进后出 3、在决定选取何种存储结构时，一般不考虑 。 Ａ. 各结点的值如何 B. 结点个数的多少 C. 对数据有哪些运算 D. 所用编程语言实现这种结构是否方便 4、带头结点的单链表 head 为空的判定条件是 。 Ａ. head= =NULL Ｂ. head-next= =NULL Ｃ. head-next= =head Ｄ. head!=NULL 5、若已知一个栈的进栈序列是 1，2，3，…，n，其出栈序列为 p1,p2,p3,…,pn,若 p1=3，则 p2 为 。 A. 可能是 2 B.一定是 2 C.可能是 1 D.一定是 1 6、在一个链队中，假设 f 和 r 分别为队头和队尾指针，则删除一个结点的运算为（ ） 。 A．r=f next; B．r=r next; C．f=f next; D．f=r next;
四、算法填空题（2 分/空，共 18 分） 算法填空题（ 空 1、已知线性表元素递增有序，并以带头结点的单链表作存储结构。试补充下列算法实
课程名称: 数据结构 B 考试时间 :120 分钟 班级:___________ 学号_________ 题号 满分 得分 评卷人 一、填空题（2 分/空，共 24 分） 填空题（ 空 结构存储，为了方 1、设有一批数据元素，为了最快地存取某元素，宜采用 便的插入、删除一个元素，宜采用 结构存储。 2、表长为 n 的顺序表中，若在第 i 个数据元素（1= i =n1）之前插入一个数据元素，需 要向后移动 个数据元素。 和 3、 在一个单链表中 p 所指的结点之后插入一个 s 所指的结点时， 应执行 s-next= p-next= 的操作。 4、设有一个头指针为 head 的单向循环链表，p 指向链表中的结点，若 p-next= =_______， 则 p 所指结点为尾结点。 。 5、队列的 FIFO 特性是指 6、对于一个具有个 n 顶点的无向连通图，边的数目至少为 ；最多为 。 进行。 7、栈是一种运算受限的线形表，它限制插入和删除操作只允许在 8、衡量算法好坏的两个指标是 和 。 一 20 二 24 三 36 四 20 五 六 七 八 姓名__________ 九 十 得分 100
