前言：最近快到FDS考试了，po重刷了一下学校的题目，自己整理了一些解析orz 因为po在自己找解析和学习的过程中非常痛苦，所以在此共享一下我的题目和自己写的解题思路，欢迎各位指出错误~全章节预计会陆续更新，可在专栏查看~
HW2
1. For a sequentially stored linear list of length?N, the time complexities for deleting the first element and inserting the last element are?O(1)?and?O(N), respectively.
F 顺序表查找数据很快，时间复杂度为O(1)，但是插入的话需要把后续元素都往后移动，时间复杂度为O(N)。链表刚好相反。
2. If a linear list is represented by a linked list, the addresses of the elements in the memory must be consecutive.
F 如果线性表用链式结构来存储，那元素地址必须连续存放。（错误，链表的结点每个都会存下一个结点地址，所以链表不需要连续存放）
3. To delete?p?from a doubly linked list, we must do:
A.p->prior=p->prior->prior; p->prior->next=p;
B.p->next->prior=p; p->next=p->next->next;
C.p->prior->next=p->next; p->next->prior=p->prior;
D.p->next=p->prior->prior; p->prior=p->next->next;
C 画图可知，p前一个结点的next要指向p后一个结点；p后一个结点的prior要指向p前一个结点。
4. If the most commonly used operations are to visit a random position and to insert and delete the last element in a linear list, then which of the following data structures is the most efficient?
A.doubly linked list
B.singly linked circular list
C.doubly linked circular list with a dummy head node
D.sequential list
D 因为插入删除元素只需要在尾部做，所以其实不会发生顺序存储时，插入新元素导致后续元素都要往后挪位置的情况。这样用顺序存储做插入删除和读取元素的时间复杂度都是O（1），所以省时间。
5.To merge two singly linked ascending lists, both with?N?nodes, into one singly linked ascending list, the minimum possible number of comparisons is:
A.1
B.N
C.2N
D.NlogN
B 要把两个有序单链表合并为一个链表，最少的比较情况可以假设一个链表中的元素是1,2,3,4,5；另一个链表是6,7,8,9,10；此时只要把6一直和1~5比5次就行，等前一个链表空了，再把后一个链表中的值直接链到新链表。所以最少比较N次。