数据结构期末复习题集.doc

《数据结构期末复习题集.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、A11、有n个顶点的无向完全图中，具有（A）条边。A.n(n-1)/2B.n(n-1)C.n(n+1)/2D.n25、设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6先后进入栈S，一个元素出栈后即进入队列Q，若6个元素的出队顺序是e2,e4,e3,e6,e5,e1，则栈S至少可以容纳（D）个元素。A.3B.4C.5D.66、设有一个数组queue[0..m-1]表示循环队列，若f表示当前队头元素在数组中的位置，r表示队尾元素的后一位置（按顺时针方向），则计算队列中元素个数的表达式为（D）。A.r-fB.(m-f-r)modmC.(m+f-r

2、)modmD.(m+r-f)modm3.若一个栈的输入序列是1,2,3…n，输出序列的第一个元素是n，则第i个输出元素是（C）。A)不确定   B)n-i    C)n-i+1   D)i9.堆排序的时间复杂度为（D）。A)O(n2)B)O(log2n)C)O(n)D)O(nlog2n)10．已知Huffman树的总结点数为m，叶子数为n。则m与n的关系是（C）。 A)m=2n+1B)m=n+1C)m=2n–1D)m=n-1二、判断题2、栈和队列都是顺序存储的线性结构。（×）9、通常，选择排序比插入排序的元素交换次数要少。　（√）1、线性表的链式存储结构优于顺

3、序存储结构。（×）2、一个n维数组可以视为其数据元素是n-1维的线性表。（√）4、二叉树中，有两个孩子的结点，在中序遍历序列中，其后继结点最多只有一个。（×）8、运用折半检索时，检索表中的元素必需以关键字递增（由小到大）有序排列。（×）三、填空题2.下面程序段的时间复杂度是O()。longi=1,s=0.0;while(s

4、数排序时间复杂度是O（d(n+b)）。9．对长度为n的线性表进行分块查找，其ASL的最小值是O()。10．线性表长度为n，对其进行归并排序时间复杂度是O(nlog2n)。1、在一个链栈中，top为指向栈顶的指针，p所指向的结点（已建立）入栈时，应顺序执行如下操作语句：p->next=top;top=p;3、n个结点的循环队列中，front指示当前队头的位置（下标），rear指示当前队尾的后一位置。那么，在元素出队前，要执行front=(front+1)modn语句；在元素入队前，要执行rear=(rear+1)modn语句。4、一棵深度为h的二叉树中，结点最少

5、有h个，最多有2h-1个。5、n个结点的二叉链表中，共有2n个指针，其中有n-1个指针用于指向左、右孩子，剩余的n+1个指针为空。6、在具有n个顶点的有向完全图中，共有n(n-1)条弧。8、散列表（哈希表）检索法的平均检索长度与元素个数n无关。2、栈作为实现函数递归调用的数据结构。队列作为打印缓冲区的数据结构。3、n个结点的循环队列中，front指示当前队头的前一个位置（下标），rear指示当前队尾的位置。那么，在元素入队前，要执行rear=(rear+1)%n语句；在元素出队前，要执行front=(front+1)%n语句。5、在具有n个顶点的无向完全图中，

6、共有n(n-1)/2条边；而它的生成树中，有n-1条边。6、一棵深度为6的满二叉树中，叶子结点的个数为32，(2i-1)分支结点的个数为31。n2=n0-17、有由1000个数据元素组成的顺序表，假设一次比较表中关键字所需的时间为0.5毫秒。则在机会均等的情况下顺序检索，成功检索一个元素的平均用时为250.25毫秒。(N+1)/2*0.58、对于快速排序而言，在最好情况下，算法的时间复杂度为O(nlog2n)；在最坏情况下，时间复杂度为O(n2)。11．二叉树用以下静态二叉链表作为存储结构#definen0100//数组最大下标#definedatatypec

7、harstructnode{datatypedata;intlch,rch;//lch指向左子树，rch指向右子树}tree[n0+l];introot;//根结点指针下面是先序遍历二叉树的非递算法。一维数组s作为栈，t为栈顶指针。voidpreorder（）{ints[n0+l],t=0; intp=root;while(p

8、

9、t)if(p){printf(“%c”,tree[p].data)s[++t]=tree[p].rch;p=tree[p].lch;}elsep=s[t--];}12.以下mergeSort是归并排序算法，merge是将两个相邻有序表

10、归并的算法，mergepass是一趟归