、单选题（共 20 题，40 分）1、向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 的元素 个数为（ ）。（2.0）A、8B、63.5C、63D、7 正确答案： B 2、在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间 复杂度是（ ）。2.0)A、O(1)B、O(n)C、O(n2)D、O(log n) 正确答案： B3、根据一组关键字（56, 42, 50, 64, 48）依次插入结点生成一棵AVL树，当插入到值为0的结点时需要进行旋转调整。（2.0）A、42B、50C、64D、48 正确答案： B4、若查找每个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找长度为（）。 （2.0）A、nB、n+1C、(n-1)/2D、(n+1)/2 正确答案： D 5、在一个长度为n的顺序表中删除第i个元素（0=i=n）时，需向前移动 元素。(2.0)A、n-iB、n-i+lC、n-i-1D、i 正确答案： A6、稀疏矩阵一般的压缩存储方法有两种，即（ ）。（2.0）A、二维数组和三维数组B、三元组和散列C、三元组和十字链表D、散列和十字链表 正确答案： C7、以下关于线性表的说法不正确的是。 （2.0）A、线性表中的数据元素可以是数字、字符、记录等不同类型。B、线性表中包含的数据元素个数不是任意的。C、线性表中的每个结点都有且只有一个直接前趋和直接后继。D、存在这样的线性表：表中各结点都没有直接前趋和直接后继 正确答案： C8、在n个结点的顺序表中，算法的时间复杂度是0（ 1）的操作是（）。（2.0）A、访问第i个结点（lWiWn）和求第i个结点的直接前驱（2WiWn）B、在第i个结点后插入一个新结点（lWiWn）C、删除第i个结点（lWiWn）D、将n个结点从小到大排序正确答案： A9、一棵非空的二叉树的先序遍历序列与后序遍历序列正好相同，则该二叉树一 定满足（ ）。（2.0）A、所有的结点均无左孩子B、所有的结点均无右孩子C、只有一个叶子结点D、是任意一棵二叉树 正确答案： C10、如果F是由有序树T转换而来的二叉树，那么T中结点的前序就是F中结点的（）。（2.0）A、中序B、前序C、后序D、层次序 正确答案：B11、Photoshop 的当前状态为全屏显示，而且未显示工具箱及任何调板，在此情况下，按什么键，能够使其恢复为显示工具箱、调板及标题条的正常工作显示状态。 （）（2.0）A、先按F键，再按Tab键B、先按Tab键，再按F键，但顺序绝对不可以颠倒C、先按两次F键，再按两次Tab键D、先按Ctrl+Shift+F键，再按Tab键 正确答案： A12、在等概率情况下，顺序表的插入操作要移动结点。（2.0）A、全部B、一半C、三分之一D、四分之一 正确答案： B 13、在一个长度为n的顺序表中，在第i个元素（lWiWn+1）之前插入一个新 元素时须向后移动（ ）个元素。（2.0）A、n-iB、n-i+1C、n-i-1D、I正确答案： B14、有一个有序表为1, 3, 9,12，32,41，45，62，75，77，82，95,100 当二分查找值为82 的结点时,_次比较后查找成功。（2.0）A、1B、2C、4D、8正确答案： C15、从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正 确位置上的方法，这种排序方法称为（ ）。（2.0）A、归并排序B、冒泡排序C、插入排序D、选择排序 正确答案： C16、若一个图的边集为（A,B）,（A,C）,（B,D）,（C,F）,（D,E）,（D,F），则从顶点A开始对该图进行深度优先搜索，得到的顶点序列可能为（ ）。（2.0）A、A,B,C,F,D,EB、A,C,F,D,E,BC、A,B,D,C,F,ED、A,B,D,F,E,C 正确答案： B17、用邻接表表示图进行广度优先遍历时，通常借助（ ）来实现算法。（2.0）A、栈B、队列C、树D、图正确答案： B18、下列关键字序列中，（ ）是堆。（2.0）A、16，72，31，23，94，53B、94，23，31，72，16，53C、16，53，23，94，31，72D、16，23，53，31，94，72正确答案： D19、由3个结点可以构造出多少种不同的二叉树？（ ）（2.0）A、2B、3C、4D、5 正确答案： D20、算法分析的目的是（ ）。（2.0）A、找出数据结构的合理性B、研究算法中输入和输出的关系C、分析算法的效率以求改进D、分析算法的易懂性 正确答案： C二、多选题（共 5题，10分）1、在对n个元素进行快速排序的过程中，平均情况下的时间复杂度错误的是（）。（2.0）A、O(1)B、O(log2n)C、O(n2)D、O(nlog2n) 正确答案： ABC2、在对n个元素进行直接插入排序的过程中，算法的空间复杂度错误的是（）。（2.0）A、O(1)B、O(log2n)C、O(n2)D、O(nlog2n) 正确答案： BCD3、数据元素又称为（）。（2.0）A、元素B、结点C、记录D、英文 正确答案： ABC4、数组元素的下标一般具有固定的（），因此它比其他复杂的非线性结构简单。（2.0）A、上界B、下界C、中界D、尾界 正确答案： AB5、在对n个元素进行快速排序的过程中，最坏情况下的时间复杂度错误的是（）。（2.0）A、O（1）B、O（log2n）C、O（n2）D、O（nlog2n） 正确答案： ABD三、判断题（共 10题，20分）1、解决递归问题的策略是把一个规模比较大的问题分解为一个或若干规模比较小的问题，分别对这些比较小的问题求解，再综合它们的结果，从而得到原问题的解。（2.0）正确答案：正确2、队头、队尾指针加1时从maxsSize-1直接进到0,可用语言的取模（余数）运算实现。（2.0）正确答案：正确3、创建一个空集合必须用 set（） （2.0）正确答案：错误4、2.二叉树的前序遍历中,任意结点均处在其子女结点之前。（ ）（2.0）正确答案：正确5、5.由二叉树的先序序列和后序序列可以唯一确定一颗二叉树。（ ）（2.0）正确答案：错误6、只可以使用set（）函数创建集合（2.0）正确答案：错误7、在一般情况下,采用压缩存储之后,对称矩阵是所有特殊矩阵中存储空间节约最多的。（）（2.0）正确答案：错误8、N个元素进队列的顺序和出队列的操作顺序总是一致的（2.0）正确答案：正确9、在查找树（二叉树排序树）中插入一个新结点,总是插入到叶结点下面（2.0）正确答案：错误10、就平均查找长度而言,分块查找最小,折半查找次之,顺序查找最大（2.0）正确答案：错误一、单选题（共 20 题,40 分）1、一棵完全二叉树上有1001个结点,其中叶子结点的个数是（ ）。（2.0）A、250B、500C、254D、501正确答案： D2、对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数最多为（）。（2.0）A、n+1B、nC、n-1D、n（n-1）/2 正确答案： D3、图的BFS生成树的树高比DFS生成树的树高（）。（2.0）A、小B、相等C、小或相等D、大或相等正确答案： C4、设哈希表长为14,哈希函数是H（key）=key%11,表中已有数据的关键字为15, 38, 61, 84共四个，现要将关键字为49的元素加到表中，用二次探测法解决冲突，则放入的位置是（ ）。（2.0）A、8B、3C、5D、9 正确答案： D5、在下列存储形式中,（ ）不是树的存储形式？（2.0）A、双亲表示法B、孩子链表表示法C、孩子兄弟表示法D、顺序存储表示法 正确答案： D6、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为。（2.0）A、rearn= = frontB、front+l= rearC、rear= = frontD、（rear+l）n= front 正确答案： C7、线性表采用链式存储时,其地址。（2.0）A、必须是连续的B、一定是不连续的C、部分地址必须是连续的D、连续与否均可以 正确答案： D 8、已知一个有向图的边集为）。（2.0）, 则由该图产生的一种可能的拓扑序列为（A、a,b,c,d,eB、a,b,d,e,bC、a,c,b,e,dD、a,c,d,b,e正确答案： A9、已知图的邻接矩阵如图6.30所示，则从顶点v0出发按深度优先遍历的结果 是（ ）。图6.30 邻接矩阵（2.0）A、 0 2 4B、0 1 3C、0 1 3D、 0 3 6 1正确答案： C31566542425654210、若对n个元素进行归并排序，则进行归并的趟数为（）。（2.0）A、nB、n-1C、n/2D、log2n正确答案： D 11、数组A中，每个元素的长度为3个字节，行下标i从1到8,列下标j从1 到10,从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A85 的起始地址为（ ）。（2.0）A、SA+141B、SA+144C、SA+222D、SA+225正确答案： C12、在Photoshop中历史记录（History）调板默认的记录步骤是（）（2.0）A、10步B、20步C、30步D、40步 正确答案： B13、从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较个元素结点。 （2. 0）A、n/2B、nC、（n+1）/2D、（n-1）/2 正确答案： C14、若对n个元素进行直接插入排序，在进行第i趟排序时，假定元素ri+1的插入位置为rj, 则需要移动元素的次数为（ ）。（2.0）A、j-iB、i-j-1C、i-jD、i-j+1正确答案：15、若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（ ）图。（2.0）A、非连通B、连通C、强连通D、有向 正确答案： B16、在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（）。（2.0）A、s-next=p+1; p-next=s;B、(*p).nex