2025年数据结构与算法真题库含详细解答与考点分析

数据构造习题集含答案

目录

目录......................................................错误!未定义书签。

选择题错误!未定义书签。

第一章结论....错误!未定义书签。

第二章线性表..错误!未定义书签。

第三章栈和队列错误!未定义书签。

第四章串..........错误!未定义书签。

第五章数组和广义表错误!未定义书签。

第六章树和二叉树..错误!未定义书签。

第七章图..........错误!未定义书签。

第八章查找........错误!未定义书签。

第九章排序错误!未定义书签。

简答题错误!未定义书签。

第一章结论错误!未定义书签。

第二章线性表.....错误!未定义书签。

第三幸栈和队列....错误!未定义书签。

第四章串..........错误!未定义书签。

第五章数组和广义表错误!未定义书签。

第六章同和二叉树错误!未定义书签。

第七堂图.......错误!未定义书答.

第八章查找.....错误!未定义书签。

第九章排序.....错误!未定义书签。

编程题错误!未定义书签。

第一章绪论.........错误!未定义书签。

第二章线性表......错误!未定义书签。

第三章栈和队列....错误!未定义书签。

第四章串..........错误!未定义书签。

第五章数组和广义表错误!未定义书签。

第六章树和二叉树..错误!未定义书签。

第七章图..........错误!未定义书签。

第八章查找........错误!未定义书签。

第九章排序........错误!未定义书签。

选择题

第一章绪论

1.数据构造这门学科是针对什么问题而产生的？（A）

A、针对非数值计算的程序设计问题B、针对数值计算的程序设计问题

C＞数值计算与非数值计算的问题都针对D、两者都不针对

2.数据构造这门学科的研究内容下面选项最精确的是（D）

A、研究数据对象和数据之间的关系B、研究数据对象

C'研究数据对象和数据的操作D、研究数据对象、数据之间的关系和操作

3.某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据构造考了90

分，那么下面有关数据对象、数据元素、数据项描述对的的是（C）

A、某班级的学生成绩表是数据元素，90分是数据项

B'某班级的学生成绩表是数据对象，90分是数据元素

C'某班级的学生成绩表是数据对象，90分是数据项

D、某班级的学生成绩表是数据元素，90分是数据元素

4.米数据构造是指（A）＜＞

A、数据元素的组织形式B、数据类型

C、数据存储构造D、数据定义

5.数据在计算机存储器内表达时，物理地址与逻辑地址不相似，称之为（C）。

A、存储构造B、逻辑构造

C、链式存储构造D、次序存储构造

6.算法分析的目的是（C）

A、找出数据的合理性B、研究算法中的输入和输出关系

C'分析算法效率以求改善D、分析算法的易慢性和文档型性

7.算法分析的重要措施（A）。

A'空间复杂度和时间复杂度B、对的性和简要性

C'可读性和文档性D、数据复杂性和程序复杂性

8.计算机内部欠理的基本单元是（B）

A、数据B、数据元素C、数据项D、数据库

9.数据在计算机内有链式和次序两种存储方式，在存储空间使用的灵活性上，

链式存储比次序存储要（B）。

A、低B、高C、相似D、不好说

10.算法的时间复杂度取决于（C）

A、问题的规模B、待欠理数据的初始状态

C、问题的规模和待外理数据的初始状态D、不好说

11.数据构造既研究数据的逻辑构造，又研究物理构造，这种观点（B）。

A、对的B、错误

C、前半句对，后半句错D、前半句错，后半句对

12.在数据构造中，从逻辑上可以把数据构造提成（C）

A、动态构造和衿态构造B、紧凑构造和非紧凑构造

C、线性构造和非线怛构造D、内部构造和外部构造

13.线性表的次序存储构造是一种（）的存储构造，线性表的链式存储构造是一

种（A）存储构造。

A、随机存取B、次序存取

C'索引存取D、散列存取

14.米下列程序的时间复杂度是(A)

