《算法与数据结构线性表答案》由会员分享，可在线阅读，更多相关《算法与数据结构线性表答案（9页珍藏版）》请在金锄头文库上搜索。
1、第 2 章 线性表、判断题1 线性关系的逻辑构造与存储构造总是一致的。解： 错。 单链表的逻辑构造与存储构造有可能是不一致的， 有可能两个相邻结点的存储地址并不是相邻的。2 每种数据构造都包括插入、删除和查找这三种根本运算。解：错。散列构造无插入与删除运算；栈没有查找，查找须配有另一个栈。3 线性表中的每个结点最多只有一个前驱和一个后继。解：对。 线性表的定义为：表中任意一个元素至多有一个前驱，至多有一后继。4 线性的数据构造既可以顺序存储，也可以链接存储；非线性的数据构造那么只能链接存储。解： 错。 对于非线性的数据构造， 假设对它的数据规定某种次序之后， 也可以顺序存储。 如，树的前、中、
2、后序遍历之后的存储，一个前驱可能对应多个后继。5 顺序存储方式只能用于存储线性构造。解：错。非线性构造也可采用顺序存储。6 多维数组是向量的推广。解：对。多维向量的存储方式实际上与一维向量是一致的。7设串s的长度为n,那么s的子串个数最多为n (n+1)/2。解：错。s的长度为n,故它含有n个字符，它的子串应包括：1个字符的子串，2个字符的 子串，n个字符的子串；这些子串的个数分别为Cn2Cn3Cnn(1 1) n 1 2n 18 单链表从任何一个结点出发，都能访问到所有结点。解：错。 单链表仅能从头结点出发去访问所有结点，不能访问前驱。9 线性表的长度是线性表所占用的存储空间的大小。解： 错
3、。 线性表所占用的存储空间大小为： 每个结点所占用的存储字节数乘以线性表的长度。10 双循环链表中，任意一结点的后继指针均指向其逻辑后继。解：错。 任意结点的后继结点包含有两个指针 llink 和 rlink ，只有 rlink 指向其逻辑后继，而 llink 指向其逻辑前驱。11 数据构造、数据元素、数据项在计算机中的映象(或表示)分别称为存储构造、结点、数据域。解：对。12 线性表的顺序存储构造优于链式存储构造。解：错。 各有优缺点。顺序存储构造的优点是： 1 存储效率高。 2可随机访问任意结点，存取速度快。顺序存储构造的缺点是： 1 插入与删除操作费事。 2 顺序表的长度扩大费事。链式存
4、储构造的优点是： 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与Eo因为，需要第i个位置至第n个位置的n-i+1个元素向后逐一挪动，因此， 共做n-i+1次赋值运算，故 T(n尸n-i+1 ,即T(n)=O(n)。2在长度
5、为n的顺序存储的线性表中，删除第 i个元素(0 V Wi-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 link = p-link;p-link= q ;(B) . p-link = q-link; q = p;(C) . q-link = p-link;p = q ;(D) .
6、p-link = q-link; q-link = p;解：选D。8在一个单链表 HL中，假设要向表头插入一个由指针p指向的结点，那么执行 (A) . HL = p; p-next = HL;(C). p-link = HL; p = HL;(B) . p-link = HL; HL = p;(D) . p-link = HL-link; HL-link = p;解：假设单链表不带头结点，那么应选Bo假设单链表带头结点，那么应选D。9在一个单链表 HL中，假设要删除由指针q所指向结点的后继结点，那么执行 。(A) .p=q- link ;p-link = q-link; delete p;(B
7、) .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;解：选Co假设选D,那么链表中没有了q的后继结点，但未删除。仅 C选项可使q的后继结点被删除，并按原有结点顺序重新拉链。10设p为有头结点双向循环链表中某结点的指针，lLink为左链指针，rLink为右链指针，那么下述表达式中，不恒为真。(A) . p-rLink-lLink = p(B) . p-rLink-lLink=p-lLink-rLink(C). p-
8、lLink-rLink=p(D). p-rLink-rLink=p-lLink-lLink解：选 D。因为 p-rLink-lLink = p= p-lLink-rLink ,故只有 D 不一定为真。11假设某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，那么采用 存储方式最节省时间。(A) .单链表 (B).双向链表(C).带头结点的双循环链表(D).单循环链表解：选Co12链表不具有的特点是 。(A).可随机访问任一元素(B) .插入删除不需要挪动元素(C).不必事先估计存储空间(D).所需空间与线性表长度成正比解：选A 13线性表采用链式存储时，其地址 。(A).连
9、续的(B).局部连续的(C). 一定是不连续的(D).连续与否均可解：选D。14设有一 8刈下三角矩阵A88,采用按行压缩存储的方式存放在一维数组B中，那么数组B的容量至少需要B个元素空间。(A) . 32(B) . 36(C). 16(D) . 64解：选Bo矩阵白第1行有8个非零元素，第2行有7个非零元素，第8行有1个非零 元素，故需要存储的非零元素的个数为8+7+6+5+4+3+2+1=8*(1+8)/2=36三、填空题1对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为 ,在表 尾插入元素的时间复杂度为 。解：在表头即第0个位置插入元素，需挪动的元素个数为n,然后再做1次
10、赋值操作，故T(n)=n+1=O(n)。在表尾插入元素无需挪动表中已有元素，只需1次赋值操作，故T(n)=1=O(1)。2在线性表的单链接存储中，假设一个元素所在结点的地址为p,那么其后继结点的地址为，假设假定p为一个数组a中的下标，那么其后继结点的下标为 。解：应填入p-link , p+13在单循环链表中，最后一个结点的指针指向 结点。解：表头结点。4在双向链表中每个结点包含有两个指针域，一个指向其 结点，另一个指向其 结点。解：应填入前驱，后继。5在双向循环链表中表头结点的左指针域指向 结点，最后一个结点的右指针域指向 结点。解：应填入表尾，表头。6在以HL为表头指针的带附加表头结点的单
11、链表和单循环链表中，链表为空的条件分别为 和。解：HL-link=NULL , HL-link=HL 7在双循环链表L中，指针p所指结点为尾结点的条件为 。解：p!=first & p=first-link8在单链表中，假设要使指针p指向它所指结点的后继结点，其语句是 解：p =p-link 9在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的 、和 三项。解：为了节省对矩阵的存储空间，稀疏矩阵采用仅存储非零元素的行下标、列以下与非零元素值的方式存储。10二维数组A45按行优先存储方法存储在内存中，假设每个元素占2个存储单元，且数组中第一个元素的存储地址为 120,那么元素A34的存储地
12、址为。假设其余条件不变，但是数组的存放方式变为列序优先，那么元素A34的存储地址变为 解：行优先方式存储：第。行、第1行、第2行的5个元素依次占据3*5*2=30个存储单元。而第3行的前4个元素占据4*2=8个存储单元，故 A34的存储地址为120+30+8=158列优先方式存储：第0歹U、第1歹U、第2歹U、第3列的4个元素依次占据 4*4*2=32个存储单元。而第4列的前3个元素占据3*2=6个存储单元，故 A34的存储地址为120+32+6=158四、算法设计1编写算法将以数组表示方式的顺序表原地逆置。解：#includeusing namespace std;#define N 10void Display(int a,int n) for(int i=0;in;i+)coutait;coutendl;/逆置函数1
