2012年贵州大学数据结构复习题及答案

2012年贵州大学数据结构复习题及答案1、下面程序的时间复杂度为___C_。for(i=0;im;i++)for(j=0;jn;j++)A[i][j]=i*j;(A).O(m2)(B).O(n2)(C).O(m*n)(D).O(m+n)2、在数据结构中，从逻辑上可以把数据结构分成__C__。(A).动态存储结构和静态存储结构(B).紧凑结构和非紧凑结(C).线形结构和非线性结构(D).内部结构和外部结构3、下面程序的时间复杂度为__A__。for(i=0;im;i++)for(j=0;jt;j++)c[i][j]=0;for(i=0;im;i++)for(j=0;jt;j++)for(k=0;kn;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];(A).O(m*n*t)(B).O(m+n+t)(C).O(m+n*t)(D).O(m*t+n)4、下面程序的时间复杂度为__D__。i=1；while(i=n)i=i*5;(A).O(1)(B).O(n)(C).O(5*n)(D).O(log5n)5、算法指的是_D__。(A).计算机程序(B).解决问题的步骤(C).排序算法(D).解决问题的有限运算序列6、某程序的时间复杂度为（3n+nlog2n+n2+8），其数量级表示为C(A).O(n)(B).O(nlog2n)(C).O(n2)(D).O(log2n)7、数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的__B____和运算的科学。(A).结构(B).关系(C).运算(D).算法8、算法分析的目的是__C____。(A).找出算法的合理性(B).研究算法的输入/输出关系(C).分析算法的有效性以求改进(D).分析算法的易懂性9、数据的基本单位是____B____。(A).数据(B).数据元素(C).数据项(D).结构体10、与数据元素本身的形式、内存、相对位置、个数无关的是数据的____B_。(A).存储结构(B).逻辑结构(C).算法(D).操作11、数据逻辑结构在计算机里的实现是___________A_______.(A).存储结构(B).逻辑结构(C).算法(D).操作1、在一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需要向前移动__A____个元素。(A).n-i(B).n-i+1(C).n-i-1(D).i+12、线性表采用链式存储时，其地址___D_____。(A).必须是连续的(B).一定是不连续的(C).部分地址必须连续(D).连续与否均可以3、如果某链表中最常用的操作是取第i个结点及其前驱，则采用_B____存储方式最节省时间。(A).单链表(B).双向链表(C).单循环链表(D).顺序表4、带头结点的单链表L为空的判定条件是__B_。(A).L==NULL(B).L→next==NULL(C).L→next==L(D).L!=NULL5、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行_C__。(A).s→next=p→next;p→next=s;(B).p→next=s→next;s→next=p;(C).q→next=s;s→next=p;(D).p→next=s;s→next=q;6、线性表是_A__。(A).一个有限序列，可以为空(B).一个有限序列，不可以为空(C).一个无限序列，可以为空(D).一个无限序列，不可以为空7、在一个长度为n的顺序表中向第i个元素(1i=n+1)之前插入一个新元素时，需向后移动_B___个元素。(A).n-i(B).n-i+1(C).n-i-1(D).i8、一个顺序存储的线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是__B______。(A).98(B).100(C).102(D).1069、头指针为L的非空的循环单链表的尾结点（由p所指向）满足_C__。(A).p→next==NULL(B).p==NULL(C).p→next==L(D).p==L10、用链表示线性表的优点是___C______。(A).便于随机存取(B).花费的存储空间比顺序表少(C).便于插入与删除(D).数据元素的物理顺序与逻辑顺序相同11、一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为_____B______(A).O(n)(B).O(1)(C).O(n2)(D).O(log2n)12、线性表采用链式存储不具有的特点是____A________。(A).随机访问(B).不必事先估计所需存储空间大小(C).插入与删除时不必移动元素(D).所需空间与线性表长度成正比13、在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为____A_____(A).O(n)(B).O(n/2)(C).O(1)(D).O(n2)1、对于栈操作数据的原则是__B______。(A).先进先出(B).后进先出(C).后进后出(D).不分顺序2、若一个栈的输入序列是1、2.......n，输出序列的第一个元素是n，则第k个输出元素是_________C_______。(A).k(B).n-k-1(C).n-k+1(D).不确定3、有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列__C___。(A).543612(B).453126(C).346521(D).2341564、输入序列为ABC，可以变为CBA时，经过的栈操作为_____B__。(A).push,pop,push,pop,push,pop(B).push,push,push,pop,pop,pop(C).push,push,pop,pop,push,pop(D).push,pop,push,push,pop,pop5、用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时____D__。(A).仅修改队头指针(B).仅修改队尾指针(C).队头、队尾指针都要修改(D).队头,队尾指针都可能要修改6、递归过程或函数调用时，处理参数及返回地址，要用一种称为___C___的数据结构。(A).队列(B).多维数组(C).栈(D).线性表7、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是__A____。(A).(rear-front+m)%m(B).(rear-front+1)%m(C).(rear-front-1)%m(D).(rear-front)%m8、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为___B__(A).1和5(B).2和4(C).4和2(D).5和19、最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是___B___。(A).(rear+1)%n==front(B).rear==front(C).rear+1==front(D).front+1==rear10、栈和队都是__C________。(A).顺序存储的线性结构(B).链式存储的非线性结构(C).限制存取点的线性结构(D).限制存取点的非线性结构11、向一个不带头结点的栈顶指针为top的链栈中插入s结点的时候，应当执行语句_____B___。(A).top-next=s;(B).s-next=top;top=s;(C).s-next=top-next;top-next=s;(D).s-next=top;top=s-next;1、在二叉树后序遍历中，任一个结点均在其孩子结点后面，这种说法____A___。(A).正确(B).不正确(C).无法判断(D).以上均不对2、一棵二叉树度2的结点数是7，度1的结点数是6，则叶子结点数是_C____。(A).6(B).7(C).8(D).93、已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的先序遍历序列是__D_。(A).acbed(B).decab(C).deabc(D).cedba4、按照二叉树的定义，具有3个结点的二叉树有___C种。(A).3(B).4(C).5(D).65、对一个满二叉树，m个树叶，n个结点，深度为h，则C__。(A).n=h+m(B).h+m=2n(C).n=2h-1(D).n=2h-16、设n，m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是__C_。(A).n在m右方(B).n是m祖先(C).n在m左方(D).n是m子孙7、树最适合用来表示__D_______。(A).线性结构的数据(B).顺序结构的数据(C).元素间无前驱和后继关系的数据(D).元素之间有分支和层次关系的数据8、设a、b为一棵二叉树的两个结点，在后序遍历中，a在b前的条件是___D____。(A).a在b上方(B).a在b下方(C).a在b左方(D).a在b右方9、权值为{1，2，6，8}的四个结点构成的哈夫曼树的带权路径长度是_D______。(A).18(B).28(C).19(D).291、一个有n个顶点的无向图最多有_C__条边。(A).n(B).n(n-1)(C).n(n-1)/2(D).2n2、对于一个具有n个结点e条边的无向图，若采用邻接表表示，则顶点表的大小为__A_。(A).n(B).n+1(C).n-1(D).n+e3、对于一个具有n个结点e条边的无向图，若采用邻接表表示，则所有边链表中边结点的总数为__C_。(A).e/2(B).e(C).2e(D).n+e4、一个无向连通图的生成树是含有该连通图的全部顶点的__A______。(A).极小连通子图(B).极小图(C).极大连通子图(D).极大图5、邻接表是图的一种___B___。(A).顺序存储结构(B).链式存储结构(C).索引存储结构(D).散列存储结构6、对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为__B_____。(A).n(B).n2(C).n-1(D).(n-1)2排序1、从未排序序列中依次取出元素与已排好序的序列中的元素作比较，将其放入已排序序列的正确位置上，此方法称为_______A_________。A插入排序B选择排序C交换排序D归并排序2、从未排序序列中挑选元素，并将其放入已排序序列的一端，此方法称为___C___。A插入排序B交换排序C选择排序D归并排序3、依次将每两个相邻的有序表合并成一个有序表的排序方法称为_____D______。A插入排序B交换排序C选择排序D归并排序4、当两个元素出现逆序的时候就交换位置，这种排序方法称为_____B______。A插入排序B交换排序C选择排序D归并排序5、每次把待排序的区间划分为左、右两个子区间，其中左区间中的记录的关键字均小于等于基准记录的关键字，右区间中记录的关键字均大于基准记录的关键字，这种排序方法称为_____B______。A插入排序B快速排序C堆排序D归并排序6、在正常情况下，直接插入排序的时间复杂度为_____D_______。AO(log2n)BO(n)CO(nlog2n)DO(n2)7、在正常情况下，冒泡排序的时间复杂度为________D_______。AO(log2n)BO(n)CO(nlog2n)DO(n2)8、归并排序算法的时间复杂度为______C________。AO(log2n)BO(n)CO(nlog2n)DO(n2)9、在待排序元素基本有序的情况下，效率最高的排序方法是________A________。A插入排序B快速排序C堆排序D归并排序10、设有800条记录，希望用最快的方法挑选出其中前10个最大的元素，最好选用_______C________。A插入排序B快速排序C堆排序D归并排序11、下列排序方法中，不稳定的排序算法是______C_______。A直接插入排序B冒