for(i=l;i<=n;++i){

for(j=l;j<=n;4+j){

c[i][j]=0;

}

}

A'0(n2)B'0(n)C、0(2n)D'0(2n2)

15.米下列程序的空间复杂度是(A)

for(i=l;i<=n;++i){

for(j=l;j<=m;4+j){

c[i][j]=0;

)

}

A'0(m*n)B、0(m+ii)C、O(ui-n)I)'0(ui/n)

16.*求下列程序段的时间复杂度(B)

for(i=l;i<=n;i++)

for(j=l;j<=n;j++)

x=x+l;

A'0(n2)B'0(n)C'O(l)D、0(0)

第二章线性表

1.有关线性表的说法不对的的是？(D)

A、存在唯一的一种被称为“第一种”的数据元素(开始结点)

B、存在唯一的一种被称为“最终一种”的数据元索(终端结点)

C、除第一种之外，集合中的每个数据元素均只有一种前驱

D、除第一种之外，集合中的每个数据元素均只有一种后继

2.有关次序表的说法不对的的是？(D)

A、逻辑关系上相邻的两个元素在物理存储位置上也相邻

B、可以随机存取表中任一元素，以便快捷

C、在线性表中插入某一元素时，往往需要移动大量元素

D、在线性表中删除某一元索时，无需移动大量元素

3.当线性表的元素总数基本稳定，且很少进行插入和删除操作，但规定以最快

的速度存取线性表中的元素时，应采用型L存储构造？（A）

A、次序表B、单链表0循环链表口、双链表

4.在一种长度为n的次序表中第i个元素（l<=i<=n）之前插入一种元素时5

需向后移动多少个元素。（C）

A'n-1B'n-iC'n-i+1D'n-i-1

5.在单链表中设置头结点的作用是（）。

A、单链表定义而已B、指定表的起始位置

C、为双向链表做准备D、为循环链表做准备

6.根据线性表链式存储构造中每一种结点包括的指针数，将线性链表提成（C）

A、单链表与循环犍表B、单链表与十字链表

C、单链表与双链表D、循环链表与多链表

7.链接存储的特点是运用型来表达数据元素之间的逻辑关系（A）

A、引用B、串联C、挂接D、指派

8.已知指针p指向单链表L中的某结点，则删除其后继结点的语句是（D）

A、p=p.nextB、p=nul1C、p.next=nullD、p.next=p.next,next

9.*在单链表L中，指针p所指结点有后继结点的条件是（B）

A、p=p.nextB、p.next!=nul1

C、p.next=nul1D、p.next=p.next,next

10.*在单链表p结点之后插入s结点的操作是（C）

A'p.next=s;s.next=p.next;B、s.next=p.next;p.next=p.next,next;

C's.next=p.next;p.next=s;D's.next=p;p.next=s;

第三章栈和队列

1.栈、队列一般采用两种存储构造，它们是(B)

A、散列方式和索引方式B、次序存储构造和链式存储构造

C、链表存储构造和数组D、线性和非线性存储沟造

2.一种栈入栈序列是a,b,c,d,则栈输出序列不也许是(C)

A'd,c,b,aB'c,d.b,aC*d,c,a,bD、a,b,c,d

3.判断次序栈(最多结点数为m)为栈满的条件是(D)

A、top==0B'top!=mC、top!=0D、top==m

4.栈存取数据原则(或栈特点)是(B)

A、后进后出B、后进先出C、先迸先出D、脸意进出

5.米通过如下栈运算后，x的值是(A)

InitStack(s);

Push(s,d);

Push(s,e);

Pop(s,x);

Pop(s,x);

GetTopCs,x);

A'dB'eC'xD、s

6.一力中队＞］的进队序歹“为：a，b，c，d，贝”出队序＞J是：(A)

A'a»b♦c»dB'd1c♦b,a

C'a»d»c*bD*c»b»d»a

7.循环队列为空队列的条件是：(D)

A、Q.front=0B'Q.(rear+1)%MaxSize==Q.front

C'Q.rear=0D、Q.rear==Q.front

