线性结构各章习题

第2章线性表线性表是一种最基本、最常用的数据结构，它有两种存储结构——顺序表和链表。

本章主要介绍线性表的定义、表示和基本运算的实现。

重点讨论了线性表的存储结构，以及在顺序、链式两种存储结构上基本运算的实现。

重点提示：●线性表的逻辑结构特征●线性表的顺序存储和链式存储两种存储结构的特点●在两种存储结构下基本操作的实现2-1 重点难点指导2-1-1 相关术语1．线性表线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列，通常记为：(a1,a2,…,a n)，其中n为表长，n=0时称为空表。

要点：一种逻辑结构，其数据元素属于相同数据类型，之间的关系是线性关系。

2．顺序表顺序存储的线性表。

要点：按线性表中的元素的逻辑顺序依次存放在地址连续的存储单元里，其存储特点：用物理上的相邻实现逻辑上的相邻。

3．链表用链表存储的线性表。

要点：链表是通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的，对每个结点的地址是否连续没有要求。

4．单链表每个结点除了数据域外还有一个指向其后继的指针域。

要点：通常将每个元素的值和其直接后继的地址作为一个结点，通过每个结点中指向后继结点的指针表示线性表的逻辑结构。

5．头指针要点：头指针是一个指针变量，里面存放的是链表中首结点的地址，并以此来标识一个链表。

如链表H，链表L等，表示链表中第一个结点的地址存放在指针变量H、L中。

通常用头指针来惟一标识一个链表。

6．头结点要点：附加在第一个元素结点之前的一个结点，头指针指向头结点。

当该链表表示一个非空的线性表时，头结点的指针域指向第一个元素结点；为空表时，该指针域为空。

7．头结点的作用要点：其作用有两个，一是使对空表和非空表的处理得到统一；二是在链表的第一个位置上的操作和在其他位置上的操作一致，无需特殊处理。

2-1-2 线性表的顺序存储1．顺序表顺序存储的线性表称为顺序表。

其特点是：用一组地址连续的存储单元来依次存放线性表的数据元素，因此数据元素的逻辑顺序和物理次序一致（这是顺序存储的核心所在）。

数据结构练习题线性表习题及答案精品文档第二章线性表一．名词解释1.线性结构2.数据结构的顺序实现3.顺序表4.链表5.数据结构的链接实现6. 建表7.字符串8.串9.顺序串 10.链串二、填空题1.为了便于讨论，有时将含n(n>=0)个结点的线性结构表示成(a，a,……a)，其中每n12个a代表一个______。

a称为______结点，a称为______结点，i称为a在线性表中的________ii1n或______。

对任意一对相邻结点a、a(1<=i<n),a称为a的直接______a称为a的直iii┼1i┼1┼i1i接______。

< bdsfid="75" p=""></n),a称为a的直接______a称为a的直iii┼1i┼1┼i1i接______。

<>2.为了满足运算的封闭性，通常允许一种逻辑结构出现不含任何结点的情况。

不含任何结点的线性结构记为______或______。

3.线性结构的基本特征是:若至少含有一个结点，则除起始结点没有直接______外，其他结点有且仅有一个直接______;除终端结点没有直接______外，其它结点有且仅有一个直接______.4.所有结点按1对1的邻接关系构成的整体就是______结构。

5.线性表的逻辑结构是______结构。

其所含结点的个数称为线性表的______，简称______.6.表长为O的线性表称为______7.线性表典型的基本运算包括:______、______、______、______、______、______等六种。

8.顺序表的特点是______。

9.顺序表的类型定义可经编译转换为机器级。

假定每个datatype 类型的变量占用k(k>=1)个内存单元，其中，b是顺序表的第一个存储结点的第一个单元的内存地址，那么，第i个结点a的存储地址为______。

第 1 章绪论课后习题讲解1. 填空⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑与处理。

【解答】数据元素⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。

【解答】数据项，数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。

⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）与（）。

【解答】集合，线性结构，树结构，图结构⑷数据的存储结构主要有（）与（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）与（）。

【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。

【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性⑹算法的描述方法通常有（）、（）、（）与（）四种，其中，（）被称为算法语言。

