当前位置:首页 >> 数学 >>

第一二章习题1答案


一 填空 1. 衡量算法效率的两个重要指标称为算法的______时间复杂度_和___空间复杂度 2. 一个算法应具有有穷性,确定性,可行性,输入和输出这五个特性。 3. 线性表的长度是指___表中元素的个数___。 4. 在线性表的顺序存储中,元素之间的逻辑关系是通过元素存储的相对位置决定的;在线 性表的链接存储中,元素之间的逻辑关系是通过相关元素的存储位置决定的。 5 在双向链表中,每个结点包含两个指针域,一个指向其直接前趋结点,另一个指向其直接 后继结点。 二、 判断题 1.线性表的逻辑顺序与存储顺序总是一致的。(FALSE) 2.顺序存储的线性表可以按序号随机存取。(TRUE) 3 .在线性表的顺序存储结构中,逻辑上相邻的两个元素在物理位置上并不一定紧邻。 (FALSE) 4.在线性表的链式存储结构中,逻辑上相邻的元素在物理位置上不一定相邻。 (TRUE) 5 .在线性表的顺序存储结构中,插入和删除时,移动元素的个数与该元素的位置有关。 (TRUE) 6.线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。 (TRUE) 三、 单选题 (请从下列 A,B,C,D 选项中选择一项) 1.线性表是( ) 。 (A) 一个有限序列,可以为空; (B) 一个有限序列,不能为空; (C) 一个无限序列,可以为空; (D) 一个无序序列,不能为空。 答:A 2.对顺序存储的线性表,设其长度为 n,在任何位置上插入或删除操作都是等概率的。插 入一个元素时平均要移动表中的( )个元素。 (A) n/2 (B)(n+1)/2 (C) (n –1)/2 (D) n 答:A 3.线性表采用链式存储时,其地址( ) 。 (A) 必须是连续的; (B) 部分地址必须是连续的; (C) 一定是不连续的; (D) 连续与否均可以。 答:D 4.用链表表示线性表的优点是 ( ) 。 (A)便于随机存取 (B)花费的存储空间较顺序存储少 (C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同 答:C 5. 某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素,则采 用( )存储方式最节省运算时间。 (A)单链表 (B)双链表 (C)单循环链表 (D)带头结点的双循环链表 答:D

6. 循环链表的主要优点是( ) 。 (A)不再需要头指针了 (B)已知某个结点的位置后,能够容易找到他的直接前趋 (C)在进行插入、删除运算时,能更好的保证链表不断开 (D)从表中的任意结点出发都能扫描到整个链表 答:D 7. 单链表中,增加一个头结点的目的是为了( ) 。 (A) 使单链表至少有一个结点 (B)标识表结点中首结点的位置 (C)方便运算的实现 (D) 说明单链表是线性表的链式存储 答:C 8. 若某线性表中最常用的操作是取第 i 个元素和找第 i 个元素的前趋元素,则采用( )存 储方式最节省运算时间( ) 。 (A) 单链表 (B) 顺序表 (C) 双链表 (D) 单循环链表 答:B 四、简答题 1 何时选用顺序表、何时选用链表作为线性表的存储结构为宜? 答: 在实际应用中, 应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结 构,通常有以下几方面的考虑: 1.基于空间的考虑。当要求存储的线性表长度变化不大,易于事先确定其大小时,为了节约 存储空间,宜采用顺序表;反之,当线性表长度变化大,难以估计其存储规模时,采用动态 链表作为存储结构为好。 2.基于时间的考虑。若线性表的操作主要是进行查找,很少做插入和删除操作时,采用顺序 表做存储结构为宜;反之, 若需要对线性表进行频繁地插入或删除等的操作时,宜采用链 表做存储结构。并且,若链表的插入和删除主要发生在表的首尾两端,则采用尾指针表示的 单循环链表为宜。 2 在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因 素? 答:在等概率情况下,顺序表中插入一个结点需平均移动 n/2 个结点。删除一个结点需平均 移动(n-1)/2 个结点。具体的移动次数取决于顺序表的长度 n 以及需插入或删除的位置 i。i 越接近 n 则所需移动的结点数越少。 3 为什么在单循环链表中设置尾指针比设置头指针更好? 答: 尾指针是指向终端结点的指针, 用它来表示单循环链表可以使得查找链表的开始结点和 终端结点都很方便,设一带头结点的单循环链表,其尾指针为 rear,则开始结点和终端结 点的位置分别是 rear->next->next 和 rear,查找时间都是 O(1)。 若用头指针来表示该链表,则查找终端结点的时间为 O(n)。 作业 2.1,2.2 答案见习题册后面答案 2. 6 答案:

解答: a.(4) (1) b.(7) (11)(8)(4) (1) c.(5) (12)

d.(11) (9) (1) (6)
2.7 答案:



(11)(9) (4) (1)

解答: a.(11) (3) (4) b.(10) (12) (8) (10) (3) (4) c. (10) (12) (7) (3) (4) d.(12) (11) (3) (14) e.(9) (11) (3)(14) 2 已知 P 结点是双向链表的中间结点,试从下列提供的答案中选择合适的语 2.8○ 句序列。 a.在 P 结点后插入 S 结点的语句序列是-----------。 b.在 P 结点前插入 S 结点的语句序列是-----------。 c.删除 P 结点的直接后继结点的语句序列是----------。 d.删除 P 结点的直接前驱结点的语句序列是----------。 e.删除 P 结点的语句序列是------------。 (1)P->next=P->next->next; (10) P->prior->next=P; (2)P->prior=P->prior->prior; (11) P->next->prior =P; (3) P->next=S; (12)P->next->prior=S; (4) P->prior=S; (13) P->prior->next=S; (5)S->next=P; (14) P->next->prior=P->prior (6)S->prior=P; (15)Q=P->next; (7) S->next= P->next; (16)Q= P->prior; (8) S->prior= P->prior; (17)free(P); (9) P->prior->next=p->next; (18)free(Q); 解答: a.(12) (7) (3) (6) 3 必须在 12 和 7 的后面,其余的顺序可变 b.(13) (8) (4) (5) 同上 c.(15) (1) (11) (18) 不可变 d.(16) (2) (10) (18) 不可变 e.(9) (14) (17)
2.31 答案: Typedef struct LNode{ ElemType data; //结点值 struct LNode *next; //指针域,存储下一个结点的地址 }LNode,*LinkList; Status Delete_Pre(linklist s ElemType & e) //删除单循环链表中结点 s 的直接前驱 { p=s; while(p->next->next!=s) p=p->next; //找到 s 的前驱的前驱 p

q=p->next; p->next =s; e=q ->data; free(q); return OK; }//Delete_Pre


相关文章:
单片机课后第一二章习题答案
单片机课后第一二章习题答案_理学_高等教育_教育专区。第一章 1, 什么是单片机,它与一般微型计算机在结构上有何区 别?答;单片机是把 CPU、RAM 和 ROM 存储器...
人教版七年级数学上第一二章总结练习题及答案
人教版七年级数学上第一二章总结练习题答案_数学_初中教育_教育专区。一、...1 8.四舍五入得到的近似数 0.09080,下列说法正确的是( ) A.有四个有效...
高中生物必修2第一二章单元练习及答案
高中生物必修2第一二章单元练习答案_理化生_高中教育_教育专区。高中生物必修2,第一章第二章的练习及答案生物必修 2 单元质量评估(一) 第 1、2 章(45 分钟...
线代一二章习题及答案
线代一二章习题答案_经济学_高等教育_教育专区。考研数学 经典习题 线代经典 考研必会 第一讲 行列式 例 1、下三角行列式 a11 a21 L an1 0 a22 L an ...
1 第一二章复习题
(1) 编写:张宝霞 班级: 姓名: 学号: 学案 1 第一二章习题 参考答案 学案 1 第一二章习题 参考答案 选择题: 1~5 CAABB 6-10 BCBDB 11-15 ...
固体物理第一二章习题解答
固体物理第一二章习题解答 隐藏>> 第一章 1. 习 题 画出下列晶体的惯用原胞和布拉菲格子,指明各晶体的结构以及惯用原胞、初基原胞中的原子个数和 配位数。...
第四版_微分几何_第一二章课后答案全
第四版_微分几何_第一二章课后答案全_理学_高等教育_教育专区。微分几何,第一二章答案 微分几何主要习题解答 第一章习题 1.1 13 微分几何主要习题解答 14 ...
高中生物必修三第一二章测试题(含答案)_(1)
必修三第一,二章测试题 1、与人体细胞直接进行物质交换的是 ( A.体液 B.细胞内液 ) D.细胞外液 C.消化液 ) 2、下列有关内环境的说法中不正确的是( A...
七年级上册地理第一二章测试题
七年级上册地理第一二章测试题_政史地_初中教育_教育专区。七年级上册地理第一...(每题 2 分,共 40 分,注意:请把答案填到后面的答题卡内,不然不得分) 1...
2013年初一语文上册第一二单元综合测试题及答案
2013年初一语文上册第一二单元综合测试题答案_初一语文_语文_初中教育_教育...(4 分) (1)元方入门不顾 顾:_回头看___ (2) 下车引之 引:_拉___ ...
更多相关标签: