数据结构复习题选择题部分(18页).doc

《数据结构复习题选择题部分(18页).doc》由会员分享，可在线阅读，更多相关《数据结构复习题选择题部分(18页).doc（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-数据结构复习题选择题部分-第 18 页第一课 绪论一、选择题1算法的计算量的大小称为计算的（ ）。A效率 B复杂性 C现实性 D难度参考答案：B2算法的时间复杂度取决于（ ）。A问题的规模 B待处理数据的初态 CA和B参考答案：C3计算机算法指的是（ ）。A计算方法 B排序方法 C解决问题的步骤序列 D调度方法参考答案：C4计算机算法必须具备（ ）这三个特性。A可执行性、可移植性、可扩充性 B可执行性、确定性、有穷性C确定性、有穷性、稳定性 D易读性、稳定性、安全性参考答案：B5下面关于算法说法错误的是（ ）。A算法最终必须由计算机程序实现B为解决某问题的算法同为该问题编写的程序含义是相同的

2、C算法的可行性是指指令不能有二义性D以上几个都是错误的参考答案：D6从逻辑上可以把数据结构分为（ ）两大类。A动态结构、静态结构 B顺序结构、链式结构C线性结构、非线性结构 D初等结构、构造型结构参考答案：C第二课 线性表一 选择题1下列属顺序存储结构优点的是（ ）。A存储密度大 B插入运算方便 C删除运算方便 D可方便地用于各种逻辑结构的存储表示参考答案：A2下列关于线性表的叙述中，错误的是（ ）。A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。参考答案

3、：B3若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。A顺序表 B双链表 C带头结点的双循环链表 D单循环链表参考答案：A4某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。A单链表 B仅有头指针的单循环链表 C双链表 D仅有尾指针的单循环链表参考答案：D5若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ ）存储方式最节省运算时间。A单链表 B双链表 C带尾指针的单循环链表 D带头结点的双循环链表参考答案：D6静态链表中指针表示的是（ ）。A下一元素

4、的地址 B内存储器的地址C下一元素在数组中的位置 D左链或右链指向的元素的地址参考答案：C7链表不具有的特点是（ ）。A插入、删除不需要移动元素 B可随机访问任一元素C不必事先估计存储空间 D所需空间与线性长度成正比参考答案：B8双向链表中有两个指针域，llink和rlink分别指向前趋及后继，设p指向链表中的一个结点，现要求删去p所指结点，则正确的删除是（ ）（链中结点数大于2，p不是第一个结点）。Ap-llink-rlink=p-llink; p-llink-rlink=p-rlink; free(p);Bfree (p); p-llink-rlink=p-llink; p-llink-r

5、link=p-rlink;Cp-llink-rlink=p-llink; free (p); p-llink-rlink=p-rlink;D以上A，B，C都不对。参考答案：D9下列说法错误的是（ ）。静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。A和 B C、和 D参考答案：B10若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1=inext=h Bp-next=NULL Cp-

6、next-next=h Dp-data=-1参考答案：A14双向链表中有两个指针域，llink和rlink，分别指回前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（ ）。Ap-llink=q; q-rlink=p; p-llink-rlink=q; q-llink=p-llink;Bq-llink=p-llink; p-llink-rlink=q; q-rlink=p; p-llink=q-rlink;Cq-rlink=p; p-rlink=q; p-llink-rlink=q; q-rlink=p;Dp-llink-rlink=q; q-rlin

