《数据结构与算法》试卷与答案5

课程 数据结构与算法 考试形式（闭卷，考试）

信息学院 系 专业 级 班 学号： 姓名： 题次 分数 评分 一、

填空题：（每空2分，共20分）

1．具有10个顶点的无向图，边的总数最多为 。

2. 设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有 个结点。 3．设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a85的地址为 。

4．如果结点A有3个兄弟，而且B是A的双亲，则B的度是 5．一个无序序列可以通过构造一棵 树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。 6． 法构造的哈希函数肯定不会发生冲突。

7. 求从某源点到其余各顶点的Dijkstra算法，当图的顶点数为10，用邻接矩阵表示图时计算时间约为10ms，则当图的顶点数为40时，计算时间为 ms 8. 设一棵后序线索树的高度是50，结点x是树中的一个结点，其双亲是结点y， y的右子树高度是31，x是y的左孩子，则确定x的后继最多需经过 个 中间结点（不含后继及x本身）

9．对于单向链表，在两个结点之间插入一个新结点时需修改的指针

共有 个。

一 20 二 10 三 10 四 30 五 20 六 10 总分 100 评卷人 10 .有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100}，当用折半法查找值为

1

82的结点时，经过 次比较查找成功。

二、单项选择题（每题1分，共10分）

1. ( )在一个长度为n的顺序表中向第i个元素（0A. n-i B. n-i+1 C. n-i-1 D. i

2. ( ) 设有一个栈，元素的进栈次序为A，B，C，D，E，下列( )是不可能的出栈序列

A. A，B，C，D，E B. B，C，D，E，A C. E，A，B，C，D D. E，D，C，B，A

3. ( ) 具有842个结点的完全三叉树，其叶子结点共有（ ）个

A. 421 B. 422 C.420 D.423 E.以上都不是

4.（ ）顺序查找方法适用于存储结构为（ ）的线性表 A. 压缩存储 B. 散列存储 C. 顺序存储 D. 链式存储 E 以上都不是

5.（ ）以下序列不是堆的是（ ）

A．（100，85，98，77，80，60，82，40，20，10，66） B. （100，98，85，82，80，77，66，60，40，20，10） C．（10，20，40，60，66，77，80，82，85，98，100） D．（100，85，40，77，80，60，66，98，82，10，20）

6．（ ）如果要求一个线性表既能较快地查找，又能适应动态变化的要求，则

2

可采用的查找方法是（ ）

A．分块查找 B. 顺序查找 C. 折半查找 D. 基于属性 7. （ ）一棵有n个结点的二叉树，按层次从上到下，同一层从左到右的顺序存储在一维数组A[1...n]中，则二叉树中第i个结点（i从1开始用上述方法编号）的右孩子在数组A中的位置是（ ）

A. A[2i] (2i<=n) B.A[2i+1] (2i+1<=n) C. A[i/2] D.条件不充分，无法确定

8．（ ）有数据{53，30，37，12，45，24，96}，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，则应选择下面哪个序列输入（ ） A. 45，24，53，12，37，96，30

B. 37，24，12，30，53，45，96 C. 12，24，30，37，45，53，96 D. 30，24，12，37，45，96，53

9．( )在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是( )

A. G中有弧 B.G中有一条从Vi到Vj的路径 C. G中没有弧 D. G中有一条从Vj到Vi的路径

10. ( )设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n，森林F中第一棵树的结点个数是( )

A. m-n B. m-n-1 C. n+1 D. 条件不足，无法确定

三、判断题（在括号内填上“√”或“╳”，每题1分，共10分，做错不倒扣）

1 （ ）在栈空的情况下，不能做退栈运算，否则产生下溢。

2 ( ) 任何一棵前序线索二叉树，都可以不用栈实现前序遍历。

3 （ ）就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大 4 （ ）用Shell方法排序时，若关键字的排列杂乱无序，则效率最高。 5 （ ）在任何条件下，快速排序的效率总是最好的。 6 （ ）两叉树是树的一种特殊情况。 7 （ ）N个顶点的图至少含有N-1条边

8 （ ）拓扑排序是判断一个有向图是否存在回路的唯一方法。

9 （ ）在一棵二叉排序树T中，先删除结点N，然后再插入结点N，得到新

3

的二叉排序树T1，则T和T1相同。

10 （ ）栈和队列都是存取点的线性结构。

四、画图/计算/证明 (30分)

1． 试说明一棵二叉树进行前序、中序、后序遍历，其叶结点的相对次序是否会发生改变？为什么？（5分）

2．n个结点的m叉树转化为二叉树所需存储资源比未转化前用定长结点存储节省多少？（设链域占两个单元，数据域占一个单元）（5分）

