数据结构课后答案c语言第二版

第一章 绪论 一、问答题

1. 什么是数据结构？

2. 叙述四类基本数据结构的名称与含义。 3. 叙述算法的定义与特性。 4. 叙述算法的时间复杂度。 5. 叙述数据类型的概念。

6. 叙述线性结构与非线性结构的差别。 7. 叙述面向对象程序设计语言的特点。

8. 在面向对象程序设计中，类的作用是什么？ 9. 叙述参数传递的主要方式及特点。 10. 叙述抽象数据类型的概念。 二、判断题（在各题后填写“√”或“×”）

1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（ ） 2. 算法就是程序。（ ）

3. 在高级语言（如C或 PASCAL）中，指针类型是原子类型。（ ） 三、计算下列程序段中X=X+1的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 【解答】

i=1时： 1 = (1+1)×1/2 = (1+12)/2 i=2时： 1+2 = (1+2)×2/2 = (2+22)/2 i=3时： 1+2+3 = (1+3)×3/2 =

第 1 章 绪 论

课后习题讲解

1. 填空

⑴（ 数据元素 ）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

【解答】数据元素

⑵（ 数据项）是数据的最小单位，（数据元素 ）是讨论数据结构时涉及的最小数据单位。

【解答】，

【分析】数据结构指的是数据元素以及数据元素之间的关系。

⑶ 从逻辑关系上讲，数据结构主要分为（ 集合）、（ 线性结构）、（ 树结构）和（ 图结构 ）。

【解答】，，，

⑷ 数据的存储结构主要有（顺序存储结构 ）和（ 链接存储结构）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（ 数据元素）

和（ 数据元素之间的关系 ）。

【解答】，，，

⑸ 算法具有五个特性，分别是（有零个或多个输入 ）、（有一个或多个输出 ）、（有穷性 ）、（确定性 ）、（可行性 ）。

【解答】，，，，

⑹ 算法的描述方法通常有（ 自然语言）、（程序设计语言 ）、（流程图 ）和（ 伪代码）四种，其中，（伪代码 ）被称为算法语言。

【解答】，，，，

⑺ 在一般情况下，一个算法的时间复杂度是（ 问题规模 ）的函数。

【解答】

⑻ 设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（Ο(1) ），若

为n*log25n，则表示成数量级的形

数据结构（C语言版）（第2版）

课后习题答案

李冬梅 2015.3

目 录

第第第第第第第第

1章 绪论 .................................................................................................................. 1 2章 线性表 .............................................................................................................. 5 3章 栈和队列......................................................................................................... 14 4章 串、数组和广义表 ......................................................................................... 27 5章 树和二叉

数据结构（C语言版）（第2版）

课后习题答案

李冬梅 2015.3

目 录

第第第第第第第第

1章 绪论 .................................................................................................................. 1 2章 线性表 .............................................................................................................. 5 3章 栈和队列......................................................................................................... 14 4章 串、数组和广义表 ......................................................................................... 27 5章 树和二叉

http://www.zydg.net/computer/book/read/data-structure/h971111102.html

习题解答(唐策善版)(其他版本在上面)

第一章 绪论（参考答案）

1.3 (1) O(n)

(2) (2) O(n)

(3) (3) O(n) (4) (4) O(n1/2)

(5)

(5) 执行程序段的过程中，x,y值变化如下：

循环次数 x y

0（初始） 91 100 1 92 100 2 93 100 ?? ?? ?? 9 100 100 10 101 100 11 91 99 12 92 100 ?? ?? ?? 20 101 99 21 91

第 3 章 线性表的链式存储

3.1 选择题

（1）两个有序线性表分别具有 n 个元素与 m 个元素且 n≤m，现将其归并成一个有序表， 其最少的比较次数是（ A ）。

A．n B．m C．n ? 1 D．m + n

（2）非空的循环单链表 head 的尾结点（由 p 所指向）满足（ C ）。

A．p->next==NULL B．p==NULL C．p->next==head D．p==head （3）在带头结点的单链表中查找 x 应选择的程序体是（ C ）。

