13年电大数据结构1到9章过程性测试习题答案 下载本文

《数据结构基础教程》习题解答

第1章习题解答

一、填空

1.数据是指所有能够输入到计算机中被计算机加工、处理的 符号 的集合。 2.可以把计算机处理的数据,笼统地分成 数值 型和 非数值 型两大类。 3.数据的逻辑结构就是指数据间的 邻接关系 。

4.数据是由一个个 数据元素 集合而成的。

5.数据项是数据元素中 不可再分割 的最小标识单位,通常不具备完整、确定的实际意义,只是反映数据元素某一方面的属性。

6.数据是以 数据元素 为单位存放在内存的,分配给它的内存区域称为 存储结点 。 7.每个数据元素都具有 完整 、 确定 的实际意义,是数据加工处理的对象。

8.如果两个数据结点之间有着逻辑上的某种关系,那么就称这两个结点是 邻接 的。 9.在一个存储结点里,除了要有数据本身的内容外,还要有体现 数据间邻接关系 的内容。 10.从整体上看,数据在存储器内有两种存放的方式:一是集中存放 在一个连续的 内存存储区中;一是利用存储器中的零星区域, 分散地存放在 内存的各个地方。

11.在有些书里,数据的“存储结构”也称为数据的“ 物理结构 ”。 12.“基本操作”是指算法中那种所需时间与操作数的具体取值 无关 的操作。

二、选择

1.在常见的数据处理中, B 是最基本的处理。 A.删除 B.查找 C.读取 D.插入 2.下面给出的名称中, A 不是数据元素的同义词。 A.字段 B.结点 C.顶点 D.记录 3. D 是图状关系的特例。 A.只有线性关系 B.只有树型关系

C.线性关系和树型关系都不 D.线性关系和树型关系都

4.链式存储结构中,每个数据的存储结点里 D指向邻接存储结点的指针,用以反映数据间的逻辑关系。 A.只能有1个 B.只能有2个 C.只能有3个 D.可以有多个

