算法与数据结构试卷--福州大学

专业 学号 姓名

一、选择题（10*2%=20%）

1．代码段 for (j=1; j<=n;j++) 的时间复杂性是 B 。 for (k=n; k>=1; k/=2) count++;

A、O(n2)

B、O(nlogn)

C、O(logn) D、O(n)

2．对某个无向图的邻接矩阵来说，下列叙述正确的是 A 。

A、第i行上的非零元素个数和第i列上的非零元素个数一定相等 B、矩阵中的非零元素个数等于图中的边数

C、第i行与第i列上的非零元素的总数等于顶点vi的度数 D、矩阵中非全零行的行数等于图中的顶点数

3．循环双链表中在p所指结点之后插入结点s的操作是 D 。

A、p->next=s; s->prior=p; p->next->prior=s; s->next=p->next B、p->next=s; p->next->prior=s; s->prior=p; s->next=p->next C、s->prior=p; s->next=p->next; p->next=s; p->next->prior=s D、s->prior=p; s->next=p->next; p->next->prior=s; p->next=s

4．4个元素a1，a2，a3和a4依次通过一个栈，在a4进栈前，栈的状态如图，

，不可能的出栈顺序是 C 。

A、a4，a3，a2，a1 C、a3，a1，a4，a2

B、a3，a2，a4，a1 D、a3，a4，a2，a1

5．下列四种排序方法中，不稳定的方法是 D 。

A、 插入排序 B、冒泡排序 C、归并排序 D、选择排序 6．单个结点二叉树的高度为0，所有含有15个结点的二叉树中，最小高度是 D 。

A、6 B、5 C、4 D、3

7．在一个具有n个顶点的无向图中，要连通全部顶点至少需要 B 条边。

A、 n

B、n-1 C、n/2

D、n+1

8．快速排序法的运行效率取决于 D 。

A、要排序的数据量

B、要排序的数据中含有相同值的比例

D、划分过程的对称性

C、要排序的数据的局部有序性

9．二叉树若用顺序存储结构（数组）存放，则下列四种运算中的 C 最容易实现。

A、 先序遍历二叉树 B、判断两个结点是否位于同一层 C、层次遍历二叉树

D、根据结点的值查找其存储位置

10．模式串ABBCABABDBABBC的前缀函数为 C 。

专业

学号 姓名

A、00001212000121 B、10000120001212 C、00001212001234 D、10000120012345

二、填空题（15*2%=30%）

1、已知某棵二叉树按中序遍历所得到的结点序列为DCBGEAHFIJK，按后序遍历所得到的结点序列为DCEGBFHKJIA，该二叉树按前序遍历所得到的结点序列为ABCDGEIHFJK。 2、一个n×n的下三角矩阵A中的元素aij（i≥j，1≤i，j≤n）按行存于一个一维数组B[1..n（n＋1）/2]中，对其中的任一元素aij，若在B中的位置为k，则k＝j+(i-1)i/2。

3、设一棵完全二叉树具有988个结点，则此完全二叉树有 494 个叶子结点，有 493 个度为2的结点，有 1 个结点只有非空左子树，有 0 个结点只有非空右子树。 4、向一个有127个元素的有序线性表（数组实现）中插入一个随机的新元素并依然保持有序性，平均要移动 63.5 个元素。

5、设栈S和队列Q的初始状态皆为空，元素a1，a2，a3，a4，a5和a6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3，a5，a4，a6，a2，a1则栈S至少应该能容纳 4 个元素。

6、顺序循环队列中，设队头指针为 front ，队尾指针为rear ，队中最多可有MAX个元素， 则元素入队列时队尾指针的变化为 (rear+1)%MAX ；元素出队列时队头指针的变化为 (front+1)%MAX 。 若采用少用一个存储单元的方法区分队满与队空问题，则可用 (rear+1)%MAX==front 表示队满的判别条件。

7、在输入已经有序的情况下，整个冒泡排序算法需要执行 n(n-1)/2 次元素比较操作。 8、设一个闭散列表的容量为m，用线性探测法解决冲突，要插入一个键值，若插入成功，至多要进行 m-1 次检测。

1 0??0 ??表示一张图，如果该图是有向图，共有 4 条边；若是19、用邻接矩阵A?1 0 ???1 0??0 ?无向图，则共有 2 条边。 三、简答题（28%）

