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

第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）；树形结构: 数据元素之间存在一个对多个的关系,如文件系统目录管理；图状结构: 数据元素之间存在多个对多个的关系,如教学计划课程安排顺序图。

后， rear 的值为 ， front 的值 为 ，当前队列的 长 度 为 。 14.设循环队列的容量为 40(序号从 0 到 39)， 现经过一系列的入队和出队运算后， 有: ① front=11，rear=19; ② front=19，rear=11； 问在这两种情况下，循环队列中各有元素多少个？ 15.写出下列程序段的输出结果(队列中的元素类型 QElem Type 为 char)。 void main( ){ Queue Q; Init Queue (Q); Char x=’e’; y=’c’; EnQueue (Q,’h’); EnQueue (Q,’r’); EnQueue (Q, y); DeQueue (Q,x); EnQueue (Q,x); DeQueue (Q,x); EnQueue (Q,’a’); while(!QueueEmpty(Q)){ DeQueue (Q,y); printf(y); }; printf(x); } 16.简述以下算法的功能(栈和队列的元素类型均为 int) void algo3(Queue &Q){ Stack S; int d; InitStack(S); while(!QueueEmpty(Q)){ DeQueue (Q,d); Push(S,d); }; while(!StackEmpty(S)){ Pop(S,d); EnQueue (Q,d); } }
第一章 绪论
1.数据结构是研究数据的( )以及它们之间的相互关系。 A.物理结构，逻辑结构 B.理想结构，抽象结构 C.理想结构，物理结构 D.抽象结构，逻辑结构 2.从逻辑上可以把数据结构分为( )两大类。 A.动态结构、静态结构 B.顺序结构、链式结构 C.线性结构、非线性结构 D.初等结构、构造型结构 3.以下不属于算法要素的是( ) A. 有穷性 B. 可行性 C. 可读性 D. 输入 4.算法的时间复杂度与( )有关。 A.问题规模 B.计算机硬件性能 C.编译程序质 D.程序设计语言 2 5.某算法的时间复杂度为 O(n )，表明该算法的( ) 2 A.问题规模是 n B.执行时间等于 n2 C.执行时间与 n2 成正比 D.问题规模与 n2 成正比 6.假设某算法语句总的执行次数为 T(n)=2n³ +n² ,那么该算法的时间复杂性量级为 ( ) A.O(2) B.O(n³ ) C.O(n² ) D.O(1) 7.设 n 为正整数，下面程序段中标号为①的语句频度为 。 int i = 1; k = 0; while ( i <= n-1 ){ k += 10*i; ① i++; } 8.程序段 for( i=0; i<n; i++ ) for( j=0; j<i; j++ ) k++; 中，语句 k++的执行次数为 。 9.在下面的程序段中，对 x 的赋值语句的渐进时间复杂度为 。 for(k=1;k<=n;k++) for(j=1;j<=n;j++) x=x+1; 10.下面程序段的时间复杂度为 。 void fun(int n) { int y=1; while (y <=n) y=2*y; }

数据结构习题集（自编）第一章绪论一、选择题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、数据元素是数据的______，有些情况下也称为元素、结点、顶点、记录等。

5．在线性链表存储结构下，插入操作算法
。
A. 需要判断是否表满
B. 需要判断是否表空
C. 不需要判断表满
D. 需要判断是否表空和表满
6．一个长度为 n（n>1）的单链表，已知有头和尾两个指针，则执行
表的长度有关。
操作与链
A. 删除单链表中的第一个元素 B. 删除单链表中的最后一个元素
C. 在单链表第一个元素前插入一个新元素

。
5．数据逻辑结构包括 ① 、 ②
和③
三种类型，树形结构和图形结构
合称为 ④。
6．我们把每种数据结构均视为抽象类型，它不但定义了数据的 ① 理数据的 ② 。
方式，还给出了处
7．一个算法的时间复杂度是用该算法 ①的多少来度量的，一个算法的空间复杂度是用该
算法在运行过程中所占用的②___ _的大小来度量的。
10．对于循环队列
。
A. 无法判断队列是否为空
B. 无法判断队列是否为满
C. 队列不可能满
D. 以上说法都不是
11. 设环形队列中数组的下标范围是1～n，头尾指针分别是 f 和 r，则其元素个数
为
。
A. r-f
B. r-f+1
C. (r-f+1) mod n
D. (r-f+n) mod n
12. 若用一个大小为6的数组来实现循环队列，且当前队尾指针 rear 和队头指针 front 的值
C. s->next = h; h = h->next;
D. s->next = h->next; h->next=s;
8．一个栈的入栈序列是 a，b，c，d，e，则栈的不可能的输出序列是

