没有合适的资源?快使用搜索试试~ 我知道了~
数据结构习题解答(新).doc
0 下载量 193 浏览量
2022-11-30
15:55:47
上传
评论
收藏 861KB DOC 举报
温馨提示
试读
42页
数据结构习题解答(新).doc
资源推荐
资源详情
资源评论
《数据结构基础教程》习题解答(新)
第 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<n; i++)
k++;
其时间复杂度为 B 。
A.
O
(1) B.
O
(n) C.
O
(log
2
n) D.
O
(n
2
)
三、问答
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)
printf (“输入的是正数”);
else
printf (“输入的是负数”);
}
3.分析算法段中标有记号“#
1
”和“#
2
”的基本操作的执行次数:
for ( i=0; i<n; i++)
for (j=0; j<n; j++)
{
#
1
y=1;
for (k=0; k<n; k++)
#
2
y=y+1;
}
答:标有记号“#
1
”的基本操作的执行次数是:n
2
;标有记号“#
2
”的基本操作的执行
次数是:n
3
。
4.给出下面 3 个算法段的时间复杂度:
(1)x++;
(2)for (j=1; j<n; j++)
x++;
(3)for (j=1; j<=n; 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
(
n
2
),因此整个算法段的时间复杂度应该是
O
(
n
2
)。
第 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 所指结点的后面插入一个值
为 x 的结点,则需要执行下列操作:
ptr = malloc (size);
ptr->Data = x ;
ptr->Next = qtr->Next ;
qtr->Next = ptr ;
9.顺序表 Sq = (a
1
,a
2
,a
3
,…,a
n
)(
n
≥1)中,每个数据元素需要占用
w
个存储单
元。若
m
为元素 a
1
的起始地址,那么元素 a
n
的存储地址是
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 ;
tail = tail->Next ; free (tail) ;
free (ptr);
C.tail = tail->Next->Next ; D.ptr = tail->Next->Next ;
Free (tail); tail->Next->Next = ptr->Next ;
Free (ptr); free (ptr);
10.在单链表中,如果指针 ptr 所指结点不是链表的尾结点,那么在 ptr 之后插入由指
针 qtr 所指结点的操作应该是 B 。
A.qtr->Next = ptr ; B.qtr->Next = ptr->Next ;
ptr->Next = qtr ; ptr->Next = qtr ;
C.qtr->Next = ptr->Next ; D.ptr->Next = qtr ;
ptr = qtr ; qtr->Next = ptr ;
三、问答
1.试问,如下的线性表:
L = (29,25,21,17,13,11,7,5,3,1)
是有序线性表还是无序线性表?
答:L 是一个有序线性表。
2.线性表 L 第
i
个存储结点 a
i
的起始地址 LOC(a
i
)可以通过下面的公式计算得到:
LOC(a
i
)= LOC(a
i
-1
)+
k
其中
k
表示存储结点的长度。这个公式对吗?为什么?
答:这个公式是对的,因为第
i
个存储结点 a
i
的起始地址 LOC(a
i
),实际上就是等于
第
i
-1 个存储结点 a
i
-1
的起始地址 LOC(a
i
-1
)加上一个存储结点的长度
k
得到。
3.试说明创建顺序表算法 Create_Sq ()中,Sq_max 和 Sq_num 的不同之处。
答:Sq_max 代表的是顺序表的最大长度,也就是它最多可以容纳下多少个数据元素,
顺序表创建后,Sq_max 是一个保持不变的常量;Sq_num 代表的是顺序表当前拥有的数据元
素个数,在顺序表创建后,随着对数据元素进行的插入、删除操作,Sq_num 将会不断地发
生变化。
4.如何判断一个顺序表是否为空?
答:只需判定 Sq_num 的当前值是多少,如果 Sq_num 为 0,则表示顺序表 Sq 为空,否
则表示该顺序表里有数据元素存在。
5.在算法 2-3 里,操作“Sq_num=Sq_num -1”的作用是什么?没有它行吗?
答:该操作是非常重要的,因为顺序表里当前拥有的元素个数是通过 Sq_num 来记录的,
删除了一个元素,Sq_num 必须减 1,这样才能正确反映出删除后表中元素的个数。所以,没
有这个操作是不行的。
6.在算法 2-9 里,如果现在是把一个结点插入到单链表尾结点的后面。按照算法的描
述,能够保证插入后最后一个结点的 Next 域为“Λ”吗?
答:能够。因为原来 ptr->Next 里是“Λ”,做了第 1 步操作:
qtr->Next = ptr->Next ;
后,就是把插入结点的 Next 域置为“Λ”。
7.在一个单链表中,为了删除指针 ptr 所指的结点,有人编写了下面的操作序列。读
懂并加以理解。试问,编写者能够达到目的吗?其思想是什么?
x = ptr->Data ;
qtr = ptr->Next ;
ptr->Data = ptr->Next->Data ;
ptr->Next = ptr->Next->Next ;
free (qtr);
剩余41页未读,继续阅读
资源评论
matlab大师
- 粉丝: 2501
- 资源: 8万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功