【解答】自然语言，程序设计语言，流程图，伪代码，伪代码⑺在一般情况下，一个算法的时间复杂度是（）的函数。

【解答】问题规模⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。

【解答】Ο(1)，Ο(nlog2n)【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。

2. 选择题⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。

A 线性结构B 非线性结构C 存储位置D 指针【解答】C，D【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。

⑵假设有如下遗产继承规则：丈夫与妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。

则表示该遗产继承关系的最合适的数据结构应该是（）。

第2章线性表班级学号__________-姓名一、判断正误（）1. 链表的每个结点中都恰好包含一个指针。

（）2. 链表的物理存储结构具有同链表一样的顺序。

（）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各个单元向前移动。

（）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

（）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。

（）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

（）7. 线性表在物理存储空间中也一定是连续的。

（）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。

（）9. 顺序存储方式只能用于存储线性结构。

（）10. 线性表的逻辑顺序与存储顺序总是一致的。

二、单项选择题（）1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：（A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构（）2. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（A）110 （B）108 （C）100 （D）120（）3. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：（A）访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）（B）在第i个结点后插入一个新结点（1≤i≤n）（C）删除第i个结点（1≤i≤n）（D）将n个结点从小到大排序（）4. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素（A）8 （B）63.5 （C）63 （D）7（）5. 链接存储的存储结构所占存储空间：（A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针（B）只有一部分，存放结点值（C）只有一部分，存储表示结点间关系的指针（D）分两部分，一部分存放结点值，另一部分存放结点所占单元数（）6. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址:（A）必须是连续的（B）部分地址必须是连续的（C）一定是不连续的（D）连续或不连续都可以（）7．线性表Ｌ在情况下适用于使用链式结构实现。

第二章线性表习题一判断题1．线性表的逻辑顺序与存储顺序总是一致的。

2．顺序存储的线性表可以按序号随机存取。

3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。

4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。

5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。

6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。

7．线性表的链式存储结构优于顺序存储结构。

8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。

9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。

10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。

二单选题 (请从下列A，B，C，D选项中选择一项)1．线性表是( ) 。

(A) 一个有限序列，可以为空；(B) 一个有限序列，不能为空；(C) 一个无限序列，可以为空；(D) 一个无序序列，不能为空。

2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。

插入一个元素时平均要移动表中的（）个元素。

(A) n/2 (B) n+1/2 (C) n -1/2 (D) n3．线性表采用链式存储时，其地址( ) 。

(A) 必须是连续的；(B) 部分地址必须是连续的；(C) 一定是不连续的；(D) 连续与否均可以。

4．用链表表示线性表的优点是（）。

