数据结构线性表课后答案.docx

第2章线性表1.选择题（1）顺序表 中第一个元素的存储地址是100,每一个元素的 长度为2,则第5个 元素的地址是（）。A. 110B . 108 C. 100D . 120答案：B解释：顺序表中的数据连续存储，所以第5个元素的地址为：100+2*4=108。（2）在n个结点的顺序表中，算法的时间复杂度是O（I）的操作是（）。A.访问第i个结点（in）和求第i个结点的直接前驱（2i<n）B.在第i个结点后插入一个新结点（IWiWn）C.删除第i个结点（IWwn）D.将n个结点从小到大排序答案：A解释：在顺序表中插入一个结点的时间复杂度都是O（2）,排序的时间复杂度为 O（M）或者O（MOg2口）。顺序表是一种随机存取结构，访问第i个结点和求第i个结点的 直接 前驱都可以直接通过数组的下标直接定位，时间复杂度是0（1）。（3）向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均 要挪移的元素个数为（）。A . 8 B . 63.5 C . 63 D . 7答案：B解释：平均要挪移的元素个数为：n2o（4）链接存储的存储结构所占存储空间（）。A.分两部份，一部份存放结点值，另一部份存放表示结点间关系的指针B.惟独一部份，存放结点值C.惟独一部份，存储表示结点间关系的指针D.分两部份，一部份存放结点值，另一部份存放结点所占单元数答案：A（5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。A.必须是连续的B.部份地址必须是连续的C. 一定是不连续的D.连续或者不连续都可以答案：D（6）线性表L在（）情况下合用于使用链式结构实现。A .需时常修改L中的结点值 B .需不断对L进行删除插入C. L中含有大量的结点D . L中结点结构复杂答案：B解释：链表最大的优点在于插入和删除时不需要挪移数据，直接修改指针即 可。(7)单链表的存储密度()。A.大于1B.等于1 C.小于1 D.不能确定答案：C解释：存储密度是指一个结点数据本身所占的存储空间和整个结点所占的存 储空间之比，假设单链表一个结点本身所占的空间为D,指针域所占的空间为N , 则存储密度为：D(D+N), 一定小于1。(8)将两个各有n个元素的有序表归并成一个有序表，其至少的比较次数是()0A . nB . 2n-1C . 2n D . n-1答案：A解释：当第一个有序表中所有的元素都小于(或者大于)第二个表中的元素 ,只需要用第二个表中的第一个元素挨次与第一个表的元素比较，总计比较n次 O(9)在一个长度为n的顺序表中，在第i个元素(IWwn+1)之前插入一个新元 素时须向后挪移()个元素。A . n-iB . n-i+1 C . n-i-1 D . I答案：B(10)线性表L=(a 1 , a2,an),下列说法正确的是()。A.每一个元素都有一个直接前驱和一个直接后继B.线性表中至少有一个元素C.表中诸元素的罗列必须是由小到大或者由大到小D.除第一个和最后一个元素外，其余每一个元素都有一个且仅有一个直接前驱 和直接后继。答案：D(11)创建一个包括n个结点的有序单链表的时间复杂度是()0A . 0(1)B . O(n)C . O(2)D . O(nlog2n)答案：C解释：单链表创建的时间复杂度是0(n),而要建立一个有序的单链表，则每 生成一个新结点时需要和已有的结点进行比较，确定合适的插入位置，所以时间复 杂度是O(n2)o(12)以下说法错误的是()。A .求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存 储结构时实现的效率低B.顺序存储的线性表可以随机存取C.由于顺序存储要求连续的存储区域，所以在存储管理上不够灵便D.线性表的链式存储结构优于顺序存储结构答案：D解释：链式存储结构和顺序存储结构各有优缺点，有不同的合用场合。(13)在单链表中，要将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(14)在双向链表存储结构中，删除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(15)在双向循环链表中，在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;C . q->prior=p; q->next=p->next; p->next->prior=q; p->next=q;D . q->prior=p; q->next=p->next; p->ne×t=q; p->next->prior=q; 答案：C.算法设计题(D将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来 两个链表的存储空间不此外占用其它的存储空间。表中不允许有重复的数据。题目分析合并后的新表使用头指针 指向， 和 分别是链表 和 的工作指针初始 化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表 和 均为到 达表尾结点时，挨次摘取其中较小者重新链接在 表的最后。如果两个表中的元素相等， 只摘取 表中的元素，删除 表中的元素，这样确保合并后表中无重复的元素。当一 个表到达表尾结点，为空时，将非空表的剩余元素直接链接在 表的最后。算法描述合并链表 和 ，合并后的新表使用头指针 指向和 分别是链表 和 的工作指针初始化为相应链表的第一个结点 用 的头结点作为的头结点取较小者 中的元素，将 链接在 的后面，指针后移取较小者 中的元素，将 链接在 的后面， 指针后移相等时取 中的元素，删除 中的元素插入剩余段释放的头结点(2)将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用 原来两个链表的存储空间不此外占用其它的存储空间。表中允许有重复的数据。题目分析合并后的新表使用头指针 指向， 和 分别是链表 和 的工作指针初始 化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表 和 均为到 达表尾结点时，挨次摘取其中较小者重新链接在 表的表头结点之后，如果两个表中的 元素相等，只摘取 表中的元素，保留 表中的元素。当一个表到达表尾结点，为空 时，将非空表的剩余元素挨次摘取，链接在 表的表头结点之后。算法描述合并链表 和 ，合并后的新表使用头指针 指向和 分别是链表 和 的工作指针初始化为相应链表的第一个结点用 的头结点作为 的头结点只要存在一个非空表，用指向待摘取的元素表为空，用指向表为空，用指向指针后移指针后移取较小者(包括相等)中的元素，用指向指针后移取较小者 中的元素，用 指向指针后移将指向的结点插在表的表头结点之后释放的头结点(3)已知两个链表 和 分别表示两个集合，其元素递增罗列。请设计算法求出 与 的交集，并存放于 链表中。题目分析惟独同时浮现在两集合中的元素才浮现在结果表中合并后的新表使用头指针 指 向。 a和 分别是链表a和的工作指针初始化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表 a和均为到达表尾结点时，如果两个表中相等的元素时，摘取 a表中的元素，删除 表中的元素；如果其中一个表中的元素较小时， 删除此表中较小的元素，此表的工作指针后移。当链表 a和有一个到达表尾结点，为空时，挨次删除另一个非空表中的所有元素。算法描述d x( LinkList ankListnkLista= La > next; pb=> next;a和 分别是链表a和的工作指针初始化为相应链表的第个结点= pc= a用；a的头结点作为 的头结点 le( pa& & pb)a >data>=d=ata) 交集并入结果表中。> next= pa; pc= pa; pa= pa > next;u= pb; pb=> next; delete u; elsea >data>data) u=pa; pa=pa >next; delete u;)else u= pb; =>next; delete u; )Ie(Pa) u= pa;a=pa >nextu; ; (Ie 蜂e放结点空间Ie(pb)u=pb;=>ne;x t ；释(10放Ie结te点U空间>next=null; 置链表尾标记。delete ;释放 的头结点 (4)已知两个链表和分别表示两个集合，其元素递增罗列。请设计算法求出两 个集合 和 的差集(即仅由在 中浮现而不在 中浮现的元素所构成的集合)，并以 同样的形式存储，同时返回该集合的元素个数。题目分析求两个集合 和 的差集是指在 中删除 和 中共有的元素，即删除链表中的相 应结点所以要保存待删除结点的前驱，使用指针指e向前驱结点。a和分别是链表 a和的工作指针初始化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表a和均为到达表尾结点时，如果a表中的元素小于表中的元素，e置为a表的工作指针a删除 表中的元素；如果其中一个表中的元素较小时，删除此 表中较小的元素，此表的工作指针后移。当链表 a和 有一个为空时，挨次删除另一个非空表中的所有元素。算法描述Oider (eLn ne List L LinkList ) Lb, int n差集的结果存储于单链表L中，n是结果集合中元素个数，调用时为pa= L >next; pb=L > next;P和P分别是链表L和L的工作指针初始化为相应链表的第一个结点pre= La;/7pre为L中P所指结点的前驱结点的指针(pe )p(p >dat) >d Prte=Pa; Pa=P>next; *n+ ; 链表中当前结点指针后移else ( p >data> ) >d =t >next; /链表中当前结点指针后移else pre >next=p >next; 处理， 中元素值相同的结点，应删除-pa; pa=p >next; delete ；删除结点(5)设计算法将一个带头结点的单链表 其中表的结点为表中值小于零的结点，而表中的元素为非零整数，要求表利用分解为两个具有相同结构的链表、， 表的结点为表中值大于零的结点(链表的结点)。题目分析表的头结点使用原来表的头结点，为 结点开始，挨次取其每一个结点P，判断结点 P表新申请一个头结点。从表的第一个 的值是否小于，利用前插法，将小于的结点插入表大于等于的结点插入表。算法描述oidompose( LinkedList=A;> next= NULL; / 表初始化=e LNode; 为申请结点空间> next= NULL; /初始化为空表P= >next;p为工作指针e( p! = NULL r=p >next; 暂存P的后继 p > datP >next= >next; >next=p; 将小于 的结点链入 表 前插法 else p >next= >nex>tn; ext=p; 将大于等于的结点链入 表前插法P二r;P指向新的待处理结点。(6)设计一个算法，通过一趟遍历在单链表中确定值最大的结点。题目分析假定第一个结点中数据具有最大值，挨次与下个元素比较，若其小于下一个元素, 则设其下一个元素为最大值，反复进行比较，直到遍历完该链表。算法描述假定第一个结点中数据具有最大值如果下一个结点存在如果的值大于 的值，则重新赋值遍历链表(7)设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原 表的存储空间。题目分析从首元结点开始，逐个地把链表L的当前结点P插入新的链表头部。算法描述逆置带头结点的单链表指向 的后继插入在头结点之后(8)设计一个算法，删除递增有序链表中值大于 且小于的所有元素(和是给定的两个参数，其值可以和表中的元素相同，也可以不同)o题目分析分别查找第一个值 的结点和第一个值N的结点，再修改指针，删除值大于 且小于的所有元素。算法描述首元结点查找第一个值 的结点查找第一个值2 的结点修改指针释放结点空间(9)已知 指向双向循环链表中的一个结点，其结点结构为 、三个域，写出算法交换 所指向的结点和它的前缀结点的顺序。题目分析知道双向循环链表中的一个结点，与前驱交换涉及到四个结点(结点，前驱结点, 前驱的前驱结点，后继结点)六条链。算法描述( )/是双向循环链表中的一个结点，本算法将所指结点与其前驱结点交换。；/的前驱的前驱之后继为;/的前驱指向其前驱的前驱。；的前驱的后继为的后继。：/与其前驱交换；的后继的前驱指向原的前驱;的后继指向其原来的前驱算法结束。(10)已知长度为 的线性表 采用顺序存储结构，请写一时间复杂度为O 、空 间复杂度为O的算法，该算法删除线性表中所有值为的数据元素。题目分析在顺序存储的线性表上删除元素，通常要涉及到一系列元素的挪移(删第 个元素， 第 至第个元素要挨次前移)。本题要求删除线性表中所有值为的数据元素，并未要求元素间的相对位置不变。因此可以考虑设头尾两个指针(，)，从两端向中间挪移，凡遇到值的数据元素时，直接将右端元素左移至值为的数据元素位置。算法描述( , )是有个元素的一维数组，本算法删除中所有值为的元素。;设置数组低、高端指针(下标)。);若值不为 ，左移指针。)();若右端元素为 ，指针左移) ;