8.在存储构造上，假如用带头节点单链表实现队列（假定front和rear分别

为队首和队尾指针），则删除一种结点的操作为（A）。

A、front.next=front.next,nextB、rear=rear.next

C、rear=front,nextD、front=front,next

9.栈和队列共同点是（C）

A'先进后出B、先进先出

C'容许在端点处进行操作线性表D、无共同点

10.插入和删除只能在一端进行的线性表是（B）

A、循环队列B、栈

C、队列D、循环栈

11.插入和删除分别在两端端进行的线性表是（C）

A、循环队列B、栈

C、队列D、循环栈

12.循环队列为满队列的条件是：（B）

A'Q.front=0B、Q.（rear+l）^MaxSize==Q.front

C、Q.rear=0D、Q.rear==Q.front

第四章串

1.有关串的论述，错误的是：（B）

A­串是字符有限序列B­空串是由空格构成的串

C♦模式匹配是串的重要运算D­串有用次序、链式两种存储方式

2.串长度是指（B）

A•串所含不一样字母数目B­事所含字符数m

C­串所含不一样字符数目D・串所含非空格字符数目

3.*若串S="database”，其子串数目是（B）°

A-16B-37C-8D-36

4.设串S1是串S子串，则求S1在S中定位运算称为（B）

A•求子串B•串匹配C•联接D•求串长

5.设有串si二"welcometozdsoftcolleage!"和s2="so"，那么s2在si

中的索引位置是（C）

A-12B-14C•13D-10

6.*若串S=usoftware"，其子串的数目是（B）°

A-8B•37C•36D-9

第五章数组和广义表

第六章树和二叉树

1.假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子

结点数为（B）人。

A.15B.16C.17D.47

2,假定一棵三叉树的结点数为50，则它的最小高度为（C）<>

A.3B.4C.5D.6

3.在一棵二叉树上第4层的结点数最多为（D）。

A.2B.4C.6D.8

4,用次序存储的措施将完全二叉树中的所有结点逐层寄存在数组中R[l..n]，

结点R[i]若有左孩子，其左孩子的编号为结怠（B）<>

A.R[2i+1]B.R[2i]C.R[i/2]I）.R[2i-1]

5.设n,m为一棵二叉树上的两个结点，在中序遍历序列中n在ni前的条件是

（B）。

A.n在in右方B.n在m左方

C.n是m的祖先D.n是m的子孙

6.下面论述对的的是（D）。

A.二又树是特殊的树

B.二叉树等价于度为2的树

C.完全二叉树必为满二叉树

D.二叉树的左右子树有次序之分

7,既有一深度为5的二叉树，请问其最多有（D）个结点。

A.32B.5C.30D.31

8.既有一深度为4的二叉树，请问其最多有（A）个结点。

A.15B.16C.17D.6

9.在一棵二叉排序树上按（B）遍历得到的结点序列是一种有序序列。

A.先序B.中序C.后序D.头序

10.在一棵二叉树中，度为0的结点数为m，度为2的结点数为ih，则no=（C）

A.n+1B.n+2C.n+1D.2n+l

11.由三个结点构成的二叉树，共有（B）种不一样的形态。

A.4B.5C.6D.7

12.一棵具有n个结点的树，（A）形态到达最大深度。

A.单支树B.二叉树C.三叉树D.n叉树

13.不含任何结点的空树（C）。

A.是一棵树;B.是一棵二叉树;

C.是一棵树也是一棵二叉树;D.既不是树也不是二叉树

14.二叉树是非线性数据构造，因此（C)°

A.它不能用次序存储构造存储；B.它不能用链式存储构造存储；

C.次序存储构造和链式存储构造都能存储；

D.次序存储构造和链式存储构造都不能使用

15.具有n（n>0）个结点的完全二叉树的深度为（C）。

A.Iog2（n）B.Iog2（n）C.[log2（n）]+1D.Iog2（n）+1

16.在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的

结点数为2个，则度为0的结点数为（D）人。

