目前最完整的数据结构1800题包括完整答案 第五章 数组和广义表

数据结构1800例题与答案第一章绪论一、选择题（每小题2分）1．算法的计算量的大小称为计算的（ B ）。

【北京邮电大学2000 二、3 （20/8分）】A．效率B．复杂性C．现实性D．难度2．算法的时间复杂度取决于（C）。

【中科院计算所1998 二、1 （2分）】A．问题的规模B．待处理数据的初态C．A和B D．都不是3．计算机算法指的是（①C ），它必须具备（② B ）这三个特性。

①A．计算方法B．排序方法C．解决问题的步骤序列D．调度方法②A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性C．确定性、有穷性、稳定性D．易读性、稳定性、安全性【南京理工大学1999 一、1（2分）【武汉交通科技大学1996 一、1（4分）】4．一个算法应该是（B ）。

【中山大学1998 二、1（2分）】A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C.5．下面关于算法说法错误的是（ D ）【南京理工大学2000 一、1（1.5分）】A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（C ）【南京理工大学2000 一、2 （1.5分）】(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（ C ）两大类。

【武汉交通科技大学1996 一、4（2分）】A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（ D ）。

【北方交通大学2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈9．以下数据结构中，哪一个是线性结构（ D ）？【北方交通大学2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串10．以下那一个术语与数据的存储结构无关？（Ａ）【北方交通大学2001 一、2（2分）】A．栈 B. 哈希表 C. 线索树 D. 双向链表11．在下面的程序段中，对x的赋值语句的频度为（Ｃ）【北京工商大学2001 一、10（3分）】FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A．O(2n) B．O(n) C．O(n2) D．O(log2n)12．程序段FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与A[j+1]对换；其中n为正整数，则最后一行的语句频度在最坏情况下是（Ｄ）A. O（n）B. O(nlogn)C. O(n3)D. O(n2) 【南京理工大学1998一、1(2分)】13．以下哪个数据结构不是多型数据类型（Ｄ）【中山大学1999 一、3（1分）】A．栈B．广义表C．有向图D．字符串14．以下数据结构中，（Ａ）是非线性数据结构【中山大学1999 一、4】A．树B．字符串C．队D．栈15. 下列数据中，（Ｃ）是非线性数据结构。

第一章概论一、选择题1、研究数据结构就是研究（D ）。

A. 数据的逻辑结构B。

数据的存储结构C. 数据的逻辑结构和存储结构D。

数据的逻辑结构、存储结构及其基本操作2、算法分析的两个主要方面是（ A ）。

A。

空间复杂度和时间复杂度 B. 正确性和简单性C。

可读性和文档性D。

数据复杂性和程序复杂性3、具有线性结构的数据结构是（ D ）。

A。

图B。

树C。

广义表D。

栈4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、( B )等5个特性。

A. 可执行性、可移植性和可扩充性B。

可执行性、有穷性和确定性C。

确定性、有穷性和稳定性 D. 易读性、稳定性和确定性5、下面程序段的时间复杂度是（ C )。

for(i=0；i<m;i++）for(j=0;j〈n；j++）a[i］[j]=i＊j；A. O(m2) B。

O（n2) C。

O（m*n) D. O（m+n)6、算法是（D ）。

A。

计算机程序 B. 解决问题的计算方法C。

排序算法 D. 解决问题的有限运算序列7、某算法的语句执行频度为（3n+nlog2n+n2+8），其时间复杂度表示( C ）。

A。

O（n） B. O（nlog2n) C。

O（n2） D. O （log2n)8、下面程序段的时间复杂度为（ C ）.i=1；while(i<=n）i=i*3；A. O(n）B。

O(3n) C。

O(log3n) D. O(n3）9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（）和运算等的学科。

A. 结构B。

关系C。

运算D。

算法10、下面程序段的时间复杂度是（A ）。

i=s=0；while（s<n)｛i++；s+=i;}A. O(n) B。

O（n2）C。

O（log2n）D。

O(n3)11、抽象数据类型的三个组成部分分别为（A）。

A. 数据对象、数据关系和基本操作B. 数据元素、逻辑结构和存储结构C. 数据项、数据元素和数据类型D. 数据元素、数据结构和数据类型12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量，以下解释错误的是（)。

