数据结构复习题库一、填空填1.数据结构及数据的逻辑结构包括集合、_________、_________、图形结构（网状结构）四种类型。2.通常从四个方面评价算法的质量：、可读性、健壮性和______________________。3.一种数据结构的元素集合K和它的二元关系R为K=｛a,b,c,d,e,f,g,h｝，R=｛<d，b>，，，，，，｝，该数据结构具有______结构。4.在线性结构和树型结构中，前驱结点和后继结点之间分别存在着一对一和______的联系。5.线性表、栈和队列都是_______结构，对于栈只能在_______插入和删除元素；对于队列只能在_______插入元素，在______删除元素。6.子串“ABC”在主串“ABABCABCD”中的位置为______。7.已知广义表A=(((a,b),(c),(d,e))),GetHead(GetTail(GetTail(GetHead(A))))的结果是______。8.对于一棵具有n个结点的树，该树中所有结点的度数之和为______。9.AOV网是一种___________的图。10.一棵深度为k的满二叉树的结点总数为______，一棵深度为k的完全二叉树的结点总数的最小值为______。11.在一个具有n个顶点的有向完全图中，至多包含有______条边。12.使用分块查找时是，除表本身外，尚需建立一个索引表，用来存放每一块中的最大___________及该块的起始地址。13.一个好的哈希函数其转换地址应尽可能___________，而且函数运算应尽可能简单。14.动态查找表和静态查找表的重要区别在于前者包含有插入和___________运算，而后者不包含这两种运算。15.数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和______，并由此得到两种不同的存储结构是顺序存储结构和链式存储结构。16.设元素1，2，3，4，5依次进栈，若要在输出端得到序列34251，则应进行的操作序列为push(S,1),push(S,2),______，pop(S)，push(S,4)，pop(S)，______，______,pop(S)，______。17.一个算法应具有_____，确定性，可行性，_____，_____这五个特征。18.数据结构及数据的逻辑结构包括______、线性结构、树型结构、______四种类型。19.通常从四个方面评价算法的质量：正确性、、__________和效率与低存储量需求。20.子串“ABC”在主串“ABDABCABCD”中的位置为______。21.一棵深度为k的完全二叉树的结点总数的最小值为______，最大值为______。22.如图所示的二叉树的中序遍历序列是__________。23.在双向链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向______。24.对于一个具有n个结点的二叉树，它可能具有的最小深度为______，具有的最大深度为______。25.一个算法的时间复杂性通常用它的数量级形式表示，当一个算法的时间复杂度与问题的规模n大小无关时，则表示为O(1)；成正比时，则表示为O(n)；成平方时，则表示为______。26.通常从四个方面评价算法的质量：、可读性、健壮性和__________。27.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为__________。28.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树深度为________，树的度为_________。29.后缀算式923+-102/的值为-__________。中缀算式（3+4X）-2Y/3对应的后缀算式为_______________________________。30.AOV网是一种___________________的图。31.在一个具有n个顶点的无向完全图中，至少包含有________条边；在一个具有n个顶点的有向完全图中，至多包含有_______________条边。二、选择题1.在一个长度为n的顺序表中，删除值为x的元素时需要比较元素和移动元素的总次数为（）A.（n+1）/2B.n/2C.nD.n+12.下面程序段的时间复杂度的量级为（）for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;A.O(1)B.O(n)C.O(n2)D.O(n3)3.如图所示的4棵二叉树中，（）不是完全二叉树。4.一个栈的