数据结构第一章试题

数据结构单元1练习参考答案单元练习1一．判断题（下列各题，正确的请在前面的括号内打√；错误的打w ）（√）（1）数据的逻辑结构与数据元素本身的内容和形式无关。

（√）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。

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

（ㄨ）（4）数据的逻辑结构和数据的存储结构是相同的。

（ㄨ）（5）程序和算法原则上没有区别，所以在讨论数据结构时可以通用。

（√）（6）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。

（√）（7）数据的存储结构是数据的逻辑结构的存储映像。

（√）（8）数据的物理结构是指数据在计算机内实际的存储形式。

（ㄨ）（9）数据的逻辑结构是依赖于计算机的。

（√）（10）算法是对解题方法和步骤的描述。

二．填空题（1）数据有逻辑结构和存储结构两种结构。

（2）数据逻辑结构除了集合以外，还包括：线性结构、树形结构和图形结构。

（3）数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。

（4）树形结构和图形结构合称为非线性结构。

（5）在树形结构中，除了树根结点以外，其余每个结点只有1 个前趋结点。

（6）在图形结构中，每个结点的前趋结点数和后续结点数可以任意多个。

（7）数据的存储结构又叫物理结构。

（8）数据的存储结构形式包括：顺序存储、链式存储、索引存储和散列存储。

（9）线性结构中的元素之间存在一对一的关系。

（10）树形结构结构中的元素之间存在一对多的关系，（11）图形结构的元素之间存在多对多的关系。

（12）数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）三个方面的内容。

（13）数据结构被定义为(D，R)，其中D 是数据的有限集合，R是D上的关系的有限集合。

（14）算法是一个有穷指令的集合。

（15）算法效率的度量可以分为事先估算法和事后统计法。

（16）一个算法的时间复杂性是算法输入规模的函数。

（17）算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模n的函数。

《数据结构》第一章绪论习题1-1 什么叫数据？什么叫数据元素？什么叫数据项？1-2 什么叫数据的物理结构？什么叫数据的存储结构？什么叫数据的操作？1-3 数据结构课程主要讨论哪三个方面的问题？1-4 分别画出线性结构、树结构和图结构的逻辑示意图。

1-5 什么叫类型？什么叫数据类型？什么叫抽象数据类型？1-6 怎样利用抽象数据类型设计大型软件？1-7 什么叫算法？算法的5个性质是什么？1-8 根据算法的性质解释算法和程序的区别？1-9 评判算法的优劣有哪几种方法？1-10 什么叫算法的时间复杂度？怎样表示算法的时间复杂度？1-11 设n为已在算法前边定义的整数类型，并已知n为正整数，分析下列各算法中加下划线语句的执行次数，并给出各算法的时间复杂度T(n)。

(1) int i = 1, k = 0;while (i < n-1){k = k + 10 * i; i = i + 1;}(2) int i = 1, k = 0;do{k = k + 10 * i; i = i + 1;}while (i != n);(3) int i = 1, j = 1;while (i <= n && j <= n){i = i + 1; j = j + 1;}(4) int x = n; /* n > 1 */int y = 0;while(x >= (y+1)*(y+1))y++;(5) int i, j, k, x = 0;for (i = 0; i < n; i++)for (j = 0; j < i; j++)for (k = 0; k < j; k++)x = x + 2;1-12 设求解同一个问题有三种算法，三种算法各自的时间复杂度分别为O(n2)，O(2n)和O(nlg n)，哪种算法最可取？为什么？1-13 按增长率从小到大的顺序排列下列各组函数：（1）2100，（3/2）n，（2/3）n，（4/3）n（2）n，n3/2，n2/3，n!，n n（3）lb n，n×lb n，n lb n，n*1-14 下面是几个典型的时间复杂度函数估值问题：（1）当n为正整数时，n取何值能使2n> n3；（2）说明2n+ n3是O(2n)；（3）给出5(n2 + 6) / (n + 3) + 7lg n的O值估计。