A.4B.5C.6D.7

17.有关二叉树下列说法对的的是（B）

A•二叉树的度为2B•一棵二叉树的度可以不不小于

2

C•二叉树中至少有一种结点的度为2D•二叉树中任何一种结点的度都为2

18.在完全二叉树中，若一种结点是叶结点，则它没（C）。

A•左子结点B•右子结点

C•左子结点和右子绐点D­左子结点，右子结点和兄弟结点

19.在下列状况中，可称为二叉树的是（B）

A•每个结点至多有两棵子树的树B.哈夫曼树

C♦每个结点至多有两棵子树的有序树D.每个结点只有一棵右子树

第七章图

1.图的深度优先遍历类似于二叉树的（A）。

\,先序遍历B,中序遍历C•后序遍历D•层次遍历

2.已知一种图如图所示，若从顶点a出发按深度优先遍历，则也许得到的一种

顶点序列为（C）

A-abecdfB-acfebdC•aebcfdD-aedfcb

3.若从无向图的任意一种顶点出发进行一次深度优先搜索可以访问图中所有

的顶点，则该图一定是（B）图。

A•非连通B•连通C♦强连通D•有向

4.在一种图中，所有顶点的度数之和等于所有边数的（C）倍。

A1/2B1C2D3

5.在一种有向图中，所有顶点的入度之和等于所有顶点出度之和的（B）

倍。

A1/2B1C2D3

6.一种有N个顶点的有向图最多有（B）条边。

ANBN(N-l)CN(n-l)/2D2N

7.具有4个顶点的无向完全图有）条边。

A6B12C18I)20

8.具有6个顶点的无向图至少有（）条边才能保证是一种连通图。

A5B6C7D8

9.对于一种具有N个顶点的无向图，若采用邻接矩阵表达，则该矩阵大小是

（D）

ANB(N-l)2CN-lDN*N

10.一种具有N个顶点的无向图中，要连通所有顶点至少要（C）条边

ANBN+lCN-1DN/2

11.*已知图的邻接矩阵如图所示，则从顶点0出发按深度优先遍历的成果是

01I1I0I

(C)001001

000100

100110

011010

0011O1

100010

A-0243156B-0I36542C-0134256D-0361542

12.已知图的邻接表下图所示，则从顶点0出发按广度优先遍历的成果是（），

按深度优先遍历的成果是（D）。

A-0132B-0231C-0321D-0123

13.已知图的邻接表下图所示，则从顶点0出发按广度优先遍历的成果是（），

按深度优先遍历的成果是（）。

14.当在一种有序的次序表上查找一种数据时，既可用折半查找，也可用次序查

找，但前者比后者的查找速度（C）°

A•必然快B•不一定

C­在大部分状况下要快D•取决于表递增还是递减

15.折半查找有序表（4，6，10，12，20，30，5D，70，88，100）。若查找表中

元素58，则它将依次与表中（A）比较大小，查找成果是失败。

A•20，70，30，50B•30，88，70，50

C•20，50D•30，88，50

第八章查找

1.次序查找法适合于存储构造为（B）的线性表。

A•散列存储B•次序存储或链式存储

C•压缩存储D•索引存储

2.在查找过程中，若同步还要增、删工作，这种查找称为（B）。

A、铮态查找B'动态查找C'内查找D'外查找

3.索引次序表的特点是次序表中的数据（A）。

A'有序B'无序C'块间有序D、散列

4,采用次序查找措施查找长度为n的线性表时每个元素的平均查找长度为（C）

A'nB'n/2C、（n+l）/2D、（nT）/2

5.*将10个元素散列到1000000个单元的哈希表，则（C）产生冲突。

A'一定会B、一定不会C、仍也许会D、以上都不对

6.米散列表的地址区间为0~16，散列函数H（k）=k%17，采用线性探测法处理地

址冲突，将关键字26、25、72、38、1、18、59依次存储到散列表中。元素

59寄存在散列表中的地址为（A）

A'8B、9C'10D'11

