东软数据结构,树和二叉树复习题(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所示的单链表，下列表达式值为真的是（ ）。

head A B P1 C D P2 E

图2.29 单链表head的存储结构图

A. head.getNext().getData()=='C' B. head.getData()=='B' C. P1.getData()==’D’ D. P2.getNext()==null 二、填空题

1. 线性表是由n（n≥0）个数据元素所构成的有限序列，其中n为数据元素的个数，称为线性表的长度，n=0的线性表称为空表。

2. 线性表中有且仅有一个开始结点和终端结点，除开始结点和终端结点之外，其它每一个数据元素有且仅有一个前驱，有且仅有一个后继。

3. 线性表通常采用顺序存储和链式存储两种存储结构。若线性表的长度确定或变化不大，则适合采用顺序存储结构进行存储。

4. 在顺序表{a0,a1,??,an-1}中的第i(0≤i≤n-1)个位置之前插入一个新的数据元素，会引起n-i个数据元素的移动操作。

5. 在线性表的单链表存储结构中，每一个结点有两个域，一个是数据域，用于存储数据元素值本身，另一个是指针域，用于存储后继结点的地址。

6. 在线性表的顺序存储结构中可实现快速的随机存取，而在链式存储结构中则只能进行 顺序存取。

7. 顺序表中逻辑上相邻的数据元素，其物理位置一定相邻，而在单链表中逻辑上相邻的数据元素，其物理位置不一定相邻。

8. 在仅设置了尾指针的循环链表中，访问第一个结点的时间复杂度是o（1）。

9. 在含有n个结点的单链表中，若要删除一个指定的结点p，则首先必须找到指针结点的前驱，其时间复杂度为o（n）。

10. 若将单链表中的最后一个结点的指针域值改为单链表中头结点的地址值，则这个链表就

构成了循环单链表。

一、单项选择题

1. 下面描述错误的是（）

A． HTML文件由开头，标记结束。 B．文档头信息包含在与之间。

C．在和之间可以包含