东软数据结构，树和二叉树复习题

七、已知如下所示长度为12的表(34,25,68,72,21,15,49,29,77,8,19,102)

（1）按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树

（2）并求其在等概率的情况下查找成功的平均查找长度。

`习题一参考答案

2．试述数据结构研究的3个方面的内容。 参考答案:

数据结构研究的3个方面分别是数据的逻辑结构、数据的存储结构和数据的运算（操作）。

3．试述集合、线性结构、树型结构和图型结构四种常用数据结构的特性。 参考答案:

集合结构：集合中数据元素之间除了“同属于一个集合”的特性外，数据元素之间无其它关系，它们之间的关系是松散性的。

线性结构：线性结构中数据元素之间存在“一对一”的关系。即若结构非空，则它有且仅有一个开始结点和终端结点，开始结点没有前趋但有一个后继，终端结点没有后继但有一个前趋，其余结点有且仅有一个前驱和一个后继。

树形结构：树形结构中数据元素之间存在“一对多”的关系。即若结构非空，则它有一个称为根的结点，此结点无前驱结点，其余结点有且仅有一个前驱，所有结点都可以有多个后继。

图形结构：图形结构中数据元素之间存在“多对多”的关系。即若结构非空，则在这种数据结构中任何结点都可能有多个前驱和后继。

4．设有数据的逻辑结构的二元组定义形式为B=(D,R)，其中D={a1,a2,?,an}， R={| i=1,2,?，n-1}，请画出此逻辑结构对应的顺序存储结构和链式存储结构的示意图。 参考答案:

顺序存储结构示意图如下：

a1a2a3?an-1an

0 1 2 ? n-2 n-1 链式存储结构示意图如下：

a1a2a3?an^

5．设一个数据结构的逻辑结构如图1.9所示，请写出它的二元组定义形式。

K2 K4 K6 K5 K3 K1 K8 K9 K7

图1.9第5题的逻辑结构图

参考答案:

它的二元组定义形式为B=（D，R），其中D={k1,k2,k3,k4,k5,k6,k7,k8,k9}，

R=,,,,,,,,, }。

6．设有函数f (n)=3n2-n+4，请证明f (n)=O(n2)。

习题二参考答案

一、选择题

1. 链式存储结构的最大优点是（ ）。

A.便于随机存取 C.无需预分配空间

B.存储密度高

D.便于进行插入和删除操作

2. 假设在顺序表{a0,a1,??,an－1}中，每一个数据元素所占的存储单元的数目为4，且第0

个数据元素的存储地址为100，则第7个数据元素的存储地址是（）。 A. 106 B. 107 C.124 D.128

3. 在线性表中若经常要存取第i个数据元素及其前趋，则宜采用（ ）存储方式。

A.顺序表

C.不带头结点的单链表

B. 带头结点的单链表 D. 循环单链表

4. 在链表中若经常要删除表中第一个结点或在最后一个结点之后插入一个新结点，则宜采

用（ ）存储方式。 A. 顺序表

B. 用头指针标识的循环单链表 D. 双向链表

C. 用尾指针标识的循环单链表

5. 在一个单链表中的p和q两个结点之间插入一个新结点，假设新结点为S,则修改链的

java语句序列是（ ）。

A. s.setNext(p); q.setNext(s); B. p.setNext(s.getNext()); s.setNext(p); C. q.setNext(s.getNext()); s.setNext(p); D. p.setNext(s); s.setNext(q); 6. 在一个含有n个结点的有序单链表中插入一个新结点，使单链表仍然保持有序的算法的

时间复杂度是（ ）。

A. O(1) B. O(log2n) C. O(n) D. O(n2)

7. 要将一个顺序表{a0,a1,??,an-1}中第i个数据元素ai(0≤i≤n-1)删除，需要移动（ ）

个数据元素。

A. i B. n-i-1 C. n-i D. n-i+1

8. 在带头结点的双向循环链表中的p结点之后插入一个新结点s，其修改链的java语句序

列是（ ）。

A. p.setNext(s); s.setPrior(p); p.getNext().setPrior(s); s.setNext(p.getPrior());

B. p.setNext(s); p.getNext().setPrior(s); s.setPrior(p); s.setNext(p.getNext());

C. s.setPrior(p); s.setNext(p.getNext()); p.setNext(s); p.getNext().setPrior(s);

D. s.setNext(p.getNext()); s.setPrior(p); p.getNext().setPrior(s);

p.setNext(s);

9. 顺序表的存储密度是（ ），而单链表的存储密度是（ ）。

A．小于1 B. 等于1 C. 大于1 D. 不能确定 10. 对于图2.29所示的单链表，下列表达式值为真的是（ ）。