山东科大数据结构（C）期末复习题及参考答案

数据结构（C）复习思考题一一、单选题（每题2分，共20分）1、

栈和队列的共同特点是（A）。A、只允许在端点处插入和删除元素B、都是先进后出C、都是先进先出D、没有共同点2、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储(C)。A、数据的处理方法B、数据元素的类型C、数据元素之间的关系D、数据的存储方法3、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（B）等5个特性。A、可执行性、可移植性和可扩充性 B、可执行性、有穷性和确定性 C、确定性、有穷性和稳定性 D、易读性、稳定性和确定性4、设完全无向图中有n个顶点，则该完全无向图中有（A）条边。A、n(n-1)/2 B、n(n-1) C、n(n+1)/2 D、(n-1)/25、用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则所采用的排序方法是（D）。A、选择排序B、希尔排序C、归并排序D、快速排序6、设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（A）。 A、BADC B、BCDA C、CDAB D、CBDA7、设某棵二叉树中有2000个结点，则该二叉树的最小高度为（C）。 A、9 B、10 C、11 D、128、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（C）。A、O(0)B、O(1)C、O(n)D、O(n2)9、一个队列的入队序列是1，2，3，4，则队列的输出序列是（B）。A、4，3，2，1B、1，2，3，4C、1，4，3，2D、3，2，4，110、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（D）操作。A、h->next=s

;B、s->next=h

;C、s->next=h

;h=s

;D、s->next=h->next

;h->next=s

;二、填空题（每空2分，共20分）1、数据结构被形式地定义为（D,R），其中D是数据元素的有限集合，R是D上的关系有限集合。2、数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。3、在顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。4、队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。5、在具有n个单元的循环队列中，队满时共有n-1个元素。6、快速排序算法的平均时间复杂度为O(nlog2n)，直接插入排序算法的平均时间复杂度为O(n2)。三、判断题。（每题1分，共10分）1、在决定选取何种存储结构时，一般不考虑各结点的值如何。（√）2、抽象数据类型（ADT）包括定义和实现两方面，其中定义是独立于实现的，定义仅给出一个ADT的逻辑特性，不必考虑如何在计算机中实现。（√）3、一个广义表的表头总是一个广义表。（×）4、强连通图的各顶点间均可达。（√）5、对于任意一个图，从它的某个结点进行一次深度或广度优先遍历可以访问到该图的每个顶点。（×）6、对线性表进行折半查找时，要求线性表必须以链式方式存储，且结点按关键字有序排列。（×）7、散列法存储的思想是由关键字值决定数据的存储地址。（√）8、直接选择排序算法在最好情况下的时间复杂度为O（n）。（×）9、不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（√）10、当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（√）四、简答题（每题10分，共20分）1、说明线性表、栈与队的异同点。答：相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。不同点：（1）运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。（2）用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指令寄存及其他运算等等。2、试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。答：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。五、算法设计题（每题15分，共30分）1、设有一组初始记录关键字序列（K1，K2，…，Kn），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。答：