(A)便于随机存取 (B)花费的存储空间较顺序存储少(C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同5．某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( )存储方式最节省运算时间。

(A)单链表 (B)双链表 (C)单循环链表 (D)带头结点的双循环链表6．循环链表的主要优点是( )。

第一章一、填空题：1．数据结构是一门研究非数值计算程序设计中计算机的操作对象以及它们之间的关系和运算的学科。

2.从逻辑上可以把数据结构分为线性结构和非线性结构。

3．线性结构的顺序存储结构是一种随机存取的存储结构，线性结构的链式存储是一种顺序存取的存储结构。

4．线性结构中元素的关系是一对一，树形结构中元素的关系是一对多，图形结构中元素的关系是多对多。

5算法的5个重要特征是有穷性、确定性、可行性、输入、输出。

6 算法分析的两个主要方面是：时间复杂度和空间复杂度二、判断题：1、顺序存储方式只能用于线性结构、不能用于非线性结构。

×2、基于某种逻辑结构之上的运算，其实现是唯一的。

×3、数据元素是数据的最小单位。

×4、数据结构是带有结构的数据元素的集合。

√5、算法分析的目的是研究算法中的输入和输出的关系×三、分析以下程序段的时间复杂度：5．（1）i=1;k=100while(i<n){K=k+1;i+=10;}（2）i=1;j=0;while(i+j<=n)if(i>j) j++;else i++;（3）x=n;y=0;while(x>=(y+1)*(y+1))y++;（4）x=91;y=100;while(y>0)if(x>100){x-=10;y--}else x++;（5）for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+y;（1）O(n)（2）O(n)（3）O(n1/2)（4）O(1)（5）O(n3)第二章一、选择题：1．带头结点的单链表head为空的判断条件是（B）A.head=NULLB.head->next=NULLC.head->next=headD.head!=NULL2. 若在线性表中做以下两个操作:（1）在最后一个元素之后插入一个元素（2）删除第一个元素在（D）存储方式最节省时间：A. 单链表B. 单循环链表C. 双向链表D. 带尾指针的单循环链表3. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度为（C）。

第七章 线性变换练习题参考答案一、填空题1．设123,,εεε是线性空间V 的一组基，V 的一个线性变换σ在这组基下的矩阵是33112233(),,ij A a x x x V αεεε⨯==++∈则σ在基321,,εεε下的矩阵B ＝1,T AT -而可逆矩阵T ＝001010100⎛⎫ ⎪ ⎪ ⎪⎝⎭满足1,B T AT -=σα在基123,,εεε下的坐标为123x A x x ⎛⎫ ⎪ ⎪ ⎪⎝⎭ .2．设A 为数域P 上秩为r 的n 阶矩阵，定义n 维列向量空间n P 的线性变换:(),n A P σσξξξ=∈,则1(0)σ-＝{}|0,n A P ξξξ=∈，()1dim (0)σ-＝n r -，()dim ()n P σ＝r .3．复矩阵()ij n n A a ⨯=的全体特征值的和等于1nii i a =∑ ，而全体特征值的积等于||A .4．设σ是n 维线性空间V 的线性变换，且σ在任一基下的矩阵都相同，则σ为__数乘__变换 .5．数域P 上n 维线性空间V 的全体线性变换所成的线性空间()L V 为2n 维线性空间，它与n n P ⨯同构.6．设n 阶矩阵A 的全体特征值为12,,,n λλλ，()f x 为任一多项式，则()f A 的全体特征值为12(),(),,()n f f f λλλ . 7．设⎪⎪⎭⎫ ⎝⎛=2231A ，则向量⎪⎪⎭⎫ ⎝⎛11是A 的属于特征值 4 的特征向量． 8．若⎪⎪⎪⎭⎫ ⎝⎛--=100001011A 与1010101k B k ⎛⎫ ⎪=-- ⎪ ⎪⎝⎭相似，则k = -1/2 ． 9．设三阶方阵A 的特征多项式为322)(23+--=λλλλf ，则=||A 3 ．10．n 阶方阵A 满足A A =2，则A 的特征值为 0和1 ．11．线性空间3R 上的线性变换为A =),,(321x x x 132321(2,33,2)x x x x x x ++-，变换A 在基)1,0,0(),0,1,0(),0,0,1(321===εεε下的矩阵为102033210⎛⎫ ⎪ ⎪ ⎪-⎝⎭.二、判断题1．设σ是线性空间V 的一个线性变换，12,,,s V ααα∈线性无关，则向量组12(),(),,()s σασασα也线性无关. （错） 2．设σ为n 维线性空间V 的一个线性变换，则由σ的秩＋σ的零度＝n ，有1()(0).V V σσ-=⊕ （错）未必有1()(0).V V σσ-=⊕3．在线性空间2R 中定义变换σ：(,)(1,)x y x y σ=+，则σ是2R 的一个线性变换. （错）零向量的像是（1,0）4．若σ为n 维线性空间V 的一个线性变换，则σ是可逆的当且仅当1(0)σ-＝｛0｝. （正确）σ是可逆的当且仅当σ是双射.5．设σ为线性空间V 的一个线性变换，W 为V 的一个子集，若()W σ是V 的一个子空间，则W 必为V 的子空间. （错）如平面上的向量全体在x 轴上的投影变换，W 为终点在与x 轴平行而不重合的直线上的向量全体，()W σ为x 轴上的向量全体，是V 的一个子空间，但W 不是V 的子空间.6．n 阶方阵A 至少有一特征值为零的充分必要条件是0||=A ．（正确）7．已知1-=PBP A ，其中P 为n 阶可逆矩阵，B 为一个对角矩阵．则A 的特征向量与P 有关．（ 正确 ）1P AP B -=，P 的列向量为A 的特征向量.8．σ为V 上线性变换，n ααα,,,21 为V 的基，则)(,),(),(21n ασασασ 线性无关．（错）当σ可逆时无关，当σ不可逆时相关.9．α为V 上的非零向量，σ为V 上的线性变换，则})(|{)(1αησηασ==-是V 的子空间．（ 错 ）不含零向量.三、计算与证明1．判断矩阵A 是否可对角化？若可对角化，求一个可逆矩阵T ，使1T AT -成对角形.133313331A ⎛⎫ ⎪= ⎪ ⎪⎝⎭解：先求矩阵A 的特征值与特征向量.2133313(7)(2)331E A λλλλλλ----=---=-+---. 矩阵A 的特征值为12,37,2λλ==-.当17λ=时，解方程组1231231236330,3630,3360.x x x x x x x x x --=⎧⎪-+-=⎨⎪--+=⎩得矩阵A 属于特征值7的线性无关特征向量为1(1,1,1)'ξ=.当2,32λ=-时，解方程组1231231233330,3330,3330.x x x x x x x x x ---=⎧⎪---=⎨⎪---=⎩得矩阵A 属于特征值-2的线性无关特征向量为23(1,1,0)',(1,0,1)'ξξ=-=-.矩阵A 有三个线性无关的特征向量.因此矩阵A 可对角化，取矩阵111110101T ⎛⎫ ⎪=- ⎪ ⎪-⎝⎭有1722T AT -⎛⎫ ⎪=- ⎪ ⎪-⎝⎭2．在线性空间n P 中定义变换σ：122(,,,)(0,,,)n n x x x x x σ=（1）证明：σ是n P 的线性变换.（2）求()n P σ与1(0).σ-（1）证明：112222(,,,)(0,,,)n n n n x y x y x y x y x y σ+++=++ 221212(0,,,)(0,,,)(,,,)(,,,)n n n n x x y y x x x y y y σσ=+=+12122((,,,))(,,,)(0,,,)n n n k x x x kx kx kx kx kx σσ== 212(0,,,)(,,,)n n k x x k x x x σ==.所以σ是n P 的线性变换.（2）{}2()(0,,,)|,2,,.n n i P x x x P i n σ=∈=. {}111(0)(,0,,0)|.x x P σ-=∈3．设⎪⎪⎪⎭⎫ ⎝⎛----=a A 33242111与⎪⎪⎪⎭⎫ ⎝⎛=b B 00020002相似．（1）求b a ,的值；（2）求可逆矩阵，使B AP P =-1．解：(1)由矩阵A 与B 相似可得，矩阵A 与B 有相同的迹与行列式，因此有45,46 6.b a b a +=+⎧⎨=-⎩ 所以5,6a b ==.(2)先求矩阵A 的特征值与特征向量.2111||242(6)(2)335E A λλλλλλ---=--=--- 特征值为1,232,6λλ==.当1,22λ=时，解方程组1231231230,2220,3330.x x x x x x x x x +-=⎧⎪--+=⎨⎪+-=⎩得矩阵A 属于特征值-2的线性无关特征向量为12(0,1,1)',(1,0,1)'ξξ==.当16λ=时，解方程组12312312350,2220,330.x x x x x x x x x +-=⎧⎪-++=⎨⎪++=⎩得矩阵A 属于特征值7的线性无关特征向量为1(1,2,3)'ξ=-.因此可取矩阵011102113P ⎛⎫ ⎪=- ⎪ ⎪⎝⎭，有B AP P =-1.4．令n n P ⨯表示数域P 上一切n 级方阵所成的向量空间，取定,n n A B P ⨯∈，对任意的n n P X ⨯∈，定义()''X A XA B XB σ=-. 证明σ是n n P ⨯上的一个线性变换.证明：对任意的,,n n X Y P k P ⨯∈∈，有()'()'()''''()(),X Y A X Y A B X Y BA XAB XB A YA B YB X Y σσσ+=+-+=-+-=+()'()'()('')()kX A kX A B kX B k A XA B XB k X σσ=-=-=.因此σ是n n P ⨯上的一个线性变换.。

数据结构--线性表习题及答案第⼆章线性表⼀、选择题1、若长度为n的线性表采⽤顺序存储结构，在其第i个位置插⼊⼀个新元素算法的时间复杂度（）。

A. O(log2n)B.O(1)C. O(n)D.O(n2)2、若⼀个线性表中最常⽤的操作是取第i个元素和找第i个元素的前趋元素，则采⽤（）存储⽅式最节省时间。

A. 顺序表B. 单链表C. 双链表D. 单循环链表3、具有线性结构的数据结构是（）。

A. 图B. 树C. ⼴义表D.栈4、在⼀个长度为n的顺序表中，在第i个元素之前插⼊⼀个新元素时，需向后移动（）个元素。

A. n-iB. n-i+1C. n-i-1D. i5、⾮空的循环单链表head的尾结点p满⾜（）。

A. p->next==headB. p->next==NULLC. p==NULLD. p==head6、链表不具有的特点是（）。

A. 可随机访问任⼀元素B. 插⼊删除不需要移动元素C. 不必事先估计存储空间D. 所需空间与线性表长度成正⽐7、在双向循环链表中，在p指针所指的结点后插⼊⼀个指针q所指向的新结点，修改指针的操作是（）。

A. p->next=q;q->prior=p;p->next->prior=q;q->next=q;B. p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;C. q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;D. q->next=p->next;q->prior=p;p->next=q;p->next=q;8、线性表采⽤链式存储时，结点的存储地址（）。

A. 必须是连续的B. 必须是不连续的C. 连续与否均可D. 和头结点的存储地址相连续9、在⼀个长度为n的顺序表中删除第i个元素，需要向前移动（）个元素。

习题41.名词解释：串、空串、空格串、子串。

解：串是有限的字符序列，从数据结构角度讲，串属于线性结构。

与线性表的不同之处在于串的元素是字符。

空串是不含任何字符的串，其长度为0。

空格是一个字符，其ASCII 码值是32。

空格串是由空格组成的串，其长度等于空格的个数。

串中任意连续的若干字符组成的子序列称为该串的子串。

2.已知三个字符串分别为”“a abcaabcbca ab S =，”“caab S ='，”“bcb S ="。

利用串的基本运算得到结果串为”“a aca caabcbca S ='"，要求写出得到结果串3S 所用的函数及执行算法。

解：串'"S 可看作由以下两部分组成：”“a caabcbca 和”“a ca ，设这两部分分别叫串s1和s2，要设法从S 、'S 、"S 中得到这两部分，然后使用连接操作连接s1和s2得到'"S 。

i=index();//s1=substr(S ,i,length(S )-i+1);//取出串s1j=index(S ,"S );//求串"S 在串S 中的起始位置，S 串中”“bcb 后是”“a cas2=substr(S ,j+3,length(S )-j-2);//形成串s2'"S =concat(s1,s2);3.已知字符串1S 中存放一段英文，写出算法),3,2,1(n S S S format ，将其按给定的长度n 格式化成两端对齐的字符串2S ，其多余的字符存入3S 。

解：题目要求将字符串S1拆分成字符串S2和S3，要求字符串S2“按给定长度n 格式化为两端对齐的字符串”，即长度为n 且首尾字符不能为空格字符。

算法从左到右扫描字符串S1，找到第一个非空格字符，计数到n ，第n 个拷入字符串S2的字符不能为空格，然后将余下字符复制到字符串S3中。

第1章 概述【例1-1】分析以下程序段的时间复杂度。

for(i=0;i<n;i++)for(j=0;j<m;j++)A[i][j]=0; 解：该程序段的时间复杂度为O (m*n )。

【例1-2】分析以下程序段的时间复杂度。

i=s=0; ①while(s<n){ i++; ② s+=i; ③}解：语句①为赋值语句，其执行次数为1次，所以其时间复杂度为O (1)。

语句②和语句③构成while 循环语句的循环体，它们的执行次数由循环控制条件中s 与n 的值确定。

假定循环重复执行x 次后结束， 则语句②和语句③各重复执行了x 次。

其时间复杂度按线性累加规则为O (x )。

此时s 与n 满足关系式：s ≥n ，而s=1+2+3+…+x 。

所以有：1+2+3+…+x ≥n ，可以推出： x=n n 241212811+±-=+±-x 与n 之间满足x=f(n ），所以循环体的时间复杂度为O (n )，语句①与循环体由线性累加规则得到该程序段的时间复杂度为O (n ）。

【例1-3】分析以下程序段的时间复杂度。

i=1; ①while(i<=n)i=2*i; ②解：其中语句①的执行次数是1，设语句②的执行次数为f (n )，则有：n n f ≤)(2。

得：T （n ）=O (n 2log )【例1-4】有如下递归函数fact (n )，分析其时间复杂度。

fact(int n){ if(n<=1)return(1); ①elsereturn(n*fact(n-1)); ②} 解：设fact （n ）的运行时间函数是T (n )。

该函数中语句①的运行时间是O (1)，语句②的运行时间是T (n-1)+ O (1)，其中O (1)为常量运行时间。

由此可得fact（n）的时间复杂度为O(n)。

习题1一、单项选择题1.数据结构是指（1. A ）。

A.数据元素的组织形式B.数据类型C.数据存储结构D.数据定义2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（2. C ）。

第二章线性表一、选择题1.线性表是（）A．一个有限序列，可以为空B．一个有限序列，不可以为空C．一个无限序列，可以为空D．一个无限序列，不可以为空2.一维数组与线性表的特征是（）。

A．前者长度固定，后者长度可变B．两者长度均固定C．后者长度固定，前者长度可变D．两者长度均可变3.用单链表方式存储的线性表，存储每个结点需要两个域，一个数据域，另一个是( ).A．当前结点所在地址域B．指针域C．空指针域D．空闲域4.用链表表示线性表的优点是（）。

A．便于随机存取B．便于进行插入和删除操作C．占用的存储空间较顺序表少D．元素的物理顺序与逻辑顺序相同5.在具有 n 个结点的单链表中，实现___的操作，其算法的时间复杂度都是O（n）。

A．遍历链表和求链表的第i个结点D．删除地址为P的结点的后继结点B．在地址为P的结点之后插入一个结点 C．删除开始结点6.下面关于线性表的叙述中，错误的是（）。

A．线性表采用顺序存储必须占用一片连续的存储单元B．线性表采用顺序存储便于进行插入和删除操作C．线性表采用链式存储不必占用一片连续的存储单元D．线性表采用链式存储便于进行插入和删除操作7.已知单链表的每个结点包括一个指针域next，它指向该结点的后继结点。

现要将指针 q 指向的新结点插入到指针 p 指向的结点之后，下面的操作序列中正确的是（）。

A . q = p->next; p->next = q->next ;B . p->next = q->next; q = p->next ;C . q->next = p->next; p->next = q ;D . p->next = q; q->next = p->next ;8.设 a l，a2， a3为三个结点； p , 10 , 20 代表地址，则如下的链表存储结构称为（）。

A．链表B．单链表C．双向循环链表D．双向链表9.单链表的存储密度（）。

第三章 静定结构的位移计算一、判断题：1、虚位移原理等价于变形谐调条件，可用于求体系的位移。

2、按虚力原理所建立的虚功方程等价于几何方程。

3、在非荷载因素(支座移动、温度变化、材料收缩等)作用下，静定结构不产生内力，但会有位移且位移只与杆件相对刚度有关。

4、求图示梁铰C 左侧截面的转角时，其虚拟状态应取：A.;; B.D.C.=1=15、功的互等、位移互等、反力互等和位移反力互等的四个定理仅适用于线性变形体系。

6、已知M p 、M k 图，用图乘法求位移的结果为：()/()ωω1122y y EI +。

M k M p 21y 1y 2**ωω( a )M =17、图a 、b 两种状态中，粱的转角ϕ与竖向位移δ间的关系为：δ=ϕ 。

8、图示桁架各杆E A 相同，结点A 和结点B 的竖向位移均为零。

a a9、图示桁架各杆EA =常数，由于荷载P 是反对称性质的，故结点B 的竖向位移等于零。

二、计算题：10、求图示结构铰A 两侧截面的相对转角ϕA ，EI = 常数。

q l l l /211、求图示静定梁D 端的竖向位移 ∆DV 。

EI = 常数 ，a = 2m 。

a a a 10kN/m12、求图示结构E 点的竖向位移。

EI = 常数 。

l l l /3 2 /3/3q13、图示结构，EI=常数 ，M =⋅90kN m , P = 30kN 。

求D 点的竖向位移。

P 3m 3m 3m14、求图示刚架B 端的竖向位移。

ql15、求图示刚架结点C 的转角和水平位移，EI = 常数 。

q16、求图示刚架中Ｄ点的竖向位移。

EI ＝常数。

l/217、求图示刚架横梁中Ｄ点的竖向位移。

EI＝常数。

18、求图示刚架中D点的竖向位移。

E I = 常数。

qll l/219、求图示结构Ａ、Ｂ两截面的相对转角，EI＝常数。

l/23l/320、求图示结构A、B两点的相对水平位移，E I = 常数。

ll21、求图示结构B点的竖向位移，EI = 常数。

数据结构第二章习题第2章线性表一、单项选择题1．线性表就是具备n个_________的非常有限序列。

a．表元素b．字符c．数据元素d．数据项2．线性表是_________。

a．一个非常有限序列，可以为空b．一个非常有限序列，不可以为空c．一个无穷序列，可以为空d．一个无穷序列，不可以为空3．线性表使用链表存储时，其地址_________。

a．必须是连续的b．一定是不连续的c．部分地址必须是连续的d．连续与否均可以4．链表不具备的特点是_________。

a．可以随机出访任一结点b．填入删掉不须要移动元素c．不必事先估算存储空间d．所须要空间与其长度成正比5．设立线性表存有n个元素，以下操作方式中，_________在顺序单上同时实现比在链表上同时实现效率更高。

a．输出第i(1≤i≤n)个元素值b．互换第1个元素与第2个元素的值c．顺序输入这n个元素的值d．输出与给定值x相等的元素在线性表中的序号6．设立线性表中存有2n个元素，以下操作方式中，_________在单链单上同时实现Obrero在顺序单上同时实现效率更高。

a．删掉选定的元素b．在最后一个元素的后面插入一个新元素c．顺序输出前k个元素d．互换第i个元素和第2n-i-1个元素的值(i=0,1…,n-1)7．如果最常用的操作是取第i个结点及其前驱，则采用_________存储方式最节省时间。

a．单链表中b．双链表中c．单循环链表d．顺序表8．与单链表相比，双链表的优点之一是_________。

a．填入和删掉操作方式更直观b．可以展开随机出访c．可以省略字段指针或表尾指针d．出访前后相连结点更有效率9．率先垂范结点的单链表中l为觑的认定条件就是_________。

a．l==nullb．l->next==nullc．l->next==ld．l!=null10．在一个具备n个结点的有序单链表填入一个崭新结点并仍然维持有序的时间复杂度就是_________。

数据结构第二章线性表习题含答案说明：顺序存储的线性表称为向量。

一,单项选择题一个向量第一个元素的地址是100，每个元素的长度为2，则第5个元素的地址是__①_B__。

A) 110 B) 108 C) 100 D) 120线性结构通常采用的两种存储结构是__①A___。

A) 顺序存储结构和链式存储结构B) 散列方式和索引方式C) 链表存储结构和数组D) 线性存储结构和非线性存储结构不带头结点的单链表head为空的判定条件是__①__A_.A) head==NULL B) head->next==NULLC) head->next==head D) head!=NULL带头结点的单链表head为空的判定条件是__①B___。

A) head==NULL B) head->next==NULLC) head->next==head D) head!=NULL非空的循环链表head的尾结点（由p所指向）满足__①_C__。

A) p->next==NULL B) p==NULLC) P->next==head D) p==head在循环双链表的p所指结点之后插入s所指结点的操作是___①_C_。

A) p->right=s; s->left=p; p->right->left=s; s->right=p->right;B) p->right=s; p->right->left=s; s->left=p; s->right=p->right;C) s->left=p; s->right=p->right; p->right=s; p->right->left=s;D) s->left=p; s->right=p->right; p->right->left=s; p->right=s;在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点, 则执行__①c___。

第一章绪论一、填空题1、数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。

2、数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的关系有限集合。

3、数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。

4、数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。

5、线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。

6、在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。

7、在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。

8、在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。

9、数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。

10、数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。

11、一个算法的效率可分为时间效率和空间效率。

二、单项选择题（B）1、非线性结构是数据元素之间存在一种：A）一对多关系B）多对多关系C）多对一关系D）一对一关系（ C ）2、数据结构中，与所使用的计算机无关的是数据的结构；A) 存储B) 物理C) 逻辑D) 物理和存储（C）3、算法分析的目的是：A) 找出数据结构的合理性B) 研究算法中的输入和输出的关系C) 分析算法的效率以求改进D) 分析算法的易懂性和文档性（A）4、算法分析的两个主要方面是：A) 空间复杂性和时间复杂性B) 正确性和简明性C) 可读性和文档性D) 数据复杂性和程序复杂性（ C ）5、计算机算法指的是：A) 计算方法B) 排序方法C) 解决问题的有限运算序列D) 调度方法（B）6、计算机算法必须具备输入、输出和等5个特性。

第2章线性表一、选择题1.表长为N 的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（E ），删除一个元素需要移动的元素个数为（A ）。

A. (N-1)/2B. NC. N+1D. N-1E. N/2F. (N+1)/2G. (N-2)/22.线性表是具有N 个（C ）的有限序列。

A、表元素B、字符C、数据元素D、数据项E、信息3.“线性表的逻辑顺序和物理顺序总是一致的。

”这个结论是（B ）。

A、正确的B、错误的C、不一定，与具体结构有关。

4.线性表采用链式存储结构时，要求内存中可用存储单元的地址（D ）。

A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、连续或不连续都可以。

5.带头结点的单链表为空的判定条件是（B ）。

A、head==NULLB、head->next==NULLC、head->next==headD、head!=NULL6.不带头结点的单链表head 为空的判定条件是（A ）。

A、head==NULLB、head->next==NULLC、head->next==headD、head!=NULL7.非空的循环单链表head 的尾结点P 满足（ C ）。

A、P->NEXT=NULLB、p=NULLC、p->next==headD、p==head8.在一个具有n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（B ）。

A、O(1)B、O(n)C、O(n2)D、O(nlog2n)9.在一个单链表中，若删除P 所指结点的后继结点，则执行（ A ）。

A、p->next=p->next->nextB、p=p->next;p->next=p->next->nextC、p->next=p->next;D、p=p->next->next;10.在一个单链表中，若在Ｐ所指结点之后插入Ｓ所指结点，则执行（B ）。

第二章作业题1．求单链表中当前结点的后继和前驱的时间复杂度分别是（）A．O（n）和O（1）B．O（1）和O（1）C．O（1）和O（n）D．O(n)和O（n）2．非空的单循环链表的头指针为head,尾指针为rear，则下列条件成立的是（）A．rear->next= =head B．rear->next->next= =headC．head->next= =rear D．head->next->next= =rear3．在带头结点的循环链表L中，结点的数据元素为整型，且按值递增有序存放。

给定两个整数a和b，且a<b，编写算法删除链表L中元素值大于a且小于b的所有结点。

4．在线性表的下列运算中，不．改变数据元素之间结构关系的运算是（）A．插入B．删除C．排序D．定位5.已知指针p和q分别指向某单链表中第一个结点和最后一个结点。

假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为( ) A.q->next=s->next；s->next=p； B.s->next=p；q->next=s->next；C.p->next=s->next；s->next=q；D.s->next=q；p->next=s->next；6．若线性表的插入和删除操作频繁地在表头或表尾位置进行，则更适宜采用的存储结构为（）A．无头结点的双向链表B．带尾指针的循环链表C．无头结点的单链表D．带头指针的循环链表7.在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是（）A.访问第i个元素的前驱（1<ni≤）B.在第i个元素之后插入一个新元素(n1≤≤)iC.删除第i个元素(n≤)i1≤D.对顺序表中元素进行排序8.在链表的结点中，数据元素所占的存储量和整个结点所占的存储量之比称作________。