数据结构期末综测

1、数据结构期末综测1 .以下关于链式存储结构的叙述中，是不正确的。单选题*A.结点除自身信息外还包括指针域，因此空间利用率小于顺序存储结构B.逻辑上相邻的结点物理上不必邻接C.可以通过计算直接确定第i个结点的存储地址（正确答案）D.插入、删除运算操作方便，不必移动结点2 .在下列存储结构中，最适合实现在线性表中进行随机访问的是。单选题*A.数组（正确答案）B.双向链表C.单向链表D.循环链表3 .与单链表相比，双链表的优点之一是。单选题*A.可以由最后一个结点找到头结点B.可随机访问C.插入、删除操作更加简单D.访问前驱结点更加方便（正确答案）4 .如果对线性表的运算只有2种，即删除第一个元素，

2、在最后一个元素的后面插入新元素，则最好使用单选题*A.顺序表B.单链表C.双向链表D.具有表尾指针的循环单链表（正确答案）5 .在表头指针为head且表长大于1的单向循环链表中，指针p指向表中的某个结点，若p.next.next=head贝U。单选题*A.p指向头结点B.p指向尾结点C.p所指结点的直接后继是头结点D.p所指结点的直接后继是尾结点（正确答案）6 .带表头附加结点的单链表head为空的判断条件是。单选题*A.head=NoneB.head.next=None（正确答案）C.head.next=headD.head!=NoneA.一个单链表中，若要在指针s所指结点的后面插入一个由指

3、针P所指向的结点，则执行。单选题*A. s.next=pp.next=s.next；B. p.next=s.nexts=pC. s.next=p.nextp.next=sD. p.next=s.nexts.nex匕p（正确答案）8.对线性表，在下列情况下应当采用链表表示的是。单选题*A.经常需要随机地存取元素8 .经常需要进行插入和删除操作（正确答案）C.表中元素需要占据一片连续的存储空间D.表中的元素个数不变9 .如果最常用的操作是取第i个结点及前驱，则采用存储方式最节省时问。单选题*A.顺序表（正确答案）B. 双链表C. 单循环链表D.单链表10.从一个具n个结点的单链表中查找其值等于x的

4、结点时，在查找成功的情况下，需平均比较个结点。单选题*A. nB. n/2C. （n-1）/2D. （n+1）/2（正确答案）11 .在单链表中，指针p指向元素为x的结点，实现删除x的后继的语句是一单选题*A. p=p.nextB. p.next=p.next.next（正确答案）C. p.next=pD. p=p.next.next12 .循环链表的主要优点是。单选题*A. 不再需要头指针了B. 已知某个结点的位置后，能很容易找到它的直接前驱结点C. 在进行删除操作后，能保证链表不断开D. 从表中任一结点出发都能遍历整个链表（正确答案）13 .若让元素 1, 2, 3, 4, 5依次进栈，则

5、出栈次序不可能出现在 （） 种情况。单选单选题*A. 5,4,3,2,1B. 2,1,5,4,3C. 4,3,1,2,5（正确答案）D. 2,3,5,4,1答案解析：栈是后进先出的线性表，不难发现C选项中元素1比元素2先出栈，违背了栈的后进先出原则，所以不可能出现C选项所示的情况。14.若已知一个栈的入栈序列是1,2,3,，n,其输出序列为p1,p2,p3,，pn,若p1=n,则pi为（）o单选题*A. iB. n-iC. n-i+1（正确答案）D.不确定答案解析：栈是后进先出的线性表，一个栈的入栈序列是1,2,3,，n,而输出序列的第一个元素为n,说明1,2,3,，n一次性全部进栈，再进行输

6、出，所以p1=n,p2=n-1，pi=n-i+1o15 .数组Qn用来表示一个循环队列，f为当前队列头元素的前一位置，r为队尾元素的位置，假定队列中元素的个数小于n,计算队列中元素个数的公式为（）。单选题*A. r-fB. （n+f-r）%nC. n+r-fD. （n+r-f）%n（正确答案）答案解析：对于非循环队列，尾指针和头指针的差值便是队列的长度，而对于循环队列，差值可能为负数，所以需要将差值加上MAXSIZE（本题为n）,然后与MAXSIZE（本题为n）求余，即（n+r-f）%n16 .链式栈结点为：（data,link）,top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中，

