数据结构期末考试.pdf

《数据结构期末考试.pdf》由会员分享，可在线阅读，更多相关《数据结构期末考试.pdf（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构期末考试L下面关于线性表的叙述中，错 误 的 是 0 单选题*A.线性表采用顺序储存，必须占用一片连续的储存单元。B.线性表采用顺序储存，便于进行插入和删除操作。C.线性表采用链接储存，不必占用一片连续的储存单元。D.线性表采用链接储存,便于出入和删除操作。2.在有n 个结点顺序表上做插入，删除结点运算的时间复杂度为()o 单选题*A.O(l)B.O(n)C.O(nA2)D.O(log2n)3.两个指针P 和 Q,分别指向单链表的两个元素，P 所指元素是Q 所指元素前驱条件 是 0 单选题*A.P-next=Q-nextB.P-next=QC.Q-next=PD.P=Q4.在单链表中，

2、增加头结点的目的()单选题*A.使单链表至少有一个结点B.标志表中首结点的位置C.方便运算实现 再 答案)D.说明该单链表是线性表的链式储存结构5.在顺序表中，只 要 知 道（）就可以求出任意一个结点的存储地址 单选题*A。，基地址B.结点大小C.向量大小D.基地址和结点大小6.链表不具备的特点是（）单选题*A 随机访问（正确答案）B 不必事先估计存储空间C 插入删除时不需移动元素D 所需空间与线性表成正比7.在（）的运算中，使用顺序表比链表好 单选题*A 插入B 根据序号查找C 删除D 根据元素查找8.在单链表指针为P 的节点之后插入指针为S 的结点，正确的查找条件是（）单选题*A,p-ne

3、xt=s;s-next=p-nextB,s-next=p-next;p-next=sC,p-next=s;p-next=s-nextA,p-next=s-next;p-next=s9.用链表表示线性表的优点（）单选题*A 便于进行插入和删除操作B 便于随机存储C 占用的存储空间较顺序表少D 元素的物理顺序与与逻辑顺序一致10在一个长度为n 的顺序表中，若要删除第i（tiW n）个元素，则需向前移动（）个元素 单选题*An-i+1Bn-i-1Cn-i（正确答案）Di11在一个长度为n 的顺序表中，若要在第i（lWKn）个元素之前插入一个元素，则需向 后 移 动（）个元素 单选题*An-i+1（正

4、确答案）Bn-i-1Cn-iDi12设 P 为指向单循环链表上某结点的指针，则*p 的直接 前 驱（）单选题*A 找不到B 查找时间复杂度为0（1）C 查找时间复杂度为O（n）（正确答案）D 查找结点的次数约为n13.等概率情况下，在有n 个结点的顺序表上做插入结点运算，需平均移动结点的数 目 为（）。单选题*A.nB.(n-l)/2C.n/2(正确答案)D.(n+l)/214.以下链表结构中，从当前结点出发能够访问到任意结点的是()。单选题*A.单向链表和双向链表B.循环链表和单链表C.循环链表和双向链表D.单向链表，双向链表和循环链表15.对具有n 个结点的线性表进行插入或删除操作，所需的

5、算法时间复杂度为0 o 单选题*A.O(n2)B.O(nlog2n)C.O(log2n)D.O(n)1.对于栈操作数据的原则是0 o 单选题*A.先进先出B.后进先出C.后进后出D.不分顺序2.有6 个元素按6 5 4 3 2.1 的顺序进栈，问 下 列()不是合法的出栈序列？单选题*A.5 4 3 6 1 2B.45 3 1 26C.3 4 6 5 2 1（正 中D.2 3 4 1 5 63.插入和删除只能在一端进行的线性表，称为C 单选题*A.队列B.循环队列C.栈D.循环栈4.输入序列为A B C,可以变为C B A,经过的栈操作为（）单选题*A.push,pop.push.pop.pu

6、sh.popB.push,push,push,pop,pop,popC.push.push.pop.pop.push,popD.push,pop,push,push,pop,pop5.设有编号为12 3.4 的四辆列车，顺序进入一个栈结构的站台，下列不可能的出站 顺 序 为（）单选题】*A.1234B.1243C.1324D.1423（正确答案）6.如果以链表作为栈的存储结构，则出栈操作时（）单选题*A.必须判别栈是否满B.必须判别栈是否空C.必须判别栈元素类型D.队栈可不做任何判别7.顺序栈存储空间的实现使用（）存储栈元素。单选题*A.链表B.数组C.循环链表C.变量8.在C 语言中，一个顺

7、序栈一旦被声明，其占用空间的大小（）.单选题*A.已固定（正确答案）B.不固定C.可以改变D.动态变化9.从一个栈顶指针为top的链栈中删除一个结点时，用 x 保存被删除的结点，应执行 下 列（）命令 单选题】*A.x=top:top=top-next;B.top=top-next:x-top-data;C.x-top-data;D.x=top-data:top=top-next;10 4 个元素按A,B.C,D顺序进S 栈，执行两次Pop（S,x）运算后，栈项元素的值是（B）.单选题*A.A（正确答案）B.BC.CD.D11.在一个栈顶指针为H S的链栈中，将一个S 指针所指的结点入栈，应执

8、行下列（B）命令。单选题*A.HS-next=S;国答案）B.S-next=HS-next;HS-next=S;c.S-next=HS-next;HS=S;D.S-next=HS;HS=HS-next;12.向顺序栈中压入元素时，（）。单选题*A.先存入元素，后移动栈顶指针B.先移动栈顶指针，后存入元素C.谁先谁后无关紧要D.同时进行13.一个枝的入栈次序ABCDE,.则栈的不可能的输出序列是心（C）单选题*A.EDCBAB.DECBAc.DCEABD.ABCDE14.没有一个顺序栈S,元素A.B.CD.E.F,依次进栈，如果6 个元素出栈的顺序是B.D.CFEA.的容量至少应是（）.单选题*

9、A 3 正确答案）B.4C.5D.6L对于队列操作数据的原则是（）单选题*A.先进先出B.后进先出C.先进后出D.不分顺序2.队列是限定在（）进行操作的线性表（）。单选题*A.中间B队首C.队尾D.端点（正确答案）3.队列中的元素个数是（）单选题*A.不变的B.可变的（正确答案）C.任意的D.04.同一队列内各元素的类型（）。单选题*A.必须一致B.不能一致C.可以不一一致D.不限制5.队列是一一个（）线性表结构。单选题*A.不加限制的B.推广了的C.加了限制的D.非6.当利用大小为n 的数组顺序存储个队列时，该队列的最后一个元素的下标为（）单选题】*A.n-2B.n-1（正确答案）C.nD.

10、n+17.最大容量为n 的循环队列，队尾指针是rear,队头是front,则队空的条件是（）。单选题*A.（rear+1）%n=frontB.rear-=front:答案）C.rear+l=frontD.（rear-1）%n=front8.最大容量为n 的循环队列，队尾指针是rear,队头是front,则队满的条件是（）单选题*A.（rear+1）%n=front 正确笞案）B.rear-=frontC.rear+1 frontD.（rear-1）%n=-front9.循环队列占用的空间（）单选题*A.必须连续B.不必连续C.不能连续D.可以不连续10.存放循环队列元素的数组data有 10个

11、元素，则 data数组的下标范围是（）单选题*A.0-10B.09（正确答案）C.1-9D.1-1011.若进队的序列为：A,B,C,D,则出队的序列是（）。单选题*A.B,C,D,AB.A,C,B,DC.A,B,C,D E确答案）D.C,B,D,A12.4个元素按:A,B,C,D 顺序连续进队Q,则队尾元素是（）o 单选题*A.AB.BC.CD.D（正确答案）13.循环队列SQ 队满的条件是（）。单选题*A.SQ-rear SQ-frontB.（SQ-rear+l）%MAXLEN=SQ-front 正确答案）C.SQ-rear=0D.SQ-front=014.设链栈中结点的结构:data为数

12、据域，next为指针域，且 top是栈顶指针。若想在链栈的栈顶插入一个由指针s 所指的结点，则应执行下列（）操作。单选题A.s-next=top-next;top-next=s;:答案）B.top-next=s;C.s-next=top;top=top-next;D.s-next=top;top=s;15.若用一个大小为6 的数组来实现循环队列，且当前front和 rear的值分别为3 和0,当从队列中删除一个元素，再加入两个元素后，front和 rear的值分别为（）。单选题】*A.5 和 1B.4和 2（正确答案）C.2 和 4D.1 和 516.栈和队列的共同点是（）o 单选题*A.都是

13、先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点17.栈和队都是（）。单选题*A.顺序存储的线性结构B.链式存储的非线性结构C.限制存取点的线性结构D.限制存取点的非线性结构1.以下说法正确的是（）。单选题*A,串是一种特殊的线性表B.串的长度必须大于零C.串中的元素只能是字母D.空串就是空白串2.设有一个字符串S=Welcome to Shenyang!”，问该串的长度为（）。单选题*A.18B.19C.20（正确答案）D.213.设有一个字符串S=abcdefgh，问该串的最大子串个数为（）。单选题*A.8B.36C.37（正确答案）D.94.两个字符串相等的条件是（

14、）单选题*A.两串的长度相等B.两串包含的字符相同C.两串的长度相等，并且两串包含的字符相同D.两串的长度相等，并且对应位置上的字符相同 个案5.某串的长度小于一个常数，则 采 用（）存储方式最节省空间。单选题*A.链式B.顺序C.堆结构D.无法确定6.以下论述正确的是（）。单选题*A.空串与空格串是相同的B.tel Teleptone的子串C.空串是零个字符的串D.空串的长度等于17.以下论断正确的是（）。单选题*A.“是空串，是空格串（正确答案）B.B.BEJJING 是 BEI JING的子串C.C.somethingSomethigD.D.BrT=BITE”8.设有两个串S1和 S 2

