《2023年数据结构知识点归纳.doc》由会员分享，可在线阅读，更多相关《2023年数据结构知识点归纳.doc（17页珍藏版）》请在金锄头文库上搜索。
1、一、数据结构的章节结构及重点构成数据结构学科的章节划分基本上为:概论，线性表，栈和队列，串，多维数组和广义表，树和二叉树，图，查找，内排，外排，文献，动态存储分派。对于绝大多数的学校而言，“外排，文献，动态存储分派”三章基本上是不考的，在大多数高校的计算机本科教学过程中，这三章也是基本上不作讲授的。数据结构的章节比重大体为：1. 概论: 概念，时间复杂度。2. 线性表:基础章节，必考内容之一。概念，算法设计题。3. 栈和队列:基本概念。4. 串 :基本概念。5. 多维数组及广义表 : 基本概念。6. 树和二叉树 :重点难点章节，各校必考章节。概念，问答，算法设计题。7. 图:重点难点章节，各校
2、必考章节。概念，问答，算法设计题。8. 查找 :重点难点章节，概念，问答。9. 排序 :重点难点章节，问答各种排序算法的排序过程二、各章节的重要内容：第一章 概述重要内容：本章重要起到总领作用，为读者进行数据结构的学习进行了一些先期铺垫。大家重要注意以下几点:（1）数据结构的基本概念。（数据；数据元素；数据项；数据结构；数据的逻辑结构：线性和非线性，具体分为集合、线性结构、树形结构和图状结构；数据的存储结构：顺序存储和链式存储；运算）（2）算法的度量：时间效率和空间效率，分别用时间复杂度和空间复杂度度量，掌握时间复杂度的度量方法量方法。（大O表达法）参考题目：填空题：1、数据结构是互相之间存在
3、一种或多种特定关系的数据元素的集合，它涉及三方面的内容，分别是数据的逻辑结构、（ ）和（ ）。2、数据结构按逻辑结构可分为两大类，它们分别是（ ） 和（ ） 3. 数据的物理结构重要涉及（ ）和（ ）两种情况。4线性表，栈，队列和二叉树四种数据结构中（ ）是非线性结构，（ ）是线性结构。5、线性结构中元素之间存在（ ）关系，树形结构中元素之间存在（ ）关系，图形结构中元素之间存在（ ）关系。6、程序段的时间复杂度是_。for(i=1;i=n;i+) k+; for(j=1;j=n;j+) x=x+k; 7下列算法的时间复杂度是_。 for(i=0;im;i+ +) for(j=0;jn;j+
4、+) aij=i；8下列算法的时间复杂度是_。i=s=0;while(s next = NULL； Chead - next = head； Dhead ! = NULL；5、在一个单链表中，若P所指结点不是最后结点，在P之后插入S所指结点，则执行（ ） AS-next=P-next;P-next=S BP-next=S-next;S-next=P； CP-next=P;P-next=S； DP-next=S;S-next=P；6、在已知头指针的单链表中，要在其尾部插入一新结点，其算法所需的时间复杂度为（ ） A（1） B（log2n） CO（n） DO（n2）7、在一个单链表中，已知q所指结
5、点是p所指结点的直接前趋，若在p，q之间插入s结点，则执行的操作是（ ）。 As-next=p-next;p-next=s; Bq-next=s;s-next=p;Cp-next=s-next;s-next=p; Dp-next=s;s-next=q;8、设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中（ ）个数据元素，删除第i个元素（1in）时，需向前移动的元素的个数是（ ）。在顺序表中插入一个元素，需要平均移动（ ）元素，删除一个元素，需要平均移动（ ）元素，具体移动的元素个数与（ ）有关，插入删除操作的时间复杂度均为( )。9、设单链表的结点结构为(data,ne
6、xt)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句: （ ）。10 设指针变量p指向单链表中结点A的前驱结点，若删除单链表中结点A，则执行操作（ ）三、算法设计：1.设计算法，计算顺序表中数据元素为x的元素个数。顺序表结构如下：typedef struct int data100; int length; sqlist;函数首部为： int count(sqlist L, int x) 2设计算法，在顺序线性表中，删除顺序表中第i个元素，顺序表结构同上题。函数首部为：int del(sqlis
7、t *L,int i) 3设计算法，在顺序线性表中，删除值为x的元素。函数首部为：void delx(sqlist *L , int x) 4. 对给定的单链表L(元素各不相同)，编写一个删除L中值为x的结点的算法。链式结构如下：typedef struct LinkList int data; struct LinkList *next; Node,*LinkList;int delx(LinkList *head ,int x) 5.编写算法求带头结点的单链表的表长,结构同上题。int count(LinkList *head)第三章 栈与队列重要内容：栈与队列，是很多学习DS的同学碰到第
8、一只拦路虎，很多人从这一章开始坐晕车，一直晕到现在。栈和队列一章注意以下几个方面:（1） 栈的定义及其相关数据结构的概念：合法的出栈序列、出栈序列个数、顺序栈，链栈（2） 队列的定义及其相关数据结构的概念，涉及:循环队列。（3） 栈和队列的特点：栈-后进先出；队列先进先出。（4） 递归算法概念。栈与递归的关系，所有的递归算法都可以借助栈将递归转向于非递归算法。（5） 操作：顺序栈的进栈、出栈操作。 循环队列的队空、队满条件，出队、入队、求队列元素个数操作。参考题目：1. 循环队列是空队列的条件是（ ）AQ . rear = = Q . front B（Q . rear + 1）%maxsize
9、 = = Q .front CQ . rear = = 0 DQ. front = = 02. 链栈与顺序栈相比，比较明显的优点是（ ） A通常不会出现栈满的情况 B通常不会出现栈空的情况C插入操作更加方便 D删除操作更加方便3. 若一个栈的输入序列是1,2,3，n，输出序列的第一个元素是，则第个输出元素是（ ） An - i Bn i + 1 Ci D不拟定4. 对于一个栈，给定输入序列为1，2，3，则下列不也许为输出序列的是（ ） A1，2，3 B3，2，1 C3，1，2 D2，1，35. 栈是限定在（ ）处进行插入或删除操作的线性表。A端点 B栈底 C栈顶 D中间6. 当循环队列q是满队
10、列时，存放队列元素的数组data有n个元素，则data中存放（ ）个数据元素。AnB. n-1C. n-2D.07. 循环队列用数组elem0，m-1存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是_ _。8栈的特点是 ，队列的特点是 。9. 设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈，一个元素出栈后立即进入队列Q，若6个元素出队的顺序是e2,e4,e3,e6,e5,e1,则栈S的容量至少应当是_ _。10若用一个大小为6的一维数组来实现循环队列，当前rear和front的值分别是0和3，从队列中删除一个元素，再加入两个元素后
11、，当前队列中共 个元素，rear的值为_，front的值为_。第四章 串重要内容：最容易自学的章节之一本章注意：（1）串的基本概念：串（串是其元素均为字符型数据的特殊线性表），子串、空串与空格串的区别，串相等的条件、模式匹配。（2）串的定长顺序存储（3）串的基本操作功能，如求串长,串连接，串替换等，给出一个字符串可以写出操作的结果。参考题目：1串是一种特殊的线性表，其特殊性体现在( )。 2S1=“ABCD”，S2=“CD”则S2在S1中的位置是（ ） 3假设S=“abcaabcaaabca”，T=“bca”，Index (S,T,3) 的结果是（6 ） 4设有S1=ABCDEFG，S2=PQRST，函数con(x，y)返回x和y串的连接串，subs
