数据结构第2版习题答案解析严蔚敏.docx

完美 WORD 完美 WORD 格式 专业整理知识分享 专业整理 知识分享 10 10 第 2 章 线性表 选择题 （ 1）顺序表中 第一个 元素 的存储 地址 是 100 ，每个 元素的 长度 为 2，则第 5 个元素的地址是（ ）。 A．110 B ．108 C ．100 D ． 120 答案： B 解释：顺序表中的数据连续存储，所以第 5 个元素的地址为： 100+2*4=108 。 ） 向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 的元素个数为（ ）。 A．8 B ．63.5 C ．63 D ．7 答案： B 解释：平均要移动的元素个数为： n/2 。 ）链接存储的存储结构所占存储空间（ ） 。 A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B．只有一部分，存放结点值 C．只有一部分，存储表示结点间关系的指针 D．分两部分，一部分存放结点值，另一部分存放结点所占单元数 答案： A ）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。 A．必须是连续的 B ．部分地址必须是连续的C．一定是不连续的 D ．连续或不连续都可以答案： D ）线性表Ｌ在（ ）情况下适用于使用链式结构实现。 A．需经常修改Ｌ中的结点值 Ｂ．需不断对Ｌ进行删除插入C．Ｌ中含有大量的结点 Ｄ．Ｌ中结点结构复杂 答案： B 解释：链表最大的优点在于插入和删除时不需要移动数据，直接修改指针即可。 ）单链表的存储密度（ ）。 A．大于 1 B ．等于 1 C ．小于 1 D ．不能确定 答案： C 解释：存储密度是指一个结点数据本身所占的存储空间和整个结点所占的存储空 间之比，假设单链表一个结点本身所占的空间为 D，指针域所占的空间为 N，则存储密度为： D/(D+N) ，一定小于 1。 ）将两个各有 n 个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。 A．n B ． 2n-1 C ．2n D ．n-1 答案： A 解释：当第一个有序表中所有的元素都小于（或大于）第二个表中的元素，只需要用第二个表中的第一个元素依次与第一个表的元素比较，总计比较 n 次。 ）在一个长度为 n 的顺序表中，在第 i 个元素（ 1≤i≤n+1 ）之前插入一个新元素时须向后移动（ ）个元素。 A．n-i B ．n-i+1 C ．n-i-1 D ．I 答案： B (10) 线性表 L=(a ， a ,…… a )，下列说法正确的是（ ）。 1 2 n A．每个元素都有一个直接前驱和一个直接后继B．线性表中至少有一个元素 C．表中诸元素的排列必须是由小到大或由大到小 D．除第一个和最后一个元素外， 其余每个元素都有一个且仅有一个直接前驱和直接后 继。 答案： D 以下说法错误的是（ ）。 求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构 时实现的效率低 顺序存储的线性表可以随机存取 C．由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活D．线性表的链式存储结构优于顺序存储结构 答案： D 解释： 链式存储结构和顺序存储结构各有优缺点，有不同的适用场合。 在单链表中，要将 s 所指结点插入到 p 所指结点之后，其语句应为（ ）。 A．s-next=p+1; p-next=s; B．(*p).next=s; (*s).next=(*p).next; C．s-next=p-next; p-next=s-next; D．s-next=p-next; p-next=s; 答案： D 在双向链表存储结构中，删除 p 所指的结点时须修改指针（ ）。 A．p-next-prior=p-prior; p-prior-next=p-next; B．p-next=p-next-next; p-next-prior=p; C．p-prior-next=p; p-prior=p-prior-prior; D．p-prior=p-next-next; p-next=p-prior-prior; 答案： A 在双向循环链表中，在 p 指针所指的结点后插入 q 所指向的新结点，其修改指针的操作是（ ）。 A．p-next=q; q-prior=p; p-next-prior=q; q-next=q; B．p-next=q; p-next-prior=q; q-prior=p; q-next=p-next; 完美 WORD 完美 WORD 格式 专业整理知识分享 专业整理 知识分享 4 4