数据结构期末考试.docx

数据结构期末考试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=PD.P=Q4.在单链表中，增加头结点的目的（） 单选题 *A.使单链表至少有一个结点B.标志表中首结点的位置C.方便运算实现(正确答案)D.说明该单链表是线性表的链式储存结构5.在顺序表中，只要知道（）就可以求出任意一个结点的存储地址 单选题 *A。，基地址B结点大小C向量大小D.基地址和结点大小(正确答案)6.链表不具备的特点是（） 单选题 *A随机访问(正确答案)B不必事先估计存储空间C插入删除时不需移动元素D所需空间与线性表成正比7.在（）的运算中，使用顺序表比链表好 单选题 *A插入B根据序号查找(正确答案)C删除D根据元素查找8.在单链表指针为P的节点之后插入指针为S的结点，正确的查找条件是（） 单选题 *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)个元素之前插入一个元素，则需向后移动（）个元素 单选题 *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.对具有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，可以变为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.顺序栈存储空间的实现使用（）存储栈元素。 单选题 *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)运算后，栈项元素的值是(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(正确答案). DECBA. 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.队列是一一个（）线性表结构。 单选题 *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= =front(正确答案)B. rear- = =frontC. rear+1-frontD. (rear-1) % n= -front9.循环队列占用的空间（） 单选题 *A.必须连续(正确答案)B.不必连续C.不能连续D.可以不连续10.存放循环队列元素的数组data有10个元素，则data数组的下标范围是（） 单选题 *A.010B.09(正确答案)C.19D.1 1011.若进队的序列为: 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. 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的数组来实现循环队列，且当前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.空串就是空白串2.设有一个字符串S=“Welcome to Shenyang！”，问该串的长度为（）。 单选题 *A.18B.19C.20(正确答案)D.213.设有一个字符串S=“abcdefgh“，问该串的最大子串个数为（）。 单选题 *A.8B.36C.37(正确答案)D.94.两个字符串相等的条件是（） 单选题 *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. "something"<"SomethigD. D.“BIT”=“BITE”8.设有两个串S1和S2，则 StrCompare(S1，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)的结果为（）。 单选题 *A. "ta StrB. "Str“(正确答案)C.”tru“D.以上均不正确11.若 Strlndext(S，T)表示求T在S中的位置的操作，则对于S=" Beijing and Nanjing"，T="jing"，StrIndex(S，T)的结果为（）。 单选题 *A.2B.3C.4(正确答案)D.1612.S=" morming"，执行求子串函数 SubStr(S，2，2)后的结果为（）。 单选题 *A.”moB.”or“(正确答案)C. ”in“D.”ng“13.S1="Good”，S2="Morning"，执行串连接函数 ConcatStr(S1，S2)后的结果为( A )。A. “GoodMorning“ 单选题 *B. "Good Morning“(正确答案)C. "GOODMORNING”D."GOOD MORNING“14.S1="good"，S2=" morning"，执行函数SubStr(S2，4，LenStr(S1)后的结果为（）。 单选题 *A.”good”B. ”ning“(正确答案)C. ”go“D. "morn"15.设串S1=”ABCDEFG", S2=“PQRST”，则ConcatStr(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.假设在一棵二叉树中，双分支结点数为 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(正确答案)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.在完全二叉树中，如果一个结点是叶子结点，则它没有（）。 单选题 *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的子孙