二叉排序树查找序列_二叉排序树查找序列不可能

数据结构
　　一、单项选择题

　　1.假定对称矩阵按行序为主序,顺序存储下三角元素到一维数组SA[1..n(n-1)/2]中,对下三角中任一元素aij在一维数组SA中的下标k值为().

　　A.i(i-1)/2+j-1

　　B.i(i-1)/2+j

　　C.i(i+1)/2+j-1

　　D.i(i+1)/2+j

　　[答案]:B

　　2.____可作线性表的存储结构.

　　A.循环单链表

　　B.三元组表

　　C.邻接表

　　D.多重链表

　　[答案]:A

　　3.串的长度是().

　　A.串中不同字母的个数

　　B.串中不同字符的个数

　　C.串中所含字符的个数

　　D.串中所含字符的个数,且大于0

　　[答案]:C

　　4.队列操作的原则是()

　　A.先进先出

　　B.后进先出

　　C.只能进行插入

　　D.只能进行删除

　　[答案]:A

　　5.对长度为10的表作选择(简单选择)排序,共需比较____次关键字.

　　A.45

　　B.90

　　C.10

　　D.110

　　[答案]:A

　　6.关于线性表,下列说法正确的是().

　　A.每个元素都有一个直接前驱和直接后继

　　B.线性表中至少要有2个元素

　　C.表中元素必须排序

　　D.除第一个和最后一个元素外,其余每个元素都有一个且仅有一个直接前驱和直接后继

　　[答案]:D

　　7.假设用Q[0..maxleng-1]表示循环队列,f为队头指针,r为队尾指针,则进队操作的语句是().

　　A.f=f+1

　　B.r=r+1

　　C.f=(f+1)%maxleng

　　D.r=(r+1)%maxleng

　　[答案]:D

　　8.两个串相等的判定条件是().

　　A.串为空

　　B.串中各位置对应字符相等

　　C.串长度相等

　　D.串长度相等并且串中各位置对应字符相等

　　[答案]:D

　　9.若7行6列的数组a以列序为主序顺序存储,基地址为1024,每个元素占2个存储单元,则第3行第5列的元素(假定无第0行第0列)的存储地址是____.

　　A.1100

　　B.1086

　　C.1084

　　D.答案A,B,C都不对

　　[答案]:C

　　10.若进队列的序列为1,2,3,4,则()是一个出队列序列.

　　A.1234

　　B.4321

　　C.4312

　　D.3214

　　[答案]:A

　　11.若用一个大小为6的数组来实现循环队列,且当rear和front的值分别为0和3.当从队列中删除一个元素,再加入两个元素后,rear和front的值分别为().

　　A.1和5

　　B.2和4

　　C.4和2

　　D.5和1

　　[答案]:B

　　12.设计一个判定表达式中左,右括号是否配对出现的算法,采用()数据结构最佳.

　　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)

　　[答案]:B

　　14.数据表A中有10000个元素,如果仅要求求出其中最大的10个元素,则采用()排序算法最节省时间.

　　A.堆排序

　　B.希尔排序

　　C.快速排序

　　D.直接选择排序

　　[答案]:C

　　15.数组A中,每个元素的长度为3个字节,行下标i从1到5,列下标j从1到4,从首地址SA开始连续存放在存储器内,该数组占用的字节数为().

　　A.20

　　B.60

　　C.80

　　D.120

　　[答案]:B

　　16.顺序栈存储空间的实现使用()存储栈元素.

　　A.链表

　　B.循环链表

　　C.数组

　　D.变量

　　[答案]:C

　　17.为了方便对图状结构的数据进行存取操作,则其中数据存储结构宜采用().

　　A.顺序存储

　　B.链式存储

　　C.索引存储

　　D.散列存储

　　[答案]:B

　　18.下列有关二叉树的说法正确的是().

　　A.二叉树的度为2

　　B.一棵二叉树度可以小于2

　　C.二叉树中至少有一个结点的度为2

　　D.二叉树中任一个结点的度都为2

　　[答案]:B

　　19.循环队列中元素数目是()?其中tail=32,指向队尾元素,head=15指向对头元素的前一个空位置,队列空间m=60.

　　A.42

　　B.16

　　C.17

　　D.41

　　[答案]:C

　　20.一颗非空的二叉树的先序遍历序列与后序遍历序列正好相反,则该二叉树一定满足().

　　A.只有一个叶子结点

　　B.所有的结点均无左孩子

