考场： 座位号： 专业名称：
装订线 装订线 装订线
第 20XX-20XX 学年第 X 学期考试卷
课程代码： SS1005 课程名称： 数据结构与算法
考试时间： 90 分钟 考试形式： 闭卷 试卷类型： A 学分： 4
一、 单项选择题（共15小题，每小题2分，共30分）在每小题列出的
选项中只有一个选项符合题目要求，将正确选项前的字母填写在答题纸上。
1. 数据三种最主要的逻辑结构是树形结构和（ ）。
A. 线性表、二叉树 B. 线性结构、图状结构
C. 线性表、图
D. 树形结构、堆
2. 以下数据结构中，（ ）是线性数据结构。
A ．树
B ．图
C ．堆
D ．栈 3. 下面关于线性表的叙述中，错误的是哪一个？（ ）
A ．若线性表采用顺序存储结构，则必须占用一片连续的存储单元。
B ．若线性表采用顺序存储结构，则便于进行插入和删除操作。
C ．若线性表采用链接存储结构，则不必占用一片连续的存储单元。
D ．若线性表采用链接存储结构，则便于插入和删除操作。
4. p 是指向单链表头结点的指针，若该链表是空表，下面正确的说法是( )。
A. p = = NULL
B. p != NULL
C. p->next = =NULL
D. p->next = =NULL
5.在指针p指向单链表结点之后插入s所指结点的操作是：（）。
A．p->next=s; B．s->next=p->next ;p->next=s; C．s->next=p;
D．s->next=p->next;
6.存取数据时采用先进先出的原则的数据结构是（）。
A.队列
B.栈
C.字符串
D.线性表
7.假定栈用单链表的存储结构表示，栈的栈顶指针为top，当结点x入栈时执行的
操作为( )。
A.x->next=top;
B. top->next=x; top=x;
C. top=x;
D. x->next=top; top=x;
8.队列的数据出队操作在（）进行。
A.队尾位置
B.队头位置
C. 任意位置
D. 中间位置
9.树的度是指（）。
A.树的结点数
B.树的后继个数
C. 树中任一结点最大的后继数
D. 以上都不是
10.具有8个叶子结点的二叉树中有（）个双支结点。
A．7 B．8 C．9 D．10
11.下面对完全二叉树描述正确的是（）。
A.所有层的结点数都必须是满的
B.除最后一层，其它层上的结点数都必须
是满的
C.最后一层的结点数不能是满的
D.以上都不是
12.将100个元素散列到10000个单元的散列表中，则（）产生冲突。
A.一定会
B. 一定不会
C. 仍可能会
13.假定利用数组a表示一个栈，用top 保存栈顶位置，top=-1表示栈空，已知栈
中有数据，当元素x进栈时的操作为（）。
A.a[--top]=x;
B.a[top--]=x;
C. a[++top]=x;
D. a[top++]=x;
14.n个顶点的无向图，至多有（）条边。
A．n-l B．n(n-1)/2 C．n(n+l) D．2n
15.无向图G=(V,E),其中：V={a,b,c,d }, E={(a,b), (a,c),(b,d),(c,d)}，对该
图进行广度优先遍历，得到的顶点序列正确的是（）。
A．a,c,b,d B．a,d,c,b C．a,c,d,b D．a,b,d,c
第 2 页共4 页
考场： 座位号： 专业名称：
学号： 姓名：
装订线 装订线 装订线
二、填空题（每空2分，共20分）答案写在答题纸上
1．
2．
直接前驱
3．
4．
int i=0;s=0;n=300; do {
i=i+1; s=s+10*i;
}
while( i<n && s<n);
5．采用顺序存储结构的线性表中，表的长度为n ，删除线性表中第i 个元素（1<=i<=n ）一个元素时，需向前移动____n-i+1______个元素。
6． 在二分（折半）查找算法的前提条件是查找表中的数据必须是序 。
7． 表达式a / (b+c)*d 对应的后缀表达式是 a b c +*d- 。
8． 写出下面二叉树的后序遍历结果 DBFGCA 。
三、简答题（4小题，共30分）将答案写在答题纸上
1． 设对数据A B C D 执行一系列的进出操作，若数据出栈的顺序是 B A C D ，写出相
应的数据进出栈的操作顺序。
（6分）
2．已知一组数据的排序码为：｛46，53，40，38，74，16，88｝，要求排序后数据从小
到大升序排列，写出利用简单选择排序的方法排序时经过3趟排序后的结果。
（8分）3．画出下面图所对应的邻接矩阵（8分）
4．设给定关键字输入序列为（48，27，61，95 ,38）,散列表的存储地址范围是0～10，如采用开放地址法线性探查法解决冲突。
（8分）
a.设计合理的散列函数；
b.构造出包含给定关键字的散列表。
四、设计题（共2小题，共20分）将答案写在答题纸上
1．已知数组A 和数组B中的数据分别是有序，编写算法将数组A和B中的数据合并到数组C中，并保证C中的数据也是有序的，用文字描述算法执行的步骤。
(10分) 2．设计函数Node * GetMin(Node *Head)，Head接收链表的头结点，在传入的链表中
查找最小值的结点并返回其地址，如是空链表则返回空值0。
(10分)
其中结点的类型声明如下：struct Node{ int data; Node *next; };
第 4 页共4 页。