《数据结构》模拟题一、单项选择题1.假定对称矩阵按行序为主序,顺序存储下三角元素到一维数组 SA[1..n(n-1)/2]中,对下三角中任一元素 aij 在一维数组 SA 中的下标 k 值为().A.i(i-1)/2+j-1B.i(i-1)/2+jC.i(i+1)/2+j-1D.i(i+1)/2+j[答案]:B2.____可作线性表的存储结构.A.循环单链表B.三元组表C.邻接表D.多重链表[答案]:A3.串的长度是().A.串中不同字母的个数B.串中不同字符的个数C.串中所含字符的个数D.串中所含字符的个数,且大于 0[答案]:C4.队列操作的原则是()A.先进先出B.后进先出C.只能进行插入D.只能进行删除[答案]:A5.对长度为 10 的表作选择(简单选择)排序,共需比较____次关键字.A.45B.90C.10D.110[答案]:A6.关于线性表,下列说法正确的是().A.每个元素都有一个直接前驱和直接后继B.线性表中至少要有 2 个元素C.表中元素必须排序D.除第一个和最后一个元素外,其余每个元素都有一个且仅有一个直接前驱和直接后继[答案]:D B.99C.80D.90[答案]:B56.算法的时间复杂度是指算法中()的次数的总和A.语句的读取时间B.语句重复存储的次数C.语句的存储时间D.语句重复执行的次数[答案]:D57.下列排序算法中,某一趟结束后未必能选出一个元素放在其最终位置上的是()A.堆排序B.冒泡排序C.快速排序D.直接插入排序[答案]:D58.线性表在_____时,宜用顺序表作存储结构.A.经常作插入,删除B.经常随机存取C.无足够连续存储空间D.经常作动态查找[答案]:B59.一棵左右子树均不空的二叉树在先序线索化后,其空指针域数为()A.0B.1C.2D.不确定[答案]:B60.已知一颗二叉树的后序遍历序列为 DABEC,中序遍历序列为 DEBAC,则它的先序遍历序列为().A.ACBEDB.DECABC.DEABCD.CEDBA[答案]:D二、判断题1.设串 S 的长度为 n,则 S 的子串个数为 n(n+1)/2[答案]:T 2.从具有 n 个结点的二叉排序树中查找一个元素时,最坏情况下的时间复杂度为 O(n).[答案]:T3.广义表中原子个数即为广义表的长度[答案]:F4.空栈就是所有元素都为 0 的栈.[答案]:F5.设有一个空栈,现有输入序列 1,2,3,4,5,经过 PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH 后,输出序列是 2,3.[答案]:T6.数据元素是数据的最小单位.[答案]:F7.顺序存储结构属于静态结构,链式结构属于动态结构.[答案]:T8.线性表采用链表存储时,结点和结点内部的存储空间可以是不连续的.[答案]:F9.有回路的图不能进行拓扑排序.[答案]:T10.在所有结点的权都相等的情况下,具有平衡特性的二叉排序树一定是最佳二叉排序树.[答案]:T11.n*n 对称矩阵经过压缩存储后占用的存储单元是原来的 1/2.[答案]:F12.广义表是线性表的推广,是一类线性数据结构.[答案]:F13.哈希表的查找效率主要取决于哈希表造表时选取的哈希函数和处理冲突的方法.[答案]:T14.邻接表只能用于存储有向图,而邻接矩阵则可存储有向图和无向图.[答案]:F15.数据的物理结构是指数据在计算机内实际的存储形式.[答案]:T 16.顺序查找法适用于存储结构为顺序或链接存储的线性表.[答案]:T17.完全二叉树中,若一个结点没有左孩子,则它必是树叶.[答案]:T18.一个图的广度优先搜索树是唯一的.[答案]:F19.在单链表中,要访问某个结点,只要知道该结点的指针即可;因此,单链表是一种随机存取结构.[答案]:F20.在线性表的顺序存储结构中,插入和删除元素时,移动元素的个数与该元素的位置有关.[答案]:T21.串是由有限个字符构成的连续序列,串长度为串中字符的个数,子串是主串中字符构成的有限序列.[答案]:F22.广义表是由零或多个原子或子表所组成的有限序列,所以广义表可能为空表.[答案]:T23.就平均查找长度而言,分块查找最小,折半查找次之,顺序查找最大.[答案]:F24.任何 AOV 网拓扑排序的结果都是唯一的.[答案]:F25.数据项是数据的基本单位.[答案]:F26.顺序存储的线性表可以随机存取.[答案]:T27.稀疏矩阵压缩存储后,必会失去随机存取功能.[答案]:T28.用带表头结点的单链表表示队列,则判断队列为空的标准是头指针和尾指针均指向同一个结点.[答案]:T29.在二叉排序树上删除一个结点时,不必移动其他结点,只要将该结点的父结点的相应指针域置空即可. [答案]:F30.栈和队列都是限制存取点的线性结构[答案]:T三、名词解释1.串[答案]:串是有零个或多个字符组成的优先序列.2.关键字[答案]:关键字是数据元素中某个数据项的值,用它可以标识一个数据元素或记录.3.数据项,记录和文件.[答案]:一个元素可以有若干个数据项组成,通常把数据元素称为记录,含有大量记录的线性表称为文件.4.线性表[答案]:线性表是最常用且最简单的一种数据结构,是 n 个数据元素的有限序列.5.队列[答案]:队列也是线性表,它是操作受限制的线性表,队列是先进先出表.6.树[答案]:树型结构是一类重要的非线性数据结构,树是以分支关系定义的层次结构.7.数组[答案]:数组在内存中占据连续的存储单元,其数组元素具有相同的名字和类型.8.栈[答案]:栈也是线性表,它是操作受限制的线性表,栈是后进先出表.9.二叉树[答案]:二叉树的每个结点至多只有两棵子树,并且,二叉树的子树有左右之分,其次序不能任意颠倒.10.数据结构[答案]:数据结构是相互之间存在一种或多种特定关系的数据元素的 xxx.11.图[答案]:图形结构中,结点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关.12.内部排序方法[答案]:直接插入,折半插入,2-路插入,表插入,希尔排序,起泡排序,快速排序,选择排序,树形排序,堆排序,归并,基数.任选 5 个. 7.假设用 Q[0..maxleng-1]表示循环队列,f 为队头指针,r 为队尾指针,则进队操作的语句是().A.f=f+1B.r=r+1C.f=(f+1)%maxlengD.r=(r+1)%maxleng[答案]:D8.两个串相等的判定条件是().A.串为空B.串中各位置对应字符相等C.串长度相等D.串长度相等并且串中各位置对应字符相等[答案]:D9.若 7 行 6 列的数组 a 以列序为主序顺序存储,基地址为 1024,每个元素占 2 个存储单元,则第3 行第 5 列的元素(假定无第 0 行第 0 列)的存储地址是____.A.1100B.1086C.1084D.答案 A,B,C 都不对[答案]:C10.若进队列的序列为 1,2,3,4,则()是一个出队列序列.A.1234B.4321C.4312D.3214[答案]:A11.若用一个大小为 6 的数组来实现循环队列,且当 rear 和 front 的值分别为 0 和 3.当从队列中删除一个元素,再加入两个元素后,rear 和 front 的值分别为().A.1 和 5B.2 和 4C.4 和 2D.5 和 1[答案]:B12.设计一个判定表达式中左,右括号是否配对出现的算法,采用()数据结构最佳.A.链表B.线性表C.队列D.栈[答案]:D 13.设语句 s=s+i 的时间是时间单位,则语句:s=0;for(i=1;i<=n;i++)s=s+i;的时间复杂度为().A.O(1)B.O(n)C.O(n2)D.O(log2n)[答案]:B14.数据表 A 中有 10000 个元素,如果仅要求求出其中最大的 10 个元素,则采用()排序算法最节省时间.A.堆排序B.希尔排序C.快速排序D.直接选择排序[答案]:C15.数组 A 中,每个元素的长度为 3 个字节,行下标 i 从 1 到 5,列下标 j 从 1 到 4,从首地址 SA 开始连续存放在存储器内,该数组占用的字节数为().A.20B.60C.80D.120[答案]:B16.顺序栈存储空间的实现使用()存储栈元素.A.链表B.循环链表C.数组D.变量[答案]:C17.为了方便对图状结构的数据进行存取操作,则其中数据存储结构宜采用().A.顺序存储B.链式存储C.索引存储D.散列存储[答案]:B18.下列有关二叉树的说法正确的是().A.二叉树的度为 2B.一棵二叉树度可以小于 2C.二叉树中至少有一个结点的度为 2D.二叉树中任一个结点的度都为 2[答案]:B 19.循环队列中元素数目是()?其中 tail=32,指向队尾元素,head=15 指向对头元素的前一个空位置,队列空间 m=60.A.42B.16C.17D.41[答案]:C20.一颗非空的二叉树的先序遍历序列与后序遍历序列正好相反,则该二叉树一定满足().A.只有一个叶子结点B.所有的结点均无左孩子C.左右的结点均无右孩子D.是任意一颗二叉树[答案]:A21.线性表的静态链表存储结构与顺序存储结构相比优点是A.便于随机存取B.便于插入和删除C.便于利用零散的存储器空间D.所有的操作算法实现简单[答案]:B22.____是'Hua**Zhong**Da'的子串.A.HuaB.zhongC.'*Da'D.'HuaZhongDa'[答案]:C23.串是任意有限个().A.符号构成的 xxxB.符号构成的序列C.字符构成的 xxxD.字符构成的序列[答案]:D24.队列的特点是().A.先进先出B.后进先出C.进优于出D.出优于进[答案]:A 25.二叉树在线索化后,仍不能有效求解的问题是()A.先序线索二叉树中求先序后继B.中序线索二叉树中求中序后继C.中序线索二叉树中求中序前趋D.后序线索二叉树中求后序后继[答案]:D26.广义表 A=(a,b,(c,d),(e,(f,g))),则下面式子的值为().Head(Tail(Head(Tail(Tail(A))))).A.(g)B.(d)C.cD.d[答案]:D27.将一个 A[1..10,1..10]的三对角矩阵,按行优先存入一维数组 B[1,30]中,A 中元素 a6,5 在 B数组中的位置 i 为().A.15B.16C.55D.56[答案]:A28.两个指针 p 和 q,分别指向单链表的两个元素,p 所指元素是 q 所指元素的前驱,则().A.p==qB.q->next=pC.p->next=q->nextD.p->next=q[答案]:D29.若串 s="hello",其子串个数是().A.5B.15C.16D.25[答案]:B30.若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点,则采用()存储方式最节省时间.A.单链表B.双链表C.带头结点的双循环链表D.单循环链表[答案]:C 31.若长度为 n 的线性表采用顺序存储结构,在其第 i 个位置插入一个新元素算法的时间复杂度为().A.O(1)B.O(n)C.O(n2)D.O(log2n)[答案]:B32.设循环队列中数组的下标范围是 1~n,其头尾指针分别为 f 和 r,则其元素个数为()A.r-fB.r-f+1C.(r-f)modn+1D.(r-f+n)modn[答案]:D33.设栈的输入序列是(1,2,3,4),则()不可能是其出栈序列.A.1234B.2134C.4312D.3214[答案]:C34.数据结构包含四种基本结构,它们是().A.xxx,链表,树,队列B.队列,链表,数组,图C.xxx,线性,树,图D.线性,链表,队列,xxx[答案]:C35.数组 A 中,每个元素的长度为 4 个字节,行下标 i 从 1 到 5,列下标 j 从 1 到 4,从首地址 SA 开始连续存放在存储器内,该数组按行存放时,元素 A[3][2]的起始地址为().A.SA+5B.SA+10C.SA+36D.SA+40[答案]:C36.算法必须具备的 5 个特征是:输入,输出,().A.可执行性,可移植性和可扩充性B.可执行性,有穷性和确定性C.有穷性,稳定性和确定性D.稳定性,易读性和确定性[答案]:B 37.稀疏矩阵一般的压缩存储方法有()两种.A.二维数组和三维数组B.二维数组和三元组C.三维数组和十字链表D.三元组和十字链表[答案]:D38.线性表采用链式存储时,其地址().A.必须是连续的B.一定是不连续的C.连续与否均可以D.部分地址必须是连续的[答案]:C39.一个 n*n 的对称矩阵,如果以行或列为主序放入内存,则其容量为().A.n*nB.n*n/2C.n*(n+1)/2D.(n+1)*(n+1)/2[答案]:C40.已知一个顺序存储的线性表,设每个结点需占 m 个存储单元,若第一个结点的地址为 d1,则第 i 个结点的地址为().A.d1+(i-1)*mB.d1+i*mC.d1-i*mD.d1+(i+1)m[答案]:A41._____是数据的不可分割的最小单位.A.元素B.数据元素C.数据类型D.数据项[答案]:D42.D=(a,(b,c)),则 tail(D)=().A.b,cB.(b,c)C.((b,c))D.c[答案]:C43.带头结点的单链表为空表的条件是(). A.head==NULLB.head->data==NULLC.head->next==NULLD.head->prior==NULL[答案]:C44.对有 18 个元素的有序表作二分(折半)查找,则查找 A[3]的比较序列的下标为().A.1,2,3B.9,5,2,3C.9,5,3D.9,4,2,3[答案]:D45.二维数组 A[1..5,1..6],若 A 按行先存储时元素 A[3,2]的起始地址与当 A 按列存储时的()元素的起始地址相同.A.A[2,3]B.A[3,3]C.A[4,3]D.A[5,3][答案]:C46.假定一个顺序循环队列存储于数组 A[n]中,其队首和队尾指针分别用 front 和 rear 表示,则判断队满的条件是().A.(rear-1)%n==frontB.(rear+1)%n==frontC.rear==(front-1)%nD.rear==(front+1)%n[答案]:B47.链表不具有的特点是().A.可随机访问任一元素B.插入删除不需要移动元素C.不必事先考虑存储空间D.所需空间与线性表长度成正比[答案]:A48.如果线性表最常用的操作是存取第 i 个元素及其前驱的值,则采用()方式存储节省时间.A.单链表B.双链表C.顺序表D.头尾循环链表[答案]:C49.若串 S="software",其子串数目是(). A.8B.37C.36D.9[答案]:C50.若用单链表来表示队列,则应该选用().A.带头指针的非循环链表B.带尾指针的非循环链表C.带头指针的循环链表D.带尾指针的循环链表[答案]:D51.设广义表 LS=((a,b),c,(d,e)),执行操作 GetTail(GetHead(LS))后的结果是_______.A.(b)B.bC.(c,(d,e))D.(a,b)[答案]:A52.设有广义表 D=((),((),())),则广义表的长度为().A.2B.3C.4D.∞[答案]:A53.树最适合用来表示().A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据[答案]:C54.数组 A［５］［６］的每个元素占 5 个单元,将其按行优先次序存储在起始地址为 1000的连续的内存单元中,则元素 A［５,５］的地址为()A.1140B.1145C.1120D.1125[答案]:A55.数组 SZ[-3…5,0…10]含有元素数目为().A.88