7、k=p; q-llink=p-llink; p-llink=q;参考答案：D15对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）。Ahead=NULL Bheadnext=NULL Cheadnext=head Dhead!=NULL参考答案：B第三课 栈、队列和数组一 选择题1对于栈操作数据的原则是（ ）。A先进先出 B后进先出 C后进后出 D不分顺序参考答案：B2一个栈的输入序列为123n，若输出序列的第一个元素是n，输出第i（1=i0) ? x* f(x-1):2);int i;i =f(f(1);A2 B4 C8 D无限递归参考答案：B9表达式a*(b+c)-d

8、的后缀表达式是（ ）。Aabcd*+- Babc+*d- Cabc*+d- D-+*abcd参考答案：B10表达式3*2(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（ ），其中为乘幂。A3,2,4,1,1；(*(+*- B3,2,8；(*- C3,2,4,2,2；(*(- D3,2,8；(*(-参考答案：D11用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时（ ）。A仅修改队头指针 B仅修改队尾指针C队头、队尾指针都要修改 D队头、队尾指针都可能要修改参考答案：D12递归过程或函数调用时，处理参数及返回地址，要用一种称为（

9、 ）的数据结构。A队列 B多维数组 C栈 D线性表参考答案：C13循环队列A0.m-1存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（ ）。A(rear-front+m)%m Brear-front+1 Crear-front-1 Drear-front参考答案：A14循环队列存储在数组A0.m中，则入队时的操作为（ ）。Arear=rear+1 Brear=(rear+1) mod (m-1)Crear=(rear+1) mod m Drear=(rear+1) mod (m+1)参考答案：D15若用一个大小为6的数组来实现循环队列，且当前rear和front

10、的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？（ ）A1和5 B2和4 C4和2 D5和1参考答案：B16最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（ ）。A(rear+1) MOD n=front Brear=frontCrear+1=front D(rear-l) MOD n=front参考答案：B17设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是（ ）。A6 B4 C

11、3 D2参考答案：C18数组A0.4,-1.-3,5.7中含有元素的个数（ ）。A55 B45 C36 D16参考答案：B19设二维数组A1.m，1.n（即m行n列）按行存储在数组B1.m*n中，则二维数组元素Ai，j在一维数组B中的下标为（ ）。A(i-1)*n+j B(i-1)*n+j-1 Ci*(j-1) Dj*m+i-1参考答案：A20设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。A13 B33 C18 D40参考答案：B21设有数组Ai,j，数组的每个元素长度为3字节，i的值为1 到8

12、，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A5，8的存储首地址为（ ）。ABA+141 BBA+180 CBA+222 DBA+225参考答案：B22数组A0.5,0.6的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A5，5的地址是（ ）。A1175 B1180 C1205 D1210参考答案：A23将一个A1.100，1.100的三对角矩阵，按行优先存入一维数组B1298中，A中元素A66,65（即该元素下标i=66，j=65），在B数组中的位置K为（ ）。A198 B195 C197 D196参考答案：B24对稀疏矩

13、阵进行压缩存储目的是（ ）。A便于进行矩阵运算 B便于输入和输出 C节省存储空间 D降低运算的时间复杂度参考答案：C25有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（ ）。A60 B66 C18000 D33参考答案：B26算术表达式a+b*(c+d/e)转为后缀表达式后为（ ）。Aab+cde/* Babcde/+*+ Cabcde/*+ Dabcde*/+参考答案：B第四课 树和二叉树1已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为（ ）。A-A+B*C/DE B-A+B*CD/E

14、C-+*ABC/DE D-+A*BC/DE参考答案：D2当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组Al.n中时，数组中第i个结点的左孩子为（ ）。AA2i(2i=n) BA2i+1(2i+1=n) CAi/2 D无法确定参考答案：D3一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）。A250 B500 C254 D505 E以上答案都不对参考答案：E4设树T的度为4，其中度为1、2、3和4的结点个数分别为4、2、1、1，则T中的叶子数为（ ）。A5 B6 C7 D8参考答案：D5在下述结论中，正确的是（ ）。只有一个结点的二叉树的度为0；二叉树的度为

15、2；二叉树的左右子树可任意交换；深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A B C D参考答案：D6设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n，森林F中第一棵树的结点个数是（ ）。Am-n Bm-n-1 Cn+1 D条件不足，无法确定参考答案：A7若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）。A9 B11 C15 D不确定参考答案：B8在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个。A4 B5 C6 D7参考答案：C9设森林F中有三棵树，第一、第二

16、、第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。AM1 BM1+M2 CM3 DM2+M3参考答案：D10具有10个叶结点的二叉树中有（ ）个度为2的结点。A8 B9 C10 D11参考答案：B11下述编码中不是前缀码的是（ ）。A（00，01，10，11） B（0，1，00，11） C（0，10，110，111） D（1，01，000，001）参考答案：B12设给定权值总数有n个，其哈夫曼二叉树的结点总数为（ ）。A不确定 B2n C2n+1 D2n-1参考答案：D13下面几个符号串编码集合中，不是前缀编码的是（ ）。A0,10,110,1

17、111 B11,10,001,101,0001C00,010,0110,1000 Db,c,aa,ac,aba,abb,abc参考答案：B14有关二叉树下列说法正确的是（ ）。A二叉树的度为2 B一棵二叉树的度可以小于2C二叉树中至少有一个结点的度为2 D二叉树中任何一个结点的度都为2参考答案：B15二叉树的第i层上最多含有结点数为（ ）。A2i B2i-1-1 C2i-1 D2i -1参考答案：C16一个具有1025个结点的二叉树的高h为（ ）。A11 B10 C11至1025之间 D10至1024之间参考答案：C17一棵二叉树高度为h，所有结点的度或为0，或为2，则这棵二叉树最少有（ ）结

18、点。A2h B2h-1 C2h+1 Dh+1参考答案：B18对于有n个结点的二叉树，其高度为（ ）。Anlog2n Blog2n Clog2n+1 D不确定参考答案：D19一棵具有n个结点的完全二叉树的树高度（深度）是（ ）。Alogn+1 Blogn+1 Clogn Dlogn-1参考答案：A20深度为h的满m叉树的第k层有（ ）个结点。(1=k=h)Amk-1 Bmk-1 Cmh-1 Dmh-1参考答案：A21在一棵高度为k的满二叉树中，结点总数为（ ）。A2k-1 B2k C2k-1 Dlog2k+1参考答案：C22高度为k的二叉树最大的结点数为（ ）。A2k B2k-1 C2k-1 D

19、2k-1-1参考答案：C23一棵树高为k的完全二叉树至少有（ ）个结点。A2k1 B2k-11 C2k-1 D2k参考答案：C24将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（）。A4 B5 C6 D7参考答案：C25利用二叉链表存储树，则根结点的右指针是（ ）。A指向最左孩子 B指向最右孩子 C空 D非空参考答案：C26对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（ ）次序的遍历实现编号。A先序 B中序 C后序 D从根开始按层次遍历参考答案：C27树的后根遍历序列等同于该

20、树对应的二叉树的（ ）。A先序序列 B中序序列 C后序序列参考答案：B28若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（ ）遍历方法最合适。A前序 B中序 C后序 D按层次参考答案：C29下述二叉树中，（ ）满足从任一结点出发到根的路径上所经过的结点序列按其关键字有序。A二叉排序树 B哈夫曼树 CAVL树 D堆参考答案：D30一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ ）。ACABDEFG BABCDEFG CDACEFBG DADCFEG参考答案：B31已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果

21、为（ ）。ACBEFDA BFEDCBA CCBEDFA D不定参考答案：A32已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历是（ ）。Aacbed Bdecab Cdeabc Dcedba参考答案：D33某二叉树中序序列为ABCDEFG，后序序列为BDCAFGE，则前序序列是（ ）。AEGFACDB BEACBDGF CEAGCFBD D上面的都不对参考答案：B34如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2中结点的（ ）。A先序 B中序 C后序 D层序参考答案：B35若二叉树的先序遍历为EFHIGJK，中序遍历为HFIEJKG，则该二叉树

22、根的右子树的根是（ ）。AE BF CG DH参考答案：C36将一棵树T转换为孩子兄弟链表表示的二叉树H，则T的后序遍历序列与H的（ ）序列相同。A前序遍历 B中序遍历 C后序遍历参考答案：B37某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号为1,2, . ,n，且有如下性质：T中任一结点V，其编号等于左子树上的最小编号减1，而V的右子树的结点中，其最小编号等于V左子树上结点的最大编号加1。这时是按（ ）编号的。A中序遍历序列 B前序遍历序列 C后序遍历序列 D层次顺序参考答案：B38下面的说法中正确的是（ ）。(1)任何一棵二叉树的叶子结点在三种遍历中的相对次序不变；(2)

23、按二叉树定义，具有三个结点的二叉树共有6种。A(1)(2) B(1) C(2) D(1)、(2)都错参考答案：B39一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）。A所有的结点均无左孩子 B所有的结点均无右孩子C只有一个叶子结点 D是任意一棵二叉树参考答案：C40在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（ ）A都不相同B完全相同 C先序和中序相同，而与后序不同 D中序和后序相同，而与先序不同 参考答案：B41某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。A空或只有一个结点 B任一结点无左子树C高度等于其结点数

24、D任一结点无右子树参考答案：C42由3个结点可以构造出（ ）种不同的二叉树。A2 B3 C4 D5参考答案：D43设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ ）个。An-1 Bn Cn+1 Dn+2参考答案：C44一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是：（ ）。A不确定 B0 C1 D2参考答案：D45一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：（ ）。A0 B1 C2 D不确定参考答案：C46若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为（ ）。AX的双亲 BX的右子树中最左的结点C

25、X的左子树中最右结点 DX的左子树中最右叶结点参考答案：C47引入二叉线索树的目的是（ ）。A加快查找结点的前驱或后继的速度 B为了能在二叉树中方便的进行插入与删除C为了能方便的找到双亲 D使二叉树的遍历结果唯一参考答案：A48线索二叉树是一种（ ）结构。A逻辑 B逻辑和存储 C物理 D线性参考答案：C49n个结点的线索二叉树上含有的线索数为（ ）。A2n Bn-1 Cn+1 Dn参考答案：C50（ ）的遍历仍需要栈的支持。A前序线索树 B中序线索树 C后序线索树参考答案：C51二叉树在线索后，仍不能有效求解的问题是（ ）。A先序线索二叉树中求先序后继 B中序线索二叉树中求中序后继C中序线索二

26、叉树中求中序前驱 D后序线索二叉树中求后序后继参考答案：D52由3个结点可以构造出（ ）种不同的有序树。A2 B3 C4 D5参考答案：A第五课 图1图中有关路径的定义是（ ）。A由顶点和相邻顶点序偶构成的边所形成的序列 B由不同顶点所形成的序列C由不同边所形成的序列 D上述定义都不是参考答案：A2设无向图的顶点个数为n，则该图最多有（ ）条边。An-1 Bn(n-1)/2 C n(n+1)/2 D0 En2参考答案：B备注：设有向图的顶点个数为n，则该图最多有n(n-1)条边。3一个n个顶点的连通无向图，其边的个数至少为（ ）。An-1 Bn Cn+1 Dnlogn参考答案：A4要连通具有n

27、个顶点的有向图，至少需要（ ）条边。An-l Bn Cn+l D2n参考答案：B5n个结点的完全有向图含有边的数目（）。An*n n（n+1） Cn2 Dn*（n-1）参考答案：D6一个有n个结点的图，最少有（ ）个连通分量。A0 B1 Cn-1 Dn参考答案：B7一个有n个结点的图，最多有（ ）个连通分量。？A0 B1 Cn-1 Dn参考答案：D8用有向无环图描述表达式(A+B)*（A+B）/A），至少需要顶点的数目为（）。？A5 B6 C8 D9 参考答案：A9用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是（）。A逆拓扑有序 B拓扑有序 C无序的 参

28、考答案：A10下面结构中最适于表示稀疏无向图的是（ ）。A邻接矩阵 B逆邻接表 C邻接多重表 D十字链表 E邻接表参考答案：C11下列哪一种图的邻接矩阵是对称矩阵？（ ）A有向图 B无向图 CAOV网 DAOE网参考答案：B12当一个有N个顶点的图用邻接矩阵A表示时，顶点Vi的度是（ ）。A B C D+ 参考答案：B13下列说法不正确的是（ ）。A图的遍历是从给定的源点出发每一个顶点仅被访问一次 B遍历的基本算法有两种：深度遍历和广度遍历C图的深度遍历不适用于有向图D图的深度遍历是一个递归过程参考答案：C14无向图G=(V,E),其中：V=a,b,c,d,e,f,E=(a,b),(a,e),

29、(a,c),(b,e),(c,f),(f,d),(e,d)，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。Aa,b,e,c,d,f Ba,c,f,e,b,d Ca,e,b,c,f,d Da,e,d,f,c,b参考答案：D15设图如右所示，在下面的5个序列中，符合深度优先遍历的序列有（ ）个。a e b d f c a c f d e b a e d f c b a e f d c b a e f d b cA5个 B4个 C3个 D2个参考答案：D16下列方法中可以判断出一个有向图是否有环（回路）的是（）。A广度优先遍历 B拓扑排序 C求最短路径 D求关键路径参考答案：B17下列方法中

30、可以判断出一个有向图是否有环（回路）的是（）。A深度优先遍历 B广度优先遍历 C求最短路径 D求关键路径参考答案：A18在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为（）。AO(n) BO(n+e) CO(n2) DO(n3)参考答案：B19当各边上的权值（）时，BFS算法可用来解决单源最短路径问题。A均相等 B均互不相等 C不一定相等参考答案：A20求解最短路径的Floyd算法的时间复杂度为（）。AO（n） BO（n+c） CO（n*n） DO（n*n*n）参考答案：D21已知有向图G=(V,E)，其中V=V1,V2,V3,V4,V5,V6,V7，E=, ,，G的拓扑序列是（

31、 ）。AV1,V3,V4,V6,V2,V5,V7 BV1,V3,V2,V6,V4,V5,V7CV1,V3,V4,V5,V2,V6,V7 DV1,V2,V5,V3,V4,V6,V7参考答案：A22若一个有向图的邻接矩阵中，主对角线以下的元素均为零，则该图的拓扑有序序列（ ）。A存在 B不存在参考答案：A23一个有向无环图的拓扑排序序列（ ）是唯一的。A一定 B不一定参考答案：A24在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ ）。AG中有弧 BG中有一条从Vi到Vj的路径CG中没有弧 DG中有一条从Vj到Vi的路径参考答案：D25在用邻接表表示图时，拓扑排序算法时

32、间复杂度为（）。AO(n) BO(n+e) CO(n*n) DO(n*n*n)参考答案：B26关键路径是事件结点网络中（ ）。A从源点到汇点的最长路径 B从源点到汇点的最短路径C最长回路 D最短回路参考答案：A27下面关于求关键路径的说法不正确的是（ ）。 A求关键路径是以拓扑排序为基础的 B一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同 C一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D关键活动一定位于关键路径上参考答案：C28下列关于AOE网的叙述中，不正确的是（ ）。A关键活动不按期完成就会影响整个工程的完成时间B任何一个关键活动提前完成

33、，那么整个工程将会提前完成C所有的关键活动提前完成，那么整个工程将会提前完成D某些关键活动提前完成，那么整个工程将会提前完成参考答案：B29在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍。A1/2 B2 C1 D4参考答案：B30在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。A1/2 B2 C1 D4参考答案：C第六课 查找一、选择题1若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为（ ）。 A(n-1)/2 Bn/2 C(n+1)/2 Dn参考答案：C2对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（ ）。A（N+1）/2 BN/2 C N D （1+N）*N /2参考答案：A3顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（ ）。在此假定N为线性表中结点数，且每次查找都是成功的。AN+1 B2log2N Clog2N DN/2 ENlog2N FN2参考答案：D4二分法查找只适用于查找顺序存储的有序表，平均比较次数为（ ）。在此假定N为线性表中结点数，且每次查找都是成功的。AN+1 B2log2N Clog2N DN/2 ENlog2N FN2参考答案：C5对线性表进行二分查找时，要求线性表必须（ ）。A以顺序