西交《数据结构》在线作业答卷

西交《数据结构》在线作业-00002试卷总分:100得分:100一、单选题(共30道试题,共60分)用链表表示线性表的优点是（）便于随机存取花费的存储空间比顺序表少便于插入与删除数据元素的物理顺序与逻辑顺序相同答案:C2.设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（）front=front+1front=(front+1)%(m-1)front=(front-1)%mfront=(front+1)%m答案:D3.如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用（）查找方法。分块顺序二分散列答案:A4.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。2m-12m2m+14m答案:B5.求字符串T在字符串S中首次出现的位置的操作称为()。串的模式匹配求子串求串的长度串的连接答案:A6.哈希表的平均查找长度是()的函数。哈希表的长度表中元素的多少哈希函数哈希表的装满程度答案:D7.设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（）R-FF-R(R-F+M)％M(F-R+M)％M答案:C8.设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（）。head==0head->next==0head->next==headhead!=0答案:A9.设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（）。ne2n2e答案:D10.设某完全无向图中有n个顶点，则该完全无向图中有（）条边。n(n-1)/2n(n-1)nn-1答案:A11.一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，（）次比较后查找成功。2345答案:C12.顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（）。O(n)O(n^2)O(n^3)O(1og2n)答案:A13.执行一趟快速排序能够得到的序列是（）。[41，12，34，45，27]55[72，63][45，34，12，41]55[72，63，27][63，12，34，45，27]55[41，72][12，27，45，41]55[34，63，72答案:A14.若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（）排序为宜。直接插入直接选择堆快速答案:A15.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。不确定n-i+1in-i答案:B16.设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（）。空或只有一个结点高度等于其结点数任一结点无左孩子任一结点无右孩子答案:D17.一个具有n个顶点的无向图最多有()条边。n×(n-1)/2n×(n-1)n×(n+1)/2n2答案:A18.设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）BADCBCDACDABCBDA答案:A19.设一组初始记录关键字的长度为8，则最多经过（）趟插入排序可以得到有序序列。6789答案:B20.存放循环队列元素的数组data有10个元素，则data数组的下标范围是（）。0～100～91～91～10答案:B21.空串与空格字符组成的串的区别是（）。没有区别；两串的长度不等；两串的长度相等；两串包含的字符不相同。答案:B22.在二叉排序树中插入一个结点的时间复杂度为（）。O(1)O(n)O(log2n)O(n)答案:B23.在序列（2，5，8，11，15，16，22，24，27，35，50）中采用折半查找（二分查找）方法查找元素24，需要进行（）次元素之间的比较。34811答案:B24.设某棵三叉树中有40个结点，则该三叉树的最小高度为（）。3456答案:B25.由两个栈共享一个向量空间的好处是：（）减少存取时间，降低下溢发生的机率节省存储空间，降低上溢发生的机率减少存取时间，降低上溢发生的机率节省存储空间，降低下溢发生的机率答案:B26.时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（）。堆排序冒泡排序希尔排序快速排序答案:A27.设用链表作为栈的存储结构则退栈操作（）必须判别栈是否为满必须判别栈是否为空判别栈元素的类型对栈不作任何判别答案:B28.设顺序表的长度为n，则顺序查找的平均比较次数为（）。nn/2(n+1)/2(n-1)/2答案:C29.在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，打印机依次从该缓冲区中取出数据打印，则该缓冲区的结构应该是（）。线性表数组堆栈队列答案:D30.广度优先遍历类似于二叉树的（）。先序遍历中序遍历后序遍历层次遍历答案:D二、判断题(共20道试题,共40分)31.中序遍历一棵二叉排序树可以得到一个有序的序列。答案:正确32.子串“ABC”在主串“AABCABCD”中的位置为3。答案:错误33.分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。答案:正确34.为度量一个搜索算法的性能，需要在时间和空间方面进行权衡。答案:正确35.在B+树中查找和在B-树中查找的过程完全相同。()答案:错误36.栈的特点是“后进先出”。（）答案:正确37.不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O（n）。答案:正确38.设串S的长度为n,则S的子串个数为n(n+1)/2。答案:错误39.设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为O(log2n)。（）答案:正确40.由树转化成二叉树，该二叉树的右子树不一定为空。（）答案:错误41.磁带是顺序存取的外存储设备。答案:正确42.调用一次深度优先遍历可以访问到图中的所有顶点。答案:错误43.希尔排序算法的时间复杂度为O(n2)。答案:错误44.二维数组和多维数组均不是特殊的线性结构。答案:错误45.层次遍历初始堆可以得到一个有序的序列。答案:错误46.从