1、（5分）设下列二叉树是与某森林对应的二叉树，回答下列问题。 （1）森林中有几棵树？

（2）每一棵树的根结点标号分别是什么？ （3）每一棵树中有几个结点？ （4）森林中共有几个叶子结点？ 解答： （1）3 (2分)

专业

（2）A C F （1分） （3）6 2 3 （1分） （4）6 （1分）

学号 姓名

2、（6分）用Prim算法（初始顶点集S＝{7}）构造出下图的一棵最小生成树，请用图示法画出其构造过程。

图解：（每图1分）

5066 ① ② 4065 503 60 50 ⑦ 45 42 30 ③ 70④ ⑤ ⑦ 45 ⑥ ⑦ 45 ① ② ⑤ （1）

① ④ ② ⑤ （2）

⑦ 45 ① ④ ② ⑤ （3） ③ ⑥ ③ 42 ③ 42 30 ④ ⑥ ⑥ ① ② ⑦ 45 ① ④ ② ③ ⑦ 45 42 ① ④ ② 5066 ⑦ 45 ③ 42 ③ 42 ④ 5030 5030 40 5030 403 3 3 ⑤ ⑥ ⑤ ⑥ ⑤ （5） 4） （（6） ⑥ 3．（6分）已知序列{17，31，13，11，20，35，25，8}，请将上述序列初始建为一个极小化堆，并给出输出前两个最小关键字后重建的堆。（要求画出初始建堆和两次调整后堆的示意图）。

专业 学号 姓名

图解：

（每图2分）

4．（5分）设有一组关键字{10 100 32 45 58 126 3 29 200 400 0}，散列表大小hashSize=13，表项下标从0到12，散列函数h(x)采用先将关键码各位数字折叠相加, 再用%hashSize将相加的结果映像到表中的办法，采用二次散列技术（h2i-1(x)=|h(x)+i2|%hashsize，h2i(x)=|h(x)-i2|%hashsize解决冲突，画出相应的闭散列表，并指出每一个产生冲突的关键码分别产生了多少次冲突。

解答：（每项包括位置和冲突次数0.5分）

5．（6分）已知如图所示的有向图，请按照Dijkstra算法找出顶点A到所有其它顶点的最短路径。（要求给出具体迭代过程）

下标 0 1 2 3 4 5 6 7 8 9 10 11 12 关键字 58 10 100 3 400 32 200 45 126 29 0 冲突次数 0 0 1 0 0 0 3 0 1 0 9 专业

学号 姓名

B5A2D3762C2F1371G1E解答：（每迭代0.5分，每个顶点距离0.5分） 迭代 S 初始 A 1 2 3 4 5 6 {A,C} {A,C,B} {A,C,B,G} {A,C,B,G,E} {A,C,B,G,E,F} U - C B G E F Dist[B] 5 5 5 5 5 5 5 Dist[C] 3 3 3 3 3 3 3 Dist[D] ∞ 10 10 10 9 9 9 Dist[E] ∞ 10 8 7 7 7 7 Dist[F] ∞ ∞ ∞ ∞ 8 8 8 Dist[G] ∞ ∞ 6 6 6 6 6 {A,C,B,G,E,F,D} D A－B：5 A－C：3

A－B－G－E－D：9 A－B－G－E：7 A－B－G－E—F：8 A－B－G：6

四、程序填空题（共6分）

1、（6分）下列算法实现在中序线索二叉树中求结点p的前驱，请在空白处填入正确的语句或表达式。

ThreadedNode *Predecessor( ThreadedNode *p ) { ThreadedNode *q;

if ( （1） p->LeftThread )

return (p->LeftChild); else {

q=p->LeftChild;

while ( （2） !q->RightThread )

（3） q=q->RightChild ; return(q); }

}//Predecessor

五、算法设计题（共16分）

1、（8分）二叉搜索树预先假设搜索是基于一个关键字的。如果我们想要执行或者基于关键

专业 学号 姓名

字key1或者基于关键字key2的查找，可以使用一种类似于二叉树的结构——2-d树。但是在一棵2-d树中，偶数层用key1进行分叉，奇数层用key2进行分叉(根结点层数为0)。图中就是一棵2-d树的示例，以名（first name）和姓（last name）作为两个关键字对二战以后的美国总统进行查找。总统的姓名是按照年代顺序插入的（Truman、Eisenhower、Ford、Carter、Reagan、Bush、Clinton）。请根据上述描述，编写实现2-d树的插入操作。

