《中国地质大学-数据结构-模拟题.docx》由会员分享，可在线阅读，更多相关《中国地质大学-数据结构-模拟题.docx（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构模拟题一、单项选择题1 .假定对称矩阵按行序为主序，顺序存储下三角元素到一维数组SAL.n(n-l)/2中，对下三角 中任一元素aij在一维数组SA中的下标k值为0.A.i(i-l)/2+j-lB.i(i-l)/2+jC.i(i+l)/2+j-lD.i(i+l)/2+j答案:B.可作线性表的存储结构.A.循环单链表B.三元组表C邻接表D.多重链表答案:A.串的长度是0.A.串中不同字母的个数B.串中不同字符的个数C.串中所含字符的个数D.串中所含字符的个数,且大于0答案:C.队列操作的原那么是()A.先进先出B.后进先出C.只能进行插入D.只能进行删除答案:A.对长度为10的表作选择(
2、简单项选择择)排序，共需比拟一次关键字.A.45B.90C.10D.110答案:A.关于线性表，以下说法正确的选项是().A.每个元素都有一个直接前驱和直接后继B.线性表中至少要有2个元素C.表中元素必须排序D.除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继答案:DB.99C.80D.90答案:B56 .算法的时间复杂度是指算法中()的次数的总和A.语句的读取时间B.语句重复存储的次数C语句的存储时间D.语句重复执行的次数答案:D.以下排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是()A.堆排序B.冒泡排序C.快速排序D.直接插入排序答案:D.线性表
3、在 时，宜用顺序表作存储结构.A.经常作插入，删除B.经常随机存取C.无足够连续存储空间D.经常作动态查找答案:B.一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为()A.0B.1C.2D.不确定答案:B.一颗二叉树的后序遍历序列为DABEC,中序遍历序列为DEBAC,那么它的先序遍历序 列为。A.ACBEDB.DECABC.DEABCD.CEDBA答案:D 二、判断题.设串S的长度为n,那么S的子串个数为n(n+l)/2答案:T.从具有n个结点的二叉排序树中查找一个元素时,最坏情况下的时间复杂度为O(n).答案:T.广义表中原子个数即为广义表的长度答案:F.空栈就是所有元素都为0的栈
4、.答案:F.设有一个空栈,现有输入序列 1,2,3,4,5,经过 PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH 后, 输出序列是2,3.答案:T.数据元素是数据的最小单位.答案:F.顺序存储结构属于静态结构，链式结构属于动态结构.答案:T.线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的.答案:F.有回路的图不能进行拓扑排序.答案:T.在所有结点的权都相等的情况下，具有平衡特性的二叉排序树一定是最正确二叉排序树.答案:TH.n*n对称矩阵经过压缩存储后占用的存储单元是原来的1/2.答案:F.广义表是线性表的推广，是一类线性数据结构.答案:F.哈希表的查找效率主要
5、取决于哈希表造表时选取的哈希函数和处理冲突的方法.答案:T.邻接表只能用于存储有向图，而邻接矩阵那么可存储有向图和无向图.答案:F.数据的物理结构是指数据在计算机内实际的存储形式.答案:T.顺序查找法适用于存储结构为顺序或链接存储的线性表.答案:T.完全二叉树中，假设一个结点没有左孩子，那么它必是树叶.答案:T.一个图的广度优先搜索树是唯一的.答案:F.在单链表中，要访问某个结点，只要知道该结点的指针即可;因此，单链表是一种随机存取结 构.答案:F.在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关.答案:T.串是由有限个字符构成的连续序列，串长度为串中字符的个数，子
6、串是主串中字符构成的 有限序列.答案:F.广义表是由零或多个原子或子表所组成的有限序列，所以广义表可能为空表.答案:T.就平均查找长度而言，分块查找最小,折半查找次之，顺序查找最大.答案:F.任何AOV网拓扑排序的结果都是唯一的.答案:F.数据项是数据的基本单位.答案:F.顺序存储的线性表可以随机存取.答案:T.稀疏矩阵压缩存储后，必会失去随机存取功能.答案:T.用带表头结点的单链表表示队列，那么判断队列为空的标准是头指针和尾指针均指向同一个 结点.答案:T.在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点的父结点的相应指针 域置空即可.答案:F.栈和队列都是限制存取点的线性结构答
7、案:T三、名词解释1 .串答案:串是有零个或多个字符组成的优先序列.2 .关键字答案:关键字是数据元素中某个数据项的值，用它可以标识一个数据元素或记录.3 .数据项,记录和文件.答案:一个元素可以有假设干个数据项组成，通常把数据元素称为记录，含有大量记录的线性表 称为文件.4 .线性表答案:线性表是最常用且最简单的一种数据结构，是n个数据元素的有限序列.5 .队列答案:队列也是线性表，它是操作受限制的线性表，队列是先进先出表.6 .树答案:树型结构是一类重要的非线性数据结构,树是以分支关系定义的层次结构.7 ,数组答案:数组在内存中占据连续的存储单元，其数组元素具有相同的名字和类型.8 .栈答
8、案:栈也是线性表，它是操作受限制的线性表，栈是后进先出表.9 .二叉树答案:二叉树的每个结点至多只有两棵子树，并且，二叉树的子树有左右之分，其次序不能任 意颠倒.10 .数据结构答案:数据结构是相互之间存在一种或多种特定关系的数据元素的XXX.U.S答案:图形结构中，结点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关.12 .内部排序方法答案:直接插入，折半插入,2-路插入，表插入，希尔排序，起泡排序，快速排序，选择排序,树形排 序,堆排序，归并，基数.任选5个.7 .假设用QO.maxleng-l表示循环队列,f为队头指针,r为队尾指针,那么进队操作的语句是().A.f=f+1B
9、.r=r+1C.f=(f+ l)%maxlengD.r=(r+ l)%maxleng答案:D.两个串相等的判定条件是().A.串为空B.串中各位置对应字符相等C.串长度相等D.串长度相等并且串中各位置对应字符相等答案:D.假设7行6列的数组a以列序为主序顺序存储，基地址为1024,每个元素占2个存储单元，那么第 3行第5列的元素(假定无第0行第0歹U)的存储地址是A.1100B.1086C.1084D.答案A,B,C都不对答案:C.假设进队列的序列为1,2,34那么()是一个出队列序列.A.1234B.4321C.4312D.3214答案:A.假设用一个大小为6的数组来实现循环队列，且当rea
10、r和front的值分别为0和3.当从队列中 删除一个元素，再加入两个元素后,rear和front的值分别为().A.1 和 5B.2 和 4C.4 和 2D.5 和 1答案:B.设计一个判定表达式中左，右括号是否配对出现的算法，采用()数据结构最正确.A.链表B.线性表C.队列D.栈答案:D.设语句s=s+i的时间是时间单位，那么语句:s=0;for(i=l;iv=n;i+)s=s+i;的时间复杂度为().A.O(l)B.O(n)C.O(n2)D.O(log2n)答案:B.数据表A中有10000个元素，如果仅要求求出其中最大的10个元素，那么采用()排序算法最 节省时间.A.堆排序B.希尔排序
11、C快速排序D.直接选择排序答案:C.数组A中，每个元素的长度为3个字节，行下标i从1到5,列下标j从1到4,从首地址SA 开始连续存放在存储器内，该数组占用的字节数为().A.20B.60C.80D.120答案:B.顺序栈存储空间的实现使用()存储栈元素.A.链表B.循环链表C数组D.变量答案:C.为了方便对图状结构的数据进行存取操作,那么其中数据存储结构宜采用0.A.顺序存储B.链式存储C.索引存储D.散列存储答案:B.以下有关二叉树的说法正确的选项是().A.二叉树的度为2B.一棵二叉树度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任一个结点的度都为2答案:B.循环队列中元素数
12、目是()?其中tail=32,指向队尾元素,head=15指向对头元素的前一个空位 置，队列空间m=60.A.42B.16C.17D.41答案:C.一颗非空的二叉树的先序遍历序列与后序遍历序列正好相反，那么该二叉树一定满足().A.只有一个叶子结点B.所有的结点均无左孩子C.左右的结点均无右孩子D.是任意一颗二叉树答案:A.线性表的静态链表存储结构与顺序存储结构相比优点是A.便于随机存取B.便于插入和删除C.便于利用零散的存储器空间D.所有的操作算法实现简单答案:B.是Hua*Zhong*D4的子串.A.HuaB.zhongC.DaD.HuaZhongDa答案:C.串是任意有限个().A.符号
13、构成的xxxB.符号构成的序列C.字符构成的xxxD.字符构成的序列答案:D.队列的特点是().A.先进先出B.后进先出C.进优于出D.出优于进答案:A.二叉树在线索化后，仍不能有效求解的问题是()A.先序线索二叉树中求先序后继B.中序线索二叉树中求中序后继C.中序线索二叉树中求中序前趋D.后序线索二叉树中求后序后继答案:D.广义表 A=(a,b,(c,d),(e,(f,g),那么下面式子的值为().Head(Tail(Head(Tail(Tail(A).A.(g)B.(d)C.cD.d答案:D.将一个AL.101.10的三对角矩阵，按行优先存入一维数组Bl,30中,A中元素a6,5在B 数组
14、中的位置i为().A.15B.16C.55D.56答案:A.两个指针p和q,分别指向单链表的两个元素,p所指元素是q所指元素的前驱，那么A.p=qB.q-next=pC.p-next=q-nextD.p-next=q答案:D.假设串s二heUo”,其子串个数是A.5B.15C.16D.25答案:B.假设某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，那么采用 ()存储方式最节省时间.A.单链表B.双链表C带头结点的双循环链表D.单循环链表答案:C.假设长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂 度为().A.O(l)B.O(n)C.O(n
15、2)D.O(log2n)答案:B.设循环队列中数组的下标范围是1n,其头尾指针分别为f和r,那么其元素个数为0A.r-fB.r-f+1C.(r-f)modn+lD.(r-f+n)modn答案:D.设栈的输入序列是(1,2,3,4),那么()不可能是其出栈序列.A.1234B.2134C.4312D.3214答案:C.数据结构包含四种基本结构,它们是0.A.xxx,链表，树，队列B.队歹U,链表，数组，图C.xxx,线性，树，图D.线性，链表，队列,xxx答案:C.数组A中，每个元素的长度为4个字节，行下标i从1到5,列下标j从1到4,从首地址SA 开始连续存放在存储器内，该数组按行存放时，元素
16、A的起始地址为().A.SA+5B.SA+10C.SA+36D.SA+40答案:C.算法必须具备的5个特征是:输入，输出,().A.可执行性，可移植性和可扩充性B.可执行性，有穷性和确定性C有穷性，稳定性和确定性D.稳定性，易读性和确定性答案:B37 .稀疏矩阵一般的压缩存储方法有()两种.A.二维数组和三维数组B.二维数组和三元组C.三维数组和十字链表D.三元组和十字链表答案:D38.线性表采用链式存储时,其地址().A.必须是连续的B.一定是不连续的C.连续与否均可以D.局部地址必须是连续的答案:C.一个n*n的对称矩阵，如果以行或列为主序放入内存，那么其容量为().A.n*nB.n*n/
17、2C.n*(n+l)/2D.(n+l)*(n+l)/2答案:C.一个顺序存储的线性表，设每个结点需占m个存储单元，假设第一个结点的地址为dl,那么 第i个结点的地址为().A.dl+(i-l)*mB.dl+i*mC.dl-imD.dl+(i+l)m答案:A.是数据的不可分割的最小单位.A.元素B.数据元素C.数据类型D.数据项答案:D.D=(a,(b,c),那么 tail(D)=().A.b,cB.(b,c)C.(b,c)D.c答案:C.带头结点的单链表为空表的条件是0.A.head=NULLB .head-data=NULLC.head-next=NULLD.head-prior=NULL答
18、案:C44,对有18个元素的有序表作二分(折半)查找,那么查找A3的比拟序列的下标为().A. 1,2,3B.9,5,2,3C.9,5,3D.9,4,2,3答案:D.二维数组AL.5,L.6,假设A按行先存储时元素A3,2的起始地址与当A按列存储时的。元 素的起始地址相同.A.A2,3B.A3,3C.A4,3D.A5,3答案:C.假定一个顺序循环队列存储于数组An中，其队首和队尾指针分别用front和rear表示，那么 判断队满的条件是().A.(rear-1 )%n=frontB.(rear+ l)%n=frontC.rear=(front-1 )%nD.rear=(front+ l)%n答
19、案:B.链表不具有的特点是().A.可随机访问任一元素B.插入删除不需要移动元素C.不必事先考虑存储空间D.所需空间与线性表长度成正比答案:A.如果线性表最常用的操作是存取第i个元素及其前驱的值，那么采用()方式存储节省时间.A.单链表B.双链表C顺序表D.头尾循环链表答案:C.假设串S二software”淇子串数目是().A.8B.37C.36D.9答案:C.假设用单链表来表示队列，那么应该选用().A.带头指针的非循环链表B.带尾指针的非循环链表C带头指针的循环链表D.带尾指针的循环链表答案:D.设广义表 LS=(a,b),c,(d,e),执行操作 GetTail(GetHead(LS)后的结果是.A.(b)B.bC.(c,(d,e)D.(a,b)答案:A.设有广义表D=(),(),(),那么广义表的长度为().A.2B.3C.4D.oo答案:A.树最适合用来表示().A.有序数据元素B.无序数据元素C元素之间具有分支层次关系的数据D.元素之间无联系的数据答案:C.数组A 5 6的每个元素占5个单元，将其按行优先次序存储在起始地址为1000 的连续的内存单元中，那么元素A 5,5的地址为()A.1140B.1145C.1120D.1125答案:A.数组SZ-3.5,0.10含有元素数目为().A.88