数据结构(同名10800).doc

《数据结构(同名10800).doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、《数据结构》综合复习资料一、填空题1.数据结构是（）。2.堆栈的特点是（），队列的特点是（），字符串中的数据元素为（）。3.列举三种树的存储方式（）、（）和（）。4.哈希表查找技术的性能取决于三个因素，它们是（）、（）和（）。5.ADT称为抽象数据类型，它是指（）。6.求下列程序的时间复杂度，并用大O表示方法表示（）。for(i=1;i<=n;++i)for(j=1;j<=i;++j){++x;a[i][j]=x;}7.用堆栈求中缀表达式a+b*c/d+e*f的后缀表达式，求出的后缀表达式为（）。8.含零个字符的串称为（）串，用Æ表示。其他串称为（

2、）串。任何串中所含字符的个数称为该串的（）。9.设有字母序列{Q,D,F,X,A,P,N,B,,Y,M,C,W}，请写出按2路归并排序方法对该序列进行一趟排序后的结果（）。10.数据的逻辑结构被分为（）、（）、（）和（）四种。11.算法设计的评价标准为（）、（）、（）、（）。12.在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为　　（），若假定p为一个数组a中的下标，则其后继结点的下标为（）。13.（）通常称作串的模式匹配。在一个主串中查找子串是否存在，存在返回（）；不存在返回()。14.在一棵二叉树中，第5层上的结点数最

3、多为（）；在一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为（）个。15.对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵、邻接表表示时，求任一顶点度数的时间复杂度依次为（）、（）。16.给出一组关键字序列{29，18，25，47，58，12，15，10}，增量为4的希尔（SHELL）排序结果为（）。17.数据结构的四种基本形式为集合、（）、（）和（）。18.线性表的常见链式存储结构有（）、（）和（）。19.设T是一个m*n阶矩阵，T按列序存储在一组连续的存储单元中，每个元素占用w个存储单元，若T[1,1]的存储地址

4、为base，则T[i,j]的存储地址为（）。20.在邻接表上，无向图中顶点vi的度恰为（）。对有向图，顶点vi的出度是（）。为了求入度，必须遍历整个邻接表，在所有单链表中，其邻接点域的值为（）的结点的个数是顶点vi的入度。第15页共15页21.一般情况下，当待排序序列关键字是随机情况时，快速分类是所有数量级（）的排序方法中最好的。对快速排序来讲，其最好情况下的时间复杂度是（），其最坏情况下的时间复杂度是（）。22.以下为冒泡排序的算法。请分析算法，并在____上填充适当的语句。voidbulbblesort(intn,listr){inti,j,f

5、lag;/*flag为特征位*/for(i=1;i<=n;i++){_______;for(j=1;_;j++)if(r[j+1].key

6、表D、单循环链表3、以下说法错误的是（）。A、对循环链表来说，从表中任一结点出发都能通过前后操作而扫描整个循环链表。B、对单链表来说，只有从头结点开始才能扫描表中全部结点。C、双链表的特点是找结点的前趋和后继都很容易。D、对双链表来说，某个结点的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针域中。4、一个堆栈的入栈序列为abcde，若出栈和入栈操作可间隔进行，则出栈序列不可能的为（）。A、edcbaB、decbaC、decabD、abcde5、设定树根的层次为1，则有64个结点的完全二叉树的深度为（）。第15页共15页A、

7、8B、7C、6D、56、在二叉树的先序遍历，中序遍历和后序遍历算法中，所有叶子结点的先后顺序（）。A、都不相同B、前序遍历和中序遍历相同，而与后序遍历不同C、完全相同D、前序遍历和后序遍历相同，而与中序遍历不同7、关于逻辑结构和存储结构，正确的描述是（）。A、线性数据结构必须采用链式存储结构B、一种逻辑结构，可以用不同的存储结构来存储，反之亦然C、一种逻辑结构，可以用不同的存储结构来存储，反之不然D、一种存储结构只能表示一种逻辑结构8、关于链表的特点描述不正确的是（）。A、存储空间不一定连续；B、元素之间的后继关系是由指针来体现的；C、逻辑上相邻，

8、物理上不一定相邻；D、随机存取（顺序存取），即访问任何一个元素的时间相同。9、树最适合用来表示（）。A、元素之间具有分支层