李春葆《数据结构教程》(C++语言描述)模拟试题及详解(一~二)【圣才出品】

第四部分模拟试题李春葆《数据结构教程》（第4版）模拟试题及详解（一）一、单项选择题（每小题2分，共20分）1．队列的特点是（）。

A．先进后出B．先进先出C．任意位置进出D．前面都不正确【答案】B2．有n个记录的文件，如关键字位数为d，基数为r，则基数排序共要进行（）遍分配与收集。

A．nB．dC．rD．n-d【答案】B【解析】基数排序是按组成关键字的各位值进行分配收集而完成的。

3．在二叉树节点的先序序列、中序序列和后序序列中，所有叶子节点的先后顺序（）。

A．都不相同B．完全相同C．先序和中序相同，而与后序不同D．中序和后序相同，而与先序不同【答案】B【解析】无论是哪种遍历方式，遍历叶子节点时，都是先访问左子树，后访问右子树。

4．限定在一端加入和删除元素的线性表称为（）。

A．双向链表B．单向链表C．栈D．队列【答案】C【解析】根据栈后进先出的特性，可见栈都在一端对元素进行操作。

5．设内存工作区可容纳8个记录，初始文件共有64个关键字不同的记录，且已按关键字递减排列，如用置换．选择排序产生初始归并段，最长初始归并段所含记录数是（）。

A．6B．7C．8D．9【答案】C【解析】对于置换选择排序，输入的文件是以关键字降序排列时，所得的初始归并段的最大长度为工作区的大小。

当输入的文件以关键字的升序排序时，只能得到一个长度为文件长度的初始归并段。

6．设森林F对应的二叉树为B，它有m个节点，B的根为p，p的右子树上的节点个数为n，森林F中第一棵树的节点个数是（）。

A．m-n-1B．n+lC．m-n+1D．m-n【答案】D7．设有198个初始归并段，如采用K-路平衡归并三遍完成排序，则K值最大为（）。

A．12B．13C．14D．15【答案】C【解析】k一路平衡归并，归并趟数公式s=[1og k m]，m指归并段数，s指趟数。

要三遍完成遍历，那就看两遍完成排序的需遍历的最小数。

把s=2和m=198带入公式，可知两遍完成排序时k最小为15，所以k<15。

李春葆《数据结构教程》（C++语⾔描述）模拟试题及详解（⼀）李春葆《数据结构教程》（C++语⾔描述）模拟试题及详解（⼀）⼀、单项选择题（每⼩题2分，共20分）1．队列的特点是（）。

A．先进后出B．先进先出C．任意位置进出D．前⾯都不正确【答案】B2．有n个记录的⽂件，如关键字位数为d，基数为r，则基数排序共要进⾏（）遍分配与收集。

A．nB．dC．rD．n-d【答案】B【解析】基数排序是按组成关键字的各位值进⾏分配收集⽽完成的。

3．在⼆叉树节点的先序序列、中序序列和后序序列中，所有叶⼦节点的先后顺序（）。

A．都不相同B．完全相同C．先序和中序相同，⽽与后序不同D．中序和后序相同，⽽与先序不同【答案】B【解析】⽆论是哪种遍历⽅式，遍历叶⼦节点时，都是先访问左⼦树，后访问右⼦树。

4．限定在⼀端加⼊和删除元素的线性表称为（）。

A．双向链表B．单向链表C．栈D．队列【答案】C【解析】根据栈后进先出的特性，可见栈都在⼀端对元素进⾏操作。

5．设内存⼯作区可容纳8个记录，初始⽂件共有64个关键字不同的记录，且已按关键字递减排列，如⽤置换．选择排序产⽣初始归并段，最长初始归并段所含记录数是（）。

A．6B．7C．8D．9【答案】C【解析】对于置换选择排序，输⼊的⽂件是以关键字降序排列时，所得的初始归并段的最⼤长度为⼯作区的⼤⼩。

当输⼊的⽂件以关键字的升序排序时，只能得到⼀个长度为⽂件长度的初始归并段。

6．设森林F对应的⼆叉树为B，它有m个节点，B的根为p，p的右⼦树上的节点个数为n，森林F中第⼀棵树的节点个数是（）。

A．m-n-1B．n+lC．m-n+1D．m-n【答案】D7．设有198个初始归并段，如采⽤K-路平衡归并三遍完成排序，则K值最⼤为（）。

A．12B．13C．14D．15【答案】C【解析】k⼀路平衡归并，归并趟数公式s=[1og k m]，m指归并段数，s指趟数。

要三遍完成遍历，那就看两遍完成排序的需遍历的最⼩数。

第10章外排序一、单项选择题（1）以下关于外排序的叙述正确的是______。

