内容发布更新时间 : 2024/6/9 20:48:11星期一 下面是文章的全部内容请认真阅读。

装订线—————————————————————————————————————————————————————————— 2010－2011学年第一学期

计算机科学学院《数据结构》期末考试试卷（A卷）

答案与评分标准

班级： 学号： 姓名： 题号 得分 一 二 三 四 总分 签名 注：1、总分共100分，考试时间120分钟。

2、此试卷适用于09级计算机科学与技术本科专业学生。

得 分 阅卷教师 一、 填空题（本题共10小题，每个空2分，共20分）

1．数据的逻辑结构在计算机存储器内的表示，称为数据的（存储（或物理）结构）。

2．当线性表的元素总数不稳定，且经常进行插入和删除运算，应采用（ 链式（或链表） ）存储结构。

3. 求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中（ 边（e） ）的数目相关。

4．若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是（ 稳定 ）的。

5. 若s=″ABCDEFGHIJK″,t=″ABCD″,执行运算substr(s,strlen(t), strlen(t))后的返回值为（ DEFG ）。

6．已知一棵完全二叉树共有648个结点，则该树中有（ 324 ）个叶子结点。

7．树T有n个结点且结点的度均为p或者0，则树中的叶子结点总数为：（ n－(n-1)/p ） 。 8．在无向图的邻接矩阵中，第i行非零元个数就是第i个顶点的（ 度数 ）。 9．具有n个结点的二叉树，采用二叉链表存储，共有（ n+1 ）个空链域。 10．某二叉树的后序遍历序列是CDBGFEA，中序遍历序列是CBDAFGE，则其先序遍历序列是（ ABCDEFG ）。 得 分 阅卷教师 二、 选择题（本题共10小题，每个空2分，共20分）

1．分块查找方法将表分为多块，并要求（ B ） A．块内有序 B．块间有序 C．各块等长

D．链式存储

《数据结构》期末考试试卷（A卷）第 1 页 共 4 页

2．若进栈次序为a，b，c，且进栈和出栈可以穿插进行，则可能出现的出栈序列个数是（ B ）个。 A．3 B．5 C．6 D．7

3．对一棵有100个结点的完全二叉树按层序编号，则编号为49的结点，它的左孩子的编号为（ B ）

A.99 B.98 C.97 D.50 4．二维数组A[8][9]采用列优先存储方法，若每个元素各占2个存储单元，而且A[0][0]的地址为1000，则A[5][7]的地址为 （ A ）

A．1122 B．1234 C．1212 D．1120 5．下面关于B-树和B+树的叙述中，不正确的是 （ A ）

A．B-树和B+树都能支持顺序检索 B．B-树和B+树都是平衡树

C．B-树和B+树都能支持索引检索 D．B-树和B+树都可用作文件的索引结构 6．在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（ A ）

A．n2－2e B．2e C．n2－e D．e 7．用n个值构造一棵二叉排序树，它的最大高度为（ C ）

A.n/2 B.

n C. n D.log2n

8．若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是（ C ）

A．不确定 B．11 C．10 D．9 9．下面结构中最适于表示稀疏无向图的是（ C ）

A．邻接矩阵 B．逆邻接表 C．邻接多重表 D．十字链表

10. 假定一棵度为3的树中结点总数为50，则其最小高度应为（ C ） A. 3 B. 4 C. 5 D. 6

三 得 分 阅卷教师 三、问答题(本题共6小题，共40分) 1、名词解释（6分）

数据结构——相互之间存在一种或多种特定关系的数据元素的集合；。（2分）

算法——对特定问题求解步骤的一种描述，是指令的有限序列。（2分）

队列——是限定在表的一端进行插入，另一端进行删除的线性表，也称为先进先出表。

（2分）

2、已知某图的邻接表存储结构如下所示，根据该邻接表从顶点A出发，分别写出按

深度优先搜索法和广度优先搜索法进行遍历的结点序列。（6分）

《数据结构》期末考试试卷（A卷）第 2 页 共 4 页

装订线—————————————————————————————————————————————————————————

答：深度优先搜索遍历的结点序列：ABCDEFGH

广度优先搜索遍历的结点序列：ABDCEFHG

3、简述队列和栈这两种数据结构的相同点和不同点。（6分） 答：相同点：都是插入和删除运算的位置受限制的线性表。（2分） 不同点：栈是限定在表尾进行插入和删除的线性表，也称后进先出表；（2分）而队列是限定在表的一端进行插入，另一端进行删除的线性表，也称为先进先出表。（2分）

4、设字符串P=‘abaabaab’，请求出P的next值和nextval值。（8分） 解：P的next与nextval值分别为01122345（4分）和01021021（4分）。

5、有一份电文中共使用五个字符：a、b、c、d、e，它们的出现频率依次为（8、14、10、4、18），请构造相应的哈夫曼树（要求左子树根结点的权小于等于右子树根结点的权），求出每个字符的哈夫曼编码。（8分）

解：哈夫曼树为：

（3分）

相应的哈夫曼编码为： a：011； b：10； c：00； d：010； e：11（每个1分）

6、写出右图所示的有向图的所有拓扑排序序列。（6分） 解：只有： CABEDF

（多答扣2分）

《数据结构》期末考试试卷（A卷）第 3 页 共 4 页

四 得 分 阅卷教师 四、程序填空与设计题：（共2小题，共20分）

1．请填写算法中空白之处，完成其功能。（每空2分，共10分） typedef struct { // 图的定义

VertexType vexs[MAX_VERTEX_NUM]; // 顶点信息

AdjMatrix arcs; // 邻接矩阵 int vexnum, arcnum; // 顶点数，弧数 } MGraph;

//图广度优先遍历，visited为访问标志数组。

void BFSTraverse(Graph G, Status (*Visit)(int v)){

for (v=0; v

for ( v=0; v

if ( ② !visited[v] ) { visited[v] = TRUE; Visit(v);

③EnQueue(Q, v); while (!QueueEmpty(Q)) {

④DeQueue(Q, u);

for(w=FirstAdjVex(G, u); w!=0; w=NextAdjVex(G,u,w)) if ( ⑤! visited[w] ) { visited[w]=TRUE; Visit(w); EnQueue(Q, w); } // if

} // while } // for

} // BFSTraverse

2. 已知顺序表数组A[n]中的元素为整数，设计算法将其调整为左右两个部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法时间复杂度为O（n）。

解：从顺序表数组A[n]的两端向中间比较，设置两个变量i和j，初始时i＝0，j＝n-1，若A[i]为偶数并且A[j]为奇数，则将A[i]与A[j]交换。算法如下： void Adjust(int A[ ],n){ i=0;j=n-1; while(i

while(A[i]%2!=0) i++; while(A[j]%2==0) j--; if (i< j) A[i]??A[j]; } }

《数据结构》期末考试试卷（A卷）第 4 页 共 4 页