扫码获取更多资源

●线姓表习题

●填空题

1.如果顺序表中第一个元素存储地址是100,每个元素长度为2,则第五个元素存储地 址是( )o

2.在一个长度为n的顺序表的第i(lWiWn+l)个元素之前插入一个元素，需要向后 移动( )个元素，删除第i(lVi《n)个元素时，需要向前移动( )个元素。

3.设单链表中指针p指向结点a,如果要删除a的后继(假设a存在后继)，则需要修改 指针的操作为( )o

4.在由尾指针rear指示的循环链表中在表尾插入一个结点s的操作序列是( )； 删除开始结点的操作序列为( )。

5.在一个具有n个结点的单链表中，在指针p所指结点后插入一个新结点的时间复杂 度为( );在给定值为e的结点后插入一个新结点的时间复杂度为( )

●选择题

1.在长度为n的顺序表中查找元素e的时间复杂度为( )。

(A)O(0) (B) O(1) (C) O(n) (D) O(n2)

2.已知线性表L采用顺序存储结构，如果每个元素占用4个存储单元，第九个元素的 地址为144,则第一个元素的地址是( )。

(A) 108 (B) 180 (C) 176 (D) 112

3.如果在某个线性表中最常用的操作是选取第i个元素和寻找第i个元素的前驱，则 采用( )存储结构最节省时间。

(A)顺序表 (B)单链表 (C)双链表 (D)单循环链表

4.在具有n个结点的有序单链表中插入一个新结点，并仍然保持其有序性的时间复杂 度是( )

(A) 0(1) (B) O(n) (C) O(n2) (D) O(nlog2n)

5. 在一个单链表中，已知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；

●简答题

1.什么时候选用顺序表？什么时候选用链表作为线性表的存储结构为宜？

2.为什么在单循环链表中设置尾指针比设置头指针更好？

3.在单链表、循环链表和双向链表中，如果仅知道指针p指向某结点，而不知道头指 针，则能否将P所指向的结点从相应的链表中删除？如果可以，则其时间复杂度各为多少？

4.在图2-23所示的数组A中连接存储着一个线性表，表头指针为A[0]. next,则该线 性表是什么？

●算法设计题

1.试分别用顺序表和单链表作为存储结构，实现将线性表(a。，…，就地逆置的 操作。所谓“就地”是指辅助空间应为0(1)。

2.设顺序表L是一个递减有序表，试设计一个算法将e插入到L中，并使L仍为一个 有序表。

3.设La和Lb是两个单链表，表中元素递增有序，试设计一个算法将La和Lb就地归 并成一个按元素值递减有序的单链表Lc,请分析算法的时间复杂度。

4.已知一个单链表L,试设计一个算法将单链表中值重复的结点删除，使所得的结果 单链表中各结点值均不相同。

5.假设在长度大于1的循环链表中，既无头结点也无头指针。s为指向循环链表中某 个结点的指针，试设计一个算法删除s所指向结点的前驱。

联系我们：