数据结构第一至四章练习题

第1章概论习题参考解答一、填空题1、数据的逻辑结构是数据元素之间的逻辑关系，通常有下列4类：（）、（）、（）、（）。

【答】集合、线性结构、树型结构和图状结构。

2、数据的存储结构是数据在计算机存储器里的表示，主要有4种基本存储方法：（）、（）、（）、（）。

【答】顺序存储方法、链接存储方法、索引存储方法和散列存储方法。

二、选择题1、一个算法必须在执行有穷步之后结束，这是算法的（）。

（A）正确性（B）有穷性（C）确定性（D）可行性【答】B。

2、算法的每一步，必须有确切的定义。

也就是说，对于每步需要执行的动作必须严格、清楚地给出规定。

这是算法的（）。

（A）正确性（B）有穷性（C）确定性（D）可行性【答】C。

3、算法原则上都是能够由机器或人完成的。

整个算法好像是一个解决问题的“工作序列”，其中的每一步都是我们力所能及的一个动作。

这是算法的（）。

（A）正确性（B）有穷性（C）确定性（D）可行性【答】D。

三、简答题1、算法与程序有何异同？【答】尽管算法的含义与程序非常相似，但两者还是有区别的。

首先，一个程序不一定满足有穷性，因此它不一定是算法。

例如，系统程序中的操作系统，只要整个系统不遭受破坏，它就永远不会停止，即使没有作业要处理，它仍处于等待循环中，以待一个新作业的进入。

因此操作系统就不是一个算法。

其次，程序中的指令必须是计算机可以执行的，而算法中的指令却无此限止。

如果一个算法采用机器可执行的语言来书写，那么它就是一个程序。

2、什么是数据结构？试举一个简单的例子说明。

【答】数据结构是指数据对象以及该数据对象集合中的数据元素之间的相互关系（即数据元素的组织形式）。

例如，队列的逻辑结构是线性表（先进先出）；队列在计算机中既可以采用顺序存储也可以采用链式存储；对队列可进行删除、插入数据元素以及判断是否为空队列、将队列置空等操作。

3、什么是数据的逻辑结构？什么是数据的存储结构？【答】数据元素之间的逻辑关系，也称为数据的逻辑结构。

1-4章复习题答案一、选择题。

1. 算法的计算量的大小称为计算的（ b ）。

A．效率 B. 复杂性 C. 现实性 D. 难度2.计算机算法指的是（1c），它必须具备（2b）这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性3. 下面关于算法说法错误的是（ d ）A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的4. 下面说法错误的是（ c ）(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)5．从逻辑上可以把数据结构分为（ c ）两大类。

A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构6．程序段 For(i=n-1;i>0;i--)For(j=1;j<=i;j++)If(a[j]>a[j+1])a[j]←→a[j+1]其中 n为正整数，则最后一行的语句时间复杂度在最坏情况下是（ d ）A. O（n）B. O(nlogn)C. O(n3)D. O(n2)7．下述哪一条是顺序存储结构的优点？（ a ）A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示8．下面关于线性表的叙述中，错误的是哪一个？（ b ）A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

最新版《数据结构》各章习题及答案第一章绪论一、选择题1.组成数据的基本单位是（）（A）数据项（B）数据类型（C）数据元素（D）数据变量2.数据结构是研究数据的（）以及它们之间的相互关系。

（A）理想结构，物理结构（B）理想结构，抽象结构（C）物理结构，逻辑结构（D）抽象结构，逻辑结构3.在数据结构中，从逻辑上可以把数据结构分成（）（A）动态结构和静态结构（B）紧凑结构和非紧凑结构（C）线性结构和非线性结构（D）内部结构和外部结构4.数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间的（②）和运算等的学科。

① （A）数据元素（B）计算方法（C）逻辑存储（D）数据映像② （A）结构（B）关系（C）运算（D）算法5.算法分析的目的是（）。

