《西北工业大学21秋《数据结构》在线作业三答案参考12》由会员分享，可在线阅读，更多相关《西北工业大学21秋《数据结构》在线作业三答案参考12（13页珍藏版）》请在金锄头文库上搜索。
1、西北工业大学21秋数据结构在线作业三答案参考1. 若有18个元素的有序表存放在一堆数组A19中，第一个元素放A1中，现进行二分查找，则查找A3的比较序列的下标依次为( )。A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，3参考答案：D2. 二叉树中除叶结点外，任一结点X，其左子树根结点的值小于该结点X的值;其右子树根结点的值大于等于该结点X的值，则此二叉树一定是二叉排序树。( )A.正确B.错误参考答案：B3. 在长度为n的顺表表的第i个位置上插入一个元素(1in+1)，元素的移动次数为( )。A.n-i+1B.n-iC.iD.i-1参考答案：C4. 在线性表的下列运算中，不改变
2、数据元素之间结构关系的运算是( )。A、插入B、删除C、排序D、定位参考答案：D5. 连通网的最小生成树是其所有生成树中( )。A.顶点集最小的生成树B.边集最小的生成树C.顶点权值之和最小的生成树D.边的权值之和最小的生成树参考答案：D6. 已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为k。( )A、错误B、正确参考答案：A7. 数据的存储结构是数据的逻辑结构在计算机存储器上的实现，它是依赖于计算机的。( )A.正确B.错误参考答案：A8. 可以用队列实现数值转换算法。( )A.正确B.错误参考答案：A9. 两个串相等的充分必要条件是两个
3、串的长度相等且字母相同。( )A、错误B、正确参考答案：B10. 链接存储结构属动态存储方式。( )A.正确B.错误参考答案：A11. 含n个顶点的无向连通图中至少含有n条边。( )A、错误B、正确参考答案：A12. 取顺序表的第i个元素的时间与i的大小无关。( )A.正确B.错误参考答案：A13. 结构的存储密度定义为数据本身所占的存储量与整个结构所占的存储量之比。( )A.正确B.错误参考答案：A14. AVL树是一种平衡的二叉排序树，树中任一结点的( )A.左、右子树的高度均相同B.左、右子树高度差的绝对值不超过1C.左子树的高度均大于右子树的高度D.左子树的高度均小于右子树的高度参考答
4、案：B15. 设根结点层次为1，某二叉树的结点前序序列和后序序列正好相反，则该二叉树一定是( )。A.高度等于其结点数B.空或只有一个结点C.任一结点无左子女D.任一结点无右子女参考答案：A16. 一个有向图的邻接表和逆邻接表中结点的个数可能不等。( )A.正确B.错误参考答案：B17. 平衡二叉树的平衡因子只可能是-1、0、1。( )A.正确B.错误参考答案：A18. 右图中的拓扑序列为( )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参考答案：D19. 有向图
5、用邻接矩阵表示后，顶点i的入度等于邻接矩阵中第i列的元素个数。( )A、错误B、正确参考答案：B20. 栈下溢是指在栈空时进行出栈操作。( )A、错误B、正确参考答案：B21. 对于双向链表，在两个结点之间插入一个新结点需修改的指针共( )个，单链表为( )个。A.4，1B.4，2C.1，4D.2，4参考答案：B22. 具有n个结点的连通图至少有( )条边。A.n-1B.nC.n(n-1)/2D.2n参考答案：A23. 与单链表相比，双链表的优点之一是( )。A.插入、删除操作更简单B.可以进行随机访问C.可以省略表头指针或表尾指针D.顺序访问相邻结点更灵活参考答案：C24. 以下( )不是队
6、列的基本运算。A.从队尾插入一个新元素B.从队列中删除第i个元素C.判断一个队列是否为空D.读取队头元素的值参考答案：B25. 队列的修改是按照先进先出的原则进行的。( )A、错误B、正确参考答案：B26. 无向图的邻接矩阵可用一维数组存储。( )A.正确B.错误参考答案：A27. 设串sl=DataStructureswithJava，s2=it，则子串定位函数index(s1,s2)的值为( )A.15B.16C.17D.18参考答案：D28. 下列陈述中正确的是( )。A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树中必有度为2的结点D.二叉树中最多只有两棵子
7、树，并且有左右之分参考答案：D29. 若进栈序列为a，b，c，则通过入出栈操作可能得到的a，b，c的不同排列个数为( )。A、4B、5C、6D、7参考答案：B30. 对于线性表(7，34，55，25，64，46，20，10)进行散列存储时，若选用H(K)=K%9作为散列函数，则散列地址为1的元素有( )个。A.1B.2C.3D.4参考答案：D31. 哈希表不需要进行比较便可以直接取得所查记录。( )A.正确B.错误参考答案：A32. 如果入栈序列是1，3，5，97，99，且出栈序列的第一个元素为99，则出栈序列中第30个元素为47。( )A、错误B、正确参考答案：B33. 下列四种排序中( )
8、的空间复杂度最大。A.插入排序B.冒泡排序C.堆排序D.归并排序参考答案：C34. 给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。( )A、错误B、正确参考答案：A35. 具有65个结点的完全二叉树其深度为(根的层次号为1)( )。A.8B.7C.6D.5参考答案：B36. 在含100个结点的完全二叉树中，叶子结点的个数为36。( )A、错误B、正确参考答案：A37. 深度为k的二叉树至多有2k-1个结点。( )A、错误B、正确参考答案：A38. 若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。A.(n-1)2B
9、.n2C.(n+1)2D.n参考答案：C39. 线性表的链接实现有利于( )运算。A.插入B.读表元C.查找D.定位参考答案：A40. 广义表运算式tail(a，b)，(c，d)的操作结果是( )。A.dB.c，dC.(c，d)D.(c，d)参考答案：D41. 抽象数据类型的三个组成部分分别为( )。A、数据对象、数据关系和基本操作B、数据元素、逻辑结构和存储结构C、数据项、数据元素和数据类型D、数据元素、数据结构和数据类型参考答案：A42. 先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。( )A.正确B.错误参考答案：A43. 下列存储表示中，哪一个不是树的存储形式( )。A.双亲
10、表示法B.孩子链表表示法C.顺序存储表示法D.孩子兄弟表示法参考答案：C44. 求图的最小(代价)生成树问题，考虑的是下面的哪一种图?( )A.有向图B.无向图C.带权的有向图D.带权的无向图参考答案：D45. 在一个长度为100的顺序表中删除第10个元素时，需移动90个元素。( )A、错误B、正确参考答案：B46. 对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )。A.顺序表B.用头指针表示的循环单链表C.用尾指针表示的循环单链表D.单链表参考答案：C47. 在k叉树中，无父母的结点称为( )。A.祖先B.根C.子孙D.叶参考答案：B48. 某二叉树的先序序列和后序序列正
11、好相反，则该二叉树的特点一定是( )。A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子参考答案：B49. 设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有( )条有向边。A.nB.n-1C.mD.m-1参考答案：C50. 顺序存储结构是通过( )表示元素之间的关系的;链式存储结构是通过( )表示元素之间的关系的。A.物理上相邻，指针B.逻辑上相邻，指针C.逻辑上相临，结点D.物理上相邻，结点参考答案：A51. 下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。A.选择B.冒泡C.归并D.堆参考答案：C52. 允许对队列进行的操作
12、有( )。A.对队列中的元素排序B.取出最近进队的元素C.在队头元素之前插入元素D.删除队头元素参考答案：D53. 结构就是用户定义的，( )的一个集合体。参考答案：不同数据类型54. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是( )。A.6B.4C.3D.2参考答案：C55. 最小生成树问题是构造带权连通图(网)的最小代价生成树。( )A.正确B.错误参考答案：A56. 按照二叉树的定义，具有3个结点的二叉树有( )种。A.3B.4C.5D.6参考答
13、案：C57. 依次在初始为空的队列中插入元素X，Y，Z，W以后，紧接着作了两次删除操作，此时的队头元素是( )A.XB.YC.ZD.W参考答案：C58. 一个具有4个顶点的无向完全图有6条边。( )A、错误B、正确参考答案：B59. 下列描述中正确的是( )。A.选择合适的数据结构是解决应用问题的关键步骤B.线性表的逻辑顺序与存储顺序总是一致的C.每种数据结构都具备查找、插入和删除三种基本运算D.数据结构实质上包括逻辑结构和存储结构两方面的内容参考答案：A60. 分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。( )A.正确B.错误参考答案：A
