数份卷试 ：号学 题 答： 名得姓 不 内 线 ：封级 班密业专 系程工与学科机算计 ：称名部系
数据结构 试卷 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 页
班级： 姓名： 学号： 密 封 线 内 不 得 答 题