a b e c d 图1
f
26．如图2所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一
种顶点序列为（ ）。
A．abedfc B．acfebd C．aebcdf D．aebcfd
a b e c d f
图2
27．一组记录的关键字序列为（46,20,30,79，56，38，40，84,90,110），利用快速排序，以
第一个关键字为分割元素，经过一次划分后结果为（ ）。 A．20,30,40，38，46，79，56，84,90,100 B．40，20,30,38，46，56，79，84,90,110 C．30,20,40，38，46，84，56，79,90,100
D．20,30 38，40，46，56，79，84,90,100
28．一组记录的关键字序列为（56，30,89，66，48，50，94,87,100），利用快速排序，以第
一个关键字为分割元素，经过一次划分后结果为（ ）。
A．30，50,48，56，66，89，94,100,87B． 50，30,48，56，66，89，94,87,100 C．48，30,50，56，66，89，94,87,100D．50，30,48，66，56，89，94,87,100 29．一组记录的关键字序列为（75，63，95，80，53，45，38，20），利用堆排序（堆顶元素是最大元素）的方法建立的初始堆为（ ）。 A．95，80，75，63，53，45，38，20 B．95，63，75，80，53，45，38，20 c. 95, 80, 45, 63, 53, 75, 38, 20
D．95, 80, 75, 20, 53, 45, 38, 63 30．线性表以（ ）方式存储，能进行折半查找。
A．关键字有序的链接B．顺序 C．关键字有序的顺序D．数组
16
二、填空题
1．数据元素之间的抽象关系称为________结构。
2. 数据的逻辑结构在计算机中的表示称为________结构。
3．要求在n个数据元素中找值最大的元素，其基本操作为________。算法的时间复杂 度为_______ 。
4. 求两个n阶矩阵的乘积，算法的基本操作为________，时间复杂度为 ________。 5．设有一个长度为25的顺序表,第8号元素到第25号元素依次存放的值
为 8,9,10,11,?,25，某人想要删除第8个元素，他的做法是从第25号元素开始,直 到第9号元素依次向前移动1个位置,其结果新表中第9号元素的值为（ ）。 6． 设有一个长度为25的顺序表,第8号元素到第25号元素依次存放的值为8,9,10,11,?25, 某人想要在第8个元素前插入1个元素7（也就是插入元素作为新表的第8个元素），他 的做法是从第8号元素开始,直到第25号元素依次向后移动1个位置,然后把7存放在 8号位置，其结果是新表中第25号元素的值为（ ）。
7．在双向链表中，要在p所指的结后插入q所指的结点(设q所指的结点已赋值)，可以
先用语句q->next=p->next; （p->next）->prior=q； 然后再用语句q->prior=p;和语句________。
8．在双向链表中，要在p所指的结后插入q所指的结点(设q所指的结点已赋值)，
其中所用的一条语句（p->next）->prior=q； 的功能是使P所指结点的_______指向q 。 9．在一个单向链表中，要删除p所指结点的直接后继结点。则可以用操作 ________。（用一条语句）
10．设有一个带头结点的，头指针为head的单向链表，p指向表中某一个结点，且有
p->next= =NULL,现要删除头结点，并使该单向链表构造成单向循环链表，通过 操作head=head->next; ________。
11．向一个栈顶指针为top的链栈中插入一个p所指结点时，可执行________操作。 ( 填两条语句, 结点的指针域为next)
12．从一个栈顶指针为top的链栈中删除一个结点时，用d保存被删结点的值，可执行
________。(结点的指针域为next,数据域为data)
13．在一个带头结点的链队中，设front和rear分别为队头和队尾指针，则删除一个结点
的操作为 p=front->next;_______=p->next;(结点的指针域为next, p为辅助用指针) 14 循环链队列中，设front和rear分别为队头和队尾指针，(最多元素为MaxSize,采用少用一 个元素的模式),判断循环链队列为满的条件为________ 。
15．设有n阶对称矩阵A，用一维数组s压缩存储A的下三角元素，s的下标从零开始，最 后一个元素的下标为27，则n=_______。(矩阵中的第1个元素是a1,1 ）
16．对稀疏矩阵进行压缩存储,可采用三元组表，一个6行7列的稀疏矩阵A相应的三元组 表共有8个元素,则矩阵A共有_______个零元素。
17. 一棵3度的树，其中3度结1个，2度结2个，1度结2个，则该树共有_______个 叶结点。
18.一棵有8个权重值构造的哈夫曼数，共有个结点。
19．一棵有7个叶结点的二叉树，其1度结点数的个数为2，则该树共有 _______个结点
20．一棵有18个结点的二叉树，其2度结点数的个数为8，则该树共有
_______个1度结点
21．如图3所示的二叉树，其中序遍历序列为_________。
17
21578图3
22．如图2所示的二叉树，其先序遍历序列为_________。
21578 图4
23．二叉排序树或者是一棵空树，或者是一棵具有下列性质的二叉排：若它的左子树非空，则左子树的所有结点的值都小于它的根结点的值；若它的右子树非空，则右子的所有结点的值都大于（若允许结点有相同的值，则大于等于）它的根结点的值。这种说法是__________的。(回答正确或不正确)
24．在查找表中，通过记录的某关键字能唯一地确定一个记录，该关键字称为_________。 三、综合题 1．
(1) 以3，4，5，8，9，10作为叶结点的权，构造一棵哈夫曼树。 (2) 给出相应权重值叶结点的哈夫曼编码。
(3) 一棵哈夫曼树有2n-1个结点，它是共有多少个权重值构造而成的？简述理由？
18
3469 3469
2．（1）对给定权值3，1 ，4，4，5，6，构造深度为5的哈夫曼树。(设根为第1层) (2) 求树的带权路径长度。
（3）链接存储上述哈夫曼树，结点中共有多少个指针域为空,说明理由. 3．（1）简述拓扑排序的步骤。
（2）说明有向图的拓扑序列不一定是唯一的原因。 （3）如何利用拓扑排序算法判定图是否存在回路。
（4）设有向图G如下，写出首先删除顶点1的3种拓扑序列。
1 2 3 4 5图5
6
4. (1) 如下的一棵树,给出先序遍历序列
(2) 把1,2,3,4,5,6,7,8,9填人,使它成为一棵二叉排序树
提示：设图中的树是二叉排序树，找出中序遍历序列与 1，2，…9的对应关系
(3) 请在该树中再插入一个结点3.5作为叶结点，并使它仍然是一棵二叉排序树。
A1 A2 A3 A4A5 A8 A6 A7 A9 图6
19
5．设有序表为（21，22，23，24，25，26，27，28，29，30，31,32），元素的下标从 0开始。
（1）说出有哪几个元素需要经过4次元素间的比较才能成功查到。
（2）画出对上述有序表进行折半查找所对应的判定树（树结点用数值表示） （3）设查找元素为5，需要进行多少次元素间的比较才能确定不能查到。 （4）求在等概率条件下，成功查找的平均比较次数？
6．设查找表为(5,6,7,8,9,10,11,12,13,14)
（1）画出对上述有序表进行折半查找所对应的判定树(要求以数据元素作为树结点) (2)给出二叉排序树的定义,针对上述折半查找所对应的判定树的构造过程,说明判定树 是否是二叉排序树(设树中没有相同结点)？
(3)为了查找元素5.5，经过多少次元素间的比较才能确定不能查到？
四、程序填空题
1．以下程序是快速排序的算法
设待序的记录序列存放在a[start],…a[end]中，按记录的关键字进行快速排序，先进行一次划分，再分别进行递归调用
void quicksort ( NODE a[ ], int start ,int end ) { int i，j; NODE mid ; if (start>=end ) return;
i=start; j=end; mid=a[i]; while (i { while(i 20 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构（本）期末综合练习（2013年12月）(4)在线全文阅读。
相关推荐：