数据结构期末考试.docx

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

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

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

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

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

5、n个结点的线性表进行插入或删除操作，所需的算法时间复杂度为（）。 单选题 *A.O(n2)B.O(nlog2n)C.O(log2n)D.O(n)(正确答案)1.对于栈操作数据的原则是（）。 单选题 *A.先进先出B.后进先出(正确答案)C.后进后出D.不分顺序2.有6个元素按6.5.4.3.2.1的顺序进栈，问下列（）不是合法的出栈序列? 单选题 *A.5 4 3 6 1 2B.4 5 3 1 2 6C.3 4 6 5 2 1(正确答案)D.2 3 4 1 5 63.插入和删除只能在一端进行的线性表，称为C 单选题 *A.队列(正确答案)B.循环队列C.栈D.循环栈4.输入序列为ABC，可以变

6、为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,pop5.设有编号为1.2.3.4的四辆列车，顺序进入一个栈结构的站台，下列不可能的出站顺序为（） 单选题 *A.1234B.1243C.1324D.1423(正确答案)6.如果以链表作为栈的存储结构，则出栈操作时（） 单选题 *A.必须判别栈是否满B.必须判别栈是否空(正确答案)C.必须判别栈元素类型D.队栈可不做任何判别7.

7、顺序栈存储空间的实现使用（）存储栈元素。 单选题 *A.链表B.数组(正确答案)C.循环链表C.变量8.在C语言中，一个顺序栈一旦被声明，其占用空间的大小（）. 单选题 *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)运算后，栈项元素

8、的值是(B). 单选题 *A.A(正确答案).C.CD.D11.在一个栈顶指针为HS的链栈中，将一个S指针所指的结点入栈，应执行下列(B)命令。 单选题 *A.HS-next=S;(正确答案).S-next=HS-next;HS-next=S;.S-next=HS-next;HS=S;D.S-next=HS;HS=HS-next;12.向顺序栈中压入元素时，（）。 单选题 *A.先存入元素，后移动栈顶指针B.先移动栈顶指针，后存入元素(正确答案)C.谁先谁后无关紧要D.同时进行13.一个枝的入栈次序ABCDE,.则栈的不可能的输出序列是心(C). 单选题 *A.EDCBA(正确答案).DECB

9、A.DCEABD.ABCDE14.没有一个顺序栈S,元素A.B.CD.E.F,依次进栈，如果6个元素出栈的顺序是B.D.CFEA.的容量至少应是（）. 单选题 *A.3(正确答案)B. 4C. 5D. 61.对于队列操作数据的原则是（） 单选题 *A.先进先出(正确答案)B.后进先出C.先进后出D.不分顺序2.队列是限定在()进行操作的线性表（）。 单选题 *A.中间B.队首C.队尾D.端点(正确答案)3.队列中的元素个数是（） 单选题 *A.不变的B.可变的(正确答案)C.任意的D.04.同一队列内各元素的类型（）。 单选题 *A.必须一致(正确答案)B.不能一致C.可以不一-致D.不限制5

10、.队列是一一个（）线性表结构。 单选题 *A.不加限制的B.推广了的C.加了限制的(正确答案)D.非6.当利用大小为n的数组顺序存储个队列时，该队列的最后一个元素的下标为（） 单选题 *A.n-2B.n-1(正确答案)C.nD.n+17.最大容量为n的循环队列，队尾指针是rear,队头是front,则队空的条件是（）。 单选题 *A.(rear+1)%n=frontB.rear-=front(正确答案)C.rear+1=-frontD.(rear-1)%n=front8.最大容量为n的循环队列，队尾指针是rear,队头是front,则队满的条件是（） 单选题 *A.(rear+1)%n=fro

11、nt(正确答案)B.rear-=frontC.rear+1-frontD.(rear-1)%n=-front9.循环队列占用的空间（） 单选题 *A.必须连续(正确答案)B.不必连续C.不能连续D.可以不连续10.存放循环队列元素的数组data有10个元素，则data数组的下标范围是（） 单选题 *A.010B.09(正确答案)C.19D.11011.若进队的序列为:A,B,C,D,则出队的序列是（）。 单选题 *A.B,C,D,AB.A,C,B,DC.A,B,C,D(正确答案)D.C,B,D,A12.4个元素按:A,B,C,D顺序连续进队Q，则队尾元素是（）。 单选题 *A.AB.BC.CD

12、.D(正确答案)13.循环队列SQ队满的条件是（）。 单选题 *A.SQ-rear-SQ-frontB.(SQ-rear+1)%MAXLEN=SQ-front(正确答案)C.SQ-rear=-=0D.SQ-front=014.设链栈中结点的结构:data为数据域，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的数组来实现

13、循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为（）。 单选题 *A.5和1B.4和2(正确答案)C.2和4D.1和516.栈和队列的共同点是（）。 单选题 *A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素(正确答案)D.没有共同点17.栈和队都是（）。 单选题 *A.顺序存储的线性结构B.链式存储的非线性结构C.限制存取点的线性结构(正确答案)D.限制存取点的非线性结构1.以下说法正确的是（）。 单选题 *A，串是一种特殊的线性表(正确答案)B.串的长度必须大于零C.串中的元素只能是字母D.空串就

14、是空白串2.设有一个字符串S=“WelcometoShenyang！”，问该串的长度为（）。 单选题 *A.18B.19C.20(正确答案)D.213.设有一个字符串S=“abcdefgh“，问该串的最大子串个数为（）。 单选题 *A.8B.36C.37(正确答案)D.94.两个字符串相等的条件是（） 单选题 *A.两串的长度相等B.两串包含的字符相同C.两串的长度相等，并且两串包含的字符相同D.两串的长度相等，并且对应位置上的字符相同(正确答案)5.某串的长度小于个常数，则采用（）存储方式最节省空间。 单选题 *A.链式B.顺序(正确答案)C.堆结构D.无法确定6.以下论述正确的是（）。 单

15、选题 *A.空串与空格串是相同的B.tel是Teleptone的子串C.空串是零个字符的串(正确答案)D.空串的长度等于17.以下论断正确的是（）。 单选题 *A.“”是空串， 是空格串(正确答案)B.B.BEJJING是BEIJING的子串C.C.somethingSomethigD.D.“BIT”=“BITE”8.设有两个串S1和S2，则StrCompare(S1，S2)运算称做（）。 单选题 *A.串连接B.模式匹配C.求子串D.串比较(正确答案)9.串的模式匹配是指（）。 单选题 *A.判断两个串是否相等B.对两个串比较大小C.找某字符在主串中第一次出现的位置D.找某子串在主串中第一次

16、出现的第一个字符位置(正确答案)10.若SubString(Sub，S，pos，len)表示用Sub返回串S的第pos个字符起长度为len的子串的操作，则对S=DataStructure，Substring(Sub，S，6，3)的结果为（）。 单选题 *A.taStrB.Str“(正确答案)C.”tru“D.以上均不正确11.若Strlndext(S，T)表示求T在S中的位置的操作，则对于S=BeijingandNanjing，T=jing，StrIndex(S，T)的结果为（）。 单选题 *A.2B.3C.4(正确答案)D.1612.S=morming，执行求子串函数SubStr(S，2，2

17、)后的结果为（）。 单选题 *A.”moB.”or“(正确答案)C.”in“D.”ng“13.S1=Good”，S2=Morning，执行串连接函数ConcatStr(S1，S2)后的结果为( A )。A.“GoodMorning“ 单选题 *B.GoodMorning“(正确答案)C.GOODMORNING”D.GOODMORNING“14.S1=good，S2=morning，执行函数SubStr(S2，4，LenStr(S1)后的结果为（）。 单选题 *A.”good”B.”ning“(正确答案)C.”go“D.morn15.设串S1=”ABCDEFG,S2=“PQRST”，则Conca

18、tStr(SubStr(S1,2,LenStr(S2),subStr(S1，LenStr(S2)，2)的结果串为（）。 单选题 *A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF(正确答案)16.广义表是线性表的推广，它们之间的区别在于（）。 单选题 *A.能否使用子表(正确答案)B.能否使用原子项C.是否能为空D.表的长度17.广义表(a，b)，c，d)的表尾是（）。 单选题 *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.假设

19、在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（）A.15 单选题 *B.16(正确答案)C.17D.472.在一棵二叉树上第3层上的结点数最多为（）A.2 单选题 *B.4(正确答案)C.6D.83.用顺序存储的方法将完全二叉树中所有结点逐层存放在数组aan中，结点a的若有左孩子:其左孩子的编号为结点（）。 单选题 *A.a2i+1B.a2i-1c.ai/2D.a2i(正确答案)4.已知一棵完全二叉树的结点总数为9个，则最后一层的结点数为（）。 单选题 *A.1B.2(正确答案)C.3D.45.具有35个结点的完全二叉树的深度为（）。 单选题 *A.5B.6(正确答

20、案)C.7D.86.二叉树的先序遍历序列为 ABC 的不同二叉树有( C )种形态。 单选题 *A.3(正确答案)B.4c. 5D. 67.设有一棵二叉树，其先序遍历序列是：ABCDEFG，中序遍历序列是：CBAEDFG，则该二叉树的后序遍历序列是（） 单选题 *A. CBDFGEAB.CBDGFEAC.CBEFGDAD. CBECFDA(正确答案)8.某二叉树的后序遍历序列为 DABEC，中序遍历序列为 DEBAC，则先序遍历序列为（） 单选题 *A. ACBEDB. DECABc. DEABCD. CEDBA(正确答案)9.在完全二叉树中，如果一个结点是叶子结点，则它没有（）。 单选题 *

21、A.左孩子结点B.右孩子结点C.左、右孩子结点(正确答案)D.左、右孩子结点和兄弟结点10.在下列存储形式中，哪一种不是树的存储形式（） 单选题 *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的子孙