搜索
数据结构期中期末选择判断复习题判断题：U1-U31.（×）数据元素是数据的最小单位。2.（√）健壮的算法不会因非法的输入数据而出现莫名其妙的状态。3.（×）数据的逻辑结构是指数据的各数据项之间的逻辑关系。4.（×）数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构。5.（×）数据的物理结构是指数据在计算机内的实际存储形式。6.（×）数据结构的抽象操作的定义与具体实现有关。7.（×）顺序存储方式的优点是存储密度大，且插入，删除运算效率高。8.（√）顺序存储方式插入和删除时的效率太低，在这方面它不如链式存储方式好。9.（√）顺序存储结构的主要缺点是不利于插入和删除操作。10.（×）对任何数据结构链式存储结构一定优于顺序存储结构。11.（×）取线性表的第i个元素的时间同i的大小有关。12.（√）线性表、栈和队列都是线性结构。13.（√）链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序存储结构中效率高。14.（×）线性表中每一个元素均存在唯一一个前驱和唯一一个后继。15.（×）循环链表不是线性表。16.（×）线性表的长度是线性表所占用的存储空间的大小。17.（×）在单链表表示的线性表中，取线性表的第i个元素操作的时间复杂度为O(1)。18.（√）删除带头结点单链表的第一个元素结点的时间复杂度是O(1)。19.（√）栈是实现过程和函数等子程序所必需的结构。20.（√）栈是一种插入与删除操作都限定在表的一端进行的线性表。21.（√）若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列3,2,5,6,4,1。22.（×）在顺序存储结构表示的栈中删除一个元素时可能会引起栈内数据元素的移动。23.（√）栈既可以采用顺序存储结构表示也可以采用链式存储结构表示。24.（×）队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。25.（√）无论队列采用顺序存储结构还是采用链式存储结构，入队列和出队列操作的时间复杂度均为O(1)。26.（×）循环队列就是用循环链表表示的队列。27.（×）队列和栈都是运算受限的线性表，只允许在表的两端进行运算。U4-U51.（）串是一种数据对象和操作都特殊的线性表。2.（）KMP算法的特点是在模式匹配时指示主串的指针不会变小。3.（）设模式串的长度为m，目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。4.（）数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。5.（）数组不适合作为任何二叉树的存储结构。6.（）从逻辑结构上看，n维数组的每个元素均属于n个向量。7.（）稀疏矩阵压缩存储后，必会失去随机存取功能。8.（）一个稀疏矩阵Am*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。（这一块缺少答案，就麻烦各位自己找一下了）U6-U101.（×）选择排序是一种稳定的排序方法。2.（√）一个有向无环图拓扑排序可能不唯一。3.（×）一棵二叉排序树的先序序列一定是有序序列。4.（×）在n个结点的无向图中，若边数大于n-1，则该图必是连通图。5.（×）完全二叉树中一定不存在度为1的结点。6.（√）有向图中第i个顶点的出度等于其邻接矩阵中第i行非0元素的个数。7.（√）简单选择排序的比较次数与待排序列的初始排序顺序无关。8.（√）二叉排序树的中序序列一定是一个有序序列。9.（×）快速排序是稳定排序。10.（×）当初始待排关键字排列为正序时，简单选择排序的比较次数达到最少。11.（√）当初始待排关键字排列为正序时，直接插入排序的比较次数达到最少。12.（×）二叉树只能用链式结构存储，无法用顺序存储结构存储。13.（√）B-树中的所有叶子结点均在同一层上。14.（×）一棵9阶B-树中的所有非终端结点的分支数一定大于4。15.（√）所谓动态查找是指查找表在查找后可能会发生变化。16.（√）平衡二叉树是指二叉树根结点的左子树深度和右子树深度之差的绝对值不大于1.17.（×）在二叉排序树中删除结点时，只能删除树中的叶子结点。18.（√）完全二叉树一定是一棵平衡二叉树。19.（×）具有n个顶点和至少n-1条边无向图一定是一个连通图。20.（×）用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。选择题：U1-U31.一个算法应该是（B）。A.程序B.问题求解步骤的描述C.要满足五个基本特性D.A和C2.以下数据结构中，（A）是非线性数据结构A.树B.字符串C.队列D.栈3.下面关于线性表的描述中，错误的是（B）？A.线性表采用顺序存储，必须占用一片连续的存储单元。B.线性表采用顺序存储，便于进行插入和删除操作。C.线性表采用链接存储，不必占用一片连续的存储单元。D.线性表采用链接存储，便于插入和删除操作。4.在一个长度为n的顺序表中，在第i（0i=n+1）个元素之前插入一个元素时，需向后移动（B）个元素。A.n-iB.n-i+1C.n-i-1D.i5.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A）存储方式最节省时间。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表6.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（D）最节省时间。A.单链表B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表7.链表不具有的特点是（B）A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比8.线性表（a1，a2，...，an）以链接方式存储时，访问第i位置元素的时间复杂性为（C）A.O（i）B.O（1）C.O（n）D.O(i-1)9.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（C）（1=i=n+1）。A.O（i）B.O（1）C.O（n）D.O(n2)10.在一个单循环链表（长度为n）中，已知p指针指向链表中一个非空结点，先要删除链表中p指针所指结点，其时间复杂度为（A）。A.O（n）B.O（1）C.O（n2）D.不确定11.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（C）A.O（n）O（n）B.O（n）O（1）C.O（1）O（n）D.O（1）O（1）12.非空的循环链表head的尾结点p满足（A）A.p-next=headB.p-next=NULLC.p=NULLD.p=head13.带头结点的循环链表L为空的条件是（C）A.L==NULLB.L-next==NULLC.L-next==LD.L-next==L-next14.在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（B）A.p-next=s；s-next=p-next；B.s-next=p-next；p-next=s；C.p-next=s；p-next=s-next；D.p-next=s-next；p-next=s；15.在双向链表指针p的结点前插入一个指针q的结点操作是（C）A.p-Llink=q；q-Rlink=p；p-Llink-Rlink=q；q-Llink=q；B.p-Llink=q；p-Llink-Rlink=q；q-Rlink=p；q-Llink=p-Llink；C.q-Rlink=p；q-Llink=p-Llink；p-Llink-Rlink=q；p-Llink=q；D.q-Llink=p-Llink；q-Llink=q；p-Llink=q；p-Llink=q；16.若已知一个栈的入栈序列是1,2,3，....，n，其输出序列为p1，p2，p3，....，pN，若pN是n，则pi是（D）A.iB.n-iC.n-i+1D.不确定17.一个栈的输入序列为1,2,3，....，n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（B）A.不确定B.n-i+1C.iD.n-i18.有六个元素6,5,4,3,2,1的顺序进栈，问下列哪一个不是合法出栈序列？（C）A.543612B.453126C.346521D.23415619.设栈的输入序列是1,2,3,4，则（D）不可能使其出栈序列。A.1,2,4,3B.2,1,3,4C.4,3,1,2D.3,2,1,420.栈和队列的共同点是（C）A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点21.假设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为（C）A.（rear-front+m）%mB.rear-front+1C.（front-rear+m）%mD.（rear-front）%m22.设循环队列存储空间的下标范围是0...n-1，当队列尾指针为rear（初始时rear=0），队列长度为len时，循环队列中队头元素所在位置为（D）A.rear-lenB.rear-len+1C.(rear-len+1)%nD.(rear-len+n)%n23.循环队列存储在数组A[0...m]中，则入队时的操作为（D）A.rear=rear+1B.rear=（rear+1）mod（m-1）C.rear=（rear+1）modmD.rear=（rear+1）mod（m+1）24.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（B）A.(rear+1)MODn=frontB.rear=frontC.rear+1=frontD.(rear-1)MODn=front25.执行完下列语句段后，i值为：（B）Intf（intx）{inty；y=((x0)?x*f(x-1):2);printf(“%d”,y);returny;}Inti;I=f(f(1));A.2B.4C.8D.无限递归U4-U51.下面关于串的叙述中，哪一个是不正确的？（B）A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要资源D.串既可以采用顺序存储，也可以采用链式存储2.设有两个串p和q的子串，求q在p中首先出现的位置的算法称为（C）A.求子串B.联接C.匹配D.求串长3.已知串S=‘aaab’，其Next数组值为（A）A.0123B.1123C.1231D.12114.串‘ababaaababaa’的next数组为（C）A.012345678999B.012121111212C.011234223456D.01230123223455.串的长度是指（B）A.串中所含不同字母的个数B.串中所含字符的个数C.传中所含不同字符的个数D.串中所含非空格字符的个数6字符串‘ababaabab’的nextval为（A）A.（0,1,0,1,0,4,1,0,1）B.（0,1,0,1,0,2,1,0,1）C.（0,1,0,1,0,0,0,1,1）D.（0,1,0,1,0,1,0,1,1）7.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（B）A.13B.33C.18D.408.假设以行序为主序存储二维数组A=array[1...100,1...100]，设每个数据元素占两个存储单元，基地址为10，则LOC[5,5]=（B）A.808B.818C.1010D.1020U6-U101.下列排序方法中，不稳定的排序算法是（C）A.冒泡排序B.归并排序C.快速排序D.直接插入排序2.具有n个顶点的无向图用邻接矩阵表示，若该图为连通图，则其邻接矩阵中至少有（A）个非零元素。A.2(n-1)B.n-1C.n*nD.n(n-1)3.要连通具有n个顶点的有向图，至少需要（B）条边A.n-1B.nC.n+1D.2n4.快速排序在最坏情况下的时间复杂度为（C）A.O(1)B.O(n)C.O(nlog