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

第一二章习题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、在从...D.280 32、有一家共五口人,其中三人的皮肤很粗糙,并且一到夜晚就看不清物体...
《信号与系统》第一二章自测题及参考答案
《信号与系统》第一二章自测题及参考答案_信息与通信_工程科技_专业资料。第一、二章自测题 1、判断题 (1)若 x(t)是一连续时间周期信号,则 y(t)=x(2t)...
多媒体第一二章课后习题答案
多​媒​体​第​一​二​章​课​后​习​题​答​案 暂无评价|0人阅读|0次下载|举报文档第一章 1、媒体信息表示和传播的形式载体分为...
运筹学第一二章习题
运筹学习题答案(第八章) 39页 8财富值 运筹学 习题 4页 1财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
必修一第一二章测试题 含答案
必修一第一二章测试题 含答案_理化生_高中教育_教育专区。高中生物人教版必修一第一、二章练习题 必修一 第一、二章测试题 一.选择题(共 15 小题) 1.细胞...
人教版七年级数学上第一二章总结练习题及答案
人教版七年级数学上第一二章总结练习题答案_数学_初中教育_教育专区。一、...1 8.四舍五入得到的近似数 0.09080,下列说法正确的是( ) A.有四个有效...
人教版生物必修一第一二章单元测试题及答案
果汁 2 第二部分 非选择题(共 12 小题 每空 1 分共 40 分) (请把正确答案答在答题页,不在答题页作答不给分) 31、一片森林中的桉树苗、小桉树、大...
北师大版七年级数学上册第一二章综合测试卷及答案
北师大版七年级数学上册第一二章综合测试卷及答案_数学_初中教育_教育专区。七年级数学上册第一二章综合测试题(满分 120 分 时间 90 分钟) 班级 ___ 姓名 _...
物理必修一第一二章习题集合超全含答案
物理必修一第一二章习题集合超全含答案_理化生_高中教育_教育专区。物理必修一第一二章习题集合超全含答案2014-2015 学年度卷一、选择题(题型注释) 1.教练员分...
八年级物理第一二章测试题及答案
八年级物理第一二章测试题及答案_理化生_初中教育_教育专区。由莲山课件提供 ...( B 一、单项选择题(每题只有一个正确答案,每小题 3 分,共 36 分) 1....
更多相关标签: