西北工业大学21秋《数据结构》在线作业三满分答案79

西北工业大学21秋数据结构在线作业三满分答案1. 数据的逻辑结构是指各数据元素之间的逻辑关系。( )A.正确B.错误参考答案：A2. 设串sl=DataStructureswithJava，s2=it，则子串定位函数index(s1,s2)的值为( )A.15B.16C.17D.18参考答案：D3. 按照二叉树的定义，具有3个结点的二叉树有( )种。A.3B.4C.5D.6参考答案：C4. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是( )。A.6B.4C.3D.2参考答案：C5. 一个队列的入队序列是1、2、3、4，则队列的首次输出元素是( )。A.1B.2C.3D.4参考答案：A6. 邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。( )A.正确B.错误参考答案：B7. 将森树转成二叉树，根结点没有右子树。( )A.正确B.错误参考答案：B8. 算法有以下几种特性( )。A、有穷性B、确定性C、可行性D、输入和输出参考答案：ABCD9. 下面哪些方法可以判断出一个有向图是否有环(回路)?( )A.求最短路径B.求关键路径C.拓扑排序D.广(宽)度优先遍历参考答案：C10. 设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为( )A.O(nlog2e)B.O(n+e)C.O(ne)D.O(n2)参考答案：B11. 在k叉树中，度为0的结点称为( )。A.祖先B.根C.子孙D.叶参考答案：D12. 设有以下四种排序方法，则( )的空间复杂度最大。A.冒泡排序B.快速排序C.堆排序D.希尔排序参考答案：B13. 指针p所指的元素是双向循环链表L的尾元素的条件是( )。A.p=LB.p=NULLC.p-prior=LD.p-next=L参考答案：D14. 线性表的链接实现有利于( )运算。A.插入B.读表元C.查找D.定位参考答案：A15. 下面程序段的时间复杂度为( )。for(i=0; im; i+)for(j=0; jn; j+)Aij=i*j;A、O(m2)B、O(n2)C、O(m*n)D、O(m+n)参考答案：C16. 在一个单链表中，已知q结点是p结点的前驱结点，若在q和p之间插入结点s，则执行操作：( )A.s-next=p-next; p-next=sB.s-next=p; q-next=sC.q-next=s; s-next=pD.p-next=s; s-next=q参考答案：B17. 若一个有向图的邻接距阵中，主对角线以下的元素均为零，则该图的拓扑有序序列( )。A.一定存在B.一定不存在C.不一定存在D.不确定参考答案：A18. 在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为( )。A.O(n)B.O(n+e)C.O(n2)D.O(n3)参考答案：B19. 一棵树可以只有1个结点。( )A、错误B、正确参考答案：B20. 数据的不可分割的最小标识单位是( )。A.数据项B.数据记录C.数据元素D.数据变量参考答案：A21. 非空的双向循环链表中任何结点的前驱指针均不为空。( )A.正确B.错误参考答案：A22. 若进栈序列为a，b，c，且进栈和出栈可以穿插进行，则可能出现6个不同的出栈序列。( )A、错误B、正确参考答案：A23. 深度为k的二叉树至多有2k-1个结点。( )A、错误B、正确参考答案：A24. 抽象数据类型是指数据逻辑结构及与之相关的操作。( )A、错误B、正确参考答案：B25. 字符串“sgabacbadfgbacst”中存在有6个与字符串“ba”相同的子串。( )A、错误B、正确参考答案：A26. 对长度为n的关键字序列进行堆排序的空间复杂度为( )。A.O(log2n)B.O(1)C.O(n)D.O(n*log2n)参考答案：B27. 对线性表进行二分查找时，要求线性表必须( )。A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且结点按关键字有序排列D.以链接方式存储，且结点按关键字有序排列参考答案：C28. Prim(普里姆)算法适用于求( )的网的最小生成树; kruskal(克鲁斯卡尔)算法适用于求( )的网的最小生成树。A.边稠密，边稀疏B.边稀疏，边稠密C.边稠密，边稠密D.边稀疏，边稀疏参考答案：A29. 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是( )。A.希尔排序B.快速排序C.插入排序D.选择排序参考答案：D30. 数据结构中的任一数据元素至多只有一个前驱和一个后继，该数据结构是( )。A.线性表B.树形结构C.广义表D.图结构参考答案：A31. 设有50行60列的二维数组A5060，其元素长度为4字节，按行优先顺序存储，基地址为200，则元素A1825的存储地址为( )。A.3700B.4376C.3900D.4620参考答案：D32. 数据的逻辑结构在计算机存储器内的表示，称为数据的逻辑结构。( )A、错误B、正确参考答案：A33. 在长度为n的顺表表的第i个位置上插入一个元素(1in+1)，元素的移动次数为( )。A.n-i+1B.n-iC.iD.i-1参考答案：C34. 下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。A.选择B.冒泡C.归并D.堆参考答案：C35. 线性表(a1，a2，.，an)以链式方式存储，访问第i位置元素的时间复杂度为( )。A.O(0)B.O(1)C.O(n)D.O(n2)参考答案：C36. 广义表(a，b，c，d)的表头是( )。A.(b，c，d)B.(a，b，c，d)C.aD.(a)参考答案：B37. 线性表的唯一存储形式就是链表。( )A.正确B.错误参考答案：A38. 在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度(即x与元素的平均比较次数，假定查找每个元素的概率都相等)为( )。A.nB.n/2C.(n+1)/2D.(n-1)/2参考答案：C39. 用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。A.逆拓扑有序B.拓扑有序C.无序的D.A和B参考答案：A40. 一个队列的入队序列是a、b、c、d，则队列的输出序列是( )。A.dcbaB.cbdaC.adcbD.abcd参考答案：D41. 若一个广义表的表头为空表，则此广义表亦为空表。( )A.正确B.错误参考答案：B42. 设有100个关键字，用折半查找法进行查找时，最大比较次数为( )。A.7B.6C.50D.25参考答案：A43. 对于哈希函数，冲突只能尽可能得少，不可能完全避免。( )A.正确B.错误参考答案：A44. 由带权为9，2，5，7的四个叶子结点构造一颗哈夫曼树，该树的带权路径长度为( )。A.23B.37C.46D.44参考答案：D45. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p之前插入s所指结点，则执行( )。A.s-next=p-next; p-next=sB.q-next=s; s-next=pC.p-next=s; s-next=qD.p-next=s-next; s-next=p参考答案：B46. 二叉树中的叶子结点就是二叉树中没有左右子树的结点。( )A、错误B、正确参考答案：B47. 按层次次序将一颗有n个结点的完全二叉树的所有结点从1到n编号，当iA.2i-1B.2iC.2i+1D.不确定参考答案：B48. 在k叉树中，无父母的结点称为( )。A.祖先B.根C.子孙D.叶参考答案：B49. 基数排序需要进行关键字的比较。( )A.正确B.错误参考答案：B50. 数据结构是带有结构的数据元素的集合。( )A.正确B.错误参考答案：A51. 在长度为n的顺序表的第i(1in+1)个位置上插入一个元素，元素的移动次数为( )。A、n-i+1B、n-iC、iD、i-1参考答案：A52. 若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为( )。A.4B.5C.8D.9参考答案：C53. 线性表的链式存储结构是一种( )。A.随机存取的存储结构B.顺序存取的存储结构C.索引存取的存储结构D.Hash存取的存储结构参考答案：A54. 一个关键字序列为46，79，56，38，40，84，采用快速排序以位于最左位置的元素为基准而得到的第一次划分结果为( )A.38，46，79，56，40，84B.38，79，56，46，40，84C.40，38，46，56，79，84D.38，46，56，79，40，84参考答案：C55. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为( )。A.1和5B.2和4C.4和2D.5和1参考答案：B56. 哈希表不需要进行比较便可以直接取得所查记录。( )A.正确B.错误参考答案：A57. 下列四种基本的逻辑结构中，数据元素之间关系最弱的是( )。A.集合B.线性结构C.树形结构D.图状结构参考答案：A58. 与单链表相比，双链表的优点之一是( )。A.插入、删除操作更简单B.可以进行随机访问C.可以省略表头指针或表尾指针D.顺序访问相邻结点更灵活参考答案：C59. 求图的最小(代价)生成树问题，考虑的是下面的哪一种图?( )A.有向图B.无向图C.带权的有向图D.带权的无向图参考答案：D60. 下列关于数据结构基本概念的叙述中，正确的是( )。A.数据的逻辑结构分为表结构和树结构B.数据的存储结构分为线性结构和非线性结构C.数据元素是数据的基本单位D.结点是有独立含义的数据最小单位参考答案：C