　　C.左右的结点均无右孩子

　　D.是任意一颗二叉树

　　[答案]:A

　　21.线性表的静态链表存储结构与顺序存储结构相比优点是

　　A.便于随机存取

　　B.便于插入和删除

　　C.便于利用零散的存储器空间

　　D.所有的操作算法实现简单

　　[答案]:B

　　22.____是'Hua**Zhong**Da'的子串.

　　A.Hua

　　B.zhong

　　C.'*Da'

　　D.'HuaZhongDa'

　　[答案]:C

　　23.串是任意有限个().

　　A.符号构成的xxx

　　B.符号构成的序列

　　C.字符构成的xxx

　　D.字符构成的序列

　　[答案]:D

　　24.队列的特点是().

　　A.先进先出

　　B.后进先出

　　C.进优于出

　　D.出优于进

　　[答案]:A

　　25.二叉树在线索化后,仍不能有效求解的问题是()

　　A.先序线索二叉树中求先序后继

　　B.中序线索二叉树中求中序后继

　　C.中序线索二叉树中求中序前趋

　　D.后序线索二叉树中求后序后继

　　[答案]:D

　　26.广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为().Head(Tail(Head(Tail(Tail(A))))).

　　A.(g)

　　B.(d)

　　C.c

　　D.d

　　[答案]:D

　　27.将一个A[1..10,1..10]的三对角矩阵,按行优先存入一维数组B[1,30]中,A中元素a6,5在B数组中的位置i为().

　　A.15

　　B.16

　　C.55

　　D.56

　　[答案]:A

　　28.两个指针p和q,分别指向单链表的两个元素,p所指元素是q所指元素的前驱,则().

　　A.p==q

　　B.q->next=p

　　C.p->next=q->next

　　D.p->next=q

　　[答案]:D

　　29.若串s="hello",其子串个数是().

　　A.5

　　B.15

　　C.16

　　D.25

　　[答案]:B

　　30.若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点,则采用()存储方式最节省时间.

　　A.单链表

　　B.双链表

　　C.带头结点的双循环链表

　　D.单循环链表

　　[答案]:C

　　31.若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素算法的时间复杂度为().

　　A.O(1)

　　B.O(n)

　　C.O(n2)

　　D.O(log2n)

　　[答案]:B

　　32.设循环队列中数组的下标范围是1~n,其头尾指针分别为f和r,则其元素个数为()

　　A.r-f

　　B.r-f+1

　　C.(r-f)modn+1

　　D.(r-f+n)modn

　　[答案]:D

　　33.设栈的输入序列是(1,2,3,4),则()不可能是其出栈序列.

　　A.1234

　　B.2134

　　C.4312

　　D.3214

　　[答案]:C

　　34.数据结构包含四种基本结构,它们是().

　　A.xxx,链表,树,队列

　　B.队列,链表,数组,图

　　C.xxx,线性,树,图

　　D.线性,链表,队列,xxx

　　[答案]:C

　　35.数组A中,每个元素的长度为4个字节,行下标i从1到5,列下标j从1到4,从首地址SA开始连续存放在存储器内,该数组按行存放时,元素A[3][2]的起始地址为().

　　A.SA+5

　　B.SA+10

　　C.SA+36

　　D.SA+40

　　[答案]:C

　　36.算法必须具备的5个特征是:输入,输出,().

　　A.可执行性,可移植性和可扩充性

　　B.可执行性,有穷性和确定性

　　C.有穷性,稳定性和确定性

　　D.稳定性,易读性和确定性

　　[答案]:B

　　37.稀疏矩阵一般的压缩存储方法有()两种.

　　A.二维数组和三维数组

　　B.二维数组和三元组

　　C.三维数组和十字链表

　　D.三元组和十字链表

　　[答案]:D

　　38.线性表采用链式存储时,其地址().

　　A.必须是连续的

　　B.一定是不连续的

　　C.连续与否均可以

　　D.部分地址必须是连续的

　　[答案]:C

　　39.一个n*n的对称矩阵,如果以行或列为主序放入内存,则其容量为().

　　A.n*n

　　B.n*n/2

　　C.n*(n+1)/2

　　D.(n+1)*(n+1)/2

　　[答案]:C

　　40.已知一个顺序存储的线性表,设每个结点需占m个存储单元,若第一个结点的地址为d1,则第i个结点的地址为().

　　A.d1+(i-1)*m

　　B.d1+i*m

　　C.d1-i*m

