广东海洋大学2008——2009学年第一学期 《数据结构》课程试题
一、填空题（10⨯2’=20分） 1、数据元素是（ ）的基本单位，在程序中通常作为一个（ ）进行处理。
2、数据结构是指相互间存在一定关系的（ ）的集合。
3、插入一个元素，线性表的长度（ ）1。
4、栈的操作特点是（ ）。
5、已知一棵二叉树的中序序列和后序序列分别为： DBGEACHF 和DGEBHFCA ，则该二叉树的前序序列是（ ）。
6、对于含有n 个顶点和e 条边的无向连通图，利用普里姆算法产生的最小生成树，其时间复杂度为（ ）、利用克鲁斯卡尔算法产生的最小生成树，其时间复杂度为（ ）。
7、对于包含５０个关键码的３阶B-树，其最小高度为（ ），最大高度为（ ）。
8、在插入和选择排序中，若初始数据基本正序，则选择（ ），若初始数据基本反序，则最好选择（ ）。
9、.在有n 个结点的无向图中，其边数最多为（ ）。
10、在串S="structure"中，以t 为首字符的子串有（ ）个。
二、选择题（10⨯2’=20分） 1、算法分析的两个主要方面是（ ）。
A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 2、.顺序表是线性表的 （ ）
A.链式存储结构
B.顺序存储结构
C. 索引存储结构
D. 散列存储结构
3、在线性表的下列运算中，不改变数据元素之间结构关系的运算是（ ）。
A ．插入
B ．删除
C ．排序
D ．定位
4、在一个单链表HL 中，若要在指针q 所指结点的后面插入一个由指针p 所指向的结点，则执行（ ）。
A. q->next=p->next; p->next=q;
B. p->next=q->next; q=p;
C. q->next=p->next; p->next=q;
D. p->next=q->next; q->next=p;
5、设循环队列中数组的下标范围是1～n ，其头尾指针分别为f 和r ，则其元素班
级
：
姓名： 学号：
试题共
页
加
白纸
张
密
封
线
GDOU-B-11-302
个数为( )
A. r-f
B. r-f+1
C. (r-f) mod n+1
D. (r-f+n) mod n
6、以下说法正确的是( )
A.数组中每个数据元素的数据类型相同
B.数组是一组分散的内存单元
C.数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的
D.使用三元组表表示稀疏矩阵的元素，有时并不能节省存储空间
7、常对数组进行的两种基本操作是（）
A.建立与删除
B.索引与修改
C. 查找与修改
D. 查找与索引
8、对于一个具有n个顶点和e条边的有向图，进行拓扑排序时，总的计算时间为( )
A O(en)
B O(n+e)
C O(nlog
2e) D O(elog
2
n)
9、以下说法正确的是（）
A.连通图的生成树，是该连通图的一个极小连通子图。
B.无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的。
C.任何一个有向图，其全部顶点可以排成一个拓扑序列。
D.有回路的图不能进行拓扑排序。
10、使用递归的归并排序算法时，为了保证排序过程的时间复杂度不超过
O(nlog
2
n)，必须做到( )。
A. 每次序列的划分应该在线性时间内完成
B. 每次归并的两个子序列长度接近
C. 每次归并在线性时间内完成
D. 以上全是
三、判断题（10⨯2’=20分）
1、数据的存储结构是数据的逻辑结构的存储映像，不仅要存储数据元素的值，还要存储元素之间的相互关系。
（）
2、非线性结构中，至少存在一个元素不止一个直接前驱或不止一个直接后继。
（）
3、散列表是一种链式存储结构。
（）
4、设串S的长度为n，则S的子串个数为n(n+1)/2。
（）
5、设有两个串p和q，求q在p中第一次出现的位置的运算称为字符定位。
（）
6、稀疏矩阵是指有少量非零元素的矩阵。
（）
7、任何一个非空广义表的表尾可以是原子也可以是子表。
（）
8、图G由两个集合V(G)和E(G)所组成，其中顶点集V(G)和边集E(G)都可以为空集。
（）
9、图的深度优先搜索的方法不适于有向图。
（）
10、一组纪录的关键字为（50,80,56,29,35,84），利用快速排序的方法进行第一趟排序后的结果为35,29,50,56,80,84。
（）。
四、算法阅读题（4⨯5’=20分）
阅读下面程序，在指定处填空。
1、读取队列长度
template <class T >
int CirQueue<T>::Length()
{
int length =(_____(1)___________) %____(2)________;
return ______(3)_______;
}
2、初始化一棵二叉树,构造函数调用
template <class T>
BiNode<T>* BiTree<T>::Creat( )
{
BiNode<T>* root;
T ch;
cout<<"请输入创建一棵二叉树的结点数据"<<endl;
cin>>ch;
if (ch=="____(1)_______") root = NULL;
else{
root = new BiNode<T>; //生成一个结点
root->data=______(2)________;
root->lchild =_______(3)_________; //递归建立左子树 root->rchild = Creat( ); //递归建立右子树
}
return root;
}
阅读下面程序，指出其算法的功能。
3、template <class T>
void BiTree::LeverOrder(BiNode<T> *root)
{
front=rear=0; //采用顺序队列，并假定不会发生上溢
if (root==NULL) return;
Q[++rear]=root;
while (front!=rear)
{
q=Q[++front];
cout<<q->data;
if (q->lchild!=NULL)Q[++rear]=q->lchild;
if (q->rchild!=NULL)Q[++rear]=q->rchild;
}
}
4、template <class T>
LinkList:: LinkList(T a[ ], int n)
{
first=new Node<T>; //生成头结点
r=first; //尾指针初始化
for (i=0; i<n; i++)
{
s=new Node<T>;s->data=a[i]; //为每个数组元素建立一个结点
r->next=s; r=s; //插入到终端结点之后
}
r->next=NULL; //单链表建立完毕，将终端结点的指针域置空
}
五、算法设计题（2 5’=10分）
1、两栈共享空间出栈算法Pop。
2、已知（k1，k2，…，kn，kn+1）是一个关键字序列，试将（k1，k2，…，kn，kn+1）调整为堆。
六、综合题（10分）
设有大小不等的n 个数据组（n个数据组中数据的总数为m），顺序存放在空间区D 内,每个数据占一个存储单元，数据组的首地址由数组S 给出，（如下图所示），试编写将新数据x 插入到第i个数据组的末尾且属于第i 个数据组的算法，插入后，空间区D 和数组S 的相互关系仍保持正确。
[提示]本题是在向量D内插入元素问题。
首先要查找插入位置，数据x插入到第i 个数据组的末尾，即是第i+1个数据组的开始，而第i（1≤i≤n）个数据组的首地址由数组s（即数组元素s[i]）给出。
其次，数据x插入后，还要维护数组s，以保持空间区D和数组s的正确的相互关系。