数据结构试题及答案修改一1

数据结构试题（一）一、选择1.评价一个算法时间性能的主要标准是（D）A 算法易于调试B 算法易于理解C 算法的稳定性和正确性D 算法的时间复杂度2.可用带表头结点的链表来表示表，也可用不带表头结点的链表来表示表，前者的主要好处是（B）A 可以加快对表的遍历B 使空表和非空表的处理统一C 提高存取结点的速度D 节省存储空间3.稀疏矩阵一般的压缩存储有两种，即（D）。

A 一维数组和二维数组B 一维数组和三元组C 二维数组和十字链表D 三元组和十字链表4.若进栈序列为a,b,c,d,进栈过程中可以出栈,则（ D）不可能是一个出栈序列。

A cbadB bdcaC cdbaD adbc5.将一棵有100个结点的完全二叉树从根的这一层开始，每一层从左到右依次对结点进行编号，根结点编号为１，则编号为49的结点的左孩子的编号为（A）A 98B 99C 50D 486.任何一个无向连通图的最小生成树（B）。

A 只有一棵B 有一棵或多棵C 一定有多棵D 可能不存在7.对于如图所示的带权有向图，从顶点1到顶点5的最短路径为（D）A (1,4,5)B (1,2,3,5)C (1,4,3,5)D (1,2,4,3,5)8.下列排序方法中，要求附加的内存容量最大的是（D ）。

A 冒泡排序B 快速排序C 堆排序D 归并排序9.( C）不是哈希查找中的冲突处理方法。

A 链地址法B 再哈希法C 除留余数法D 随机探测法10.在一棵7阶的B-树中,除根结点外,每个结点中的最多有（ A )个关键字。

A 6B 5C 4D 3第1题正确答案为D第2题正确答案为B第3题正确答案为D第4题正确答案为D第5题正确答案为A第6题正确答案为B第7题正确答案为D第8题正确答案为D第9题正确答案为C第10题正确答案为D二、填空题1.在长度为n的顺序表中删除一个元素时,等概率情况下的平均移动元素的次数是n-1/22. 仅允许在表的同一端进行插入和删除运算的线性表被称为栈3.大小为M的顺序存储的循环队列sq队满的条件为(sq.rear+1)%M ==sq.fpont4.已知一棵二叉树的先根序列为ＡＢＤＦＣＥ，中根序列为ＤＦＢＡＣＥ，后序序列为FDBECA5.在无向图G的邻接矩阵表示中，第j列中非零元的个数等于该顶点的度6.克鲁斯卡尔算法适用于求边稀疏的网的最小生成树。

数据结构练习试卷1(题后含答案及解析)题型有：1. 选择题选择题（每小题1分，共75分）下列各题A、B、C、D四个选项中，只有一个选项是正确的，请将此选项涂写在答题卡相应位置上，答在试卷上不得分。

1．数据结构主要研究数据的______。

A．逻辑结构B．存储结构C．逻辑结构和存储结构D．逻辑结构和存储结构及其运算的实现正确答案：D解析：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

数据结构一般包括三方面的内容：①数据之间的逻辑关系。

从逻辑关系上描述数据，与数据的存储无关。

②数据的存储结构。

存储结构分为顺序结构和链式结构，是逻辑结构在计算机存储器中的表示，它包括数据元素的表示和关系的表示。

③数据的运算。

也就是在数据上所施加的一系列操作。

只考虑操作的功能是怎样的，暂不考虑如何实现。

综上所述，本题的正确答案为选项D。

知识模块：数据结构2．在数据结构中，结点(数据元素)及结点间的相互关系组成数据的逻辑结构。

按逻辑结构的不同，数据结构通常可分为______两类。

A．线性结构和非线性结构B．紧凑结构和稀疏结构C．动态结构和静态结构D．内部结构和外部结构正确答案：A解析：在数据结构中，结点(数据元素)及结点间的相互关系组成数据的逻辑结构。

按逻辑结构的不同，数据结构通常可分为线性结构和非线性结构两类。

本题正确答案为选项A。

知识模块：数据结构3．下面叙述不正确的是______。

A．算法的执行效率与数据的存储结构有关B．算法的空间复杂度是指执行这个算法所需要的内存空间C．算法的有穷性是指算法必须能在执行有限个步骤之后终止D．算法的时间复杂度是指执行这个算法所需要的时间正确答案：D解析：算法的时间复杂度是指执行算法所需要的计算工作量，故D选项不正确。