7.设有序表的关键字序列为｛1,3,9,12,32,41,45,62,75,77,82,95,100），当采

用二分查找法查找值为82的节点时，经（C）次比较后查找成功。

A'1B、2C、3D'4

8.设有100个元素，用折半查找法进行查找时,最大、最小比较次数分别时

（A）

A'7,1B'6,1C'5,1D'8,1

第九章排序

1.对n个不一样的记录按排序码值从小到大次序重新排列，用冒泡（起泡）排序

措施，初始序列在（A）状况下，与排序码值总比较次数至少。

A•按排序码值从小到大排列B•按排序码值从大到小排列

C­随机排列（完全无序）D•基本按排序码值升序排列

2.对n个不一样的记录按排序码值从小到大次序重新排列，用冒泡（起泡）排序

措施，在（B）状况下，与排序码值总比较次数最多。

A-按排序码值从小到大排列B•按排序码值从大到小排列

C•随机排列（完全无序）D­基本按排序码值升序排列

3.对n个不一样的记录按排序码值从小到大次序重新排列，用直接插入排序措

施，初始序列在（A）状况下，与排序码值总比较次数至少。

A-按排序码值从小到大排列B•按排序码值从大到小排列

C­随机排列（完全无序）D­基本按排序码值升序排列

4.对n个不一样的记录按排序码值从小到大次序重新排列，用直接插入排序措

施，初始序列在（B）状况下，与排序码值总比较次数最多。

A•按排序码值从小到大排列B•按排序码值从大到小排列

C•随机排列（完全无序）D♦基本按排序码值升序排列

5.对n个不一样的记录按排序码值从小到大次月重新排列，用迅速排序措施在

（C）状况下，与排序码值总比较次数至少。

A-按排序码值从小到大排列B•按排序码值从大到小排列

C•随机排列（完全无序）D­基本按排序码值升序排列

6.对n个不一样的记录按排序码值从小到大次序重新排列，用迅速排序措施，

在（A）状况下与排序码值总比较次数最多。

A-按排序码值从小到大排列B-按排序码值从大到小排列

C­随机排列（完全无序）D♦基本按排序码值升序排列

7.用冒泡排序措施对n个记录按排序码值从小到大排序时，当时始序列是按排

序码值从大到小排列时，与码值总比较次数是（D）。

A,n-1B•nC,n+1D•n（n-l）/2

8.下列排序措施中，与排序码值总比较次数与待排序记录的初始序列排列状态

无关的是（D）。

A•直接插入排序B•冒泡排序C-迅速排序D•直接选择排序

9.将6个不一样的整数进行排序，至少需要比较（A）次。

A-5B-6C•15D•21

10.将6个不一样的整数进行排序，至多需要比较（C）次。

A-5B-6C•15D-21

11.米若需要时间复杂度在0（nlog2n）内，对整数数组进行排序，且规定排序措施

是稳定的，则可选择的排序措施是（B）。

A•迅速排序B•归并排序C•堆排序D•直接插入排序

12.当待排序的整数是有序序列时，采用（B）措施比很好，其时间复杂度为

O（n）。

A•迅速排序B•胃泡排序C•归并排序D•直接选择排序

13.当待排序的整数是有序序列时，采用（A）措施比较差，到达最坏状况下

时间复杂度为0（市）。

A•迅速排序B•冒泡排序C•归并排序D•直接选择排序

14.当待排序的整数是有序序列时，无论待排序序列排列与否有序，采用（D）

措施的时间复杂度都是0（/）。

A•迅速排序B•冒泡排序C•归并排序D♦直接选择排序

15.米堆是一种（B）排序。

A•插入B•选择C•互换D•归并

16.米若一组记录的排序码值序列为｛40，80，50，30，60，70｝，运用堆排序措

施进行排序，初建的大顶堆是（D）。

A•80，40，50，30，60，70B•80，70，60，50，40，30

C•80，70，50，40，30，60D•80，60，70，30，40，50

