西北工业大学22春《数据结构》在线作业三及答案参考59.docx

西北工业大学22春《数据结构》作业三及答案参考1. 对某二叉树进行前序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果为( )A.DBFEACB.DFEBCAC.BDFECAD.BDEFAC参考答案：B2. 有向图用邻接矩阵表示后，顶点i的入度等于邻接矩阵中第i列的元素个数 )A、错误B、正确参考答案：B3. 中序遍历的递归算法平均空间复杂度为( )A.2(n)B.n(2)C.0(n)D.2n参考答案：C4. 一棵树可以只有1个结点 )A、错误B、正确参考答案：B5. 设根结点层次为1，某二叉树的结点前序序列和后序序列正好相反，则该二叉树一定是( )A.高度等于其结点数B.空或只有一个结点C.任一结点无左子女D.任一结点无右子女参考答案：A6. 邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它 )A.正确B.错误参考答案：B7. n个顶点的强连通图中至少含有( )A.n-1条有向边B.n条有向边C.n(n-1)/2条有向边D.n(n-1)条有向边参考答案：B8. 队列允许在队尾删除，在队头插入 )A.正确B.错误参考答案：A9. 结构的存储密度定义为数据本身所占的存储量与整个结构所占的存储量之比。

)A.正确B.错误参考答案：A10. AVL树是一种平衡的二叉排序树，树中任一结点的( )A.左、右子树的高度均相同B.左、右子树高度差的绝对值不超过1C.左子树的高度均大于右子树的高度D.左子树的高度均小于右子树的高度参考答案：B11. 线性表(a1，a2，...，an)以链式方式存储，访问第i位置元素的时间复杂度为( )A.O(0)B.O(1)C.O(n)D.O(n2)参考答案：C12. 在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是堆排序 )A、错误B、正确参考答案：A13. 下面程序段的时间复杂度是( )for(i=0; i＜n; i++) for(j=1; j＜m; j++) A[i][j]=0;A、O(n)B、O(m+n+1)C、O(m+n)D、O(m*n)参考答案：D14. 在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next=head，则( )A、p指向头结点B、p指向尾结点C、*p的直接后继是头结点D、*P的直接后继是尾结点参考答案：D15. 数据的不可分割的最小标识单位是( )A.数据项B.数据记录C.数据元素D.数据变量参考答案：A16. 设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为( )A.O(nlog2e)B.O(n+e)C.O(ne)D.O(n2)参考答案：B17. 字符串“sgabacbadfgbacst”中存在有6个与字符串“ba”相同的子串。

)A、错误B、正确参考答案：A18. 通常将链串的结点大小设置为大于1是为了( )A、提高串匹配效率B、提高存储密度C、便于插入操作D、便于删除操作参考答案：A19. 假设三维数组A[10][9][8]按行优先顺序存储，若每个元素占3个存储单元，且首地址为100，则元素A[9][8][7]的存储地址是501 )A、错误B、正确参考答案：A20. 某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为( )A.3B.2C.4D.5参考答案：C21. 已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为( )A.DEBAFCB.DEFBCAC.DEBCFAD.DEBFCA参考答案：B22. 下面关于串的叙述中，哪一个是不正确的?( )A.空串是由空格构成的串B.模式匹配是串的一种重要运算C.串是字符的有限序列D.串既可以采用顺序存储，也可以采用链式存储参考答案：A23. 向一个有127个元素原顺序表中插入一个新元素并保存原来顺序不变，平均要移动( )个元素A.8B.63.5C.63D.7参考答案：B24. 在链队列中，假设f和r分别为队首和队尾指针，则删除一个结点的操作是( )。