习题1.1选择题1、数据结构是一门研究计算机解决实际问题中（ A ）以及它们之间的（ B ）和运算等的学科。

(1)A、数据元素 B、计算方法 C、逻辑存储 D、数据映像(2)A、结构 B、关系 C、运算 D、算法2、数据结构可以用二元组来表示，它包括（ A ）集合K和K上的（ C ）集合R。

A、数据元素B、存储结构C、元素之间的关系D、逻辑结构3、数据结构在计算机内存中的表示是指（ A ）。

A、数据的存储结构B、数据结构C、数据的逻辑结构D、数据元素之间的关系4、在数据结构中，与所使用的计算机无关的是数据的（ A ）结构。

A、逻辑B、存储C、逻辑和存储D、物理5、以下说法中正确的是（ D ）。

A、数据元素是数据的最小单位B、数据项是数据的基本单位C、数据结构是带结构的各数据项的集合D、一些表面上很不相同的数据可以有相同的逻辑结构1.2 填空题1、线性结构中元素之间存在（一对一）关系，树型结构中元素之间存在（一对多）关系，图型结构中元素之间存在（多对多）关系。

2、数据结构是研究数据的（逻辑结构）和（存储结构）以及它们之间的相互关系，并对这种结构定义相应的操作，设计出相应的（算法），而确保经过这些运算后所得到的新结构是原来的结构类型。

3、一个算法的时间复杂度是该算法包含的（简单操作次数）的多少，它是一个算法运行时间的（相对量度），一个算法的空间复杂度是指该算法在运行过程中临时占用的（存储空间）的大小。

4、一个算法的时间复杂度通常用问题规模的（最高数量级）形式表示，当一个算法的时间复杂度与问题的n大小无关时，则表示为（O（1））；成正比时，表示为（O（n）），成平方时，则表示为（O（n2））。

5、数据结构、数据元素和数据项在计算机中的映射（或表示）分别称为存储结构、结点和数据域。

这句话是（正确）。

（填写正确或错误）1.3 应用题1、给定的两个数据结构如图1-1所示，回答以下问题：(a)图1-1 用图形表示法表示的两种数据结构(1) 用二元组表示法给出该数据结构的逻辑结构？(2)判断属于哪一种逻辑结构？ 解：(a) D1=（K ，R ），其中： K={1,2,3,4,5,6} R={r}r={<1,2>,<2,3>,<3,4>,<4,5>,<5,6>} 线性结构 （b ）D2=（K ，R ），其中： K={a,b,c,d,e,f,g,h,i} R={r}r={<a,b>,<a,c>,<c,d>,<c,e>,<d,f>,<d,g>,<e,g>,<e,h>,<g,i>}图型结构 2、对下列几种用二元组表示的数据结构，画出对应的逻辑结构图形表示，并指出属于哪一种结构。

第一章概论一、填空题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个特性。

1. 填空（1）（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

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

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

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

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

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

【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性（6）在一般情况下，一个算法的时间复杂度是（）的函数。

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

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

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

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

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

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

A 树B 图C 线性表D 集合【解答】B【分析】将丈夫、妻子和子女分别作为数据元素，根据题意画出逻辑结构图。

⑶算法指的是（）。

数据结构第一章考试题库(含答案)数据结构第一章考试题库(含答案)一、选择题1. 以下哪种数据结构是先进先出（FIFO）的？A. 栈B. 队列C. 链表D. 哈希表答案：B2. 在队列中，元素的插入操作称为什么？A. EnqueueB. DequeueC. PushD. Pop答案：A3. 哪种数据结构是一种不允许重复元素的集合？A. 栈B. 队列C. 链表D. 集合答案：D4. 以下哪种数据结构是后进先出（LIFO）的？A. 栈B. 队列C. 链表D. 哈希表答案：A5. 使用链表实现的栈或队列的时间复杂度是多少？A. O(1)B. O(n)C. O(log n)D. O(n^2)答案：A二、填空题1. 广度优先搜索（BFS）使用的数据结构是______。