15、,则 StrCompare（Sl,S2）运 算 称 做（）。单选题*A.串连接B.模式匹配C.求子串D.串比较（正确答案）9串的模式匹配是指（）。单选题*A.判断两个串是否相等B.对两个串比较大小C.找某字符在主串中第一次出现的位置D.找某子串在主串中第一次出现的第一个字符位置10.若 SubString（Sub,S,pos,len）表示用Sub返回串S 的第pos个字符起长度为len 的子串的操作，则对 S=Data Structure,Substring（Sub,S,6,3）的结果为0 o 单选题*A.ta StrB.Str(正确答案)C.”tru“D.以上均不正确11.若Strlndex

16、t(S,T)表示求T 在 S 中的位置的操作，则对于S=Beijing and Nanjing,T=jing,StrIndex(S,T)的结 果 为()o 单选题*A.2B.3C.4(正确答案)D.1612.S=morming,执行求子串函数SubStr(求 2,2)后的结果为()。单选题*A.”mo正确答案)C.”inD.”ng13.S l=Good,)S2=Moming,执行串连接函数 ConcatStr(Sl,S2)后的结果为(A)0 A.“GoodMorning 单选题*B.Good Moming(正确答案)C.GOODMORNINGD.GOOD MORNING”14.Sl=good,

17、S2=m orning,执行函数 SubStr(S2,4,LenStr(Sl)后的结果为0 o 单选题*A.goodB.”ning“F.确答案)C.”goD.morn15.设串 S1=ABCDEFG,S2=PQRST”，贝ConcatStr(SubStr(Sl,2,LenStr(S2),subStr(Sl,LenStr(S2),2)的结果串为()o 单选题*A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF16.广义表是线性表的推广，它们之间的区别在于()。单选题*A.能否使用子表(正确答案)B.能否使用原子项C.是否能为空D.表的长度17.广义表(a,b),c,d)的 表 尾

18、 是()0 单选题*A.aB.bC.(a,b)D.(c,d)(正确答案)18.广义表(a,b,c,d,e)的 表 尾 是()。单选题*A.(b,c,d,e)确答案)B.()c.（a,b,c,d,e）D.（e）1.假设在一棵二叉树中，双分支结点数为1 5,单分支结点数为30个，则叶子结点数 为（）A.15 单选题*B.16（正确答案）C.17D.472.在一棵二叉树上第3 层上的结点数最多为（）A.2 单选题*B.4（正确答案）C.6D.83.用顺序存储的方法将完全二叉树中所有结点逐层存放在数组a an中，结点a的若有左孩子:其左孩子的编号为结点（）。单选题*A.a2i+lB.a2i-llc.a

19、i/2D.a2i（正确答案）4.已知一棵完全二叉树的结点总数为9 个，则最后一层的结点数为（）o 单选题*A.1B.2（正确答案）C.3D.45.具有35个结点的完全二叉树的深度为（）。单选题*A.5B.6（正确答案）C.7D.86.二叉树的先序遍历序列为ABC的不同二叉树有（C）种形态。单选题*A.3（正确答案）B.4c.5D.67.设有一棵二叉树，其先序遍历序列是：ABCDEFG,中序遍历序列是：CBAEDFG,则该二叉树的后序遍历序列是（）单选题*A.CBDFGEAB.CBDGFEAC.CBEFGDAD.CBECFDA8.某二叉树的后序遍历序列为D A B EC,中序遍历序列为D EBA

20、 C,则先序遍历序列 为（）单选题*A.ACBEDB.DECABc.DEABCD.CEDBA正确答案）9.在完全二叉树中，如果一个结点是叶子结点，则 它 没 有（）。单选题*A.左孩子结点B.右孩子结点C.左、右孩子结点D.左、右孩子结点和兄弟结点1（）.在下列存储形式中，哪一种不是树的存储形式（）单选题*A.双亲表示法B.孩子链表表示法C.孩子兄弟链表表示法D.顺序存储表示法11、树最适合用来表示（）单选题*A.有序数据元素C.无序数据元素B.元素之间具有分支层次关系的数据D.元素之间无联系的数据13.在一棵度为3 的树中，度为3 的结点数为2 个，度为2 的结点数为1个，度 为 1的结点数为2 个那么度为0 的结点数有（C）个。单选题*A.4（正确答案）B.5c.6D.714.任何一棵二叉树的叶子结点在先序、中序、后序遍历序列中的相对次序（）单选题*A.不发生改变（正 田B.发生改变C.不能确定D.以上都不对15.A、B 为一棵二叉树上的两个叶子结点，在中序遍历时，A 在 B 前的条件是()。单选题*A.A 在B 的右方B.A 是 B 的祖C.A 在 B 的左方(正确答案)D.A是 B 的子孙