17.若一组记录的排序码值序列为｛50，80，30，40，70，60｝运用迅速排序措施，

以第一种记录为基准，得到一趟迅速排序的成果为（B）。

A•30，40，50，60，70，80B•40，30，50，80，70，60

C•50，30•40，70，60，80D•40，50，30•70，60，80

18.米下列几种排序措施中规定辅助空间最大的是（C）。

A•堆排序B•直接选择排序C•归并排序D•迅速排序

19.已知A[m]中每个数组元素距其最终位置不远，采用下列（A）排序措施最

节省时间。

A•直接插入B•堆C•迅速D•直接选择

20.如殳有10000个互不相等的无序整数，若仅规定找出其中前10个最大整数，

最佳采用（B）排序措施。

A•归并B•堆C•迅速D•直接选择

21.*在下列排序措施中不需要对排序码值进行比较就能进行排序的是（A）

A：基数排序B•迅速排序C­直接插入排序D•堆排序

22.米给定排序码值序列为{F，B，J，C，E，A，I，D，C，H}，对其按字母的字

典序列的次序进行排列，希尔（Shell）排序的第一趟（dl=5）成果应为（D）。

A・{B，F，C，J，A，E，D，I，C，H}

B•{C，B，D，A，E，F，I，C，J，H}

C・{B，F，C，E，A，I，D，C，H，J}

D•{A，B，D，C，E，F，I，J，C，H}

23.给定排序码值序列为{F，B，J，C，E，A，I，D，C，H}，对其按字母的字典

序列的次序进行排列，冒泡排序（大数下沉）的第一趟排序成果应为（C）。

A•{B，F，C，J，A，E，D，I，C，H}

B•{C，B，D，A，E，F，I，C，J，H}

C•{B，F，C，E，A，I，D，C，H，J}

D•{A，B，D，C，E，F，I，J，C，H}

24.给定排序码值序列为{F，B，J，C，E，A，I，D，C，H}，对其按字母的字典

序列的次序进行排列，迅速排序的第一趟排序成果为（B）。

A•{B，F，C，J，A，E，D，I，C，H}

B•{C，B，D，A，E，F，I，C，J，H}