第6章树和二叉树部分答案解释如下。

12. 由二叉树结点的公式：n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1，因为n=1001,所以1002=2n0+n1,在完全二叉树树中，n1只能取0或1,在本题中只能取0，故n=501，因此选E。

42.前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树，所以本题的A和B均对，单支树的特点是只有一个叶子结点，故C是最合适的，选C。

A或B 都不全。

由本题可解答44题。

47. 左子树为空的二叉树的根结点的左线索为空（无前驱），先序序列的最后结点的右线索为空（无后继），共2个空链域。

52．线索二叉树是利用二叉树的空链域加上线索，n个结点的二叉树有n+1个空链域。

部分答案解释如下。

6．只有在确定何序（前序、中序、后序或层次）遍历后，遍历结果才唯一。

19．任何结点至多只有左子树的二叉树的遍历就不需要栈。

24. 只对完全二叉树适用，编号为i的结点的左儿子的编号为2i(2i<=n)，右儿子是2i+1（2i+1<=n）37. 其中序前驱是其左子树上按中序遍历的最右边的结点（叶子或无右子女），该结点无右孩子。

38 . 新插入的结点都是叶子结点。

42. 在二叉树上，对有左右子女的结点，其中序前驱是其左子树上按中序遍历的最右边的结点（该结点的后继指针指向祖先），中序后继是其右子树上按中序遍历的最左边的结点（该结点的前驱指针指向祖先）。

44．非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索和后继线索为空指针。

三.填空题1.(1)根结点(2)左子树(3)右子树2.(1)双亲链表表示法(2)孩子链表表示法(3)孩子兄弟表示法3．p->lchild==null && p->rchlid==null 4.(1) ++a*b3*4-cd (2)18 5.平衡因子6. 97. 128.(1)2k-1 (2)2k-19.(1)2H-1 (2)2H-1(3)H=⎣log2N⎦+110. 用顺序存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结点”。

一、选择题1. 算法的计算量的大小称为计算的（B ）。

【北京邮电大学2000 二、3 （20/8分）】A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（C ）【中科院计算所1998 二、1 （2分）】A．问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是（1），它必须具备（2）这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性【南京理工大学1999 一、1（2分）【武汉交通科技大学1996 一、1（4分）】4．一个算法应该是（）。