voidquickpass(intr[],ints,intt){inti=s,j=t,x=r[s];while(i<j){while(i<j&&r[j]>x)j=j-1;if(i<j){r[i]=r[j];i=i+1;}while(i<j&&r[i]<x)i=i+1;if(i<j){r[j]=r[i];j=j-1;}}r[i]=x;}2、阅读下列函数arrange()intarrange(inta[],int1,inth,intx){//1和h分别为数据区的下界和上界inti,j,t；i=1；j=h；while(i<j){while(i<j&&a[j]>=x)j--；while(i<j&&a[j]>=x)i++；if(i<j){t=a[j]；a[j]=a[i]；a[i]=t；}}if(a[i]<x)returni；elsereturni－1；}（1）写出该函数的功能；（2）写一个调用上述函数实现下列功能的算法：对一整型数组b[n]中的元素进行重新排列，将所有负数均调整到数组的低下标端，将所有正数均调整到数组的高下标端，若有零值，则置于两者之间，并返回数组中零元素的个数。答：（1）该函数的功能是：调整整数数组a[]中的元素并返回分界值i，使所有＜x的元素均落在a[1、、i]上，使所有≥x的元素均落在a[i＋1、、h]上。（2）intf(intb[],intn)或intf(intb[],intn){{intp,q；intp,q；p=arrange(b,0,n－1,0)；p=arrange(b,0,n－1,1)；q=arrange(b,p+1,n－1,1)；q=arrange(b,0,p,0)；returnq－p；returnp－q；}}

数据结构（C）复习思考题二及答案一、单选题（每题2分，共20分）1、数据结构在计算机内存中的表示是指(A)。A、数据的存储结构B、数据结构C、数据的逻辑结构D、数据元素之间的关系2、在以下的叙述中，正确的是(B)。A、线性表的顺序存储结构优于链表存储结构B、二维数组是其数据元素为线性表的线性表C、栈的操作方式是先进先出D、队列的操作方式是先进后出3、下面关于线性表的叙述中，错误的是（B）。A、线性表采用顺序存储，必须占用一片连续的存储单元B、线性表采用顺序存储，便于进行插入和删除操作。C、线性表采用链式存储，不必占用一片连续的存储单元D、线性表采用链式存储，便于进行插入和删除操作。4、数组A[0…4，-1…-3，5…7]中含有的元素个数是（A）。A、55B、45C、36D、165、栈的插入和删除操作在（A）进行。A、栈顶B、栈底C、任意位置D、指定位置6、在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行（D）。A、s→link=p→link;p→link=s;B、p→link=s;s→link=q;C、p→link=s→link;s→link=p;D、q→link=s;s→link=p;7、以下哪种组织结构适于对动态查找表进行高效率查找（C）。A、有序表B、分块有序表C、三叉排序树D、线性链表8、根据二叉树的定义可知二叉树共有（B）种不同的形态。 A、4 B、5 C、6 D、79、设有两个串S1和S2，求串S2在S1中首次出现位置的运算称作（C）。A、连接 B、求子串 C、模式匹配 D、判断子串10、稀疏矩阵的常见压缩存储方法有（C）两种。A、二维数组和三维数组 B、三元组和散列表 C、三元组和十字链表 D、散列表和十字链表二、填空题（每空2分，共20分）1、线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。2、一个算法的效率可分为时间效率和空间效率。3、设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第6次匹配成功。4、三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的行下标、列下标和元素值。5、在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑应最好选择快速排序，如果从节省存储空间的角度来考虑则最好选择堆排序。三、判断题。（每题1分，共10分）1、抽象数据类型与计算机内部表示和实现无关。（√）2、顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。（×）3、线性表中每个元素都有一个直接前驱和一个直接后继。（×）4、线性表就是顺序存储的表。（×）5、循环链表不是线性表。（×）6、数组元素的下标值越大，存取时间越长。（×）7、用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。（√）8、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（×）9、冒泡排序算法关键字比较的次数与记录的初始排列次序无关。（×）10、二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。（×）四、简答题（每题10分，共20分）1、设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。答：至少有14种。（1）全进之后再出情况，只有1种：4，3，2，1（2）进3个之后再出的情况，有3种，3,4,2,13,2,4,13,2,1,4（3）进2个之后再出的情况，有5种，2,4,3,12,3,4,12,1,3,42,1,4,32,1,3,4（4）进1个之后再出的情况，有5种，1,4,3,21,3,2,41,3,4,21,2,3,41,2,4,32、简述线性结构与非线性结构的不同点。答：线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是多对多的。五、算法设计题（每题15分，共30分）1、请设计一个判断单链表中结点是否关于中心对称的算法。答：typedefstruct{ints[100];inttop;}sqstack;intlklistsymmetry(lklist*head){sqstackstack;stack、top=-1;lklist*p;for(p=head;p!=0;p=p->next){stack、top++;stack、s[stack、top]=p->data;}for(p=head;p!=0;p=p->next)if(p->data==stack、s[stack、top])stack、top=stack、top-1;elsereturn(0);return(1);}2、设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。答:typedefchardatatype;typedefstructnode{datatypedata;structnode*next;}lklist;voidsplit(lklist*head,lklist*&ha,lklist*&hb,lklist*&hc){lklist*p;ha=0,hb=0,hc=0;for(p=head;p!=0;p=head){head=p->next;p->next=0;if(p->data>='A'&&p->data<='Z'){p->next=ha;ha=p;}elseif(p->data>='0'&&p->data<='9'){p->next=hb;hb=p;}else{p->next=hc;hc=p;}}}

数据结构（C）复习思考题三及答案一、单选题（每题2分，共20分）1、研究数据结构就是研究（D）。A、数据的逻辑结构B、数据的存储结构C、数据的逻辑结构和存储结构D、数据的逻辑结构、存储结构及其基本操作2、线性表采用链式存储时，结点的存储地址（B）。A、必须是不连续的B、连续与否均可C、必须是连续的D、和头结点的存储地址相连续3、算法指的是（D）。A、计算机程序B、解决问题的计算方法C、排序算法D、解决问题的有限运算序列4、用链接方式存储的队列，在进行插入运算时（D）。A、仅修改头指针B、头、尾指针都要修改C、仅修改尾指针D、头、尾指针可能都要修改5、以下数据结构中哪一个是非线性结构？（D）A、队列B、栈C、线性表D、二叉树6、在具有n个结点的单链表上查找值为x的元素时，其时间复杂度为（A）。A、O(n) B、O(1) C、O(n2) D、O(n-1)7、在长度为n的顺序表的第i个位置上插入一个元素（1≤i≤n+1），元素的移动次数为：(A)。A、n–i+1B、n–iC、iD、i–18、下述哪一条是顺序存储结构的优点？（C）。A、插入运算方便B、可方便地用于各种逻辑结构的存储表示C、存储密度大D、删除运算方便9、二叉树的深度为k，则二叉树最多有（C）个结点。A、2k B、2k-1 C、2k-1 D、2k-110、字符串的长度是指（C）。 A、串中不同字符的个数 B、串中不同字母的个数 C、串中所含字符的个数 D、串中不同数字的个数二、填空题（每空2分，共20分）1、设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2,e4,e3,e6,e5,e1，则栈的容量至少应该是3。2、n个顶点的连通图至少有n-1条边。3、数据的物理结构主要包括__顺序存储结构__和__链式存储结构__两种情况。4、设一棵完全二叉树中有500个结点，则该二叉树的深度为___9___；若用二叉链表作为该完全二叉树的存储结构，则共有___501_____个空指针域。5、通常从四个方面评价算法的质量：时间正确性、占用内存易读性、复杂度强壮性和准确度高效率。6、设完全有向图中有n个顶点，则该完全有向图中共有n(n-1)条有向条；设完全无向图中有n个顶点，则该完全无向图中共有n(n-1)/2条无向边。三、判断题。（每题1分，共10分）1、线性表采用链式存储结构时，结点和结点内部的存储空间可以是不连续的。（×）2、对任何数据结构链式存储结构一定优于顺序存储结构。（×）3、在单链表中，给定任一结点的地址p，则可用下述语句将新结点s插入结点p的后面：p－＞next；（×）4、队列是一种插入和删除操作分别在表的两端进行的线性表，是一种先进后出的结构。（×）5、二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。（√）6、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（×）7、在哈夫曼树中，权值最小的结点离根结点最近。（×）8、在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次序仍然保持不变，称这种排序为稳定排序。（√）9、完全二叉树中的叶子结点只可能在最后两层中出现。（√）10、哈夫曼树中没有度数为1的结点。（√）四、简答题（每题10分，共20分）1、数据结构和数据类型两个概念之间有区别吗？答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。2、设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有（1）front=11，rear=19；（2）front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？答：用队列长度计算公式：(N＋r－f)%N（1）L=（40＋19－11）%40=8（2）L=（40＋11－19）%40=32五、算法设计题（每题15分，共30分）1、请设计判断一棵二叉树是否是二叉排序树的算法。答：intminnum=-32768,flag=1;typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidinorder(bitree*bt){if(bt!=0){inorder(bt->lchild);if(minnum>bt->key)flag=0;minnum=bt->key;inorder(bt->rchild);}}2、请设计一个判断两个二叉树是否相同的算法。答：typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;intjudgebitree(bitree*bt1,bitree*bt2){if(bt1==0&&bt2==0)return(1);elseif(bt1==0||bt2==0||bt1->data!=bt2->data)return(0);elsereturn(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild));}

