《西北工业大学21秋《数据结构》平时作业2-001答案参考70》由会员分享，可在线阅读，更多相关《西北工业大学21秋《数据结构》平时作业2-001答案参考70（11页珍藏版）》请在金锄头文库上搜索。
1、西北工业大学21秋数据结构平时作业2-001答案参考1. 字符串“sgabacbadfgbacst”中存在有6个与字符串“ba”相同的子串。( )A、错误B、正确参考答案：A2. 结构就是用户定义的，( )的一个集合体。参考答案：不同数据类型3. 无向图中一个顶点的度是指图中( )。A、通过该顶点的简单路径数B、与该顶点相邻接的顶点数C、通过该顶点的回路数D、与该顶点连通的顶点数参考答案：B4. 下列描述中正确的是( )。A.选择合适的数据结构是解决应用问题的关键步骤B.线性表的逻辑顺序与存储顺序总是一致的C.每种数据结构都具备查找、插入和删除三种基本运算D.数据结构实质上包括逻辑结构和存储结
2、构两方面的内容参考答案：A5. 设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为( )A.O(nlog2e)B.O(n+e)C.O(ne)D.O(n2)参考答案：B6. 后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。( )A.正确B.错误参考答案：A7. 若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为O(n)。( )A、错误B、正确参考答案：A8. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是( )。A.单链表B.静态链表C.线性链表D.顺序存储结构参考答案：C9. 二叉树中的叶子结点就是
3、二叉树中没有左右子树的结点。( )A、错误B、正确参考答案：B10. 引入二叉线索树的目的是( )。A.加快查找结点的前驱或后继的速度B.使二叉树的遍历结果唯一C.为了能方便的找到双亲D.为了能在二叉树中方便的进行插入与删除参考答案：A11. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是( )。A.0B.1C.2D.3参考答案：B12. 若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列3，2，5，6，4，1。( )A.正确B.错误参考答案：A13. 数据结构中的任一数据元素至多只有一个前驱和一个后继，该数据结构是( )。A.线性表B.树形结构C.广义表D.图结构参
4、考答案：A14. 下列排序中，某一趟结束后未必能选出一个元素放在其最终位置上的是( )。A.直接插入排序B.冒泡排序C.快速排序D.堆排序参考答案：A15. 判断线索二叉树中某结点p有右子女的条件是( )。A.p-rtag=1B.p-rtag=0C.p-lchild!=NULLD.p!=NULL参考答案：B16. 哈希表不需要进行比较便可以直接取得所查记录。( )A.正确B.错误参考答案：A17. 对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。( )A、错误B、正确参考答案：B18. 队列允许在队尾删除，在队头插入。( )A.正确B.错误参考答案：A19.
5、下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。A.选择B.冒泡C.归并D.堆参考答案：C20. 下面说法错误的是( )。 (1)算法原地工作的含义是指不需要任何额外的辅助空间; (2)在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法; (3)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界; (4)同一个算法，实现语言的级别越高，执行效率就越低。A.(1)B.(1)，(2)C.(1)，(4)D.(3)参考答案：C21. 采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为( )。A.n/2B.nC.(n-1)/2D.(
6、n+1)/2参考答案：D22. 下面关于串的叙述中，哪一个是不正确的?( )A.空串是由空格构成的串B.模式匹配是串的一种重要运算C.串是字符的有限序列D.串既可以采用顺序存储，也可以采用链式存储参考答案：A23. 二叉排序树上左子树上所有结点的值均小于它的根结点的值。( )A.正确B.错误参考答案：A24. 二叉树中必有度为2的结点。( )A、错误B、正确参考答案：A25. 假设一棵完全二叉树含1000个结点,则其中度为2的结点数为512个。( )A、错误B、正确参考答案：A26. 非空的双向循环链表中任何结点的前驱指针均不为空。( )A.正确B.错误参考答案：A27. 若有向图的邻接矩阵中
7、，主对角线以下元素均为零，则该图的拓扑有序序列( )。A.存在B.可能不存在C.不存在D.不一定存在参考答案：A28. 在队列中，允许进行插入操作的一端称为队头。( )A、错误B、正确参考答案：B29. 给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。( )A、错误B、正确参考答案：A30. 向顺序栈中压入新元素时，应当( )A.先移动栈顶位置，再存入元素B.先存入元素，再移动栈顶位置C.先后 次序无关紧要D.同时进行参考答案：A31. 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是( )。A.希尔排序B.快速排序C.插入排序D.选择排序参考答案：D32. 若要在单
8、链表中的结点p之后插入一个结点s，则应执行的语句是( )。A.s-next=p-next; p-next=sB.p-next=s; s-next=p-nextC.p-next=s-next; s-next=pD.s-next=p; p-next=s-next参考答案：A33. 对无序表用折半查找比顺序查找快。( )A.正确B.错误参考答案：B34. 向二叉搜索树中插入一个元素时，其时间复杂度大致为( )A.O(log2n)B.O(n)C.O(1)D.O(2n)参考答案：A35. 任何一个递归过程都可以转换成非递归过程。( )A.正确B.错误参考答案：A36. 若进栈序列为1，2，3，4，5，6
9、，且进栈和出栈可以穿插进行，则可能出现的出栈序列为( )。A、3，2，6，1，4，5B、3，4，2，1，6，5C、1，2，5，3，4，6D、5，6，4，2，3，1参考答案：B37. 在图G的最小生成树T中，可能会有某条边的权值超过未选边的权值。( )A.正确B.错误参考答案：A38. 在单链表中设置头结点的作用是( )。A.主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表指针不变B.便于查找C.便于连接D.快速插入记录参考答案：A39. 一个具有767个结点的完全二叉树，其叶子结点个数为( )。A.383B.384C.385D.3
10、86参考答案：B40. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。( )A.正确B.错误参考答案：B41. 一个关键字序列为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参考答案：C42. n个结点的线索二叉树上含有的线索数为( )。A.n-1B.n+1C.nD.2n参考答案：B43. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3
11、，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为( )。A.1和5B.2和4C.4和2D.5和1参考答案：B44. 由于排序过程中涉及的存储器不同，可以将排序方法分为( )。A、稳定排序B、不稳定排序C、内部排序D、外部排序参考答案：CD45. 已知一组关键字为25，48，36，72，79，82，23，40，16，35，其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是( )。A.25，36，48，72，23，40，79，82，16，35B.25，36，48，72，16，23，40，79，82，35C.25，36，48，72，16，23，35，40，79
12、，82D.16，23，25，35，36，40，48，72，79，82参考答案：D46. 从未排序序列中挑选元素，并将其依次插入已排序序列(初始时为空)的一端的方法，称为( )。A.希尔排序B.归并排序C.插入排序D.选择排序参考答案：D47. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的( )。A.先序遍历B.中序遍历C.后序遍历D.按层遍历参考答案：C48. 一个有向图的邻接表和逆邻接表中结点的个数可能不等。( )A.正确B.错误参考答案：B49. 通用的处理哈希冲突的方法有( )。A、开放定址法B、再哈希法C、链地址法D、建立公共溢出区参考答案：ABCD50. 分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。( )A.正确B.错误参考答案：A