　　D.d1+(i+1)m

　　[答案]:A

　　41._____是数据的不可分割的最小单位.

　　A.元素

　　B.数据元素

　　C.数据类型

　　D.数据项

　　[答案]:D

　　42.D=(a,(b,c)),则tail(D)=().

　　A.b,c

　　B.(b,c)

　　C.((b,c))

　　D.c

　　[答案]:C

　　43.带头结点的单链表为空表的条件是().

　　A.head==NULL

　　B.head->data==NULL

　　C.head->next==NULL

　　D.head->prior==NULL

　　[答案]:C

　　44.对有18个元素的有序表作二分(折半)查找,则查找A[3]的比较序列的下标为().

　　A.1,2,3

　　B.9,5,2,3

　　C.9,5,3

　　D.9,4,2,3

　　[答案]:D

　　45.二维数组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]

　　[答案]:C

　　46.假定一个顺序循环队列存储于数组A[n]中,其队首和队尾指针分别用front和rear表示,则判断队满的条件是().

　　A.(rear-1)%n==front

　　B.(rear+1)%n==front

　　C.rear==(front-1)%n

　　D.rear==(front+1)%n

　　[答案]:B

　　47.链表不具有的特点是().

　　A.可随机访问任一元素

　　B.插入删除不需要移动元素

　　C.不必事先考虑存储空间

　　D.所需空间与线性表长度成正比

　　[答案]:A

　　48.如果线性表最常用的操作是存取第i个元素及其前驱的值,则采用()方式存储节省时间.

　　A.单链表

　　B.双链表

　　C.顺序表

　　D.头尾循环链表

　　[答案]:C

　　49.若串S="software",其子串数目是().

　　A.8

　　B.37

　　C.36

　　D.9

　　[答案]:C

　　50.若用单链表来表示队列,则应该选用().

　　A.带头指针的非循环链表

　　B.带尾指针的非循环链表

　　C.带头指针的循环链表

　　D.带尾指针的循环链表

　　[答案]:D

　　51.设广义表LS=((a,b),c,(d,e)),执行操作GetTail(GetHead(LS))后的结果是_______.

　　A.(b)

　　B.b

　　C.(c,(d,e))

　　D.(a,b)

　　[答案]:A

　　52.设有广义表D=((),((),())),则广义表的长度为().

　　A.2

　　B.3

　　C.4

　　D.∞

　　[答案]:A

　　53.树最适合用来表示().

　　A.有序数据元素

　　B.无序数据元素

　　C.元素之间具有分支层次关系的数据

　　D.元素之间无联系的数据

　　[答案]:C

　　54.数组A［５］［６］的每个元素占5个单元,将其按行优先次序存储在起始地址为1000的连续的内存单元中,则元素A［５,５］的地址为()

　　A.1140

　　B.1145

　　C.1120

　　D.1125

　　[答案]:A

　　55.数组SZ[-3…5,0…10]含有元素数目为().

　　A.88

　　B.99

　　C.80

　　D.90

　　[答案]:B

　　56.算法的时间复杂度是指算法中()的次数的总和

　　A.语句的读取时间

　　B.语句重复存储的次数

　　C.语句的存储时间

　　D.语句重复执行的次数

　　[答案]:D

　　57.下列排序算法中,某一趟结束后未必能选出一个元素放在其最终位置上的是()

　　A.堆排序

　　B.冒泡排序

　　C.快速排序

　　D.直接插入排序

　　[答案]:D

　　58.线性表在_____时,宜用顺序表作存储结构.

　　A.经常作插入,删除

　　B.经常随机存取

　　C.无足够连续存储空间

　　D.经常作动态查找

　　[答案]:B

　　59.一棵左右子树均不空的二叉树在先序线索化后,其空指针域数为()

　　A.0

　　B.1

　　C.2

　　D.不确定

　　[答案]:B

　　60.已知一颗二叉树的后序遍历序列为DABEC,中序遍历序列为DEBAC,则它的先序遍历序列为().

　　A.ACBED

　　B.DECAB

　　C.DEABC

　　D.CEDBA

　　[答案]:D

　　二、判断题

　　1.设串S的长度为n,则S的子串个数为n(n+1)/2

　　[答案]:T

　　2.从具有n个结点的二叉排序树中查找一个元素时,最坏情况下的时间复杂度为O(n).

　　[答案]:T

　　3.广义表中原子个数即为广义表的长度

　　[答案]:F

