数据结构经典例题
数据结构例题（及答案）
项目一习题(答案)
一选择题
1. 算法的计算量的大小称为计算的(B )。
A( 效率 B. 复杂性 C. 现实性 D. 难度
2.算法的时间复杂度取决于(C )
A(问题的规模 B. 待处理数据的初态 C. A和B
3(从逻辑上可以把数据结构分为(C )两大类。
A(动态结构、静态结构 B(顺序结构、链式结构
C(线性结构、非线性结构 D(初等结构、构造型结构
4(连续存储设计时，存储单元的地址(A )。
A(一定连续 B(一定不连续 C(不一定连续 D(部分连续，部分不连续
5. 以下属于逻辑结构的是(C )。
A(顺序表 B. 哈希表 C.有序表 D. 单链表
二、判断题
1. 数据元素是数据的最小单位。(×)
2. 记录是数据处理的最小单位。(×)
3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系;(×)
4(程序一定是算法。(×)
5. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。(×)
6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(×)
7. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。(?)
8. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. (×)
三、填空
1(数据的物理结构包括数据元素的表示和数据元素间关系的表示。
2. 对于给定的n个元素,可以构造出的逻辑结构有集合，线性结构，树形
结构，图状结构或网状结构四种。
3(数据的逻辑结构是指数据的组织形式，即数据元素之间逻辑关系的总体。而
逻辑关系是指数据元素之间的关联方式或称“邻接关系”。
4(一个数据结构在计算机中表示(又称映像) 称为存储结构。
5(抽象数据类型的定义仅取决于它的一组逻辑特性，而与在计算机内部如何表
示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响
其外部使用。 6(数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度。 7. 数据结构是研讨数据的逻辑结构和物理结构，以及它们之间的相互
关系，并对与这种结构定义相应的操作(运算)，设计出相应的算法。
( 一个算法具有5个特性: 有穷性、确定性、可行性，有零个或多个输入、
有一个或多个输8
出。
四、应用题
1. 1. 数据结构是一门研究什么内容的学科,
答:数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象
及对象间的关系和施加于对象的操作等的学科
2. 2. 数据元素之间的关系在计算机中有几种表示方法,各有什么特点, 答:四
种表示方法
(1)顺序存储方式。数据元素顺序存放，每个存储结点只含一个元素。存储位
置反映数据元素间的逻辑关系。存储密度大，但有些操作(如插入、删除)效率较差。
(2)链式存储方式。每个存储结点除包含数据元素信息外还包含一组(至少一个)指针。指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操作(如插入、删除等)，但存储空间开销大(用于指针)，另外不能折半查找等。
(3)索引存储方式。除数据元素存储在一地址连续的内存空间外，尚需建立一
个索引表，索引表中索引指示存储结点的存储位置(下标)或存储区间端点(下标)，兼有静态和动态特性。
(4)散列存储方式。通过散列函数和解决冲突的方法，将关键字散列在连续的
有限的地址空间内，并将散列函数的值解释成关键字所在元素的存储地址，这种存储方式称为散列存储。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。
3. 3. 数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处，抽象数据类型的
主要特点是什么,使用抽象数据类型的主要好处是什么,
答:数据类型是程序设计语言中的一个概念，它是一个值的集合和操作的集
合。如C语言中的整型、实型、字符型等。整型值的范围(对具体机器都应有整数范围)，其操作有加、减、乘、除、求余等。实际上数据类型是厂家提供给用户的已实现了的数据结构。“抽象数据类型(ADT)”指一个数学模型及定义在该模型上的一组操作。“抽象”的意义在于数据类型的数学抽象特性。抽象数据类型的定义仅取决于它的逻辑特性，而与其在计算机内部如何表示和实现无关。无论其内部结构如何变化，只要它的数学特性不变就不影响它的外部使用。抽象数据类型和数据类型实质上是一个概念。此外，抽象数据类型的范围更广，它已不再局限于机器已
定义和实现的数据类型，还包括用户在设计软件系统时自行定义的数据类型。使用抽象数据类型定义的软件模块含定义、表示和实现三部分，封装在一起，对用户透明(提供接口)，而不必了解实现细节。抽象数据类型的出现使程序设计不再是“艺术”，而是向“科学”迈进了一步。
4. 4. 回答问题
(1)在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎
样的关系,
答:数据的逻辑结构反映数据元素之间的逻辑关系(即数据元素之间的关联方式或“邻接关系”)，数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。数据的运算是对数据定义的一组操作，运算是定义在逻辑结构上的，和存储结构无关，而运算的实现则是依赖于存储结构。
5. (2)若逻辑结构相同但存储结构不同，则为不同的数据结构。这样的说法对吗,举例说
明之。
答: 逻辑结构相同但存储不同，可以是不同的数据结构。例如，线性表的逻辑结构属于线性结构，采用顺序存储结构为顺序表，而采用链式存储结构称为线性链表。
6. (3)在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同的数据
结构。这样说法对吗,举例说明之。
答:栈和队列的逻辑结构相同，其存储表示也可相同(顺序存储和链式存储)，但由于其运算集合不同而成为不同的数据结构。
7. (4)评价各种不同数据结构的标准是什么,
答:数据结构的评价非常复杂，可以考虑两个方面，一是所选数据结构是否准确、完整的刻划了问题的基本特征;二是是否容易实现(如对数据分解是否恰当;逻辑结构的选择是否适合于运算的功能，是否有利于运算的实现;基本运算的选择是否恰当。)
8. 5(评价一个好的算法，您是从哪几方面来考虑的,
答:评价好的算法有四个方面。一是算法的正确性;二是算法的易读性;三是算法的健壮性;四是算法的时空效率(运行)。
9. 6(解释和比较以下各组概念
10. (1)算法的时间复杂性
答:算法的时间复杂性是算法输入规模的函数。算法的输入规模或问题的规模是作为该算法输入的数据所含数据元素的数目，或与此数目有关的其它参数。有时考虑算法在最坏情况下的时间复杂度或平均时间复杂度。
11. (2)算法
答: 算法是对特定问题求解步骤的描述，是指令的有限序列，其中每一条指令表示一个或多个操作。算法具有五个重要特性:有穷性、确定性、可行性、输入和输出。
12. (3)频度
答:频度。在分析算法时间复杂度时，有时需要估算基本操作的原操作，它是执行次数最多的一个操作，该操作重复执行的次数称为频度。
13. 7. 根据数据元素之间的逻辑关系，一般有哪几类基本的数据结构, 答:集合、线性结构、树形结构、图形或网状结构。
14. 8(对于一个数据结构，一般包括哪三个方面的讨论,
答:逻辑结构、存储结构、操作(运算)。
第二项线性表
一选择题
1. 下述哪一条是顺序存储结构的优点,(A)。
A(存储密度大 B(插入运算方便 C(删除运算方便 D(可方便地用于各种逻辑结构的存储表示
2.下面关于线性表的叙述中，错误的是哪一个,(B)
A(线性表采用顺序存储，必须占用一片连续的存储单元。 B(线性表采用顺序存储，便于进行插入和删除操作。
C(线性表采用链接存储，不必占用一片连续的存储单元。 D(线性表采用链接存储，便于插入和删除操作。
3(线性表是具有n个( C)的有限序列(n>0)。
A(表元素 B(字符 C(数据元素 D(数据项 E(信息项
4(若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用(A)
存储方式最节省时间。
A(顺序表 B(双链表 C(带头结点的双循环链表 D(单循环链表
5(某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用(D)存
储方式最节省运算时间。
A(单链表 B(仅有头指针的单循环链表 C(双链表 D(仅有尾指针的单循环链表6(设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用(D)最节省时间。 A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表
7(若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用(D)存储
方式最节省运算时间。
A(单链表 B(双链表 C(单循环链表 D(带头结点的双循环链表
8. 静态链表中指针表示的是(C)。
A( 内存地址 B(数组下标 C(下一元素地址 D(左、右孩子地址
9. 链表不具有的特点是(B)。
A(插入、删除不需要移动元素 B(可随机访问任一元素 C(不必事先估计存储空间 D(所需空间与线性长度成正比
10. 下面的叙述不正确的是(B,C)。
A(线性表在链式存储时，查找第i个元素的时间同i的值成正比
B. 线性表在链式存储时，查找第i个元素的时间同i的值无关
C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比
D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关
11. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为
(C)。 A(O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)
二、判断题
1. 链表中的头结点仅起到标识的作用。(×)
2. 顺序存储结构的主要缺点是不利于插入或删除操作。(?)
3(线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。(?) 4(顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。(×)
5. 对任何数据结构链式存储结构一定优于顺序存储结构。(×)
6(顺序存储方式只能用于存储线性结构。(×)
7(集合与线性表的区别在于是否按关键字排序。(×)
8. 所谓静态链表就是一直不发生变化的链表。(×)
9. 线性表的特点是每个元素都有一个前驱和一个后继。(×)
10. 取线性表的第i个元素的时间同i的大小有关. (×)
11. 循环链表不是线性表. (×)
12. 线性表只能用顺序存储结构实现。(×)
13. 线性表就是顺序存储的表。(×)
14(为了很方便的插入和删除数据，可以使用双向链表存放数据。(?)
15. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(×)
16. 链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。 (?)
三、填空
1(当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用__顺序__存储结构。
2(线性表L=(a1,a2,…,an)用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是__(n-1)/2__。
3(设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x 之后，则需要执行以下语句:py->next=px->next; px->next=py;
4(在一个长度为n的顺序表中第i个元素(1<=i<=n)之前插入一个元素时，需向后移动 n-i+1个元素。
5(在单链表中设置头结点的作用是主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表指针不变。。 6(对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为O(1),在给定值为x的结点后插入一个新结点的时间复杂度为O(n)。
7(根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成单链表和多重链表;而又根据指针的连接方式，链表又可分成(动态)链表和静态链表。
8( 在双向循环链表中,向p所指的结点之后插入指针f所指的结点，其操作是f->next=p->next、f->prior=p、p->next->prior=f、p->next=f。
四、应用题
1. 1(线性表有两种存储结构:一是顺序表，二是链表。试问:
2. (1)如果有 n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表
的总数也会自动地改变。在此情况下，应选用哪种存储结构, 为什么, 答:选链式存储结构。它可动态申请内存空间，不受表长度(即表中元素个数)的影响，插入、删除时间复杂度为O(1)。
3. (2)若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性
表中的元素，那么应采用哪种存储结构,为什么,
答:选顺序存储结构。顺序表可以随机存取，时间复杂度为O(1)。
4. 2(线性表的顺序存储结构具有三个弱点:其一，在作插入或删除操作时，需移动大量元
素;其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利
用;其三，表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱
点，试讨论之。
答:链式存储结构一般说克服了顺序存储结构的三个弱点。首先，插入、删除不需移动元素，只修改指针，时间复杂度为O(1);其次，不需要预先分配空间，可根据需要动态申请空间;其三，表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储的缺点。
5. 3(若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构,为什
么,
答:采用链式存储结构，它根据实际需要申请内存空间，而当不需要时又可将不用结点空间返还给系统。在链式存储结构中插入和删除操作不需要移动元素。
6. 4(线性表(a1，a2，…，an)用顺序映射表示时，ai和ai+1(1<=i,n〉的物理位置相
邻吗,链接表示时呢,
答:顺序映射时，ai与ai+1的物理位置相邻;链表表示时ai与ai+1的物理位置不要求相邻。
7. 5. 说明在线性表的链式存储结构中，头指针与头结点之间的根本区别;头结点与首元结
点的关系。
答:在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指
针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设
立的，放在第一元素结点之前，其数据域一般无意义(当然有些情况下也可存放链表的长度、用
做监视哨等等)，有头结点后，对在第一元素结点前插入结点和删除第一结
点，其操作与对其它
结点的操作统一了。而且无论链表是否为空，头指针均不为空。首元结点也就
是第一元素结点，
它是头结点后边的第一个结点。
项目三习题(答案)
一选择题
1. 对于栈操作数据的原则是(B )。
A. 先进先出 B(后进先出 C(后进后出 D( 不分顺序
2.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第
i(1<=i<=n)个元素是( B )。 A(不确定 B(n-i+1 C( i D( n-i
3. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j
个输出元素是(D )。 A(i-j-1 B(i-j C(j-i+1 D( 不确定的
4. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN是n，则pi是( D )。 A. i B(n-i C(n-i+1 D. 不确定
5. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈
序列,( C )。 A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6
6. 设栈的输入序列是1，2，3，4,则(D )不可能是其出栈序列。
A. 1，2，4，3，
B. 2，1，3，4，
C. 1，4，3，2，
D. 4，3，1，2，
E. 3，2，1，4，
7. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是( B )。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2
8. 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序
列的是( D )。 A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4
d,下面的四个序列中，不可能是它的输出序列的是( D )。 9. 某堆栈的输入
序列为a, b，c ，
A. a，c，b，d
B. b, c，d，a
C. c, d，b, a
D. d, c，a，b
10. 设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的序列为( D )。 A(fedcba B. bcafed C. dcefba D. cabdef
11. 设有三个元素X，Y，Z顺序进栈(进的过程中允许出栈)，下列得不到的出栈排列是( C )。 A(XYZ B. YZX C. ZXY D. ZYX
12. 用链接方式存储的队列，在进行删除运算时(D )。
A. 仅修改头指针
B. 仅修改尾指针
C. 头、尾指针都要修改
D. 头、尾指针
可能都要修改
13. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行
删除操作时( D )。
A(仅修改队头指针 B. 仅修改队尾指针 C. 队头、队尾指针都要修改 D. 队头,队尾指针都可能要修改
14. 递归过程或函数调用时，处理参数及返回地址，要用一种称为(C )的数据结构。 A(队列 B(多维数组 C(栈 D. 线性表
二、判断题
1. 消除递归不一定需要使用栈，此说法(? )
2. 栈是实现过程和函数等子程序所必需的结构。(? )
3. 两个栈共用静态存储空间，对头使用也存在空间溢出问题。(? )
4(两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。(? )
5. 即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组
合操作，所得的输出序列也一定相同。(× )
6. 栈与队列是一种特殊操作的线性表。(? )
7. 若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列3,2,5,6,4,1. (? )
8. 栈和队列都是限制存取点的线性结构。( ? )
9(若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列1，5，4，
6，2，3。(× ) 10. 任何一个递归过程都可以转换成非递归过程。(? )
11. 只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用
栈。(× ) 12. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种
先进后出型结构。(× ) 13. 通常使用队列来处理函数或过程的调用。(× )
14. 队列逻辑上是一个下端和上端既能增加又能减少的线性表。(? )
15. 循环队列通常用指针来实现队列的头尾相接。(× )
16. 循环队列也存在空间溢出问题。(? )
17. 队列和栈都是运算受限的线性表，只允许在表的两端进行运算。(× )
18. 栈和队列都是线性表，只是在插入和删除时受到了一些限制。(? )
19. 栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。(? )
三、填空
1(栈是操作受限(或限定仅在表尾进行插入和删除操作)的线性表，其运算遵循
后进先出的原则。 2(栈是限定仅在表尾进行插入或删除操作的线性表。
3. 一个栈的输入序列是:1，2，3则不可能的栈输出序列是3 1 2。
4(两个栈共享空间时栈满的条件两栈顶指针值相减的绝对值为1(或两栈顶指针
相邻)。。 5(在作进栈运算时应先判别栈是否满;在作退栈运算时应先判别栈是否空;当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为n。为
了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，
应将两栈的栈底分别设在内存空间的两端，这样只有当两栈顶指针相邻(即值之差的绝对值为1)时才产生溢出。
6. 多个栈共存时，最好用链式存储结构作为存储结构。
7(用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为S×SS×S×× 。
8. 循环队列的引入，目的是为了克服假溢出时大量移动数据元素。
9(队列又称作先进先出表。
10. 已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是
s=(LinkedList)malloc(sizeof(LNode)); s->data=x;s->next=r->next;r-
>next=s;r=s;。 (区分循环队列的满与空，只有两种方法，它们是牺牲一个存储单元和设标记。 11
四、应用题
1. 名词解释:栈。
答:栈是只准在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。最后插入的元素最先删除，故栈也称后进先出(LIFO)表。
2. 名词解释:队列
答:队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。最先插入队的元素最先离开(删除)，故队列也常称先进先出(FIFO)表。
3. 什么是循环队列,
答:用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质(队尾插入和队头删除)，容易造成“假溢出”现象，即队尾已到达一维数组的高下标，不能再插入，然而队中元素个数小于队列的长度(容量)。循环队列是解决“假溢出”
的一种方法。通常把一维数组看成首尾相接。在循环队列下，通常采用“牺牲一个存储单元”或“作标记”的方法解决“队满”和“队空”的判定问题。
4. 假设以S和X分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由S和X组
成的序列表示(如SXSX)。
(1)试指出判别给定序列是否合法的一般规则。
答:通常有两条规则。第一是给定序列中S的个数和X的个数相等;第二是从给定序列的开始，到给定序列中的任一位置，S的个数要大于或等于X的个数。
(2)两个不同合法序列(对同一输入序列)能否得到相同的输出元素序列,如能得到，请举列说明。
答:可以得到相同的输出元素序列。例如，输入元素为A，B，C，则两个输入的合法序列ABC和BAC均可得到输出元素序列ABC。对于合法序列ABC，我们使用本题约定的S×S×S×操作序列;对于合法序列BAC，我们使用SS××S×操作序列。
5. 有5 个元素，其入栈次序为:A，B，C，D，E，在各种可能的出栈次序中，以元素C，D
最先出栈(即C第一个且D第二个出栈)的次序有哪几个,
答:三个:CDEBA，CDBEA，CDBAE
6. 如果输入序列为1 2 3 4 5 6,试问能否通过栈结构得到以下两个序列:4 3 5 6 1 2和1 3 5 4 2 6;
请说明为什么不能或如何才能得到。
答:输入序列为123456，不能得出435612，其理由是，输出序列最后两元素是12，前面4个元素(4356)得到后，栈中元素剩12，且2在栈顶，不可能栈底元素1在栈顶元素2之前出栈。
得到135426的过程如下:1入栈并出栈，得到部分输出序列1;然后2和3入栈，3出栈，部分输出序列变为:13;接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542;最后6入栈并退栈，得最终结果135426。
7. 若元素的进栈序列为:A、B、C、D、E，运用栈操作，能否得到出栈序列B、
C、A、E、
D和D、B、A、C、E,为什么,
答: 能得到出栈序列B、C、A、E、D，不能得到出栈序列D、B、A、C、E。其理由为:若出
栈序列以D开头，说明在D之前的入栈元素是A、B和C，三个元素中C是栈顶元素，B和A不
可能早于C出栈，故不可能得到D、B、A、C、E出栈序列。
8. 设输入序列为a,b,c,d,试写出借助一个栈可得到的两个输出序列和两个不能得到的输出序
列。
答:借助栈结构，n个入栈元素可得到1/(n+1)((2n)～/(n!*n!))种出栈序列。本题4个元素，可
有14种出栈序列，abcd和dcba就是其中两种。但dabc和adbc是不可能得到的两种。
9. 设输入序列为2，3，4，5，6，利用一个栈能得到序列2，5，3，4，6吗,栈可以用单链
表实现吗,
答:不能得到序列2，5，3，4，6。栈可以用单链表实现，这就是链栈。由于栈只在栈顶操作，
所以链栈通常不设头结点。
项目四习题(答案)
1. 一选择题
2. 1(下面关于串的的叙述中，哪一个是不正确的,(B )
A(串是字符的有限序列 B(空串是由空格构成的串 C(模式匹配是串的一种重要运算 D(串既可以采用顺序存储，也可以采用链式存储
1. 2( 若串S1=…ABCDEFG?, S2=…9898? ,S3=…###?,S4=…012345?,执行
concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,ind ex
(S2,…8?),length(S2)))，其结果为(E )
A(ABC###G0123 B(ABCD###2345 C(ABC###G2345 D(ABC###2345 E(ABC###G1234 F(ABCD###1234 G(ABC###01234
1. 3(设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为(C )。 A(求子串 B(联接 C(匹配 D(求串长
1. 4. 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，
a11为第一元素，其存储
地址为1，每个元素占一个地址空间，则a85的地址为(B )。
A. 13
B. 33
C. 18
D. 40
1. 5. 对稀疏矩阵进行压缩存储目的是( C )。
A(便于进行矩阵运算 B(便于输入和输出 C(节省存储空间 D(降低运算的时间
复杂度
1. 6. 广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为(D )。
Head(Tail(Head(Tail(Tail(A))))) A. (g) B. (d) C. c D. d
1. 7. 设广义表L=((a,b,c))，则L的长度和深度分别为( C )。 A. 1和1 B. 1和3 C. 1和2 D. 2和3
二、判断题
1(串是一种数据对象和操作都特殊的线性表。(? )
2. 稀疏矩阵压缩存储后，必会失去随机存取功能。(? )
3. 数组是同类型值的集合。(× )
4. 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。( × )
5. 一个稀疏矩阵Am*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并
把m和n的值互换，则就完成了Am*n的转置运算。(× )
6. 二维以上的数组其实是一种特殊的广义表。( ? )
7. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。(× )
三、填空
1(空格串是指由空格字符(ASCII值32)所组成的字符串，其长度等于空格个数。
2(组成串的数据元素只能是字符。
3(一个字符串中任意个连续的字符组成的子序列称为该串的子串。
4. 数组的存储结构采用顺序存储结构存储方式。
5. 所谓稀疏矩阵指的是非零元很少(t,,m*n)且分布没有规律。
6. 广义表A=(((a，b)，(c，d，e)))，取出A中的原子e的操作是:
head(tail(tail(head(tail(head(A))))))。
四、应用题
1. 1(名词解释:串
答:串是零个至多个字符组成的有限序列。从数据结构角度讲，串属于线性结
构。与线性表的特殊性在于串的元素是字符。
2. 2(描述以下概念的区别:空格串与空串。
答:空格是一个字符，其ASCII码值是32。空格串是由空格组成的串，其长度
等于空格的个数。空串是不含任何字符的串，即空串的长度是零。
3. 3. 特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能,为什么,
答:特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律，因此可以对非
零元素分配单元(对值相同元素只分配一个单元)，将非零元素存储在向量中，元素
的下标i和j和该元素在向量中的下标有一定规律，可以用简单公式表示，仍具有
随机存取功能。而稀疏矩阵是指非零元素和矩阵容量相比很小(t,,m*n)，且分布没
有规律。用十字链表作存储结构自然失去了随机存取的功能。即使用三元组表的顺
序存储结构，存取下标为i和j的元素时，要扫描三元组表，下标不同的元素，存
取时间也不同，最好情况下存取时间为O(1)，最差情况下是O(n)，因此也失去了
随机存取的功能。
4. 4. 试叙述一维数组与有序表的异同。
答:一维数组属于特殊的顺序表，和有序表的差别主要在于有序表中元素按值
排序(非递增或非递减)，而一维数组中元素没有按元素值排列顺序的要求。
5. 5. 一个n?n的对称矩阵，如果以行或列为主序存入内存，则其容量为多少,
答:n(n+1)/2(压缩存储) 或n2(不采用压缩存储)
项目五习题(答案)
选择题 1. 一
2. 1. 已知一算术表达式的中序遍历结果为 A+B*C-D/E，前序遍历的结果为
ABC*+DE/-，其前序遍
历的结果为( D ),
-+*ABC/DE D. -+A*BC/DE A(-A+B*C/DE B. -A+B*CD/E C(
1. 2.在下述结论中，正确的是(D ),
?只有一个结点的二叉树的度为0; ?二叉树的度为2; ?二叉树的左右子树可任意交换; ?深度
为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A(??? B(??? C(?? D(??
1. 3(若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是(B ) A(9 B(11 C(15 D(不确定
1. 4. 设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对
应的二叉树根结点的右子树上的结点个数是( D )。
A(M1 B(M1+M2 C(M3 D(M2+M3
1. 5(具有10个叶结点的二叉树中有(B )个度为2的结点。
A(8 B(9 C(10 D(ll
1. 6(一棵完全二叉树上有1001个结点，其中叶子结点的个数是( E )
A( 250 B( 500 C(254 D(505 E(以上答案都不对
1. 7. 有n个叶子的哈夫曼树的结点总数为(D )。
A(不确定 B(2n C(2n+1 D(2n-1
1. 8(二叉树的第I层上最多含有结点数为(C )
A(2I B( 2I-1-1 C( 2I-1 D(2I -1
1. 9. 利用二叉链表存储树，则根结点的右指针是( C )。
A(指向最左孩子 B(指向最右孩子 C(空 D(非空
1. 10(对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同
数据结构经典例题
数据结构例题（及答案） 项目一习题(答案) 一选择题 1. 算法的计算量的大小称为计算的(B )。 A( 效率 B. 复杂性 C. 现实性 D. 难度 2.算法的时间复杂度取决于(C ) A(问题的规模 B. 待处理数据的初态 C. A和B 3(从逻辑上可以把数据结构分为(C )两大类。 A(动态结构、静态结构 B(顺序结构、链式结构 C(线性结构、非线性结构 D(初等结构、构造型结构 4(连续存储设计时，存储单元的地址(A )。 A(一定连续 B(一定不连续 C(不一定连续 D(部分连续，部分不连续 5. 以下属于逻辑结构的是(C )。 A(顺序表 B. 哈希表 C.有序表 D. 单链表 二、判断题 1. 数据元素是数据的最小单位。(×) 2. 记录是数据处理的最小单位。(×) 3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系;(×) 4(程序一定是算法。(×) 5. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。(×) 6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(×) 7. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。(?)
8. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. (×) 三、填空 1(数据的物理结构包括数据元素的表示和数据元素间关系的表示。 2. 对于给定的n个元素,可以构造出的逻辑结构有集合，线性结构，树形 结构，图状结构或网状结构四种。 3(数据的逻辑结构是指数据的组织形式，即数据元素之间逻辑关系的总体。而 逻辑关系是指数据元素之间的关联方式或称“邻接关系”。 4(一个数据结构在计算机中表示(又称映像) 称为存储结构。 5(抽象数据类型的定义仅取决于它的一组逻辑特性，而与在计算机内部如何表 示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响 其外部使用。 6(数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度。 7. 数据结构是研讨数据的逻辑结构和物理结构，以及它们之间的相互 关系，并对与这种结构定义相应的操作(运算)，设计出相应的算法。 ( 一个算法具有5个特性: 有穷性、确定性、可行性，有零个或多个输入、 有一个或多个输8 出。 四、应用题 1. 1. 数据结构是一门研究什么内容的学科, 答:数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象 及对象间的关系和施加于对象的操作等的学科 2. 2. 数据元素之间的关系在计算机中有几种表示方法,各有什么特点, 答:四 种表示方法
经典数据结构面试题(含答案)
栈和队列的共同特点是__________________________ .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中，增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是 __________________________ 13.树是结点的集合，它的根结点数目是_____________________ 14.在深度为5的满二叉树中，叶子结点的个数为_______________ 15.具有3个结点的二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是 ____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中，算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________
数据结构模拟卷(含答案)经典习题培训讲学
数据结构模拟卷(含答案)经典习题
练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4
6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位10. 下列图示的顺序存储结构表示的二叉树是( )
经典数据结构面试题(含答案)
.栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中，增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是__________________________ 13.树是结点的集合，它的根结点数目是_____________________ 14.在深度为5的满二叉树中，叶子结点的个数为_______________ 15.具有3个结点的二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中，算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________
大数据结构经典复习题(仅供参考)
一、选择题(20分) 1．下面关于线性表的叙述错误的是（D ）。 (A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现 (D) 线性表采用顺序存储便于插入和删除操作的实现 2．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（A ）。 (A) BADC (B) BCDA (C) CDAB (D) CBDA 3．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（C ）。 (A) 9 (B) 10 (C) 11 (D) 12 4．设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（B ）。 (A) O(1) (B) O(log2n) (C) (D) O(n2) 5．设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（B ）方法可以达到此目的。 (A) 快速排序(B) 堆排序(C) 归并排序(D) 插入排序 第9小题分析：9快速排序、归并排序和插入排序必须等到整个排序结束后才能够求出最小的10个数，而堆排序只需要在初始堆的基础上再进行10次筛选即可，每次筛选的时间复杂度为O(log2n)。 6.下列四种排序中（D ）的空间复杂度最大。 (A) 插入排序(B) 冒泡排序(C) 堆排序(D) 归并排序
7．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（C ）。 (A) O(n) (B) O(nlog2n) (C) O(1) (D) O(n2) 8．设一棵二叉树的深度为k，则该二叉树中最多有（D ）个结点。 (A) 2k-1 (B) 2k(C) 2k-1(D) 2k-1 9．在二叉排序树中插入一个结点的时间复杂度为（B ）。 (A) O(1) (B) O(n) (C) O(log2n) (D) O(n2) 10．设用链表作为栈的存储结构则退栈操作（B ）。 (A) 必须判别栈是否为满(B) 必须判别栈是否为空 (C) 判别栈元素的类型(D) 对栈不作任何判别 11．下列四种排序中（A ）的空间复杂度最大。 (A) 快速排序(B) 冒泡排序(C) 希尔排序(D) 堆 12．设某二叉树中度数为0的结点数为N0，度数为1的结点数为N l，度数为2的结点数为N2，则下列等式成立的是（C ）。 (A) N0=N1+1 (B) N0=N l+N2(C) N0=N2+1 (D) N0=2N1+l 13.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不 超过（A ）。 (A) log2n+1 (B) log2n-1 (C) log2n (D) log2(n+1) 14．数据的最小单位是（A ）。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 15．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（D ）。 (A) O(log2n) (B) O(1) (C) O(n2) (D) O(n)
数据结构模拟卷(含答案)经典习题
练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 1
6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位 10. 下列图示的顺序存储结构表示的二叉树是( ) 2
数据结构经典例题
数据结构经典例题 1.设计一个算法将L拆分成两个带头节点的单链表L1和L2。 void split(LinkList *&L,LinkList *&L1,LinkList *&L2) { LinkList *p=L->next,*q,*r1; //p指向第1个数据节点 L1=L; //L1利用原来L的头节点 r1=L1; //r1始终指向L1的尾节点 L2=(LinkList *)malloc(sizeof(LinkList));//创建L2的头节点 L2->next=NULL; //置L2的指针域为NULL while (p!=NULL) { r1->next=p; //采用尾插法将*p(data值为ai)插入L1中 r1=p; p=p->next; //p移向下一个节点(data值为bi) q=p->next; //由于头插法修改p的next域,故用q保存*p的后继节点 p->next=L2->next; //采用头插法将*p插入L2中 L2->next=p; p=q; //p重新指向ai+1的节点 } r1->next=NULL; //尾节点next置空 } 2.查找链表中倒数第k个位置上的节点（k为正整数）。若查找成功，算法输出该节点的data域的值，并返回1；否则，只返回0。 typedef struct LNode {int data; struct LNode *link; } *LinkList; int Searchk(LinkList list,int k) { LinkList p,q; int count=0; p=q=list->link; while (p!=NULL) { if (count 数据结构上机实验题目 实验一线性表的顺序存储结构 实验学时 2学时 背景知识:顺序表的插入、删除及应用。 目的要求： 1．掌握顺序存储结构的特点。 2．掌握顺序存储结构的常见算法。 实验容 1．输入一组整型元素序列，建立顺序表。 2．实现该顺序表的遍历。 3．在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。4．判断该顺序表中元素是否对称,对称返回1,否则返回0。 5．实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。 6．输入整型元素序列利用有序表插入算法建立一个有序表。 7．利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。 8. 利用该顺序结构实现循环队列的入队、出队操作。 8．编写一个主函数,调试上述算法。 #include #define OVERFLOW 0 #define MAXSIZE 100 typedef int ElemType; typedef struct list {ElemType elem[MAXSIZE]; int length; }Sqlist; void Creatlist(Sqlist &L) {int i; printf("请输入顺序表的长度："); //输入一组整型元素序列，建立一个顺序表。 scanf("%d",&L.length); for(i=0;i 基本概念典型例题 一、单项选择题 [例6-1]数据结构用集合的观点可以表示为一个二元组DS＝(D，R)。其中，D是( ①)的有穷集合，R是D上( ②)的有限集合。 ①A.算法B. 数据元素C. 数据操作D. 逻辑结构 ②A. 操作B. 映像C. 存储D．关系 解析：由数据结构的集合形式化定义可知，本题答案为：①B；②D。 [例6-2]数据的常用存储结构中不包括( )。 A．顺序存储结构B．线性结构C．索引存储结构D．散列存储结构 解析：数据通常有四种基本的存储方法，即顺序存储方法、链式存储方法、索引存储 方法和散列存储方法。由此可知，本题答案为：B。 [例6-3] 算法指的是( ①)，它必须具备( ②)这三个特性。 ①A．计算方法B．排序方法C．解决问题的步骤序列D．调度方法 ②A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性 C．确定性、有穷性、稳定性D．易读性、稳定性、安全性 解析：算法是对特定问题求解步骤的一种描述，是由若于条指令组成的有限序列。它 必须满足以下性质：输人性、输出性、有穷性、确定性、无二义性和可行性。由此可知，本 题答案为：①㈠②B。 [例6-4] 在下面的程序段中，对x的赋值语句的执行频度为( )。 for(i=0；i 《数据结构》课程设计题目 (程序实现采用C语言) 题目1：猴子选王（学时：3） 一堆猴子都有编号，编号是1，2，3 ...m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 要求：m及n要求从键盘输入，存储方式采用向量及链表两种方式实现该问题求解。 //链表 #include { pCurr = (RingNodePtr)malloc(sizeof(RingNode)); i++; pCurr->pos = i; pPrev->next = pCurr; pPrev = pCurr; } pCurr->next = pHead; // 构成环状链表 } void KickFromRing(RingNodePtr pHead, int n) { RingNodePtr pCurr, pPrev; int i = 1; // 计数 pCurr = pPrev = pHead; while(pCurr != NULL) { if (i == n) { // 踢出环 printf("\n%d", pCurr->pos); // 显示出圈循序 pPrev->next = pCurr->next; free(pCurr); pCurr = pPrev->next; i = 1; } pPrev = pCurr; 《数据结构与算法》复习题 选择题 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构 B．数据结构 C．数据的逻辑结构 D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑 B．存储 C．逻辑和存储 D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。A．数据的处理方法 B．数据元素的类型 C．数据元素之间的关系 D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何 B．结点个数的多少 C．对数据有哪些运算 D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。（1）A．找出数据结构的合理性 B．研究算法中的输入和输出的关系C．分析算法的效率以求改进 C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度 B．正确性和简明性 C．可读性和文档性 D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是 O(n2) 。 s =0; for( I =0; i 1．假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。【北京大学1998 三、1 （5分）】 LinkedList Union(LinkedList la,lb) { pa=la->next; pb=lb->next; la->next=null; while(pa!=null && pb!=null) ∥当两链表均不为空时作 if(pa->data<=pb->data) { r=pa->next; pa->next=la->next; ∥将pa结点链于结果表中，同时逆置。 la->next=pa; pa=r; } else {r=pb->next; pb->next=la->next; ∥将pb结点链于结果表中，同时逆置。 la->next=pb; pb=r; } while(pa!=null) ∥将la表的剩余部分链入结果表，并逆置。 {r=pa->next; pa->next=la->next; la->next=pa; pa=r; } while(pb!=null) {r=pb->next; pb->next=la->next; la->next=pb; pb=r; } } 1）设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中ha表中已有的数据若hb中也有,则hb中的数据不归并到ha中,hb的链表在算法中不允许破坏。【南京理工大学1997 四、3（15分）】 LinkedList Union(LinkedList ha, hb)∥ha和hb是两个无头结点的数据域值递增有序的单链 ｛LinkedList 表，本算法将hb中并不出现在ha中的数据合并到ha中，合并中不能破坏hb链表。 la; la=(LinkedList)malloc(sizeof(LNode)); la->next=ha; pa=ha; pb=hb; pre=la; while(pa&&pb) if(pa->data 习题二 ⒉１描述以下四个概念的区别：头指针变量，头指针，头结点，首结点（第一个结点）。解：头指针变量和头指针是指向链表中第一个结点（头结点或首结点）的指针；在首结点之前附设一个结点称为头结点；首结点是指链表中存储线性表中第一个数据元素的结点。若单链表中附设头结点，则不管线性表是否为空，头指针均不为空，否则表示空表的链表的头指针为空。 2.2简述线性表的两种存储结构有哪些主要优缺点及各自使用的场合。 解：顺序存储是按索引直接存储数据元素，方便灵活，效率高，但插入、删除操作将引起元素移动，降低了效率；而链式存储的元素存储采用动态分配，利用率高，但须增设表示结点之间有序关系的指针域，存取数据元素不如顺序存储方便，但结点的插入和删除十分简单。顺序存储适用于线性表中元素数量基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素的情况；而链式存储适用于频繁进行元素动态插入或删除操作的场合。 2.3 在头结点为h的单链表中，把值为b的结点s插入到值为a的结点之前，若不存在a，就把结点s插入到表尾。 Void insert(Lnode *h,int a,int b) {Lnode *p,*q,*s; s=(Lnode*)malloc(sizeof(Lnode)); s->data=b; p=h->next; while(p->data!=a&&p->next!=NULL) {q=p; p=p->next; } if (p->data==a) {q->next=s; s->next=p;} else {p->next=s; s->next=NULL; } } 2.4 设计一个算法将一个带头结点的单链表A分解成两个带头结点的单链表A和B，使A中含有原链表中序号为奇数的元素，而B中含有原链表中序号为偶数的元素，并且保持元素原有的相对顺序。 Lnode *cf(Lnode *ha) {Lnode *p,*q,*s,*hb; int t; p=ha->next; q=ha; t=0; hb=(Lnode*)malloc(sizeof(Lnode)); s=hb; while(p->next!=NULL) {if (t==0) {q=p;p=p->next;t=1;} else {q->next=p->next; p->next=s->next; s->next=p; s=p; p=p->next; t=0; } } s->next=NULL; return (hb); } 第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 数据结构练习题及参考答案 《数据结构》练习题 一、解答题（共50分） 1、（8分）假设用于通讯的电文字符集及其出现的频率如下表所 请为这8个字符设计哈夫曼编码，并画出其哈夫曼树，计算 WPL。 2.（8分）若一棵二叉树中序遍历和后序遍历序列分别为： DBEHGAFIC和DHGEBIFCA。试画出这棵二叉树，并写出其 先序遍历和层序遍历序列。 3.（16分）以下无向网络以邻接表为存储结构（假设邻接表的 顶点表按字母a、b、c、d、e、f、g、h的顺序依次存储，邻接表 的边表结点按顶点的下标由小到大链接）。请画出其邻接表，并 写出从顶点f出发，分别进行深度和广度优先遍历的序列，写出用Prime方法从顶点c 开始产生最小生成树的边的序列。 4.（8分）已知键值序列为(44，39，67，25，52，59，43，84，54，58，15，26，12，73，92，69)，取填充因子α=0.8，采用线性探查法处理冲突，试构造散列表。 ⒌（5分）已知一组记录为(67,88,15,12,60,37,7,31,45,81)，用希尔排序方法进行排序，d1=5,d2=3,d3=1,则第二趟的排序结果是（）。 ⒍（5分）已知一组记录为(67,88,15,12,60,37,7,31,45,81) ，用堆（大根堆）排序方法进 行排序，第一趟的排序结果是（）。 二、完善程序（共20分，每空2分） 1.假设一组递减有序的原始数据存储在数组r中，存放元素的下标下限为low,下标上限为high,以下是在数组中查找数值为k的折半查找算法。请填空完善程序。 int BinSearch(int r[ ], int low,int high,int k) { int l,h,m; l= low; h= high; while ( ⑴) { m= ⑵; if (k < r[m]) ⑶; else if (k > r[m]) ⑷; else return m; } return 0; } 2. 以下程序功能是将数组r中，从下标first到end之间的元素进行快速排序的分区。请填空，完善程序。 int Partition(int r[ ], int first, int end) { int i,j,t; i=first; j=end; //初始化 while ( ⑸) { while (i 第六章习题 1．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 2．对题1所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。 3．已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，n k个度为k的结点，则该树中有多少个叶子结点并证明之。 4.假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。5．已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？ 6．给出满足下列条件的所有二叉树： ①前序和后序相同 ②中序和后序相同 ③前序和后序相同 7．n个结点的K叉树，若用具有k个child域的等长链结点存储树的一个结点，则空的Child域有多少个？ 8．画出与下列已知序列对应的树Ｔ： 树的先根次序访问序列为GFKDAIEBCHJ； 树的后根次序访问序列为DIAEKFCJHBG。 9．假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为： 0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10 请为这8个字母设计哈夫曼编码。 10．已知二叉树采用二叉链表存放,要求返回二叉树T的后序序列中的第一个结点指针,是否可不用递归且不用栈来完成?请简述原因. 11. 画出和下列树对应的二叉树： 12．已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。 13．编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。 14．分别写函数完成：在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。 15．分别写出算法，实现在中序线索二叉树中查找给定结点*p在中序序列中的前驱与后继。16．编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数。 典型题目分类 §1 概述 ［全真模拟试卷３选择题３］数据结构中，与计算机无关的是数据的 Ａ存储结构Ｂ物理结构Ｃ逻辑结构Ｄ物理和存储结构 答案：Ｃ ［全真模拟试卷５选择题１］数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及Ａ数据的存储结构Ｂ计算方法Ｃ数据映象Ｄ逻辑存储 答案：Ａ ［全真模拟试卷５选择题３］在计算机中，算法是指 Ａ加工方法Ｂ解决方案的准确而完整的描述 Ｃ排序方法Ｄ查询方法 答案：Ｂ ［全真模拟试卷１填空题１］算法的基本特征是可行性、确定性、和拥有足够的情报。 答案：有穷性 ［全真模拟试卷６选择题２］算法分析的目的是 Ａ找出数据结构的合理性Ｂ找出算法中输入和输出之间的关系Ｃ分析算法的易懂性和可靠性Ｄ分析算法的效率以求改进 答案：Ｄ ［全真模拟试卷６填空题１］在算法正确的前提下，评价一个算法的两个标准是。答案：时间复杂度和空间复杂度［专家预测试卷３填空题１］算法的工作量大小和实现算法所需的存储单元多少分别称为算法的。 答案：时间复杂度和空间复杂度 ［全真模拟试卷３选择题１］算法的空间复杂度是指 Ａ算法程序的长度Ｂ算法程序中的指令条数 Ｃ算法程序所占的存储空间Ｄ执行过程中所需要的存储空间答案：Ｄ §2 线性表 ［全真模拟试卷６选择题３］线性表Ｌ＝（a1,a2,……,a i,……,a n），下列说法正确的是 Ａ每个元素都有一个直接前件和直接后件 Ｂ线性表中至少要有一个元素 Ｃ表中诸元素的排列顺序必须是由小到大或由大到小 Ｄ除第一个元素和最后一个元素外，其余每个元素都有且只有一个直接前件和一个直接后件 答案：Ｄ ［全真模拟试卷７选择题１］下列叙述正确的是 Ａ线性表是线性结构Ｂ栈和队列是非线性结构 Ｃ线性链表是非线性结构Ｄ二叉树是线性结构 答案：Ａ ［专家预测试卷３选择题１］根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成 Ａ动态结构和静态结构Ｂ紧凑结构和非紧凑结构 Ｃ线性结构和非线性结构Ｄ内部结构和外部结构 答案：Ｃ ［全真模拟试卷３填空题１］数据的逻辑结构有线性结构和两大类。 答案：非线性结构 ［专家预测试卷１选择题３］线性表的顺序存储结构和线性表的链式存储结构分别是 Ａ顺序存取的存储结构，顺序存取的存储结构 Ｂ随机存取的存储结构，顺序存取的存储结构 Ｃ随机存取的存储结构，随机存取的存储结构 Ｄ任意存取的存储结构，任意存取的存储结构 答案：Ｂ ［全真模拟试卷５填空题１］长度为ｎ的顺序存储线性表中，当在任何位置上插入一个元素概率都相等时，插入一个元素所需移动元素的平均个数为。 答案：ｎ/2 §3 栈和队列 ［全真模拟试卷１选择题１］栈和队列的共同特点是 Ａ都是先进先出Ｂ都是后进先出 Ｃ只允许在端点处插入和删除元素Ｄ没有共同点 答案：Ｃ ［全真模拟试卷２选择题３］如果进栈序列为e1,e2,e3,e4，则可 算法设计综合实训题目 0．逆序数字（借助栈） 编写一个函数，接收一个4位整数值，返回这个数中数字逆序后的结果值。例如，给定数7631，函数返回1367. 输入： 第一行一个正整数T（T<=10），表示有T组测试数据; 以下T行，每行一个非负的整数N。 输出： 共T行，对于每组输入数据输出一行，即数字逆序后的结果值。 样本输入： 3 7631 1018 5158 样本输出： 1367 8101 8515 1．人见人爱A+B 这个题目的A和B不是简单的整数，而是两个时间，A和B 都是由3个整数组成，分别表示时分秒，比如，假设A为34 45 56，就表示A所表示的时间是34小时 45分钟 56秒。 输入： 输入数据有多行组成，首先是一个整数N，表示测试实例的个数，然后是N行数据，每行有6个整数AH,AM,AS,BH,BM,BS，分别表示时间A和B所对应的时分秒。题目保证所有的数据合法。 输出： 对于每个测试实例，输出A+B，每个输出结果也是由时分秒3部分组成，同时也要满足时间的规则（即：分和秒的取值范围在0-59），每个输出占一行，并且所有的部分都可以用32位整数表示。 样本输入： 2 1 2 3 4 5 6 34 45 56 12 23 34 样本输出： 5 7 9 47 9 30 2．敲七 【问题描述】 输出7和7的倍数，还有包含7的数字例如（17，27，37...70，71，72，73...） 【要求】 【数据输入】一个整数N。(N不大于30000) 【数据输出】从小到大排列的不大于N的与7有关的数字，每行一个。 【样例输入】 20 【样例输出】 7 14 17 3．统计同成绩学生人数问题 【问题描述】 读入N名学生的成绩，将获得某一给定分数的学生人数输出。 【要求】 【数据输入】测试输入包含若干测试用例，每个测试用例的格式为 第1行：N 第2行：N名学生的成绩，相邻两数字用一个空格间隔。 第3行：给定分数 当读到N=0时输入结束。其中N不超过1000，成绩分数为（包含）0到100之间的一个整数。 【数据输出】对每个测试用例，将获得给定分数的学生人数输出。 【样例输出】 3 80 60 90 60 2 85 66 5 60 75 90 55 75 75 【样例输出】 1 2 4．高斯日记 大数学家高斯有个好习惯：无论如何都要记日记。他的日记有个与众不同的地方，他从不注明年月日，而是用一个整数代替，比如：4210。后来人们知道，那个整数就是日期，它表示那一天是高斯出生后的第几天。这或许也是个好习惯，它时时刻刻提醒着主人：日子又过去一天，还有多少时光可以用于浪费呢？ 高斯出生于：1777年4月30日。 数据结构经典案例 1.停车场问题 停车场管理员的任务就是帮助车主把车停放在停车场中，或者是帮助车主将车开出乘车场。然后停车场中能够停放的车辆数目很多，这就使得让莫辆车开出停车场变得复杂。比如：要开走一辆车，则管理员需要把他前面的车全部暂时清除，然后等这辆车开出后再将这些车重新放入停车场。当然了，这个时候腾出了一个空位置，此位置由后面的车占据。 任务：编程模拟这样的情况，这里假设停车场最多可停放5辆车。data.txt记录了某一时间段内，该停车场车辆的到来与离开记录，刚开始，停车场是空的。其中大写字母A--P是车辆的代号，arrives--到来，departs---离开。 程序需要从data.txt中读取这些信息，并且用这些数据来模拟停车场的车辆调度情况。 data.txt内容如下： A arrives A departs B arrives C arrives D arrives C departs E arrives F arrives G arrives B departs H arrives D departs E departs I arrives I departs J arrives F departs K arrives L arrives M arrives H departs N arrives J departs K departs O arrives P arrives P departs O departs L departs 实现代码如下： 模拟停车场问题.cpp（没有再继续分.h文件，混为一体了，主要.h文件过于简单）经典数据结构上机题_答案解析
数据结构典型例题
数据结构经典题目c语言代码
数据结构(C语言)【经典题库】含标准答案
数据结构经典算法试题
数据结构上机例题及答案
数据结构课后习题详解(超完整,超经典)
数据结构练习题及
数据结构课后习题及解析第六章
[IT认证]全国计算机等级考试《数据结构》典型试题
《算法设计综合实训》题目讲解
数据结构经典案例教学文案