《数据结构》试题A

一、填空题(每空1分,共25分)

1.数据元素之间的关系在计算机中有两种表示方法:顺序映象和非顺序映象, 由此 得到两类不同的存储结构:____________存储结构和___________存储结构。

2._________________________________称为线性表的长度。

3._______________________________________的线性表称为队列。

4.设n个元素的线性表顺序存储,若在它的第i个(1≤i≤n)元素之后插入一个新元 素,共需移动_____________个元素。

5.栈中元素的进出原则为___________________。

6.字符串A中_______________称为串A的子串,________________称为空格串。

7.若7行6列的数组a以列序为主序顺序存储，基地址为1024,每个元素占2个存储单 元,则第3行第5列的元素(假定无第0行第0列)的存储地址是____。

8.___________________________________ 称为树的深度。

9.树的度指的是_________________________。

10.有n(n>0)个结点的完全二叉树的深度为__________________。

11.深度为k(k>0)的满二叉树共有____________________个非叶子。

12.在有向图G中,以顶点i为________________的数目称为i的出度。

13.有向图的存储结构有_________、___________、___________等表示法。

14.折半查找有序表(4,6,7,8,9,10,12,20,24,37,77,110),若查找值为9的元素,它 将依次与表中元素____________________比较大小；若查找值为80的元素,它将 依次与表中元素____________________比较大小。

15.构造Hash函数的方法有直接定址法、随机数法、____、____、____、____等。

16.对n个记录的表进行简单选择排序,共计需要进行______________次比较关键字, 在最坏情况下,共计交换____________对记录。

二、简答题(每小题5分,共10分)

1.二叉树有哪几种基本形态? 试举例说明。

2.线性表的顺序存储结构和链式存储结构各有哪些优点和缺点?