《西北工业大学21春《数据结构》在线作业二满分答案71》由会员分享，可在线阅读，更多相关《西北工业大学21春《数据结构》在线作业二满分答案71（13页珍藏版）》请在装配图网上搜索。
1、西北工业大学21春数据结构在线作业二满分答案1. 算法分析的目的是( )。A、辨别数据结构的合理性B、评价算法的效率C、研究算法中输入与输出的关系D、鉴别算法的可读性参考答案：B2. 在队列中，允许进行删除操作的一端称为队尾。( )A、错误B、正确参考答案：B3. 在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为( )。A.O(n)B.O(n+e)C.O(n2)D.O(n3)参考答案：B4. 在一个长度为100的顺序表中删除第10个元素时，需移动90个元素。( )A、错误B、正确参考答案：B5. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是( )。A.单链表B
2、.静态链表C.线性链表D.顺序存储结构参考答案：C6. 下面哪些方法可以判断出一个有向图是否有环(回路)?( )A.求最短路径B.求关键路径C.拓扑排序D.广(宽)度优先遍历参考答案：C7. 对于3个结点a、b、c，可构成不同的二叉树的棵数为( )。A.32B.30C.28D.24参考答案：B8. 在文本编辑程序中查找某一特定单词在文本中出现的位置，可以利用串的定位操作。( )A、错误B、正确参考答案：B9. 归并排序是一种稳定的排序方法。( )A.正确B.错误参考答案：A10. 取顺序表的第i个元素的时间与i的大小无关。( )A.正确B.错误参考答案：A11. 由于排序过程中涉及的存储器不同
3、，可以将排序方法分为( )。A、稳定排序B、不稳定排序C、内部排序D、外部排序参考答案：CD12. 用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。A.逆拓扑有序B.拓扑有序C.无序的D.A和B参考答案：A13. 已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为k。( )A、错误B、正确参考答案：A14. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为( )。A、3，2，6，1，4，5B、3，4，2，1，6，5C、1，2，5，3，4，6D、5，6，4，2，3，
4、1参考答案：B15. 一个有向无环图的拓扑排序序列( )是唯一的。A.可能B.不一定C.三者均不对D.一定参考答案：B16. 若进栈序列为a，b，c，则通过入出栈操作可能得到的a，b，c的不同排列个数为( )。A、4B、5C、6D、7参考答案：B17. 在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针P所指向的结点，则执行( )A.q-next=p-next;p=qB.p-next=q-next;q=pC.q-next=p-next;p-next=qD.p-next=q-next;q-next=p参考答案：D18. 下列陈述中正确的是( )。A.二叉树是度为2的有序树B.二叉树中结
5、点只有一个孩子时无左右之分C.二叉树中必有度为2的结点D.二叉树中最多只有两棵子树，并且有左右之分参考答案：D19. 在计算机内实现递归算法时所需的辅助数据结构是( )。A、栈B、队列C、树D、图参考答案：A20. 二叉树中必有度为2的结点。( )A、错误B、正确参考答案：A21. 在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度(即x与元素的平均比较次数，假定查找每个元素的概率都相等)为( )。A.nB.n/2C.(n+1)/2D.(n-1)/2参考答案：C22. 队列允许在队尾删除，在队头插入。( )A.正确B.错误参考答案：A23. 任何有向网的拓扑排序的结果
6、是唯一的。( )A.正确B.错误参考答案：B24. 在下列排序算法中，哪一个算法的时间复杂度与记录初始排列无关?( )A.直接选择排序B.直接插入排序C.快速排序D.冒泡排序参考答案：A25. 算法分析的两个主要方面是( )。A.空间复杂度和时间复杂度B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性参考答案：A26. 链接存储结构属动态存储方式。( )A.正确B.错误参考答案：A27. 冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。( )A.正确B.错误参考答案：A28. 已知循环队列的存储空间为数组data21，且当前队列的头指针和尾指针的值分别为8和3，则该队列的
7、当前长度为( )。A.5B.6C.16D.17参考答案：C29. 在单链表中设置头结点的作用是( )。A.主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表指针不变B.便于查找C.便于连接D.快速插入记录参考答案：A30. 在指定结点之前插入新结点时，双链表比单链表更方便。( )A.正确B.错误参考答案：A31. 下面程序段的时间复杂度为( )。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)参考答案：C32. 若有序表的关键字序列为(b，c
8、，d，e，f，g，q，r，s，t)，则在二分查找关键字b的过程中，先后进行比较的关键字依次为( )。A.f，c，bB.f，d，bC.g，c，bD.g，d，b参考答案：A33. 快速排序是排序算法中平均性能最好的一种排序。( )A.正确B.错误参考答案：A34. 设有以下四种排序方法，则( )的空间复杂度最大。A.冒泡排序B.快速排序C.堆排序D.希尔排序参考答案：B35. 右图中的拓扑序列为( )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参考答案：D36. 线性
9、链表是通过( )方式表示元素之间的关系A.后继元素地址B.元素的存储顺序C.左、右孩子地址D.元素的相对存储位置参考答案：A37. 不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。( )A.正确B.错误参考答案：A38. B+树应用在( )文件系统中。A.顺序B.散列C.VSAMD.ISAM参考答案：C39. 快速排序方法在( )情况下最不利于发挥其长处。A.被排序的数据量太大B.被排序数据中含有多个相同值C.被排序数据已基本有序D.被排序数据数目为奇数参考答案：C40. 将森树转成二叉树，根结点没有右子树。( )A.正确B.错误参考答案：B41. 在以单链表为存储结构的
10、线性表中，数据元素之间的逻辑关系用( )。A.数据元素的相邻地址表示B.数据元素在表中的序号表示C.指向后继元素的指针表示D.数据元素的值表示参考答案：C42. 后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。( )A.正确B.错误参考答案：A43. 数据的逻辑结构描述数据元素之间的逻辑关系，与存储方式无关。( )A、错误B、正确参考答案：B44. 设某算法的问题规模函数f(n)=300n2+8000n+900，则它的渐进时间复杂度为( )A.O(n3)B.O(n2)C.O(n)D.O(1)参考答案：B45. 设根结点层次为1，某二叉树的结点前序序列和后序序列正好相反，则该二叉树一定是
11、( )。A.高度等于其结点数B.空或只有一个结点C.任一结点无左子女D.任一结点无右子女参考答案：A46. 对于双向链表，在两个结点之间插入一个新结点需修改的指针共( )个，单链表为( )个。A.4，1B.4，2C.1，4D.2，4参考答案：B47. 程序一定是算法。( )A.正确B.错误参考答案：B48. 对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。( )A、错误B、正确参考答案：B49. 循环队列SQ采用数组空间SQ.base0，n-1存储其元素值，已知其头尾指针分别是front和rezr，则判断此循环队列Q为满队列的条件是( )。A.Q.front=
12、Q.rearB.Q.rear!=Q.frontC.Q.front=(Q.rear+1)%nD.Q.front!=(Q.rear+1)%n参考答案：C50. 以下( )不是队列的基本运算。A.从队尾插入一个新元素B.从队列中删除第i个元素C.判断一个队列是否为空D.读取队头元素的值参考答案：B51. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的( )。A.先序遍历B.中序遍历C.后序遍历D.按层遍历参考答案：C52. 对某二叉树进行前序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果为( )A.DBFEACB.DFEBCAC.BDFECAD.BDEFAC参考答案：B
13、53. n个结点的线索二叉树上含有的线索数为( )。A.n-1B.n+1C.nD.2n参考答案：B54. 算法有以下几种特性( )。A、有穷性B、确定性C、可行性D、输入和输出参考答案：ABCD55. 数据的逻辑结构是指各数据元素之间的逻辑关系。( )A.正确B.错误参考答案：A56. 以下关于线性表的说法不正确的是( )。A.线性表中的数据元素可以是数字、字符、记录等不同类型B.线性表中包含的数据元素个数不是任意的C.线性表中的每个结点都有且只有一个直接前趋和直接后继D.存在这样的线性表：表中各结点都没有直接前趋和直接后继参考答案：C57. 算法分析的目的是( )。A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易读性和文档性参考答案：C58. 通常将链串的结点大小设置为大于1是为了( )。A、提高串匹配效率B、提高存储密度C、便于插入操作D、便于删除操作参考答案：A59. 若已知一个栈序列是1，2，3，.，n，其输出序列为p1，p2，p3，.，pn，若p1=n，则pi为( )。A.iB.n-iC.n-i+1D.不确定参考答案：C60. 由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多。( )A、错误B、正确参考答案：A
西北工业大学21春《数据结构》在线作业二满分答案71