A．外排序把外存文件调入内存，再利用内排序方法进行排序，所以外排序所花的时间完全由采用的内排序确定B．外排序所花的时间=内排序时间+外存信息读／写时间+内部归并所花的时间C．外排序并不涉及文件的读／写操作D．外排序完全可以由内排序来替代【答案】B【解析】外排序所花的时间由内排序时间、外存读写时间、内部归并时间三部分时间构成，因此AC两项错误，B项正确；外排序要将文件读取到内存中进行排序，但是由于文件大小可能会大于内存的最大容量，因此外排序不能完全由内排序替代。

（2）如果将一个由置换-选择排序得到的输出文件F1（含所有初始归并段）作为输入文件再次进行置换-选择排序，得到输出文件F2（含所有初始归并段），则F1和F2的差异是______。

A．F2中归并段的个数减少B．F2中归并段的最大长度增大C．F2和F1无差异D ．归并段个数及各归并段长度均不变，但F 2中可能存在与F 1不同的归并段【答案】C 【解析】当进行一次置换-选择排序后，文件的归并段即达到理想状态，无论再进行多少次排序，均不会发生变化，因此答案为C 项。

（3）采用败者树进行k 路平衡归并的外排序算法，其总的归并效率与k______。

A ．有关B ．无关【答案】A【解析】利用败者树进行k 路平衡归并不会影响总共需要的关键字比较次数，但是随着k 的增大，归并树的高度会减小，磁盘读/写的次数也就相应减少，从而提高总的归并效率，因此答案为A 项。

（4）对m 个初始归并段实施k 路平衡归并排序，所需的归并趟数是______。

A ．1B ．m/kC ．/m k ⎡⎤⎢⎥D ．log k m ⎡⎤⎢⎥【答案】D【解析】采用k 路归并，相应的归并树就有log k m ⎡⎤⎢⎥+1层，则需要归并的趟数为log k m ⎡⎤⎢⎥，答案为D 项。

（5）设有100个初始归并段，如果采用k 路平衡归并3趟完成排序，则k 值最小是______。

第二部分课后习题第1章绪论1．简述数据与数据元素的关系与区别。

答：凡是能被计算机存储、加工的对象统称为数据，数据是一个集合。

数据元素是数据的基本单位，是数据的个体。

数据与元素之间的关系是元素与集合之间的关系。

2．数据结构和数据类型有什么区别？答：数据结构是互相之间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容，即数据的逻辑结构、存储结构和数据的运算。

而数据类型是一个值的集合和定义在这个集合上的一组运算的总称，如C语言中的int数据类型是由-32768~32767（16位机）的整数和+、-、*、/、%等运算符组成。

3．设3个表示算法频度的函数f、g和h分别为：f（n）=100n3+n2+1000g（n）=25n3+5000n2h（n）=n1.5+5000nlog2n求它们对应的时间复杂度。

答：f（n）=100n3+n2+1000=O（n3），g（n）=25n3+5000n2=O（n3），当n→∞时，√n>log2n，所以h（n）=n1.5+5000nlog2n=O（n1.5）。

4．用C／C++语言描述下列算法，并给出算法的时间复杂度。

（1）求一个n阶方阵的所有元素之和。

（2）对于输入的任意三个整数，将它们按从小到大的顺序输出。

（3）对于输入的任意n个整数，输出其中的最大和最小元素。

答：（1）算法如下：本算法的时间复杂度为O（n2）。

（2）算法如下：本算法的时间复杂度为O（1）。

（3）算法如下：本算法的时间复杂度为O（n）。

5．设n为正整数，给出下列各种算法关于n的时间复杂度。

（1）（2）（3）答：（1）设while循环语句执行次数为T（n），则：（2）算法中的基本运算语句是if（b[k]>b[j]）k=j，其执行次数T（n）为：（3）设while循环语句执行次数为T（n），则：则6．有以下递归算法用于对数组a[i．．j]的元素进行归并排序：求mergesort（a，0，n－1）的时间复杂度。

第二部分课后习题第1章绪论1．简述数据与数据元素的关系与区别。

答：凡是能被计算机存储、加工的对象统称为数据，数据是一个集合。

数据元素是数据的基本单位，是数据的个体。

数据与元素之间的关系是元素与集合之间的关系。

2．数据结构和数据类型有什么区别？答：数据结构是互相之间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容，即数据的逻辑结构、存储结构和数据的运算。

而数据类型是一个值的集合和定义在这个集合上的一组运算的总称，如C语言中的int数据类型是由-32768~32767（16位机）的整数和+、-、*、/、%等运算符组成。

3．设3个表示算法频度的函数f、g和h分别为：f（n）=100n3+n2+1000g（n）=25n3+5000n2h（n）=n1.5+5000nlog2n求它们对应的时间复杂度。

答：f（n）=100n3+n2+1000=O（n3），g（n）=25n3+5000n2=O（n3），当n→∞时，√n>log2n，所以h（n）=n1.5+5000nlog2n= O（n1.5）。

