数据结构作业4

数据结构复习题1．数据结构在计算机中的表示称为数据的（）存储结构B）抽象结构）顺序结构）逻辑结构2．对于下面程序段的时间复杂度为（for(i=1;i<=n;i++)for(j=1;j<=i;j++)x=x+1;）O(n)B）O(n)C）O(n*i)）O(n+i)3．数据结构是（）相互之间存在一种或多种特定关系的数据元素的集合）相互之间存在一种特定关系的数据元素的集合）数据元素的集合4．数据结构可形式地定义为(D,S)，其中S是D上（）操作B）存储映像C）关系）前面都不正确）的有限集。）数据元素5．数据结构在计算机中存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为（）逻辑结构B）顺序存储结构）链式存储结构）以上都对6．如一个结构中的数据元素之间存在一个对多个的关系，则此结构为（）集合结构B）线性结构C）树形结构）图状结构7．在数据类型中，值不可分解的类型为（）原子类型B）结构类型C）固定聚合类型）可变聚合类型8．下面程序段的时间复杂度为（for(i=n;i>=1;i--)for(j=1;j<=i;j++)x=x+1;）O(n)B）O(n2)）O(n*i)）O(n+i)9．数据类型为（）数据项的集合B）值的集合及定义在其上的一组操作的总称）关键字的集合）数据元素的集合10．网状结构的特征是（）结构中数据元素之间只存在“同属于一个集合”的关系）结构中数据元素之间存在一个对应一个的关系）结构中数据元素之间存在一个对应多个的关系）结构中数据元素之间存在多个对应多个的关系．设计一个“好”的算法应达到的目标为（）正确性、可读性、健壮性及效率与低存储量需求）正确性、可读性、健壮性及有穷性）正确性、可读性、健壮性及可行性）正确性、可读性、健壮性及确定性13．线性链表中各链结点之间的地址（）必须连续）部分地址必须连续C）不一定连续）连续与否无所谓14．如某链表中最常用的操作是在最后一个结点后插入一个结点和删除最后一个结点，则（）存储方式最节省运行时间。）单链表）带头结点的单链表）单循环链表D）带头结点的双循环链表15．在非空线性链表中由p所指的链结点后面插入一个由q所指的链结点的过程是依次执行动作（）q->next=p;p->next=q;）q->next=p->next;p=q;B）q->next=p->next;p->next=q）p->next=q;q->next=p;16．线性表的顺序存储结构具有的特点是（）可直接随机访问任一元素）不必事先估计元素个数B）插入删除不需要移动元素）所需空间与线性表长度成正比17．线性表的静态存储结构与顺序存储结构相比，优点是（）所有的操作算法实现简单）便于插入和删除B）便于随机存取）便于利用零散的存储器空间19．将如下图所示的s所指结点加到p所指结点之后，其语句应为（nextpsnext）s->next=p+1;p->next=sB）(*p).next=s;(*s).next=(*p).next）s->next=p->next;p->next=s）s->next=p->next;p->next=s->next20．在单链表中，如要删除p所指结点，则执行如下操作：q=p->next;p->data=q->data;p->next=deleteq;）q;）p->next->next）q->next->nextD）前面都不正确21．将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（）n22．设la是带表头的单向循环链表的头指针，此表为空的条件是（）la==NULLB）la->next==NULL）la->next==la）n==023．在下面给出的链式存储结构中，能在O(1)时间内完成在指定结点p之前插入元素x的结构是为（）单向链表）单向循环链表）带表头的单向链表D）双向循环链表B）2n-1C）2n）n-124．用链表表示线性表的优点是（）便于随机存取B）便于插入删除操作）元素的物理顺序与逻辑顺序相同）花费的存储空间较顺序存储少25．在一长度为n的顺序表中，向第i个元素（≤i≤）之前插入一新元素时，需向后移到（）n-i）个元素。B）n-i+1）n-i-1）i26．从一个具有头结点的单链表中查找数据元素值为x的结点时，在查找成功的情况下，平均比较次数是（）nB）n/227．对于长度为n的顺序线性表进行删除元素操作，如删除每个元素的概率相同，则删除一个元素移动元素的平均次数是（）n/2B）(n-1)/2）(n+1)/2）(n-1)/2）(n+1)/2）Dn28．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的平均时间复杂度为（）O(0)B）O(1)）O(n)）O(n)29．用单链表表示的链式队列的队头在链表的（）链头B）链尾C）链中）位置。）任意30．栈应用的典型事例是（）排队）查找）归并）用“算符优先法”进行表达式求值31．若用单链表来表示队列，则应该选用（）带尾指针的非循环链表）带尾指针的循环链表）带头指针的循环链表）带头指针的非循环链表32．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，这样主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区应该是一个（）堆栈B）队列）结构。）数组）线性表33．设一个栈的入栈序列是ABCD，则借助于一个栈所得到的出栈序列不可能是（）ABCDB）DCBA）ACDB）DABC34）1、2、、4、、6）3、4、、1、、6B）2、1、、4、、6）4、3、、1、、635．设栈的输入序列是2n，若输出序列的第一个元素是n，则第i个输出元素是（）n-i+139:fedba以后，连续进行了3次删除操作，此时的栈顶元素是（）cB）d43．设某二叉树前序为abdcef，中序为dbaecf，则此二叉树的后序为(）dbefcaB）debfca）dfebca）dbfecaB）i）n-i）b）e)。441）2n+2B）2n+1）2n）2n-145．设二叉树中有n个度为2的结点，n个度为1n个叶子结点，则此二210叉树中空指针域个数为（）n+n+nB）n+n+2n）2n+n）2n+n012210210146．用权值分别为15，4，5的四个结点，构造出的哈夫曼树为（6）50B）60）52）6548．、B两个结点可以构成（）棵不等价的二叉树。）2B）3）4）549．设哈夫曼树的叶结点数为n，则它的结点总数为（）2n-1B）2n）2n+1）不确定50．采用邻接表存储的图按深度优先搜索方法进行遍历的算法类似于二叉树的（）先序遍历B）中序遍历）后序遍历）层次遍历51．在如下图所示的AOE网中，关键路径长度为（）16B）13）10）952．在如图6-7所示的AOE网中，关键路径长为（）18B）16）19）853．对于具有n个顶点的强连图，其弧条数的最小值为（）n+1B）n）n-1）n-254．具有n个顶点的无向图，它可能具有的边的条数的最大值为（）(n+n)/2B）n2）(n-n)/2）n2201055．对于有向图的邻接矩阵101，该图共有（）条弧。A010）5B）4）3）256．G是一个非连通无向图，共有28条边，则该图至少有（）6B）7）8）9）个顶点。57．一个n个顶点的连通无向图，其边的个数至少为（）n-1B）n）n+1）nlogn87．哈夫曼树是（）满二叉树B）二叉排序树）带权路径长度最短的二叉树）树的路径长度最短的二叉树88．对于如下图所示的二叉树，后序遍历结果序列为（），，，，E，，，H），F，，，C，，E，H），，D，F，，，，H），F，，B，，，，A89．与树的后根序遍历相应的树的二叉树表示的遍历是（）先序遍历B）中序遍历）后序遍历）按层遍历90．对于如下图所示的二叉树，后序遍历结果序列为（），，，，E，，G），F，，，C，，EB），，，F，C，，G）F，，，，E，，A91．已知某二叉树前序遍历序列为ABDCE，它可能的中序遍历序列为（）BDAECB）BCADE）CBADE）BEACD92．具有127个结点的完全二叉树其深度为（）8B）7）6）5930i）2iB）2-1）2+1）iii94．二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK中序遍历：HFIEJKG该二叉树根的右子树的根是（）EB）F）G）H95．树结构最适合用来表示（）元素间具有分支层次关系的数据B）无序数据）元素间没有关联的数据）有序数据96．中序遍历与后序遍历所得序列完全相同的二叉树一定是（）空二叉树或所有右孩子域都为空B）所有左孩子域都为空）前面都不正确）所有右孩子域都为空97C则遍历方式为（）中序遍历B）先序遍历）后序遍历）层次遍历98．如以顺序表示存储二叉树，每个结点占用一个存储单元，则深度为K的单左枝二叉树共浪费（）2-K）个存储单元。B）2-K-1）2-K-1）2-K+1KK99．将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为，则编号为49的结点的左孩子编号为（）98B）99）50）48100．树中用一个分支把两个结点连结起来（）不一定出现环）一定出现环）前面都不正确）使树的度数增加1101．设有如图所示的逻辑结构图，试给出数据结构形式。【102．有如下数据结构的形式定义，试画出此结构的图形表示。DS={D,S}，其中，D={1,2,3,4}S=={R}R={<1,2>,<1,3>,<2,3>,<2,4>,<3,4>}105．下面程序段用于求两个n*n矩阵相乘的算法，试求其时间复杂度。for(i=0;i<n;i++)for(j=0;j<n;j++){c[i][j]=0;for(k=0;k<n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];}107．试给出以下算法的时间复杂度。voidsort(inta[],intb[],inti,intn)/*对数组a进行升序排序，并将排序结果存入数组b中i为待排序序列下标的下界，n为待排序序列下标的上界*/{intj,k,tem;if(i==n)b[n]=a[n];//语句1//语句2else{j=n;for(k=i;k<n;k++)if(a[j]<a[k])j=k;if(j!=n){//语句3tem=a[j];a[j]=a[n];a[n]=tem;}b[n]=a[n];//语句4//语句5sort(a,b,i,n-1);}}．设有多项式f(x)=2-3x+6x，试用线性链表表示。49q所指的结点后面插入p所指的结点的过程已经依次进行了以下3步：第1步p->prior=q;第2步p->next=q->next;第3步q->next=p;第4步应是什么动作？（写出该动作对应的语句）（北方名校经典试题）1）写出在双向链表中，在指针p所指结点前面插入一个s所指结点的语句序列。（2）写出带头结点的双向循环链表L为空表的条件。．已知结点指针pq分别表示双链表中任意两个相邻结点（即p->next==q且q->prior==pq所指结点的程序段。．对链表设置表头结点的作用是什么？．线性表有两种存储结构：一是顺序表，二是链表。试问：（1n线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存取结构？为什么？（西部名校经典试题）．在单链表和双向链表中，能否从当前结点出发访问到任一结点？．链表所表示的元素是否是有序的？如果有序，则有序性体现在何处？链表所表示的元素是否一定要在物理上是相邻的？有序表的有序性又如何理解？121．要借助栈由输入序列是输入1,2,3,„,n得到的输出序列为p,p,p,„,p(此输出123n序列是输入序列经过栈操作后的某个排列)，则在输出序列中不可能出现当i<j<k时有p<p<p的情况。jki122．有5个元素，其入栈次序为：、、、、E，在各种可能的出栈次序中，以元素C第一个出栈，D第二个出栈的次序有哪几个？124．循环队列用数组存放其数据元素。设tailfront指向其实际队首的前一个位置，则当前队列中的数据元素有多少个？如何进行队空和队满的判断？127．已知一个栈S的输入序列为abcd，下面两个序列能否通过栈的Push和Pop操作输出；如果能，请写出操作序列；如果不能，清说明原因。（1）dbca（2）cbda152.已知某一完全k叉树只有度为k的结点及叶结点，设叶结点数为n，试求它的0树高h。153.设有表达式：a*(b-c)/d+f/(g+h*i)，试给出此表达式的下面结果：①二叉树表示；②逆波兰式表示；③中缀表示。154．一棵非空的有向树中恰有一个顶点入度为，其他顶点入度为。但一个恰有一个顶点入度为0、其他顶点入度为1的有向图却不一定是一棵有向树。请举例说明之。（北方名校经典试题）155ABCEFGHDABFHGEDC；请画出此二叉树。156．假设先根次序遍历某棵树的结点次序为SACEFBDGHIJK，后根次序遍历该树的结点次序为CFEABHGIKJDS，要求画出这棵树。157S中共有8分别出现2145734次和9次，对该字符串用｛0，1｝进行前缀编码，问该字符串的编码至少有多少位？15819710个词的英文行中出现最普遍的15个词的出现频度。词A频度2log265（1bitbit计的平均长度是多少？2（2均长度是多少？159．已知下列字符AEFG的权值分别为312748，试求对应哈夫曼树HT。160．已知一棵度为m的树中有N个度为1的结点，N个度为2的结点，„，N12m个度为m的结点。试问该树中有多少个叶子结点？163其叶结点的相对次序不发生改变。164n2(n。00165．已知如图所示的二叉树是由某森林转换而来，画出其原来的森林。171．设有带权无向图G如图所示：试给出：（1）G的邻接矩阵表示；（2）从V开始的深度优先遍历；1（3）从V开始的广度优先遍历；1（4）从V开始执行的普里姆（）算法过程中所选边的序列。1172．对如图6-10所示的有向图G试给出：（1）各顶点的入/出度；（2）逆邻接表；（3）强连通分量。174．给出如图所示的所有拓扑有序序列。175．用Kruskal算法分别构造如下所示网络的最小生成树。176．如图所示，用Prim算法从结点1出发构造出一棵最小生成树，要求图示出每一步的变化情况。177．如图所示，从顶点d出发分别按深度优先搜索与广度优先搜索方法进行遍历，写出相应的顶点序列。193．简述栈与队列的异同。194．试说明用栈求表达式值的基本思想。195．栈的定义及特性。196．试列举出数据结构栈的至少五种基本操作。197．栈的特点是什么？试举出栈的两个应用实例。198.用一维数组sq[0:m-1]tag来区分尾指针（rear）和头指针（front）相等时队列的状态是空还是满？199．何谓顺序队列的上溢现象？有哪些解决方法？数据结构复习大纲数据结构与算法分析是计算机科学与技术专业统设的一门重要的必修专业基础课，它主要研究数据的各种逻辑结构和在计算机中的存储结构，还研究对数据进行的插入、查找、删除、排序、遍历等基本运算或操作以及这些运算在各种存储结构上具体实现的算法。由于本课程的主教材采用语言描述算法，期末卷面考试也采用语言描述，因而要求在做平时作业和上机实验操作时用VisualC++或C++Builder或Borland第一章绪论重点掌握的内容：1.数据结构的二元组表示，对应的图形表示，序偶和边之间的对应关系。2.集合结构、线性结构、树结构和图结构的特点。3.抽象数据类型的定义和表示方法。4.一维和二维数组中元素的按下标和按地址的访问方式以及相互转换，元素地址和数组地址的计算，元素占用存储空间大小和数组占用存储空间大小的计算。5.普通函数重载和操作符函数重载的含义，定义格式和调用格式。6.函数定义中值参数和引用参数的说明格式及作用，函数被调用执行时对传送来的实际参数的影响。7.算法的时间复杂度和空间复杂度的概念，计算方法，数量级表示。8.一个简单算法的最好、最差和平均这三种情况的时间复杂度的计算。对于本章的其余内容均作一般掌握。第二章线性表重点掌握的内容：1.线性表的定义及判别和抽象数据类型的描述，线性表中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。2.线性表的顺序存储结构的类型定义，即List类型的定义和每个域的定义及作用。3.线性表的每一种运算在顺序存储结构上实现的算法，及相应的时间复杂度。4.链接存储的概念，线性表的单链接和双链接存储的结构，向单链表中一个结点之后插入新结点或从单链表中删除一个结点的后继结点的指针链接过程。5.单链表中结点的结构，每个域的定义及作用，即LNode类型的定义及结构。6.带表头附加结点的链表、循环链表、双向链表的结构特点。7.线性表的每一种运算在单链表上实现的算法及相应的时间复杂度。8.在顺序存储或链接存储的线性表上实现指定功能的算法的分析和设计。9Josephus问题的求解过程。10．顺序表和线性链表的性能比较及各自使用背景。对于本章的其余内容均作一般掌握。第四章栈和队列重点掌握的内容：1.栈的定义和抽象数据类型的描述，栈中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。2.栈的顺序存储结构的类型定义，即Stack类型的定义和每个域的定义及作用。3．栈的每一种运算在顺序存储结构上实现的算法，及相应的时间复杂度。4.栈的每一种运算在链接存储结构上实现的算法及相应的时间复杂度。5.算术表达式的中缀表示和后缀表示，以及相互转换的规则，后缀表达式求值的方法。6n个栈元素,出栈可能或不可能的序列数。7.队列的定义和抽象数据类型的描述，队列中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。8.队列的顺序存储结构的类型定义，即Queue类型的定义和每个域的定义及作用。9.队列的每一种运算在顺序存储结构上实现的算法及相应的时间复杂度。10.利用栈和队列解决简单问题的算法分析和设计。11．双端队的概念及可能出队序列。12．队和栈的应用背景，如cpu队、进程队、打印机队。13．链队的各种存储表示。一般掌握的内容：1.后缀表达式求值的算法，把中缀表达式转换为后缀表达式的算法。2.队列的链接存储结构，以及实现每一种队列运算的算法和相应的时间复杂度。对于本章的其余内容均作一般了解。第六章树和二叉树重点掌握的内容：1.树和二叉树的定义，对于一棵具体树和二叉树的二元组表示及广义表表示。2.树和二叉树的概念，如结点的度、树的度、树叶、分枝结点、树的层数、树的深度等。3．不同结点数的树和二叉树的形态。4.树和二叉树的性质，如已知