数据结构与算法试卷及答案6.doc

学院领导

审批并签名

AB卷

广州大学学年第学期考试卷

课程数据结构与算法考试形式（闭卷，考试）

信息学院系专业级班学号：姓名：

题次

一

二

三

四

五

六

总分

评卷人

分数

20

10

10

30

20

10

100

评分

填空题：（每格2分，共20分）

时间复杂度O(1)的意思是。

若长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，需要移动表中个数据元素（设线性表的首元素是第1个元素）。

设存储分配是从低地址到高地址进行的。若每个数据元素占用4个存储单元，则某数据元素的地址是指它所占用的单元的。

将一个20阶的五对角矩阵中所有非零元素压缩存储到一个一维数组中，该一维数组至少应该有个数组元素才行。

当队列的最大长度难以估计时，队列最好采用存储结构。

若某堆栈初始为空，PUSH与POP分别表示对堆栈进行一次进栈与出栈操作，那么，对于输入序列a,b,c,d,e，经过PUSH，PUSH，POP，PUSH，POP，PUSH，PUSh，POP以后，输出序列应该是。

设n个数据元素的进栈序列为P1，P2，P3，……，Pn，出栈序列为1，2，3，……,n，若Pn=1，则Pi(1≤in)的值。

在建立散列表时，若散列函数为H(k),a和b分别为关键字值，则当

时，称此现象为为散列冲突。

若对序列(fang,deng,an,wang,shi,bai,tang,liu)采用快速排序法按字典顺序进行排序，并且以序列的第一个元素作为分界元素，当该分界元素的排序最终位置确定那一刻，序列的状态是_____。

冒泡排序法、快速排序法、堆积排序法和二路归并排序法四种排序法中，要求辅助空间最多的方法是排序法。

单项选择题（每题1分，共10分）

1．（）数据的存储结构通常可以有：

A．两种，它们分别是：顺序存储结构和链式存储结构

B．三种，它们分别是：顺序存储结构、链式存储结构与索引结构

C．三种，它们分别是：顺序存储结构、链式存储结构与散列结构

D．四种，它们分别是：顺序存储结构、链式存储结构、索引结构与散列结构

2．（）若长度为n的非空线性表采用顺序存储结构，在表的第i个位置插入一个新的数据元素前，首先需要移动表中几个数据元素？（设线性表的首元素是第1个元素）

A．n-i

B．n+i

C．n-i+1

D．n-i-1

3．（）若变量list是某带头结点的循环链表的头结点指针，当变量p（p与list同类型）指向链表的最后那个链结点时：

该结点的指针域为空

p为空

p的内容与头结点的内容相同

该链结点指针域内容与list的内容相同

4．（）删除非空线性链表中由p所指链结点的直接后继结点的过程时依次执行：

A．r=p-link;p-link=r;free(r);

B．r=p-link;p-link=r-link;free(r);

C．r=p-link;p-link=r-link;free(p);

D．p-link=p-link-link;free(p);

5．（）若二叉树中度为2的结点有15个，度为1的结点有10个，则该二叉树有几个结点？

A．41B．31C．25D．30

6．（）若某完全二叉树的深度为h，则该完全二叉树中至少有几个结点？

A．B．C．D．

7．（）在二叉排序树中进行查找的时间效率与什么有关？

A．二叉排序树的深度B．二叉排序树的结点的个数

C．被查找结点的度D．二叉排序树的存储结构

8.（）在带权图中，两个顶点之间的路径长度是指：

A．路径上的顶点数目 B．路径上的边的数目

C．路径上顶点和边的数目 D．路径上所有边上的权值之和

9．（）若具有n个顶点的无向连通图采用邻接矩阵表示，则邻接矩阵中至少有多少个非零元素?

A．2(n-1)B．