数据结构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. 描述以下三个概念的区别：头指针，头结点，首元结点(第一个元素结点)。

第一章 绪论练习一1、 设有数据逻辑结构为Data-Structure = (D,S)，其中D={d 1, d 2, …, d 9}，S={r}，r={< d 1,d 3>, < d 1, d 8>,< d 2, d 3>, <d 2, d 4>, <d 2, d 5>, <d 3, d 9>,<d 5, d 6>,<d 8, d 9>,<d 9, d 7>,<d 4,d 6>,<d 4, d 7>}，画出这个逻辑结构的图示，对于关系r ，那些结点是起始结点，那些结点是终端结点？2、 设n 为整数，试确定下列各程序中前置以@语句的频度(1) FOR (i=1;i<=n;i++){FOR (j=1;j<=i;j++){FOR (k=1;k<=j;k++) @ x+=delta; } }(2) X=91;y=100;WHILE (y>0){@ if (x>100) {x-=10;y--;} else x++; }3、 按增长率由小到大的顺序排列下列各函数：,log,log,,!,,,,)34(,)32(,)23(,22223100nn n n n n n n n n n nnnn n n n 2log22222,log),(loglog ,log4、设有以下三个函数：f(n)=21n 4+ n 2+1000, g(n)=15 n 4 +500n 3 h(n)=5000 n 3.5+nlogn判断下列断言正确与否： （1） f(n)是O(g(n)); （2） h(n)是O(f(n)); （3） g(n)是O(h(n)); （4） h(n)是 O(n 3.5) （5） h(n)是 O(nlogn) 5、试用数学归纳法证明：（1）∑=+--=ni n i x x x 01)1/()1( ）且（01≥≠n x （2）∑==-ni n i 12)12(）（1≥n 6、试写一算法自大到小依次输出顺序读入的三个整数X 、Y 、Z 的值。

第一章作业一、选择题1.被计算机加工的数据元素不是孤立的，它们彼此之间一般存在某种关系，通常把数据元素之间的这种关系称为( ).A。

规则B。

结构 C. 集合 D. 运算2.在Data_Structure=(D，S)中，D是（)的有限集合。

A。

数据元素 B. 算法C。

数据操作D。

数据对象3.计算机所处理的数据一般具有某种关系，这是指（）之间存在的某种关系。

A。

数据与数据B。

数据元素与数据元素C。

元素内数据项与数据项D。

数据文件内记录与记录4.顺序存储表示中数据元素之间的逻辑关系是由( ）表示的.A。

指针B。

逻辑顺序 C. 存储位置D。

问题上下文5.链接存储表示中数据元素之间的逻辑关系是由( ）表示的。

A。

指针B。

逻辑顺序C。

存储位置 D. 问题上下文6.从逻辑上可将数据结构分为（)。

A. 动态结构和静态结构B. 紧凑结构和非紧凑结构C。

内部结构和外部结构D。

线性结构和非线性结构7.以下选项属于线性结构的是( )。

A。

广义表 B. 二叉树C。

串 D. 稀疏数组8.以下选项属于非线性结构的是（).A。

广义表B。

队列 C. 优先队列D。

栈9.以下属于逻辑结构的是( )A. 顺序表B。

散列表 C. 有序表 D. 单链表10.一个完整的算法应该具有( )等特性。

A. 可执行性、可修改性和可维护性B. 可行性、确定性和有穷性C。

确定性、有穷性和可靠性D。

正确性、可读性和有效性11.若一个问题既可以用迭代方法也可以用递归方法求解，则( ）的方法具有更高的时空效率.A. 迭代B。

递归C。

先递归后迭代D。

先迭代后递归12.一个递归算法必须包括( )A。

递归部分 B. 终止条件和递归部分C。

迭代部分 D. 终止条件和迭代部分13.算法的时间复杂度与（)有关。

A. 问题规模B. 源程序长度C. 计算机硬件运行速度D. 编译后执行程序的质量二、指出下列各算法的功能并求出其时间复杂度。

