西北工业大学21秋《数据结构》平时作业二参考答案75

西北工业大学21秋数据结构平时作业二参考答案1. 邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。( )A.正确B.错误参考答案：B2. 依次在初始为空的队列中插入元素X，Y，Z，W以后，紧接着作了两次删除操作，此时的队头元素是( )A.XB.YC.ZD.W参考答案：C3. 在一个单链表中，已知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参考答案：B4. 线性表是具有n个( )的有限序列。A.字符B.数据元素C.数据项D.表元素参考答案：B5. 二叉树的叶结点，在前序遍历、中序遍历和后序遍历下皆以相同的相对位置出现。( )A.正确B.错误参考答案：A6. 队列的队尾位置通常是随着入队操作而变化的。( )A、错误B、正确参考答案：B7. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的( )。A.先序遍历B.中序遍历C.后序遍历D.按层遍历参考答案：C8. 一棵含18个结点的二叉树的高度至少为( )。A、3B、4C、5D、6参考答案：C9. 由于排序过程中涉及的存储器不同，可以将排序方法分为( )。A、稳定排序B、不稳定排序C、内部排序D、外部排序参考答案：CD10. 如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用( )。A.深度优先搜索算法B.广度优先搜索算法C.求最小生成树的prim算法D.拓扑排序算法参考答案：B11. 下列存储表示中，哪一个不是树的存储形式( )。A.双亲表示法B.孩子链表表示法C.顺序存储表示法D.孩子兄弟表示法参考答案：C12. 在目标串T0.n-1=“xwxxyxy”中，对模式串P0.m-1=“xy”进行子串定位操作的结果是( )。A.1B.2C.3D.5参考答案：C13. 已知一个散列表如图所示，其散列函数为H(key)=key%11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为( )。A.2B.3C.8D.9参考答案：C14. 在k叉树中，度为0的结点称为( )。A.祖先B.根C.子孙D.叶参考答案：D15. 在线性表的下列运算中，不改变数据元素之间结构关系的运算是( )。A、插入B、删除C、排序D、定位参考答案：D16. 引入二叉线索树的目的是( )。A.加快查找结点的前驱或后继的速度B.使二叉树的遍历结果唯一C.为了能方便的找到双亲D.为了能在二叉树中方便的进行插入与删除参考答案：A17. 若有18个元素的有序表存放在一堆数组A19中，第一个元素放A1中，现进行二分查找，则查找A3的比较序列的下标依次为( )。A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，3参考答案：D18. 若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为( )。A.4B.5C.8D.9参考答案：C19. 一个加权的无向连通图的最小生成树( )。A.有一颗或多颗B.只有一颗C.一定有多颗D.可能不存在参考答案：A20. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是( )。A.9B.11C.15D.不能确定参考答案：C21. 下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序?( )A.堆B.哈夫曼树C.二叉排序树D.AVL树参考答案：A22. 数据的不可分割的最小标识单位是( )。A.数据项B.数据记录C.数据元素D.数据变量参考答案：A23. AOV网的含义是以顶点表示活动的网。( )A.正确B.错误参考答案：A24. 数据结构是( )。A、一种数据类型B、数据的存储结构C、一组性质相同的数据元素的集合D、相互之间存在一种或多种特定关系的数据元素的集合参考答案：D25. 先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。( )A.正确B.错误参考答案：A26. 下列描述中正确的是( )。A.选择合适的数据结构是解决应用问题的关键步骤B.线性表的逻辑顺序与存储顺序总是一致的C.每种数据结构都具备查找、插入和删除三种基本运算D.数据结构实质上包括逻辑结构和存储结构两方面的内容参考答案：A27. 如果某种排序算法是不稳定的，则这种算法不可用。( )A.正确B.错误参考答案：A28. 删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。( )A、错误B、正确参考答案：A29. 设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为( )A.O(nlog2e)B.O(n+e)C.O(ne)D.O(n2)参考答案：B30. 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是( )。A.希尔排序B.快速排序C.插入排序D.选择排序参考答案：D31. 健壮的算法不会因非法的输人数据而出现莫名其妙的状态。( )A.正确B.错误参考答案：A32. 最佳二叉排序树是AVL树(平衡二叉排序树)。( )A.正确B.错误参考答案：A33. 在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是( )。A.O(1)B.O(n)C.O(n2)D.O(nlog2n)参考答案：B34. 一个队列的入队序列是a、b、c、d，则队列的输出序列是( )。A.dcbaB.cbdaC.adcbD.abcd参考答案：D35. head指向的带表头结点的单链表为空的判定条件是( )。A.head-next=headB.head-next=NULLC.head=NULLD.head!=NULL参考答案：B36. 冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。( )A.正确B.错误参考答案：A37. 在链表的结点中，数据元素所占的存储量和整个结点所占的存储量之比称作存储密度。( )A、错误B、正确参考答案：B38. 对线性表进行折半查找时，要求线性表必须( )。A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且结点按关键字有序排序D.以链接方式存储，且结点按关键字有序排序参考答案：C39. 按排序过程中依据的原则分类，快速排序属于( )。A.插入类的排序方法B.选择类的排序方法C.交换类的排序方法D.归并类的排序方法参考答案：C40. 下列程序段for(i=1; iA.O(1)B.O(0)C.O(1+n)D.O(n)参考答案：D41. 设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为( )。A.21B.23C.41D.62参考答案：C42. 任何一棵二叉树的叶结点在前序、中序和后序遍历序列中的相对次序( )。A.稍有改变B.发生改变C.不能确定D.不发生改变参考答案：D43. 任何一个递归过程都可以转换成非递归过程。( )A.正确B.错误参考答案：A44. B+树应用在( )文件系统中。A.顺序B.散列C.VSAMD.ISAM参考答案：C45. 采用分快查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分( )个结点最佳。A.10B.25C.6D.625参考答案：B46. 取顺序表的第i个元素的时间与i的大小无关。( )A.正确B.错误参考答案：A47. 结构的存储密度定义为数据本身所占的存储量与整个结构所占的存储量之比。( )A.正确B.错误参考答案：A48. 程序一定是算法。( )A.正确B.错误参考答案：B49. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是( )。A.(rear+1)%n=frontB.rear=frontC.rear+1=frontD.(rear-l)%n=front参考答案：B50. 线性表的链式存储结构是一种( )。A.随机存取的存储结构B.顺序存取的存储结构C.索引存取的存储结构D.Hash存取的存储结构参考答案：A51. 链式栈与顺序栈相比，一个比较明显的优点是( )A.插入操作更加方便B.通常不会出现栈满的情况C.不会出现栈空的情况D.删除操作更加方便参考答案：B52. 已知函数Sub(s,I,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=SCIENCESTUDY，则调用函数Scopy(P,Sub(S,1,7)后得到( )。A、P=SCIENCEB、P=STUDYC、S=SCIENCED、S=STUDY参考答案：A53. 栈是一种操作受限的线性结构，其操作的主要特征是( )。A、先进先出B、后进先出C、进优于出D、出优于进参考答案：B54. 中序遍历二叉排序树可以得到一个有序的序列。( )A.正确B.错误参考答案：A55. 设某完全无向图中有n个顶点，则该完全无向图中有( )条边。A.n(n-1)/2B.n(n-1)C.n2D.n2-1参考答案：A56. 链式队列Q为空的判定条件：( )A.Q.front=Q.rearB.Q.front=QC.Q=Q.rearD.没有正确参考答案：A57. 在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是堆排序。( )A、错误B、正确参考答案：A58. 算法有以下几种特性( )。A、有穷性B、确定性C、可行性D、输入和输出参考答案：ABCD59. n个顶点的连通图至少有( )条边。A.n-1B.nC.n+1D.0参考答案：A60. 用ISAM组织文件适合于( )。A.磁盘B.磁带C.外存储器D.光盘参考答案：A