数据结构经典算法
1.1 编写冒泡排序算法，使结果从大到小排列。
void BubbleSortDec ( DataType a[], int n )
{
for ( i=0; i change = false; for( j=0; j if ( a[j] swap( a[j], a[j+1] ); change = true; } if ( not change ) break; // 没有交换则完成排序 } } 1.2 计算下面语句段中指定语句的频度： 1) for ( i=1; i<=n; i++ ) for ( j=i; j<=n; j++ ) x++; // @ 2) i = 1; while ( i<=n ) i = i*2; // @ 分析：计算语句频度是计算时间复杂度的基础。可以用观察和归纳进行简单的计算。 1) 问题规模n 执行次数 1 1 2 2+1 3 3+2+1 ... ... n n+...+2+1=n(n+1)/2 结论：语句频度为n(n+1)/2。 2) 问题规模n 执行次数 1 1 2 2 3 2 4 3 ... ... 2k k+1 结论：语句频度为。 2.1 将顺序表中的元素反转顺序。 void Reverse ( SqList& L ) { for ( i=0; i L.elem[i] L.elem[L.length-i-1]; } 2.2 在非递减有序的顺序表中插入元素x，并保持有序。 思路1：先查找适合插入的位置i 向后移动元素（从后向前处理） 插入元素，表长加1 思路2：从后向前查找插入位置，同时向后移动大于x的元素插入元素，表长加1 注意：表满时不能插入。 // 顺序表结构 const int MAXSIZE = 1024; typedef struct { DataType elem[MAXSIZE]; int length; } SqList; // 向非递减有序的顺序表L中插入元素x，仍保持非递减有序 // 插入成功返回true，否则返回false bool OrderListInsert ( SqList &L, DataType x ) { if ( L.length==MAXSIZE ) return false; // 表满，插入失败// 将大于x的元素后移 for ( i=L.length-1; i>=0 && L.elem[i]>x; i--) L.elem[i+1] = L.elem[i]; // 插入x (因为最后执行i--，故应在i+1处) L.elem[i+1] = x; L.length++; return true; } 2.3 删除顺序表中所有等于x的元素。 void Remove ( SqList &L, DataType x ) { i = 0; // 剩余元素个数，同时是下一个元素的插入位置 for ( j=0; j if ( L.elem[j]!=x ) { // 复制不等于x的元素组成新表 if ( i!=j ) L.elem[i] = L.elem[j]; // 当i==j时不必复制 i++; } L.length = i; // 剩余元素个数 } 本算法的时间复杂度为O(n)；若改用反复调用查找和删除算法，时间复杂度会达到O(n2)。 2.4 编写算法实现顺序表元素唯一化(即使顺序表中重复的元素只保留一个)，给出算法的时间复杂度。 思路：设已经唯一化的序列是(a0, … , a i-1)，剩余序列是(a j,…, a n)。所要做的就是在已经唯一化的序列L.elem[0..i-1]中查找L.elem[j]，如果未找到则复制到L.elem[i]处。如此重复直到剩余序列为空。 void Unique ( SqList &L ) { if ( L.length<=1 ) return; // 空表或只有一个元素的表已经唯一化了 i = 1; // 开始L.elem[0..0]是唯一化序列 for ( j=1; j // 在L.elem[0..i-1]中查找L.elem[j] for ( k=0; k if ( L.elem[k]==L.elem[j] ) break; if ( k==i ) { // L.elem[j]未出现过，复制到L.elem[i]处 if ( j!=i ) L.elem[i] = L.elem[j]; i++; } } L.length = i; // 表长为i } 以上算法的时间复杂度为O(n2)。当然，可以反复将重复元素删除达到唯一化，时间复杂度仍是O(n2)，但是与以上算法相比要移动更多元素。 错误！未找到引用源。 分析：由于该表是有序的，相等的元素必然靠在一起，不必从头开始查找，所以算法的时间复杂度可以降低。 思路：类似习题2.4，但是查找部分只要与L.elem[i-1]比较就可以了。 void Unique ( SqList &L ) { i = 0; // 开始的唯一化序列为空(?对比习题2.4思考为什么不用i=1开始2[②]) for ( j=1; j if ( L.elem[j]!=L.elem[i-1] ) { // Note：写成L.elem[j]!=L.elem[j-1]亦可 if ( j!=i ) L.elem[i] = L.elem[j]; i++; } L.length = i; // 表长 } 错误！未找到引用源。 思路：从链上依次取下结点，按照逆序建表的方法(参见2.3. (8) 2°. 节)重新建表。 void Reverse ( LinkList &L ) { p = L->next; // 原链表 L->next = NULL; // 新表(空表) while ( p ) { // 从原链表中取下结点s s = p; p = p->next; // 插入L新表表头 s->next = L->next; L->next = s; } } 错误！未找到引用源。 void InsertionSort ( LinkList &L ) { h = L->next; // 原链表 L->next = NULL; // 新空表 while ( h ) { // 从原链表中取下结点s s = h; h = h->next; // 在新表中查找插入位置 p = L; while ( p->next && p->next->data<=s->data ) p = p->next; // 在p之后插入s s->next = p->next; p->next = s; } } 错误！未找到引用源。 void SelectionSort ( LinkList &L ) { p = L; while ( p->next ) { // 选择最小(从p->next至表尾) q = p; // 最小元素的前驱q s = p; while ( s->next ) { if ( s->next->data < q->next->data ) q = s; s = s->next; } m = q->next; // 找到最小m // 最小元素m插入有序序列末尾(p之后) if ( q!=p ) { q->next = m->next; // 解下最小m m->next = p->next; // 插入p之后 p->next = m; } p = p->next; // L->next至p为有序序列 } } 错误！未找到引用源。 // 将非递减有序的单链表lb合并入la，保持非递减有序 // 结果la中含有两个链表中所有元素，lb为空表 void Merge ( LinkList &la, LinkList &lb ) { p = la, q = lb; while ( p->next and q->next ) { // 跳过la中较小的元素 while ( p->next and (p->next->data <= q->next->data) ) p = p->next; // 把lb中较小的元素插入la中 while ( p->next and q->next and (q->next->data < p->next->data) ) { s = q->next; q->next = s->next; s->next = p->next; p->next = s; p = s; } } if ( lb->next ) { // 表lb剩余部分插入la末尾 p->next = lb->next; lb->next = NULL; } } 3.1 元素1,2,3,4依次入栈，不可能的出栈序列有哪些？ 分析：什么是不可能的出栈序列？如果后入栈的数(如4)先出栈，则此前入栈元素(如1,2,3)在栈中的顺序就确定了，它们的出栈顺序一定是逆序(如3,2,1)，否则就是不可能的出栈序列(如2,1,3)。 不可能的出栈序列有：4123，4132，4213，4231，4312，3412，3142，3124。其中后3种都含312这一不可能序列。 错误！未找到引用源。 [f a][r][][][]→[f a][b][r][][]→[f a][b][c][r][]→[][f b][c][r][]→[][][f c][r][]→ [][][][f r][] 队列空 → ... →[f][r][][f d][e]→[f][g][r][f d][e] 队列满。 错误！未找到引用源。 思路：先将队列中的元素入栈，然后从栈中取出重新入队列。 void Reverse ( SqQueue &Q ) { InitStack ( S ); while ( ! QueueEmpty(Q) ) { DeQueue ( Q, x ); Push ( S, x ); } while ( ! StackEmpty(S) ) { Pop ( S, x ); EnQueue ( Q, x ); } } 4.1 长度为n的串的子串最多有多少个？ 思路：对子串长度归纳。 子串的长度是0，1，2，...，n，对应子串的个数分别是1(空串)，n，n-1，...，1，总起来就是1+n+(n-1)+...+2+1=1+n(n+1)/2。 6.1 度为k的树中有n1个度为1的结点，n2个度为2的结点，…，n k个度为k的结点，问该树中有多少个叶子结点。 分析：分别从结点个数和分支个数考虑。 设叶子个数为n0，结点总数：n = n0+n1+n2+...+n k，分支数目：n-1 = n1+2 n2+...+k n k，于是得到叶子个数 错误！未找到引用源。 分析：完全二叉树中度为1的结点至多有一个。 完全二叉树中的结点数n+(n-1) ≤N ≤n + (n-1) + 1，即2n-1 ≤N ≤2n，二叉树的高度是 于是，(1) 当n=2k时，，当没有度为1的结点时；，当有1个度为1的结点时。(2) 其他情况下，。 错误！未找到引用源。 void PrintBinaryTree ( BinTree bt, int indent ) { if ( ! bt ) return; for ( i=0; i print ( bt->data ); PrintBinaryTree ( bt->lchild, indent+1 ); PrintBinaryTree ( bt->rchild, indent+1 ); } 错误！未找到引用源。 void PrintBinaryTree ( BinTree bt, int level ) { if ( ! bt ) return; PrintBinaryTree ( bt->rchild, level+1 ); // 旋转后先打印右子树 for ( i=0; i print ( bt->data ); PrintBinaryTree ( bt->lchild, level+1 ); } 错误！未找到引用源。 分析：按层遍历完全二叉树，当遇到第一个空指针之后应该全都是空指针。 bool IsComplete ( BinTree bt ) { // 按层遍历至第一个空指针 InitQueue ( Q ); EnQueue ( Q, bt ); while ( ! QueueEmpty(Q) ) { DeQueue ( Q, p ); if ( p ) { EnQueue ( Q, p->lchild ); EnQueue ( Q, p->rchild ); break; // 遇到第一个空指针时停止遍历 } // 检查队列中剩余元素是否全部是空指针 while ( ! QueueEmpty(Q) ) { DeQueue ( Q, p ); if ( ! p ) return false; // 不是完全二叉树 } return true; // 完全二叉树 } 错误！未找到引用源。 分析：进行后序遍历时，栈中保存的是当前结点的所有祖先。所以，后序遍历二叉树，遇到该结点时，取出栈中的内容即是所有祖先。 // 求二叉树bt中结点xptr的所有祖先 vector Ancestors ( BinTree bt, BinTree xptr ) { stack s; stack tag; p = bt; while ( p || ! s.empty() ) { if ( p ) { s.push ( p ); tag.push ( 1 ); p = p->lchild; } else { p = s.pop(); f = tag.pop(); if ( f==1 ) { s.push ( p ); tag.push ( 2 ); p = p->rchild; } else { if ( p==xptr ) { v = s; // 当前栈的内容就是xptr的所有祖先 return v; } p = NULL; } } return vector(); // return a null vector } 注：这里为描述方便借助了C++中的某些描述方式。 错误！未找到引用源。 思路：用后序遍历求出两者的所有祖先，依次比较。 // 求二叉树bt中两个结点q和r的最近的共同祖先 BinTree LastAncestor ( BinTree bt, BinTree q, BinTree r ) { stack sq, sr; stack s; stack tag; // 求q和r的所有祖先 p = bt; while ( p || ! s.empty() ) { if ( p ) { s.push ( p ); tag.push ( 1 ); p = p->lchild; } else { p = s.pop(); f = tag.pop(); if ( f==1 ) { s.push ( p ); tag.push ( 2 ); p = p->rchild; } else { if ( p==q ) sq = s; // q的所有祖先 if ( p==r ) sr = s; // s的所有祖先 p = NULL; } } } // 先跳过不同层的祖先，然后依次比较同一层的祖先 if ( sq.size()>sr.size() ) while ( sq.size()>sr.size() ) sq.pop(); else while ( sr.size()>sq.size() ) sr.pop(); // 求q和r的最近的共同祖先 while ( !sq.empty() and (sq.top()!=sr.top()) ) { //寻找共同祖先sq.pop(); sr.pop(); } if ( !sq.empty() ) return sq.top(); else return NULL; } 错误！未找到引用源。 分析：当左孩子的优先级低于根时需要加括号，根的优先级大于右孩子时也需要加括号。void PrintExpression ( BinTree bt ) { if ( bt==NULL ) return ; if ( bt->lchild==NULL and bt->rchild==NULL ) print ( bt->data ); // 叶子结点直接打印 else { // 左子树 brackets = bt->lchild and is_operator(bt->lchild->data) and comp_operator(bt->lchild->data, bt->data)<0; // 左孩子优先级低于根if ( brackets ) print (“(“); PrintExpression ( bt->lchild ); if ( brackets ) print (“)”); // 根结点 print ( bt->data ); // 右子树 brackets = bt->rchild and is_operator(bt->lchild->data) and comp_operator(bt->data, bt->rchild->data)>0; // 根的优先级大于右孩子if ( brackets ) print (“(“); PrintExpression ( bt->rchild ); if ( brackets ) print (“)“); } } 注：is_operator(c)判断c是否是运算符；comp_operator(a,b)比较两个运算符的优先级。bool is_operator(char c) { // 判断c是否是运算符 return c=='+' || c=='-' || c=='*' || c=='/'; } int comp_operator(char opl, char opr) { // 比较两个运算符的优先级 return (opl=='*' || opl=='/' || opr=='+' || opr=='-') ? +1 : -1; } 错误！未找到引用源。 分析：树中的叶子没有孩子，即firstchild为空。 // 求树t中叶子结点的个数 int LeafCount ( CSTree t ) { if ( t==NULL ) return 0; // 空树 if ( t->firstchild==NULL ) // 没有孩子 return 1 + LeafCount(t->nextsibling); else return LeafCount(t->firstchild) + LeafCount(t->nextsibling); } 错误！未找到引用源。 分析：度最大的结点的度数。 int Degree ( CSTree t ) { if ( t==NULL ) return 0; else return max( Degree(t->firstchild), 1+Degree(t->nextsibling)); } 错误！未找到引用源。 int Depth ( CSTree t ) { if ( t==NULL ) return 0; else { depchild = Depth(t->firstchild); // 孩子的深度 depsibling = Depth(t->nextsibling); // 兄弟的深度 return max(depchild+1, depsibling); // 取较大者 } } 错误！未找到引用源。 分析：划分先序序列a=(D,(L),(R))和后序序列b=((L),D,(R))，然后对子序列(L)和(R)递归。 // 根据先序序列a[si..ti]和中序序列b[sj..tj]构造二叉树 BinTree CreateBinaryTree ( T a[], int si, int ti, T b[], int sj, int tj ) { if ( n<=0 ) return 0; // 空树 // 建立根结点 p = new BinNode(a[si]); // 以a[si]为数据域建立新结点 // 根据根结点划分中序序列为b[sj..k-1]和b[k+1..tj] k = sj; while ( b[k]!=a[si] ) k++; // 在b[]中搜索根结点a[si] // 建立左右子树 p->lchild = CreateBinaryTree ( a, si+1, si+k-sj, b, sj, k-1 ); // 建立左子树 p->rchild = CreateBinaryTree ( a, si+k-sj+1, b, k+1, tj); // 建立右子树 return p; } 6.13 树T的先根遍历序列为GFKDAIEBCHJ，后根遍历序列为DIAEKFCJHBG，画出树T。 分析：根据先根和后根序列可以唯一确定一棵树。先根序列中的第一个是树的根，后根序列中最后一个是根，然后根据先根序列和后根序列，将其余序列划分成若干不相交的子序列，就是根的子树，对每一个子树，重复前面的步骤，最终就可以得到整个树。 先根GFKDAIEBCHJ 根为G，第一棵子树的根为F，又后根DIAEKFCJHBG，所以第一棵子树为(DIAEKF)，同样第二棵子树为(CJHB)，依此类推，可得该树。 G F D K I C B A E H J 错误！未找到引用源。 分析：根据森林和二叉树的对应关系，可知森林的先序序列和中序序列。划分出每一棵树，正好得到每棵树的先序和后序序列，最终得到整个森林。 B A D G C E F H I K L J 错误！未找到引用源。 分析：由于每个字符出现的频率不同，使用固定长度的编码往往比哈夫曼编码使得整个通信量增多。这里先建立哈夫曼树，得出哈夫曼编码，然后计算通信所需的字节数。每字节含8位。 使用固定长度的编码所需字节数为(20+6+34+11+9+7+8+5)*3/8=37.5字节。一种可能的哈夫曼编码是：A:00, B:1100, C:10, D:010, E:011, F:1110, G:1111, H:1101，通信的总字节数是[(20+34)*2+(11+9)*3+(6+5+7+8)*4]/8=34字节。 6.16 n个权值构造的哈夫曼树共有多少个结点？ 分析：哈夫曼树总是取两个最小的子树合并成一棵二叉树，共需n-1步完成算法，共增加n-1 个结点，故总结点个数为n+(n-1)=2n-1。 7.1 具有n个顶点的有向图构成强连通图最少有多少条弧？当弧的数目超过多少时该图一定是强连通的？ 分析：如果n条弧恰好使n个顶点构成环的话，这是构成强连通图所需弧最少的情况。类似无向图的情况，n-1个顶点最多有(n-1)(n-2)条弧，再增加n-1条指向另外一点顶点的弧(或者相反方向的弧)，此时该图恰好不能构成强连通图，若再增加一条弧则必定强连通。 因此，n个顶点的有向图最少需要n条弧就可以构成强连通图；当弧的数目超过(n-1)(n-2)+(n-1) = (n-1)2时，必定构成强连通图。 7.2 给出下面有向图(a)的1)邻接矩阵2)邻接表3)逆邻接表4) 十字链表和无向图(b)的5)邻接多重表。 A B C D E A B C D E (a) 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 A B C D E B C /\ D E 0 1 2 3 4 2 /\ 2 3 /\ 0 2 /\ 0 3 数据结构与算法基础知识总结 1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 2 数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 3 线性表及其顺序存储结构 线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。 非空线性表的结构特征： （1）且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件； （3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。 线性表的顺序存储结构具有以下两个基本特点： （1）线性表中所有元素的所占的存储空间是连续的； （2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 ai的存储地址为：adr(ai)=adr(a1)+(i-1)k,，adr(a1)为第一个元素的地址，k代表每个元素占的字节数。 顺序表的运算：插入、删除。（详见14--16页） 4 栈和队列 栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。 栈按照“先进后出”（filo）或“后进先出”（lifo）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。 栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。 队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。rear指针指向队尾，front指针指向队头。 队列是“先进行出”（fifo）或“后进后出”（lilo）的线性表。 队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。循环队列：s=0表示队列空，s=1且front=rear表示队列满 前端如何搞定数据结构与算法(先导篇) 「观感度：?」 「口味：锅包肉」 「烹饪时间：20min」 本文已收录在Github? 为什么要学习数据结构与算法？ 在0202年的今天，由于每天被无数的信息轰炸，大多数人已经变得越来越浮躁了，并且丧失了独立思考的能力。 你可能会经常听到这样的感慨： 技术人究竟能走多远？我遇到了天花板 35岁的程序员要如何面对中年危机？ 技术更新太快，好累，学不动了 然后，你也变得焦虑起来。那你有没有静下心来想过，如何才能抵御年龄增长并且使自己增值呢？ 无非是终身学习，持续修炼自己的内功。内功也就是基础知识和核心概念，这些轰轰烈烈发展的技术本质，其实都是基础知识，也就是我们在大学里学过的基础课-程。 操作系统 计算机组成原理 计算机网络 编译原理 设计模式 数据结构与算法 这也就是为什么越靠谱的面试官越注重你基础知识的掌握程度，为什么越牛的的企业越重视你的算法能力。因为当你拥有了这些，你已经比大多数人优秀了。你的天花板由你自己来决定，大家口中的中年危机可能并不会成为你的危机。新技术来临时，你对它的本质会看得更加透彻，学起来会一通百通。这样的人才，公司培养你也会花费更少的成本。 (不过，一辈子做个开开心心的 CRUD Boy 也是一种选择。) 数据结构与算法之间的关系 Rob Pikes 5 Rules of Programming中的第五条是这样说的： Data dominates. If youve chosen the right data structures and organized things well, the algorithms will almost always be self-evident. Data structures, not algorithms, are central to programming. 数据占主导。如果您选择了正确的数据结构并组织得当，那么这些算法几乎总是不言而喻的。数据结构而非算法是编程的核心。 瑞士计算机科学家，Algol W，Modula，Oberon 和 Pascal 语言的设计师 Niklaus Emil Wirth 写过一本非常经典的书《Algorithms + Data Structures = Programs》，即算法 + 数据结构 = 程序。 我们可以得出结论，数据结构与算法之间是相辅相成的关系。数据结构服务于算法，算法作用于特定的数据结构之上。 数据结构与算法好难，怎么学？ 数据结构例题（及答案） 项目一习题(答案) 一选择题 1. 算法的计算量的大小称为计算的(B )。 A( 效率 B. 复杂性 C. 现实性 D. 难度 2.算法的时间复杂度取决于(C ) A(问题的规模 B. 待处理数据的初态 C. A和B 3(从逻辑上可以把数据结构分为(C )两大类。 A(动态结构、静态结构 B(顺序结构、链式结构 C(线性结构、非线性结构 D(初等结构、构造型结构 4(连续存储设计时，存储单元的地址(A )。 A(一定连续 B(一定不连续 C(不一定连续 D(部分连续，部分不连续 5. 以下属于逻辑结构的是(C )。 A(顺序表 B. 哈希表 C.有序表 D. 单链表 二、判断题 1. 数据元素是数据的最小单位。(×) 2. 记录是数据处理的最小单位。(×) 3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系;(×) 4(程序一定是算法。(×) 5. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。(×) 6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(×) 7. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。(?) 8. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. (×) 三、填空 1(数据的物理结构包括数据元素的表示和数据元素间关系的表示。 2. 对于给定的n个元素,可以构造出的逻辑结构有集合，线性结构，树形 结构，图状结构或网状结构四种。 3(数据的逻辑结构是指数据的组织形式，即数据元素之间逻辑关系的总体。而 逻辑关系是指数据元素之间的关联方式或称“邻接关系”。 4(一个数据结构在计算机中表示(又称映像) 称为存储结构。 5(抽象数据类型的定义仅取决于它的一组逻辑特性，而与在计算机内部如何表 示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响 其外部使用。 6(数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度。 7. 数据结构是研讨数据的逻辑结构和物理结构，以及它们之间的相互 关系，并对与这种结构定义相应的操作(运算)，设计出相应的算法。 ( 一个算法具有5个特性: 有穷性、确定性、可行性，有零个或多个输入、 有一个或多个输8 出。 四、应用题 1. 1. 数据结构是一门研究什么内容的学科, 答:数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象 及对象间的关系和施加于对象的操作等的学科 2. 2. 数据元素之间的关系在计算机中有几种表示方法,各有什么特点, 答:四 种表示方法 算法与数据结构复习资料 一、单选题 在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( B)。 A. HL=p;p->next=HL; B.p->next=HL->next;HL->next=p; C.p->next=HL;p=HL; D.p->next=HL;HL=p; 若顺序存储的循环队列的QueueMaxSize=n,则该队列最多可存储（B）个元素. A. n B.n-1 C.n+1 D.不确定 下述哪一条是顺序存储方式的优点？（A） A．存储密度大B.插入和删除运算方便 C. 获取符合某种条件的元素方便 D.查找运算速度快 设有一个二维数组A[m][n]，假设A[0][0]存放位置在600 (10)，A[3][3]存放位置在678 (10) ， 每个元素占一个空间，问A[2][3] (10)存放在什么位置？(脚注 (10) 表示用10进制表示,m>3)C A．658 B．648 C．633 D．653 下列关于二叉树遍历的叙述中，正确的是( D) 。 A. 若一个树叶是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点 B．若一个点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点 C．若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点 D．若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点 k层二叉树的结点总数最多为(A). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 对线性表进行二分法查找，其前提条件是( C). A.线性表以链接方式存储，并且按关键码值排好序 B.线性表以顺序方式存储，并且按关键码值的检索频率排好序 C. 线性表以顺序方式存储，并且按关键码值排好序 D. 线性表以链接方式存储，并且按关键码值的检索频率排好序 对n个记录进行堆排序，所需要的辅助存储空间为（C） A. O（1og2n） B. O（n） C. O（1） D.O（n2） 对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K）=K%7作为散列函数，则散列地址为0的元素有（D）个， A．1 B．2 C．3 D．4 下列关于数据结构的叙述中，正确的是( D). A. 数组是不同类型值的集合 B. 递归算法的程序结构比迭代算法的程序结构更为精炼 C. 树是一种线性结构 D. 用一维数组存储一棵完全二叉树是有效的存储方法 在决定选取何种存储结构时，一般不考虑（ A ）。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是（B）。A．单链表B．静态链表C．线性链表D．顺序存储结构 设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（A）。 A．q=p->next；p->data=q->data；p->next=q->next；free(q)； B．q=p->next；q->data=p->data；p->next=q->next；free(q)； C．q=p->next；p->next=q->next；free(q)； 《数据结构与算法》复习题 选择题 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构 B．数据结构 C．数据的逻辑结构 D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑 B．存储 C．逻辑和存储 D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。A．数据的处理方法 B．数据元素的类型 C．数据元素之间的关系 D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何 B．结点个数的多少 C．对数据有哪些运算 D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。（1）A．找出数据结构的合理性 B．研究算法中的输入和输出的关系C．分析算法的效率以求改进 C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度 B．正确性和简明性 C．可读性和文档性 D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是 O(n2) 。 s =0; for( I =0; i 复习题集─参考答案 一判断题 （√）1. 在决定选取何种存储结构时，一般不考虑各结点的值如何。 （√）2. 抽象数据类型与计算机部表示和实现无关。 （×）3. 线性表采用链式存储结构时，结点和结点部的存储空间可以是不连续的。 （×）4. 链表的每个结点中都恰好包含一个指针。 （×）5.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。（×）6. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 （×）7. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （×）8. 线性表在物理存储空间中也一定是连续的。 （×）9. 顺序存储方式只能用于存储线性结构。 （√）10.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）11.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 （√）12.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）13.两个栈共享一片连续存空间时，为提高存利用率，减少溢出机会，应把两个栈的栈底分别设在这片存空间的两端。 （×）14.二叉树的度为2。 （√）15.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。 （×）16.二叉树中每个结点的两棵子树的高度差等于1。 （√）17.用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 （√）18.具有12个结点的完全二叉树有5个度为2的结点。 （√）19.二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。 （×）20.在冒泡法排序中，关键值较小的元素总是向前移动，关键值较大的元素总是向后移动。 （×）21.计算机处理的对象可以分为数据和非数据两大类。[计算机处理的对象都是数据] （×）22.数据的逻辑结构与各数据元素在计算机中如何存储有关。 （×）23.算法必须用程序语言来书写。 （×）24.判断某个算法是否容易阅读是算法分析的任务之一。 （×）25.顺序表是一种有序的线性表。[任何数据结构才用顺序存储都叫顺序表] （√）26.分配给顺序表的存单元地址必须是连续的。 （√）27.栈和队列具有相同的逻辑特性。[它们的逻辑结构都是线性表] （√）28.树形结构中每个结点至多有一个前驱。 （×）29.在树形结构中，处于同一层上的各结点之间都存在兄弟关系。 （×）30.如果表示图的邻接矩阵是对称矩阵，则该图一定是无向图。 （×）31.如果表示图的邻接矩阵是对称矩阵，则该图一定是有向图。 （×）32.顺序查找方法只能在顺序存储结构上进行。 （×）33.折半查找可以在有序的双向链表上进行。 数据结构经典例题 1.设计一个算法将L拆分成两个带头节点的单链表L1和L2。 void split(LinkList *&L,LinkList *&L1,LinkList *&L2) { LinkList *p=L->next,*q,*r1; //p指向第1个数据节点 L1=L; //L1利用原来L的头节点 r1=L1; //r1始终指向L1的尾节点 L2=(LinkList *)malloc(sizeof(LinkList));//创建L2的头节点 L2->next=NULL; //置L2的指针域为NULL while (p!=NULL) { r1->next=p; //采用尾插法将*p(data值为ai)插入L1中 r1=p; p=p->next; //p移向下一个节点(data值为bi) q=p->next; //由于头插法修改p的next域,故用q保存*p的后继节点 p->next=L2->next; //采用头插法将*p插入L2中 L2->next=p; p=q; //p重新指向ai+1的节点 } r1->next=NULL; //尾节点next置空 } 2.查找链表中倒数第k个位置上的节点（k为正整数）。若查找成功，算法输出该节点的data域的值，并返回1；否则，只返回0。 typedef struct LNode {int data; struct LNode *link; } *LinkList; int Searchk(LinkList list,int k) { LinkList p,q; int count=0; p=q=list->link; while (p!=NULL) { if (count 数据结构与方法 1、算法的基本特征:可行性、确定性、有穷性、拥有足够的情报 2、算法的基本运算与操作:算术运算、逻辑运算、关系运算、数据传输 3、算法的基本控制结构:顺序结构、选择结构、循环(重复)结构 4、算法设计的基本方法:列举法、归纳法、递推、递归、减半递推技术、回溯法 5、算法的复杂度主要包括:时间复杂度、空间复杂度 6、算法的时间复杂度:指执行算法所需要的计算工作量 7、算法的空间复杂度:指执行这个算法所需要的内存空间 8、数据结构主要研究:数据的逻辑结构、数据的存储结构、对各种数据结构进行的运算 9、数据结构研究的目的:提高数据处理的效率 10、数据处理的效率:数据处理的速度、减少处理过程中占用计算机的存储空间 11、数据处理:指对数据集合中的各元素以各种方式进行运算 12、数据元素:指在数据处理中,每一个需要处理的对象都可以抽象成数据元素 13、数据结构:指反映数据元素之间关系的数据元素集合的表示 14、数据的逻辑结构:指反映数据元素之间逻辑关系的数据结构,两要素:数据元素的集合、数据元素在集合上的关系 15、数据的存储结构:指数据的逻辑结构在计算机存储空间的存放形式,常用的存储结构有:顺序、链接、索引等 16、数据结构的图形表示中每个元素加上方框成为结点 17、数据结构一般分为:线性结构、非线性结构 18、线性结构满足:有且仅有一个根结点、每个结点最多有一个前件与后件、在一个线性结构中插入与删除任何一个结点后还就是线性结构 19、线性表定义:线性表就是由n个数据元素a1、a2、a3、a4……an组成的一个有限序列,表中每一个数据元素,除了第一个外,有且仅有一个前件,除了最后一个外,有且仅有一个后件20、非线性表的特征:有且只有一个根节点a1,它无前件、有且只有一个终结点an,它无后件、除了第一个与最后一个外,其她所有结点只有一个前件与一个后件 21、线性表的长度:线性表中的结点的个数n成为线性表的长度,当n=0时,成为空表 22、线性表的顺序存储的特点:所有元素所占的存储空间就是连续的、各数据元素在存储空间中就是按逻辑顺序一次存放的 23、线性表的随机存取地址计算公式:ADD(ai)=ADD(a1)+(i-1)*k 24、线性表的主要操作:插入、删除、查找、排序、分解、合并、复制、逆转 25、栈的定义:栈就是限定在一端进行插入与删除的线性表,它按照“先进后出,后进先出”的原则组织数据 26、栈的顺序存储:在程序设计语言中,一般一维数组S(1:m)作为栈的顺序存储空间,其中m 为栈的最大容量 27、栈的基本运算:入栈、退栈、读栈顶元素 28、入栈运算:首先将栈顶指针(top)加1,然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时,说明栈空间已满,称为“上溢”错误 29、退栈运算:首先将栈顶元素赋给一个指定的变量,然后将栈顶指针(top)减1。当栈顶指针为0时,说明栈空,成为“下溢”错误 30、队列的定义:队列就是指允许在一端进行插入,而在另一端进行删除的线性表,它按照“先进先出”的原则组织数据 31、循环队列:在实际应用中,队列的顺序存储结构一般采用循环队列的形式。所谓循环队列, //插入排序法 void InsertSort() { int s[100]; int n,m,j,i=0,temp1,temp2; printf("请输入待排序的元素个数："); scanf("%d",&n); printf("请输入原序列："); for (i=0; i //堆排序 static a[8] = {0,25,4,36,1,60,10,58,}; int count=1; void adjust(int i,int n) { int j,k,r,done=0; k = r = a[i]; j = 2*i; while((j<=n)&&(done==0)) { if(j 数据结构与算法设计知识点 试题类型： 本课程为考试科目（闭卷笔试），试题类型包括：概念填空题（10 %），是非判断题（10 %），单项选择题（40 %），算法填空题（10%），算法应用题（20 %)，算法设计题（10 %）。 第一章绪论 重点内容及要求： 1、了解与数据结构相关的概念（集合、数据、数据元素、数据项、关键字、元 素之间的关系等）。 数据：所有能被输入到计算机中，且能被计算机处理的符号的 集合。是计算机操作的对象的总称。是计算机处理的信息的某种特定 的符号表示形式。 数据元素：是数据（集合）中的一个“个体”，数据结构中的基本 单位，在计算机程序中通常作为一个整体来考虑和处理。 数据项：是数据结构中讨论的最小单位，数据元素可以是一个或 多个数据项的组合 关键码：也叫关键字（Key），是数据元素中能起标识作用的数 据项。 其中能起到唯一标识作用的关键码称为主关键码（简称主码）； 否则称为次关键码。通常，一个数据元素只有一个主码，但可以有多 个次码。 关系：指一个数据集合中数据元素之间的某种相关性。 数据结构：带“结构”的数据元素的集合。这里的结构指元素之 间存在的关系。 数据类型：是一个值的集合和定义在此集合上的一组操作的总 称。 2、掌握数据结构的基本概念、数据的逻辑结构（四种）和物理结构（数据元素 的表示与关系的表示、两类存储结构：顺序存储结构和链式存储结构）。 数据结构包括逻辑结构和物理结构两个层次。 数据的逻辑结构：是对数据元素之间存在的逻辑关系的一种抽象的描述，可以用一个数据元素的集合和定义在此集合上的若干关系来表示 逻辑结构有四种：线性结构、树形结构、图状结构、集合结构数据的物理结构：是其逻辑结构在计算机中的表示或实现，因此又称其为存储结构。 存储结构：顺序存储结构和链式存储结构 顺序存储结构：利用数据元素在存储器中相对位置之间的某种特定的关系来表示数据元素之间的逻辑关系； 链式存储结构：除数据元素本身外，采用附加的“指针”表示数据元素之间的逻辑关系。 3、了解算法分析的基本方法，掌握算法时间复杂度相关的概念。 算法：是为了解决某类问题而规定的一个有限长的操作序列 或处理问题的策略 一个算法必须满足以下五个重要特性：1．有穷性2．确定性3．可行性4．有输入5．有输出 设计算法时，通常还应考虑满足以下目标： 1.正确性， 2.可读性， 3.健壮性 4.高效率与低存储量需求 基本概念典型例题 一、单项选择题 [例6-1]数据结构用集合的观点可以表示为一个二元组DS＝(D，R)。其中，D是( ①)的有穷集合，R是D上( ②)的有限集合。 ①A.算法B. 数据元素C. 数据操作D. 逻辑结构 ②A. 操作B. 映像C. 存储D．关系 解析：由数据结构的集合形式化定义可知，本题答案为：①B；②D。 [例6-2]数据的常用存储结构中不包括( )。 A．顺序存储结构B．线性结构C．索引存储结构D．散列存储结构 解析：数据通常有四种基本的存储方法，即顺序存储方法、链式存储方法、索引存储 方法和散列存储方法。由此可知，本题答案为：B。 [例6-3] 算法指的是( ①)，它必须具备( ②)这三个特性。 ①A．计算方法B．排序方法C．解决问题的步骤序列D．调度方法 ②A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性 C．确定性、有穷性、稳定性D．易读性、稳定性、安全性 解析：算法是对特定问题求解步骤的一种描述，是由若于条指令组成的有限序列。它 必须满足以下性质：输人性、输出性、有穷性、确定性、无二义性和可行性。由此可知，本 题答案为：①㈠②B。 [例6-4] 在下面的程序段中，对x的赋值语句的执行频度为( )。 for(i=0；i 1．假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。【北京大学1998 三、1 （5分）】 LinkedList Union(LinkedList la,lb) { pa=la->next; pb=lb->next; la->next=null; while(pa!=null && pb!=null) ∥当两链表均不为空时作 if(pa->data<=pb->data) { r=pa->next; pa->next=la->next; ∥将pa结点链于结果表中，同时逆置。 la->next=pa; pa=r; } else {r=pb->next; pb->next=la->next; ∥将pb结点链于结果表中，同时逆置。 la->next=pb; pb=r; } while(pa!=null) ∥将la表的剩余部分链入结果表，并逆置。 {r=pa->next; pa->next=la->next; la->next=pa; pa=r; } while(pb!=null) {r=pb->next; pb->next=la->next; la->next=pb; pb=r; } } 1）设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中ha表中已有的数据若hb中也有,则hb中的数据不归并到ha中,hb的链表在算法中不允许破坏。【南京理工大学1997 四、3（15分）】 LinkedList Union(LinkedList ha, hb)∥ha和hb是两个无头结点的数据域值递增有序的单链 ｛LinkedList 表，本算法将hb中并不出现在ha中的数据合并到ha中，合并中不能破坏hb链表。 la; la=(LinkedList)malloc(sizeof(LNode)); la->next=ha; pa=ha; pb=hb; pre=la; while(pa&&pb) if(pa->data 数据结构与算法基础 一．判断题： 1．数据元素是数据的最小单位。 2．数据结构是带有结构的数据元素的集合。 3．数据结构、数据元素、数据项在计算机中的映像（或表示）分别称为存储结构、结点、数据域。 4．数据项是数据的基本单位。 5．数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要而建立的。 6．数据的物理结构是指数据在计算机内实际的存储形式。 7．算法和程序没有区别，所以在数据结构中二者是通用的。 答案： 1．错误 2．正确 3．正确 4．错误 5．正确 6．正确 7．错误 二． 数据结构是研究数据的 A 和 B 以及它们之间的相互关系，并对这种结构定义相应的 C ，设计出相应的 D ，而确保经过这些运算后所得到的新结构是 E 结构类型。 供选择答案： A、Ｂ：ａ理想结构ｂ抽象结构ｃ物理结构ｄ逻辑结构 Ｃ、Ｄ、Ｅ：ａ运算ｂ算法ｃ结构ｄ规则ｅ现在的ｆ原来的 答案： Ａ：ｃＢ；ｄＣ：ａＤ：ｂＥ：ｆ 三．从供选择的答案中选取正确的答案填在下面叙述中的横线上： 1． A 是描述客观事物的数字、字符以及所能输入到计算机中并被计算机程序加工处理的符号的集合。 2. B 是数据的基本单位,即数据集合中的个体。有时一个 B 由若干个___C____组成，在这种情况下，称 B 为记录。 C 是数据的最小单位。而由记录所组成的线性表为 D 。 3. E 是具有相同特性的数据元素的集合，是数据的子集。 4. Ｆ是带有结构特性数据元素的集合。 5. 被计算机加工的数据元素不是孤立无关的，它们彼此之间一般存在着某种联系。通常将数据元素的这种关系称为Ｇ。 6. 算法的计算量的大小称为计算的Ｈ。 供选择的答案： Ａ－Ｆ：ａ数据元素ｂ符号ｃ记录ｄ文件ｅ数据ｆ数据项ｇ数据对象ｈ关键字ｉ数据结构 考点1 算法的复杂度 【考点精讲】 1．算法的基本概念 计算机算法为计算机解题的过程实际上是在实施某种算法。 算法的基本特征：可行性、确定性、有穷性、拥有足够的情报。 2．算法复杂度 算法复杂度包括时间复杂度和空间复杂度。 名称 描述 时间复杂度 是指执行算法所需要的计算工作量 空间复杂度 是指执行这个算法所需要的内存空间 考点2 逻辑结构和存储结构 【考点精讲】 1．逻辑结构 数据的逻辑结构是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合中的若干关系来表示。数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D；二是D上的关系，它反映了数据元素之间的前后件关系，通常记为R。一个数据结构可以表示成 B=（D，R） 其中B表示数据结构。为了反映D中各数据元素之间的前后件关系，一般用二元组来表示。例如，如果把一年四季看作一个数据结构，则可表示成 B =（D,R） D ={春季，夏季，秋季，冬季} R ={（春季，夏季）,（夏季，秋季），（秋季，冬季）} 2．存储结构 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。 由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同，因此，为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系（即前后件关系），在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。 一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接等存 储结构。 顺序存储方式主要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现。 链式存储结构就是在每个结点中至少包含一个指针域，用指针来体现数据元素之间逻辑上的联系。 考点3 线性结构和非线性结构 【考点精讲】 根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。如果一个非空的数据结构满足下列两个条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 则称该数据结构为线性结构。线性结构又称线性表。在一个线性结构中插入或删除任何一个结点后还应是线性结构。栈、队列、串等都线性结构。 如果一个数据结构不是线性结构，则称之为非线性结构。数组、广义表、树和图等数据结构都是非线性结构。 考点4 栈 【考点精讲】 1．栈的基本概念 栈（stack）是一种特殊的线性表，是限定只在一端进行插入与删除的线性表。在栈中，一端是封闭的，既不允许进行插入元素，也不允许删除元素；另一端是开口的，允许插入和删除元素。通常称插入、删除的这一端为栈顶，另一端为栈底。当表中没有元素时称为空栈。栈顶元素总是后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。 栈是按照“先进后出”或“后进先出”的原则组织数据的。例如，枪械的子弹匣就可以用来形象的表示栈结构。子弹匣的一端是完全封闭的，最后被压入弹匣的子弹总是最先被弹出，而最先被压入的子弹最后才能被弹出。 2．栈的顺序存储及其运算 栈的基本运算有三种：入栈、退栈与读栈顶元素。 （1）入栈运算：入栈运算是指在栈顶位置插入一个新元素。 （2）退栈运算：退栈是指取出栈顶元素并赋给一个指定的变量。 （3）读栈顶元素：读栈顶元素是指将栈顶元素赋给一个指定的变量。 考点5 队列 【考点精讲】 1．队列的基本概念 队列是只允许在一端进行删除，在另一端进行插入的顺序表，通常将允许删除的这一端称为队头，允许插入的这一端称为队尾。 当表中没有元素时称为空队列。 队列的修改是依照先进先出的原则进行的，因此队列也称为先进先出的线性表，或者后进后出的线性表。例如：火车进遂道，最先进遂道的是火车头，最后是火车尾，而火车出遂道的时候也是火车头先出，最后出的是火车尾。若有队列： Q =（q1，q2，…，qn） 那么，q1为队头元素（排头元素），qn为队尾元素。队列中的元素是按照q1，q2，…，qn 的顺序进入的，退出队列也只能按照这个次序依次退出，即只有在q1，q2，…，qn-1 都退队之后，qn才能退出队列。因最先进入队列的元素将最先出队，所以队列具有先进先出的 一、单项选择题（50个） 1. 数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称，而（B）是数据不分割的最小单位。 A．数据元素B．数据项C．数据对象D．数据结构 2.以下数据结构中，（A）是非线性数据结构 A.树 B.字符串 C.队 D.栈 3．在定义ADT时，除数据对象和数据关系外，还需说明（c）。 A．数据元素B．算法C．基本D．数据项 4．算法分析的两个方面是（ C）。 A. 正确性和简明性 B. 可读性和文档性 C. 空间复杂性和时间复杂性 D. 数据复杂性和程序复杂性 5．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（B）。 A．数据具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 6．以下说法正确的是（D）。 A．数据元素是数据的最小单位 B．数据项是数据的基本单位 C．数据结构是带有结构的各个数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7. 在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个结点从小到大排序 8．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（B）。 A．p->next=s;s->next=p->next; B．s->next=p->next;p->next=s; C．p->next=s;p->next=s->next; D．p->next=s->next;p->next=s; 9．线性表L=(a1,a2, ……an)，下列陈述正确的是（D）。 A．每个元素都有一个直接前驱和一个直接后续 B．线性表中至少有一个元素 C．表中诸元素的排列必须是由小到大或由大到小 D．除第一个和最后一个元素外，其余每个元素都有且仅有一个直接前驱和直接后继 算法名称：选择排序 算法定义：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。算法类型：不稳定排序 算法时间复杂度：O(n2)--[n的平方] 最少移动次数：0 最多移动次数：3(n-1) 算法适用场景：这个算法时间复杂度偏高，一般不选择使用。 算法代码： void select_sort(int *x, int n) { int i, j, min, t; for (i=0; i 算法定义：在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。 算法类型：稳定排序 算法时间复杂度：O(n2)--[n的平方] 算法适用场景：这个算法时间复杂度偏高，一般不选择使用。 算法代码： void insert_sort(int *x, int n) { int i, j, t; for (i=1; i 数据结构与算法基础知识总结
力 扣 数 据 结 构 与 算 法
数据结构经典例题
算法与数据结构复习资料
数据结构(C语言)【经典题库】含标准答案
数据结构与算法复习题及参考答案
数据结构经典例题
数据结构与算法知识点必备
数据结构经典算法 C语言版
数据结构与算法设计知识点
数据结构典型例题
数据结构经典算法试题
数据结构与算法基础
全国计算机二级第1章数据结构与算法
算法与数据结构复习重点全
数据结构经典七种排序方法