(1）int Prime（int n)｛int i=2，x=(int）sqrt（n)； //sqrt（n）为求n的平方根while（i<=x)｛if(n％i==0)break;i++；}if(i〉x）return 1；else return 0；｝(2)int sum1（int n）｛int p=1,s=0；for(int i=1；i<=n;i++){p＊=i；s+=p;}return s;}(3）int sum2（int n){int s=0；for(int i=1；i〈=n;i++){int p=1;for（int j=1;i〈=i；j++） p＊=j;s+=p；}return s;｝(4)int fun(int n){int i=1,s=1;while（s<n) s+=++i;return i；}（5)void mtable(int n)｛for(int i=1；i〈=n；i++){for（int j=i；j<=n;j++)cout<〈i〈<"＊"<<j〈<"=”〈〈setw(2)<〈i*j<<" ”;cout<<endl;}｝第二章作业 一、选择题1. 在线性表中的每一个表元素都是不可再分的（ )A 。

11、 一个栈的输入序列为 123…n，若输出序列的第一个元素是 n，输出第 i（1<=i<=n）个元
素是（ B ）。
A. 不确定
B. n-i+1
C. i
D. n-i
1
12、 有六个元素 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
A. 1 和 5
B. 2 和 4
C. 4 和 2
D. 5 和 1
16、下面关于串的的叙述中，哪一个是不正确的？（ B ）
A．串是字符的有限序列
B．空串是由空格构成的串
C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储
17、设有两个串 p 和 q，其中 q 是 p 的子串，求 q 在 p 中首次出现的位置的算法称为（ c ）
A． 内存地址
B．数组下标 C．下一元素地址
D．左、右孩子地址
7、下面的叙述不正确的是（ BC ）
A．线性表在链式存储时，查找第 i 个元素的时间同 i 的值成正比
B. 线性表在链式存储时，查找第 i 个元素的时间同 i 的值无关
C. 线性表在顺序存储时，查找第 i 个元素的时间同 i 的值成正比
D. 线性表在顺序存储时，查找第 i 个元素的时间同 i 的值无关
13、 设有三个元素 X，Y，Z 顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是( C )。
A．XYZ
B. YZX
C. ZXY
D. ZYX
14、 假设以数组 A[m]存放循环队列的元素,其头尾指针分别为 front 和 rear，则当前队列中的

第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、研究数据结构就是研究（ 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、下面程序段的时间复杂度是（）。

i=s=0;while(s<n){i++;s+=i;}A. O(n)B. O(n2)C. O(log2n)D. O(n3)11、抽象数据类型的三个组成部分分别为（）。

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

数据结构练习题习题1 绪论1.1 单项选择题1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。

①A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象②A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。

①A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象②A．操作Ｂ．映象Ｃ．存储Ｄ．关系3. 在数据结构中，从逻辑上可以把数据结构分成。

A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构4. 算法分析的目的是①，算法分析的两个主要方面是②。

①A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进D. 分析算法的易懂性和文档性②A. 空间复杂性和时间复杂性 B. 正确性和简明性C. 可读性和文档性D. 数据复杂性和程序复杂性5. 计算机算法指的是①，它必具备输入、输出和②等五个特性。

① A. 计算方法 B. 排序方法C. 解决问题的有限运算序列D. 调度方法②A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性C. 确定性、有穷性和稳定性D. 易读性、稳定性和安全性1.2 填空题（将正确的答案填在相应的空中）1. 数据逻辑结构包括、、和四种类型，树形结构和图形结构合称为。

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

3. 在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。

4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。

5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。

数据结构练习题第一部分绪论一、单选题1. 一个数组元素a[i]与________的表示等价。

A、 *(a+i)B、 a+iC、 *a+iD、 &a+i2. 对于两个函数，若函数名相同，但只是____________不同则不是重载函数。

A、参数类型B、参数个数C、函数类型3. 若需要利用形参直接访问实参，则应把形参变量说明为________参数A、指针B、引用C、值4. 下面程序段的时间复杂度为____________。

for(int i=0; i<m; i++)for(int j=0; j<n; j++)a[i][j]=i*j;A、 O(m2)B、 O(n2)C、 O(m*n)D、 O(m+n)5. 执行下面程序段时，执行S语句的次数为____________。

for(int i=1; i<=n; i++)for(int j=1; j<=i; j++)S;A、 n2B、 n2/2C、 n(n+1)D、 n(n+1)/26. 下面算法的时间复杂度为____________。

int f( unsigned int n ) {if ( n==0 || n==1 ) return 1; else return n*f(n-1);}A、 O(1)B、 O(n)C、 O(n2)D、 O(n!)二、填空题1. 数据的逻辑结构被分为__________、_________、__________和__________四种。

2. 数据的存储结构被分为__________、_________、__________和__________四种。

3. 在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着________、________和________的联系。

4. 一种抽象数据类型包括__________和__________两个部分。

5. 当一个形参类型的长度较大时，应最好说明为_________，以节省参数值的传输时间和存储参数的空间。