7、则应执行操作（）。单选题*A. x=top->data;top=top->link;（正确答案）B. top=top->link;x=top->link;C. x=top;top=top->link;D. x=top->link;答案解析：x=top-&gt;data将结点的值保存到x中，top=top-&gt;link栈顶指针指向栈顶下一结点，即摘除栈顶结点。17 .设有一个递归算法如下intfact（intn）/n大于等于0if（n<=return1;elsereturnn*fact（n-；则计算fact（n）需要调用该函数的次数为

8、（）。单选题*A. n+1（正确答案）B. n-1C. nD. n+2答案解析：特殊值法。设n=0,易知仅调用一次fact（n）函数，故选A。18 .栈在（）中有所应用。单选题*A. 递归调用B. 函数调用C. 表达式求值D.前三个选项都有（正确答案）答案解析：递归调用、函数调用、表达式求值均用到了栈的后进先出性质。19 .为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（）。单选题*A. 队列（正确答案）B. 栈C. 线性表D.有序表答案解析：解决缓冲区问题应利用一种先进先出的

9、线性表，而队列正是一种先进先出的线性表。20.设栈S和队列Q的初始状态为空，元素el、e2、e3、e4、e5和e6依次进入栈S,一个元素出栈后即进入Q,若6个元素出队的序列是e2、e4、e3、e6、e5和el,则栈S的容量至少应该是（）。单选题*A. 2B. 3（正确答案）C. 4D. 6答案解析：元素出队的序列是e2、e4、e3、e6、e5和el,可知元素入队的序列是e2、e4、e3、e6、e5和el,即元素出栈的序列也是e2、e4、e3、e6、e5和el,而元素el、e2、e3、e4、e5和e6依次进入栈，易知栈S中最多同时存在3个元素，故栈S的容量至少为3。21 .若一个栈以向量V1.n

10、存储，初始栈顶指针top设为n+1,则元素x进栈的正确操作是（）。单选题*A. top+;Vtop=x;B. Vtop=x;top+;C. top-Mtop=x；（正确答案）D. Vtop=x;top-;答案解析：初始栈顶指针top为n+1,说明元素从数组向量的高端地址进栈，又因为元素存储在向量空间V1.n中，所以进栈时top指针先下移变为n,之后将元素x存储在Vn。22 .设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。单选题*A. 线性表的顺序存储结构B. 队列C. 线性表的链式存储结构D.栈（正确答案）答案解析：利用栈的后进先出原则。23 .用链接方式存储的队列，

11、在进行删除运算时（）。单选题*A. 仅修改头指针B. 仅修改尾指针C. 头、尾指针都要修改D.头、尾指针可能都要修改（正确答案）答案解析：一般情况下只修改头指针，但是，当删除的是队列中最后一个元素时，队尾指针也丢失了，因此需对队尾指针重新赋值。24 .循环队列存储在数组A0.m中，则入队时的操作为（）。单选题*A.rear=rear+1B.rear=（rear+1）%（m-1）C.rear=（rear+1）%mD.rear=（rear+1）%（m+1）（正确答案）答案解析：数组A：0.m中共含有m+1个元素，故在求模运算时应除以m+1o25.最大容量为n的循环队列，队尾指针是rear,队头是f

12、ront,则队空的条件是（）。单选题*A.（rear+1）%n=frontB.rear=frontC. rear+1=front（正确答案）D. （rear-l）%n=front答案解析：最大容量为n的循环队列，队满条件是（rear+1）%n=front,队空条件是rear=fronto26 .栈和队列的共同点是（）。单选题*A. 都是先进先出B. 都是先进后出C. 只允许在端点处插入和删除元素（正确答案）D.没有共同点答案解析：栈只允许在栈顶处进行插入和删除元素，队列只允许在队尾插入元素和在队头删除元素。27 .二叉树中每个结点的两棵子树的高度差等于1。单选题*对错（正确答案）28 .二叉树