数据结构（C）复习思考题四及答案一、单选题（每题2分，共20分）1、在数据结构中，从逻辑上可以把数据结构分为（C）。A、动态结构和静态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构2、链表不具备的特点是(A)。A、可随机访问任一结点B、插入删除不需要移动元素C、不必事先估计存储空间D、所需空间与其长度成正比3、树最适合用来表示（C）。A、有序数据元素B、无序数据元素C、元素之间具有分支层次关系的数据D、元素之间无联系的数据4、任何一棵二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序（A）。A、不发生改变B、发生改变C、不能确定D、以上都不对5、在一棵度为3的树中,度为3的结点个数为2,度为2的结点个数为1,则度为0的结点个数为（C）。A、4B、5C、6D、76、循环链表的主要优点是（D）。A、不再需要头指针B、已知某结点位置后能容易找到其直接前驱C、在进行插入、删除运算时能保证链表不断开

D、在表中任一结点出发都能扫描整个链表7、对n个记录的文件进行快速排序，所需要的辅助存储空间大致为（C）。A、O（1）B、O（n）C、O（1og2n）D、O（n2）8、设有6个结点的无向图，该图至少应有（A）条边才能确保是一个连通图A、5B、6C、7D、89、与单链表相比，双链表的优点之一是(D)。A、插入、删除操作更简单B、可以进行随机访问C、可以省略表头指针或表尾指针D、顺序访问相邻结点更灵活10、若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0，3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（B）。A、1和5 B、2和4 C、4和2 D、5和1二、填空题（每空2分，共20分）1、栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。2、由3个结点所构成的二叉树有5种形态。3、设有一稀疏图G，则G采用邻接表存储较省空间。4、设指针p指向单链表中结点A，指针s指向被插入的结点X，则在结点A的前面插入结点X时的操作序列为：1)s->next=p->next；2)p->next=s；3)t=p->data；4)p->data=s->data；5)s->data=t；5、下面程序段的时间复杂度是O(n*m)。for(i=0;i<n;i++) for(j=0;j<m;j++) A[i][j]＝0;6、一棵有n个叶子结点的哈夫曼树共有2n－1个结点。7、当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是___top==0___。8、向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1个元素。三、判断题。（每题1分，共10分）1、集合与线性表的区别在于是否按关键字排序。（×）2、空串和空白串是相同的。（×）3、二叉树的后序遍历序列中，任意一个结点均处在其孩子结点的后面。（√）4、度为2的有序树是二叉树。（×）5、在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1。（√）6、拓扑排序是按AOE网中每个结点事件的最早发生时间对结点进行排序。（×）7、对连通图进行深度优先遍历可以访问到该图中的所有顶点。（√）8、先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（√）9、一个广义表的表尾总是一个广义表。（√）10、若已知一棵二叉树的前序遍历序列和后序遍历序列，则可以恢复该二叉树。（×）四、简答题（每题10分，共20分）1、描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点）。在单链表中设置头结点的作用是什么？答：首元结点是指链表中存储线性表中第一个数据元素a1的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。否则表示空表的链表的头指针为空。这三个概念对单链表、双向链表和循环链表均适用。是否设置头结点，是不同的存储结构表示同一逻辑结构的问题。头结点headdatalink头指针首元结点简而言之，头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息；首元素结点是指链表中存储线性表中第一个数据元素a1的结点。2、找出所有满足下列条件的二叉树：(1)它们在先序遍历和中序遍历时，得到的节点访问序列相同；(2)它们在后序遍历和中序遍历时，得到的结点访问序列相同；(3)它们在先序遍历和后序遍历时，得到的节点访问序列相同。答：(1)不含左子树的二叉树。 (2)不含右子树的二叉树。 (3)即不含左子树，也不含右子树的二叉树。 五、算法设计题（每题15分，共30分）1、请设计一个在单链表中删除值相同的多余结点的算法。答：typedefintdatatype;typedefstructnode{datatypedata;structnode*next;}lklist;voiddelredundant(lklist*&head){lklist*p,*q,*s;for(p=head;p!=0;p=p->next){for(q=p->next,s=q;q!=0;)if(q->data==p->data){s->next=q->next;free(q);q=s->next;}else{s=q,q=q->next;}}}2、设关键字序列(k1，k2，…，kn-1)是堆，请设计一个算法，将关键字序列(k1，k2，…，kn-1，x)调整为堆。答：voidadjustheap(intr[],intn){intj=n,i=j/2,temp=r[j-1];while(i>=1)if(temp>=r[i-1])break;else{r[j-1]=r[i-1];j=i;i=i/2;}r[j-1]=temp;}

