在具有n个结点 。

20、的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ ） 。
A O(1) B O(n) C O(n2) D O(nlog2n)【解答】B【分析】首先应顺序查找新结点在单链表中的位置 。
对于n个元素组成的线性表 ， 建立一个有序单链表的时间复杂度是（ ） 。
A O(1) B O(n) C O(n2) D O(nlog2n)【解答】C【分析】该算法需要将n个元素依次插入到有序单链表中 ， 而插入每个元素需O(n) 。
使用双链表存储线性表 ， 其优点是可以（ ） 。
A 提高查找速度 B 更方便数据的插入和删除C 节约存储空间 D 很快回收存储空间【解答】B【分析】在链表中一般只能进行顺序查找 ， 所以 ， 双链表并不能提高 。

21、查找速度 ， 因为双链表中有两个指针域 ， 显然不能节约存储空间 ， 对于动态存储分配 ， 回收存储空间的速度是一样的 。
由于双链表具有对称性 ， 所以 ， 其插入和删除操作更加方便 。
在一个单链表中 ， 已知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;
【解答】B【分析】注意此题是在q和p之间插入新结点 ， 所以 ， 不用考虑修改指针的顺序 。
在循环双链表的p所指结点后插入s所指结点的操作是（ ） 。
A。

【数据结构|数据结构习题和答案及解析】22、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【解答】D【分析】在链表中 ， 对指针的修改必须保持线性表的逻辑关系 ， 否则 ， 将违背线性表的逻辑特征 ， 图2-10给出备选答案C和D的图解 。
3. 判断题 线性表的逻辑顺序和存储顺序总是一致 。

23、的 。
【解答】错 。
顺序表的逻辑顺序和存储顺序一致 ， 链表的逻辑顺序和存储顺序不一定一致 。
线性表的顺序存储结构优于链接存储结构 。
【解答】错 。
两种存储结构各有优缺点 。
设p ， q是指针 ， 若p=q ， 则*p=*q 。
【解答】错 。
p=q只能表示p和q指向同一起始地址 ， 而所指类型则不一定相同 。
线性结构的基本特征是：每个元素有且仅有一个直接前驱和一个直接后继 。
【解答】错 。
每个元素最多只有一个直接前驱和一个直接后继 ， 第一个元素没有前驱 ， 最后一个元素没有后继 。
在单链表中 ， 要取得某个元素 ， 只要知道该元素所在结点的地址即可 ， 因此单链表是随机存取结构 。
【解答】错 。
要找到该结点的地址 ， 必须从头指针开始查找 ， 所以单链表是顺 。

24、序存取结构 。
4请说明顺序表和单链表各有何优缺点 ， 并分析下列情况下 ， 采用何种存储结构更好些 。
若线性表的总长度基本稳定 ， 且很少进行插入和删除操作 ， 但要求以最快的速度存取线性表中的元素 。
如果n个线性表同时并存 ， 并且在处理过程中各表的长度会动态发生变化 。
描述一个城市的设计和规划 。
【解答】顺序表的优点： 无需为表示表中元素之间的逻辑关系而增加额外的存储空间； 可以快速地存取表中任一位置的元素（即随机存取） 。
顺序表的缺点： 插入和删除操作需移动大量元素； 表的容量难以确定； 造成存储空间的“碎片” 。
单链表的优点： 不必事先知道线性表的长度； 插入和删除元素时只需修改指针 ， 不用移动元素 。
单链表的缺点： 。

25、 指针的结构性开销； 存取表中任意元素不方便 ， 只能进行顺序存取 。
应选用顺序存储结构 。
因为顺序表是随机存取结构 ， 单链表是顺序存取结构 。
本题很少进行插入和删除操作 ， 所以空间变化不大 ， 且需要快速存取 ， 所以应选用顺序存储结构 。
应选用链接存储结构 。
链表容易实现表容量的扩充 ， 适合表的长度动态发生变化 。
应选用链接存储结构 。
因为一个城市的设计和规划涉及活动很多 ， 需要经常修改、扩充和删除各种信息 ， 才能适应不断发展的需要 。
而顺序表的插入、删除的效率低 ， 故不合适 。
5算法设计 设计一个时间复杂度为(n)的算法 ， 实现将数组An中所有元素循环右移k个位置 。

来源：(未知)

【学习资料】网址：/a/2021/0126/0021177228.html

标题：数据结构|数据结构习题和答案及解析( 四 )