数据结构13级期中考试参考答案

五邑大学 试 卷（期中参考答案）

课程：

数据结构

学期： 2014 至 2015 学年度 第 2 学期

一、单项选择题（10小题，每小题2分，共20分）

1．若一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n ，则第i个输出元素是（ D ）。 A．不确定 A．顺序表 A． 7

B．n-i B．栈

C．n-i-1 C．队列

D．n-i+1 D．链表

2．设计一个判别表达式中左右括号是否配对的算法，采用（ B ）数据结构最佳。 3．设有6个结点的无向图，该图至少应有（ C ）条边才能确保是一个连通图。

B. 6

C. 5

D. 4

D．散列存取 D．O(nlog2n)

4．线性表的顺序存储结构是一种（ A ）的存储结构。

A．随机存取 A．O(1)

B．顺序存取 B．O(n)

C．索引存取 C．O(n2)

5．对于n个元素组成的线性表，建立一个有序单链表的时间复杂度是（ C ）。 6．任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序（ A ）。

A．肯定不发生改变 C．不能确定

B．肯定会发生改变 D．有时发生变化

B．从源点到终点的最短路径 D．最短的回路

7．关键路径是AOE网中（ A ）。

A．从源点到终点的最长路径 C．最长的回路 for(i=0; i

B． O(n)

C． O(log2n) C．树形结构

D． O(n2)

8．下列算法的时间复杂度是（ B ）。

9．下列四种基本的逻辑结构中，数据元素之间关系最弱的是（ A ）。 A．集合

B. 线性结构

D. 图状结构

10．在单链表中，若p所指结点不是尾结点，在p之后插入s所指结点的操作是（ B ）。

A．s->next=p; p->next=s C．s->next=p->next; p=s;

二、填空题(10小题，19个空，每空2分，共38分)

1． 表示有100个顶点，133条边的无向图的邻接矩阵有（266）个非零矩阵元素。

2． 给定一个有k个元素的有序线性表。采用顺序存储结构，在等概率前提下，插入一个元素平均需要移动（ k/2 ）个元素；而删除其中的一个元素平均需要移动（ (k-1)/2 ）个元素。 3． 含A、B、C这3个结点的不同形态的树有（2）棵，不同形态的二叉树有（5）棵。 4． 中缀表达式(66－10)／(7＋8)转换为后缀表达式（数据间用#分隔）为(66#10-7#8+/)。后缀表达式a b／c d e＋×－ 转换为中缀表达式为(a/b-c×(d＋e))。

5． 一个n阶对称矩阵，采用压缩存储，即存储其包括主对角线在内的下三角部分的数据，压缩后需要（ n(n+1)/2 ）存储单元； 一个n阶对角矩阵，其带宽为s，则矩阵中有（(n-2s)(n-2s+1)）个0元素。

第 1 页 共 3 页

B．s->next=p->next; p->next=s; D．p->next=s; s->next=p;

6． 已知一棵树T的边集为{（I,M）,（I,N）,（E,I）,（B,E）,（B,D）,（C,B）,（G ,J）,（G ,K）,（A,G）,（A,F）,（H,L）,（A,H）,（C,A）}，则该树的根结点是( C )，叶子结点共( 7 ) 个， 该树的深度为( 5 )。

7． 设待处理问题的规模为n，若一个算法的时间复杂度n×log25n, 则表示成数量级的形式为O ( nlog2n ) 。

8． 在由尾指针rear指示的单循环链表中，在表尾插入一个结点s的操作序列是 (s->next=rear->next; ) rear->next=s;和rear=s。

9． 假设以数组seq［num］存放循环队列的元素，设变量rear和qlen分别指示循环队列中队尾元素的位置和元素的个数。队满的条件表达式为（qlen == num）；当num=20，rear=12，qlen=5，队头元素的位置是（（12 - 5 + 20 ) % 20 = 7）

10． 设有无向图G，如图所示。用普里母算法构造最小生成树，在初始U={v0}情况下，选择的顶点的顺序依次为（ v0,v5,v2/v3,v3/v2,v4,v1 ）。用克鲁斯卡尔算法构造最小生成树应该选择（ 5 ）条边，所选择的边的顺序依次为( (v1,v4),(v2,v3),(v0,v5),(v2/v3,v5),(v4,v5) ）。

三、解答题(7小题，每小题6分，共42分)

1． 已知一棵二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，画出所对应的二叉树，

并给出该二叉树的前序遍历序列。

E A C B D F G 解答：前序遍历序列：EACBDGF

2． 已知一棵二叉树如下所示，画出该二叉树对应的森林。

E A C F G E G A C B D B D

F 3． 有容量为4（0~3）的循环队列Q，写出Q在下列顺序运算时队列头和尾变化的情况。

初始状态 入队 入队 入队 出队 出队 入队 Q.front 0 0 0 0 1 2 2 Q.rear 0 1 2 3 3 3 0 第 2 页 共 3 页

4． 试给出稀疏矩阵A的三元组表示。下标从0开始。

评分：三元组数据5分，总信息1分。

0 0 2 2 3 5

2 3 1 3 0 1 7 6 1 8 4 3 6 5 6

5． 已知某字符串S中共有5种字符(A，B，C，D，,E)，各种字符出现的频率分别是{15，36，

3，6，20}，建立相应的哈夫曼树，并计算其WPL。 哈夫曼树：4分 WPL：2分

WPL=36+40+45++36=157

6． 已知某图的邻接表如下：

（1） 分别给出从A、B点出发进行广度优先搜索的序列。 （2） 画出该图。

解答：(1) 分别给出从A、B点出发进行广度优先搜索的序列。

A： A B C D B： B A C D (2) 对应的图如下： （2分）

7． 现有一个用顺序表data[MAX_SIZE]表示的栈，栈顶位置用top表示。请设计一个 压栈算

法Push( DataType x)。

void Push ( DataType x) {

if (top == MAX_SIZE-1) throw “溢出”; top++;

data[top] = x; }

第 3 页 共 3 页

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新幼儿教育数据结构13级期中考试参考答案 全文阅读和word下载服务。