2014数据结构A卷参考答案

试卷编号 命题人： 审核人： 试卷分类（A卷或B卷） A

五邑大学 试卷及参考答案与评分标准

学期： 2013 至 2014 学年度 第 1 学期 课程：

数据结构 课程代号： 0800310

使用班级： 120109 姓名： 学号：

题号 得分

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

1． 设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2,e4,e3,e6,e5,e1，则栈S的容量至少应该是（ B ）。 A．2

B．3

C．4

D．6

一 二 三 四 五 六 七 八 九 十 总分 2． 由4个叶子结点构造一棵哈夫曼树，该树的总结点数是（ D ）。 A．4

B．5

C．6

D．7

具有n个叶子节点的哈夫曼树共有 2n-1 个结点

3． 对于长度为m（ m>1）的指定序列，通过初始为空的一个栈、一个队列后，错误的叙述是（ D ）。

A．若入栈和入队列的序列相同，则出栈序列和出队序列可能相同 B．若入栈和入队列的序列相同，则出栈序列和出队序列可以互为逆序 C．入队序列与出队序列关系为1:1，而入栈序列与出栈序列关系是1: n (n≥1) D．入队序列与出队序列关系为1: n (n≥1)，而入栈序列与出栈序列关系是1:1

第一句：入队列和出队列的是一样的，要是什么就都是什么，是1:1,一个入队列只可能对应一个出队列

第2句：一个入栈序列可能对应多个出站队列1:n

4． 在一个单链表HL中，若要删除由指针q所指结点的后继结点，则执行（ A ）。 A．p=q->next; q->next=p->next; C．p=q->next; p->next=q->next;

B．p=q->next; q->next=p;

D．q->next= q->next->next; q->next=q;

5． 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女之间不能相互继承。则表示该遗产继承关系的数据结构应该是（ B ）。 A．树

B．图

C．线性表

D．集合

6． 设数组S[n]作为两个栈S1和S2的存储空间，对任何一个栈只有当S[n]全满时才不能进行进栈操作。为这两个栈分配空间的最佳方案是（ A ）。

第 1 页 共 6 页

A．S1的栈底位置为0，S2的栈底位置为n-1 B．S1的栈底位置为0，S2的栈底位置为n/2 C．S1的栈底位置为0，S2的栈底位置为n D．S1的栈底位置为0，S2的栈底位置为1 7． 下面说法中不正确的是（ D ）。

A．对称矩阵只须存放包括主对角线在内的下（或上）三角的元素即可 B．对角矩阵只须存放非零元素即可

C．稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储

D．稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储所需空间（行，列，非零元素值）与线性表长度（下标，对应值）成正比

8． 为5个使用频率不等的字符设计哈夫曼编码，不可能的方案是（ A ）。 A．100，11，10，1，0

B．111，110，10，01，00 D．001，000，01，11，10

C．000，001，010，011，1

9． 已知一棵二叉树的结点数为n,若该二叉树无度为1的结点，则该二叉树的叶子结点数为（ Ｄ ）。 P109 二叉树的性质

A． n

B．n-1

C．(n-1)/2

D．(n+1)/2

满二叉树：叶子结点：n0=（n（结点数）+1）/ 2 二叉树：叶子结点：n0 度为2的节点：n2 则：n0=n2+1

10． 求单源最短路径的迪杰斯特拉（Dijkstra）算法是按（ Ｂ ）的顺序求源点到各顶点的最短路径的。 A．路径长度递减 二、 得分 （8分）试给出下面稀疏矩阵A的三元组表示。下标从0开始。

0 0 2 2 3 ４

5 2 4 1 3 0 ５ 1 1 8 4 3 6 ２ 5 B．路径长度递增

C．顶点编号递减

D．顶点编号递减

7（行数） 前7行：5分

6（列数） 后3行：3分

7（非零个

数） 三、 得分 （8分）已知一个连通图如图1所示，试给出图的邻接矩阵示意图，若从顶

点v1出发对该图进行遍历，分别给出基于存储结构的深度优先遍历的顶点序列和广度优先遍历的顶点序列。

第 2 页 共 6 页

?0?1???0 ??1?0???1arc[6][6]= 图1

10111?0??0??? 1?11100??00100??010011000111V[6]={v1,v2,v3,v4,v5,v6} DFS: v1 v2 v3 v5 v4 v6

BFS: v1 v2 v4 v6 v3 v5 各2分 四、 得分 (8分) 图2是一个无向网图，请按Kruskal算法，给出求最小生成树的过程。

图2

解：

adebad1bad1bad31bcfcefce2fce2f

（a） 初始状态 (b) 边(b,d)加入 (c) 边 (e,f)加入 (d) 边(a,c)加入

ad31b5a35dfe1b5ce2c2f

(e) 边(b,f)加入 (f) 边(a,b)加入 (a)和(d)2分，其余各步个1分 五、 得分 （8分）试由权值为 29、12、15、6、23 的五个叶子结点构造一棵哈夫曼树，

并求其带权路径长度WPL。 解：

61215232915182329232933126第 3 页 共 6 页 1518612

335285

写出结果4分，前面4

52151823122933步每步1分

29615182312

得分 六、

6（8分）已知模式T=”abaabcab”,求其对应的next[0..7]的值。

next

0 1 2 3 4 5 6 7

-1

一个1分

0011201

七、

得分 （8分）为便于存储和处理一般树结构形式的信息，常采用孩子—兄弟表

示法将其转换成二叉树（左孩子关系表示父子、右孩子关系表示兄弟），将下图所示的树转换成对应的二叉树是。

111232342734546756567 图3 (a) 加线 (b) 去线 (c) 层次调整 直接写出结果4分 前2步每步2分

八、 得分 （8分）已知某二叉树的中序、层序序列分别为DBAFCE、FDEBCA，请

构造该二叉树，并给出该二叉树的后序序列。 评分：二叉树构造：5分，后序遍历序列：3分 二叉树如下所示；后序序列：ABDCEF

第 4 页 共 6 页

九、 得分 （8分）用容量为n的顺序表（n：0~3）表示一个循环队列Q，Q.front

为队头元素的前一个位置，Q.rear为队尾元素位置，填写循环队列Q在下列运算中队列头和尾变化的情况。

初始状态 E1进队（队尾rear+1） 出队（队头rear+1） E2进队 E3进队 出队 E4进队（循环：01230） Q.front 0 0 1 1 1 2 2 Q.rear 0 1 1 2 3 3 0

十、 得分 算法设计题 （2小题，每小题8分，共16分） 1．设一个二叉树以二叉链表为存储结构，结点结构为： struct node { int data;

struct node lchild,rchild; };

设计算法按前序遍历次序输出二叉树中的叶子结点。 int PreOrder(BiNode *root) //root为根结点 { if(root==NULL) return 0; else { if(root->lchild==NULL && root->rchild==NULL) return 1; else return PreOrder(root->lchild)+PreOrder(root->rchild); } }

2．设单链表的结点结构如下：

template struct Node{ T data; Node *next; };

设计算法，统计带头结点的单链表HL中结点值为数字字符的结点个数。 int statsNN(Node *HL) {

第 5 页 共 6 页

Node *p=HL->next; int count=0; while(p) { if(p->data>=’0’ && p->data<=’9’) count++; p=p->next; }

return count;}

第 6 页 共 6 页