C•{B，F，C，E，A，I，D，C，II，J）

D•{A，B，D，C，E，F，I，J，C，H}

25.*给定排序码值序列为{F，B，J，C，E，A，I，D，C，H}，对其按字母的字

典序列的次序进行排列，二路归并排序的第一趟排序成果是（A）。

A•{B，F，C，J，A，E，D，I，C，H}

B•{C，B，D，A，E，F，I，C，J，H}

C・{B，F，C，E，A，I，D，C，H，J}

D•{A，B，D，C，E，F，I，J，C，H}

简答题

第一章绪论

1.请分别给出数据、数据对象、数据元素、数据项的含义，并阐明四者的关系。

数据（Data）:是对信息的一种符号表达。在计算机科学中是指所有能输入到计算机

中并能被计算机程序处理的符号的总称。（一种得分点）

数据元素（DataElement）:是数据的基本单位，在计算机程序中一般作为一种整体

进行考虑和处理，相称于表中的一条记录。（一种得分点）

数据项：相称于记录的“域”，是数据的不可分割的最小单位，如学号（一种得分

点）

数据对象：性质相似的数据元素的集合，是数据的一种子集.例如：同一种班的所

有学生记录集合。（一种得分点）

关系：包括关系：数据泛指所有。数据对象是数据的一种子集，由数据元素构成，

数据元素是由数据项构成。（一种得分点）

评分原则，总共5个得分点，每段话一种得分。

2.请给出数据的逻辑构造的含义，并举例阐明数据的逻辑构造一般有哪些。

数据的逻辑构造：指数据元素之间的逻辑关系。即用自然语言描述数据，它与数据的存

储无关，是独立于计算机的，逻辑构造有四种。（一种得分点）

集合构造：仅同属一种集合（构造名字0.5个得分点、举例0.5得分点）

线性构造：一对一（1:1）（构造名字0.5个得分点、举例0.5得分点）

树结构：一对多（l:n）（构造名字0.5个得分点、举例0.5得分点）

图结构：多对多（m:n）（构造名字0.5个得分点、举例0.5得分点）

评分原则：每段话一种得分点，总共5个得分点。

什么是数据的物理构造？有哪些物理构造？数据的物理构造与逻辑构造有什么区别与

联络？

数据的物理构造：物理构造亦称存储构造，是数据的逻辑构造在计算机存储器内的表达

（或映像）。它依赖于计算机。（一种得分点）

存储构造可分为4大类：次序、链式、索引、散列。（共2个得分点，一种0.5得分点）

区别：数据的逻辑构造属于顾客视图，是面向问题的，数据的存储构造属于详细实现的

视图，是面向计算机的。（一种得分点）

联络：一种数据的逻辑构造可以用多种存储构造来存储，而采用不一样的存储构造其处

理的效率往往不一样。（一种得分点）

评分原则：共5个得分点，按照每段话各自标注的得分点进行评分。

3.求两个正整数m，n中的最大数MAX的算法

（1）若m>n则nax=m

（2）若m<=n则max=n

请根据上述算法解释一下算法的构成要素有哪些，分别是什么。

算法由操作、控制构造、数据构造3要素构成

操作包括：算术运算、关系比较、逻辑运算、数据传送（输入、输出、赋值）（一种得

分点）

例子中有关系比较和献值计算的操作。（一种得分点）

控制构造包括：次序构造、选择构造、循环构造（一种得分点）

例子中有选择构造（一种得分点）

数据构造：算法操作的对象是数据，数据间的逻辑关系、数据的存储方式及处理方式就

是数据构造。（一种得分点）

本例是数值问题，波及到两个正整数，因此使用基本的整数类型就可以欠理问题>（-

种得分点）

评分原则：本题共6个得分点，每段话一种得分点。

4.简述算法的基本性质

1）揄入：0个或多种输入

2）揄出：1个或多种输出

3）有穷性：算法必须在有限步内结束

4）确定性：构成算法的操作必须清晰无二义性

5）可行性：构成算法的操作必须可以在计算机上实现

评分原则，本题共5个得分点，每个要点一分。

5.简述算法的设计规定

1、对的性（correctness）

2、可读性（readabi1ity）

3、强健性（robustness）

4、通用性（generality）

5、效率与存储的规定（物行算法所花费的存储空间、执行算法所花费的时间）

评分原则，本题共5个得分点，每个要点一分。

6.评价算法好坏的3条重要原则

1）算法实现所花费的时间。

2）算法实现所花费的存储空间，其中重要考虑辅助存储空间。

3）算法应易于理解、易于编码、易于调试等。

评分原则，本题共3个得分点，每个要点一分。

7,请简述数据构造所研究的三种基本构造，以及数据元素间的关系。

线性构造：数据元素之间一对一的关系。（2分）

树形构造：数据元素之间一对多的关系。（1.5分）

图形构造：数据元素之间多对多的关系。（:1.5分）

8.请问算法的分析和评价的两个原则，以及各自作用。

时间复杂度：评估算法运行所需时间。（1.5+1分）

空间复杂度：评估算法运行时所需最大存储空间。（1.5+1分）

9.请说出三种逻辑数据构造，以及他们的特点。（5分）

（1）线性构造：数据元素只有一种前躯数据元素和一种后继数据元素。（2分）

（2）树构造：每个数据元素只有一种前驱数据元素，可有零个或若干个后继数据元素。

（1.5分）

（3）图构造：每个数据元素可有零个或若干个前驱数据元素，零个或若干个后继数据

元索。（1.5分）

10.评价算法的重要原则是什么？

（1）算法实现所花费的时间（2分）

（2）算法实现所花费的存储空间，其中重要考虑辅助存储空间。（2分）

（3）算法应易于理解、易于编码、易于调试。（1分）

11.请说出三种逻辑数据构造，并分别画图表达它们。