数据结构复习题选择题部分.docx
《数据结构复习题选择题部分.docx》由会员分享，可在线阅读，更多相关《数据结构复习题选择题部分.docx（39页珍藏版）》请在冰点文库上搜索。
数据结构复习题选择题部分
第一课绪论
一、选择题
1．算法的计算量的大小称为计算的（）。
A．效率B．复杂性C．现实性D．难度
参考答案：
B
2．算法的时间复杂度取决于（）。
A．问题的规模B．待处理数据的初态C．A和B
参考答案：
C
3．计算机算法指的是（）。
A．计算方法B．排序方法C．解决问题的步骤序列D．调度方法
参考答案：
C
4．计算机算法必须具备（）这三个特性。
A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性
C．确定性、有穷性、稳定性D．易读性、稳定性、安全性
参考答案：
B
5．下面关于算法说法错误的是（）。
A．算法最终必须由计算机程序实现
B．为解决某问题的算法同为该问题编写的程序含义是相同的
C．算法的可行性是指指令不能有二义性
D．以上几个都是错误的
参考答案：
D
6．从逻辑上可以把数据结构分为（）两大类。
A．动态结构、静态结构B．顺序结构、链式结构
C．线性结构、非线性结构D．初等结构、构造型结构
参考答案：
C
第二课线性表
一选择题
1．下列属顺序存储结构优点的是（）。
A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示
参考答案：
A
2．下列关于线性表的叙述中，错误的是（）。
A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
参考答案：
B
3．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。
A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表
参考答案：
A
4．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。
A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表
参考答案：
D
5．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。
则采用（）存储方式最节省运算时间。
A．单链表B．双链表C．带尾指针的单循环链表D．带头结点的双循环链表
参考答案：
D
6．静态链表中指针表示的是（）。
A．下一元素的地址B．内存储器的地址
C．下一元素在数组中的位置D．左链或右链指向的元素的地址
参考答案：
C
7．链表不具有的特点是（）。
A．插入、删除不需要移动元素B．可随机访问任一元素
C．不必事先估计存储空间D．所需空间与线性长度成正比
参考答案：
B
8．双向链表中有两个指针域，llink和rlink分别指向前趋及后继，设p指向链表中的一个结点，现要求删去p所指结点，则正确的删除是（）（链中结点数大于2，p不是第一个结点）。
A．p->llink->rlink=p->llink;p->llink->rlink=p->rlink;free（p）;
B．free（p）;p->llink->rlink=p->llink;p->llink->rlink=p->rlink;
C．p->llink->rlink=p->llink;free（p）;p->llink->rlink=p->rlink;
D．以上A，B，C都不对。
参考答案：
D
9．下列说法错误的是（）。
⑴静态链表既有顺序存储的优点，又有动态链表的优点。
所以，它存取表中第i个元素的时间与i无关。
⑵静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。
⑶静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。
A．⑴和⑵B．⑴C．⑴、⑵和⑶D．⑵
参考答案：
B
10．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）（1<=i<=n+1）。
A．O（0）B．O
（1）C．O（n）D．O（n2）
参考答案：
C
11．对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。
A．O（n）O（n）B．O（n）O
（1）C．O
（1）O（n）D．O
（1）O
（1）
参考答案：
C
12．线性表（a1，a2，…，an）以链接方式存储时，访问第i位置元素的时间复杂性为（）。
A．O（i）B．O
（1）C．O（n）D．O（i-1）
参考答案：
C
13．在一个以h为头的单循环链中，p指针指向链尾的条件是（）。
A．p->next=hB．p->next=NULLC．p->next->next=hD．p->data=-1
参考答案：
A
14．双向链表中有两个指针域，llink和rlink，分别指回前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（）。
A．p->llink=q;q->rlink=p;p->llink->rlink=q;q->llink=p->llink;
B．q->llink=p->llink;p->llink->rlink=q;q->rlink=p;p->llink=q->rlink;
C．q->rlink=p;p->rlink=q;p->llink->rlink=q;q->rlink=p;
D．p->llink->rlink=q;q->rlink=p;q->llink=p->llink;p->llink=q;
参考答案：
D
15．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）。
A．head==NULLB．head→next==NULLC．head→next==headD．head!
=NULL
参考答案：
B
第三课栈、队列和数组
一选择题
1．对于栈操作数据的原则是（）。
A．先进先出B．后进先出C．后进后出D．不分顺序
参考答案：
B
2．一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。
A．不确定B．n-i+1C．iD．n-i
参考答案：
B
3．若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（）。
A．i-j-1B．i-jC．j-i+1D．不确定的
参考答案：
D
4．设abcdef以所给的次序进栈，若在进栈操作时，允许出栈操作，则下面得不到的出栈序列为（）。
A．fedcbaB．bcafedC．dcefbaD．cabdef
参考答案：
D
5．输入序列为ABC，可以变为CBA时，经过的栈操作为（）
A．push,pop,push,pop,push,popB．push,push,push,pop,pop,pop
C．push,push,pop,pop,push,popD．push,pop,push,push,pop,pop
参考答案B
6．若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是（）。
A．top=top+1;V[top]=xB．V[top]=x;top=top+1
C．top=top-1;V[top]=xD．V[top]=x;top=top-1
参考答案：
C
7．若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈（i=1,2）栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。
A．|top[2]-top[1]|==0B．top[1]+1==top[2]C．top[1]+top[2]==mD．top[1]==top[2]
参考答案：
B
8．执行完下列语句段后，i值为：
（）。
intf（intx）
{return（（x>0）?
x*f（x-1）:
2）;}
inti;
i=f（f
（1））;
A．2B．4C．8D．无限递归
参考答案：
B
9．表达式a*（b+c）-d的后缀表达式是（）。
A．abcd*+-B．abc+*d-C．abc*+d-D．-+*abcd
参考答案：
B
10．表达式3*2^（4+2*2-6*3）-5求值过程中当扫描到6时，对象栈和算符栈为（），其中^为乘幂。
A．3,2,4,1,1；（*^（+*-B．3,2,8；（*^-C．3,2,4,2,2；（*^（-D．3,2,8；（*^（-
参考答案：
D
11．用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时（）。
A．仅修改队头指针B．仅修改队尾指针
C．队头、队尾指针都要修改D．队头、队尾指针都可能要修改
参考答案：
D
12．递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。
A．队列B．多维数组C．栈D．线性表
参考答案：
C
13．循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（）。
A．（rear-front+m）%mB．rear-front+1C．rear-front-1D．rear-front
参考答案：
A
14．循环队列存储在数组A[0..m]中，则入队时的操作为（）。
A．rear=rear+1B．rear=（rear+1）mod（m-1）
C．rear=（rear+1）modmD．rear=（rear+1）mod（m+1）
参考答案：
D
15．若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？
（）
A．1和5B．2和4C．4和2D．5和1
参考答案：
B
16．最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。
A．（rear+1）MODn==frontB．rear==front
C．rear+1==frontD．（rear-l）MODn==front
参考答案：
B
17．设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是（）。
A．6B．4C．3D．2
参考答案：
C
18．数组A[0..4,-1..-3,5..7]中含有元素的个数（）。
A．55B．45C．36D．16
参考答案：
B
19．设二维数组A[1..m，1..n]（即m行n列）按行存储在数组B[1..m*n]中，则二维数组元素A[i，j]在一维数组B中的下标为（）。
A．（i-1）*n+jB．（i-1）*n+j-1C．i*（j-1）D．j*m+i-1
参考答案：
A
20．设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。
A．13B．33C．18D．40
参考答案：
B
21．设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为（）。
A．BA+141B．BA+180C．BA+222D．BA+225
参考答案：
B
22．数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是（）。
A．1175B．1180C．1205D．1210
参考答案：
A
23．将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元素A66,65（即该元素下标i=66，j=65），在B数组中的位置K为（）。
A．198B．195C．197D．196
参考答案：
B
24．对稀疏矩阵进行压缩存储目的是（）。
A．便于进行矩阵运算B．便于输入和输出C．节省存储空间D．降低运算的时间复杂度
参考答案：
C
25．有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。
A．60B．66C．18000D．33
参考答案：
B
26．算术表达式a+b*（c+d/e）转为后缀表达式后为（）。
A．ab+cde/*B．abcde/+*+C．abcde/*++D．abcde*/++
参考答案：
B
第四课树和二叉树
1．已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为（）。
A．-A+B*C/DEB．-A+B*CD/EC．-+*ABC/DED．-+A*BC/DE
参考答案：
D
2．当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组A[l..n]中时，数组中第i个结点的左孩子为（）。
A．A[2i]（2i<=n）B．A[2i+1]（2i+1<=n）C．A[i/2]D．无法确定
参考答案：
D
3．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。
A．250B．500C．254D．505E．以上答案都不对
参考答案：
E
4．设树T的度为4，其中度为1、2、3和4的结点个数分别为4、2、1、1，则T中的叶子数为（）。
A．5B．6C．7D．8
参考答案：
D
5．在下述结论中，正确的是（）。
①只有一个结点的二叉树的度为0；
②二叉树的度为2；
③二叉树的左右子树可任意交换；
④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A．①②③B．②③④C．②④D．①④
参考答案：
D
6．设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n，森林F中第一棵树的结点个数是（）。
A．m-nB．m-n-1C．n+1D．条件不足，无法确定
参考答案：
A
7．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）。
A．9B．11C．15D．不确定
参考答案：
B
8．在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（）个。
A．4B．5C．6D．7
参考答案：
C
9．设森林F中有三棵树，第一、第二、第三棵树的结点个数分别为M1、M2和M3。
与森林F对应的二叉树根结点的右子树上的结点个数是（）。
A．M1B．M1+M2C．M3D．M2+M3
参考答案：
D
10．具有10个叶结点的二叉树中有（）个度为2的结点。
A．8B．9C．10D．11
参考答案：
B
11．下述编码中不是前缀码的是（）。
A．（00，01，10，11）B．（0，1，00，11）C．（0，10，110，111）D．（1，01，000，001）
参考答案：
B
12．设给定权值总数有n个，其哈夫曼二叉树的结点总数为（）。
A．不确定B．2nC．2n+1D．2n-1
参考答案：
D
13．下面几个符号串编码集合中，不是前缀编码的是（）。
A．{0,10,110,1111}B．{11,10,001,101,0001}
C．{00,010,0110,1000}D．{b,c,aa,ac,aba,abb,abc}
参考答案：
B
14．有关二叉树下列说法正确的是（）。
A．二叉树的度为2B．一棵二叉树的度可以小于2
C．二叉树中至少有一个结点的度为2D．二叉树中任何一个结点的度都为2
参考答案：
B
15．二叉树的第i层上最多含有结点数为（）。
A．2iB．2i-1-1C．2i-1D．2i-1
参考答案：
C
16．一个具有1025个结点的二叉树的高h为（）。
A．11B．10C．11至1025之间D．10至1024之间
参考答案：
C
17．一棵二叉树高度为h，所有结点的度或为0，或为2，则这棵二叉树最少有（）结点。
A．2hB．2h-1C．2h+1D．h+1
参考答案：
B
18．对于有n个结点的二叉树，其高度为（）。
A．nlog2nB．log2nC．log2n+1D．不确定
参考答案：
D
19．一棵具有n个结点的完全二叉树的树高度（深度）是（）。
A．logn+1B．logn+1C．lognD．logn-1
参考答案：
A
20．深度为h的满m叉树的第k层有（）个结点。
（1=A．mk-1B．mk-1C．mh-1D．mh-1
参考答案：
A
21．在一棵高度为k的满二叉树中，结点总数为（）。
A．2k-1B．2kC．2k-1D．log2k+1
参考答案：
C
22．高度为k的二叉树最大的结点数为（）。
A．2kB．2k-1C．2k-1D．2k-1-1
参考答案：
C
23．一棵树高为k的完全二叉树至少有（）个结点。
A．2k–1B．2k-1–1C．2k-1D．2k
参考答案：
C
24．将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（）。
A．4B．5C．6D．7
参考答案：
C
25．利用二叉链表存储树，则根结点的右指针是（）。
A．指向最左孩子B．指向最右孩子C．空D．非空
参考答案：
C
26．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（）次序的遍历实现编号。
A．先序B．中序C．后序D．从根开始按层次遍历
参考答案：
C
27．树的后根遍历序列等同于该树对应的二叉树的（）。
A．先序序列B．中序序列C．后序序列
参考答案：
B
28．若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（）遍历方法最合适。
A．前序B．中序C．后序D．按层次
参考答案：
C
29．下述二叉树中，（）满足从任一结点出发到根的路径上所经过的结点序列按其关键字有序。
A．二叉排序树B．哈夫曼树C．AVL树D．堆
参考答案：
D
30．一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（）。
A．CABDEFGB．ABCDEFGC．DACEFBGD．ADCFEG
参考答案：
B
31．已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为（）。
A．CBEFDAB．FEDCBAC．CBEDFAD．不定
参考答案：
A
32．已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历是（）。
A．acbedB．decabC．deabcD．cedba
参考答案：
D
33．某二叉树中序序列为ABCDEFG，后序序列为BDCAFGE，则前序序列是（）。
A．EGFACDBB．EACBDGFC．EAGCFBDD．上面的都不对
参考答案：
B
34．如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2中结点的（）。
A．先序B．中序C．后序D．层序
参考答案：
B
35．若二叉树的先序遍历为EFHIGJK，中序遍历为HFIEJKG，则该二叉树根的右子树的根是（）。
A．EB．FC．GD．H
参考答案：
C
36．将一棵树T转换为孩子兄弟链表表示的二叉树H，则T的后序遍历序列与H的（）序列相同。
A．前序遍历B．中序遍历C．后序遍历
参考答案：
B
37．某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号为1,2,...,n，且有如下性质：
T中任一结点V，其编号等于左子树上的最小编号减1，而V的右子树的结点中，其最小编号等于V左子树上结点的最大编号加1。
这时是按（）编号的。
A．中序遍历序列B．前序遍历序列C．后序遍历序列D．层次顺序
参考答案：
B
38．下面的说法中正确的是（）。
（1）任何一棵二叉树的叶子结点在三种遍历中的相对次序不变；
（2）按二叉树定义，具有三个结点的二叉树共有6种。
A．
（1）
（2）B．
（1）C．
（2）D．
（1）、
（2）都错
参考答案：
B
39．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）。
A．所有的结点均无左孩子B．所有的结点均无右孩子
C．只有一个叶子结点D．是任意一棵二叉树
参考答案：
C
40．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（）
A．都不相同 B．完全相同C．先序和中序相同，而与后序不同
D．中序和后序相同，而与先序不同
参考答案：
B
41．某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。
A．空或只有一个结点B．任一结点无左子树
C．高度等于其结点数D．任一结点无右子树
参考答案：
C
42．由3个结点可以构造出（）种不同的二叉树。
A．2B．3C．4D．5
参考答案：
D
43．设F是一个森林，B是由F变换得的二叉树。
若F中有n个非终端结点，则B中右指针域为空的结点有（）个。
A．n-1B．nC．n+1D．n+2
参考答案：
C
44．一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是：
（）。
A．不确定B．0C．1D．2
参考答案：
D
45．一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：
（）。
A．0B．1C．2D．不确定
参考答案：
C
46．若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为（）。
A．X的双亲B．X的右子树中最左的结点
C．X的左子树中最右结点D．X的左子树中最右叶结点
参考答案：
C
47．引入二叉线索树的目的是（）。
A．加快查找结点的前驱或后继的速度B．为了能在二叉树中方便的进行插入与删除
C．为了能方便的找到双亲D．使二叉树的遍历结果唯一
参考答案：
A
48．线索二叉树是一种（）结构。
A．逻辑B．逻辑和存储C．物理D．线性
参考答案：
C
49．n个结点的线索二叉树上含有的线索数为（）。
A．2nB．n-1C．n+1D．n
参考答案：
C
50．（）的遍历仍需要栈的支持。
A．前序线索树B．中序线索树C．后序线索树
参考答案：
C
51．二叉树在线索后，仍不能有效求解的问题是（）。
A．先序线索二叉树中求先序后继B．中序线索二叉树中求中序后继
C．中序线索二叉树中求中序前驱D．后序线索二叉树中求后序后继
参考答案：
D
52．由3个结点可以构造出（）种不同的有序树。
A．2B．3C．4D．5
参考答案：
A
第五课图
1．图中有关路径的定义是（）。
A．由顶点和相邻顶点序偶构成的边所形成的序列B．由不同顶点所形成的序列
C．由不同边所形成的序列D．上述定义都不是
参考答案：
A
2．设无向图的顶点个数为n，则该图最多有（）条边。
A．n-1B．n（n-1）/2C．n（n+1）/2D．0E
升级会员 