数据结构模考试题及答案.docx

《数据结构模考试题及答案.docx》由会员分享，可在线阅读，更多相关《数据结构模考试题及答案.docx（21页珍藏版）》请在第一文库网上搜索。

1、数据结构模考试题及答案一、单选题（共IOO题，每题1分，共100分）1、下面关于生成树的描述中，不正确的是（）A、生成树是树的一种表现形式B、生成树一定是连通的C、生成树一定不含有环D、若生成树顶点个数为n,则其边数一定为n-1正确答案：A2、用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法 的。A、图B、栈C、队列D、树正确答案：C3、下列四种基本的逻辑结构中，结构结点间不存在任何逻辑联系的是 （）A、集合B、树形结构C、图形结构D、线性结构正确答案：A4、以下数据结构中，哪一个是线性结构（）oA、线索二叉树B、二叉树C、有向图D、串正确答案：D5、n个顶点的连通图至少中含有（）边

2、。A n-1B、n+1C nD、0正确答案：A6、G是一个非连通无向图，共有28条边，则该图至少有()个顶点。A、7B、8C、6D、9正确答案：D7、在一个链队列中，假定front和rear分别为队首和队尾指针，则删 除一个结点的操作为()。A、 rear=front-nextB、 front=rear-nextC front=front-nextD、 rear=rear-next正确答案：C8、一个栈的输入序列是1 2 3 4 5,则下列序列中是栈的输出序列的是 ()。A 1, 4, 2, 5, 3B、3, 1,2,4,5C、2, 3, 4, 1,5D 5, 4, 1, 3, 2正确答案：C

3、9、假设以数组Am存放循环队列的元素。已知队列的长度为length, 指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置 为()A、(rear-1 ength+m+1) %mB、(rear-length+m) %mC (rear-1 ength+m-1) %mD、(rear-length) %m正确答案：B10、与数据元素本身的形式、内容、相对位置、个数无关的是数据的 ()。A、存储结构B、操作C、逻辑结构D、算法正确答案：C11、深度为k的完全二叉树中最少有（）个结点。A、 2k-lB、 2k-lC、 2k-l+lD、 2k-l-l正确答案：A12、逻辑上通常可以将数据结构分

4、为（）A、顺序结构和链式结构B、初等结构和组合结构C、线性结构和非线性结构D、动态结构和静态结构正确答案：C13、排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算 法是（）。A、快速排序B、冒泡排序C、插入排序D、选择排序正确答案：C14、设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的 入度为（）。A、第i行非O元素的个数之和B、第i列非O元素的个数之和C、第i行O元素的个数之和D、第i列O元素的个数之和正确答案：B15、由一个具有n个顶点的连通图生成的最小生成树中，具有（）条边。A、n+1B、nC、2nD、n-1正确答案：D16、循环队列是空队列的条件是（）A、 （Q-

5、rear1）%maxsize=-Q-frontB、 Q-rear=0C Q-front=0D Q-rear=Q-front正确答案：D17、数据的四种基本逻辑结构是指（）A、线性结构、链表、树、图形结构B、线性表、链表、栈队列、数组广义表C、数组、链表、树、图形结构D、集合、线性结构、树、图形结构正确答案：D18、设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为 ml, m2和m3与森林F对应的二叉树根结点的右子树上的结点个数是（）。A m2B、 m2+m3C、 ml+m2D m3正确答案：B19、数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称 之为（）。A、顺序存储结构B

6、、存储结构C、逻辑结构D、链式存储结构正确答案：D20、为了有效地利用散列查找技术，主要解决的问题是（）。找一个好 的散列函数。有效地解决冲突。用整数表示关键值A、和B、和C、和D、和正确答案：A21、树的先根序列等同于与该树对应的二叉树的（）A、中序序列B、层序序列C、后序序列D、先序序列正确答案：D22、图的邻接矩阵表示法适用于表示（）A、有向图B、稀疏图C、无向图D、稠密图正确答案：D23、设数据结构 A= （D, R）,其中 D=l, 2, 3, 4, R=r, r=, , 4, 1,则数据结构 A 是（）。A、线性结构B、树型结构C、图型结构D、集合正确答案：C24、队列是一种（）的

7、线性表。A先进先出B、只能插入C、先进后出D、只能删除正确答案：A25、若允许表达式内多种括号混合嵌套，则为检查表达式中括号是否正 确配对的算法，通常选用的辅助结构是（）oA、二叉排序树B、队列C、栈D、线性表正确答案：C26、若进栈次序为a, b, c,且进栈和出栈可以穿插进行，则可能出现的 含3个元素的出栈序列个数是（）A、6B、7C、5D、3正确答案：C27、任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对 次序()oA、不发生改变B、发生改变C、不能确定D、以上都不对正确答案：A28、在一个长度为n的顺序线性表中顺序查找值为X的元素时，查找成 功时的平均查找长度(即X与元素的

8、平均比较次数，假定查找每个元素 的概率都相等)为()。A、(n-l)2B、n/2C、(n+l)2D n正确答案：C29、在一个具有n个结点的有序单链表插入一个新结点并仍然有序的时 间复杂度是()。A、0(1)B、0(n2)C、0(n)D、 0(nlog2n)正确答案：C30、在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链 表的表头指针向量的大小至少为()。A、eBs 2nC、nD、2e正确答案：C31、高度为h的完全二叉树中，结点数最多为()A、2(h-l)B、2%C、 2h+lD、 2h-l正确答案：D32、设输入序列是1、2、3、n,经过栈的作用后输出序列的第一 个元素是n,则

