《西北工业大学21春《数据结构》在线作业二满分答案_21》由会员分享，可在线阅读，更多相关《西北工业大学21春《数据结构》在线作业二满分答案_21（14页珍藏版）》请在金锄头文库上搜索。
1、西北工业大学21春数据结构在线作业二满分答案1. 平衡二叉树的平衡因子只可能是-1、0、1。( )A.正确B.错误参考答案：A2. 在数据结构中，数据的逻辑结构可以分成( )。A、内部结构和外部结构B、线性结构和非线性结构C、紧凑结构和非紧揍结构D、动态结构和静态结构参考答案：C3. 下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序?( )A.堆B.哈夫曼树C.二叉排序树D.AVL树参考答案：A4. 如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用( )。A.深度优先搜索算法B.广度优先搜索算法C.求最小生成树的prim算法D.拓扑排序算法参考答
2、案：B5. 对线性表进行二分查找时，要求线性表必须( )。A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且结点按关键字有序排列D.以链接方式存储，且结点按关键字有序排列参考答案：C6. 数据结构是带有结构的数据元素的集合。( )A.正确B.错误参考答案：A7. 深度为5的二叉树至多有( )个结点。A.16B.32C.31D.10参考答案：C8. 在长度为n的顺表表的第i个位置上插入一个元素(1in+1)，元素的移动次数为( )。A.n-i+1B.n-iC.iD.i-1参考答案：C9. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为( )。A、3，
3、2，6，1，4，5B、3，4，2，1，6，5C、1，2，5，3，4，6D、5，6，4，2，3，1参考答案：B10. 在一个长度为100的顺序表中删除第10个元素时，需移动90个元素。( )A、错误B、正确参考答案：B11. 哈希表不需要进行比较便可以直接取得所查记录。( )A.正确B.错误参考答案：A12. 设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行( )趟的分配和回收才能使得初始关键字序列变成有序序列。A.3B.4C.5D.8参考答案：A13. 若已知一个栈序列是1，2，3，.，n，其输出序列为p1，p2，p3，.，pn，若p1=n，则pi为(
4、 )。A.iB.n-iC.n-i+1D.不确定参考答案：C14. 数据的逻辑结构是指各数据元素之间的逻辑关系。( )A.正确B.错误参考答案：A15. 下列陈述中正确的是( )。A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树中必有度为2的结点D.二叉树中最多只有两棵子树，并且有左右之分参考答案：D16. 由带权为9，2，5，7的四个叶子结点构造一颗哈夫曼树，该树的带权路径长度为( )。A.23B.37C.46D.44参考答案：D17. 设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为( )A.O(nlog2e)B.O(n+e)
5、C.O(ne)D.O(n2)参考答案：B18. 下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。A.选择B.冒泡C.归并D.堆参考答案：C19. 在一个单链表中，已知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参考答案：B20. 在一个长度为n的循环链表中，删除其元素值为x的结点的时间复杂度为O(n)。( )A、错误B、正确参考答案：B21. 在目标串T0.n-
6、1=“xwxxyxy”中，对模式串P0.m-1=“xy”进行子串定位操作的结果是( )。A.1B.2C.3D.5参考答案：C22. 以下数据结构中，属于线性结构的是( )。A.广义表B.二叉树C.稀疏矩阵D.串参考答案：A23. 从未排序序列中挑选元素，并将其依次插入已排序序列(初始时为空)的一端的方法，称为( )。A.希尔排序B.归并排序C.插入排序D.选择排序参考答案：D24. 线性表的链式存储结构是一种( )。A.随机存取的存储结构B.顺序存取的存储结构C.索引存取的存储结构D.Hash存取的存储结构参考答案：A25. 带行表的三元组表是稀疏矩阵的一种( )。A.顺序存储结构B.链式存储
7、结构C.索引存储结构D.散列存储结构参考答案：A26. 插入、删除只能在同一端进行的线性表，称为( )。A.队列B.栈C.循环队列D.循环栈参考答案：B27. 若有向图的邻接矩阵中，主对角线以下元素均为零，则该图的拓扑有序序列( )。A.存在B.可能不存在C.不存在D.不一定存在参考答案：A28. 若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为( )。A.4B.5C.8D.9参考答案：C29. 在一个单链表中，已知q结点是p结点的前驱结点，若在q和p之间插入结点s，则执行操作：( )A.s-next=p-next; p-next=sB.s-next=p; q-nex
8、t=sC.q-next=s; s-next=pD.p-next=s; s-next=q参考答案：B30. 四个元素进入队列QU的顺序是U、V、X、Y，进行DeQueue(QU，x)操作后，队头元素是( )。A.YB.XC.VD.U参考答案：C31. 若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。A.(n-1)2B.n2C.(n+1)2D.n参考答案：C32. 不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。( )A.正确B.错误参考答案：A33. 采用顺序查找方法查找长度为n的线性表时，
9、每个元素的平均查找长度为( )。A.n/2B.nC.(n-1)/2D.(n+1)/2参考答案：D34. 线性表的唯一存储形式就是链表。( )A.正确B.错误参考答案：A35. 对某二叉树进行前序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果为( )A.DBFEACB.DFEBCAC.BDFECAD.BDEFAC参考答案：B36. 下列程序段for(i=1; iA.O(1)B.O(0)C.O(1+n)D.O(n)参考答案：D37. 程序一定是算法。( )A.正确B.错误参考答案：B38. 在含100个结点的完全二叉树中，叶子结点的个数为36。( )A、错误B、正确参考答
10、案：A39. 引入二叉线索树的目的是( )。A.加快查找结点的前驱或后继的速度B.使二叉树的遍历结果唯一C.为了能方便的找到双亲D.为了能在二叉树中方便的进行插入与删除参考答案：A40. 若进栈序列为a，b，c，则通过入出栈操作可能得到的a，b，c的不同排列个数为( )。A、4B、5C、6D、7参考答案：B41. 链表中的表头指针与表头结点起到相同的作用。( )A.正确B.错误参考答案：B42. 数据项是数据的基本单位。( )A.正确B.错误参考答案：A43. n个顶点的强连通图中至少含有( )。A.n-1条有向边B.n条有向边C.n(n-1)/2条有向边D.n(n-1)条有向边参考答案：B4
11、4. 归并排序的辅助存储空间代价为O(1)。( )A.正确B.错误参考答案：B45. 若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为O(n)。( )A、错误B、正确参考答案：A46. 一个加权的无向连通图的最小生成树( )。A.有一颗或多颗B.只有一颗C.一定有多颗D.可能不存在参考答案：A47. 一个队列的入队序列是1、2、3、4，则队列的首次输出元素是( )。A.1B.2C.3D.4参考答案：A48. 在有向图中，以顶点v为终点的边的数目称为v的入度。( )A、错误B、正确参考答案：B49. 下列说法中，不正确的是( )。A.数据元素是数据的基本单位B
12、.数据项是数据中不可分割的最小可标识单位C.数据可由若干个数据元素构成D.数据项可由若干个数据元素构成参考答案：D50. 设串sl=DataStructureswithJava，s2=it，则子串定位函数index(s1,s2)的值为( )A.15B.16C.17D.18参考答案：D51. 数据的不可分割的最小标识单位是( )。A.数据项B.数据记录C.数据元素D.数据变量参考答案：A52. 二叉树中除叶结点外，任一结点X，其左子树根结点的值小于该结点X的值;其右子树根结点的值大于等于该结点X的值，则此二叉树一定是二叉排序树。( )A.正确B.错误参考答案：B53. 在一个单链表中，若删除*p
13、结点的后继结点，则执行操作( )。A.q=p-next; p-next=q-next; free(q)B.p=p-next; p-next=p-next-next; free(p)C.p-next=q-next; free(p-next)D.p=p-next-next; free(p-next)参考答案：A54. 在对含n个结点的二叉树进行先序、中序和后序遍历时，其时间复杂度( )。A.都不相同B.完全相同C.先序和中序相同，而与后序不同D.中序和后序相同，而与先序不同参考答案：B55. 对无序表用折半查找比顺序查找快。( )A.正确B.错误参考答案：B56. 已知一个散列表如图所示，其散列函数为H(key)=key%11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为( )。A.2B.3C.8D.9