（A）找出数据结构的合理性（B）研究算法中的输入和输出的关系（C）分析算法的效率以求改进（D）分析算法的易懂性和文档性6.计算机算法指的是（①）,它必须具备输入、输出和（②）等5 个特性。

① （A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法② （A）可执行性、可移植性和可扩充性（B）可行性、确定性和有穷性（C）确定性、有穷性和稳定性（D）易读性、稳定性和安全性二、判断题1.数据的机内表示称为数据的存储结构。

（）2.算法就是程序。

（）3.数据元素是数据的最小单位。

（）4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。

（）5.算法的时间复杂度取决于问题的规模和待处理数据的初态。

（）三、填空题1.数据逻辑结构包括________、________、_________ 和__________ 四种类型,其中树形结构和图形结构合称为_____ 。

2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______ 个前驱结点；最后一个结点______后续结点,其余每个结点有且只有 _______ 个后续结点。

3.在树形结构中,树根结点没有_______ 结点,其余每个结点有且只有_______个前驱结点；叶子结点没有 ________ 结点,其余每个结点的后续结点可以_________。

各章习题各章习题 (1)第一章绪论（7） (1)第二章线性表（6） (1)第三章栈和队列（5） (2)第四章串（3） (2)第五章数组（3） (3)第六章二叉树（20） (3)第七章图（5） (5)第九章查找（5） (6)第十章排序（8） (6)第一章绪论（7）1、数据结构中的4种逻辑结构是_________、__________、_________、_________.2．在数据结构中，从逻辑上可以把数据结构分成_________。

A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构3、一个算法除了输入和输出特性外，还必须具有的特性不包括_____A有穷性 B 可扩展性 C 确定性D可行性4.算法分析的两个主要方面是____。

A．空间复杂性和时间复杂性B．正确性和简明性C．可读性和文档性D．数据复杂性和程序复杂性5.设有数据结构D={d1,d2,d3,d4}，R={(d1,d2),(d2,d3),(d3,d4)}画出相关逻辑图6．设图G=(V,E),V={1,2,3,4,5,6},E={<1,2>,<1,3>,<2,5>,<3,6>,<6,5>,<5,4>,<6,4>}。

