习题课LIST.ppt

Data Structures and Algorithm Analysis in C Shi ting-ting exercise LIST 1.填空 （1）设单链表中指针p 指向结点A，若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为（ ）。 （2）非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（ ）。 （3）在由尾指针rear指示的单循环链表中，在表尾插入一个结点s的操作序列是（ ）；删除开始结点的操作序列为（ ）。 （4）一个具有n个结点的单链表，在指针p所指结点后插入一个新结点的时间复杂度为（ ）；在给定值为x的结点后插入一个新结点的时间复杂度为（ ）。 2. 选择题 ⑴ 线性表的顺序存储结构是一种（ ）的存储结构，线性表的链接存储结构是一种（ ）的存储结构。 A 随机存取 B 顺序存取 C 索引存取 D 散列存取 ⑵ 线性表采用链接存储时，其地址（ ）。A 必须是连续B 部分地址必须是连续的C 一定是不连续的　D 连续与否均可以 ⑶ 单循环链表的主要优点是（ ）。A 不再需要头指针了 B 从表中任一结点出发都能扫描到整个链表；C 已知某个结点的位置后，能够容易找到它的直接前趋；D 在进行插入、删除操作时，能更好地保证链表不断开。 ⑷ 链表不具有的特点是（ ）。A 可随机访问任一元素 B 插入、删除不需要移动元素C 不必事先估计存储空间 D 所需空间与线性表长度成正比 ⑸ 若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋，则采用（ ）存储方法最节省时间。A 顺序表 B 单链表 C 双链表 D 单循环链表 ⑹ 若链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用（ ）存储方法最节省运算时间。A 单链表 B 循环双链表 C单循环链表 　　D 带尾指针的单循环链表 ⑺在循环双链表的p所指结点后插入s所指结点的操作是（ ）。A p-next=s; s-prior=p; p-next-prior=s; s-next=p-next; B p-next=s; p-next-prior=s; s-prior=p; s-next=p-next;C s-prior=p; s-next=p-next; p-next=s; p-next-prior=s;D s-prior=p; s-next=p-next; p-next-prior=s; p-next=s 3．算法设计 （1）试分别用顺序表和单链表作为存储结构，实现将线性表(a0,a1,...an-1)就地逆置的操作，所谓就地指辅助空间应为O(1)。 （2）设 A和B是两个单链表，其表中元素递增有序。试写一算法将A和B归并成一个按元素值递减有序的单链表C，并要求辅助空间为O(1) 。 （3）写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。 * 顺序表的 C 语言描述 typedef struct { } SqList; ElemType *elem; // 存储空间基址 int length; // 当前长度 int listsize; // 当前分配的存储容量 // (以sizeof(ElemType)为单位) // 存储结构 typedef struct LNode { ElemType data; // 数据域 struct LNode *next; // 指针域 } *LinkList; 单链表的 C 语言描述 LinkList L； // L 为单链表的头指针 *