《西北工业大学21春《数据结构》在线作业三满分答案74》由会员分享，可在线阅读，更多相关《西北工业大学21春《数据结构》在线作业三满分答案74（13页珍藏版）》请在金锄头文库上搜索。
1、西北工业大学21春数据结构在线作业三满分答案1. 不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。( )A.正确B.错误参考答案：A2. 数据结构是指( )。A.数据元素的组织形式B.数据类型C.据存储结构D.数据定义参考答案：A3. 由树转化成二叉树，其根节点的右子树总是空。( )A.正确B.错误参考答案：A4. 在有向图中，以顶点v为终点的边的数目称为v的入度。( )A、错误B、正确参考答案：B5. 对某二叉树进行前序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果为( )A.DBFEACB.DFEBCAC.BDFECAD.BD
2、EFAC参考答案：B6. 一棵含999个结点的完全二叉树的深度为12。( )A、错误B、正确参考答案：A7. 算法分析的两个主要方面是( )。A.正确性与健壮性B.时间复杂度与空间复杂度C.数据复杂性与程序复杂性D.可读性与可用性参考答案：B8. 在含100个结点的完全二叉树中，叶子结点的个数为36。( )A、错误B、正确参考答案：A9. 设串s1=Data Structures with Java，s2=it，则子串定位函数index(s1,s2)的值为( )。A、15B、16C、17D、18参考答案：D10. 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是( )。A.希尔排
3、序B.快速排序C.插入排序D.选择排序参考答案：D11. 若进栈序列为a，b，c，且进栈和出栈可以穿插进行，则可能出现6个不同的出栈序列。( )A、错误B、正确参考答案：A12. 对线性表进行折半查找时，要求线性表必须( )。A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且结点按关键字有序排序D.以链接方式存储，且结点按关键字有序排序参考答案：C13. 已知指针p指向某单链表中的一个结点，则判别该结点有且仅有一个后继结点的条件是p-next-next=null。( )A、错误B、正确参考答案：B14. 一个队列的入队序列是a、b、c、d，则队列的输出序列是( )。A.dcbaB.cb
4、daC.adcbD.abcd参考答案：D15. 在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p-next-next=head，则( )。A、p指向头结点B、p指向尾结点C、*p的直接后继是头结点D、*P的直接后继是尾结点参考答案：D16. 有关二叉树下列说法正确的是( )。A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为2参考答案：B17. 栈是一种操作受限的线性结构，其操作的主要特征是( )。A、先进先出B、后进先出C、进优于出D、出优于进参考答案：B18. 已知完全二叉树T的第5层只有7个结点，则该
5、树共有15个叶子结点。( )A、错误B、正确参考答案：A19. 若进栈序列为a，b，c，则通过入出栈操作可能得到的a，b，c的不同排列个数为( )。A、4B、5C、6D、7参考答案：B20. 在长度为n的顺序表的第i(1in+1)个位置上插入一个元素，元素的移动次数为( )。A、n-i+1B、n-iC、iD、i-1参考答案：A21. 在目标串T0.n-1=“xwxxyxy”中，对模式串P0.m-1=“xy”进行子串定位操作的结果是( )。A.1B.2C.3D.5参考答案：C22. 若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )
6、。A.(n-1)2B.n2C.(n+1)2D.n参考答案：C23. 链接存储结构属动态存储方式。( )A.正确B.错误参考答案：A24. 对于3个结点a、b、c，可构成不同的二叉树的棵数为( )。A.32B.30C.28D.24参考答案：B25. 一个具有767个结点的完全二叉树，其叶子结点个数为( )。A.383B.384C.385D.386参考答案：B26. 一个队列的入队序列是1、2、3、4，则队列的首次输出元素是( )。A.1B.2C.3D.4参考答案：A27. 分块查找在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中的元素个数有关。( )A.正确B.错误参考答案
7、：A28. 某二叉树的前序和后序序列正好相同，则该二叉树一定是( )的二叉树。A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子参考答案：A29. 若让元素1，2，3依次进栈，则出栈次序不可能出现种情况( )A.3，2，1B.2，1，3C.3，1，2D.1，3，2参考答案：C30. 在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度(即x与元素的平均比较次数，假定查找每个元素的概率都相等)为( )。A.nB.n/2C.(n+1)/2D.(n-1)/2参考答案：C31. 非空的双向循环链表中任何结点的前驱指针均不为空。( )A.正确B.错误
8、参考答案：A32. 若一个广义表的表头为空表，则此广义表亦为空表。( )A.正确B.错误参考答案：B33. 为使平均查找长度达到最小，当由关键字集合05，11，21，25，37，40，41，62，84构建二叉排序树时，第一个插入的关键字应为( )。A.5B.37C.41D.62参考答案：B34. 分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。( )A.正确B.错误参考答案：A35. 下列说法中，不正确的是( )。A.数据元素是数据的基本单位B.数据项是数据中不可分割的最小可标识单位C.数据可由若干个数据元素构成D.数据项可由若干
9、个数据元素构成参考答案：D36. 在单链表中设置头结点的作用是( )。A.主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表指针不变B.便于查找C.便于连接D.快速插入记录参考答案：A37. 深度为5的二叉树至多有( )个结点。A.16B.32C.31D.10参考答案：C38. 线性表的链式存储结构是一种( )。A.随机存取的存储结构B.顺序存取的存储结构C.索引存取的存储结构D.Hash存取的存储结构参考答案：A39. 一棵左右子树均不空的二叉树在前序线索化后，其中空的链域的个数是( )。A.不确定B.2C.1D.0参考答案：C4
10、0. 设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数为( )A.3B.4C.5D.1参考答案：B41. 已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为( )。A.DEBAFCB.DEFBCAC.DEBCFAD.DEBFCA参考答案：B42. 在头指针为head的非空单循环链表中，指针p指向尾结点，下列关系成立的是( )。A、p-next=headB、p-next-next=headC、p-next=NULLD、p=head参考答案：A43. 在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是堆排序。( )A、错误B、正确参考答案：A
11、44. 设根结点层次为1，某二叉树的结点前序序列和后序序列正好相反，则该二叉树一定是( )。A.高度等于其结点数B.空或只有一个结点C.任一结点无左子女D.任一结点无右子女参考答案：A45. 设有以下四种排序方法，则( )的空间复杂度最大。A.冒泡排序B.快速排序C.堆排序D.希尔排序参考答案：B46. 如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为( )。A.插入排序B.归并排序C.冒泡排序D.堆排序参考答案：A47. 用链接方式存储的队列，在进行插入运算时( )。A.仅修改头指针B.头、尾指针都要修改C.仅修改尾指针D.头、尾指
12、针可能都要修改参考答案：D48. 在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为( )。A.O(n)B.O(n+e)C.O(n2)D.O(n3)参考答案：B49. 下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。A.选择B.冒泡C.归并D.堆参考答案：C50. 若哈希表(散列表)的负载因子l，则可避免冲突的产生。( )A.正确B.错误参考答案：B51. 在无向图中，若从顶点a到顶点b存在通路，则称a与b之间是连通的。( )A、错误B、正确参考答案：B52. 在下列排序算法中，哪一个算法的时间复杂度与记录初始排列无关?( )A.直接选择排序B.直接插入排
13、序C.快速排序D.冒泡排序参考答案：A53. n个顶点的连通图至少有( )条边。A.n-1B.nC.n+1D.0参考答案：A54. 将森树转成二叉树，根结点没有右子树。( )A.正确B.错误参考答案：B55. 栈和队列都是限制存取点的线性结构。( )A.正确B.错误参考答案：A56. 算法分析的目的是( )。A、辨别数据结构的合理性B、评价算法的效率C、研究算法中输入与输出的关系D、鉴别算法的可读性参考答案：B57. 下面程序段的时间复杂度是( )。for(i=0; in; i+) for(j=1; jm; j+) Aij=0;A、O(n)B、O(m+n+1)C、O(m+n)D、O(m*n)参考答案：D58. 下列四种排序中( )的空间复杂度最大。A.插入排序B.冒泡排序C