答案：队列2. 深度优先搜索（DFS）使用的数据结构是______。

答案：栈3. 在二叉树中，每个节点最多有几个子节点？答案：24. 快速排序使用的分治策略是将数组分成几个子数组进行排序？答案：25. 哈希表的平均查找时间复杂度是多少？答案：O(1)三、简答题1. 请简要解释栈和队列的区别。

答案：栈是一种后进先出（LIFO）的数据结构，只能在栈顶进行插入和删除操作；队列是一种先进先出（FIFO）的数据结构，只能在队尾插入，在队头删除。

2. 请解释什么是链表。

答案：链表是一种动态数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

与数组不同，链表的节点在内存中可以不连续存储，通过指针来链接每个节点。

3. 请简述快速排序的思想和算法步骤。

答案：快速排序使用分治的思想，首先选择一个元素作为基准值，然后将数组划分为两个子数组，小于基准值的元素放在左侧，大于基准值的元素放在右侧。

然后对左右子数组递归地进行快速排序，直到排序完成。

4. 请解释什么是哈希表及其应用场景。

答案：哈希表是一种基于哈希函数进行查找的数据结构，通过将关键字映射到哈希表中的位置来实现高效的查找。

01绪论【单选题】1. （A）是数据的基本单位。

Ａ、数据元素Ｂ、数据对象Ｃ、数据项Ｄ、数据结构2. （C）是数据的不可分割的最小单位。

Ａ、数据元素Ｂ、数据对象Ｃ、数据项Ｄ、数据结构3. 若采用非顺序映象，则数据元素在内存中占用的存储空间（C）。

Ａ、一定连续Ｂ、一定不连续Ｃ、可连续可不连续4. 若采用顺序映象，则数据元素在内存中占用的存储空间（A）。

Ａ、一定连续Ｂ、一定不连续Ｃ、可连续可不连续5. 在数据结构中，从逻辑上可以把数据结构分为（C）Ａ、动态结构和静态结构Ｂ、紧凑结构和非紧凑结构Ｃ、线性结构和非线性结构Ｄ、内部结构和外部结构6. 在树形结构中，数据元素间存在（B）的关系。

Ａ、一对一Ｂ、一对多Ｃ、多对多Ｄ、除同属一个集合外别无关系7. 下列说法中错误的是（B）。

Ａ、数据对象是数据的子集Ｂ、数据元素间关系在计算机中的映象即为数据的存储结构Ｃ、非顺序映象的特点是借助指示元素存储地址的指针来表示数据元素间逻辑关系Ｄ、抽象数据类型指一个数学模型及定义在该模型上的一组操作8. 计算机算法指的是（C）。

Ａ、计算方法Ｂ、排序方法Ｃ、解决问题的有限运算序列Ｄ、调度方法9. 下列不属算法特性的是（D）。

Ａ、有穷性Ｂ、确定性Ｃ、零或多个输入Ｄ、健壮性10.算法分析的目的是（C）。

Ａ、找出数据结构的合理性Ｂ、研究算法中的输入和输出的关系Ｃ、分析算法的效率以求改进Ｄ、分析算法的易读性和文档性11.算法分析的两个主要方面是（A）。

Ａ、空间复杂性和时间复杂性Ｂ、正确性和简明性Ｃ、可读性和文档性Ｄ、数据复杂性和程序复杂性12.算法的计算量的大小称为算法的（A）。

Ａ、效率Ｂ、复杂性Ｃ、现实性Ｄ、难度13.在下面的程序段中，对x的赋值语句的频度为（C）。

for(i=1;i<=n;++i)for(j=1;j<=n;++j)x=x+1;Ａ、2nＢ、nＣ、n2Ｄ、log2n14.设n为正整数，则如下程序段中最后一行的语句频度在最坏情况下是（D）。

