北外《数据结构》知识要点0223672

“数据结构”知识要点02试卷课程编号：BWCST2013学习中心： 学籍号： 姓名： 注意事项：1、本试卷满分100分，考试时间120分钟；2、考试形式：闭卷考试。一、单选题（每题3分，共45分）.算法是（）。A、计算机代码 B、解决问题的计算方法C、查找算法 D、解决问题的有限运算序列.抽象数据类型的三个组成部分分别为（）。A、数据对象、数据关系和数据操作 B、数据元素、逻辑结构和存储结构C、数据项、数据元素和数据类型 D、数据元素、逻辑结构和数据类型.线性表L=（a1,a2,……,an），下列说法正确的是（ ）。A、每个元素都有一个直接前驱和一个直接后继B、线性表中不可以为空C、表中诸元素的排列顺序必须是由小到大或由大到小D、除第一个和最后一个元素外，其余每个元素都由一个且仅有一个直接前驱和直接后继.在等概率的条件下，采用顺序查找的方法查找长度为n的线性表时，查找成功的平均查找长度为（）。A、n B、n+1 C、（n+1）/2 D、（n-1）/2.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。A、必须是连续的 B、部分地址必须是连续的C、一定是不连续的D、连续或不连续都可以.任何一个无向连通图的最小生成树中( )。A、只有一棵 B、有一棵或多棵C、一定有多棵 D、可能不存在.在无向图中，一个顶点的度是指图中( )。A、通过该顶点的简单路径数 B、与该顶点相相邻的顶点数C、通过该顶点的回路数 D、与该顶点连通的顶点数.程序段k=i=0；do{i=i+1；k=k+i；}while(i<=n)；的时间复杂度为( )。A、O(n) B、O(nlog2n) C、O(n2) D、O(n3/2).在一个单链表中，已知q结点，若在q后插入一个结点s，则执行( )。A、q=s; B、q=s->next; C、q->next=s; D、q->next=s->next;.在具有n个结点的顺序表上查找值为X的元素时，其时间复杂度为( )。A、O(n) B、O(1) C、O(n2) D、O(log2n).串s="abcdebda”，关于下面的说法，不正确的是( )。A、StrIndex(“abcdebda”,“bc”)=2B、StrLength(s)=8C、StrASSign(SLS)，则Us1=abcdebdaD、StrASSign(S,s1),则Us1=abcdebda.关于循环队列的说法，不正确的是()。人、入队时的队尾指针加1操作改为：rear=(rear+1)%SiZeB、出队时队头指针加1操作改为：front=(front+1)%SiZeC、队满条件：front=rear%size口、队空条件：front=rear.一个顺序表的第一个元素的存储地址是90，每个元素的长度为4，则第6个元素的存储地址是()。A、102B、110C、112D、108.一组记录的的序列（46，79，56，38，40，84，90），则利用插入排序的方法将其从小到大，经过2轮排序，序列变为（ ）。A、46，79，40，38，56，84，90B、46，79，38，40，56，84，90C、46，56，79，38，40，84，90D、38，40，46，56，79，84，90.设栈S和队列q均为空，先将a,b,c,d,e前3个元素进队列q,后2个元素进栈，再将队列4中的元素顺次出队的元素进栈s,得到栈里的元素为（ ）。A、cbaed B、abcde C、abced D、acedb二、判断题（每题2.5分，共25分）.队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。.查找的方法可以分静态查找和动态查找。.线性结构中元素之间存在一对一关系,.树形结构中元素之间存在多对多关系,图形结构中元素之间存在一对一关系。.栈和队列都是特殊的线性表,栈的元素进出规则是先进先出。.队列的元素进出规则是先进后出。7,规模为n的序列，使用直接插入排序，则最好情况下的时间复杂度是O（n），最好情况下比较的次数是n-1。.在一棵具有5层的满二叉树中结点总数为30。.在二叉树的第i层上最多有i-1个节点。.若以邻接矩阵表示有向图，邻接矩阵上第j列中非零元素的个数即为顶点vj的入度。三、计算题（每题15分，共30分）1.（1）写出用冒泡排序将关键字序列｛54,23,89,48,64,50,25｝排序过程的第一趟结果。（8分）（2）写出用直接插入排序将关键字序列｛54,23,89,48,64,50,25｝排序过程的每一趟结果。（7分）2.（1）某不带权无向图如下所示，求该图的邻接矩阵；并求该图的广度优先遍历序列，以结点6开始。（7分）（2）已知有向图的邻接矩阵如下,请问该有向图有几个节点？怎么看出来的？画出该有向图。（8分）一0 1 0 0 0 1 「0 0 0 0 0 0 10 1 0 0 0 0 00 0 1 0 0 0 00 0 0 1 0 0 010001000011010“数据结构”知识要点02答案 -单选题（每题3分，共45分）1、D2、B3、D4、C5、D6、B7、B8、A9、C10、B11、D12、C13、B14、C15、A二、判断题（每题2.5分，共25分）1、T2、T3、T4、F5、F6、F7、F8、F9、F10、T三、计算题（每题15分，共30分）1、答:（1）冒泡排序的第一趟结果：（8分）（）（54,23,89,48,64,50,25）（）（54,23,89,48,64,25,50）（）（54,23,89,48,25,64,50）（）（54,23,89,25,48,64,50）（）（54,23,25,89,48,64,50）（）（54,23,25,89,48,64,50）（23）（54,25,89,48,64,50）（2）直接插入排序：（7分）第一趟:[54],23,89,48,64,50,25第二趟:[23，54],89,48,64,50,25第三趟:[23，54，89],48,64,50,25第四趟:[23，48,54，89],64,50,25第五趟:[23，48,54，64，89],50,25第六趟:[23，48,50，54，64，89],25第七趟:[23，25，48,50，54，64，89]2、答：（1）该图的邻接矩阵是：01100000100001001000011100100111010000110111