发布时间 : 星期一 文章数据结构导论填空题目汇总更新完毕开始阅读
20．设数组A［0..8］［0..8］的起始元素位置为a，每个元素占2 L个存储单元，按行序为
主序存储。若元素A［i］［j］的存储位置为a+66 L，则元素A［j］［i］的存储位置为__a+114L_____。
21．有4个结点且深度为4的二叉树的形态共有___4____种。
22．某二叉树的先根遍历序列为IJKLMNO，中根遍历序列为JLKINMO，则该二叉树中根
结点的右孩子是____M___。
23．第一个顶点和最后一个顶点相同的路径称为回路或者环，除第一个顶点和最后一个顶
点外，其余顶点都不重复的回路，称为____简单回路或简单环___。 24．一个具有10个顶点的完全无向图中有___45____条边。 26．二分查找的时间复杂度为___ O(log2n次方)____。
27．二路归并排序算法的时间复杂度为__O(nlog2n次方)_____。
2007----10
17.设有指针head指向不带表头结点的单链表用next表示结点的一个链域指针p指向与链表中结点同类型的一个新结点。现要将指针p指向的结点插入表中使之成为第一个结点则所需的操作为“p→next=head”和“__________”。
18.单链表中逻辑上相邻的两个元素在物理位置上_____未必_____相邻。
19.在一个长度为n的数组中删除第i个元素1≤i≤n时需要向前移动的元素的个数是_____n-i_____。
20.设F、C是二叉树中的两个结点若F是C的祖先结点则在采用后根遍历方法遍历该二叉树时F和C的位置关系为F必定在C的_____后边_____。
21.若用后根遍历法遍历题21图所示的二叉树其输出序列为__________。
题21图
22.具有n个顶点的连通图至少需有__________条边。
23.在无向图G的邻接矩阵A中若Aij等于1则Aji等于____1______。
24.设顺序表的表长为n且查找每个元素的概率相等则采用顺序查找法查找表中任一元素在查找成功时的平均查找长度为__________。
25.在索引顺序表上的查找分两个阶段一是查找___索引表_______二是查找块。
27.在对一组关键字为54,38,96,23,15,72,60,45,83的记录采用直接选择排序法进行排序时整个排序过程需进行____9______趟才能够完成。
28.冒泡排序是一种稳定排序方法。该排序方法的时间复杂度为____O(n2平方)______。
2008----01
16.数据的逻辑结构通常包括集合、线性结构、____树形结构________和图状结构。
17.设双链表中结点的前趋指针和后继指针的域名分别为t1和r1，指针s指向双链表中的一个结点（该结点既非头结点，也非尾结点），则删除s指针所指向结点的操作为“s->tl->r1=s->r1；”和“____ s->r1->t1=s->t1;________”。
18.对稀疏矩阵进行压缩存储的目的是节省_____储存空间_______。
19.在一个具有n个结点的单链表中查找值为m的某结点，若查找成功，则需平均比较的结点数为____n+1/2____。
20.深度为15的满二叉树上，第11层有______1024______个结点。
21.对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的左孩子的编号为_____98_______。
i 的左孩子是2i,右孩子是2i+1.所以49的右孩子编号为98+1. 22.一个具有4个顶点的无向完全图有______6______条边。 n(n-1)/2
23.一个有向图G中若有孤
24.在一棵二叉排序树上按______中序______遍历得到的结点序列是一个有序序列。
25.实现二分查找的存储结构仅限于顺序存储结构，且其中元素排列必须是_____有序表 _______的。
27.在插入排序和选择排序中，若原始记录已基本有序，则较适合选用_____插入排序_______。
28.对n个元素的序列进行冒泡排序时，最多需进行____n-1________趟。
2008---10
16.在任何问题中，数据元素都不是孤立的，它们之间总存在某种关系，通常称这种关系为 ___图状结构_____。
17.存储结点之间通常有四种基本存储方式，即顺序存储方式、索引存储方式、___链式存储方式_____和散列存储方式。
18.在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动___n-i+1_____个元素。
19.对一棵深度为10的满二叉树按层编号，则编号为51的结点，它的双亲结点编号为____25____。
20.用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到1342的出栈顺序，相应的S和X操作串为___ SXSSXSXX_____。
21.具有n个叶子结点的哈夫曼树，其结点总数为___2n-1_____。
22.一棵具有n个结点的树，所有非终端结点的度均为k，则该树中叶子结点个数为________。
一棵具有n个结点的树，所有非终端结点的度均为k，则此二叉树为K叉树，这棵树只右度为K和度为0的结点，设度为K的结点数为a，度为0的结点数为b，则n=a+b。又设二叉树的所有分支为m,则m=k*a,同样可以得到n=m+1。 综上可以得到b=[(n-1)*(k-1)/k-1]。
23.在无向图G的邻接矩阵A中，若A［i］［j］等于0，则A［j］［i］等于___0_____。 25.某二叉树的后根遍历序列为abd，中根遍历序列为adb，则它的先根遍历序列为____ dab____。
26.先在所有的记录中选出键值最小的记录，将它与第一个记录交换；然后在其余的记录中再选出最小的记录与第二个记录交换，依此类推，直至所有记录排序完成。这种排序方法称为___直接选择排序_____。
27.对含有n个结点e条边的无向连通图，利用prim算法生成最小生成树的时间复杂度为____O(n2次方)____。
28.对n个元素进行冒泡排序时，最少的比较次数为__n-1______。
2009----01
16.在数据结构中，数据的存储结构有顺序存储方式、链式存储方式、__索引存储方式_______和散列存储方式等四种。
17. 作为一个算法输入的数据所含数据元素的数目，或与此数目有关的其他参数，称为_算法的输入规模和问题的规模________。
18.在双链表中，存储一个结点有三个域，一个是数据域，另两个是指针域，分别指向 ____直接前驱_____和 ____直接后继_____。
19.在有n个元素的链队列中，入队和出队操作的时间复杂度分别为__O(1)_______和__O(n)_______。
20.在栈结构中，允许插入的一端称为 ____栈顶_____；在队列结构中，允许插入的一端称为 _____队尾____。
21.在循环队列中，存储空间为0~n-1。设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么其队空标志为rear=front，队满标志为 _(rear+1)%maxsize==front________。
22.深度为k的二叉树至多有 __2k次方-1_______个结点，最少有 ___2(k次方-1)______个结点。
23.设有一稠密图G，则G采用 ____邻接矩阵_____存储结构较省空间。设有一稀疏图G，则G采用 _____邻接表____存储结构较省空间。
24.在一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较____(n+1)/2_____个元素结点。
25.假定对线性表R［0…59］进行分块检索，共分为10块，每块长度等于6。若检索索引表和块均用顺序检索的方法，则检索每一个元素的平均检索长度为___9______。 27.在插入排序、冒泡排序、快速排序、归并排序等排序算法中，占用辅助空间最多的是 ____归并排序_____。
28.冒泡排序最好的时间复杂度为 ___O（n）______，平均时间复杂度为 __ O（n的平方）_______，是一种稳定的排序算法。
2009---10
16.下列程序段的时间复杂度为___O(n)_____。
i=0s=0 whilei { i++ s=s+i } 17.数据的逻辑结构被分为集合结构、___线性结构_____、树形结构和图状结构4种。 18.线性表中所含结点的个数称为___表长_____。 19.向一个栈顶指针为top的链栈中插入一个新结点*p时应执行__top-->next_=p____和top=p操作。 20.设一个顺序栈S元素s1s2s3s4s5s6依次进栈如果6个元素的退栈顺序为s2s3s4s6s5s1则顺序栈的容量至少为____3____。 21.若满二叉树的结点数为n则其高度为___【log2(n)】+1_____。 22.在一棵具有n个结点的完全二叉树中从树根起自上而下、从左到右地给所有结点编号。若编号为i的结点有父结点那么其父结点的编号为___[i/2]____。 23.深度为k的二叉树结点数最多有____2k次方-1____个。 24.某二叉树的后根遍历为ABKCBPM则该二叉树的根为_____M___。 25.在一个具有n个顶点的无向图中顶点的度最大可达____n-1____。 26.有向图G的邻接矩阵为A如果图中存在弧 _____。