下载文档原格式
数据结构习题习题一一、选择题1、数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的（B）和运算的学科。
A．结构B．关系C．运算D．算法2、在数据结构中，从逻辑上可以把数据结构分成（C）。
A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．逻辑结构和存储结构3、线性表的逻辑顺序和存储顺序总是一致的，这种说法（B）。
A．正确B．不正确C．无法确定D．以上答案都不对4、算法分析的目的是（C）。
A．找出算法的合理性B．研究算法的输人与输出关系C．分析算法的有效性以求改进D．分析算法的易懂性二、填空题1、数据是信息的载体，是对客观事物的符号表示，它能够被计算机识别、存储、加工和处理，数据是对能够有效的输人到计算机中并且能够被计算机处理的符号的总称。
例如，数学中所用到的整数和实数，文本编辑所用到的字符串等。
2、数据元素是数据的基本单位，有些情况下也称为元素、结点、顶点、记录等。
3、数据项是数据不可分割的最小单元，是具有独立含义的最小标识单位。
例如构成一个数据元素的字段、域、属性等都可称之为_数据项。
4、简而言之，数据结构是数据之间的相互关系，即数据的组织形式。
5、数据的逻辑结构是指数据之间的逻辑关系。
逻辑结构是从逻辑关系上描述数据，它与具体存储无关，是独立于计算机的。
因此逻辑结构可以看作是从具体问题抽象出来的数学模型。
6、数据的存储结构指数据元素及其关系在计算机存储器内的表示。
存储结构是逻辑结构在计算机里的实现，也称之为映像。
7、数据的运算是指对数据施加的操作。
它定义在数据的逻辑结构之上，每种逻辑结构都有一个数据的运算。
常用的有：查找、排序、插人、删除、更新等操作。
8、数据逻辑结构可以分为四种基本的类型，集合结构中的元素除了仅仅只是同属于一个集合_，不存在什么关系。
9、数据逻辑结构的四种基本类型中，线性结构_中的元素是一种一对一的关系，这种结构的特征是：若结构是非空集，则有且只有一个开始结点和一个终端结点，并且所有结点最多只能有一个直接前驱和一个直接后继。
编译技术中常用的数据结构一、线性表线性表是编译技术中常用的数据结构之一，它是一种能够按照线性顺序存储数据元素的数据结构。
线性表可以通过顺序存储结构或链式存储结构来实现。
1. 顺序存储结构顺序存储结构是将线性表的元素按照顺序存储在一块连续的存储空间中。
在编译技术中，顺序存储结构常用于存储符号表、常量表等数据结构。
通过数组来实现顺序存储结构，可以快速访问线性表的任意位置元素。
2. 链式存储结构链式存储结构是通过节点之间的指针链接来实现线性表的存储。
在编译技术中，链式存储结构常用于存储中间代码、语法树等数据结构。
链式存储结构灵活性较高，可以动态地分配和释放存储空间。
二、栈栈是一种具有后进先出（LIFO）特性的线性表。
在编译技术中，栈常用于处理函数调用、表达式求值等场景。
栈的基本操作包括入栈和出栈。
入栈将元素压入栈顶，出栈将栈顶元素弹出。
编译技术中，栈还常用于处理函数的局部变量、函数的三、队列队列是一种具有先进先出（FIFO）特性的线性表。
在编译技术中，队列常用于处理优化算法、指令调度等场景。
队列的基本操作包括入队和出队。
入队将元素插入队尾，出队将队头元素移除。
编译技术中，队列还常用于处理指令流水线、任务调度等问题。
四、树树是一种非线性的数据结构，它由若干个节点组成，节点之间通过边连接。
在编译技术中，树常用于构建语法树、抽象语法树等数据结构。
树的基本概念包括根节点、叶子节点和内部节点。
树的遍历方式有前序遍历、中序遍历和后序遍历。
编译技术中，树的遍历常用于语法分析、语义分析等阶段。
五、图图是一种由节点和边组成的非线性数据结构。
在编译技术中，图常用于构建控制流图、数据依赖图等数据结构。
图的基本概念包括顶点、边和路径。
图可以分为有向图和无向图，还可以带有权重。
编译技术中，图的遍历常用于寻找程序中的循环、六、哈希表哈希表是一种通过哈希函数将关键字映射到存储位置的数据结构。
在编译技术中，哈希表常用于符号表、常量表等数据结构。
《数据结构》题库及答案一、选择题1．线性表的顺序存储结构是一种 的存储结构，线性表的链式存储结构是一种 的存储结构。
a. 随机存储；b.顺序存储；c. 索引存取；d. HASH 存取2．一个栈的入栈序列是a,b,c,d,e ，则栈的不可能的输出序列是 。
a. edcba;b. decba;c. dceab;d.abcde3．一个队列的入队序列是1，2，3，4，则队列的输出序列是 。
a. 4,3,2,1;b. 1,2,3,4;c. 1,4,3,2;d.3,2,4,14．在一个单链表中，已知p 结点是q 结点的直接前驱结点，若在p 和q 之间插入结点s ，则执行的操作是 。
a. s->nxet=p->next; p->next=s;b. p->next=s->next; s->next=p;c. q->next=s; s->next=p;d. p->next=s; s->next=q;5．设有两个串p,q ，求q 在p 中首次出现的位置的运算称作 。
a.联接b.模式匹配c.求子串d.求串长6．二维数组M 的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i 的范围从0到8，列下标j 的范围从1到10，则存放M 至少需要 个字节。
a. 90b.180c.240d.540 7．在线索二叉树中，结点p 没有左子树的充要条件是 。
a. p->lch==NULLb. p->ltag==1c. p->ltag==1且p->lch=NULLd. 以上都不对8．在栈操作中，输入序列为（A ，B ，C ，D ），不可能得到的输出序列为：______A 、（A ，B ，C ，D ） B 、（D ，C ，B ，A ） C 、（A ，C ，D ，B ） D 、（C ，A ，B ，D ）9．已知某二叉树的后序序列是dabec ，中序序列是debac ，则它的先序序列是 。
2022年忻州师范学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、n个结点的完全有向图含有边的数目（）。
A.n*nB.n(n+1)C.n/2D.n*(n-1)2、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。
A.NB.2N-1C.2ND.N-13、线性表的顺序存储结构是一种（）。
A.随机存取的存储结构B.顺序存取的存储结构C.索引存取的存储结构D.Hash存取的存储结构4、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。
A.543612B.453126C.346521D.2341565、在用邻接表表示图时，拓扑排序算法时间复杂度为（）。
A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)6、已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（）。
A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，197、下列关于无向连通图特性的叙述中，正确的是（）。
Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ8、一个具有1025个结点的二叉树的高h为（）。
A.11B.10C.11至1025之间D.10至1024之间9、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。
A.107B.108C.214D.21510、数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的（）的两趟排序后的结果。
A.选择排序B.起泡排序C.插入排序D.堆排序二、填空题11、在有n个顶点的有向图中，每个顶点的度最大可达______。
820数据结构考研大纲导言本文档旨在全面介绍考研数据结构科目的大纲，帮助考生更好地准备考试。
将按照大纲的结构，详细阐述每个知识点的内容和要求。
第一章概述1.1数据结构的定义数据结构是指数据对象中元素之间的关系，是在计算机中组织和存储数据的方式。
1.2数据结构的基本概念数据结构的基本概念包括数据、数据元素、数据项、数据对象、逻辑结构和物理结构等。
1.3数据结构的分类数据结构可以根据不同的特点进行分类，包括线性结构、非线性结构、集合结构、树结构和图结构等。
第二章线性表2.1线性表的定义和特性线性表是一种包含有限个数据元素的序列，具有前驱和后继关系。
2.2线性表的顺序存储结构线性表的顺序存储结构是利用一段连续的存储单元存储线性表的元素。
2.3线性表的链式存储结构线性表的链式存储结构是通过节点之间的链接关系来存储线性表的元素。
2.4线性表的操作线性表的操作包括插入、删除、查找等基本操作，以及合并、拆分等高级操作。
第三章栈和队列3.1栈的定义和特性栈是一种特殊的线性表，只能在表的一端进行插入和删除操作，遵循先进后出的原则。
3.2栈的顺序存储结构栈的顺序存储结构利用数组来实现，通过栈顶指针来指示栈顶元素。
3.3栈的链式存储结构栈的链式存储结构利用链表来实现，通过指针来指示栈顶元素。
3.4栈的应用栈在计算表达式、递归实现、迷宫求解等方面有广泛的应用。
第四章串和数组4.1串的定义和特性串是由零个或多个字符组成的有限序列，是一种特殊的线性表。
4.2串的存储结构串的存储结构包括顺序存储结构和链式存储结构。
4.3串的操作串的操作包括定位操作、模式匹配操作、替换操作等。
4.4数组的定义和特性数组是相同类型数据元素的有序集合，可以通过下标来访问元素。
第五章树和二叉树5.1树的定义和基本概念树是由n（n>=0）个节点组成的有限集合，其中一个节点被称为根节点。
5.2树的存储结构树的存储结构包括双亲表示法、孩子表示法、孩子兄弟表示法等。
2022年湘南学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、n个结点的完全有向图含有边的数目（）。
A.n*nB.n(n+1)C.n/2D.n*(n-1)2、将线性表的数据元素进行扩充，允许带结构的线性表是（）。
A.串B.树C.广义表D.栈3、线性表的顺序存储结构是一种（）。
A.随机存取的存储结构B.顺序存取的存储结构C.索引存取的存储结构D.Hash存取的存储结构4、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。
A.543612B.453126C.346521D.2341565、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。
A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都可能要修改D.队头、队尾指针都要修改6、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（）。
7、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。
假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。
初始时为空，下列判断队空和队满的条件中，正确的是（）。
A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod MB．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1）C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod MD．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1）8、有n（n>0）个分支结点的满二叉树的深度是（）。
A.n2-1B.log2（n+1）+1C.log2（n+1）D.log2（n-l）9、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。
第 2 章线性表课后习题讲解1. 填空⑴在顺序表中，等概率情况下，插入和删除一个元素平均需移动（）个元素，具体移动元素的个数与（）和（）有关。
【解答】表长的一半，表长，该元素在表中的位置⑵顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（）。
【解答】108【分析】第5个元素的存储地址=第1个元素的存储地址＋(5－1)×2=108⑶设单链表中指针p 指向结点A，若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为（）。
【解答】p->next=(p->next)->next⑷单链表中设置头结点的作用是（）。
【解答】为了运算方便【分析】例如在插入和删除操作时不必对表头的情况进行特殊处理。
⑸非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（）。
【解答】p->next=head【分析】如图2-8所示。
⑹在由尾指针rear指示的单循环链表中，在表尾插入一个结点s的操作序列是（）；删除开始结点的操作序列为（）。
【解答】s->next =rear->next; rear->next =s; rear =s;q=rear->next->next; rear->next->next=q->next; delete q;【分析】操作示意图如图2-9所示：⑺一个具有n个结点的单链表，在指针p所指结点后插入一个新结点的时间复杂度为（）；在给定值为x的结点后插入一个新结点的时间复杂度为（）。
【解答】Ο(1)，Ο(n)【分析】在p所指结点后插入一个新结点只需修改指针，所以时间复杂度为Ο(1)；而在给定值为x的结点后插入一个新结点需要先查找值为x的结点，所以时间复杂度为Ο(n)。
⑻可由一个尾指针唯一确定的链表有（）、（）、（）。
【解答】循环链表，循环双链表，双链表2. 选择题⑴线性表的顺序存储结构是一种（）的存储结构，线性表的链接存储结构是一种（）的存储结构。
数据结构综合题参考答案数据结构综合题部分参考答案（仅供参考）⼀、填空1、⼀个算法的效率可分为_____时间_________效率和______空间________效率。
，2、栈的特点是_____先进后出______,队列的特点是_____先进先出________。
、3、在线性表的顺序存储结构中，若每个元素占L个存储单元，则第i个元素ai的存储位置为LOC(ai)=LOC(a1)+ ____（i-1）*L________。
4、已知⼀棵完全⼆叉树共139个结点，按照层次从左到右进⾏编号，根结点编号为1，则编号为60的左孩⼦编号为_____120_________右孩⼦编号为____121__________双亲编号为____30__________。
、、5、已知P为单链表中的⾮⾸尾结点，在P结点后插⼊S结点的语句为：__ s->next=p->next; p-next=s;___。
6、在各种查找⽅法中,平均查找长度与结点个数n⽆关的查法⽅法是______哈希表查找法________。
7、算法时间复杂度的分析通常有两种⽅法，即__事后统计_________和___事前估计________的⽅法，通常我们对算法求时间复杂度时，采⽤后⼀种⽅法。
8、已知元素序列E,F,G,H,I,J,K,L,M,N经过操作XXYXXYXYXYYXXYXYYYXY以后的出栈序列（注X表⽰⼊栈，Y表⽰出栈）_____ FHIJGLMKEN _________。
9、设数组A[1..10,1..8]的基地址为2000,每个元素占2个存储单元,若以⾏序为主序顺序存储,则元素A[4,5]的存储地址为____2056_______；若以列序为主序顺序存储,则元素A[4,5]的存储地址为_2086______。
10、⼀个⼆叉树中叶⼦结点3个，度为1的结点4个，则该⼆叉树共有___9____个结点。
11、在图G的邻接表表⽰中，每个顶点邻接表中所含的结点数，对于⽆向图来说等于该顶点的__度_____,对于有向图来说等于该顶点的____出度_____。
第2章线性表一、填空题1、线性结构反映结点间的逻辑关系是一对一的。
2、线性结构的特点：1）只有一个首结点和尾结点2）除首尾结点外，其他结点只有一个直接前驱和一个直接后继3、线性表的顺序表示又称为顺序存储结构。
4、结点只有一个指针域的链表，称为单链表。
5、首尾相接的链表称为循环链表。
6、线性表的链式表示又称为非顺序映像。
7、指向链表中第一个结点的指针称为头指针。
8、链表中存储第一个数据元素的结点称为首元结点。
二、判断题1、线性表的逻辑顺序与存储顺序总是一致的。
（╳）2、顺序存储的线性表可以按序号随机存取。
（√）3、顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。
（╳）4、线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。
（√）5、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。
（╳）6、在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。
（√）7、线性表的链式存储结构优于顺序存储结构。
（╳）8、在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。
（√）9、线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。
（√）10、在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。
（╳）11、线性表的特点是每个元素都有一个前驱和一个后继。
（╳）三、单项选择题1、顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（B）。
A．110 B．108 C．100 D．120解释：顺序表中的数据连续存储，所以第5个元素的地址为：100+2*4=108。
2、在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（A）。
A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B．在第i个结点后插入一个新结点（1≤i≤n）C．删除第i个结点（1≤i≤n）D．将n个结点从小到大排序解释：在顺序表中插入一个结点的时间复杂度都是O(n2)，排序的时间复杂度为O(n2)或O(nlog2n)。