知识模块：数据结构4．数据的存储结构是指______。

A．数据所占的存储空间量B．数据的逻辑结构在计算机中的表示C．数据在计算机中的顺序存储方式D．存储在外存中的数据正确答案：B解析：数据的存储结构是数据元素在计算机存储器内的表示。

文档来源为:从网络收集整理.word 版本可编辑.欢迎下载支持.第1章 绪论1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。

解：数据是对客观事物的符号表示。

在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

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

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

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

存储结构是数据结构在计算机中的表示。

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。

是对一般数据类型的扩展。

1.2 填空题：1.常见的数据结构有__结构，_____结构，____结构等三种。

2.常见的存储结构有_________结构，______结构等两种。

3.数据的基本单位是____，它在计算机中是作为一个整体来处理的。

4.数据结构中的结构是指数据间的逻辑关系，常见的结构可分为两大类，______和_____。

5.《数据结构》课程讨论的主要内容是数据的逻辑结构、存储结构和________。

1.2设有数据结构(D,R)，其中{}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r =试按图论中图的画法惯例画出其逻辑结构图。

解：1.3设有以下三个函数：()10002124++=n n n f ，()3450015n n n g+=，()n n n n h log 5005.3+=请判断以下断言正确与否：(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)解：(1)对 (2)错 (3)错 (4)对 (5)错第二章序列2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。

数据结构试卷一、填空殖（每空1分共20分)1.数据的物理结构主要包括___顺序存储结构__________和_链式_____________两种情况。

2.设一棵完全二叉树中有500个结点，则该二叉树的深度为_______9___;若用二叉链表作为该完全二叉树的存储结构，则共有______501_____个空指针域.3.设输入序列为1、2、3，则经过栈的作用后可以得到_____6______种不同的输出序列。

4.设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的___出度_____,第i列上所有元素之和等于顶点i的____入度____。

5.设哈夫曼树中共有n个结点,则该哈夫曼树中有___0_____个度数为1的结点。

6.设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d,则e和d的关系为____e=d_____。

