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

第一二章习题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 存储器...
第一二章习题
14页 1财富值 第一二章习题 12页 2财富值 第一二章习题答案 9页 5财富值 第一二章练习题 4页 免费 第一二章 习题参考答案 2页 5财富值如要投诉违规内...
物理必修一第一二章习题集合超全含答案
物理必修一第一二章习题集合超全含答案_理化生_高中教育_教育专区。物理必修一第一二章习题集合超全含答案2014-2015 学年度卷一、选择题(题型注释) 1.教练员分...
第四版_微分几何_第一二章课后答案全
第四版_微分几何_第一二章课后答案全_理学_高等教育_教育专区。微分几何,第一二章答案 微分几何主要习题解答 第一章习题 1.1 13 微分几何主要习题解答 14 ...
人教版高一物理必修1第一二章综合测试整理版含答案
人教版高一物理必修1第一二章综合测试整理版含答案_理化生_高中教育_教育专区。高一物理必修一第一二章综合测试 姓名一、选择题 1.下列情况中加划线的物体,哪些...
高一必修一物理一二章习题及答案
高一必修一物理一二章习题答案_政史地_高中教育_教育专区。高一必修一物理一...1 2 3 4 5 t/s A B 14.做匀减速直线运动的物体经 4 s 停止,若在第...
高中生物必修2第一二章单元练习及答案
高中生物必修2第一二章单元练习答案_理化生_高中教育_教育专区。高中生物必修2,第一章第二章的练习及答案生物必修 2 单元质量评估(一) 第 1、2 章(45 分钟...
经济法第一二章练习答案
2011 年初级经济法 第一二章练习答案 刘衍平 2011 年经济法第一、二章练习题答案一、单项选择题 1.下列表述中,反映了法的本质的是 ( )。 A.法是统治阶级...
微机原理第一二章习题答案
微机原理第一二章习题答案 北科07北科07隐藏>> 第一章 一.思考题(略) 二.综合题 1. 设机器字长为 8 位,写出下列用真值表示的二进制数的原码、补码和反码...
...修订版-(复旦大学)第一二章课后习题答案
概率论与数理统计习题答案-修订版-(复旦大学)第一二章课后习题答案_理学_高等教育_教育专区。详细完整版概率论与数理统计习题及答案 习题 一 1.?略.见教材习题参...
更多相关标签: