数据结构(c语言版)试题.doc

数据结构考试试卷 ( A )

课程名称: 数据结构（C语言） 试卷满分 100 分
考试时间: 年 月 日 (第 周 星期 )
题 号
一
二
三
四
五
六
七
八
九
十
总分
评卷得分

评卷签名

复核得分

复核签名

一、选择题(每项选择2分，共34分)
1、在数据结构中，与所使用的计算机无关的是（ D ）。
A、存储结构 B、物理结构 C、物理和存储结构 D、逻辑结构
2、可以把数据的逻辑结构划分成（ D）。
A、内部结构和外部结构 B、动态结构和静态结构
C、紧凑结构和非紧凑结构 D、线性结构和非线性结构
3、一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ B ）。
A、110 B、108 C、100 D、120
4、栈结构通常采用的两种存储结构是（ A ）。
A、顺序存储结构和链式存储结构；
B、散列方式和索引方式；
C、链式存储结构和数组；
D、线性存储结构和非线性存储结构。
5、在下列链表中不能从当前结点出发访问到其余各结点的是（ A）。
A、单链表 B、单循环链表 C、双向链表 D、双向循环链表

学 院： 专 业： 学 号： 姓 名：

装 订 线

6、在表长为n的单链表中，算法时间复杂度为O(n)的操作是（ A ）。
A、查找单链表中第i个结点。
B、在当前结点之后插入一个结点。
C、删除表中第一个结点。
D、删除当前结点的直接后继结点。
7、数组A中，每个数据元素的长度为3个字节，行下标从1到8，列下标从3到10，存放该数组至少需要的单元数是（ D ）。
A、80 B、100 C、240 D、270
8、稀疏矩阵一般的压缩存储方法有两种，即（ C ）。
A、二维数组和三维数组 B、三元组和散列
C、三元组和十字链表 D、散列和十字链表
9、广义表（a,b,c,d）的表头是（ A ）表尾是（ D）。
A、a B、b C、( a,b) D、(b,c,d)
10、已知二叉树的后序序列为fgbedca，中序序列为fbgadec则该二叉树的前序序列为（ B ），层次序列为（ C ）。
A、abcdefg B、abfgcde C、abcfgde D、fgedcba
11、某二叉树只有度为0和度为2的结点，如果该二叉树只有21个结点，则叶子结点数为（ C ）。
A、9 B、10 C、11 D、12
12、一个有n个顶点的无向图最多有（ C ）条边。
A、n B、n(n-1) C、n(n-1)/2 D、2n
13、对于一个具有n个顶点e条边的无向图，若采用邻接矩阵表示，该矩阵大小是（ D ）。
A、e2 B、n+e C、n*e D、n2
14、如果要求一个线性表既能较快的查找，又能适应动态变化的要求，可以采用（ A ）方法。
A、分块 B、顺序 C、二分 D、散列

广东工业大学试卷用纸，共 6 页，第 10 页
15、在以下排序算法中，关键字的比较次数与记录的初始排列次序无关的是（ D ）。
A、希尔排序 B、起泡排序 C、插入排序 D、选择排序
二、算法测试（共28分）
先按要求填空完成程序，再回答有关问题。
1、 （31分）设h是带表头结点的单链表的头指针，请设计一个逆置这个单链表的程序。
即原链表为(a1,a2,a3…an)，逆置后变为( an,an-1…a2,a1)。
单链表结点结构为：
typedef struct node{int data;
___ struct node *link;__（2分）}LNode;
void invert(LNode *h)
{ LNode *s,*p;
p=h->link;
h->link=___ NULL ；或者 0 ；（2分）
while(p!=NULL)
{ s=p;
p=p->link;
__ s->link=h->link;_（2分）
h->link=s;
}
}
什么是表头结点？（2分）
如果该链表无表头结点，则原程序该做怎样的修改？（4分）
2、 （13分）对以下函数填空，实现以带头结点的单链表h为存储结构的直接选择排序。单链表的结点结构定义为
typedef struct node{int key;
struct node *next;}JD;
void zjxzpx(JD *h)
{ JD *p,*q,*m;
int x;
p=h->next;
while(p!=NULL)
{ q=p->next;
m=p;
while(q!=NULL)
{ if (m->key>q->key) _________;（2分）
_____________;（2分）
}
if (p!=m)
{ x=p->key;
p->key=m->key;
m->key=x;
}
______________;（2分）
}
直接选择排序属于___________(稳定/不稳定)排序。（2分）
该排序算法总的键值比较次数为____________。（2分）
并分析什么情况下有最小移动记录次数？什么情况下有最大移动记录次数？算法的平均时间复杂度为多少？（3分 ）
3、（6分）对以下函数填空实现求中序线索二叉树中结点后继的算法。
中序线索树中结点结构定义为：
typedef struct TbTree{
int data;
struct TbTree *lchild,*rchild;
int LTag,RTag;//左右标志，0表示有子女，1表示线索指针
}TbTree；
TbTree * succ(TbTree *p) //p为指向当前结点的指针
{
TbTree *q;
if (p->RTag==1) return (___________);(2分)
else
{
q=p->rchild;
while (____________ ) q=q->left;（2分）
return(q);
}
}
在中序线索二叉树中，中序遍历访问的第一个结点左标志位（LTag）为____（1分），其lchild=________。（1分）
三、应用题（共35分）
1、（6分）已知二叉树的层次序列为ABCDEFGHIJK，中序序列为DBGEHJACIKF，请构造一棵二叉树，并写出其后序序列。
2、（10分）已知二叉树的先序、中序和后序序列如下，其中有一些看不清的字母用*表示，请先补充*处的字母，再构造一棵符合条件的二叉树（画出图示），最后画出带头结点的中序线索链表。
前序序列：*BC***G*
中序序列：CB*EAGH*
后序序列：*EDB**FA
3、（6分）将下列二叉树还原成森林，并写出先序遍历森林序列。

4、 （8分）已知图G=（V，E），其中V={a,b,c,d,e}，E={<a,b>,<a,c>,<a,d>,<b,c>,<d,c>,<b,e>,<c,e>,<d,e>}
要求：
（1） 画出图G；（2分）
（2） 给出图G的邻接矩阵；(2分)
（3） 给出图G的邻接表；（2分）
（4） 给出图G的一种拓扑序列。（2分）
5、 （2分）判断下列序列是否为大根堆 ，如果不是则把它们调整成大根堆。
{90，86，48，73，35，40，42，58，66，20}
6、 （3分）按下列输入顺序，建立相应的二叉排序树 。
（1）4，5，6 （2）5，4，6 （3）6，5，4

答案及评分标准
一、 选择题（每项选择2分，共34分，错选不给分）
1、D 2、D 3、B 4、A 5、A 6、A 7、D 8、C 9、①A ②D
10、①B ②C 11、C 12、C 13、D 14、A 15、D
二、算法测试题（共31分）
1、struct node *link;(2分)
NULL ；或者 0 ；(2分)
s->link=h->link;（2分）
什么是表头结点？
答：表头结点是有时为了操作方便而在链表的第一结点之前添加的一个结点①，该结点结构与表中结点相同，但数据域不存放表中数据②，或者闲置不用，或者存放特殊信息。表头结点的链域存放指向链表中第一个结点的指针③。（2分，回答对①点给1分；②点0.5分；③点0.5分。）
如果该链表无表头结点该做怎样的修改？
修改如下：
void invert(LNode *h)
{ LNode *s,*p;
p=h；(1分)
h=NULL;（1分）
while(p!=NULL)
{ s=p;
p=p->link;
s->link=h;（1分）
h =s;（1分）
}
}
2、m=q;(2分)
q=q->link;（2分）
p=p->link;（2分）
不稳定（2分）
n(n-1)/2（2分）
当待排序序列为“正序”时，有最小移动次数0；（1分）
当待排序序列为“逆序”时，有最大移动次数3(n-1)；（1分）
算法的平均时间复杂度为O（n2）。（1分）
3、p->rchild;（2分）
q->LTag!=1;（2分）
1 （1分）；
NULL；或者 0 ；
三、应用题：
1、 （4分，画对根结点1分，左子树正确1.5分，右子树正确1.5分）

后序序列为：DGJHEBKIFCA（2分）

2、前序序列补充完整为：ABCDEFGH（1分）
中序序列补充完整为：CBDEAGHF（1分）
后序序列补充完整为：CEDBHGFA（1分）

（3分，画对根结点1分，左子树正确1分，右子树正确1分）

（4分）画对各结点线索指针得2分，标志位正确得1分，表头结点正确得
3、 （4分，画对各树根结点2分， 画对各子树子女结点2分）
该森林的先序序列为：
ABCMNSDEFGHKIJ（2分）

4、 （1） （2分,如果画的是无向图不給分）

（2）（2分，上小题答错的学生，如果这里给出的答案符合他自己所画的图，给全分）
0
1
1
1
0
0
0
1
0
1
0
0
0
0
1
0
0
1
0
1
0
0
0
0
0
（3）
a
4
3
2

b
5
3

c
5

d
5
3

e

(2分，第1小题答错的学生，如果这里给出的答案符合他自己画的图，给全分)
（4）可能的拓扑排序为：abdce 或 adbce (2分)
5、该序列为大根堆，不需要调整。（2分）

6、（1） （2） （3）

（每小题1分，完全符合答案才给分）