算法设计思想：

从根结点开始，从上往下搜索元素X合适的插入位置，搜索过程中，记录当前结点current所在层次（根结点层次为0），若current的层次为奇数时，用key2进行比较，当current->key2>x->key2，则搜索current的左子树，否则搜索其右子树；同理，若current的层次为偶数时，用key1进行比较，当current->key1>x->key1，则搜索current的左子树，否则搜索其右子树。搜索过程中要记录当前结点current的父结点，以便找到一个空指针的时候，可以直接在这个位置插入新的结点，并将元素x存储在这个新结点中。

算法设计题酌情给分 2、（8分）现有一个计算机网络和一个双向连接表，每一个连接A－B表示文件可以在计算机A和B之间传送，如果存在M个连接和N台计算机，设计一个有效的算法帮助判定能否将一个文件从网络上任意一台计算机发送到任意的另外一台计算机上。 要求：算法时间复杂性为O(M+N)

算法设计思想：将每一台计算机视为某一张无向图G中的结点，每一个连接A－B表示结点A和B之间存在一条边。可通过图的连通性判断是否能将一个文件从网络上任意一台计算机发送到任意的另外一台计算机上。由于这样的一张图具有N个结点和M条边，为了满足时间复杂性的要求，采用邻接表的方式实现图，并对图进行深度优先搜索

也可以初始将每一台计算看成一个个独立的集合，将每一个连接A－B看成是一个等价关系，对于所有的连接进行处理，测试A和B是否处于同一个集合中，若非同一集合，则合并两个集合，当且仅当所有的计算机最终都位于同一个集合中，才能确定可将一个文件从网络上任意一台计算机发送到任意的另外一台计算机上。使用大小求并和路径压缩的方法，存在2M次Find和至多N-1次Union，实际时间复杂性可视为O(M+N)

算法设计题酌情给分

专业 学号 姓名

字key1或者基于关键字key2的查找，可以使用一种类似于二叉树的结构——2-d树。但是在一棵2-d树中，偶数层用key1进行分叉，奇数层用key2进行分叉(根结点层数为0)。图中就是一棵2-d树的示例，以名（first name）和姓（last name）作为两个关键字对二战以后的美国总统进行查找。总统的姓名是按照年代顺序插入的（Truman、Eisenhower、Ford、Carter、Reagan、Bush、Clinton）。请根据上述描述，编写实现2-d树的插入操作。

算法设计思想：

从根结点开始，从上往下搜索元素X合适的插入位置，搜索过程中，记录当前结点current所在层次（根结点层次为0），若current的层次为奇数时，用key2进行比较，当current->key2>x->key2，则搜索current的左子树，否则搜索其右子树；同理，若current的层次为偶数时，用key1进行比较，当current->key1>x->key1，则搜索current的左子树，否则搜索其右子树。搜索过程中要记录当前结点current的父结点，以便找到一个空指针的时候，可以直接在这个位置插入新的结点，并将元素x存储在这个新结点中。

算法设计题酌情给分 2、（8分）现有一个计算机网络和一个双向连接表，每一个连接A－B表示文件可以在计算机A和B之间传送，如果存在M个连接和N台计算机，设计一个有效的算法帮助判定能否将一个文件从网络上任意一台计算机发送到任意的另外一台计算机上。 要求：算法时间复杂性为O(M+N)

算法设计思想：将每一台计算机视为某一张无向图G中的结点，每一个连接A－B表示结点A和B之间存在一条边。可通过图的连通性判断是否能将一个文件从网络上任意一台计算机发送到任意的另外一台计算机上。由于这样的一张图具有N个结点和M条边，为了满足时间复杂性的要求，采用邻接表的方式实现图，并对图进行深度优先搜索

也可以初始将每一台计算看成一个个独立的集合，将每一个连接A－B看成是一个等价关系，对于所有的连接进行处理，测试A和B是否处于同一个集合中，若非同一集合，则合并两个集合，当且仅当所有的计算机最终都位于同一个集合中，才能确定可将一个文件从网络上任意一台计算机发送到任意的另外一台计算机上。使用大小求并和路径压缩的方法，存在2M次Find和至多N-1次Union，实际时间复杂性可视为O(M+N)

算法设计题酌情给分

本文来源：https://www.bwwdw.com/article/e7up.html