A．node *p=head->next; while (p && p->info!=x) p=p->next;

if (p->info==x) return p else return NULL;

B．node *p=head; while (p&& p->info!=x) p=p->next; return p; C．node *p=head->next; while (p&&p->info!=x) p=p->next; return p; D．node *p=head; while (p->info!=x) p=p-

第一章 习题答案 2、××√ 3、（1）包含改变量定义的最小范围 （2）数据抽象、信息隐蔽

（3）数据对象、对象间的关系、一组处理数据的操作 （4）指针类型

（5）集合结构、线性结构、树形结构、图状结构 （6）顺序存储、非顺序存储 （7）一对一、一对多、多对多 （8）一系列的操作

（9）有限性、输入、可行性 4、（1）A（2）C（3）C

5、语句频度为1+（1+2）+（1+2+3）+…+（1+2+3+…+n） 第二章 习题答案 1、（1）一半，插入、删除的位置 （2）顺序和链式，显示，隐式 （3）一定，不一定

（4）头指针，头结点的指针域，其前驱的指针域 2、（1）A（2）A：E、A

B：H、L、I、E、A C：F、M

D：L、J、A、G或J、A、G （3）D（4）D（5）C（6）A、C

3、头指针：指向整个链表首地址的指针，标示着整个单链表的开始。

头结点：为了操作方便，可以在单链表的第一个结点之前附设一个结点，该结点的数据域可以存储一些关于线性表长度的附加信息，也可以什

第3章 栈和队列

1．选择题

（1）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（ ）种情况。 A．5，4，3，2，1 B．2，1，5，4，3 C．4，3，1，2，5 D．2，3，5，4，1 答案：C

解释：栈是后进先出的线性表，不难发现C选项中元素1比元素2先出栈，违背了栈的

后进先出原则，所以不可能出现C选项所示的情况。

（2）若已知一个栈的入栈序列是1，2，3，?，n，其输出序列为p1，p2，p3，?，pn，若p1=n，则pi为（ ）。

A．i B．n-i C．n-i+1 D．不确定 答案：C

解释：栈是后进先出的线性表，一个栈的入栈序列是1，2，3，?，n，而输出序列的第

一个元素为n，说明1，2，3，?，n一次性全部进栈，再进行输出，所以p1=n，p2=n-1，?，pi=n-i+1。

（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（ ）。

A．r-f B．(n+f-r)%n C．n+r-f

第 3 章 线性表的链式存储

3.1 选择题

（1）两个有序线性表分别具有 n 个元素与 m 个元素且 n≤m，现将其归并成一个有序表， 其最少的比较次数是（ A ）。

A．n B．m C．n ? 1 D．m + n

（2）非空的循环单链表 head 的尾结点（由 p 所指向）满足（ C ）。

A．p->next==NULL B．p==NULL C．p->next==head D．p==head （3）在带头结点的单链表中查找 x 应选择的程序体是（ C ）。

A．node *p=head->next; while (p && p->info!=x) p=p->next;

if (p->info==x) return p else return NULL;

B．node *p=head; while (p&& p->info!=x) p=p->next; return p; C．node *p=head->next; while (p&&p->info!=x) p=p->next; return p; D．node *p=head; while (p->info!=x) p=p-

第 3 章 线性表的链式存储

3.1 选择题

（1）两个有序线性表分别具有 n 个元素与 m 个元素且 n≤m，现将其归并成一个有序表， 其最少的比较次数是（ A ）。

A．n B．m C．n ? 1 D．m + n

（2）非空的循环单链表 head 的尾结点（由 p 所指向）满足（ C ）。

A．p->next==NULL B．p==NULL C．p->next==head D．p==head （3）在带头结点的单链表中查找 x 应选择的程序体是（ C ）。

A．node *p=head->next; while (p && p->info!=x) p=p->next;

if (p->info==x) return p else return NULL;

B．node *p=head; while (p&& p->info!=x) p=p->next; return p; C．node *p=head->next; while (p&&p->info!=x) p=p->next; return p; D．node *p=head; while (p->info!=x) p=p-