数据结构课程复习

南京信息工程大学计算机与软件学院《数据结构》课程复习2012.12南京信息工程大学计算机与软件学院南京信息工程大学计算机与软件学院数据结构课程单元及知识模块结构第一单元：基本概念数据结构基本概念算法基本概念特殊线性表广义(线性)表栈队列串数组树和二叉树图线性表第二单元：基本数据结构排序查找第三单元：数据处理南京信息工程大学计算机与软件学院第一章绪论基本要求本章要求掌握数据结构的基本概念和术语、明确学习数据结构的意义。应掌握的基本知识：基本概念（数据、数据元素、数据项、数据对象、数据结构）、数据结构三方面含义，ADT三要素、算法的定义、算法的五个特性、算法评价标准、算法的伪码描述方法、算法时间复杂度分析的基本方法。重点内容：数据结构三方面含义、算法的伪码描述方法、简单算法的时间复杂度分析。南京信息工程大学计算机与软件学院第二章线性表基本要求本章要求理解线性表的逻辑结构和两种存储结构，并能够应用线性表解决实际问题。应掌握的基本知识：线性表的定义及相关概念、ADT描述，顺序表及其运算的实现，线性链表及其运算实现，循环链表和双向链表的存储结构特点，一元多项式的线性链表表示及相加运算实现。重点内容：熟练掌握顺序表和单链表上实现的插入、删除、归并算法及相关的时间复杂度分析。南京信息工程大学计算机与软件学院第三章栈和队列基本要求本章要求掌握栈和队列的逻辑结构定义及在两种存储结构上如何实现栈和队列的基本运算。应掌握的基本知识：栈的定义及特点、顺序栈和链栈的实现、顺序栈运算的实现，栈的简单应用、队列的定义及特点、循环队列和链队列的实现。重点内容：顺序栈及其运算的实现、栈的简单应用。南京信息工程大学计算机与软件学院第四章串基本要求本章要求掌握串的定义、常用串运算、存储表示和基本模式匹配运算。应掌握的基本知识：串的定义、常用串运算、存储表示和基本模式匹配。重点内容：串的常用运算含义、串的顺序存储表示。南京信息工程大学计算机与软件学院第五章数组基本要求本章要求掌握数组的定义、存储表示、对称矩阵和稀疏矩阵的压缩存储。应掌握的基本知识：数组的定义、存储表示、对称矩阵和稀疏矩阵的压缩存储。重点内容：数组的存储表示、对称矩阵和稀疏矩阵的压缩存储。南京信息工程大学计算机与软件学院第六章树和二叉树基本要求本章要求掌握树和二叉树的定义、性质、存储结构、遍历、树和森林与二叉树的转换，赫夫曼树及赫夫曼编码。应掌握的基本知识：二叉树的定义、性质、二叉链表存储表示、二叉树遍历的递归算法、树的定义、存储结构、遍历过程分析、树和森林与二叉树的转换过程分析，赫夫曼树定义、赫夫曼树的构造、赫夫曼算法及赫夫曼编码。重点内容：二叉树的性质、二叉树存储表示、二叉树遍历算法、赫夫曼算法、赫夫曼编码。南京信息工程大学计算机与软件学院第七章图基本要求本章要求掌握图的基本概念及术语、图的存储、遍历及其他相关应用算法。应掌握的基本知识：图的基本概念及术语、图的两种存储结构(邻接矩阵和邻接表)的表示方法，图的两种遍历(深度优先搜索遍历和广度优先搜索遍历)的算法思想与步骤分析；理解最小生成树的概念，能按Prim算法和Kruskal算法构造最小生成树；能运用拓扑排序算法、关键路径求解算法、Dijkstra算法进行有关图运算的分析。重点内容：图的存储表示、图的遍历算法、最小生成树算法、最短路径算法。南京信息工程大学计算机与软件学院第八章查找基本要求本章要求掌握线性表、树和哈希表的查找过程、算法实现以及各种查找方法的时间性能(平均查找长度)分析。应掌握的基本知识：顺序查找、折半查找、分块（索引顺序）查找、二叉排序树及其建立、二叉排序树查找及ASL分析、平衡二叉树（AVL树）概念、AVL树建立过程分析、AVL树的查找及ASL分析、哈希表的概念、哈希表的建立、哈希表查找及ASL分析。重点内容：顺序查找、折半查找、二叉排序树及其建立、二叉排序树查找、AVL树建立过程分析、AVL树的查找及ASL分析、哈希表的建立、哈希表查找及ASL分析。南京信息工程大学计算机与软件学院第九章排序基本要求本章要求掌握内排序方法的基本思想、排序过程、算法实现、时间和空间性能的分析、稳定性分析以及各种排序方法的比较和选择。应掌握的基本知识：排序的定义，排序方法的时间和空间特性、稳定性，直接插入排序、希尔排序（分析其操作过程）、快速排序的基本思想及其递归算法、简单选择排序、堆的定义、堆的整理过程、堆排序、归并排序。重点内容：简单排序算法、快速排序、堆排序和归并排序。绪论掌握概念：逻辑结构、物理结构、运算、算法定义、5个特性、算法描述方法。分析：基本的算法时间复杂度、空间复杂度分析。线性表掌握概念：线性表定义、直接前驱、直接后继、表长、空表、序号、顺序和链接两种存储方式及特点、运算实现。分析：线性表的基本操作（存取、插入、删除、归并）。描述算法：顺序表、线性链表的插入、删除、归并。栈和队列掌握概念：栈和队列定义、栈顶、栈底、队头、队尾、上溢、下溢、栈和队列两种存储方式及特点。分析：栈基本操作(push、pop、getTop)、循环队列操作(入队、出队等)、栈应用：数制转换、括号匹配、表达式计算。描述算法：栈和队列基本运算，栈基本应用算法。串掌握概念：串定义、子串和主串、子串的位置、串相等、串长、模式匹配。分析：串运算(求串长、串比较、串连接、求子串、求子串位置、串替换)。数组掌握概念：数组定义、顺序表示，对称矩阵、三角矩阵、稀疏矩阵的压缩存储。分析：计算数组元素、特殊矩阵元素存储地址。树和二叉树掌握概念：树、二叉树定义，特点，术语，二叉树性质，树、二叉树存储结构，线索二叉树。分析：二叉树、树和森林的遍历，森林与二叉树的转换，哈夫曼树、哈夫曼编码生成，哈夫曼译码。描述算法：描述二叉树遍历算法。图掌握概念：图定义、术语、图的存储结构(邻接矩阵、邻接表)、图的遍历、AOV网和AOE网、拓扑序列、关键路径、关键活动。分析：图的遍历、最小生成树、拓扑排序、求关键活动和关键路径、最短路径。查找掌握概念：查找的定义、查找表、关键字、内查找、外查找、ASL、静态查找、动态查找、散列表、B-树、B+树。分析：顺序查找、二分法查找、分块查找、二叉排序树、AVL树、散列表生成及其查找。描述算法：描述顺序查找、折半查找算法。排序掌握概念：排序的定义、排序码、内排序、外排序、稳定性。分析：直接插入排序、Shell排序、直接选择排序、堆排序、冒泡排序、快速排序、归并排序算法。描述算法：直接插入排序、直接选择排序算法、冒泡排序算法、快速排序南京信息工程大学计算机与软件学院南京信息工程大学计算机与软件学院一、选择题1、队列是插入和删除受限的线性表，其删除操作是在线性表的（1）进行。A．表头B．表尾C．任意位置D．指定位置2、下述哪一条是顺序存储结构的优点？（2）。A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示3、设有一个栈，元素的进栈次序为A,B,C,D,E，下列哪个是不可能的出栈序列（3）。A．A,B,C,D,EB．B,C,D,E,AC．E,A,B,C,DD．E,D,C,B,A4、若二叉树的根结点所在的层次为第1层，则该二叉树的第k层上至多有（4）个结点。A.2k-1B．2kC．2k-1D．2k+1南京信息工程大学计算机与软件学院5、设单链表中指针p指向结点m，若要删除m的后继结点（假设该后继结点存在），则需修改指针的操作为（5）。A．p-next=p-next-next;B．p=p-next;C．p=p-next-next;D．p-next=p;6、下面程序段的时间复杂度为（6）。for(inti=0;im;i++)for(intj=0;jn;j++)a[i][j]=i*j;A．O(m2)B．O(n2)C．O(m+n)D．O(m*n)7、非空的循环单链表head的尾结点指针p满足（7）。A．p==NULLB．p==headC．p-next==headD．p-next==NULL南京信息工程大学计算机与软件学院8、已知二维数组A[0..9,0..9]中，元素a[2][0]的地址为560，每个元素占4个字节，则元素a[1][0]的地址为（8）。A.518B.520C.522D.5249、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为（9）。A．rear％n==frontB．(front+l)％n==rearC．rear％n-1==frontD．(rear+l)％n==front10、假设在一棵二叉树中，度为2的结点数为15，度为1的结点数为10个，则该二叉树的分支总数为（10）个。A.41B.40C.30D.25L(a[2,0]=L(a[0,0])+((2-0)*10*4)∴L(a[0,0])=560-80=480L(a[1,0])=L(a[0,0])+((1-0)*10*4)=480+40=520n2=15,n1=10n0=n2+1=15+1=16N=n0+n1+n2=41∴分支总数=N-n0=41-16=25南京信息工程大学计算机与软件学院二、填空题1.一棵深度为k的完全二叉树（假定根结点所在的层次为第1层），则其结点总数的最小值为（1），最大值为（2）。2．对于一个具有n个结点的单链表（n≥1），在指针变量p指向的结点后插入一个新结点的时间复杂度为（3），在给定值为x的结点后插入一个新结点的时间复杂度为（4）。3.设有一空栈，现有输入序列A，B，C，D，E，经过push,push,pop,push,pop,push,push后，此时的输出序列为（5）。4.有一个100*90整型数据的稀疏矩阵，非0元素有10个，设每个整型数据占2字节，则用三元组表示该矩阵时，所需的字节数是（6）。2k-12k-1O(1)O(n)BC64南京信息工程大学计算机与软件学院5.设栈S和队列Q初始为空。6个元素依a,b,c,d,e,f的顺序通过栈S，一个元素出栈后立即进入队列Q。若这6个元素出队的序列为d,c,b,f,e,a，则栈S的最小容量需（7）。6.若对n阶对称矩阵A[0..n-1,0..n-1]以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij（i≤j）的位置k的关系为（8）。7.表达式a+((b*c-d)/e+f*g/h)+x/y对应的后缀表达式是（9）。8.若INDEX（S，T）表示求T在S中的位置的操作，则对于S=Beijing＆Nanjing，T=jing，INDEX（S，T）=（10）。4j*(j+1)/2+iabcdabc*d-e/fg*h/++xy/+4南京信息工程大学计算机与软件学院三、判断题1．二叉树结构中，任何一个结点都有一个且仅有一个直接前驱和直接后继。............()2．在一棵二叉树中，假定每个结点只有左孩子，没有右孩子，对它分别进行中序遍历和后序遍历，则具有相同的结果。.............()3.对线性链表来说，从任意结点开始均能扫描表中全部结点。.............()4.线性表的特点是每个元素都有一个前驱和一个后继。.............()5.栈和队列都是限制存取点的线性结构。.............()×√××√南京信息工程大学计算机与软件学院四、简答题1．已知一棵二叉树如下，请分别写出按前序、中序、后序遍历时得到的字符序列。前序：ABDEGHJCFI中序：DBGEJHACIF后序：DGJHEBIFCA南京信息工程大学计算机与软件学院2．设x，n为整型变量，且n0，下面程序片段中语句x/=2执行次数的数量级是多少？试进行分析。用“O”记号表示。x=n*n;while(x=1)x/=2;设当x=1时，循环执行了k次，则必有：=〉=〉=〉所以，x/=2执行次数的数量级是21*12kxn22kn22lognk22lognk2(log)nO南京信息工程大学计算机与软件学院3．用栈实现将中缀表达式：