算法与数据结构 线性表答案

《算法与数据结构 线性表答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章线性表一、判断题1线性关系的逻辑结构与存储结构总是一致的。解：错。单链表的逻辑结构与存储结构有可能是不一致的，有可能两个相邻结点的存储地址并不是相邻的。2每种数据结构都包括插入、删除和查找这三种基本运算。解：错。散列结构无插入与删除运算；栈没有查找，查找须配有另一个栈。3线性表中的每个结点最多只有一个前驱和一个后继。解：对。线性表的定义为：表中任意一个元素至多有一个前驱，至多有一后继。4线性的数据结构既可以顺序存储，也可以链接存储；非线性的数据结构则只能链接存储。解：错。对于非线性的数据结构，若对它的数据规定某种次序之后

2、，也可以顺序存储。如，树的前、中、后序遍历之后的存储，一个前驱可能对应多个后继。5顺序存储方式只能用于存储线性结构。解：错。非线性结构也可采用顺序存储。6多维数组是向量的推广。解：对。多维向量的存储方式实际上与一维向量是一致的。7设串s的长度为n，则s的子串个数最多为n(n+1)/2。解：错。s的长度为n，故它含有n个字符，它的子串应包括：1个字符的子串，2个字符的子串，…，n个字符的子串；这些子串的个数分别为8单链表从任何一个结点出发，都能访问到所有结点。解：错。单链表仅能从头结点出发去访问所有结点，不能访问前驱。9线性表的

3、长度是线性表所占用的存储空间的大小。解：错。线性表所占用的存储空间大小为：每个结点所占用的存储字节数乘以线性表的长度。10双循环链表中，任意一结点的后继指针均指向其逻辑后继。解：错。任意结点的后继结点包含有两个指针llink和rlink，只有rlink指向其逻辑后继，而llink指向其逻辑前驱。11数据结构、数据元素、数据项在计算机中的映象(或表示)分别称为存储结构、结点、数据域。解：对。12线性表的顺序存储结构优于链式存储结构。解：错。各有优缺点。顺序存储结构的优点是：（1）存储效率高。（2）可随机访问任意结点，存取速度快。

4、顺序存储结构的缺点是：（1）插入与删除操作麻烦。（2）顺序表的长度扩充麻烦。链式存储结构的优点是：（1）插入与删除方便。（2）顺序表的长度可任意（动态分配内存）。链式存储结构的缺点是：（1）存储效率低。（2）对结点的访问不方便。二、选择题1若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为C，元素的移动次数为F(0≤i≤n)。(A)．O(0)(B)．O(1)(C)．O(n)(D)．O(n2)(E)．n-i+1(F)．n-i(G)．i(H)．i-1解：选C与E。因为，需要第i个位置至第n个位置的

5、n-i+1个元素向后逐一移动，因此，共做n-i+1次赋值运算，故T(n)=n-i+1，即T(n)=O(n)。2在长度为n的顺序存储的线性表中，删除第i个元素(0≤i≤n-1)时，需要从前向后依次前移C个元素。(A)．n-i(B)．n-i+1(C)．n-i-1(D)．i解：选C。因为前移元素的个数为n-i。3从解决问题的需要出发，为实现必要的功能所建立的数据结构，称为B。(A)．物理结构(B)．逻辑结构(C)．数据类型(D)．数据对象解：选B。4若长度为n的线性表采用顺序存储结构，在其第i(0≤i≤n)个位置插入一个新元素的平均

6、移动元素移动次数为C，在其第i(0≤i≤n-1)个位置删除一个元素的平均移动元素移动次数为D。(A)．n(B)．(n+1)/2(C)．n/2(D)．(n-1)/2解：选C。因为，在第0个位置插入新元素应移动n个元素，而在第1个位置插入新元素应移动n-1个元素，一般地，在第i(0≤i≤n)个位置插入一个新元素应移动n-i个元素，而在某个位置上插入新元素的概率为1/（n+1），故平均移动的次数为n/(n+1)+(n-1)/(n+1)+…+(n-i)/(n+1)+…+1/(n+1)+0/(n+1)=n/2选D。因为，在第0个位置删除

7、一个元素应移动n-1个元素，而在第1个位置删除元素应移动n-2个元素，一般地，在第i(0≤i≤n-1)个位置删除一个元素的应移动n-i-1个元素，而在某个位置上删除元素的概率为1/n，故平均移动的次数为(n-1)/n+(n-2)/n+…+(n-i-1)/n+…+1/n+0/n=(n-1)/25若长度为n的无序线性表采用顺序存储结构，在其中查找某个元素的平均比较的次数为D。(A)．n(B)．(n-1)/2(C)．n/2(D)．(n+1)/2解：选D。n个元素的排列方式有n!种，而某个指定元素排在第i个位置的种数为(n-1)!，故

8、某个指定元素恰好排在第i个位置的概率为(n-1)!/n!=1/n。这表明，待查找的元素恰好排在第1个位置、第2个位置、…和第n个位置的概率均为1/n。若待查找的元素排在第i个位置，那么查找的次数为i次（1≤i≤n），故平均查找次数为1/n+2/n+…+i/n+…+n/n=(n