线性表抽象数据类型定义与顺序表操作

超、凢脫俗 2022-12-24 13:59 107阅读 0赞

作业3-线性表抽象数据类型定义与顺序表操作  
1-1  
对于顺序存储的长度为N的线性表，  
访问结点和增加结点的时间复杂度  
分别对应为O(1)和O(N)。(T)  
\[解析\]增加结点,不同位置复杂度不同,但平均复杂度在O(N)

1-2  
若某线性表最常用的操作是  
存取任一指定序号的元素和在最后进行插入和删除运算，  
则利用顺序表存储最节省时间。(T)  
\[解析\]顺序表的一个很大的缺点就是增删结点需要移动,  
但是此题只在表的末尾插入和删除,不需要移动,访问任意指定序号  
的元素用顺序表更方便

1-3  
对于顺序存储的长度为N的线性表，  
删除第一个元素和插入最后一个元素的  
时间复杂度分别对应为O(1)和O(N)。(F)

1-4  
(neuDS)在顺序表中逻辑上相邻的元素，  
其对应的物理位置也是相邻的。(T)

1-5  
(neuDS)所谓随机存取，就是通过首地址和  
元素的位序号值可以在O(1)的时间内找到指定的元素。(T)

1-6  
(neuDS)顺序存储的线性表不支持随机存取。(F)

1-7  
(neuDS)在顺序表上进行插入、删除操作时  
需要移动元素的个数与待插入或待删除元素的位置无关。(F)

2-1  
对于顺序存储的长度为N的线性表，  
访问结点和增加结点的时间复杂度为：(A)  
A.O(1), O(1)  
B.O(1), O(N)  
C.O(N), O(1)  
D.O(N), O(N)

2-2  
在N个结点的顺序表中，算法的时间复杂度为O(1)的操作是：(A)  
A.访问第i个结点（1≤i≤N）和求第i个结点的直接前驱（2≤i≤N）  
B.在第i个结点后插入一个新结点（1≤i≤N）  
C.删除第i个结点（1≤i≤N）  
D.将N个结点从小到大排序

2-3  
若某线性表最常用的操作是存取任一指定序号的元素和  
在最后进行插入和删除运算，  
则利用哪种存储方式最节省时间？(D)  
A.双链表  
B.单循环链表  
C.带头结点的双循环链表  
D.顺序表

2-4  
顺序表中第一个元素的存储地址是100，  
每个元素的长度为2，则第5个元素的地址是()。©  
A.100  
B.105  
C.108  
D.110  
\[解析\]100, 102, 104, 106, 108

2-5  
(neuDS)线性表的顺序存储结构是一种(B)  
A.随机存取的存储结构  
B.顺序存取的存储结构  
C.索引存取的存储结构  
D.散列存取的存储结构

2-7  
(neuDS)要将一个顺序表\{a0,a1,……,an−1\}中第i个数据元素ai(0≤i≤n-1)删除，需要移动（ ）个数据元素。  
A.i  
B.n-i-1  
C.n-i  
D.n-i+1  
\[解析\]第i个元素的位序是i + 1, 需要移动的元素的个数是 n - (i + 1)

2-8  
用数组表示线性表的优点是()。(B)  
A.便于插入和删除操作  
B.便于随机存取  
C.可以动态地分配存储空间  
D.不需要占用一片相邻的存储空间

2-9  
若长度为n的线性表采用顺序存储结构，  
那么删除它的第i个数据元素之前，  
需要它一次向前移动（）个数据元素。(A)  
A.n-i  
B.n+i  
C.n-i-1  
D.n-i+1

2-10  
若长度为n的线性表采用顺序结构，  
在第i个数据元素之前插入一个元素，  
需要它依次向后移动()个元素。(B)  
A.n-i  
B.n-i+1  
C.n-i-1  
D.i  
\[解析\]n-i + 1 : 其中 "n-i"是指 第i+1个元素到 第n个元素,  
"+1"是指第i个元素

2-11  
线性表L=(a1, a2 ,……，an)用一维数组表示，  
假定删除线性表中任一元素的概率相同(都为1/n)，  
则删除一个元素平均需要移动元素的个数是()。©  
A.n/2  
B.(n+1)/2  
C.(n-1)/2  
D.n  
\[解析\]删除第一个需要 移动 n-1, 删除最后一个需要移动0个  
求和 为 (n-1)n/2, 平均 为 (n-1)/2