数据结构练习题[].docVIP

1、3个结点可构成 棵不同形态的树。 2、利用直接选择排序算法对n个记录进行排序，最坏的情况下，记录交换的次数为 。 3、一个图的_______表示法是唯一的，而______表示法是不唯一的。 4、一棵深度为h的满二叉树上的结点总数为　　　　　　，一棵深度为h的完全二叉树上的结点总数的最小值为　　　，最大值为　　　　　。 5、在一棵完全二叉树中有n个结点，对这些结点按层序编号，若一个结点编号为69，则其双亲编号为　　　　，有左孩子的条件是　　　　，其左孩子编号为　　　　。 6、二维数组M的成员是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要________个字节；M的第8列和第5行共占___________个字节；若M按行优先方式存储，元素M[8][5]的起始地址与当M按列优先方式存储时的________元素的起始地址一致。 7、设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是________。 8、在线性表的顺序存储中，元素之间的逻辑关系是通过 决定的；在线性表的链式存储中，元素之间的逻辑关系是通过_________决定的。 9、n个顶点的连通图的生成树有　　　　条边。n个结点的二叉树，当它为一棵 完全 二叉树时具有最小高度，即为 ∟log2n」+1 ，当它为一棵单支树时具有 最大 高度，即为 n 。 13、在一棵有n个结点的完全二叉树中，对这些结点按层序编号，若一个结点编号为59，则其双亲编号为 ，若一个结点编号为23，则其有右孩子的条件是 。 14、数组M中每个元素的长度是3个字节，行下标i从1到8，列下标j从1到10，从首地址EA开始连续存放在存储器中。若按行优先方式存放，元素M[8][5]的起始地址为________；若按列优先方式存放，元素M[8][5]的起始地址为________。 15、对于一个具有n个结点的单链表，在p所指结点后插入一个新结点的时间复杂度为_______；在给定值为x的结点后插入一个新结点的时间复杂度为__________。 16、数据结构的实质就是研究数据的　　　　　　、 以及定义在逻辑结构上所进行的一组　 　　　。 17、任何连通图的连通分量有_____1_____个，即__它本身_________。 18 假定查找有序表A[1..10]中每个元素的概率相等，则进行顺序查找时的平均查找长度为　　5.5　，进行二分查找时的平均查找长度为　　 20　　。 1、在一个单链表中，已知q所指结点是p所指结点的前驱，若在p、q之间插入s结点，则执行（ ）操作。 A、s-next=p-next;p-next=s; B、q-next=s;s-next=p; C、p-next=s-next;s-next=p; D、p-next=s;s-next=q; 2、下面程序段的时间复杂度为（　 ）。 　　i=1; while (i=n) i=i*2; A、O(log2n) B、O(n) C、O( n) D、O(nlog2n) 3、设森林T中有三棵树，第一、二、三棵树的结点个数分别是n1，n2，n3，那么当把森林转换成二叉树后，其根结点的左子树上有（　）个结点，右子树上有（　）个结点。 A、n1-1　B、n1　C、n1+n2　D、n2+n3 4、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ 　）存储方式最节省时间。 A、单链表　B、双链表　C、单向循环链表　D、顺序表 5、使用双向链表存储数据，其优点是可以（ 　）。 A、提高检索速度　 B、很方便地插入和删除数据　 C、节约存储空间　 D、很快回收存储空间 6、单链表中，增加头结点的目的是为了（ ）。 A、方便运算的实现 B、标识单链表 C、使单链表中至少有一个结点 D、用于标识起始结点的位置 7、在具有n个结点的二叉排序树上插入一个新结点时，其时间复杂度大致为（ ）。 A、O（n2） B、O(n) C、O(log2n) D、O(nlog2n) 8、下面程序段的时间复杂度为（ 　）。 　　 for (i=1;i=m;++i) for (j=1;j=n;++j) A[i,j]=i*j; h为空的判断条件是（ ）。 A、h==NULL B、h-next==NULL C、h-next==h