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

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

ID:12162890

大小:48.00 KB

页数:9页

时间:2018-07-15

算法与数据结构线性表答案_第1页
算法与数据结构线性表答案_第2页
算法与数据结构线性表答案_第3页
算法与数据结构线性表答案_第4页
算法与数据结构线性表答案_第5页
资源描述:

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

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)可随机访问任意结点,存取速度快。顺序存储结构的缺点是:(1)插入与删除操作麻烦。(2)顺序表的长度扩充麻烦。链式存储结构的优点是:(1)插入与删除方便。

4、(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个位置的n-i+1个元素向后逐一移动,因此,共做n-i+1次赋值运算,故T(n)=n-i+1,即T(n)=O(n)。2在长度为n的顺序存储的线性表中,删除第i个元素(0

5、≤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)个位置插入一个新元素的平均移动元素移动次数为C,在其第i(0≤i≤n-1)个位置删除一个元素的平均移动元素移动次数为D。(A).n(B).(n+1)/2(C).n/2(D).(n-1)/2解:选C。因为,在第0个位置插入新元素

6、应移动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个位置删除一个元素应移动n-1个元素,而在第1个位置删除元素应移动n-2个元素,一般地,在第i(0≤i≤n-1)个位置删除一个元素的应移动n-i-1个元素,而在某个位置上删除元素的概率为1/n,故平均移动的次数为(n-1)/n+(n-2)/n+…+(

7、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)!,故某个指定元素恰好排在第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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。