《数据结构》习题剖析.doc

《数据结构》习题 一、单项选择题 1．对矩阵进行压缩存储是为了（　　　） A．节省存储空间 B．提高运算速度 C．便于运算 D．方便存储 2．链式栈与顺序栈相比，一个比较明显的优点是（　　　） A．插入操作更加方便 B．通常不会出现栈满的情况 C．不会出现栈空的情况 D．删除操作更加方便 3．设输入序列为1，2，3，4，5，则借助一个队列可以得到的输出序列是（　　　） A．3，4，1，2，5 B．1，2，3，4，5 C．2，3，4，1，5 D．5，4，3，2，1 4.一个栈的输入序列是6,5,4,3,2,1,可能的输出序列是（ ）? A．4,3,2,1,5,6?? B．3,6,2,1,5,4 C．1,2,3,5,4,6???D．5,4,1,3,2,65 B．C，A，D，B C．D，C，A，B D．D，A，B，C 6．将含100个结点的完全二叉树从根开始，每层从左到右依次对结点编号，根结点的编号为1，则编号为71的结点的双亲结点的编号为（　　　） A．34 B．35 C．36 D．无法确定 7．已知完全二叉树有80个结点，则该二叉树有 （　　　） 个度为1的结点。 A．0 B．1 C．2 D．不确定 8．任何一个无向连通图的最小生成树（　　　） A．只有一棵 B．有一棵或多棵 C．一定有多棵 D．可能不存在 9．设图G用邻接表存储，对该图进行深度优先有哪些信誉好的足球投注网站遍历，则算法的时间复杂度为 （　） A． O(n) B． O(n+e) C． O(n2) D． O(n3) 10．用n个键值构造一棵二叉排序树，最低高度为（　　　） A．n/2 B．n C．[㏒2n] D．[㏒2n]+1 11．如果以链表作为栈的存储结构，则执行出栈操作时（　　　） A．必须判断栈是否满 B．必须判断栈是否空 C．判断栈元素的类型 D．对栈不作任何判断 12．设数组Data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为 （　　　） A．front=front+1 B．front=(front+1)%m C．rear=(rear+1)%m D．front=(front+1)%(m+1) 13．线性表的长度是指（　　　） A．顺序存储方式下数组所占用的元素个数 B．链表存储方式下的结点个数 C．表中的元素个数 D．所能存储的最大的结点个数 14．设有一个无向图G＝(V，E)和G’=(V’，E’)，如果G’是G的生成树，则下面不正确的说法是（　） A．G’为G的子图 B．G’为G的连通分量 C．G’为G的极小连通子图且V’=V D．G’是G的一个无环子图 15．在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的键值（　　　） A．一定都是同义词 B．一定都不是同义词 C．都相同 D．不一定都是同义词 16．在有序表A[20]中按二分查找方法查找A[13]依次比较的元素的下标是（　　） A．9，14，12，13 B．9，15，12，13 C．9，14，11，12，13 D．10，15，12，13 17．栈和队列都是（　　　） A．顺序存储的线性表 B．链式存储的线性表 C．限制的线性表 D．限制存储点的非线性结构 18．向顺序栈中压入新元素时，应当（　　　） A．先移动栈顶指针，再存入元素 B．先存入元素，再移动栈顶指针 C． 先后次序无关紧要 D．同时进行 19．若树的先序序列和中序序列正好相同，则一定是一棵 （　　　） 的二叉树。 A．结点个数可能大于1且该树无左子树 B．结点个数可