7.____中序______遍历二叉排序树中的结点可以得到一个递增的关键字序列(填先序、中序或后序）.8.设查找表中有100个元素,如果用二分法查找方法查找数据元素X,则最多需要比较_____7___次就可以断定数据元素X是否在查找表中。

9.不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为______1______。

10.设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号,则第i个结点的双亲结点编号为___i/2_________,右孩子结点的编号为____2i+1_______。

11.设一组初始记录关键字为（72，73,71，23,94,16,5），则以记录关键字72为基准的一趟快速排序结果为_____5 16 71 23 72 94 73______。

12.设有向图G中有向边的集合E=｛〈1，2〉，<2,3>，〈1，4〉，〈4,2>，〈4，3〉｝，则该图的一种拓扑序列为___1 4 2 3___。

数据结构试卷试题及答案一、选择题（每题5分，共40分）1. 数据结构是研究数据元素的（）A. 存储结构B. 处理方法C. 逻辑结构D. 所有以上内容答案：D2. 在数据结构中，通常采用（）方式来表示数据元素之间的逻辑关系。

A. 顺序存储结构B. 链式存储结构C. 索引存储结构D. 散列存储结构答案：B3. 下面哪一个不是栈的基本操作？（）A. 入栈B. 出栈C. 判断栈空D. 获取栈顶元素答案：D4. 下面哪一个不是队列的基本操作？（）A. 入队B. 出队C. 判断队列空D. 获取队头元素答案：D5. 下面哪一个不是线性表的特点？（）A. 有且只有一个根节点B. 每个节点最多有一个前驱和一个后继C. 数据元素类型相同D. 数据元素类型可以不同答案：D6. 在下列哪种情况中，使用链式存储结构比顺序存储结构更合适？（）A. 数据元素经常插入和删除B. 数据元素大小不固定C. 数据元素个数不确定D. 所有以上情况答案：D7. 下面哪一个不是树的遍历方式？（）A. 前序遍历B. 中序遍历C. 后序遍历D. 翻转遍历答案：D8. 在下列哪种情况中，使用散列存储结构比其他存储结构更合适？（）A. 数据元素个数较少B. 数据元素查找频繁C. 数据元素插入和删除频繁D. 数据元素大小不固定答案：B二、填空题（每题5分，共30分）9. 栈是一种特殊的线性表，它的插入和删除操作都限定在表的一端进行，这一端称为______。

答案：栈顶10. 队列是一种特殊的线性表，它的插入操作在表的一端进行，这一端称为______，而删除操作在另一端进行，这一端称为______。

答案：队尾、队头11. 二叉树中的节点包括______和______。

答案：根节点、子节点12. 在图的存储结构中，邻接矩阵表示法用______个一维数组来表示图中各个顶点之间的关系。

答案：两个13. 散列存储结构中，关键码到存储地址的映射方法称为______。

数据结构试卷一一、选择题20分1．组成数据的基本单位是 ;A 数据项B 数据类型C 数据元素D 数据变量2．设数据结构A=D,R,其中D={1,2,3,4},R={r},r={<1,2>,<2,3>,<3,4>,<4,1>},则数据结构A 是 ;A 线性结构B 树型结构C 图型结构D 集合3．数组的逻辑结构不同于下列的逻辑结构;A 线性表B 栈C 队列D 树4．二叉树中第ii≥1层上的结点数最多有个;A 2iB 2iC 2i-1D 2i-15．设指针变量p指向单链表结点A,则删除结点A的后继结点B需要的操作为 ;A p->next=p->next->nextB p=p->nextC p=p->next->nextD p->next=p6．设栈S和队列Q的初始状态为空,元素E1、E2、E3、E4、E5和E6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出列的顺序为E2、E4、E3、E6、E5和E1,则栈S的容量至少应该是 ;A 6B 4C 3D 27．将10阶对称矩阵压缩存储到一维数组A中,则数组A的长度最少为 ;A 100B 40C 55D 808．设结点A有3个兄弟结点且结点B为结点A的双亲结点,则结点B的度数数为 ;A 3B 4C 5D 19．根据二叉树的定义可知二叉树共有种不同的形态;A 4B 5C 6D 710.设有以下四种排序方法,则的空间复杂度最大;A 冒泡排序B 快速排序C 堆排序D 希尔排序二、填空题30分1.设顺序循环队列Q0：m-1的队头指针和队尾指针分别为F和R,其中队头指针F指向当前队头元素的前一个位置,队尾指针R指向当前队尾元素所在的位置,则出队列的语句为F =____________;;2.设线性表中有n个数据元素,则在顺序存储结构上实现顺序查找的平均时间复杂度为___________,在链式存储结构上实现顺序查找的平均时间复杂度为___________;3.设一棵二叉树中有n个结点,则当用二叉链表作为其存储结构时,该二叉链表中共有________个指针域,__________个空指针域;4.设指针变量p指向单链表中结点A,指针变量s指向被插入的结点B,则在结点A的后面插入结点B的操作序列为______________________________________;5.设无向图G中有n个顶点和e条边,则其对应的邻接表中有_________个表头结点和_________个表结点;6.设无向图G中有n个顶点e条边,所有顶点的度数之和为m,则e和m有______关系;7.设一棵二叉树的前序遍历序列和中序遍历序列均为ABC,则该二叉树的后序遍历序列为__________;8.设一棵完全二叉树中有21个结点,如果按照从上到下、从左到右的顺序从1开始顺序编号,则编号为8的双亲结点的编号是___________,编号为8的左孩子结点的编号是_____________;9.下列程序段的功能实现子串t在主串s中位置的算法,要求在下划线处填上正确语句;int indexchar s , char t{i=j=0;whilei<strlens && j<strlent ifsi==tj{i=i+l; j=j+l;}else{i=_______; j=______;}if j==strlentreturni-strlent;else return -1;}10.设一个连通图G中有n个顶点e条边,则其最小生成树上有________条边;三、应用题30分1．设完全二叉树的顺序存储结构中存储数据ABCDE,要求给出该二叉树的链式存储结构并给出该二叉树的前序、中序和后序遍历序列;2．设给定一个权值集合W=3,5,7,9,11,要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL;3．设一组初始记录关键字序列为19,21,16,5,18,23,要求给出以19为基准的一趟快速排序结果以及第2趟直接选择排序后的结果;4．设一组初始记录关键字集合为25,10,8,27,32,68,散列表的长度为8,散列函数Hk=k mod 7,要求分别用线性探测和链地址法作为解决冲突的方法设计哈希表;5．设无向图G所右图所示,要求给出该图的深度优先和广度优先遍历的序列并给出该图的最小生成树;四、算法设计题20分1.设计判断单链表中结点是否关于中心对称算法;2.设计在链式存储结构上建立一棵二叉树的算法;3.设计判断一棵二叉树是否是二叉排序树的算法;数据结构试卷一参考答案一、选择题二、填空题1. F+1 % m2. On,On3. 2n,n+14. s->next=p->next; s->next=s5. n, 2e6. m=2e7. CBA8. 4,169. i-j+1,010. n-1三、应用题1. 链式存储结构略,前序ABDEC,中序DBEAC,后序DEBCA;2. 哈夫曼树略,WPL=783. 18,5,16,19,21,23,5,16,21,19,18,234. 线性探测：6827322510876543210ΛΛ 链地址法：276832251086543210>->->->->->-h h h h h h h 5. 深度：125364,广度：123456,最小生成树T 的边集为E={1,4,1,3,3,5,5,6,5,6}四、算法设计题1. 设计判断单链表中结点是否关于中心对称算法;typedef struct {int s100; int top;} sqstack;int lklistsymmetrylklist head{sqstack stack; = -1; lklist p;forp=head;p=0;p=p->next {++; =p->data;}forp=head;p=0;p=p->next if p->data== =; else return0;return1;}2. 设计在链式存储结构上建立一棵二叉树的算法;typedef char datatype;typedef struct node {datatype data; struct node lchild,rchild;} bitree;void createbitreebitree &bt{char ch; scanf"%c",&ch;ifch=='' {bt=0; return;}bt=bitreemallocsizeofbitree; bt->data=ch;createbitreebt->lchild; createbitreebt->rchild;}3.设计判断一棵二叉树是否是二叉排序树的算法;int minnum=-32768,flag=1;typedef struct node{int key; struct node lchild,rchild;}bitree;void inorderbitree bt{if bt=0{inorderbt->lchild; ifminnum>bt->keyflag=0; minnum=bt->key; inorderbt->rchild;} }。

广州大学2017-2018学年第二学期试卷课程《数据结构》考试形式（闭卷，考试）物理与电子工程学院电子系电子061、062、063 专业学号姓名一、判断题（对打√，错打×。

每题1分，共15分）1、顺序存储结构只能用于存储线性结构。

( )2、在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。

( )3、在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻( )。

4、二叉树的前序遍历序列中，任意一个结点均处在其子树结点的前面( )。

5、二叉树的前序和后序遍历序列能惟一确定这棵二叉树( )。

6、在无向图中，边的条数是结点度数之和( )。

7、图的邻接矩阵必定是对称矩阵( )。

8、二叉树是度最大为2的有序树( )。

9、结点数固定的二叉树中，完全二叉树具有最小路径长度( )。

10、中序线索树中，右线索若不为空，则一定指向其双亲结点( )。

11、有向图用邻接矩阵表示，容易实现求结点度数的操作( )。

12、按深度优先搜索遍历图时，与始点相邻的结点先于不与始点相邻的结点访问( )13、若有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑排序序列必定存在( )。

14、若有向图G中包含一个环，则G的结点间不存在拓扑排序( )。

15、图的拓扑排序序列是唯一的( )。

二、选择题（每题2分，共20分）1.数据结构被形式定义为（D，S），其中D是（）的有限集合，S是D上的（）有限的集合。

A．算法 B．数据元素C．数据操作D．逻辑结构E．操作F．映像G．存储H．关系2.设n为正整数。

下列程序段中前置以记号@的语句的频度为（）。

i=1;k=0;while(i<n-1){@ k+=10*i;i++;}A．n B．n-1 C．n-2 D．n-33.线性表若采用链式存储结构时，要求内存可用存储单元的地址（）。

A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续不连续都可以4.在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区。

数据结构习题答案一评论:0 条查看:40 次zjw313014322发表于2009-04-21 16:25一、选择题1. 下面说法错误的是 C 。

（1）算法原地工作的含义是指不需要任何额外的辅助空间。

（2）在相同的规模n下，复杂度O（n）的撒在时间上总是优于复杂度O(2n)的算法。

（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界。

（4）同一个算法，实现语言的级别越高，执行效率越低。

A、（1）B、（1）（2）C、（1）（4）D、（3）2. 一个递归算法必须包括 B 。

A、递归部分B、终止条件和递归部分C、迭代部分D、终止条件和迭代部分3. 数据的 C 包括查找、插入、删除、更新、排序等操作类型。

A、存储结构B、逻辑结构C、基本运算D、算法描述4. 在数据结构中，从逻辑上可以把数据结构分成 C 。

A、动态结构和静态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构5. 与数据元素本身的形式、内容、相对位置、个数无关的是数据的 C 。

A、存储结构B、存储实现C、逻辑结构D、运算实现6. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 B 。

A、数据具有同一特点B、不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C、每个数据元素都一样D、数据元素所包含的数据项的个数要相等7. 以下说法正确的是 D 。

A、数据元素是数据的最小单位B、数据项是数据的基本单位C、数据结构是带有结构的各数据项的集合D、一些表面上很不相同的数据可以有相同的逻辑结构8. 以下说法错误的是 A 。

A、程序设计的实质是数据处理B、数据的逻辑结构是数据的组织形式，基本运算规定了数据的基本操作方式C、运算实现是完成运算功能的算法或这些算法的设计D、数据处理方式总是与数据的某种相应表示形式相联系，反之亦然9. 下列程序段的时间复杂度为 B 。

x=n;y=0;while (x>=(y+1)*(y+1))y=y+1;A、O(n)B、O(n1/2)C、O(1)D、O(n2)10. 下列叙述中有关好的编程风格的正确描述是 C 。

数据结构试题库及答案一、选择题1. 在数据结构中，线性结构的特点是：A. 元素之间存在一对一关系B. 元素之间存在一对多关系C. 元素之间存在多对多关系D. 元素之间存在一对一或多对多关系答案：A2. 栈（Stack）是一种特殊的线性表，其特点是：A. 只能在一端进行插入和删除操作B. 可以在两端进行插入和删除操作C. 只能在一端进行插入操作，另一端进行删除操作D. 可以在任意位置进行插入和删除操作答案：A3. 在二叉树中，度为1的节点数目为2，度为0的节点数目也为2，该二叉树的节点总数是：A. 5B. 6C. 7D. 8答案：B二、简答题1. 请简述什么是哈希表，并说明其主要优点。

答案：哈希表是一种通过哈希函数将键映射到表中一个位置来访问记录的数据结构。

其主要优点包括：平均情况下，查找、插入和删除操作的时间复杂度为O(1)，即常数时间内完成操作；空间效率高，能够存储大量数据。

2. 描述图的深度优先搜索（DFS）算法的基本思想。

答案：深度优先搜索算法的基本思想是从一个顶点开始，尽可能深地搜索图的分支。

搜索过程中使用一个栈来保存路径上的顶点。

当搜索到一个顶点时，先访问该顶点，然后依次搜索其所有未被访问过的邻接顶点。

如果当前顶点的所有邻接顶点都被访问过，则回溯到上一个顶点，继续搜索其他邻接顶点。

三、应用题1. 给定一个无向图，使用邻接表表示，请编写一个算法找出图中的所有连通分量。

答案：首先，创建一个访问过的顶点集合。

然后，从图中任意一个未被访问的顶点开始，执行深度优先搜索（DFS）。

每次DFS完成后，就找到了一个连通分量。

重复这个过程，直到所有顶点都被访问过，即可找到图中的所有连通分量。

2. 假设有一个数组，需要频繁地进行查找、插入和删除操作，请设计一个适合这种场景的数据结构，并说明其优势。

答案：对于这种场景，可以使用平衡二叉搜索树（如AVL树或红黑树）。

这些数据结构可以保证在最坏情况下，查找、插入和删除操作的时间复杂度为O(log n)。

数据结构模拟练习题1 参考答案一、单项选择题（每小题2分，共30分）1、算法的计算量的大小称为计算的（ B ）。

A．效率 B. 复杂性 C. 现实性 D. 难度2、静态链表中指针表示的是（B）Ａ.内存地址 B.数组下标 C.下一元素地址 D.左、右孩子地址3、对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（C）Ａ.O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)4、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（D ）。

A．p->next=s;s->next=p->next; B．p->next=s->next;p->next=s;C．p->next=s;p->next=s->next; D． s->next=p->next;p->next=s;5、设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6 , s5,s1,则栈的容量至少应该是（ B ）A.2B. 3C. 5D.66、串是一种特殊的线性表，其特殊性体现在（B）。

A．可以顺序存储 B．数据元素是一个字符C．可以链接存储 D．数据元素可以是多个字符7、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ D ）。

A．9 B．11 C．15 D．不确定8、列说法中正确的是（ A ）。

A．任何一棵二叉树中至少有一个结点的度为2B．任何一棵二叉树中每个结点的度都为2C．任何一棵二叉树中的度肯定等于2D．任何一棵二叉树中的度可以小于29、已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ B ）。

A．CBEFDA B． FEDCBA C． CBEDFA D．不定10、下列哪一种图的邻接矩阵是对称矩阵（ B ）。