《西北工业大学21秋《数据结构》在线作业二答案参考65》由会员分享，可在线阅读，更多相关《西北工业大学21秋《数据结构》在线作业二答案参考65（13页珍藏版）》请在金锄头文库上搜索。
1、西北工业大学21秋数据结构在线作业二答案参考1. 用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。A.逆拓扑有序B.拓扑有序C.无序的D.A和B参考答案：A2. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是( )。A.0B.1C.2D.3参考答案：B3. 一棵左右子树均不空的二叉树在前序线索化后，其中空的链域的个数是( )。A.不确定B.2C.1D.0参考答案：C4. 抽象数据类型是指数据逻辑结构及与之相关的操作。( )A、错误B、正确参考答案：B5. 程序一定是算法。( )A.正确B.错误参考答案：B6. 设顺序存储的线性表共有
2、123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为( )。A.21B.23C.41D.62参考答案：C7. 向一个有127个元素原顺序表中插入一个新元素并保存原来顺序不变，平均要移动( )个元素。A.8B.63.5C.63D.7参考答案：B8. 数据元素及其关系在计算机存储器内的表示，称为数据的( )。A.逻辑结构B.存储结构C.线性结构D.非线性结构参考答案：B9. 若哈希表(散列表)的负载因子l，则可避免冲突的产生。( )A.正确B.错误参考答案：B10. 高度为5的完全二叉树中含有
3、的结点数至少为( )。A、16B、17C、31D、32参考答案：A11. 算法分析的两个主要方面是( )。A.空间复杂度和时间复杂度B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性参考答案：A12. 非空的双向循环链表中任何结点的前驱指针均不为空。( )A.正确B.错误参考答案：A13. 数据结构中所定义的数据元素，是用于表示数据的( )。A.最小单位B.最大单位C.基本单位D.不可分割的单位参考答案：C14. 算法有以下几种特性( )。A、有穷性B、确定性C、可行性D、输入和输出参考答案：ABCD15. 具有n个结点的连通图至少有( )条边。A.n-1B.nC.n(n-1)/2
4、D.2n参考答案：A16. 一棵含999个结点的完全二叉树的深度为12。( )A、错误B、正确参考答案：A17. 下列说法中，不正确的是( )。A.数据元素是数据的基本单位B.数据项是数据中不可分割的最小可标识单位C.数据可由若干个数据元素构成D.数据项可由若干个数据元素构成参考答案：D18. 哈希表不需要进行比较便可以直接取得所查记录。( )A.正确B.错误参考答案：A19. 一个有向无环图的拓扑排序序列是( )。A.一定唯一的B.一定不唯一的C.不一定唯一的D.都不对参考答案：C20. 对无序表用折半查找比顺序查找快。( )A.正确B.错误参考答案：B21. 在二叉树中插入结点，则此二叉树
5、便不再是二叉树了。( )A.正确B.错误参考答案：B22. 若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是( )。A.10B.11C.12D.15参考答案：A23. 一个有向图的邻接表和逆邻接表中结点的个数可能不等。( )A.正确B.错误参考答案：B24. 设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有( )条有向边。A.nB.n-1C.mD.m-1参考答案：C25. 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是( )。A.nB.2n-1C.2nD.n-1参考答案：A26. 结构就是用户定义的，( )的一个集合体。参考答案：不同数据类型27. 取顺序
6、表的第i个元素的时间与i的大小无关。( )A.正确B.错误参考答案：A28. 数据结构是带有结构的数据元素的集合。( )A.正确B.错误参考答案：A29. 深度为15的满二叉树上，第11层有211个结点。( )A、错误B、正确参考答案：A30. 在长度为n的顺序表的第i(1in+1)个位置上插入一个元素，元素的移动次数为( )。A、n-i+1B、n-iC、iD、i-1参考答案：A31. 若有18个元素的有序表存放在一堆数组A19中，第一个元素放A1中，现进行二分查找，则查找A3的比较序列的下标依次为( )。A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，3参考答案：D32. 栈是
7、一种操作受限的线性结构，其操作的主要特征是( )。A、先进先出B、后进先出C、进优于出D、出优于进参考答案：B33. 队列允许在队尾删除，在队头插入。( )A.正确B.错误参考答案：A34. 用ISAM组织文件适合于( )。A.磁盘B.磁带C.外存储器D.光盘参考答案：A35. 在下列排序算法中，哪一个算法的时间复杂度与记录初始排列无关?( )A.直接选择排序B.直接插入排序C.快速排序D.冒泡排序参考答案：A36. 后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。( )A.正确B.错误参考答案：A37. 在关键字序列(12，23，34，45，56，67，78，89，91)中二分查找关
8、键字为45、89和12的结点时，所需进行的比较次数分别为( )。A.4，4，3B.4，3，3C.3，4，4D.3，3，4参考答案：B38. 在含100个结点的完全二叉树中，叶子结点的个数为36。( )A、错误B、正确参考答案：A39. 用有向无环图描述表达式(A+B)*(A+B)/A)，至少需要顶点的数目为( )。A.5B.6C.8D.9参考答案：A40. 设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有( )个空指针域。A.2m-1B.2mC.2m+1D.4m参考答案：B41. 二叉树是度为2的有序树。( )A、错误B、正确参考答案：A42. 依次在初始为空的队
9、列中插入元素X，Y，Z，W以后，紧接着作了两次删除操作，此时的队头元素是( )A.XB.YC.ZD.W参考答案：C43. 一个具有4个顶点的无向完全图有6条边。( )A、错误B、正确参考答案：B44. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为( )。A.O(n) O(n)B.O(n) O(1)C.O(1) O(n)D.O(1) O(1)参考答案：C45. 算法分析的目的是( )。A、辨别数据结构的合理性B、评价算法的效率C、研究算法中输入与输出的关系D、鉴别算法的可读性参考答案：B46. 求图的最小(代价)生成树问题，考虑的是下面的哪一种图?( )A.有向图B.无向图C.带
10、权的有向图D.带权的无向图参考答案：D47. 一个好的算法有( )设计要求。A、正确性B、可读性C、健壮性D、效率与低存储量要求参考答案：ABCD48. AVL树是一种平衡的二叉排序树，树中任一结点的( )A.左、右子树的高度均相同B.左、右子树高度差的绝对值不超过1C.左子树的高度均大于右子树的高度D.左子树的高度均小于右子树的高度参考答案：B49. 在对链队列作出队操作时，不会改变front指针的值。( )A、错误B、正确参考答案：A50. 抽象数据类型的三个组成部分分别为( )。A、数据对象、数据关系和基本操作B、数据元素、逻辑结构和存储结构C、数据项、数据元素和数据类型D、数据元素、数
11、据结构和数据类型参考答案：A51. 已知一个散列表如图所示，其散列函数为H(key)=key%11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为( )。A.2B.3C.8D.9参考答案：C52. 指针p所指的元素是双向循环链表L的尾元素的条件是( )。A.p=LB.p=NULLC.p-prior=LD.p-next=L参考答案：D53. 一个关键字序列为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
12、，56，79，40，84参考答案：C54. 中序遍历的递归算法平均空间复杂度为( )。A.2(n)B.n(2)C.0(n)D.2n参考答案：C55. 一棵树可以只有1个结点。( )A、错误B、正确参考答案：B56. B+树应用在( )文件系统中。A.顺序B.散列C.VSAMD.ISAM参考答案：C57. 已知完全二叉树T的第5层只有7个结点，则该树共有15个叶子结点。( )A、错误B、正确参考答案：A58. 设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有( )A.n-1B.nC.n+1D.n+2参考答案：B59. 在无向图中，若从顶点a到顶点b存在通路，则称a与b之间是连通的。( )A、错误B、正确参考答案：B60. 有关二叉树下列说法正确的是( )。A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为2参考答案：B
