数据结构导论填空题目汇总

28.如果要将序列{60182869997578}建成堆则只需把60与___18___相互交换。

2013----01

16.下面算法程序段的时间复杂度为___0(n2平方)_______。 for(i=1;i<=n;i++) for(j=1;j<=i;j++) {x=a[i][j];

a[i][j]=a[j][i]; a[j][i]=x;}

17.设p指向单链表的最后一个结点,要在最后一个结点之后插入q所指的结点,需执行的语句序列是①p->next=q;②___p=q_______;③p->next=NULL。

18.向一个长度为100的顺序表中第50个元素之前插入一个元素时,需向后移动的元素个数为_____51_____。

19.一个带头结点的链栈LS,现将一个新结点入栈,指向该结点的指针为p,入栈操作为p->next=LS->next和____ls->next=p______。 20.队列操作的原则是___先进先出_______。

21.含有n个顶点的连通图中的任意一条简单路径,其最大长度为____n-1______。

22.在一棵度为3的树中,度为3的结点数为1个,度为2的结点数为2个,度为1的结点数为3个,则度为0的结点数为_____6_____个。

23.某二叉树的中序遍历序列为BACDEFGH,后序遍历序列为BCAEDGHF,则根结点F的左子树上共有____5______个结点。

24.设有向图G的邻接矩阵为A,如果是图中的一条弧,则A[i][j]的值为___1____。 25.一个有序表A含有15个数据元素,且第一个元素的下标为1,按二分查找算法查找元素A[14],所比较的元素下标依次是__8,12,14________。 二分查找算法是从low=1开始的。Hgih=有序表长度 1+15/2=8(8<14), 9+15/2=12(12<14) 13+15/2=14(14==14)

26.用n个值构造一棵二叉排序树,它的最大深度为__[log2n]+1________。

27.设记录数为n,则冒泡排序算法在最好情况下所作的比较次数为___n-1_______。 28.二路归并排序算法的时间复杂度为____ O(n*logn2(n))______。

2013---10

16数据中不可分割的最小标识单位是____数据项______。

17双向循环链表中在p所指结点的后面插入一个新结点*t需要修改四个指针分别为t->prior=p__t->next=p->next________p->next->prior=tp->next=t。

18.在带有头结点的循环链表中头指针为head判断指针p所指结点为首结点的条件是____p==head->next______。

19元素的进栈次序为123…n出栈的第一个元素是n则第k个出栈的元素是___n-k+1_______。 20在栈结构中允许插入和删除的一端称为_____栈顶_____。

21 100个结点的二叉树采用三叉链表存储时空指针域NULL有______102____个。

100个结点的二叉树用三叉链表存储共有101+ 1 = 102个空指针域 1代表双亲指针,只有根没有双亲

101:每个结点有两个孩子域,因此一共100*2= 100个指针域,但100个结点中间的连接边一定是100-1=99个,所以空的指针域有200-99=101,也就是n个结点有n+1个空的指针域

这样加上双亲域,n个结点的三叉链表共有n+2个空指针域

101是二叉树的空指针域,而三叉树比二叉树每个节点多了父指针。此种存储跟节点是没有父节点的。所以二叉树的空指针域+1(跟节点父指针为空)=三叉树空节点

22.某二叉树的先序遍历序列为ABKLMNO中序遍历序列为BLKANMO则该二叉树中结点A的右孩子为结点___M_______。

23一个二叉树的最少结点个数为____0______。

24图中第一个顶点和最后一个顶点相同的路径称为回路。除第一个顶点和最后一个顶点相同外其余顶点不重复的回路称为___简单回路或简单环_______。

25设查找表有n个数据元素则二分查找算法的平均查找长度为____(n+1)/n*log2(n+1)--1______。

26用键值通过散列函数获取存储位置的这种存储方式构造的存储结构称为_____散列值_____。

27若在线性表中采用二分查找法查找元素则该线性表必须按值有序并且采用____顺序______存储结构。

?k?k2i?n?(i?1,2,?,??)则这n个键28堆分为最小堆和最大堆若键值序列{k1,k2,…kn}满足?i?2??ki?k2i?1值序列{k1,k2,…kn}是____最小堆(或最大堆)______。

2014---4

16.数据的基本单位是__数据元素_______。

17.双向循环链表中,在p所指结点的后面插入一个新结点*t,需要修改四个指针,分别为 t->prior=P;t->next=p->next;___p->next->prior=t______;p->next=t;。

18.在带有头结点的循环链表中,尾指针为rear,判断指针P所指结点为首结点的条件是___ rear->next->next ______。

19.若线性表中最常用的操作是求表长和读表元素,则顺序表和链表这两种存储方式中,较节省时间的是___顺序表______。

20.不含任何数据元素的栈称为___空栈______。

21.稀疏矩阵一般采用的压缩存储方法是____三元组表示法_____。

22.100个结点的二叉树采用二叉链表存储时,用来指向左、右孩子结点的指针域有___99______个。

23.已知完全二叉树的第5层有5个结点,则整个完全二叉树有____20_____个结点。 24.n个顶点的有向图G用邻接矩阵A[1..n,1..n]存储,其第i列的所有元素之和等于顶点 Vi的____入度_____。

25.具有10个顶点的有向完全图的弧数为____90___。

26.要完全避免散列所产生的“堆积’’现象,通常采用___公共溢出区______解决冲突。

27.在长度为n的带有岗哨的顺序表中进行顺序查找,查找不成功时,与关键字的比较次数为____N+1_。

28.归并排序算法的时间复杂度是____ O(NLOG2N) _____。

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4