数据结构作业第2章.docVIP

第2章 线性表 1. 填空 在顺序表中，等概率情况下，插入和删除一个元素平均需移动（ ）个元素，具体移动元素的个数与（ ）和（ ）有关。 顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（ ）。 设单链表中指针p 指向结点A，若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为（ ）。 单链表中设置头结点的作用是（ ）。 非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（ ）。 在由尾指针rear指示的单循环链表中，在表尾插入一个结点s的操作序列是（ ）；删除开始结点的操作序列为（ ）。 一个具有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 带尾指针的单循环链表 若链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用（ ）存储方法最节省运算时间。 A 单链表 B 循环双向链表 C单循环链表 　　D 带尾指针的单循环链表 在具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ ）。 A O(1) B O(n) C O(n2) D O(nlog2n) 对于n个元素组成的线性表，建立一个有序单链表的时间复杂度是（ ）。 A O(1) B O(n) C O(n2) D O(nlog2n) 使用双向链表存储线性表，其优点是可以（ ）。 A 提高查找速度 B 更方便数据的插入和删除 C 节约存储空间 D 很快回收存储空间 在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则执行（ ）操作。 A s-next=p-next; p-next=s; B q-next=s; s-next=p; C p-next=s-next; s-next=p; D p-next=s; s-next=q; 在循环双向链表的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. 判断题 线性表的逻辑顺序和存储顺序总是一致的。 线性表的顺序存储结构优于链接存储结构。 设p，q是指针，若p=q，则*p=*q。 线性结构的基本特征是：每个元素有且仅有一个直接前驱和一个直接后继。 在单链表中，要取得某个元素，只要知道该元素所在结点的地址即可，因此单链表是随机存取结构。 4．请说明顺序表和单链表各有何优缺点，并分析下列情况下，采用何种存储结构更好些。 若线性表的总长度基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素。 如果n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化。 描述一个城市的设计和规划。 5．算法设计 设计一个时间复杂度为Ｏ(n)的算法，实现将数组A[n]中所有元素循环移k个位置。 已知数组A[n]中的元素为整型，设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为Ｏ(n)。 试编写在无头结点的