A.r=r->nextB.r=f->nextC.f=r->nextD.f=f->next参考答案：D25. 可以用队列实现数值转换算法 )A.正确B.错误参考答案：A26. 数据的逻辑结构是指数据的各数据项之间的逻辑关系 )A.正确B.错误参考答案：B27. 深度为h的满m叉树的第k层的结点(1=A.mk-1B.mk-1C.mh-1D.mh-1参考答案：A28. 设有100个数据元素，采用折半搜索时，最大比较次数为( )A.6B.7C.8D.10参考答案：B29. 向二叉搜索树中插入一个元素时，其时间复杂度大致为( )A.O(log2n)B.O(n)C.O(1)D.O(2n)参考答案：A30. 线性表的链接实现有利于( )运算A.插入B.读表元C.查找D.定位参考答案：A31. 在有向图中，以顶点v为终点的边的数目称为v的入度 )A、错误B、正确参考答案：B32. 在一个图中所有顶点的度数之和等于所有边数的( )倍A.1/2B.2C.1D.4参考答案：B33. 一个有向无环图的拓扑排序序列是( )A.一定唯一的B.一定不唯一的C.不一定唯一的D.都不对参考答案：C34. 在单链表中设置头结点的作用是( )。

A.主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断另外，不论链表是否为空，链表指针不变B.便于查找C.便于连接D.快速插入记录参考答案：A35. 在二叉树的第i层上至多可以有2i个结点 )A、错误B、正确参考答案：A36. 算法分析的目的是( )A、辨别数据结构的合理性B、评价算法的效率C、研究算法中输入与输出的关系D、鉴别算法的可读性参考答案：B37. 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树 )A.正确B.错误参考答案：A38. 下列陈述中正确的是( )A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树中必有度为2的结点D.二叉树中最多只有两棵子树，并且有左右之分参考答案：D39. 线性表的链式存储结构是一种( )A.随机存取的存储结构B.顺序存取的存储结构C.索引存取的存储结构D.Hash存取的存储结构参考答案：A40. 在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为( )A、n-i+1B、n-iC、iD、i-1参考答案：A41. 数据的逻辑结构描述数据元素之间的逻辑关系，与存储方式无关。

)A、错误B、正确参考答案：B42. 深度为15的满二叉树上，第11层有2^11个结点 )A、错误B、正确参考答案：A43. 用链表表示线性表的优点是( )A.便于随机存取B.花费的存储空间比顺序表少C.便于插入与删除D.数据元素的物理顺序与逻辑顺序相同参考答案：C44. 在k叉树中，度为0的结点称为( )A.祖先B.根C.子孙D.叶参考答案：D45. 在数据结构中，数据的逻辑结构可以分成( )A、内部结构和外部结构B、线性结构和非线性结构C、紧凑结构和非紧揍结构D、动态结构和静态结构参考答案：C46. 如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为( )A.插入排序B.归并排序C.冒泡排序D.堆排序参考答案：A47. 二叉树索化后，仍不能有效求解的问题是( )A.后序线索二叉树中求后序后继B.前序线索二叉树中求前序后继C.中序线索二叉树中求中序后继D.中序线索二叉树中求中序前驱参考答案：A48. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为( )。

A.1和5B.2和4C.4和2D.5和1参考答案：B49. 设某算法的问题规模函数f(n)=300n2+8000n+900，则它的渐进时间复杂度为( )A.O(n3)B.O(n2)C.O(n)D.O(1)参考答案：B50. 在下列各种文件中，不能进行顺序查找的文件是( )A.顺序文件B.索引文件C.散列文件D.多重表文件参考答案：C51. 线性表中的所有元素都有一个前驱元素和后继元素 )A.正确B.错误参考答案：A52. 不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n) )A.正确B.错误参考答案：A53. 数据结构是( )A、一种数据类型B、数据的存储结构C、一组性质相同的数据元素的集合D、相互之间存在一种或多种特定关系的数据元素的集合参考答案：D54. 将一个A[1..100，1..100]的三对角矩阵，按行优先次序存入一维数组B[1..298]中，A中元素A[66，65]在数组B中的位置K为( )A.199B.197C.195D.193参考答案：C55. 下列程序段for(i=1; iA.O(1)B.O(0)C.O(1+n)D.O(n)参考答案：D56. 设有100个关键字，用折半查找法进行查找时，最大比较次数为( )。

A.7B.6C.50D.25参考答案：A57. 右图中的拓扑序列为( )A.C1，C2，C6，C7，C5，C4，C3B.C1，C2，C6，C3，C4，C5，C7C.C1，C4，C2，C3，C5，C6，C7D.C5，C7，C4，C1，C2，C6，C3参考答案：D58。