999kao.com
西北工业大学22春《数据结构》在线作业一及答案参考88
A. 4
B. 5
C. 6#7
A.4
B.5
C.6
D.7
● (45) 从二叉树的任一结点出发到根的路径上，所经过的结点序列必按其关键字降序排列。
(45) A．二叉排序树
B．大顶堆
C．平衡二叉树
D．小顶堆
【解析】二叉排序树有以下特点：每个结点的左子树中所有结点的值都小于该结点的值，而右子树中所有结点的值都大于该结点的值。平衡二叉树是指其上任一结点的左右子树的高度(或者结点个数)保持一定比例的树，即平衡树上任一结点的左、右子树仍然保持平衡。堆排序的基本思想为对一组待排序记录的关键字，首先把它们按堆的定义排成一个序列，即建立初始小(或大)顶堆，输出堆项最小(或大)元素，然后将剩余的关键字再调整成新堆，便得到次小(或大)的关键字，其中降序排列为小顶堆，升序排序为大顶堆。
若进栈序列为a，b，c，则通过入出栈操作可能得到的a，b，c的不同排列个数为 _______。
A．4
B．5
C．6
D．7
● 若将某有序树 T 转换为二叉树 T1，则 T 中结点的后（根）序序列就是 T1 中结点的 （27） 遍历序列。例如下图(a)所示的有序树转化为二叉树后如图(b)所示。
（27）
A. 先序
B. 中序
C. 后序
D. 层序
西北工业大学22春数据结构在线作业一及答案参考1. 任何一个无向连通图的最小生成树( )。A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在参考答案：B2. 设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行( )趟的分配和回收才能使得初始关键字序列变成有序序列。A.3B.4C.5D.8参考答案：A3. 字符串“sgabacbadfgbacst”中存在有6个与字符串“ba”相同的子串。( )A、错误B、正确参考答案：A4. 下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序?( )A.堆B.哈夫曼树C.二叉排序树D.AVL树参考答案：A5. 若进栈序列为a，b，c，则通过入出栈操作可能得到的a，b，c的不同排列个数为( )。A、4B、5C、6D、7参考答案：B6. 下列序列中，不构成堆的是( )。A.(1，2，5，3，4，6，7，8，9，10)B.(10，5，8，4，2，6，7，1，3)C.(10，9，8，7，3，5，4，6，2)D.(1，2，3，4，10，9，8，7，6，5)参考答案：D7. 抽象数据类型的三个组成部分分别为( )。A、数据对象、数据关系和基本操作B、数据元素、逻辑结构和存储结构C、数据项、数据元素和数据类型D、数据元素、数据结构和数据类型参考答案：A8. 对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的左孩子的编号为98。( )A、错误B、正确参考答案：B9. 在计算机内实现递归算法时所需的辅助数据结构是( )。A、栈B、队列C、树D、图参考答案：A10. 一个栈的入栈序列是abcde，则栈的不可能的输出序列是( )。A.edcbaB.decbaC.dceabD.abcde参考答案：C11. 计算机识别、存储和加工处理的对象被统称为( )。A、数据B、数据元素C、数据结构D、数据类型参考答案：A12. 采用邻接表存储的图的广度优先遍历算法类似于二叉树的( )。A.先序遍历B.中序遍历C.后序遍历D.按层遍历参考答案：D13. 将一个A1.100，1.100的三对角矩阵，按行优先次序存入一维数组B1.298中，A中元素A66，65在数组B中的位置K为( )。A.199B.197C.195D.193参考答案：C14. 在一个长度为n的循环链表中，删除其元素值为x的结点的时间复杂度为O(n)。( )A、错误B、正确参考答案：B15. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是( )。A.(rear+1)%n=frontB.rear=frontC.rear+1=frontD.(rear-l)%n=front参考答案：B16. 某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为( )。A.3B.2C.4D.5参考答案：C17. 中序遍历的递归算法平均空间复杂度为( )。A.2(n)B.n(2)C.0(n)D.2n参考答案：C18. 按排序过程中依据的原则分类，快速排序属于( )。A.插入类的排序方法B.选择类的排序方法C.交换类的排序方法D.归并类的排序方法参考答案：C19. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为( )。A.1和5B.2和4C.4和2D.5和1参考答案：B20. 设s1=“abc”，则strlen(s1)=( )。A.3B.2C.1D.0参考答案：A21. 分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。( )A.正确B.错误参考答案：A22. 线性表中的所有元素都有一个前驱元素和后继元素。( )A.正确B.错误参考答案：A23. 如果某种排序算法是不稳定的，则这种算法不可用。( )A.正确B.错误参考答案：A24. 最佳二叉排序树是AVL树(平衡二叉排序树)。( )A.正确B.错误参考答案：A25. 二叉树中的叶子结点就是二叉树中没有左右子树的结点。( )A、错误B、正确参考答案：B26. 哈希表不需要进行比较便可以直接取得所查记录。( )A.正确B.错误参考答案：A27. 对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )。A.顺序表B.用头指针表示的循环单链表C.用尾指针表示的循环单链表D.单链表参考答案：C28. 四个元素进入队列QU的顺序是U、V、X、Y，进行DeQueue(QU，x)操作后，队头元素是( )。A.YB.XC.VD.U参考答案：C29. 数据元素及其关系在计算机存储器内的表示，称为数据的( )。A.逻辑结构B.存储结构C.线性结构D.非线性结构参考答案：B30. 设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有( )条有向边。A.nB.n-1C.mD.m-1参考答案：C31. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是( )。A.0B.1C.2D.3参考答案：B32. 二叉树中必有度为2的结点。( )A、错误B、正确参考答案：A33. 设串s1=Data Structures with Java，s2=it，则子串定位函数index(s1,s2)的值为( )。A、15B、16C、17D、18参考答案：D34. 不含任何字符的串称为空串。( )A、错误B、正确参考答案：B35. 已知循环队列的存储空间为数组data21，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为( )。A.5B.6C.16D.17参考答案：C36. 栈的插入和删除操作在( )进行。A.栈顶B.栈底C.任意位置D.指定位置参考答案：A37. 已知一个散列表如图所示，其散列函数为H(key)=key%11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为( )。A.2B.3C.8D.9参考答案：C38. 对无序表用折半查找比顺序查找快。( )A.正确B.错误参考答案：B39. 一个加权的无向连通图的最小生成树( )。A.有一颗或多颗B.只有一颗C.一定有多颗D.可能不存在参考答案：A40. 若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为O(n)。( )A、错误B、正确参考答案：A41. 在线性表的下列运算中，不改变数据元素之间结构关系的运算是( )。A、插入B、删除C、排序D、定位参考答案：D42. 与单链表相比，双链表的优点之一是( )。A.插入、删除操作更简单B.可以进行随机访问C.可以省略表头指针或表尾指针D.顺序访问相邻结点更灵活参考答案：C43. 二叉树的叶结点，在前序遍历、中序遍历和后序遍历下皆以相同的相对位置出现。( )A.正确B.错误参考答案：A44. 如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用( )。A.深度优先搜索算法B.广度优先搜索算法C.求最小生成树的prim算法D.拓扑排序算法参考答案：B45. 不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。( )A.正确B.错误参考答案：A46. 对于哈希函数H(key)=key%13，被称为同义词的关键字是( )。A、35和41B、23和39C、15和44D、25和51参考答案：D47. 对某二叉树进行前序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果为( )A.DBFEACB.DFEBCAC.BDFECAD.BDEFAC参考答案：B48. 在对链队列作出队操作时，不会改变front指针的值。( )A、错误B、正确参考答案：A49. 对于哈希函数，冲突只能尽可能得少，不可能完全避免。( )A.正确B.错误参考答案：A50. 在链表的结点中，数据元素所占的存储量和整个结点所占的存储量之比称作存储密度。( )A、错误B、正确参考答案：B51. 某二叉树的前序和后序序列正好相同，则该二叉树一定是( )的二叉树。A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子参考答案：A52. 队列的修改是按照先进先出的原则进行的。( )A、错误B、正确参考答案：B53. 在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为( )。A.O(n)B.O(n+e)C.O(n2)D.O(n3)参考答案：B54. 下面哪些方法可以判断出一个有向图是否有环(回路)?( )A.求最短路径B.求关键路径C.拓扑排序D.广(宽)度优先遍历参考答案：C55. 已知广义表LS=(a，b，c)，(d，e，f)，运算head和tail函数取出元素e的运算是( )。A.head(tail(LS)B.tail(head(LS)C.head(tail(head(tail(LS)D.head(tail(tail(head(LS)参考答案：C56. 按层次次序将一颗有n个结点的完全二叉树的所有结点从1到n编号，当iA.2i-1B.2iC.2i+1D.不确定参考答案：B57. 设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有( )A.n-1B.nC.n+1D.n+2参考答案：B58. 数据的存储结构是数据的逻辑结构在计算机存储器上的实现，它是依赖于计算机的。( )A.正确B.错误参考答案：A59. 已知指针p指向某单链表中的一个结点，则判别该结点有且仅有一个后继结点的条件是
______从二叉树的任一节点出发到根的路径上，所经过的节点序列必须按其关键字降序排列。
A．二叉排序树
B．大顶堆
C．小顶堆
D．平衡二又树
解析：n0是度为0的节点总数(即叶子节点数)，n1是度为l的节点总数，n2是度为2的节点总数，由二叉树的性质可知：n0=n2+1，则完全二叉树的节点总数n为：n=n0+n1+n2，由于完全二叉树中度为1的节点数只有两种可能0或1，由此可得n0=(n+1)/2或n0=nJ2，合并成一个公式为：n0=(n+1)/2(注：此处表示整除)，即可根据完全二又树的节点总数计算出叶子节点数。
下列关于哈夫曼树的叙述错误的是
A．一棵哈夫曼树是带权路径长度最短的二叉树
B．一棵哈夫曼树中叶结点的个数比非叶结点的个数大1
C．一棵哈夫曼树结点的度要么是0，要么是2
D．哈夫曼树的根结点的权值等于各个叶子结点的权值之和
解析：哈夫曼树中结点的度可以是0，1，2。
从二叉树的任一结点出发到根的路径上，所经过的结点序列必须按其关键字降序排列。
A．二叉排序树
B．大顶堆
C．小顶堆
D．平衡二叉树
解析：由堆的定义我们知道，当为小顶堆时，任意一棵子树的根结点比其左右子结点都要小，所以从任一结点出发到根的路径上，所经过的结点序列必须按其关键字降序排列。大根堆则具有完全相反的性质。很多考生对这个答案不是很理解，认为是二叉排序树。下面，我们根据二叉排序树的定义和性质推导错误结果。二叉排序树又称为二叉查找树，其定义为：二叉排序树或者是一棵空树，或者是具有如下性质(BST性质)的二叉树：(1)若它的左子树非空，则左子树上所有结点的值均小于根结点；(2)若它的右子树非空，则右子树上所有结点的值均大于根结点；(3)左、右子树本身又各是一棵二叉排序树。例如，如图4-2所示就是一棵二叉排序树。由图4-2可知，从二叉排序树的任一结点出发到根结点的路径上，所经过的结点序列不一定按其关键字降序排列或者升序排列。
从二叉树的任一节点出发到根的路径上，所经过的节点序列必按其关键字降序排列。
A．二叉排序树
B．大顶堆
C．小顶堆
D．平衡二叉树
解析：当堆为小顶堆时，任意一棵子树的根点比其左右子节点要小，所以从任意节点出发到根的路径上，所经过的节点序列必按其关键字降序排列。
若某二叉树中的所有结点值均大于其左子树上的所有结点值，且小于右子树上的所有结点值，则该二叉树遍历序列中有序的是（ ）。
A.前序序列
B.中序序列
C.后序序列
D.以上说法均可以
二叉树遍历可以分为3种：前序遍历(访问根结点在访问左子树和访问右子树之前)、中序遍历(访问根结点在访问左子树和访问右子树两者之间)、后序遍历(访问根结点在访问左子树和访问右子树之后)。由于结点值均大于其左子树上的所有结点值，且小于右子树上的所有结点值，那么只要遍历时访问根结点在访问左子树和右子树之间，遍历序列有序，即中序序列有序。故选B选项。