13、中每个结点有两棵非空子树或有两棵空子树。单选题*对错（正确答案）29 .若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n-1个非对（正确答案）错30 .具有12个结点的完全二叉树有5个度为2的结点。判断题*对（正确答案）错31 .二叉树中树的深度为k,那么二叉树的所有结点个数是2k-1。判断题*对错（正确答案）32 .对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i1个结点。判断题*对（正确答案）错33 .二叉树是非线性数据结构，下面说法正确的是？单选题*它不能用顺序存储结构存储；它不能用链式存储结构存储；顺序存储结构和链式存储结构都能存储；（正确答案）顺序存

14、储结构和链式存储结构都不能使用34 .把任意一棵树转换为二叉树后，这棵二叉树的形态是单选题*唯一的（正确答案）有多种有多种，但根结点都没有左孩子有多种，但根结点都没有右孩子35 .由3个结点所构成的二叉树有（）种形态。填空题*侨_案：5）36 .一棵具有257个结点的完全二叉树，它的深度为（）填空题*侨_案：9）37.一棵深度为6的满二叉树有（）个分支结点和（）个叶子。问题1:问题2:填空题*空1答案：31空2答案：3238 .键盘输入序列12,8,17,11,16,2,13,9,21,4,构成一棵二叉排序树。这棵树的层数应当为（）填空题*侨_案：4）39 .用5个权值3,2,4,5,1构造的

15、哈夫曼（Huffman）树的带权路径长度是（）填空题*侨_案：33）40 .若已知一棵二叉树的前序遍历序列是BEFCGD叩序序列是FEBGCHD则它的后序序列是（）填空题*答案里字母必须大写，且前后中间都不能留空白，如ABCDEF41 .图的两种存储结构：遍历图有哪两种遍历的方法*邻接矩阵、邻接表（正确答案）深度优先遍历、广度优先遍历（正确答案）42 .若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是*连通图（正确答案）3连通图（正确答案）连通图2（正确答案）43 .用邻接表表示图进行广度优先遍历时，通常借助来实现算法。*队列（正确答案）队列2（正确答案）4

16、4 .n个顶点的连通图用邻接矩阵表示时，该矩阵至少有个非零元素。*2（n-1）（正确答案）2（n-1）?%正确答案）45 .关键路径的基本概念*关键路径：从起点到终点的最长路径长度（路径上各活动持续时间之和）；2（正确答案）关键路径：从起点到终点的最长路径长度（路径上各活动持续时间之和）；（正确答案）46 .关于关键路径AOEl勺一些问题*事件是顶点，活动是边（正确答案）关键路径不唯一（正确答案）延期某个关键活动，整个工程的时间必定延期（正确答案）AO纲中一定没有顶点数超过1的强连通分量（正确答案）47 .线性表的顺序存储结构是一种（）的存储结构单选题*随机存取（正确答案）顺序存取索引存取散列

