第3部分 模拟试题及参考答案(3)

第3部分 模拟试题及参考答案 ·11·

法查找一个与k相等的元素，比较次数分别是s和b，在查找不成功的情况下，正确的s和b的数量关系是( )。

A) 总有 s＝b B) 总有s＞b C) 总有 s＜b D) 与k值大小有关 7．链表不具有的特点是( )。 A) 插入删除不需要移动元素 B) 可随机访问任意元素 C) 不必要先估计存储空间 D) 所需空间与线性长度成正比

8．一组记录的关键码为(46,79,56,38,40,84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为( )。

A) (38,40,46,56,79,84) B) (40,38,46,79,56,84) C) (40,38,46,56,79,84) D) (40,38,46,84,56,79)

9．下面关于哈希(HASH)查找的说法正确的是( ) 。

A) 哈希函数构造的越复杂越好，因为这样随机性好，冲突小 B) 不存在特别好与坏的哈希函数，要视情况而定 C) 除留余数法是所有哈希函数中最好的

D) 若在哈希表中删除一个元素，不管用何种方法解决冲突都只要简单地将元素删去即可 10．下列关于AOE网的叙述中，不正确的是( )。 A) 关键活动不按期完成就会影响整个工程的完成时间

B) 任何一个关键活动提前完成，那么整个工程将会提前完成 C) 所有的关键活动提前完成，那么整个工程将会提前完成 D) 某些关键活动提前完成，那么整个工程将会提前完成 二、填空题(20分)

1．在二叉树中，指针p所指结点为叶子结点的条件是_____________。

2．已知一无向图G =(V,E)，其中V={a,b,c,d,e} E={(a,b),(a,d),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abedc，则采用的是_____________遍历方法

3． 设G为具有N个顶点的无向连通图，则G中至少有____________条边。

4．设有N个结点的完全二叉树顺序存放在向量A[1..N]中，其下标值最大的分支结点为____________。

5． 设循环队列存放在向量sq.data[0..M-1]中，则队头指针sq.front在循环意义下的出队列操作可表示为____________，若用牺牲一个单元的办法来区分队满和队空(设队尾指针为sq.rear)， 则队满的条件为____________。

6．在有序表A[1..20]中，按二分查找方法进行查找，查找长度为5的元素的下标从小到大依次是____________。

7．当一个AOV网用邻接表表示时，可按下列方法进行拓扑排序。 (1) 查邻接表中入度为____________的顶点，并进栈。 (2) 若栈不空，则

① 输出栈顶元素vj，并退栈；

② 查vj的直接后继vk，对vk入度处理，处理方法是____________

(3) 若栈空时，输出顶点数小于图的顶点数，说明有__________，否则拓扑排序完成。

三、应用题(30分)

1．已知一棵二叉树的中序(或中根)遍历结点排列为DGBAECHIF，后序(或后根)遍历结点排列为

·12· 数据结构简明教程（C语言描述）

GDBEIHFCA。

(1) 试画出该二叉树。

(2) 试画出与(1)中二叉树对应的森林。

2．下图所示是一棵正在进行插入运算的AVL树，关键码70的插入使它失去平衡，按照AVL树的插入方法，需要对它的结构进行调整以恢复平衡。请画出调整后的AVL树。

100 60 40 80 120 70

3．已知有向图如下所示。

(1) 给出其邻接表表示和逆邻接表表示。

(2) 判断该有向图是否含有强连通分量，若有，请将它们画出来。

4．假设用于通讯的电文仅有6个字母(A,B,C,D,E,F)组成，字母在电文中出现的频率分别为(7,19,5,16,42,11)。试为这6个字母设计哈夫曼编码。

5．计算下列AOE网中各顶点所表示的事件的发生时间ve(j)、vl(j)和各边所表示活动的开始时间e(i)和l(i)，并找出其关键路径。

其中：

a1=2 a6=4 a2=3 a7=6 a3=3 a8=2 a4=5 a9=3 a5=9

6．判断以下序列是否为堆，如果不是，则把它调整为堆。 (1) (12,24,33,65,33,56,48,92,86,70)

(2) (25,56,20,23,40,38,29,61,35,76,28,100) 四、算法设计题(30分)

1．假设二叉树采用二叉链表存储结构，设计一个算法，求二叉树中指定结点x的层数。

2．设有两个栈S1和S2均采用顺序栈方式，并且共享一个存储区[0..M﹣1]，为了尽量利用空间，减少溢出的可能，可采用栈顶相向、迎面增长的存储方式。试设计算法，实现S1和S2的入栈和出栈运算。

3．设图用邻接矩阵表示，写出求从指定顶点到其与各顶点的最短路径的迪杰斯特拉算法。

第3部分 模拟试题及参考答案 ·13·

模拟试题1参考答案

一、选择题(20分) 1~5 6~10

A D

B D

C C

A B

C B

二、填空题(20分)

l．(n﹣2)(n+3)/2 2．n0=n2+1 3．3 4．n1﹣1 5．50 6．直接插入排序和冒泡排序 三、判断题(10分) 1．× 6．√

2．× 7．√

3．√ 4．√ 5．× 8． × 9．× 10．√

1

n2+n3 4

4

四、应用题(20分) 1．参考答案：

0 1 2 3 4

5 6 7

8 9 10

30 53 ^ 41 ^ 13 46 ^ 22 ^ 01 67 ^

2．参考答案：

·14· 数据结构简明教程（C语言描述）

3．参考答案：

4．参考答案： (1)

(2) 带权路径长度269

5．参考答案： (1) ABCDEG (2) ABCEDG

6．参考答案：

01 14 21 19 66 23 83 27 56

A B C D E F G

100 40 60 20 20 30 30 8 12 12 18 5 7 3 4

第3部分 模拟试题及参考答案 ·15·

五、算法设计题(30分) 1．算法代码：

int flag=1; int max;

void sortBiTree(BiTree T){ if(T) {

sortBiTree(T->lchild); k++; if(k==1)

max=T->data; else{

if(T->data>max) max=T->data; else flag=0; }

sortBiTree(T->rchild); } }

2．算法代码：

int pathed[MAX_VERTEX_NUM]; int top=0;

int path[MAX_VERTEX_NUM];

int ispath(ALGraph graph,int vi,int vj){ ArcPtr p; int j;

pathed[vi]=1; path[++top]=vi;/*将顶点vi加入当前路径path */ if(path[top]==vj) /*存在顶点vi到顶点vj的路径*/ return 1;

else /*将顶点vi的邻接点加入当前路径*/ for(p=graph.vertices[vi].firstarc;p;p=p->nextarc) if(!pathed[p->adjvex]) return ispath(graph,p->adjvex,vj); pathed[vi]=0; top--; /*将顶点vi从当前路径path中删除 */ if(top==0) return 0 …… 此处隐藏：1622字，全部文档内容请下载后查看。喜欢就下载吧 ……