第一章习题：(1) 简述数据与数据元素的关系与区别。

(2) 说出数据结构中的四类基本逻辑结构，并说明哪种关系最简单、哪种关系最复杂。

(3) 画出线性结构的示意图。

(4) 画出树形结构的示意图。

(5) 画出图状结构的示意图。

(6) 什么是逻辑结构、存储结构？有哪几种存储结构？(7) 简述顺序存储结构与链式存储结构在表示数据元素之间关系上的主要区别。

(8) 简述逻辑结构与存储结构的关系。

(9) 通常从哪几个方面评价算法的质量？(10) 算法的时间复杂度主要有哪几种？按从优到劣的顺序写出各种表示形式。

(11) 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。

(12) 下列算法的时间复杂度是( ) 。

for （i=0 ；i<n ；i++ ）for （j=0 ；j<n ；j++ ）c[i][j]=i+jA. O(1)B. O(n)C. O(log2n)D. O(n2)(13) 下列算法的时间复杂度是( ) 。

for （i=0 ；i<n ；i++ ）c[i][i]=i+iA. O(1)B. O(n)C. O(log2n)D. O(n2)第二章习题：(1) 若某线性表采用顺序存储结构，每个元素占四个存储单元，首地址为100，则下标为11的(第12个)元素的存储地址为（）。

(2) 下列说法正确的是( ) 。

A. 线性表的逻辑顺序与存储顺序总是一致的B. 线性报第链式存储结构中，内存中可用的存储单元可以使连续的，也可以不连续C. 线性表弟顺序存储结构优于链式存储结构D. 每种数据结构都具有插入、删除和查找三种基本运算(3) L是线性表，已知ListLength(L) 的值是5，运算DeleteList（L，2）后ListLength（L）的值是( ) 。

A. 5B. 0C. 4D. 6(4) 线性表中哪些元素只有一个直接前驱和一个直接后继( ) 。

A. 首元素B. 尾元素C. 中间元素D. 所有的元素(5) 线性表（L ）经运算InitList （L ）后，函数IEmpty （L ）的值是( ) 。

《数据结构》课程第一章小测验一、判断题：（每题2分，共4分）1、数据元素是数据的最小单位。

F2、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。

F链表的存储中结点之间可以是连续的，也可以是不连续的。

但结点内部是连续的。

答题区二、选择题：（每题2分，共16分）1、线性表是具有n个（）的有限序列。

C（A）表元素（B）字符（C）数据元素（D）数据项2、如果数据结构中每个结点都有一个前驱，则该结构属于（）。

A（A）图状结构（B）树形结构（C）循环结构（D）线性结构3、如果数据结构中每个结点都没有后继，则该结构属于（）。

D（A）独立结构（B）散列结构（C）树形结构（D）非线性结构4、算法的时间复杂度与（）有关。

A（A）问题规模（B）计算机硬件性能（C）编译程序质量（D）程序设计语言5、算法的执行时间一般与（）无关。

D（A）问题规模的大小（B）计算机的档次（C）程序设计语言的种类或版本（D）算法设计者的水平6、算法分析的主要任务是分析（）。

D（A）算法是否具有较好的可读性（B）算法中是否存在语法错误（C）算法的功能是否符合设计要求（D）算法的执行时间和问题规模之间的关系7、某算法的时间复杂度为O（2n），表明该算法的（）。

C（A）问题规模是2n（B）执行时间等于2n（C）执行时间与2n成正比（D）问题规模与2n成正比8、在决定选取何种存储结构时，一般不考虑（）。

A（A）各结点的值如何（B）结点数目的多少（C）对数据有哪些运算（D）所用编程语言实现这种结构是否方便三、填空题：（每空2分，共14分）1、数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。

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

3、线性表是具有n个数据元素有限序列。

四、简答题：（每题10分，共20分）1.数据结构和数据类型两个概念之间有区别吗？答：简单地说，数据结构定义了一组按某些关系结合在一起的数据元素。