【中山大学1998 二、1（2分）】A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A 和C.5. 下面关于算法说法错误的是（）【南京理工大学2000 一、1（1.5分）】A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（）【南京理工大学2000 一、2 （1.5分）】(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（）两大类。

【武汉交通科技大学1996 一、4（2分）】A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（）。

【北方交通大学2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈9．以下数据结构中，哪一个是线性结构（）？【北方交通大学2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串10．以下那一个术语与数据的存储结构无关？（）【北方交通大学2001 一、2（2分）】A．栈 B. 哈希表 C. 线索树 D. 双向链表11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学2001 一、10（3分）】FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1。

第五章数组和广义表答案部分答案解释如下。

1. 错误。

对于完全二叉树，用一维数组作存储结构是效率高的（存储密度大）。

4. 错误。

数组是具有相同性质的数据元素的集合，数据元素不仅有值，还有下标。

因此，可以说数祖是元素值和下标构成的偶对的有穷集合。

5. 错误。

数组在维数和界偶确定后，其元素个数已经确定，不能进行插入和删除运算。

6. 错误。

稀疏矩阵转置后，除行列下标及行列数互换外，还必须确定该元素转置后在新三元组中的位置。

8. 错误。

广义表的取表尾运算，是非空广义表除去表头元素，剩余元素组成的表，不可能是原子。

9. 错误。

广义表的表头就是广义表的第一个元素。

只有非空广义表才能取表头。

10. 错误。

广义表中元素可以是原子，也可以是表（包括空表和非空表）。

11. 错误。

广义表的表尾，指去掉表头元素后，剩余元素所组成的表。

三、填空题1. 顺序存储结构2.（1）9572（2）12283.（1）9174（2）87884. 11005. 1164 公式：LOC(a ijk)=LOC(a000)+[v2*v3*(i-c1)+v3*(j-c2)+(k-c3)]*l (l为每个元素所占单元数)6. 2327. 13408. 11969. 第1行第3列10. (1)270 (2)27 (3)2204 11. i(i-1)/2+j (1<=i,j<=n)12. (1)n(n+1)/2 (2)i(i+1)/2 (或j(j+1)/2) (3)i(i-1)/2+j (4)j(j-1)/2+i (1<=i,j<=n)13. 1038 三对角矩阵按行存储：k=2(i-1)+j (1<=i,j<=n)14. 33 (k=i(i-1)/2+j) (1<=i,j<=n)15. 非零元很少(t<<m*n)且分布没有规律 16. 节省存储空间。

17. 上三角矩阵中，主对角线上第r(1≤r≤n) 行有n-r+1个元素，a ij所在行的元素数是j-i+1。

数据结构考试试题库含答案解析数据结构习题集含答案⽬录⽬录 (1)选择题 (2)第⼀章绪论 (2)第⼆章线性表 (4)第三章栈和队列 (6)第四章串 (7)第五章数组和⼴义表 (8)第六章树和⼆叉树 (8)第七章图 (11)第⼋章查找 (13)第九章排序 (14)简答题 (19)第⼀章绪论 (19)第⼆章线性表 (24)第三章栈和队列 (26)第四章串 (28)第五章数组和⼴义表 (29)第六章树和⼆叉树 (31)第七章图 (36)第⼋章查找 (38)第九章排序 (39)编程题 (41)第⼀章绪论 (41)第⼆章线性表 (41)第三章栈和队列 (52)第四章串 (52)第五章数组和⼴义表 (52)第六章树和⼆叉树 (52)第七章图 (52)第⼋章查找 (52)第⼀章绪论1.数据结构这门学科是针对什么问题⽽产⽣的？（A ）A、针对⾮数值计算的程序设计问题B、针对数值计算的程序设计问题C、数值计算与⾮数值计算的问题都针对D、两者都不针对2.数据结构这门学科的研究内容下⾯选项最准确的是（D ）A、研究数据对象和数据之间的关系B、研究数据对象C、研究数据对象和数据的操作D、研究数据对象、数据之间的关系和操作3.某班级的学⽣成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那么下⾯关于数据对象、数据元素、数据项描述正确的是（C ）A、某班级的学⽣成绩表是数据元素，90分是数据项B、某班级的学⽣成绩表是数据对象，90分是数据元素C、某班级的学⽣成绩表是数据对象，90分是数据项D、某班级的学⽣成绩表是数据元素，90分是数据元素4.*数据结构是指（A ）。

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

A、存储结构B、逻辑结构C、链式存储结构D、顺序存储结构6.算法分析的⽬的是（C ）A、找出数据的合理性B、研究算法中的输⼊和输出关系C、分析算法效率以求改进D、分析算法的易懂性和⽂档型性7.算法分析的主要⽅法（A ）。

习题五数组和广义表一、单项选择题1．常对数组进行的两种基本操作是（）A.建立与删除B. 索引与修改C. 查找与修改D. 查找与索引2．对于C语言的二维数组DataType A[m][n],每个数据元素占K个存储单元，二维数组中任意元素a[i,j] 的存储位置可由( )式确定.A.Loc[i,j]=A[m,n]+[(n+1)*i+j]*kB.Loc[i,j]=loc[0,0]+[(m+n)*i+j]*kC.Loc[i,j]=loc[0,0]+[(n+1)*i+j]*kD.Loc[i,j]=[(n+1)*i+j]*k3．稀疏矩阵的压缩存储方法是只存储 ( )A.非零元素B. 三元祖（i,j, aij）C. aijD. i,j4. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。

A. 1175B. 1180C. 1205D. 12105. A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（）。

A. i（i-1）/2+jB. j（j-1）/2+iC. i（j-i）/2+1D. j（i-1）/2+16. 用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j 沿链移动的操作为( )。

A. j=r[j].nextB. j=j+1C. j=j->nextD. j=r[j]-> next7. 对稀疏矩阵进行压缩存储目的是（）。

A．便于进行矩阵运算 B．便于输入和输出C．节省存储空间 D．降低运算的时间复杂度8. 已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是( )。

A. head(tail(LS))B. tail(head(LS))C. head(tail(head(tail(LS)))D. head(tail(tail(head(LS))))9. 广义表（（a,b,c,d））的表头是（），表尾是（）。

数据结构1800试题第5章数组和广义表数据结构1800试题-第5章数组和广义表一、多项选择题1.设有一个10阶的对称矩阵a，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。

【燕山大学2001一、2（2分）】a、 13b。

33c。

18d。

402.有一个二维数组a[1:6，0:7]每个数组元素存储有六个相邻的字节，内存按字节寻址，所以这个数组的容量是(①) 字节。

假设存储数组元素a[1，0]的第一个字节的地址为0，则存储数组a的最后一个元素的第一个字节的地址为(②). 如果按行存储，则[2，4]的第一个字节的地址为(③). 如果按列存储，则[5,7]的第一个字节的地址为(④). 一般来说(⑤), 按行存储的a[I，J]地址等于按列存储的a[J，I]地址。

备选答案：[上海海事学院1998 II，2（5分）]①-④：a．12b.66c.72d.96e.114f.120g、 156h。

234i。

276j。

282k。

283l。

二百八十八⑤：a．行与列的上界相同b.行与列的下界相同c、行和列的上限和下限相同。

D.行中的元素数与列中的元素数相同3.设有数组a[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址ba开始顺序存放，当用以列为主存放时，元素a[5，8]的存储首地址为()。

a、 ba+141b。

ba+180摄氏度。

ba+222d。

Ba+225[南京大学，1997年1，8（2分）]4.假设以行序为主序存储二维数组a=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则loc[5，5]=（）。

【福州大学1998一、10(2分)】a.808b.818c.1010d.10205.数组a[0..5,0..6]的每个元素占用五个字节，并根据列优先级以1000的起始地址存储在内存单元中，则元素a[5,5]的地址为（）。

数据结构1800例题与答案第一章绪论一、选择题（每小题2分）1．算法的计算量的大小称为计算的（ B ）。

【北京邮电大学2000 二、3 （20/8分）】A．效率B．复杂性C．现实性D．难度2．算法的时间复杂度取决于（C）。

【中科院计算所1998 二、1 （2分）】A．问题的规模B．待处理数据的初态C．A和B D．都不是3．计算机算法指的是（①C ），它必须具备（② B ）这三个特性。

①A．计算方法B．排序方法C．解决问题的步骤序列D．调度方法②A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性C．确定性、有穷性、稳定性D．易读性、稳定性、安全性【南京理工大学1999 一、1（2分）【武汉交通科技大学1996 一、1（4分）】4．一个算法应该是（B ）。

【中山大学1998 二、1（2分）】A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C.5．下面关于算法说法错误的是（ D ）【南京理工大学2000 一、1（1.5分）】A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（C ）【南京理工大学2000 一、2 （1.5分）】(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（ C ）两大类。

【武汉交通科技大学1996 一、4（2分）】A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（ D ）。

【北方交通大学2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈9．以下数据结构中，哪一个是线性结构（ D ）？【北方交通大学2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串10．以下那一个术语与数据的存储结构无关？（Ａ）【北方交通大学2001 一、2（2分）】A．栈 B. 哈希表 C. 线索树 D. 双向链表11．在下面的程序段中，对x的赋值语句的频度为（Ｃ）【北京工商大学2001 一、10（3分）】FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A．O(2n) B．O(n) C．O(n2) D．O(log2n)12．程序段FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与A[j+1]对换；其中n为正整数，则最后一行的语句频度在最坏情况下是（Ｄ）A. O（n）B. O(nlogn)C. O(n3)D. O(n2) 【南京理工大学1998一、1(2分)】13．以下哪个数据结构不是多型数据类型（Ｄ）【中山大学1999 一、3（1分）】A．栈B．广义表C．有向图D．字符串14．以下数据结构中，（Ａ）是非线性数据结构【中山大学1999 一、4】A．树B．字符串C．队D．栈15. 下列数据中，（Ｃ）是非线性数据结构。

《数据结构》第五章习题参考答案一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”）1、知道一颗树的先序序列和后序序列可唯一确定这颗树。

( ×)2、二叉树的左右子树可任意交换。

（×）3、任何一颗二叉树的叶子节点在先序、中序和后序遍历序列中的相对次序不发生改变。

（√）4、哈夫曼树是带权路径最短的树，路径上权值较大的结点离根较近。

（√）5、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。

( ×)6、完全二叉树中，若一个结点没有左孩子，则它必是叶子结点。

( √)7、一棵树中的叶子数一定等于与其对应的二叉树的叶子数。

（×）8、度为2的树就是二叉树。

（×）二、单项选择题1．具有10个叶结点的二叉树中有（ B ）个度为2的结点。

A．8 B．9 C．10 D．112．树的后根遍历序列等同于该树对应的二叉树的( B )。

A. 先序序列B. 中序序列C. 后序序列3、二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历：HFIEJKG 。

该二叉树根的右子树的根是：( C )A. EB. FC. GD. H04、在下述结论中，正确的是（ D ）。

①具有n个结点的完全二叉树的深度k必为┌log2(n+1)┐；②二叉树的度为2；③二叉树的左右子树可任意交换；④一棵深度为k(k≥1)且有2k-1个结点的二叉树称为满二叉树。

A．①②③B．②③④C．①②④D．①④5、某二叉树的后序遍历序列与先序遍历序列正好相反，则该二叉树一定是（ D ）。

A．空或只有一个结点B．完全二叉树C．二叉排序树D．高度等于其结点数三、填空题1、对于一棵具有n个结点的二叉树，对应二叉链接表中指针总数为__2n____个，其中___n-1_____个用于指向孩子结点，___n+1___个指针空闲着。

2、一棵深度为k(k≥1)的满二叉树有_____2k-1______个叶子结点。

一、选择题1. 算法的计算量的大小称为计算的（B ）。

【北京邮电大学2000 二、3 （20/8分）】A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（C ）【中科院计算所1998 二、1 （2分）】A．问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是（1），它必须具备（2）这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性【南京理工大学1999 一、1（2分）【武汉交通科技大学1996 一、1（4分）】4．一个算法应该是（）。

【中山大学1998 二、1（2分）】A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A 和C.5. 下面关于算法说法错误的是（）【南京理工大学2000 一、1（1.5分）】A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（）【南京理工大学2000 一、2 （1.5分）】(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（）两大类。

【武汉交通科技大学1996 一、4（2分）】A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（）。

【北方交通大学2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈9．以下数据结构中，哪一个是线性结构（）？【北方交通大学2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串10．以下那一个术语与数据的存储结构无关？（）【北方交通大学2001 一、2（2分）】A．栈 B. 哈希表 C. 线索树 D. 双向链表11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学2001 一、10（3分）】FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A．O(2n) B．O(n) C．O(n2) D．O(log2n)12．程序段FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与A[j+1]对换；其中n为正整数，则最后一行的语句频度在最坏情况下是（）A. O（n）B. O(nlogn)C. O(n3)D. O(n2) 【南京理工大学1998一、1(2分)】13．以下哪个数据结构不是多型数据类型（）【中山大学1999 一、3（1分）】A．栈B．广义表C．有向图D．字符串14．以下数据结构中，（）是非线性数据结构【中山大学1999 一、4】A．树B．字符串C．队D．栈15. 下列数据中，（）是非线性数据结构。

第五章习题5.1 假设有6行8列的二维数组A，每个元素占用6个字节，存储器按字节编址。

已知A的基地址为1000，计算：数组A共占用多少字节；数组A的最后一个元素的地址；按行存储时元素A36的地址；按列存储时元素A36的地址；5.2 设有三对角矩阵An×n ,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得B[k]= aij，求：（1）用i,j表示k的下标变换公式；（2）用k表示i,j的下标变换公式。

5.3假设稀疏矩阵A和B均以三元组表作为存储结构。

试写出矩阵相加的算法，另设三元组表C存放结果矩阵。

5.4在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法只占用一个辅助向量空间。

5.5写一个在十字链表中删除非零元素aij的算法。

5.6画出下面广义表的两种存储结构图示：((((a), b)), ((( ), d), (e, f)))5.7求下列广义表运算的结果：（1）HEAD[((a,b),(c,d))];（2）TAIL[((a,b),(c,d))];（3）TAIL[HEAD[((a,b),(c,d))]];（4）HEAD[TAIL[HEAD[((a,b),(c,d))]]];（5）TAIL[HEAD[TAIL[((a,b),(c,d))]]];实习题若矩阵Am×n 中的某个元素aij是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵中的一个马鞍点。

假设以二维数组存储矩阵，试编写算法求出矩阵中的所有马鞍点。

第五章答案5.2设有三对角矩阵A n×n,将其三条对角线上的元素逐行的存于数组B[1..3n-2]中，使得B[k]=a ij，求：（1）用i,j表示k的下标变换公式；（2）用k表示i、j的下标变换公式。

【解答】（1）k=2(i-1)+j(2) i=[k/3]+1, j=[k/3]+k%3 （[ ]取整，%取余）5.4在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法只占用一个辅助向量空间。

第1章绪论二、判断题三．填空题1．数据元素数据元素间关系 2．集合线性结构树形结构图状结构或网状结构。

3．数据的组织形式，即数据元素之间逻辑关系的总体。

而逻辑关系是指数据元素之间的关联方式或称“邻接关系”。

4．表示（又称映像）。

5．（1）逻辑特性（2）在计算机内部如何表示和实现（3）数学特性。

6．算法的时间复杂度和空间复杂度。

7．（1）逻辑结构（2）物理结构（3）操作（运算）（4）算法。

8．（1）有穷性（2）确定性（3）可行性。

9．（1）n+1 （2）n （3）n(n+3)/2 （4）n(n+1)/2。

10．1+（1+2++（1+2+3）+…+（1+2+…+n）=n(n+1)(n+2)/6 O(n3)11. log2n 12. nlog2n 13. log2n2 14. (n+3)(n-2)/2 15. O(n)16.① (1)1 (2)1 (3)f(m,n-1) (4)n ② 9 17. n(n-1)/2四．应用题1．数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象及对象间的关系和施加于对象的操作等的学科。

2．四种表示方法（1）顺序存储方式。

数据元素顺序存放，每个存储结点只含一个元素。

存储位置反映数据元素间的逻辑关系。

存储密度大，但有些操作（如插入、删除）效率较差。

（2）链式存储方式。

每个存储结点除包含数据元素信息外还包含一组（至少一个）指针。

指针反映数据元素间的逻辑关系。

这种方式不要求存储空间连续，便于动态操作（如插入、删除等），但存储空间开销大（用于指针），另外不能折半查找等。

（3）索引存储方式。

除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表，索引表中索引指示存储结点的存储位置（下标）或存储区间端点（下标），兼有静态和动态特性。

（4）散列存储方式。

通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将散列函数的值解释成关键字所在元素的存储地址，这种存储方式称为散列存储。

第1章绪论一、填空题01、【操作对象】【关系和运算】02、【数据元素】【关系】03、【逻辑结构】【存储结构】【运算】04、【线性结构】【非线性结构】05、【一对一】【一对多】【多对多】06、【没有】【没有】07、【前驱】【1】【后续】【任意多个】08、【任意多个】09、【顺序】【链式】【索引】【散列】10、【集合】【线性结构】【树形结构】【图状结构】11、【插入】【删除】【修改】【查找】【排序】12、【时间】【空间】13、【时间复杂度】【空间复杂度】14、【映射】15、【有穷性】【确定性】【可行性】16、【n+1】【n】【n(n+3)/2】【n(n+1)/2】17、【n(n+1)(n+2)/6】【O(n3)】18、【O(n2 log)】19、【O(nn2 log)】20、【O(22log n)】21、【(n+3)(n-2)/2】22、【n(n-1)/2】二、判断题01-05、×××√×06-10、×√×××11-12、√×三、单项选择题B01 BD02 A03 C04 C05A06 C07 B08 A09 C10B11 A12 C13 D14 A15C16四、分析下面各程序段的时间复杂度01、O（nm ）02、O（2n）03、答：O（2n）04、答：O（n3 log）五、设有数据逻辑结构S=(D,R)，试按各小题所给条件画出这些逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点？01、此图为线性结构d1→d2→d3→d4d1—无直接前驱，是首结点d4—无直接后继是尾结点02、此图为树形结构d1—无直接前驱，是根结点d2,d5,d7,d9—无直接后继是叶子结点03、此图为图形结构d1，d2—无直接前驱，是开始结点d6,d7—无直接后继是终端结点六、简述题01、什么是数据结构?答：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。

一、选择题1. 算法的计算量的大小称为计算的（B ）。

【北京邮电大学2000 二、3 （20/8分）】A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（C ）【中科院计算所1998 二、1 （2分）】A．问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是（1），它必须具备（2）这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性【南京理工大学1999 一、1（2分）【武汉交通科技大学1996 一、1（4分）】4．一个算法应该是（）。

【中山大学1998 二、1（2分）】A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A 和C.5. 下面关于算法说法错误的是（）【南京理工大学2000 一、1（1.5分）】A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（）【南京理工大学2000 一、2 （1.5分）】(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（）两大类。

【武汉交通科技大学1996 一、4（2分）】A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（）。

【北方交通大学2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈9．以下数据结构中，哪一个是线性结构（）？【北方交通大学2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串10．以下那一个术语与数据的存储结构无关？（）【北方交通大学2001 一、2（2分）】A．栈 B. 哈希表 C. 线索树 D. 双向链表11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学2001 一、10（3分）】FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A．O(2n) B．O(n) C．O(n2) D．O(log2n)12．程序段FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与A[j+1]对换；其中n为正整数，则最后一行的语句频度在最坏情况下是（）A. O（n）B. O(nlogn)C. O(n3)D. O(n2) 【南京理工大学1998一、1(2分)】13．以下哪个数据结构不是多型数据类型（）【中山大学1999 一、3（1分）】A．栈B．广义表C．有向图D．字符串14．以下数据结构中，（）是非线性数据结构【中山大学1999 一、4】A．树B．字符串C．队D．栈15. 下列数据中，（）是非线性数据结构。

数据结构1800题【数据结构题1800题】第一篇：队列（Queue）队列是一种线性数据结构，按照先进先出（FIFO）的原则进行操作。

它可以理解为在一端进行插入操作，在另一端进行删除操作。

队列常用的操作有入队（enqueue）和出队（dequeue）。

入队操作将新元素插入到队列的末尾，出队操作将队列中的第一个元素删除并返回。

队列的另外两个常用操作是获取队列中的第一个元素（front）和判断队列是否为空（isEmpty）。

队列的实现方式有很多种，常见的有基于数组和基于链表的实现。

基于数组的实现一般需要指定队列的最大容量，而基于链表的实现则没有容量限制。

无论采用哪种实现方式，我们需要注意队列的扩容问题，以保证队列能够存储任意数量的元素。

队列在计算机科学中有着广泛的应用。

比如，操作系统中的进程调度、网络数据包的传输、任务队列等都可以使用队列来实现。

此外，队列还可以用于解决一些实际问题，比如打印队列、排队等。

第二篇：栈（Stack）栈是一种线性数据结构，按照先进后出（LIFO）的原则进行操作。

它可以理解为只能在一端进行插入或删除操作的线性表。

栈的插入操作通常称为入栈（push），删除操作称为出栈（pop）。

栈在计算机科学中有着广泛的应用。

比如，操作系统中的函数调用栈、Web浏览器的历史记录、文本编辑器中的撤销操作等都可以使用栈来实现。

此外，栈还可以用于解决一些实际问题，比如括号匹配、表达式求值等。

栈的实现方式有很多种，常见的有基于数组和基于链表的实现。

基于数组的实现一般需要指定栈的最大容量，而基于链表的实现则没有容量限制。

无论采用哪种实现方式，我们需要注意栈的扩容问题，以保证栈能够存储任意数量的元素。

总结起来，队列和栈都是常用的数据结构，它们在计算机科学和实际应用中都有着广泛的应用。

理解队列和栈的基本概念、操作和实现方式对于编程和解决实际问题都具有重要意义。

数据结构1800例题与答案第一章绪论一、选择题（每小题2分）1．算法的计算量的大小称为计算的（ B ）。

【北京邮电大学2000 二、3 （20/8分）】A．效率 B．复杂性 C．现实性 D．难度2．算法的时间复杂度取决于（C）。

【中科院计算所 1998 二、1 （2分）】A．问题的规模 B．待处理数据的初态 C．A和B D．都不是3．计算机算法指的是（①C），它必须具备（②B）这三个特性。

① A．计算方法 B．排序方法C．解决问题的步骤序列 D．调度方法② A．可执行性、可移植性、可扩充性 B．可执行性、确定性、有穷性C．确定性、有穷性、稳定性D．易读性、稳定性、安全性【南京理工大学1999 一、1（2分）【武汉交通科技大学 1996 一、1（ 4分）】4．一个算法应该是（B）。

【中山大学1998 二、1（2分）】A．程序 B．问题求解步骤的描述C．要满足五个基本特性 D．A和C.5．下面关于算法说法错误的是（D）【南京理工大学2000 一、1（1.5分）】A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（C）【南京理工大学 2000 一、2 （1.5分）】(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（C）两大类。

【武汉交通科技大学 1996 一、4（2分）】A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（D ）。

目录线性表 (1)栈和队列 (6)串 (8)数组和广义表 (10)树和二叉树 (13)图 (21)集合 (26)排序 (29)1．假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。

请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。

【北京大学 1998 三、1 （5分）】类似本题的另外叙述有：（1）设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中ha表中已有的数据若hb中也有,则hb中的数据不归并到ha中,hb的链表在算法中不允许破坏。

【南京理工大学1997 四、3（15分）】PROCEDURE merge(ha,hb);（2）已知头指针分别为la和lb 的带头结点的单链表中，结点按元素值非递减有序排列。

写出将la 和 lb 两链表归并成一个结点按元素值非递减有序排列的单链表（其头指针为 lc），并计算算法的时间复杂度。

【燕山大学 1998 五（20分）】2. 图（编者略）中带头结点且头指针为ha和hb的两线性表A和B 分别表示两个集合。

两表中的元素皆为递增有序。

请写一算法求A和B的并集AUB。

要求该并集中的元素仍保持递增有序。

且要利用A和B的原有结点空间。

【北京邮电大学 1992 二（15分）】类似本题的另外叙述有：(1) 已知递增有序的两个单链表A，B分别存储了一个集合。

设计算法实现求两个集合的并集的运算A:=A∪B 【合肥工业大学 1999 五、1（8分）】（2）已知两个链表A和B分别表示两个集合，其元素递增排列。

编一函数，求A与B的交集，并存放于A链表中。

【南京航空航天大学 2001 六（10分）】（3）设有两个从小到大排序的带头结点的有序链表。

试编写求这两个链表交运算的算法（即L1∩L2）。

要求结果链表仍是从小到大排序，但无重复元素。

一、选择题1. 算法的计算量的大小称为计算的（B ）。

【北京邮电大学2000 二、3 （20/8分）】A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（C ）【中科院计算所1998 二、1 （2分）】A．问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是（1），它必须具备（2）这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性【南京理工大学1999 一、1（2分）【武汉交通科技大学1996 一、1（4分）】4．一个算法应该是（）。

【中山大学1998 二、1（2分）】A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A 和C.5. 下面关于算法说法错误的是（）【南京理工大学2000 一、1（1.5分）】A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（）【南京理工大学2000 一、2 （1.5分）】(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（）两大类。

【武汉交通科技大学1996 一、4（2分）】A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（）。

【北方交通大学2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈9．以下数据结构中，哪一个是线性结构（）？【北方交通大学2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串10．以下那一个术语与数据的存储结构无关？（）【北方交通大学2001 一、2（2分）】A．栈 B. 哈希表 C. 线索树 D. 双向链表11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学2001 一、10（3分）】FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A．O(2n) B．O(n) C．O(n2) D．O(log2n)12．程序段FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与A[j+1]对换；其中n为正整数，则最后一行的语句频度在最坏情况下是（）A. O（n）B. O(nlogn)C. O(n3)D. O(n2) 【南京理工大学1998一、1(2分)】13．以下哪个数据结构不是多型数据类型（）【中山大学1999 一、3（1分）】A．栈B．广义表C．有向图D．字符串14．以下数据结构中，（）是非线性数据结构【中山大学1999 一、4】A．树B．字符串C．队D．栈15. 下列数据中，（）是非线性数据结构。