　　4.空栈就是所有元素都为0的栈.

　　[答案]:F

　　5.设有一个空栈,现有输入序列1,2,3,4,5,经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH后,输出序列是2,3.

　　[答案]:T

　　6.数据元素是数据的最小单位.

　　[答案]:F

　　7.顺序存储结构属于静态结构,链式结构属于动态结构.

　　[答案]:T

　　8.线性表采用链表存储时,结点和结点内部的存储空间可以是不连续的.

　　[答案]:F

　　9.有回路的图不能进行拓扑排序.

　　[答案]:T

　　10.在所有结点的权都相等的情况下,具有平衡特性的二叉排序树一定是最佳二叉排序树.

　　[答案]:T

　　11.n*n对称矩阵经过压缩存储后占用的存储单元是原来的1/2.

　　[答案]:F

　　12.广义表是线性表的推广,是一类线性数据结构.

　　[答案]:F

　　13.哈希表的查找效率主要取决于哈希表造表时选取的哈希函数和处理冲突的方法.

　　[答案]:T

　　14.邻接表只能用于存储有向图,而邻接矩阵则可存储有向图和无向图.

　　[答案]:F

　　15.数据的物理结构是指数据在计算机内实际的存储形式.

　　[答案]:T

　　16.顺序查找法适用于存储结构为顺序或链接存储的线性表.

　　[答案]:T

　　17.完全二叉树中,若一个结点没有左孩子,则它必是树叶.

　　[答案]:T

　　18.一个图的广度优先搜索树是唯一的.

　　[答案]:F

　　19.在单链表中,要访问某个结点,只要知道该结点的指针即可;因此,单链表是一种随机存取结构.

　　[答案]:F

　　20.在线性表的顺序存储结构中,插入和删除元素时,移动元素的个数与该元素的位置有关.

　　[答案]:T

　　21.串是由有限个字符构成的连续序列,串长度为串中字符的个数,子串是主串中字符构成的有限序列.

　　[答案]:F

　　22.广义表是由零或多个原子或子表所组成的有限序列,所以广义表可能为空表.

　　[答案]:T

　　23.就平均查找长度而言,分块查找最小,折半查找次之,顺序查找最大.

　　[答案]:F

　　24.任何AOV网拓扑排序的结果都是唯一的.

　　[答案]:F

　　25.数据项是数据的基本单位.

　　[答案]:F

　　26.顺序存储的线性表可以随机存取.

　　[答案]:T

　　27.稀疏矩阵压缩存储后,必会失去随机存取功能.

　　[答案]:T

　　28.用带表头结点的单链表表示队列,则判断队列为空的标准是头指针和尾指针均指向同一个结点.

　　[答案]:T

　　29.在二叉排序树上删除一个结点时,不必移动其他结点,只要将该结点的父结点的相应指针域置空即可.

　　[答案]:F

　　30.栈和队列都是限制存取点的线性结构

　　[答案]:T

　　三、名词解释

　　1.串

　　[答案]:串是有零个或多个字符组成的优先序列.

　　2.关键字

　　[答案]:关键字是数据元素中某个数据项的值,用它可以标识一个数据元素或记录.

　　3.数据项,记录和文件.

　　[答案]:一个元素可以有若干个数据项组成,通常把数据元素称为记录,含有大量记录的线性表称为文件.

　　4.线性表

　　[答案]:线性表是最常用且最简单的一种数据结构,是n个数据元素的有限序列.

　　5.队列

　　[答案]:队列也是线性表,它是操作受限制的线性表,队列是先进先出表.

　　6.树

　　[答案]:树型结构是一类重要的非线性数据结构,树是以分支关系定义的层次结构.

　　7.数组

　　[答案]:数组在内存中占据连续的存储单元,其数组元素具有相同的名字和类型.

　　8.栈

　　[答案]:栈也是线性表,它是操作受限制的线性表,栈是后进先出表.

　　9.二叉树

　　[答案]:二叉树的每个结点至多只有两棵子树,并且,二叉树的子树有左右之分,其次序不能任意颠倒.

　　10.数据结构

　　[答案]:数据结构是相互之间存在一种或多种特定关系的数据元素的xxx.

　　11.图

　　[答案]:图形结构中,结点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关.

　　12.内部排序方法

　　[答案]:直接插入,折半插入,2-路插入,表插入,希尔排序,起泡排序,快速排序,选择排序,树形排序,堆排序,归并,基数.任选5个.