数据结构与算法 Data Structures and Algorithms 线性表

Question 1

以下哪种结构是逻辑结构，而与存储和运算无关：

Your Answer		Score	Explanation
双向链表
线性表	Correct	1.00
循环链表
单向链表
Total		1.00 / 1.00

Question 2

已知两个元素依值递增有序排列的线性表A和B，且同一表中的元素值各不相同。构造一个线性表C，其元素为A和B中元素的交集，且表C中的元素也依值递增有序排列。已知A和B的最大长度都是n。求你设计的高效算法的时间复杂度：

Your Answer		Score	Explanation
$O\left(\log n\right)$
$O\left(n\right)$	Correct	1.00
$O\left(\sqrt{n}\right)$
$O\left(n\ast n\right)$
Total		1.00 / 1.00

Question Explanation
根据A,B的增序性质，可以用两个指针扫描A,B数组，以线性时间完成求交集的运算。

Question 3

下面的叙述中正确的是：

Your Answer		Score	Explanation
线性表在链式存储时，查找第i个元素的时间与i的数值成正比。	Correct	0.25
线性表在链式存储时，插入第i个元素的时间与i的数值成正比。	Inorrect	0.00
线性表在顺序存储时，插入第i个元素的时间与i的数值成正比。	Inorrect	0.00
线性表在链式存储时，删除第i个元素的时间与i的数值无关。	Inorrect	0.00
Total		0.25 / 1.00

Question Explanation
链式存储默认用单链表实现。 链式存储时，按位置i查找，插入，删除都需要与i的数值成正比的时间开销。 顺序存储时，按位置i查找需要常数的时间开销，与i无关；按位置i插入，删除需要与总长度n-i的时间开销。

Question 4

某个线性表以顺序表形式实现，长度为n，现在按值查找元素，假设线性表中没有该值的概率为p，且要查找的值在线性表中等概率出现。则平均比较次数为：

Your Answer		Score	Explanation
$p\ast n+(1-p)\ast (n+1)/4$
$p\ast n+(1-p)\ast (n+1)$
$p\ast n+p\ast (n+1)/2$
$p\ast n+(1-p)\ast (n+1)/2$	Correct	1.00
Total		1.00 / 1.00

Question 5

某个线性表存储元素如下：$a0，a1，a2，a3，a4，a5，a6，a7，a8$。如果该线性表以顺序表形式实现，那么在$ai\left(0\le i\le 9\right)$的位置插入新元素，需要移动的元素个数为：

Your Answer		Score	Explanation
$i+1$
$8-i$
$i$
$9-i$	Correct	1.00
Total		1.00 / 1.00

Question Explanation
每次插入新元素后，需要将该元素之后的元素都向后移动一个位置。需要移动的元素下标有i，i+1，…，8，共9-i个元素。

Question 6

某个线性表存储元素如下：$a0，a1，a2，a3，a4，a5，a6，a7，a8$。如果该线性表以单链表形式实现（含头结点），已知头指针，那么在 $ai\left(0\le i\le 9\right)$前的位置插入新元素，需要移动指针的次数为：

Your Answer		Score	Explanation
$9-i$
$i$	Correct	1.00
$8-i$
$i+1$
Total		1.00 / 1.00

Question Explanation
已知线性表存储结构为含头节点的单链表，当要在$ai$元素位置插入元素时，需要把指针从头节点移动到$ai$节点的前一个节点，共需要$i$次指针移动操作。