数据结构试卷（07计应考查）答案

数份卷试 ：号学 题 答： 名得姓 不 内 线 ：封级 班密业专 系程工与学科机算计 ：称名部系

数据结构 试卷 A卷

考试方式：闭卷 本试卷考试分数占学生总评成绩的 70 % 题号 一 二 三 四 五 六 七 总分 核分人 得分 密

复查总分 总复查人 得分 评卷人 一、填空题（本题15分，每空1分）

1．数据结构是指组成数据的元素之间的结构关系。最常见的数据结构形式有 线性 结构、 树状 结构和 图 结构。

2．栈的特点是 后进先出或先进后出 ，队列的特点是 先进先封

出 ，栈和队列都是操作受限的线性表。

3．对矩阵采用压缩存储的目的是为了 为了节省存储空间 。 4．深度为6的完全二叉树至少有 32 个结点。 5．二叉排序树的 中序 序列是非降序列。

6．在进行算法性能分析时， 时间性能 和 空间性能 是衡量算法的主要 性能指标。

7．按照所涉及的存储设备的不同，排序分为 内部排序 和 外部排序 两 大类。

8．在n个顶点的有向图G中，则最多有 n(n-1) 条边。

9．在各种查找方法中，其平均查找长度与结点个数n无关的查找方法是 散列函数线

查找 。

10．图的存储结构主要有邻接矩阵和 邻接表 。 得分 评卷人 二、单选题(本题20分，每小题2分)

1、 1 、按照二叉树的定义，具有3个结点的二叉树有( C )种。 A)3 B)4 C)5 D)6

《数据结构》试卷 2、带头结点的单链表head为空的判断条件是( B )

A) head=NIL B) head->next=NIL C.)head->next=head D) head< >NIL 3、n个顶点的无向完全图中含有边的数目为(C )

A）n-1 B）n C）n(n-1)/2 D）n(n-1) 4、深度为5的二叉树至多有( C )个结点。 A) 16 B) 32 C)31 D)10 5、栈和队列的共同特点是( C )。

A)都是先进后出 B)都是先进先出 C)只允许在端点处插入和删除元素 D)没有共同点

6、设有四个元素A、B、C和D依次进栈，在进栈过程中可以出栈，下列出栈序列中正确的是( B )

A) CABD B) ACDB C) DABC D) BDAC 7、下面的二叉树中，( C )不是完全二叉树

8、设有6个结点的无向图，该图至少应有( A )条边才能确保是一个连通图。 A)5 B)6 C)7 D)8 9、下列有关线性表的叙述中，正确的是（A ） A)线性表中的元素之间是线性关系 B)线性表中至少有一个元素

C)线性表中任何一个元素有且仅有一个直接前趋 D)线性表中任何一个元素有且仅有一个直接后继A

10 、某个数组第一元素的存储地址为100，每个元素的长度为2，则第五个元素的地址是( B )。

第 1 页 共 3 页

A)110 B)108 C)100 D)120

得分 评卷人 三、判断题（本题10分，正确的打“√”，错误的打“×”。）

（ x ） 1 、算法和程序没有区别，所以在数据结构中二者是通用的。

（ 1 ）2、在顺序表中无需为表示结点间的逻辑关系而增加存储空间。 （ x ）3、单链表中的头结点就是单链表的第一个结点。

密

（ 1 ）4、队列和栈都是运算受限的线性表。

（ x ）5、任何一棵二叉树中至少有一个结点的度为2。 （ 1 ）6、平衡二叉树中，其左、右子树深度之差的绝对值不超过1。

（ 1 ）7、给出不同的输入序列建造二叉排序树，可以得到不同的二叉排序树。 （ 1 ）8、一棵哈夫曼树中存在度为0、1、2的结点。 （ x ）9、插入排序是稳定的，而直接选择排序是不稳定的。

（ x ）10、对于n个记录的集合进行冒泡排序，所需要的平均时间是0(n)。 封

得分 评卷人 四、算法设计（本题10分） 假设以带头结点的单链表表示有序表L，单链表的类型定义如下： typedef struct node{ int data;

struct node *next; }LinkNode, *LinkList;

线

设计算法删除单链表L中值为X的元素。

Void list_delete(node*L,int i) {node*u ,*p=L;int k=0;

While(k!=i-1&&p!=NULL) {P=P->next;k++;}

If(p==NULL||p->next==NULL) Error(“删除序号错”); Else{u=p->next;

p->next=u->next; delete u; }}

《数据结构》试卷

得分 评卷人 （本题20分）

五、下图所示的无向带权图G

8 3 8 7 7 4 5 8 6 8

（1）写出对图G从顶点V1出发进行深度优先搜索和广度优先搜索的遍历次序 （2）画出图G的邻接矩阵

（3）按照Kruskal算法，生成最小生成树，按生成次序画出各条边； （4）求出最小生成树的权值之和。 (1)深度优先搜索遍历：123465 广度优先搜索遍历：123456 (2)略 (3)略

（4）3+4+5+6+7=25

第 2 页 共 3 页

系部名称： 专业班级： 姓名： 学号： 密 封 线 内 不 得 答 题

得分 评卷人 （本题10分）

六、设散列函数为H(K)=K%7,采用拉链法处理冲突。将关键字序列11，27，

39，44，56，70，73，89，101，93依次存储到散列表中，试构造出该散列表，并求出在等概率情况下的平均查找长度。

11-4 39-4 27-6 44-2 56-0 70-0 73-3 89-5 101-3 93-2 （0——10） 画11个散列区间 密

略。 封

《数据结构》试卷 得分 评卷人 （本题15分）

七、对于给定的一组关键字：{50，46，12，75，50，33，88，71}，分别写出应用下列排序方法进行排序的过程。

(1) 直接插入排序 (2) 冒泡排序 (3) 归并排序

略

第 3 页 共 3 页

班级： 姓名： 学号： 密 封 线 内 不 得 答 题

本文来源：https://www.bwwdw.com/article/ngk.html