………………………………………装……………………………订……………………………线………………………………………
五、将如下图所示的无向图给出其存储结构的邻接链表表示（注：这里顶点的邻 将如下图所示的无向图给出其存储结构的邻接链表表示（ 接点按升序排列） 然后分别写出对其邻接表 ，然后分别写出对其邻接表从顶点 接点按升序排列） 然后分别写出对其邻接表从顶点 1 开始进行深度优先遍历序列 ， 和广度优先遍历序列的结果。 求出深度优先序列和广度优先 和广度优先遍历序列的结果。 画出邻接链表 4 分，求出深度优先序列和广度优先 （ 序列各 3 分，共 10 分）
在堆排序和快速排序中，若初始记录接近正序或反序， 7．在堆排序和快速排序中，若初始记录接近正序或反序，则选用 若初始记录基本无序， 若初始记录基本无序，则最好选用 。
；
错打“ ，并说明理由。 三、判断题：对打“√” ；错打“×” 并说明理由。 （每小题 1 分，共 10 分） 判断题：对打“
1. 顺序存储结构的主要缺点是不利于插入或删除操作。( 顺序存储结构的主要缺点是不利于插入或删除操作。 2. 线性表的长度是线性表所占用的存储空间的大小 ( 线性表的长度是线性表所占用的存储空间的大小。(
姓名
学号
)
3. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型 队列是一种插入与删除操作分别在表的两端进行的线性表，
结构。 （ 结构。
）
班级
4. 完全二叉树中，若一个结点没有左孩子，则它必是树叶。( 完全二叉树中，若一个结点没有左孩子，则它必是树叶。
)
5. 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。( 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。
A卷
‘ababaaababaa ababaa’ next 的函数 8．串 ‘ababaaababaa’ 的 next 的函数值为（ ） 。 A．012345678999 B．012121111212 ． ． C．011234223456 D．0123012322345 ． ． 9．若一棵二叉树具有 10 个度为 2 的结点，5 个度为 1 的结点，则度为 0 的结点个 的结点， 的结点， 数是（ 数是（ ） A．9 B．11 C．15 D．不确定 ． ． ． ． 10． 的二叉树最大的结点数为（ 10．高度为 k 的二叉树最大的结点数为（ ） 。 k k-1 k B．2 C．2 -1 A．2 ． ． ．
8．在用堆排序算法排序时，如果要使排序后的记录序列按关键字非递减有序排列， 在用堆排序算法排序时，如果要使排序后的记录序列按关键字非递减有序排列， __四种 则需要采用“大根堆” 四种。 ,_ __,_ __,_ __四种。 则需要采用“大根堆” （ 。 ） ）
的拓扑序列唯一， 为顶点数）。 ）。（ 2. 顺序存储结构是通过__ 顺序存储结构是通过__ _____表示元素之间的关系的; 链式存储结 9．图 G 的拓扑序列唯一，则其弧数必为 n-1（其中 n 为顶点数）。（ _____表示元素之间的关系的; 表示元素之间的关系的 构是通过____ ____表示元素之间的关系的 表示元素之间的关系的。 构是通过____ ____表示元素之间的关系的。 10．散列表的装填因子α越小，发生冲突的可能性就越小。 10．散列表的装填因子α越小，发生冲突的可能性就越小。（ 个结点的二叉树，采用二叉链表存储，共有______个空指针域。 ______个空指针域 3．具有 n 个结点的二叉树，采用二叉链表存储，共有______个空指针域。 则编号最大的非终端结点的编号为___ 4．完全二叉树中，结点个数为 n，则编号最大的非终端结点的编号为___ 完全二叉树中， ___。 ___。 ）
)
6. 折半查找与二叉排序树的时间性能有时不相同。 折半查找与二叉排序树的时间性能有时不相同。 查找与二叉排序树的时间性能有时不相同 （
）
7. 十字链表是无向图的一种存储结构 ， 而邻接多重表是有向图的一种存储结构 。 十字链表是无向图的一种存储结构，而邻接多重表是有向图的一种存储结构。
（
） 本试卷共 3 页，此页为 A 卷第 2 页
姓名
A． i =1
∑ A[i, j ]
n
B．
∑ A[i, j]
j=1
n
C． i =1
∑ A[ j, i]
n
D． i =1
∑ A[i, j ]
n
+
∑ A[ j, i]
j=1
n
13. L=（ a,b,c），则 的长度和深度分别为（ （a,b,c ） 13. 设广义表 L=（ a,b,c），则 L 的长度和深度分别为（ （ A. 1 和 2 B. 1 和 3 C. 1 和 1
中
………………………………………装……………………………订……………………………线………………………………………
原
工
学 院
重修标识
2006～2007 学年 第 2 学期 ～ 计算机 网络 软件 专业 数据结构 课程期末试卷
题号 一 二 三 四 五 六 七 八 九 十
7. 若已知一个栈的入栈序列是 1, 2, 3, …, n，其输出序列为 p1, p2，p3，…，pn， ， ， ， ， ) 若 p1=n，则 pi 为 ( ， A．i B．n=i C．n-i+1 D．不确定 ． ． ． ．
本试卷共
3 页，此页为
A
卷第 1 页
（注：参加重修考试者请在重修标识框内打钩）
………………………………………装……………………………订……………………………线………………………………………
二、填空 （每空 1 分，共 16 分） 个元素,可以构造出的逻辑结构有_ 1． 3
班级
14. 排好序的线性表，当查找不成功时， 14.折半查找法查找一个长为 10 的，排好序的线性表，当查找不成功时，最多需要 比较多少次（ 比较多少次（ ） A 5 B2 C 4 D1 15．一组记录的关键码为（46，79，56，38，40，84） 则利用快速排序的方法， ，则利用快速排序的方法 15．一组记录的关键码为（46，79，56，38，40，84） 则利用快速排序的方法， ， 以第一个记录为基准得到的一次划分结果为（ 以第一个记录为基准得到的一次划分结果为（ ） 。 A．(40,38,46,56,79,84) ． B. (40,38,46,79,56,84) C．(38,40,46,56,79,84) D. (40,38,46,84,56,79) ．
)
四、算法设计题： 共 10 分） 算法设计题： 设计题 （ 是一个非空队列， 是一个空栈。仅用如下给定的 如下给定的队列和栈的 已知 Q 是一个非空队列，S 是一个空栈。仅用如下给定的队列和栈的 ADT 函数 尽量少 工作变量， C++语言编写一个算法 语言编写一个算法， 和尽量少的工作变量，使用 C 或 C++语言编写一个算法，将队列 Q 中的所有元素逆 置。 函数有： 栈的 ADT 函数有： void MakeEmpty(Stack &S) 置空栈 bool Push(Stack &S,DataType e) 新元素 e 进栈，入栈成功返回 TRUE，否则返回 进栈， ，否则返回 FALSE DataType Pop(Stack &S ) 出栈，返回栈顶值 否则返回空值 出栈，返回栈顶值,否则返回空值 bool isSEmpty(Stack S) 判栈空否 若空返回 TRUE，否则返回 FALSE 判栈空否,若空返回 ， 函数有： 队列的 ADT 函数有： bool EnQueue(Queue &Q, DataType e) 元素 e 进队，入队成功返回 TRUE，否则 进队， ， 返回 FALSE DataType DeQueue(Queue &Q) 出队列， 出队列， 若队列非空返回队头值 返回队头值, 若队列非空返回队头值 否则返回空值 bool isQEmpty( Queue Q ) . 判队列空否。若空返回 TRUE，否则返回 FALSE 判队列空否。 ，
D．2 ．
k-1
-1
学号
11． 个小村庄， 现要为他们建成能互相通信的网， 并且总的花费最少， 11．边远山区的 N 个小村庄，现要为他们建成能互相通信的网，并且总的花费最少， 这可以归结为什么问题（ 这可以归结为什么问题（ ） A 最短路径 B 关键路径 C 拓扑排序 D 最小生成树 个顶点的无向 无向图用邻接矩阵 表示时， 的度是（ 12．当一个有 n 个顶点的无向图用邻接矩阵 A 表示时，顶点 Vi 的度是（ 。 ）
条边的无向图的邻接表的表示， 5. 对于一个具有 n 个顶点 e 条边的无向图的邻接表的表示，则表头向量大小为 ______，邻接表的边结点个数为______ ______。 ______，邻接表的边结点个数为______。
个结点， 个叶子结点， 6．设一棵完全二叉树具有 1000 个结点，则此完全二叉树有 个叶子结点，有 的结点， 个结点只有非空左子树， 个结点只有非空右子树。 个度为 2 的结点， 有 个结点只有非空左子树， 有 个结点只有非空右子树。
1 2 5 6 9 7 3 8 4
学号
七、设散列表的长度 m = 13；散列函数为 H (Key)＝Key MOD m，给定的关键码序 13； (Key) ey 列 为 19, 14, 23, 01, 68, 20, 84, 27, 55, 11 ， 试 画 出 用 线 性 探 查 法 Hi=(H(K m，i=1,2,……k(k≤ 1)）解决冲突时所构造的散列表。 （Hi=(H(Key)+di)MOD m，i=1,2,……k(k≤m-1)）解决冲突时所构造的散列表。 并求出在等概率的情况下，这种方法的搜索成功时的平均搜索长度。 并求出在等概率的情况下，这种方法的搜索成功时的平均搜索长度。 （构造出散列表 7 分，求出其搜索成功时的平均搜索长度 4 分，共计 11 分）