数据结构课后练习题参考答案

数据结构习题参考答案 第一章: 一、1、B,H 2、A,B 3、D,C 4、C 5、C,E 6、A,B 7、A 8、D 9、 B 10、A 11、D 二、 1、线性、树型和图型,非线性 2、集合、线性、树型、图形结构 3、有穷性、确定性、可行性、输入和输出 4、时间复杂度和空间复杂度 5、一对一、一对多、多对多 6、O(n) 7、O(m*n) 8、逻辑关系 9、数据的逻辑结构、数据的存储结构、对数据施加的操作 10、没有、一个 11、一个、一个、后继、任意个 12、任意个 13、物理 14、数据、数据元素、数据项 15、结点、记录、元素、顶点 16、顺序存储、链式存储、 索引存储、散列存储 17、正确性、可读性、健壮性、高效性 18、时间复杂度、空 间复度、计算量、存储量 19、问题规模 20、 1、 log 2 n 、n、 n 2 、 2n 、不可行 21、设 计、实现 22、数据元素 23、数学模型 、判断题 1. × 2.√ 3.√ 4. × 5.√ 6.√ 7. × 8. × 四、计算题 1、 (1)n-2 (2)n(n+1)/2 (3)n 2、(1)n (2)1 (3)n (4)n-1 (5)(n-1)(n-2)/2 (6)n-1 3、O(n) O(n2) 6、解答:数据是信息的载体,是描述客观事物的数、字符,以及所有能输入到计算机中并 被计算机程序识别和处理的符号的集合。数据元素是数据的基本单位。在不同的条件下,数 据元素又可称为元素、结点、顶点、记录等。数据结构是指相互之间存在着一种或多种关系 的数据元素的集合。数据对象是性质相同的数据元素的集合。 7、解答:在数据结构中,逻辑结构与存储结构是密切相关的,存储结构不仅将数据元素存 储到计算机中,而且还要表示各数据元素之间的逻辑关系。逻辑结构与计算机无关,存储结 构是数据元素及其之间的关系在计算机中的表示。 ? ? 8、 2 3 n , 210 ,log2n, n , n 2 3 ,n,nlog2n,n2,n3,2n,n! 第二章:一、选择题 1、E,A 2、C 3、B 4、D 5、B C 13、D 14、A,C,D 15、A 21、A 22、D 23、D 二、填空题 1、 没有;1 2、 表中一半;该元素的位置 3、 (1)FC (2)BIAG 4、 (1)HGBJ (2)HFDBJ 5、 (1)FAI (2)EGDAI 6、 n/2, n/4 7、 O(1 ) O(n) 6、A 7、C 8、B 16、D 17、B 9、A 18A 10、B 11、C 12、 19、B 20、C 8、 线性表 9、 插入和删除首元素时不必进行特殊处理 10、 其直接前趋结点的链域 11、 q->prior=p; 12、 前趋结点,后继结点 13、 必定,不一定 14、 结点、第一个、最后一个、位置、前驱、后继 15、 前驱、前驱、后继、后继 16、 线性 17、 线性、长度 18、 p→next=NULL; 三、判断题 1.√ 2.? 3.√ 4.? 5.√ 6.√ 7.? 8.√ 9.? 10.? 四、简答题 1、 宜采用链式存储结构,因为它使线性表的插入和删除操作的时间复杂度为 O(1),而顺 序存储结构的为 O(n)。 2、 首元结点是指链表中存储线性表中第一个数据元素的结点。为了操作方便,通常在链表 的首元结点之前附设一个结点,称为头结点,该结点的数据域中不存线性表的数据元素, 其作用是为了对链表进行操作时,可以对空表、非空表的情况以及对首元结点进行统一 的处理。头指针是指向链表第一个结点(头结点或首元结点)的指针。若链表中附设头 结点,则不管线性表是否为空表,头指针均不为空,否则表示空表的链表的头指针为空。 这三个概念对单链表、双向链表和循环链表均适用。 3、 在等概率前提下,平均每插入一个元素需要移动的元素个数为(0+1+2+…+n)/(n+1)=n/2。 若元素插在 ai 与 ai+1 之间(0<=i<=n-1)的概率为 2(n-i)/(n(n+1)),则平均每插入一个元 素所要移动的元素个数为:(2n+1)/3 4、 解答:单循环链表中无论设置尾指针还是头指针都可以任一结点从遍历表中其它结点, 但设置尾指针时,若在表尾进行插入或删除操作时可在 O(1)时间内完成,同样在表头进 行插入或删除操作时也可在 O(1)时间内完成。但若设置的是头指针,表尾进行插入或删 除操作,需要遍历整个链表,时间复杂度为 O(n)。 5、 解答:能删除。双链表上删除 p 所指向的结点的时间复杂度为 O(1),单循环链表上删除 p 所指向的结点的时间复杂度为 O(n)。 6、 解答:如果长度大于 1,则将首元结点删除并插入到表尾。 7、 解答:应选用链式存储结构。因为顺序表是静态存储结构,只能预先分配存储单元,不 能随着线性表长度的改变而变化。而链表则可根据需要动态的申请空间,因此适用于动 态变化表长的线性表。 8、 解答:应该用顺序存储结构。因为顺序存储结构存取元素操作的时间复杂度为 O(1)。 9、 解答:用单链表表示多项式,除指针域外需设置两个数据域,一个用来存储系数,一个 用来存储指数。 (1) a 90 81 94 5 10 ∧ b -2 1 22 7 -5 10 ∧ (3)c 90 61 94 22 7 ∧ 四、设计题 1、 void split(SqList A,SqList &B,SqList &C) {//采用顺序存储结构实现 int I;B.length=C.length=0; for(I=0;I<AS.length;I++) {if(A.elem[i]>0){B.elem[B.length]=A.elem[i];B.length++;} else {C.elem[C.lengt

相关文档

数据结构第4单元课后练习答案
数据结构第1单元课后练习答案
数据结构课后练习题
数据结构课后练习答案
数据结构课后练习题汇总
数据结构课后练习题(树)
数据结构课后练习题汇编
数据结构课后习题答案[1]范文
数据结构第2单元课后练习答案
数据结构第3单元课后练习答案
电脑版