请画出该图7．计算下列标有@语句的频度i=1;j=0;while (i+j<=n){if(i<j) j++ //@else i++;}第二章线性表（6）1．在n个元素的顺序表中插入或删除一个元素，需要平均移动________个元素。

2．带头结点的单循环链表，判定表空的条件是(设指向头结点的指针是H)_________________。

3. 不带头结点的单链表head为空的判定条件是___________A.head == NULLB.head->next == NULLC.head->next == headD.head != NULL4．线性表的顺序存储结构是一种______的存储结构，线性表的链式存储结构是一种______的存储结构。

第一章绪论一、选择题1.D2.C3.C4.B5.D6.C7.D8.C9.A 10.D11.D 12.B二、填空题1. 逻辑结构存储结构运算2. 集合结构线性结构树形结构图状结构3. 有穷性. 确定性. 可行性. 输入. 输出4. 顺序存储. 链式存储5. 数据元素6. 线性结构非线性结构三、简答题1. 尽管算法的含义与程序非常相似，但两者还是有区别的。

首先，一个程序不一定满有穷性，因为它不是一个算法。

其次，程序中的指令必须是计算机可以执行的，而算法中的指令却无此限制。

如果一个算法采用机器可执行的语言来书写，那么它就是一个程序。

2. 数据结构是指数据对象以及该数据对象集合中的数据元素之间的相互关系（数据元素的组织形式）。

例如：队列的逻辑结构是线性表（先进后出）；队列在计算机中既可以采用顺序存储也可以采用链式存储；队列可进行删除数据元素. 插入数据元素. 判断是否为空队列，以及队列置空等操作。

3. 数据元素之间的逻辑关系，也称为数据的逻辑结构。

数据元素以及它们之间的相互关系在计算机存储器内的表示（又称映像）称为数据的存储结构，也称数据的物理结构。

4. 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或者多个操作。

此外，一个算法还具有下列5个特性：（1）有穷性：一个算法必须在执行有穷步之后结束，即算法必须在有限时间内完成。

（2）确定性：算法中每一步必须有明确的含义，不会产生二义性。

并且，在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。

（3）可行性：一个算法是能执行的，即算法中的每一步都可以通过已经实现的基本运算执行有限次得以实现。

（4）输入：一个算法有零个或者多个输入，它们是算法开始时对算法给出的初始量。

（5）输出：一个算法有一个或者多个输出，它们是与输入有特定关系的量5. 举例说明四种基本结构的区别:集合: 数据元素之间无任何关系,如集合A={x,5,t,&};线性结构: 数据元素之间存在一个对一个的关系,如线性表L=（2,3，4,5,7,10）；树形结构: 数据元素之间存在一个对多个的关系,如文件系统目录管理；图状结构: 数据元素之间存在多个对多个的关系,如教学计划课程安排顺序图。

数据结构习题集（自编）第一章绪论一、选择题1．数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的（）和运算的学科。

A．结构B．关系 C．运算 D．算法2．在数据结构中，从逻辑上可以把数据结构分成（）。

A．动态结构和静态结构 B．紧凑结构和非紧凑结构C．线性结构和非线性结构 D．逻辑结构和存储结构3．线性表的逻辑顺序和存储顺序总是一致的，这种说法（）。

A．正确B．不正确 C．无法确定 D．以上答案都不对4．算法分析的目的是（）。

A．找出算法的合理性 B．研究算法的输人与输出关系C．分析算法的有效性以求改进 D．分析算法的易懂性5. 算法的时间复杂度取决于（）A．问题的规模B待处理数据的初态 C. A和B6．一个算法应该是（）。

A．程序B．问题求解步骤的描述C．要满足五个基本特性 D．A和C.7. 下面关于算法说法错误的是（）A．算法最终必须由计算机程序实现B.为解决某问题的算法与为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的8．以下与数据的存储结构无关的术语是（）。

A．循环队列 B. 链表 C. 哈希表 D. 栈9．在下面的程序段中，对x的赋值语句的频度为（）for（i=0;i<n;i++）for(j=0;j<n;j++)x=x+1;nA． 2n B．n C．n2 D．log210．以下数据结构中，（）是非线性数据结构A．树 B．字符串 C．队列 D．栈11. 下列数据中，（）是线性数据结构。

A．哈夫曼树 B.有向无环图 C. 二叉排序树 D. 栈12．以下属于逻辑结构的是（）。

A．顺序表 B. 哈希表 C.有序表 D. 单链表二、填空题1、_______是信息的载体，是对客观事物的符号表示，它能够被计算机识别、存储、加工和处理，________是对能够有效的输人到计算机中并且能够被计算机处理的符号的总称。

（数据、数据）2、数据元素是数据的______，有些情况下也称为元素、结点、顶点、记录等。

数据结构1-4章习题答案一、名词解释抽象数据类型、数据结构、数据结构的逻辑结构、数据结构的物理结构、算法、算法评价、时间复杂度、大O表示法、线性表、栈、队列、广义表、稀疏矩阵二、填空1、抽象数据类型是由一组数据结构和在该组数据结构上的一组操作所组成。

2、在定义某种数据结构时，其数据域的数据类型可分为简单类型和结构体类型两种，为增强其通用性，应将其再定义为通用数据类型。

3、如果将线性数据结构关系描述为1：1，那么树型和图型数据结构应分别为1：N、M：N5、算法应具备以下5个特性：有穷性、正确性、可行性、输入和输出。

6、在分析各种算法的时间复杂度时，一般只讨论相应的数量级，用f(n)表示，请问其中n的含义是处理问题的样本量7、对于一个以顺序实现的循环队列Q[m]，队首、队尾指针分别为f 和r，其盘空的条件是f=r，盘满的条件是(r+1)%m=f8、循环链表的主要优点是最大限度的利用空间9、链表对于数据元素的插入和删除不需要移动结点，只需改变相关结点的指针域的值。

10、在一个链式栈中，若栈顶指针等于NULL，则为空栈11、主程序第一次调用递归函数被称为外部调用，递归函数自己调用自己被称为内部调用，它们都需要利用栈保存调用后的返回地址地址。

12、某算法在求解一个10阶方程组时，运算次数是500，求解一个30阶方程组时，运算次数是4500，则该算法的时间复杂度为O（N2）三、选择题1、对一个线性表的存取操作很少，而插入和删除操作较多时应采用B存储结构。

A．顺序存储B.链式存储C.索引存储D.散列式存储2、对一个线性表的随机存取操作较多时，应采用B存储结构。

A.静态顺序存储B.动态顺序存储C.动态链接存储D.静态链接存储3、对一个顺序存储结构的栈，栈满的判断条件是（D）A.S.top==-1B.S.top==0C.S.top==Ma某SizeD.S.top==Ma某Size-14、若循环队列有n个顺序存储单元，front、rear分别为队首和队尾指针则判断队满的条件是(C)A.(front+1)%n==rearB.(front-1)%n==rearC.(rear+1)%n==frontD.(rear-1)%n==front5、下列是顺序存储线性表排序的算法voidSort(Lit&L){}问：此算法的时间复杂性为：BA.O(n)B.(n2)C.(n某i)D.(n某j) inti,j;ElemType某;for(i=1;i某=L.lit[i];for(j=i-1;j>=0;j--)if(某L.lit[j+1]=L.lit[j];elebreak;L.lit[j+1]=某;四、简答题1、简述线性表的顺序存储和链接存储实现的异同。

【基础知识题】1. 简述下列术语：数据、数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。

2. 在程序设计中，常用下列三种不同的出错处理方式：(1) 用exit语句终止执行并报告错误；(2) 以函数的返回值区别正确返回或错误返回；(3) 设置一个整型变量的函数参数以区别正确返回或某种错误返回。

试讨论这三种方法各自的优缺点，并编写算法，计算i!×2i 的值并存入数组a[0..arrsize-1] 的第i-1 个分量中(i=1,2,…,n)。

假设计算机中允许的整数最大值为maxint，则当n>arrsize 或对某个k(1≤k≤n) 使k!×2k>maxint 时，应按出错处理。

注意选择你认为较好的出错处理方法。

3. 在程序设计中，可采用下列三种方法实现输出和输入：(1) 通过scanf 和printf 语句；(2) 通过函数的参数显式传递；(3) 通过全局变量隐式传递。

试讨论这三种方法的优缺点，并编写算法求一元多项式的值，并确定算法中每一语句的执行次数和整个算法的时间复杂度。

注意选择你认为较好的输入和输出方法，本题的输入为ai (i=0,1,…,n)，x0 和n，输出为。

4. 设n 为正整数。

试确定下列各程序段中前置以记号@ 的语句的频度：(1) i=1; k=0;while ( i<=n-1) {@ k += 10 * i;i++;}(2) i=1; k=0;do {@ k +=10 * i;i++;} while(i<=n-1);(3) i = 1; k = 0;while (i<=n-1) {i++ ;@ k+= 10 * i;}(4) k=0;for( i=1; i<=n; i++) {for (j=i ; j<=n; j++)@ k++;}(5) for( i=1; i<=n; i++) {for (j=1; j<=i; j++) {for (k=1; k<=j; k++)@ x += delta;}(6) i=1; j=0;while (i+j<=n) {@ if (i>j ) j++ ;else i++ ;}(7) x=n; y=0; // n 是不小于1的常数while (x>=(y+1)*(y+1)) {@ y++;}(8) x=91; y=100;while (y>0 ) {@ if (x>100 ) { x -= 10; y- -; }else x++;}第二章线性表【基础知识题】1. 描述以下三个概念的区别：头指针，头结点，首元结点(第一个元素结点)。