5.本书将采用 C 来描述算法。 A.自然语言 B.流程图(即框图) C.类C语言 D.C语言 6.有下面的算法段: for (i=0; i

- 1 -

习题解答

三、问答 1.中国百家姓中的赵、钱、孙、李、周、吴、郑、王??等姓氏数据之间,是一种什么样的邻接关系,为什么?

答:是一种线性关系,因为这些姓氏之间符合关系的“有头有尾,顺序排列”的特点。 2.什么是数据结点?什么是存储结点?它们间有什么关系?

答:数据结点即是数据集合中的一个数据元素,存储结点是存放数据结点的内存单位。在存储结点里,不仅要存放数据结点的内容,还要(显式或隐式地)存放数据结点间的逻辑关系。 3.为什么说链式存储既提高了存储的利用率,又降低了存储的利用率?

答:由于链式存储是通过指针来体现数据元素之间的逻辑关系的,因此,存储结点可以不占用存储器的连续存储区。从这个意义上说,链式存储能够充分利用存储器中小的存储区,因此提高了存储器的利用率。另一方面,链式存储中的存储结点不仅要存放数据元素,还要占用适当的存储区来存放指针,这是一种额外的存储开销。从这个意义上说,链式存储降低了存储器的利用率。 4.列举几个数据之间具有树型结构的实际例子。

答:学校各级管理之间,是一种分支层次结构;一本书的书目,是一种分支层次结构。 5.判断如下除法过程是否是一个算法,为什么: (1)开始; (2)给变量m赋初值5,给变量n赋初值0; (3)m=m/n; (4)输出m; (5)结束。

答:因为0不能为除数,本题第(3)步不具有有效性,所以它不是一个算法。但如果n的初值不为0,则是一个正确的算法。

四、应用 1.用类C语言中的do-while语句,描述输出整数1、2、3、??、9、10的过程。

答:算法编写如下。

void num () { i=1; do {

printf (“i = %d\\n”, i ); i = i +1; } while (i<= 10); }

2.用类C语言中的if-else语句,编写算法,描述当输入的数据大于等于0时,输出信息:“输入的是正数”;当输入的数据小于0时,输出信息:“输入的是负数”。

答:算法编写如下。

void judge () {

scanf (“%d\\n”, &x); if (x>=0)

- 2 -

习题解答

printf (“输入的是正数”); else

printf (“输入的是负数”); }

3.分析算法段中标有记号“#1”和“#2”的基本操作的执行次数: for ( i=0; i

#1 y=1;

for (k=0; k

答:标有记号“#1”的基本操作的执行次数是:n2;标有记号“#2”的基本操作的执行次数是:n3。 4.给出下面3个算法段的时间复杂度: (1)x++; (2)for (j=1; j

printf (“j=%”, j); for (k=j; k<=n; k++) x++; } 答:(1)的时间复杂度为O(1);

(2)的时间复杂度O(n);

(3)中“printf (“j=%”, j);”执行次数的数量级为O(n),“x++;”执行次数是: n+(n-1)+(n-2)+??+2+1 = n(n+1)/2

其数量级为O(n2),因此整个算法段的时间复杂度应该是O(n2)。

第2章习题解答

一、填空

1.当一组数据的逻辑结构呈线性关系时,在数据结构里就称其为 线性表 。 2.线性表中数据元素的个数n称为线性表的 长度 。 3.以顺序存储结构实现的线性表,被称为 顺序表 。 4.以链式存储结构实现的线性表,被称为 链表 。 5.不带表头结点的链表,是指该链表的表头指针直接指向该链表的 起始结点 。 6.在一个双链表中,已经由指针ptr指向需要删除的存储结点,则删除该结点所要执行的两条操作是 ①ptr->Prior->Next = ptr->Next; ②ptr->Next->Prior = ptr->Prior; 。 7.设tail是指向非空、带表头结点的循环单链表的表尾指针。那么,该链表起始结点的存储位置应该表示成 tail->Next->Next 。 8.在一个不带表头结点的非空单链表中,若要在指针qtr所指结点的后面插入一个值

- 3 -

习题解答

为x的结点,则需要执行下列操作: ptr = malloc (size);

ptr->Data = x ; ptr->Next = qtr->Next ; qtr->Next = ptr ;

9.顺序表Sq = (a1,a2,a3,?,an)(n≥1)中,每个数据元素需要占用w个存储单元。若m为元素a1的起始地址,那么元素an的存储地址是 m+(n-1)*w 。 10.当线性表的数据元素个数基本稳定、很少进行插入和删除操作,但却要求以最快的速度存取表中的元素时,我们应该对该表采用 顺序 存储结构。

二、选择

1.下面,对非空线性表特点的论述, C 是正确的。 A.所有结点有且只有一个直接前驱

B.所有结点有且只有一个直接后继

C.每个结点至多只有一个直接前驱,至多只有一个直接后继

D.结点间是按照1对多的邻接关系来维系其逻辑关系的 2.一般单链表Lk_h为空的判定条件是 A 。 A.Lk_h == NULL B.Lk_h->Next == NULL

C.Lk_h->Next == Lk_h D.Lk_h != NULL 3.带表头结点的单链表Lk_h为空的判定条件是 B 。 A.Lk_h == NULL B.Lk_h->Next == NULL

C.Lk_h->Next == Lk_h D.Lk_h != NULL 4.往一个顺序表的任一结点前插入一个新数据结点时,平均而言,需要移动 B个结点。 A.n B.n/2 C.n+1 D.(n+1)/2 5.在一个单链表中,已知qtr所指结点是ptr所指结点的直接前驱。现要在qtr所指结点和ptr所指结点之间插入一个rtr所指的结点,要执行的操作应该是 C 。 A.rtr->Next = ptr->Next; ptr->Next = rtr; B.ptr->Next = rtr->Next;

C.qtr->Next = rtr; rtr->Next = ptr; D.ptr->Next = rtr; rtr->Next = qtr->Next;

6.在一个单链表中,若现在要删除ptr指针所指结点的直接后继结点,则需要执行的操作是 A 。 A.ptr->Next = ptr->Next->Next ; B.ptr = ptr->Next; ptr->Next = ptr->Next->Next ;

C.ptr = ptr->Next->Next ; D.ptr->Next ptr ;

7.在长度为n的顺序表中,往其第i个元素(1≤i≤n)之前插入一个新的元素时,需要往后移动 B 个元素。 A.n-i B.n-i+1 C.n-i-1 D.i 8.在长度为n的顺序表中,删除第i个元素(1≤i≤n)时,需要往前移动 A 个元素。 A.n-i B.n-i+1 C.n-i-1 D.i 9.设tail是指向一个非空带表头结点的循环单链表的尾指针。那么,删除链表起始结点的操作应该是 D 。 A.ptr = tail ; B.tail = tail->Next ;

- 4 -