数据结构B卷及答案.doc

题号 一 二 三 四 五 总分 复查人 得分 一、单项选择题(本大题共15 题，每小题2分，共30分)在每小题列出的四个选项中只有一个选项是正确的，请将正确答案填在括号内。 1． 若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。A、单链表 B、双链表 C、单向循环 D、顺序表 2． 串是任意有限个（ ） A、符号构成的序列 B、符号构成的集合 C、字符构成的序列 D、字符构成的集合 3． 设矩阵A（aij ，l≤i,j≤ 10）的元素满足： aij≠0(i≥j, l≤i, j≤ 10) aij=0 (ij, l≤i, j≤ 10) 现将A的所有非0元素以行序为主序存放在首地址为2000的存储区域中，每个元素占有4个单元，则元素A[9][5]的首址为A、2340 B、2336 C、2164 D、2160 4． 如果以链表作为栈的存储结构，则退栈操作时（ ） A、 必须判别栈是否满 B、 对栈不作任何判别 C、 必须判别栈是否空 D、 判别栈元素的类型 5． 设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为（ ） A、front=front+1 B、front=(front+1)% m C、rear=(rear+1)%m D、front=(front+1)%(m+1) 6． 深度为6（根的层次为1）的二叉树至多有（ ）结点。 A、 64 B、32 C、31 D、63 7． 将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。编号为49的结点X的双亲编号为（ ） A、24 B、25 C、23 D、无法确定 8． 设有一个无向图G=（V，E）和G’=（V’，E’）如果G’为G的生成树，则下面不正确的说法是（ ） A、G’为G 的子图 B、G’为G 的边通分量 C、G’为G的极小连通子图且V’=V D、G’为G的一个无环子图 9． 用线性探测法查找闭散列表，可能要探测多个散列地址，这些位置上的键值（ ） A、 一定都是同义词 B、一定都不是同义词 C、都相同 D、不一定都是同义词 10． 二分查找要求被查找的表是（ ） A、 键值有序的链接表 B、链接表但键值不一定有序 C、 键值有序的顺序表 D、顺序表但键值不一定有序 11． 当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数为（ ） A、n2 B、nlog2n C、log2n D、n-1 12． 堆是一个键值序列{k1,k2,…, kn},对i=1,2,…,|_n/2_|,满足( ) A、ki≤k2i≤k2i+1 B、kik2i+1k2i C、ki≤k2i且ki≤k2i+1(2i+1≤n) D、ki≤k2i 或ki≤k2i+1(2i+1≤n) 13．一个具有n个顶点的无向完全图的边数为（　 ） A、n(n+1)/2 B、n(n-1)/2 C、n(n-1) D、n(n+1) 14．在索引顺序表中查找一个元素，可用的且最快的方法是（　 ） A、用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找 B、用顺序查找法确定元素所在块，再用二分查找法在相应块中查找 C、用二分查找法确定元素所在块，再用顺序查找法在相应块中查找 D、用二分查找法确定元素所在块，再用二分查找法在相应块中查找 15．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用（ 　）存储方式最节省运算时间。 A、 单链表　 B、双链表　 C、带头结点的双循环链表　D、容量足够大的顺序表 1．双链表中至多只有一个结点的后继指针为空。（ ） 2．在循环队列中，front指向队列中第一个元素的前一位置，rear指向实际的队尾元素，队列为满的条件是front=rear。（ ） 3．对链表进行插入和删除操作时，不必移动结点。（ ） 4．栈可以作为实现程序设计语言过程调用时的一种数据结构。（ ） 5．在一个有向图的拓朴序列中，若顶点a在顶点b之前，则图中必有一条弧a,b。( ) 6．对有向图G，如果从任一顶点出发进行一次深度优先或广度优先有哪些信誉好的足球投注网站就能访问每个顶点，则该图一定是完全图。( ) 7．“顺序查找法”是指在顺序表上进行查找的方法。（ ） 8．向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。（） 9．键值序列{A，C，D，E，F，E，F}是一个堆。10．二路归并时，被归并的两个子序列中的关键字个数一定要相等。（） 1．在带有头结点的单链表L中，若要删除第一个结点，则需执行下列三条语句：＿＿＿＿＿＿＿＿；L-next=U-next；free(U)； 2．有一个长度为20的有序表