4．用C／C++语言描述下列算法，并给出算法的时间复杂度。

（1）求一个n阶方阵的所有元素之和。

（2）对于输入的任意三个整数，将它们按从小到大的顺序输出。

（3）对于输入的任意n个整数，输出其中的最大和最小元素。

答：（1）算法如下：本算法的时间复杂度为O（n2）。

（2）算法如下：本算法的时间复杂度为O（1）。

（3）算法如下：本算法的时间复杂度为O（n）。

5．设n为正整数，给出下列各种算法关于n的时间复杂度。

（1）（2）（3）答：（1）设while循环语句执行次数为T（n），则：（2）算法中的基本运算语句是if（b[k]>b[j]）k=j，其执行次数T（n）为：（3）设while循环语句执行次数为T（n），则：则6．有以下递归算法用于对数组a[i．．j]的元素进行归并排序：求mergesort（a，0，n－1）的时间复杂度。

第1章绪论教材中练习题及参考答案1. 简述数据与数据元素的关系与区别。

答：凡是能被计算机存储、加工的对象统称为数据，数据是一个集合。

数据元素是数据的基本单位，是数据的个体。

数据元素与数据之间的关系是元素与集合之间的关系。

2. 采用二元组表示的数据逻辑结构S=<D，R>，其中D={a，b，…，i}，R={r}，r={<a，b>，<a，c>，<c，d>，<c，f>，<f，h>，<d，e>，<f，g>，<h，i>}，问关系r是什么类型的逻辑结构？哪些结点是开始结点，哪些结点是终端结点？答：该逻辑结构为树形结构，其中a结点没有前驱结点，它是开始结点，b、e、i和g、结点没有后继结点，它们都是终端结点。

3. 简述数据逻辑结构与存储结构的关系。

答：在数据结构中，逻辑结构与计算机无关，存储结构是数据元素之间的逻辑关系在计算机中的表示。

存储结构不仅将逻辑结构中所有数据元素存储到计算机内存中，而且还要在内存中存储各数据元素间的逻辑关系。

通常情况下，一种逻辑结构可以有多种存储结构，例如，线性结构可以采用顺序存储结构或链式存储结构表示。

4. 简述数据结构中运算描述和运算实现的异同。

答：运算描述是指逻辑结构施加的操作，而运算实现是指一个完成该运算功能的算法。

它们的相同点是，运算描述和运算实现都能完成对数据的“处理”或某种特定的操作。

不同点是，运算描述只是描述处理功能，不包括处理步骤和方法，而运算实现的核心则是设计处理步骤。

5. 数据结构和数据类型有什么区别？答：数据结构是相互之间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容，即数据的逻辑结构、存储结构和数据的运算。

而数据类型是一个值的集合和定义在这个值集上的一组运算的总称，如C语言中的short int数据类型是由-32768～32767（16位机）的整数和+、-、*、/、%等运算符构成。

第1章绪论1.1复习笔记一、数据结构1．概述（1）计算机对具体问题的处理在用计算机解决一个具体的问题时，大致需要经过以下几个步骤：①分析问题，确定数据模型。

②设计相应的算法。

③编写程序，运行并调试程序，直至得到正确的结果。

（2）数据的含义①数据是描述客观事物的数、字符以及所有能输入到计算机中并被计算机程序处理的符号的集合。

从计算机的角度看，数据是所有能被输入到计算机中，且能被计算机处理的符号的集合。

它是计算机操作的对象的总称，也是计算机所处理信息的某种特定的符号表示形式。

②数据元素是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理，有些情况下数据元素也称为元素、结点、记录等。

一个数据元素可以由若干个数据项组成。

数据项是具有独立含义的数据的最小单位，也称为域。

③数据对象是性质相同的有限个数据元素的集合，它是数据的一个子集。

默认情况下，数据结构中的数据指的都是数据对象。

（3）数据结构的定义数据结构是指所有数据元素以及数据元素之间的关系，可以看作是相互之间存在特定关系的数据元素的集合，因此，可时把数据结构看成是带结构的数据元素的集合。

数据结构包括以下几个方面：①数据元素之间的逻辑关系，即数据的逻辑结构，它是数据结构在用户面前呈现的形式。

数据的逻辑结构是从逻辑关系（主要指数据元素的相邻关系）上描述数据的，它与数据的存储无关，是独立于计算机的。

因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

②数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构，也称为数据的物理结构。

数据的存储结构是逻辑结构用计算机语言的实现或在计算机中的表示（也称为映像），也是指逻辑结构在计算机中的存储方式，它是依赖于计算机语言的。

一般情况下，只在高级语言（如C、C++、Java语言）的层次上讨论存储结构。

③施加在该数据上的操作，即数据的运算。

数据的运算是定义在数据的逻辑结构之上的，每种逻辑结构都有一组相应的运算。