17、存取48 .链表不具有的特点是()单选题插入删除不需要移动元素可随机访问任一一元素(正确答案)不必事先估计存储空间所需空间与线性表长度成正比49 .申是一种特殊的线性表，其特殊性体现在()。单选题*(A) 可以顺序存储(B) 可以用链表存储(C) 数据元素是一个字符(正确答案)(D) 数据元素可以是多个字符50 .申是()。单选题*(A) 少于一个字母的序列(B) 任意个字母的序列(C) 不少于一个字符的序列(D) 有限个字符的序列(正确答案)51 .S1="good",S2="morning",执行串连接函数ConcatStr(S1,S后的结果为()单

18、选题*A."GOODMORNING"B.”goodmorning”C."GOODMORNING"D."goodmorning"(正确答案)52 .有如下代码chars="interesting"则s数组的的长度是()单选题*A.12(正确答案)C.13D.1053 .树最适合用来表示（）。单选题*A. 元素之间具有层次关系的数据（正确答案）B. 有序数据元素C. 无序数据元素D.元素之间无联系的数据54.现有一遗传”关系，设x是y的父亲，则x可以把他的属性遗传给V。表示该遗传关系最适合的数据结构为（）o单选题*A.

19、 树（正确答案）B. 数组C.图D.线性表55 .线性表具有n个（）的有限序列单选题*表兀素字符数据元素（正确答案）数据项56 .下列那一条是顺序存储结构的优点单选题*存储密度大（正确答案）插入运算方便删除运算方便可以方便的用于各种逻辑结构的存储表示57. 树形结构中元素之间存在一个对多个的关系判断题对（正确答案）错58 .先根遍历树正好等同于按遍历对应的二叉树单选题*A. 先根（正确答案）B. 中根C. 后根D.层次59 .将一棵树转成二叉树，根结点没有左子树。判断题*对错（正确答案）60 .后根遍历树正好等同于按遍历对应的二叉树。单选题*A. 先根B. 中根（正确答案）C. 后根D.层次判

20、断61 .赫夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。题*对（正确答案）错62 .赫夫曼树的结点个数不能是偶数。判断题*对（正确答案）错答案解析：n个权值构成的赫夫曼树共有2n-1个节点，为奇数63 .树最适合用来表示（）单选题*A有序数据元素B、无序数据元素C、元素之间具有分支层次关系的数据（正确答案）D、元素之间无联系的数据64 .下面那个是完全二叉树（）*AB7654C（止确答案）65.以下关于树和二叉树的描述，正确的是（）单选题*各结点的度均为2的树即为二叉树任一遍历序列可唯一确定一棵二叉树任何树都可以转换为唯一的二叉树与之对应（正确答案）树和二叉树都只能用链式存储实

21、现66.3个结点构成的二叉树，共有（）种单选题*5（正确答案）67.一棵深度为5的完全二叉树，至少包括（）个结点单选题*32311516（正确答案）68.由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。单选题*24487253（正确答案）69 .若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n1个非空指针域。判断题*对（正确答案）错70 .二叉树中每个结点的两棵子树的高度差等于1。判断题*对错（正确答案）71 .二叉树中每个结点有两棵非空子树或有两棵空子树。判断题*对错（正确答案）72.二叉树中所有结点个数是2k-1-1,其中k是树的深度。判断题

22、错（正确答案）73 .二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。判断题*对错（正确答案）74 .用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。判断题*对（正确答案）错75 .具有12个结点的完全二叉树有5个度为2的结点。判断题*对（正确答案）错76 .二叉树是非线性数据结构，所以（）。单选题*A. 它不能用顺序存储结构存储B. 它不能用链式存储结构存储；C. 顺序存储结构和链式存储结构都能存储；（正确答案）D.顺序存储结构和链式存储结构都不能使用77.设T是一棵有n个顶点的树，下列说法不正确的是（）。单选题*A.T有n

23、条边（正确答案）B.T是连通的C.T是无环的78.14.高度为n的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为n-1的满二叉树。在这里，树高等于叶结点的最大深度，根结点的深度为0,如果某个均衡的二叉树共有2381个结点，则该树的树高为（）。单选题*A.10B.11（正确答案）C.12D.1379 .5.如果树根算第1层，那么一棵n层的二叉树最多有（）个结点。单选题*A.2n-1（正确答案）B.2nC.2n+1D.2n+180 .一个包含n个分支结点（非叶结点）的非空二叉树，它的叶结点数目最多为（）。单选题*A. 2n+1B. 2n-1C. n-1D. n+1（正确答案）81.

24、7.如果根结点的深度记为1,则一棵恰有2011个叶结点的二叉树的深度最少是（）。单选题*A. 10B. 11C. 12（正确答案）D. 1382. 已知一棵二叉树有10个节点，则其中至多有（）个节点有2个子节点。单选题*A.4（正确答案）B.5C.6D.783. 5.完全二叉树共有2*N-1个结点，则它的叶节点数是（）。单选题*A.N-1B.N（正确答案）C.2*ND.2*N-184. 16.一棵具有5层的满二叉树中结点数为（）。单选题*A.31（正确答案）B.32C.33D.1685. 17.如果根的高度为1,具有61个结点的完全二叉树的高度为（）。单选题*A.5B.6（正确答案）C.7D.

25、8右依次86.19.完全二叉树的顺序存储方案，是指将完全二叉树的结点从上至下、从左至存放到一个顺序结构的数组中。假定根结点存放在数组的1号位置，则第k号结点的父结点如果存在的话，应当存放在数组的（）号位置。单选题*A.2kB.2k+1C.k/2下取整（正确答案）D.（k+1）/2下取整87.已知6个结点的二叉树的先根遍历是123456（数字为结点的编号，以下同），后根遍历是325641,则该二叉树的可能的中根遍历是（）单选题*A.321465B.321546（正确答案）C.213546D.23146588.已知7个结点的二叉树的先根遍历是1245637（数字为结点的编号，以下同），中根遍历是4

26、265173,则该二叉树白人后根遍历是（）单选题*A.4652731（正确答案）B.4652137C.4231547D.465317289.二叉树T,已知其先根遍历是1243576颔字为结点的编号，以下同），中根遍历是2415736,则该二叉树白人后根遍历是（）。单选题*A.4257631B.4275631（正确答案）C.7425631D.427653190.17.一棵二叉树的前序遍历序列是ABCDEF隔序遍历序歹（J是CBFEGDA，则根结点的左子树的结点个数可能是（）。单选题*A.2（正确答案）B.3C.4D.51.6.1. 果一棵二叉树的中序遍历是BAC,那么它的先序遍历不可能是（）。单

27、选题*A. ABCB. CBAC. ACB（正确答案）D. BAC92 .二叉树的（）第一个访问的节点是根节点。单选题*A. 先序遍历（正确答案）B. 中序遍历C. 后序遍历D. 以上都是93 .16.前序遍历序列与中序遍历序列相同的二叉树为（）。单选题*A. 根结点无左子树B. 根结点无右子树C. 只有根结点的二叉树或非叶子结点只有左子树的二叉树D.只有根结点的二叉树或非叶子结点只有右子树的二叉树94 .表达式a*（b+c）-d的后缀表达式是：单选题A.abcd*+-B.abc+*d-（正确答案）C.abc*+d-D.-+*abcd95.9.前缀表达式“+3*2+512的值是（）。单选题*A

28、.23B.25C.37（正确答案）D.6596 .树最适合用来表示（）单选题*A有序数据元素R无序数据元素G元素之间具有分支层次关系的数据（正确答案）D元素之间无联系的数据97 .在完全二叉树中，若一个结点是叶结点，则它没（）o单选题*A左子结点B、右子结点C左子结点和右子结点（正确答案）D以上说法都不对98 .有三个结点的二叉树有（）种形态。单选题*355（正确答案）99.下面那个是完全二叉树（）*ABC（正确答案）D（正确答案）100.若一棵二叉树具有10个度为2的结点，5个度为1的结点，个则度为0的结点数是（）单选题*A9B、11（正确答案）C、15口不确定101.在一棵二叉树上第5层的

29、结点数最多是多少（）个？单选题141516 （正确答案）17 2A（k-1）1。所以第答案解析：一棵二叉树，如果每个结点都是是满的，那么会满足5层至多有2A（5-1）=16个结点!102.深度为6的二叉树最多有（）个结点。单选题*6463（正确答案）3331答案解析：见二叉树性质103.一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为（）个？单选题106. 一个具有 1025个结点的二叉树的高 h 为（）?单选题二叉树的高度的公式是什么？218216219（正确答案）217答案解析：假设n表示二叉树的所有结点数，n0表示度为0的结点（叶子结点），n1表示度为1的结点

30、，n2表示度为2的结点：n=n0+n1+n2,又由二叉树性质：n2=n0-1,将n2带入得总结点数n=70+80+70-1=219104.一棵具有5层的满二叉树中结点数为（）。单选题*A.31（正确答案）B.32C.33D.16105.如果根的高度为1,具有61个结点的完全二叉树的高度为（）。单选题*A.5B.6（正确答案）C.7D.8答案解析：根据二叉树性质，从所给答案中取值计算。111011至1025之间(正确答案)10至1024之间答案解析：若该二叉树为完全二叉树，根据二叉树性质或计算某一深度的满二叉树的结点总数，向下取整log2(1025)+1=log2(1024+1=log2(2A1

31、0)+1=10+1=11；或深度为10的满二叉树有2A10-1=1024-1=1023,1025>1023所以至少11层。该二叉树有至少有11层。层数最多时：每层一个结点，有1025层107 .已知一棵完全二叉树含有1001个结点，那么它有()个度为2的结点。单选题*250500(正确答案)501505答案解析：设二叉树中度为0的叶子结点个数为n0,度为1结点个数为n1,度为2结点个数为n2,于是n0+n1+n2=1001根据二叉树性质：n0=n2+1，代入得到，2n2+1+n1=1001由于完全二叉树的n1只能是0或者1,为满足2n2+1+n1=1001，只有n1=0时上式才能成立，因

32、此n2=500,n0=501。此题有时也考叶子结点数目。108 .已知某二叉树的后序遍历序列是dabec中序遍历序列是debac它的前序遍历是()。单选题*A.acbedB.decabC.deabcD.cedb&正确答案)109 .二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK;中序遍历：HFIEJKG该二叉树根的右子树的根是：单选题*A.EB.FC.G（正确答案）D.H答案解析：注意审题，要求二叉树根右子树的根结点，由先序序列可知二叉树的根结点为E,所以在中序序列中E的左子树不需考虑。110 .表达式a*（b+c）-d的后缀表达式是：单选题*A.abcd*+-B.abc+*

33、d-（正确答案）C.abc*+d-D.-+*abcd111.完全二叉树的顺序存储方案，是指将完全二叉树的结点从上至下、从左至右依次存放到一个顺序结构的数组中。假定根结点存放在数组的1号位置，则第k号结点的父结点如果存在的话，应当存放在数组的（）号位置。单选题*A.2kB.2k+1C.k/2下取整（正确答案）D.（k+1）/2下取整112.以下说法错误的是（）。单选题*树形结构的特点是一个结点可以有多个直接前趋（正确答案）线性结构中的一个结点至多只有一个直接后继树形结构可以表达（组织）更复杂的数据树（及一切树形结构）是一种“分支层次”结构A.二叉树不能用顺序存储结构存储B.二叉树不能用链式存储结

34、构存储；C.二叉树顺序存储结构和链式存储结构都能存储；（正确答案）D.二叉树顺序存储结构和链式存储结构都不能使用114.3个结点构成的二叉树，共有（）种单选题*5（正确答案）115.二叉树的第i层上最多含有结点数为（）单选题*i次方i-1次方减1i-1次方（正确答案）i次方减1116.下列正确的是（）如图先序遍历结果：ABCDFE中序遍历结果：BDCAFE后序遍历结果：DCBFEA正确答案）117.如果树根算第1层，那么一棵n层的二叉树最多有（）个结点。单选题*A.2An-1（正确答案）B.2A（n-1）OnD.2An+1答案解析：根据二叉树性质，或让n取简单的值进行计算，如n=2,n=3等。118 .已知一棵二叉树有10个结点，则其中至多有（）个度为2的结点。单选题*A.4（正确答案）B.5C.6D.7答案解析：设总结点数为n,度为0,1,2的结点数分别为no,n1,n2则有：n=n0+n1+n2根据二叉树性质将n0=n2+1和n=10带入得：10=2n2+1+n1,要使n2最大）只有取n1=1，此时n2=4o119 .完全二叉树共有2*N-1个结点，则它的叶节点数是（）。单选题*A.N-1B.N（正确答案）C.2*ND.2*N-1答案解析：取N为某一具体值。120. 一棵具有5 层的满二叉树中结点数为（）。单选题O单选题*A.3