数据结构(本科)期末综合练习二(填空与判断题)

...wd......wd......wd...数据构造〔本科〕期末综合练习二〔填空与判断题〕填空题1.数据是__信息__的载体，它能够被计算机程序识别、存储和加工处理。2.数据构造包括逻辑构造、__存储构造__和数据的运算三个方面。3.数据构造的逻辑构造包括线性构造和__非线性__构造两大类。4.数据构造的存储构造包括顺序、__链接___、索引和散列等四种。5.基本数据类型是计算机已经实现了的_数据构造__。6.抽象数据类型的特点是__数据封装__、信息隐蔽、使用与实现别离。7.算法的一个特性是__有穷性__，即算法必须执行有限步就完毕。8.面向对象的特征应包括对象、类、__继承__、消息通信。9.属性与服务一样的对象构成类，类中的每个对象称为该类的__实例__。10.对象的私有状态只能通过该对象的__操作〔或服务〕_才能改变。11.模板类是一种数据抽象，它把__数据类型_当作参数，可以实现类的复用。12.在类的继承构造中，位于上层的类叫做基类，其下层的类那么叫做__派生〔或子〕__类。13.一维数组所占用的空间是连续的。但数组元素不一定顺序存取，通常是按元素的__下标〔或顺序号〕__存取的。14.在程序运行过程中不能扩大的数组是__静态__分配的数组。这种数组在声明它时必须指定它的大小。15.在程序运行过程中可以扩大的数组是__动态___分配的数组。这种数组在声明它时需要使用数组指针。16.二维数组是一种非线性构造，其中的每一个数组元素最多有__两个__个直接前驱〔或直接后继〕。17.假设设一个nn的矩阵A的开场存储地址LOC(0,0)及元素所占存储单元数d，按行存储时其任意一个矩阵元素a[i][j]的存储地址为__LOC(0,0)+(i*n+j)*d__。18.对称矩阵的行数与列数__相等_且以主对角线为对称轴，aij=aji，因此只存储它的上三角局部或下三角局部即可。19.将一个n阶对称矩阵的上三角局部或下三角局部压缩存放于一个一维数组中，那么一维数组需要存储__n(n+1)/2_个矩阵元素。20.将一个n阶对称矩阵A的上三角局部按行压缩存放于一个一维数组B中，A[0][0]存放于B[0]中，那么A[I][J]在I≤J时将存放于数组B的__(2n-I-1)*I/2+J__位置。21.利用三元组表存放稀疏矩阵中的非零元素，那么在三元组表中每个三元组元素对应一个非零元素的行号、列号和__值__。22.线性表是由n〔n≥0〕个__数据元素__组成的有限序列。23.假设设串S=“documentHash.doc\0〞，那么该字符串S的长度为___16____。24.链表是一种采用链式〔或链接〕存储构造存储的线性表。25.链表只适用于顺序查找。26.在链表中进展插入和删除操作的效率比在顺序存储构造中进展一样操作的效率高。27.链表对于数据元素的插入和删除不需要移动结点，只需要改变相应结点的__指针域_的值。28.链接存储表示的结点存储空间一般在程序的运行过程中进展动态地__分配__和释放。29.单链表中逻辑上相邻的结点而在物理位置上_不一定_相邻。30.在单链表中,除了表头结点外,任意结点的存储位置由其直接_前驱_结点的指针域的值所指示。31.在单链表设置表头结点的作用是插入和删除表中第一个元素时不必对__表头指针_进展特殊处理。32.假设设L是指向带表头的单链表,语句L->link=L->link->link的作用是__删除_单链表中的第一个结点。33.在双向链表中,每个结点除了数据域外,还有两个指针域,它们分别指向__前趋结点和后继结点__。34.线性表的链接存储只能通过_链接指针_顺序访问。35.链表与顺序表、索引表、散列表等都是数据逻辑构造的__存储__表示。36.设双向循环链表每个结点构造为(data,llink,rlink),那么结点*p的前驱结点的地址为__p->llink__。37.栈是一种限定在表的一端进展插入和删除的线性表，又被称为__后出先进__表。38.队列是一种限定在表的一端插入，在另一端删除的线性表，它又被称为__先进先出__表。39.向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给新结点的指针域，然后把新结点的存储位置赋给__栈顶指针__。40.队列的删除操作在_队头〔或队首〕_进展。41.向一个顺序栈插入一个元素时，首先使__栈顶指针_后移一个位置，然后把待插入元素写入到这个位置上。42.假设设顺序栈的最大容量为MaxSize，top==-1表示栈空，那么判断栈满的条件是__top==MaxSize-1__。43.当用长度为MaxSize的数组顺序存储一个栈时，假设用top==MaxSize表示栈空，那么表示栈满的条件为__top==0__。44.向一个循环队列中插入元素时，需要首先移动__队尾__指针，然后再向所指位置写入新元素。45.向一个栈顶指针为top的链式栈中插入一个新结点*p时，应执行__p->link=top_和top=p操作。46.在一个链式队列中，假设队头指针与队尾指针的值一样，那么表示该队列至多有__1__个结点。47.在一个链式队列中，假设队头指针与队尾指针的值一样，那么表示该队列至多有___一__个结点。48.如果一个对象局部地包含自己，或自己定义自己，那么称这个对象是__递归_的对象。49.如果一个过程直接或间接地调用自己，那么称这个过程是一个__递归_的过程。50.递归工作栈起到两个作用，其一是将递归调用时的实际参数和返回地址传递给下一层递归；其二是保存本层的形式参数和_局部变量_。51.函数内部的局部变量是在进入函数过程后才分配存储空间，在函数过程执行完毕后就__释放___局部变量所占用的存储空间。52.迷宫问题是一个回溯控制的问题，最好使用__递归___的方法来解决。53.非空广义表的除第一个元素外其他元素组成的表称为广义表的__表尾__。54.广义表A((a,b,c),(d,e,f))的表尾为_((d,e,f))_。55.广义表是一种递归的数据构造，子表结点那么指示下一层广义表的__表头结点__。56.广义表的深度定义为广义表括号的__重数__。57.对于一棵具有n个结点的树，该树中所有结点的度数之和为_n-1_。58.一棵树的广义表表示为a(b(c,d(e,f),g(h)),i(j,k(x,y)))，结点k的所有祖先的结点数为___2__个。59.一棵树的广义表表示为a(b(c,d(e,f),g(h)),i(j,k(x,y)))，结点f的层数为___3___。假定树根结点的层数为0。60.假定一棵三叉树〔即度为3的树〕的结点个数为50，那么它的最小高度为__4_。假定树根结点的深度为0。61.在一棵高度为3的四叉树中，最多含有__85__个结点，假定树根结点的高度为0。62.在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度为0的结点数有__6__个。63.一棵高度为5的完全二叉树中，最多包含有__63__个结点。假定树根结点的高度为0。64.假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)))，那么该树的高度为__3__。假定树根结点的高度为0。65.在一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，那么叶子结点数为_6_个。66.假定一棵二叉树的结点数为18，那么它的最小高度为__4__。假定树根结点的高度为0。67.在一棵高度为h的理想平衡二叉树中，最少含有__2h__个结点。假定树根结点的高度为0。68.在一棵高度为h的理想平衡二叉树中，最多含有__2h+1-1_个结点。假定树根结点的高度为0。69.假设将一棵树A(B(C,D,E),F(G(H),I))按照左子女-右兄弟表示法转换为二叉树，该二叉树中度为2的结点的个数为__2__个。70.将一棵树按照左子女-右兄弟表示法转换成对应的二叉树，那么该二叉树中树根结点肯定没有__右__子女。71.在一个堆的顺序存储中，假设一个元素的下标为i(0≤i≤n-1)，那么它的左子女元素的下标为__2i+1_。72.在一个堆的顺序存储中，假设一个元素的下标为i(0≤i≤n-1)，那么它的右子女元素的下标为__2i+2__。73.在一个最小堆中，堆顶结点的值是所有结点中的__最小值_。74.在一个最大堆中，堆顶结点的值是所有结点中的_最大值_。75.以顺序搜索方法从长度为n的顺序表或单链表中搜索一个元素的渐进时间复杂度为__O(n)_。76.对长度为n的搜索表进展搜索时，假定搜索第i个元素的概率为pi,搜索长度〔即在搜索过程中依次同有关元素比较的总次数〕为ci，那么在搜索成功情况下的平均搜索长度的计算公式为____。77.假定一个顺序表的长度为40，并假定顺序搜索每个元素的概率都一样，那么在搜索成功情况下的平均搜索长度为_20.5_。78.从有序表(12,18,30,43,56,78,82,95)中折半搜索元素56时，其搜索长度为__3__。79.假定对长度n=50的有序表进展折半搜索，那么对应的判定树中最底下一层的结点数为__19__个。80.从一棵二叉搜索树中搜索一个元素时，假设给定值大于根结点的值，那么需要向_右子树_继续搜索。81.向一棵二叉搜索树中插入一个元素时，假设元素的值小于根结点的值，那么应把它插入到根结点的_左子树_上。82.根据n个元素建设一棵二叉搜索树的渐进时间复杂度大致为__O(nlog2n)__。83.在一棵AVL树中，每个结点的左子树高度与右子树高度之差的绝对值不超过__1___。84.根据一组记录(56,42,50,64,48)依次插入结点生成一棵AVL树时，当插入到值为_50_的结点时需要进展旋转调整。85.根据一组记录(56,74,63,64,48)依次插入结点生成一棵AVL树时，当插入到值为63的结点时需要进展__先右后左双旋转_调整。86.根据一组记录(56,42,38,64,48)依次插入结点生成一棵AVL树时，当插入到值为38的结点时需要进展_右单旋转_调整。87.根据一组记录(56,42,73,50,64,48,22)依次插入结点生成一棵AVL树时，当插入到值为__64_的结点时才出现不平衡，需要进展旋转调整。88.在一棵具有n个结点的AVL树上进展插入或删除元素的渐进时间复杂度大致为_O(log2n)_。89.n(n﹥0)个顶点的连通无向图各顶点的度之和最少为__2(n-1)__。90.用邻接矩阵存储图，占用的存储空间与图中的_顶点_数有关。91.设图G=(V,E)，V={V0,V1,V2,V3},E={(V0,V1),(V0,V2),(V0,V3),(V1,V3)}，那么从顶点V0开场的图G的不同深度优先序列有__4__种。92.设图G=(V,E)，V={1,2,3,4},E={<1,2>,<1,3>,<2,4>,<3,4>}，从顶点1出发，对图G进展广度优先搜索的序列有__2__种。93.n(n﹥0)个顶点的无向图中顶点的度的最大值为__n-1_。94.在重连通图中每个顶点的度至少为__2__。95.n个顶点的连通无向图的生成树含有__n-1__条边。96.11个顶点的连通网络N有10条边，其中权值为1,2,3,4,5的边各2条，那么网络N的最小生成树各边的权值之和为__30__。97.在使用Kruskal算法构造连通网络的最小生成树时，只有当一条候选边的两个端点不在同一个_连通分量_上，才会被参加到生成树中。98.一般来说,深度优先生成树的高度比广度优先生成树的高度要__高__。99.求解带权连通图最小生成树的Prim算法使用图的__邻接矩阵_作为存储构造。100.设图的顶点数为n，那么求解最短路径的Dijkstra算法的时间复杂度为_O(n2)__。101.第i(i=1,2,…,n-1)趟从参加排序的序列中取出第i个元素，把它插入到由第0个至第i-1个元素组成的有序表中适当的位置，此种排序方法叫做_直接插入_排序。102.第i(i=0,1,...,n-2)趟从参加排序的序列中第i个至第n-1个元素中挑选出一个最小元素，把它交换到第i个位置，此种排序方法叫做_直接选择_排序。103.每次直接或通过基准元素间接比较两个元素，假设出现逆序排列就交换它们的位置，这种排序方法叫做__交换_排序。104.每次使两个相邻的有序表合并成一个有序表，这种排序方法叫做__二路归并__排序。105.在直接选择排序中，记录比较次数的时间复杂度为__O(n2)__。106.在直接选择排序中，记录移动次数的时间复杂度为___O(n)__。107.在堆排序中，对n个记录建设初始堆需要调用__n/2__次调整算法。108.在堆排序中，如果n个对象的初始堆已经建好，那么到排序完毕，还需要从堆顶结点出发调用__n-1_次调整算法。109.在堆排序中，对任意一个分支结点进展调整运算的时间复杂度为__O(log2n)__。110.对n个数据对象进展堆排序，总的时间复杂度为___O(nlog2n)___。111.给定一组数据对象的关键码为{46,79,56,38,40,84}，那么利用堆排序方法建设的初始堆〔最大堆〕为__84，79，56，38，40，46__。112.快速排序在平均情况下的时间复杂度为_O(nlog2n)_。113.快速排序在最坏情况下的时间复杂度为___O(n2)__。114.快速排序在平均情况下的空间复杂度为___O(log2n)___。115.快速排序在最坏情况下的空间复杂度为___O(n)___。116.给定一组数据对象的关键码为{46，79，56，38，40，84}，对其进展一趟快速排序处理，得到的右子表中有__3__个对象。117.在对n个数据对象的二路归并排序中，每趟归并的时间复杂度为___O(n)___。118.在对n个数据对象进展的二路归并排序中，整个归并过程的时间复杂度为__O(nlog2n)__。119.在索引表中，每个索引项至少包含有__关键码_域和地址域这两项。120.假定一个线性表为{12,23,74,55,63,40,82,36}，假设按key%3条件进展划分，使得同一余数的元素成为一个子表，那么包含74的子表长度为__2__。121.假定一个线性表为(〞abcd〞,〞baabd〞,〞bcef〞,〞cfg〞,〞ahij〞,〞bkwte〞,〞ccdt〞,〞aayb〞)，假设按照字符串的第一个字母进展划分，使得同一个字母被划分在一个子表中，那么得到的以a为第一个字母的子表长度为__3__。122.在索引表中，假设一个索引项对应数据对象表中的一个表项，那么称此索引为稠密索引，假设对应数据对象表中的假设干表项，那么称此索引为__稀疏_索引。 123.假定对长度n=100的线性表进展索引顺序搜索，并假定每个子表的长度均为，那么进展索引顺序搜索的时间复杂度为_O(Eq\r(n))_。124.假定对长度n=100的线性表进展索引顺序搜索，并假定每个子表的长度均为，那么进展索引顺序搜索的平均搜索长度为__11__。125.假设对长度n=10000的线性表进展二级索引存储，每级索引表中的索引项是下一级20个表项的索引，那么一级索引表的长度为__500_。126.假设对长度n=10000的线性表进展二级索引存储，每级索引表中的索引项是下一级20个表项的索引，那么二级索引表的长度为__25__。127.假定要对长度n=100的线性表进展散列存储，并采用开散列法处理冲突，那么对于长度m=20的散列表，每个散列地址的同义词子表〔单链表〕的长度平均为_5__。128.在线性表的散列存储中，装载因子又称为装载系数，假设用m表示散列表的长度，n表示待散列存储的元素的个数，那么等于_n/m_。129.对于包含n个关键码的m阶B树，其最小高度为__logm(n+1)__。130.一棵3阶B树中含有50个关键码，那么该树的最小高度为___4___。131.一棵3阶B树中含有50个关键码，那么该树的最大高度为___5____。132.在一棵m阶B树上，每个非根结点的关键码数最少为__m/2-1__个。133.在一棵m阶B树上，每个非根结点的子树最少为__m/2__棵。134.在一棵m阶B树上，每个非根结点的关键码数最多为__m-1__个。135.在对m阶B树插入元素的过程中，每向一个结点插入一个关键码后，假设该结点的关键码个数等于__m__个，那么必须把它分裂为2个结点。136.在从m阶B树删除关键码的过程中，当从一个结点中删除掉一个关键码后，所含关键码个数等于m/2-2个，并且它的左、右兄弟结点中的关键码个数均等于_m/2-1_，那么必须进展结点合并。判断题1.数据元素是数据的最小单位。错2.数据的逻辑构造是指各数据元素之间的逻辑关系，是用户根据应用需要建设的。对3.算法和程序原那么上没有区别，在讨论数据构造时二者是通用的。错4.数据的逻辑构造与数据元素本身的内容和形式无关。对5.算法和程序都应具有下面一些特征：有输入，有输出，确定性，有穷性，有效性。错6.只有用面向对象的计算机语言才能描述数据构造算法。错7.如果采用如下方式定义一维字符数组：constintmaxSize=30;chara[maxSize];那么这种数组在程序执行过程中不能扩大。对8.如果采用如下方法定义一维字符数组：intmaxSize=30;char*a=newchar[maxSize];那么这种数组在程序执行过程中不能扩大。错9.数组是一种静态的存储空间分配，就是说，在程序设计时必须预先定义数组的数据类型和存储空间大小，由编译程序在编译时进展分配。错10.多维数组是一种复杂的数据构造，数组元素之间的关系既不是线性的也不是树形的。对11.在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。错12.顺序表和一维数组一样，都可以按下标随机〔或直接〕访问。对13.插入与删除操作是数据构造中最基本的两种操作，因此这两种操作在数组中也经常被使用。错14.使用三元组表示稀疏矩阵中的非零元素能节省存储空间。对15.用字符数组存储长度为n的字符串，数组长度至少为n+1。对16.线性表假设采用链式存储表示时，其存储结点的地址可连续也可不连续。对17.线性表假设采用链式存储表示,在删除时不需要移动元素。对18.在线性链表中删除中间的结点时，只需将被删结点释放。错19.在对双向循环链表做删除一个结点操作时，应先将被删除结点的前驱结点和后继结点链接好再执行删除结点操作。对20.每次从队列中取出的是具有最高优先权的元素,这种队列就是优先级队列。对21.链式栈与顺序栈相比,一个明显的优点是通常不会出现栈满的情况。对22.在一个顺序存储的循环队列中,队头指针指向队头元素的后一个位置。错23.栈和队列都是顺序存取的线性表,但它们对存取位置的限制不同。对24.在使用后缀表示实现计算器类时用到一个栈的实例,它的作用是暂存运算器对象。对25.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。对26.假设让元素1,2,3依次进栈，那么出栈次序1,3,2是不可能出现的情况。错27.在用单链表表示的链式队列Q中，队头指针为Q->front，队尾指针为Q->rear，那么队空条件为Q->front==Q->rear。错28.递归定义的数据构造通常用递归算法来实现对它的操作。对29.递归的算法简单、易懂、容易编写，而且执行效率也高。错30.递归调用算法与一样功能的非递归算法相比，主要问题在于重复计算太多，而且调用本身需要分配额外的空间和传递数据和控制，所以时间与空间开销通常都比较大。对31.递归方法和递推方法本质上是一回事，例如求n!时既可用递推的方法，也可用递归的方法。错32.用非递归方法实现递归算法时一定要使用递归工作栈。错33.将f=1+1/2+1/3+…+1/n转化为递归函数时，递归局部为f(n)=f(n-1)+1/n，递归完毕条件为f(1)=1。对34.一个广义表的表头总是一个广义表。错35.一个广义表的表尾总是一个表。对36.一个广义表((a),((b),c),(((d))))的长度为3，深度为4。对37.一个广义表((a),((b),c),(((d))))的表尾是((b),c),(((d)))。错38.当向一个最小堆插入一个具有最小值的元素时，该元素需要逐层向上调整，直到被调整到堆顶位置为止。对39.当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到适宜位置为止。对40.二叉树是一棵无序树。错41.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进展前序遍历和后序遍历，那么具有一样的结果。错42.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进展中序遍历和后序遍历，那么具有一样的结果。对43.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进展前序遍历和中根遍历，那么具有一样的结果。错44.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进展前序遍历和按层遍历，那么具有一样的结果。对45.在树的存储中，假设使每个结点带有指向双亲结点的指针，这为在算法中寻找双亲结点带来方便。对46.对于一棵具有n个结点，其高度为h的二叉树，进展任一种次序遍历的时间复杂度为O(n)。对47.对于一棵具有n个结点，其高度为h的任何二叉树，进展任一种次序遍历的时间复杂度均为O(h)。错48.对于一棵具有n个结点的任何二叉树，进展前序、中序或后序的任一种次序遍历的空间复杂度为O(log2n)。错49.在一棵具有n个结点的线索二叉树中，每个结点的指针域可能指向子女结点，也可能作为线索，使之指向某一种遍历次序的前驱或后继结点，所有结点中作为线索使用的指针域共有n个。错50.线索二叉树中的每个结点通常包含有5个数据成员。对51.对具有n个结点的堆进展插入一个元素运算的时间复杂度为O(n)。错52.在顺序表中进展顺序搜索时，假设各元素的搜索概率不等，那么各元素应按照搜索概率的降序排列存放，那么可得到最小的平均搜索长度。对53.进展折半搜索的表必须是顺序存储的有序表。对54.能够在链接存储的有序表上进展折半搜索，其时间复杂度与在顺序存储的有序表上一样。错55.假定有两个用单链有序表表示的集合，那么这两个集合的交运算可得到一个新的集合单链表，其长度小于等于参加运算的任意一个集合单链表的长度。对56.假定有两个用单链有序表表示的集合，那么这两个集合的差运算可得到一个新的集合单链表，其长度小于参加运算的任意一个集合单链表的长度。错57.折半搜索所对应的判定树，既是一棵二叉搜索树，又是一棵理想平衡二叉树。对58.对于同一组关键码互不一样的记录，假设生成二叉搜索树时插入记录的次序不同那么得到不同形态的二叉搜索树。对59.对于同一组记录，生成二叉搜索树的形态与插入记录的次序无关。错60.对于两棵具有一样记录集合而具有不同形态的二叉搜索树，按中序遍历得到的结点序列是一样的。对61.在二叉搜索树中，假设各结点的搜索概率不等，使得搜索概率越大的结点离树根越近，那么得到的是最优二叉搜索树。对62.在二叉搜索树中，假设各结点的搜索概率不等，使得搜索概率越小的结点离树根越近，那么得到的是最优二叉搜索树。错63.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。对64.邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。错65.邻接矩阵适用于稠密图〔边数接近于顶点数的平方〕，邻接表适用于稀疏图〔边数远小于顶点数的平方〕。对66.存储无向图的邻接矩阵是对称的，因此可以只存储邻接矩阵的下〔上〕三角局部。对67.强连通分量是有向图中的极大强连通子图。对68.对任何用顶点表示活动的网络〔AOV网〕进展拓扑排序的结果都是唯一的。错69.有回路的有向图不能完成拓扑排序。对70.在AOE网络中一定只有一条关键路径。错71.用边表示活动的网络〔AOE网〕的关键路径是指从源点到终点的路径长度最长的路径。对72.对于AOE网络，加速任一关键活动就能使整个工程提前完成。错73.对于AOE网络，任一关键活动延迟将导致整个工程延迟完成。对74.在AOE网络中，可能同时存在几条关键路径，称所有关键路径都需通过的有向边为桥。如果加速这样的桥上的关键活动就