3. 已知一棵二叉树的中序遍历序列为:BAFDJGCKHLEIM，后序遍历序列为BFJGDKLHMIECA.请完成（6分） 1． 构造出这颗二叉树；

2． 画出这颗二叉树中序线索化后的结构

4

4. 对长度为8的有序表，给出折半查找的判定树，给出等概率情况下的平均查找长度。（5分）

5. (9分) 已知一个图G=(V,E)，其中V={a,b,c,d,e,f}; E={,,,,,,,,} (1) 请画出该图，并写出邻接矩阵

(2) 根据邻接矩阵，分别给出从顶点a出发的深度优先和广度优先遍历序列 (3) 画出由此得到的深度优先和广度优先生成树（或森林）

5

五. 程序填空题 （20分，每个函数5分）

1. 用链表表示数据的简单选择排序，结点的域为数据域data，指针域next，链表首指针为head，链表无头结点。 selectsort(head)

{ p=head;

while (p ) { q=p;

r= ; while ( )

{ if ( q->next->data > r->data ) q=r; r= ; }

tmp=q->data; q->data=p->data; p->data=tmp;

p= ; }

6

}

2. n个顶点的有向图用邻接矩阵array表示，下面是其拓扑排序算法，试补充完整。注：

（1） 图的顶点号从0开始计；

（2） indegree是有n个分量的一维数组，放顶点的入度； （3） 函数crein用于计算顶点的入度； （4） 有三个函数push(data)、pop( )、check( )，它们的含义为数据data进栈、

退栈和测试栈是否为空（不空返回1，否则返回0）。

# include crein (array, indegree, n) {

for (i=0; iindegree[i]= ; for (i=0; iindegree[i]+=array [ ] [ ]; }

topsort( array, indegree, n) { count= ; for (i=0; i{ k=array ; if ( ) { indegree[i]--;

if ( ) push(i); }

7

} } }

3．设顺序表la的数据结构定义如下：

typedef struct

{ Datatype list[Maxnum]; int num; } SeqList;

试将下面删除顺序表la中所有值为x的数据元素的算法补充完整。 void DeleteSeqList ( SeqList * la, Datatype x) { int j, k;

for (j=1; j<=la->num; j++) { if ( )

{for (k=j; knum; k++) ; la->num--; j--; } } }

四、编写算法（10分）

设单链表中存放着n个字符，试设计算法并判断字符是否中心对称。 例如xyzzyx和xyzyx都是中心对称的字符串。

8

试卷答案

一、 填空题：（每空1.5分，共15分） 1．45 6．直接定址 2. 2n0-1 。 7. 160 ms 3． 41 8. 31 个中间结点 4．B的度是 4 9． 2 个 5．二叉排序 10. 4 次

二、单项选择题（每题1.5分，共15分）

1. ( B )

2. ( C ) 3. E

4. C或A或D 5.（D）

6.（A） 7.（D） 8．（B） 9．( D ) 10. ( A )

三、判断题（在括号内填上“√”或“╳”，每题1.5分，共15分，做错不倒扣）

1 （√） 2 ( ╳ ) 3 （╳） 4 （╳） 5 （╳ ） 6 （√） 7 （╳） 8 （╳ ） 9 （╳ ） 10 （√ ）

9

四、画图/计算/证明/算法分析 (30分) 1．二叉树中叶结点必在某结点的左或右子树中，三种遍历方法对左右子树的遍历都是按左子树在前、右子树在后的顺序进行遍历的。所以在三种遍历序列中叶结点的相对次序是不会发生改变的。 2． 节省 n(2m+1)-5n=2n(m-2) 3. (1)．二叉树为

A

B C

D E

F G H I M

J K L

(2) (略) 4.

ASL=(1+2*2+3*4+4)/8=21/8

5. (9分) 已知一个图G=(V,E)，其中V={a,b,c,d,e,f};

E={,,,,,,,,} (1) (略)

(2) 深度优先序列：a b d e c f 广度优先序列：a b d e c f (3) 深度优先森林： 广度优先遍历森林为

a c a c

b d f b d e f

e

五. 程序填空题 （15分，每小题5分）

10

1． while (p!=NULL) r= p ; 或p->next 或q 或 q->next while (q->next!=NULL) 或 r!=NULL r=q->next; 或 r->next p=p->next; 2． indegree[i]= 0 ; indegree[i]+= [ j ] [ i ] 3． count= 0 ; if ( !indegree[i] ) k=array[vex][i]; if (k= =1) if (!indegree[i]) 4．if (la->list[j]= =x) la->list[k]=la->list[k+1];

六、编写算法（10分）

解：先将链表的前半部分倒置，与后半部分比较后再倒置。 也可以把字符串分别放入堆栈和队列，再逐一弹出进行比较。

11