数据结构（C）复习思考题一一、单选题（每题2分，共20分）1、树最适合用来表示（C）。A、有序数据元素B、无序数据元素C、元素之间具有分支层次关系的数据D、元素之间无联系的数据2、二叉树的第k层的结点数最多为（D）。A、2k-1B、2K+1C、2K-1D、2k-13、由两个栈共享一个向量空间的好处是：（B）。A、减少存取时间，降低下溢发生的机率B、节省存储空间，降低上溢发生的机率C、减少存取时间，降低上溢发生的机率D、节省存储空间，降低下溢发生的机率4、以下说法中正确的是（A）。A、串是一种特殊的线性表B、串的长度必须大于零C、串中元素只能是字母D、空串就是空白串5、一个非空广义表的表头（D）。A、不可能是子表B、只能是子表C、只能是原子D、可以是子表或原子6、假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是（C）。A、O(n)B、O(e)C、O(n+e)D、O(n*e)7、设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（A）。 A、p->next=p->next->next B、p=p->next C、p=p->next->next D、p->next=p8、设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（C）。 A、2，3，5，8，6 B、3，2，5，8，6 C、3，2，5，6，8 D、2，3，6，5，89、一个队列的入队序列是1，2，3，4，则队列的出队序列是（B）。 A、1，2，3，4 B、4，3，2，1 C、1，4，3，2 D、3，4，1，210、队列是一种（A）的线性表。 A、先进先出 B、先进后出 C、只能插入 D、只能删除二、填空题（每空2分，共20分）1、设输入序列为1、2、3，则经过栈的作用后可以得到___5___种不同的输出序列。2、设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d，则e和d的关系为__e=d___。3、数据结构从逻辑上划分为三种基本类型：线性结构、树型结构和图型结构。4、设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的前序遍历序列为ABDECF，中序遍历序列为DBEAFC，后序遍历序列为DEBFCA。5、深度为k的完全二叉树中最少有2k-1个结点。6、下面程序段的时间复杂度是O(n2)。 s=0;for(I=0;i<n;i++) for(j=0;j<n;j++) s+=B[i][j];sum=s;三、判断题。（每题1分，共10分）1、顺序存储方式只能用于存储线性结构。（×）2、取线性表的第i个元素的时间同i的大小有关。（×）3、链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序表中效率高。（√）4、双向链表可随机访问任一结点。（×）5、串是一种特殊的线性表，其特殊性体现在可以顺序存储。（×）6、长度为1的串等价于一个字符型常量。（×）7、广义表（（（a），b），