数据结构与算法分析习题及参考答案(3)

} (1) 指出该算法的功能； (2) 该算法的时间复杂度是多少？ 2. 写出下述算法的功能： void AJ(adjlist GL, int i, int n) { Queue Q; InitQueue(Q); cout<

while(!QueueEmpty(Q)) { int k=QDelete(Q); edgenode* p=GL[k]; while(p!=NULL) { int j=p->adjvex; if(!visited[j]) { cout<next; } } } 五、 算法填空（共8分）

如下为二分查找的非递归算法，试将其填写完整。 Int Binsch(ElemType A[ ],int n,KeyType K) {

int low=0; int high=n-1;

while (low<=high) {

int mid=_______________________________；

if (K==A[mid].key) return mid; //查找成功，返回元素的下标

else if (K<[mid].key)

______________________________________; //在左子表上继续查找

else __________________________________; //在右子表上继续查找

}

return -1; //查找失败，返回-1 } 六、 编写算法（共8分）

11

HL是单链表的头指针，试写出删除头结点的算法。 ElemType DeleFront(LNode * & HL)

模拟试卷三参考答案

一、 单选题（每题2分，共20分）

1.B 2.A 3.B 4.C 5.D 6.B 7.D 8.A 9.D 10.C 二、 填空题（每空1分，共26分） 1. 联系 图（或图结构） 2. 尾 首 3. top==0

4. O（1） O（n） 5. 128 44 108 6. 3 3

7. 有序 n-1

8. 有序序列 后缀表达式（或逆波兰式） 6 5 5 9. 2n n-1 n+1

1 5 1 3 2 -1 10. 2i+1 2i+2 (i-1)/2 4 5 -2 11. 开放定址法 链接法 5 1 5 12. 快速 归并 6 3 7 三、 运算题（每题6分，共24分）

图7 1. （1） ((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7)) (3分)

（2） 三元组线性表的顺序存储表示如图7示。 2. 如图8所示。

图8

3. DFS：?????

BFS：?????

4. 拓朴排序为： 4 3 6 5 7 2 1 四、 阅读算法（每题7分，共14分） 1. (1) 判断n是否是素数（或质数） （2）O（n）

2. 功能为：从初始点vi出发广度优先搜索由邻接表GL所表示的图。 五、 算法填空（8 分）

(low+high)/2 high=mid-1 low=mid+1 六、 编写算法（8分）

ElemType DeleFront(LNode * & HL) {

if (HL==NULL){

12

cerr<<\空表\exit(1); }

LNode* p=HL; HL=HL->next;

ElemType temp=p->data; delete p; return temp;

}

模拟试卷四

一、 单选题（每题 2 分，共20分） 1. 以下数据结构中哪一个是线性结构？( )

A. 有向图 B. 栈 C. 二叉树 D. B树

2. 若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采

用( )存储方式最节省时间。

A.单链表 B.双链表 C.带头结点的双循环链表 D.单循环链表

3. 以下哪一个不是队列的基本运算？（ ）

A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值

4. 字符A、B、C、D依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以

组成( )个不同的字符串？

A.15 B.14 C.16 D.21

5. 由权值分别为4,7,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。

A． 11 B.37 C. 19 D. 53

以下6-8题基于下面的叙述：若某二叉树结点的中序遍历的序列为A、B、C、D、E、

F、G，后序遍历的序列为B、D、C、A、F、G、E。 6. 则该二叉树结点的前序遍历的序列为( ).

A. E、G、F、A、C、D、B B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. E、G、A、C、D、F、B 7. 该二叉树有（ ）个叶子。

A．3 B.2 C.5 D.4 8. 该二叉树的按层遍历的序列为( )

A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F

C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9. 下面的二叉树中，( )不是完全二叉树。

13

10. 设有关键码序列(q，g，m，z，a)，下面哪一个序列是从上述序列出发建的小根堆的结

果?( )

A. a，g ，m，q， z B. a，g ，m，z,q C. g ，m，q，a，z D. g， m， a，q，z 二、 填空题（每空1分，共26分）

1. 数据结构是指数据及其相互之间的______________。当结点之间存在1对N（1：N）

的联系时，称这种结构为_____________________。

2. 一个广义表中的元素分为________元素和________元素两类。

3. 对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_________，

在表尾插入元素的时间复杂度为____________。 4. 向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是_________________;

删除一个结点时，需要执行的操作是___________________________（假设栈不空而且无需回收被删除结点）。

5. 栈又称为_______________表，队列又称为___________表。 6. 在稀疏矩阵所对应的三元组线性表中，每个三元组元素按_________为主序、_________

为辅序的次序排列。

7. 若一棵二叉树中只有叶子结点和左、右子树皆非空的结点，设叶结点的个数为K，则左、

右子树皆非空的结点个数是________。

8. 以折半（或二分）查找方法从长度为8的有序表中查找一个元素时，平均查找长度为

________。

9. 表示图的三种常用的存储结构为_____________、____________和_______________。 10. 对于线性表（78，4，56，30，65）进行散列存储时，若选用H（K）=K %5作为散列

函数，则散列地址为0的元素有________个，散列地址为4的有_______个。

11. 在归并排序中，进行每趟归并的时间复杂度为______，整个排序过程的时间复杂度为

____________，空间复杂度为___________。

12. 在n个带权叶子结点构造出的所有二叉树中，带权路径长度最小的二叉树称为

________。WPL称为_____________________。

13. 在索引表中，若一个索引项对应主表的一个记录，则此索引为__________索引 ，若对

应主表的若干条记录，则称此索引为________索引。 三、 运算题（每题 6 分，共24分） 1. 写出下列中缀表达式的后缀形式：

（1） 3X/(Y-2H)+1 （2） 2+X*(Y+3)

2. 假定一棵二叉树广义表表示为a(b(c),d(e,f))，分别写出对它进行先序、中序、后序、按

层遍历的结果。 先序： 中序： 后序：

14

按层： 3. 已知一个无向图的顶点集为{a, b, c, d, e} ,其邻接矩阵如下所示

a b c d e

?01001??10010????00011???01101????10110??

(1) 画出该图的图形；

（2）根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。

4. 已知一个图的顶点集V和边集E分别为：

V={0,1,2,3,4,5,6,7};

E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10, (4,6)4,(5,7)20};

按照普里姆算法从顶点0出发得到最小生成树，试写出在最小生成树中依次得到的各条边。 四、 阅读算法（每题7分，共14分） 1. void AE(Stack& S){ InitStack(S); Push(S,3); Push(S,4); int x=Pop(S)+2*Pop(S); Push(S,x); int i,a[5]={2,5,8,22,15}; for(i=0;i<5;i++) Push(S,a[i]); while(!StackEmpty(S)) cout<

该算法被调用后得到的输出结果为：

2. int akm ( unsigned m, unsigned n ) { if ( m == 0 ) return n+1; else if ( n == 0 ) return akm ( m-1, 1 ); else return akm ( m-1, akm ( m, n-1 ) ); }

该函数执行的功能是什么？ 五、 算法填空（共8分） 二叉搜索树的查找——非递归算法

bool Find(BTreeNode* BST,ElemType& item)

{while(BST(!=NULL){

if (item==______________){ item=BST->data;//查找成功 return true;}

else if(itemdata)

15