数据结构2024春试题 - A卷

西北农林科技大学本科课程考试试题（卷） 2009—2010学年第2学期《数据结构》课程 A 卷

专业班级：09计算机1-3 命题教师： 审题教师： 学生姓名： 学号： 考试成绩：

一、 单项选择题（每小题 2 分，共20分） 得分： 分 1. 一个算法应该是 ( )。

A.程序 B.问题求解步骤的描述

C.要满足五个基本特性

D.A和C

2. 以下数据结构中，( )是线性数据结构。

A. 图

B. 哈夫曼树

C.森林

D.栈

3. 下面关于线性表的叙述中，错误的是( )。

A. 线性表采用顺序存储，必须占用一片连续的存储单元。 B. 线性表采用顺序存储，便于进行插入和删除操作。 C. 线性表采用链式存储，不必占用一片连续的存储单元。 D. 线性表采用链式存储，便于插入和删除操作。

4. 对于顺序存储的线性表，访问结点和删除结点的时间复杂度分别为( )。

A.O(n)和O(n)

B.O(n)和O(1) C.O(1)和O(n) D.O(1)和O(1)

5. 在单链表指针为p的结点之后插入指针为s的结点，正确的操作为( )。

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

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

6. 栈和队列的共同点是( )。 A.只允许在端点处插入和删除元素 B.都是后进先出 C. 都是先进后出 D.没有共同点

7. 某堆栈的输入序列为A,B,C,D。下面四个序列中，不可能是它的输出序列的

是( )。

A.A,C,B,D B.B,C,D,A C.C,D,B,A D.D,C,A,B 8. 在下列存储形式中，那一个不是树的存储形式( )。

第 1 页 共 6 页

A.双亲表示法 B.孩子表示法 C.孩子兄弟表示法 D.顺序存储表示法 9. 二叉树的前序遍历和中序遍历序列如下：前序遍历：EFHIGJK，中序遍历：

HFIEJKG。该二叉树根的右子树的根是( )。 A. E

B. J

C. G

D. K

10. 设如右图所示，在下面的5个序列中，符合深度优先遍

历的序列有( )个。

abef第10题图(1)a e b d f c (2)a c f d e b (3)a e d f c b (4)a e f d c b (5)a e f d b c A. 5个

B. 4个

C. 3个

D. 2个

cd二、填空题（每空1分，共20分） 得分： 分 1. 一个算法具有5个特性: 、确定性、 、 、

有零个或多个输入、有一个或多个输出。

2. 线性结构包括 、 和 等，其存储结构可分

为 和 。

3. 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最

快的速度存取线性表中的元素时，应采用 存储结构。 4. 已知一循环队列的存储空间为[m..n],其中n>m,队头和队尾指针分别为

front和rear，则此循环队列判满的条件是 。

5. 一棵有n个结点的满二叉树有 个度为1的结点， 个分

支（非终端）结点和 个叶子结点，该满二叉树的深度为 。 6. 构造连通网最小生成树的两个典型算法是 和 。 7. 直接插入排序用监视哨的作用是 。 8. 分别采用快速排序，冒泡排序和归并排序，对初始状态有序的表，最省时

间的是 ，最费时间的是 。

9. 在二叉树中，指针p所指结点为叶子结点的条件是 。 10. 某二叉树的后序遍历序列是dabec,中序遍历序列是debac,则其前序遍历序

列是 。

第 2 页 共 6 页

三、简答题（共10分） 得分： 分 线性表的两种存储结构各有哪些优缺点？

四、应用题（每小题10分，共20分）

得分： 分

1. 有一棵哈夫曼树，其结点{a,b,c,d,e,f}对应的权值分别为（5，9，11，2，7，16）

画出这棵哈夫曼树，并为这6个字母设计哈夫曼编码。

第 3 页 共 6 页

2. 已知世界六大城市为：北京（Pe）、纽约（N）、巴黎（Pa）、伦敦（L）、东

京（T）、墨西哥（M），下表给定了这六大城市之间的交通里程： 世界六大城市交通里程表（单位：百公里）

Pe N Pa L T M Pe 109 82 81 21 124 N 109 58 55 108 32 Pa 82 58 3 97 92 L 81 55 3 95 89 T 21 108 97 95 113 M 124 32 92 89 113 （1） 画出这六大城市的交通网络图。 （2） 画出该图的邻接表表示法。

第 4 页 共 6 页

五、程序设计题（每小题10分，共30分） 得分： 分

1. 带头结点的单链表有Data和Next两个域。设计一个算法，删除其重复元

素结点。

2. 写出前序遍历二叉树的算法。

第 5 页 共 6 页

3. 有n个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上

升序进行排序，请写出这种排序的算法（注：双向起泡排序即相邻两趟排序向相反方向起泡）

head

∧a1......an∧第 6 页 共 6 页

百度搜索“70edu”或“70教育网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，70教育网，提供经典综合文库数据结构2024春试题 - A卷在线全文阅读。