9、输出序列中第i个输出元素是（）oA、 n+1-IB、不能确定C、 n-1-ID、n-I正确答案：A33、一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（）。A edcbaBs abcdeC、 decbaD、 dceab正确答案：D34、在一个具有n个顶点和e条边的有向图的邻接矩阵中，表示边存在 的元素个数为（）。A eB、2eC、nD ne正确答案：A35、下列查找算法中，平均查找长度与元素个数n不直接相关的查找方 法是（）A、二分查找B、顺序查找C、分块查找D、散列查找正确答案：D36、在一个具有n个顶点和e条边的无向图的邻接表中，边结点的个数 为（）。A、neB、nC、2e

10、D、e正确答案：C37、采用顺序存储结构存储的线性表，其首地址为100,每个元素的长度 为2,则第5个元素的地址为（）。A、120B、110C、100D、108正确答案：D38、循环队列A0m-l存放其元素值，分别用front和rear表示队头 和队尾，则当前队列的元素个数是（）。 （rear-front+m）%mB、 rear-front+1C、 rear-front-lD rear-front正确答案：A39、元素大小为1个单元，容量为n个单元的非空顺序栈中，以地址高 端为栈底，以top作为栈顶指针，则出栈处理后，top的值应修改为（） A、 top=topB、 top=top-lC to

11、p=n-lD、 top=top+l正确答案：D40、设某棵二叉树的中序遍历序列为ABCD,前序遍历序列为CABD,则后 序遍历该二叉树得到序列为（）。A、 BADCB、 BCDAC、 CDABD、 CBDA正确答案：A41、对于一个无向图，下面（）种说法是正确的。A、每个顶点的入度等于出度B、每个顶点的度等于其入度与出度之和C、每个顶点的入度为OD、每个顶点的出度为O正确答案：A42、对包含n个元素的散列表进行搜索，平均搜索长度为()A、不直接依赖于nB、上述都不对C、 O (n)D、 O (Iog2n)正确答案：A43、顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为 ()。A、

12、0(nl2)Bs 0(log2n)C、0(n)D、0(n2)正确答案：C44、栈的数组表示中，top为栈顶指针，指向栈顶元素的下一个位置，栈 空的条件是()。A top=-lB、 top=maxSizeC、 top=maxSizeD top=0正确答案：D45、下面程序的时间复杂为()for (i=l, s=0； i=; i+) t=l; for(j=l; j=i; j+) t=t*j; s=s+t; A、0(n3)B、0(n2)C、0(n)D、0(n4)正确答案：B46、若采用邻接矩阵存储一个n个顶点的无向图，则该邻接矩阵是一个 ()。A、对角矩阵B、对称矩阵C、上三角矩阵D、稀疏矩阵正确答

13、案：B47、关于栈和队列的说法中正确的是（）A、栈和队列都是线性结构B、栈和队列都不是线性结构C、栈不是线性结构，队列是线性结构D、栈是线性结构，队列不是线性结构正确答案：A48、下列四种排序中（）的空间复杂度最大。A、希尔排序B、快速排序C、冒泡排序D、堆正确答案：B49、排序方法中，从未排序序列中依次取出元素与已排序序列（初始时 为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法， 称为（）A、希尔排序B、选择排序C、冒泡排序D、插入排序正确答案：D50、数组的逻辑结构不同于下列（）的逻辑结构。A、线性表B、树C、栈D、队列正确答案：B51、在一棵二叉树上第4层的结点数最多为（）

14、。A、2B、6C、4D、8正确答案：D52、在对n个元素进行直接插入排序的过程中，共需要进行（）趟。A 2nBs n+1C、nD、n-1正确答案：D53、设森林F对应的二叉树为B,它有m个结点，B的根为p, p的右子 树结点个数为n,森林F中第一棵子树的结点个数是（）oA m-nB、 m-n-lC、n+1D、条件不足，无法确定正确答案：A54、在下列对顺序表进行的操作中，算法时间复杂度为O（I）的是（）A、对顺序表中元素进行排序B、访问第i个元素的前驱（li=n）C、在第i个元素之后插入一个新元素（k=i*n）D、删除第i个元素（l=i=n）正确答案：B55、设一组权值集合W= 2, 3, 4, 5, 6）,则由该权值集合构造的哈夫曼 树中带权路径长度之和为（）oA、20B、