《算法与数据结构线性表答案》由会员分享，可在线阅读，更多相关《算法与数据结构线性表答案（9页珍藏版）》请在金锄头文库上搜索。
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）插入与删除方便。（2）顺序表的长度可任意（动态分配内存）。链式存储结构的缺点
4、是：（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 i n-1)时，需要从前向后依次前移 C 个元素。(A)n-i (B
5、)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个位置插入新元素应移动n个元素，而在第1个位置插入新元素应移动n-1个元素，一般地，在第i
6、 (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+(n-i-1)/n+1/n+0/n=(n-1)/25 若长度为n的无序线性表采用顺序存储结构，在其中查找某个
7、元素的平均比较的次数为 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)/26 对于只在首、尾两端进行插入操作的线性表，宜采用的存储结构为 。(A)顺序表 (B)带头指针的单链表(C)带尾指针的单循环链表 (D)单
8、链表解：选C。7 在一个单链表中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行 。(A)q-link = p-link；p-link = q； (B)p-link = q-link；q = p；(C)q-link = p-link；p = q； (D)p-link = q-link；q-link = p；解：选D。8 在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行 。(A)HL = p; p-next = HL; (B)p-link = HL; HL = p;(C)p-link = HL; p = HL; (D)p-link = HL-link; HL-li
9、nk = p; 解：若单链表不带头结点，则应选B。若单链表带头结点，则应选D。9 在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行 。(A)p=q- link ; p-link = q-link; delete p;(B)p = q-link ; q-link = p; delete p;(C)p = q-link ; q-link = p-link; delete p;(D)q-link = q-link-link; q-link = q;解：选C。若选D，则链表中没有了q的后继结点，但未删除。仅C选项可使q的后继结点被删除，并按原有结点顺序重新拉链。10 设p为有头结点双向
10、循环链表中某结点的指针，lLink为左链指针，rLink为右链指针，则下述表达式中， 不恒为真。(A)p-rLink-lLink = p (B)p-rLink-lLink=p-lLink-rLink(C)p-lLink-rLink=p (D)p-rLink-rLink=p-lLink-lLink解：选D。因为p-rLink-lLink = p= p-lLink-rLink，故只有D不一定为真。11 若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用 存储方式最节省时间。(A)单链表 (B)双向链表 (C)带头结点的双循环链表 (D)单循环链表解：选C。12 链表不具
11、有的特点是 。(A)可随机访问任一元素 (B)插入删除不需要移动元素(C)不必事先估计存储空间 (D)所需空间与线性表长度成正比解：选A。13 线性表采用链式存储时，其地址 。(A)连续的 (B)部分连续的(C)一定是不连续的 (D)连续与否均可解：选D。14 设有一88下三角矩阵A88，采用按行压缩存储的方式存放在一维数组B 中，则数组B 的容量至少需要 B 个元素空间。(A)32 (B)36 (C)16 (D)64解：选B。矩阵的第1行有8个非零元素，第2行有7个非零元素，第8行有1个非零元素，故需要存储的非零元素的个数为8+7+6+5+4+3+2+1=8*(1+8)/2=36三、填空题1
12、 对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为 ，在表尾插入元素的时间复杂度为 。解：在表头（即第0个位置）插入元素，需移动的元素个数为n，然后再做1次赋值操作，故T(n)=n+1=O(n)。在表尾插入元素无需移动表中已有元素，只需1次赋值操作，故T(n)=1=O(1)。2 在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为 ，若假定p为一个数组a中的下标，则其后继结点的下标为 。解：应填入p-link，p+13 在单循环链表中，最后一个结点的指针指向 结点。解：表头结点。4 在双向链表中每个结点包含有两个指针域，一个指向其 结点，另一个指向 其 结
13、点。解：应填入前驱，后继。5 在双向循环链表中表头结点的左指针域指向 结点，最后一个结点的右指针域指向 结点。解：应填入表尾，表头。6 在以HL为表头指针的带附加表头结点的单链表和单循环链表中，链表为空的条件分别为 和 。解：HL-link=NULL , HL-link=HL7 在双循环链表L中，指针p所指结点为尾结点的条件为 。解：p!=first & p=first-link8 在单链表中，如果要使指针p指向它所指结点的后继结点，其语句是 。解：p =p-link9 在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的 、 和 三项。解：为了节省对矩阵的存储空间，稀疏矩阵采用仅存储非零元素的行下标、列下列与非零元素值的方式存储。10 二维数组A45按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A34的存储地址为 。如果其余条件不变，但是数组的存放方式变为列序优先，则元素A34的存储地址变为 。解：行优先方式存储：第0行、第1行、第2行的5个元素依次占据3*5*2=30个存储单元。而第3行的前4个元素占据4*2=8个存储单元，故A34的存储地址为120+30+8=158列优
