20166月数据结构习题.docx

1、一棵二叉树没有单分支结点，有6个叶结点，则该树总共有____11____个结点。 2、数据结构的实质就是研究数据的　　　　　　、 以及定义在逻辑结构上所进行的一组　　　　。 3、栈和队列的操作特点分别是___ 后进先出 ____和 _____ 先进先出 ___。 4、设一棵完全二叉树，其最高层上最右边的叶结点的编号为奇数，该叶节点的双亲结点的编号为10，该完全二叉树一共有____21____个结点。 5、一个图的_________表示法是唯一的，而___________表示法是不唯一的。 6、已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有 个叶子结点。 7、G为无向图，如果从G的某个顶点出发，进行一次广度优先有哪些信誉好的足球投注网站，即可访问图的每个顶点，则该图一定是 。 8、结构中的数据元素存在多对多的关系称为_____ 图状 （网状） ___结构。 9、按照二叉树的递归定义，对二叉树遍历的常用算法有先序；中序；后序三种。 10、在具有n个单元的循环队列中，队满时共有__________个元素。 11、3个结点可构成 棵不同形态的树。 12、一棵深度为h的满二叉树上的结点总数为　　　　　　，一棵深度为h的完全二叉树上的结点总数的最小值为　　　，最大值为　　　　　。 13、在一棵完全二叉树中有n个结点，对这些结点按层序编号，若一个结点编号为69，则其双亲编号为　　　　，有左孩子的条件是　　　　，其左孩子编号为　　　　。 14、根据数据元素间关系的不同特性，通常可分为集合、线性、树形 、 图状 四类基本结构。 15、数据结构中的数据元素存在一对多的关系称为__树形_____结构。 16、要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为__n-1和 O(n)__ 。 17、顺序存储的栈中，在作进栈运算时,应先判别栈是否 ,在进行出栈运算时应先判别栈是否 。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为 。 18、在带头结点的循环链表h中，判断表空的条件是　　　　　　　　。 19、具有n个顶点的有向完全图的弧数为_________。 20、数据的存储结构被分为_________和_________。 21、设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是________。 22、在线性表的顺序存储中，元素之间的逻辑关系是通过 决定的；在线性表的链式存储中，元素之间的逻辑关系是通过_________决定的。 23、把数据存储到计算机中,并具体体现数据之间的逻辑结构称为____物理（存储）____结构。 24、在一个单向链表中p所指结点之后插入一个s所指向的结点时，应执行___ s-next=p-next ____和p-next=s;的操作。 25、3个结点可以构成 棵不同形态的二叉树。 26、对于一棵具有n个结点的二叉树，当它为一棵 二叉树时具有最小高度，即为 ，当它为一棵单支树时具有 高度，即为 。 27、一个图的_________表示法是唯一的，而___________表示法是不唯一的。 28、在一棵有n个结点的完全二叉树中，对这些结点按层序编号，若一个结点编号为59，则其双亲编号为 ，若一个结点编号为23，则其有右孩子的条件是 。 29、一棵深度为h的完全二叉树上的结点总数的最小值为 ，最大值为 。 30、 查找法的平均查找长度与元素个数n无关。 31、在带头结点的循环链表h中，判断表空的条件是 。 32、一个具有n个顶点的无向完全图的边数为 。 33、数组M中每个元素的长度是3个字节，行下标i从1到8，列下标j从1到10，从首地址EA开始连续存放在存储器中。若按行优先方式存放，元素M[8][5]的起始地址为_____________；若按列优先方式存放，元素M[8][5]的起始地址为___________。 34、对于一个具有n个结点的单链表，在p所指结点后插入一个新结点的时间复杂度为__________；在给定值为x的结点后插入一个新结点的时间复杂度为_____________。 35、数据结构的实质就是研究数据的