《西北工业大学21春《数据结构》离线作业2参考答案89》由会员分享，可在线阅读，更多相关《西北工业大学21春《数据结构》离线作业2参考答案89（11页珍藏版）》请在装配图网上搜索。
1、西北工业大学21春数据结构离线作业2参考答案1. 某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是( )。A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子参考答案：B2. 数据结构是带有结构的数据元素的集合。( )A.正确B.错误参考答案：A3. 已知完全二叉树T的第5层只有7个结点，则该树共有15个叶子结点。( )A、错误B、正确参考答案：A4. 哈希表不需要进行比较便可以直接取得所查记录。( )A.正确B.错误参考答案：A5. 下列四种排序中( )的空间复杂度最大。A.插入排序B.冒泡排序C.堆排序D.归并排序参考答案：C6. 程序一定是算法。(
2、 )A.正确B.错误参考答案：B7. 线性表的唯一存储形式就是链表。( )A.正确B.错误参考答案：A8. 在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是( )。A.O(1)B.O(n)C.O(n2)D.O(nlog2n)参考答案：B9. 设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为( )。A.21B.23C.41D.62参考答案：C10. 对长度为n的关键字序列进行堆排序的空间复杂度为( )。A.O(log2n)B.O(1)C.O
3、(n)D.O(n*log2n)参考答案：B11. 冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。( )A.正确B.错误参考答案：A12. 在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是堆排序。( )A、错误B、正确参考答案：A13. 若一个广义表的表头为空表，则此广义表亦为空表。( )A.正确B.错误参考答案：B14. 求图的最小(代价)生成树问题，考虑的是下面的哪一种图?( )A.有向图B.无向图C.带权的有向图D.带权的无向图参考答案：D15. 在队列中，允许进行删除操作的一端称为队尾。( )A、错误B、正确参考答案：B16. 一个加权的无向连通图的最小生
4、成树( )。A.有一颗或多颗B.只有一颗C.一定有多颗D.可能不存在参考答案：A17. 某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为( )。A.3B.2C.4D.5参考答案：C18. 若采用邻接矩阵法存储一个N个顶点的无向图，则该邻接矩阵是一个( )A.队头元素的前一个位置B.队头元素的后一个位置C.队头元素位置D.队尾元素的前一位置参考答案：A19. 任何一个无向连通图的最小生成树( )。A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在参考答案：B20. 允许对队列进行的操作有( )。A.对队列中的元素排序B.取出最近进队的元素C.在队头元
5、素之前插入元素D.删除队头元素参考答案：D21. 最小生成树问题是构造带权连通图(网)的最小代价生成树。( )A.正确B.错误参考答案：A22. 由带权为9，2，5，7的四个叶子结点构造一颗哈夫曼树，该树的带权路径长度为( )。A.23B.37C.46D.44参考答案：D23. 设某完全无向图中有n个顶点，则该完全无向图中有( )条边。A.n(n-1)/2B.n(n-1)C.n2D.n2-1参考答案：A24. 算法有以下几种特性( )。A、有穷性B、确定性C、可行性D、输入和输出参考答案：ABCD25. 一个关键字序列为46，79，56，38，40，84，采用快速排序以位于最左位置的元素为基准
6、而得到的第一次划分结果为( )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参考答案：C26. 若让元素1，2，3依次进栈，则出栈次序不可能出现种情况( )A.3，2，1B.2，1，3C.3，1，2D.1，3，2参考答案：C27. 在一个图中所有顶点的度数之和等于所有边数的( )倍。A.1/2B.2C.1D.4参考答案：B28. 若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是( )。A.1234B.4132C.4231D.4
7、213参考答案：C29. 邻接表法只能用于有向图存储。( )A.正确B.错误参考答案：B30. 两个串相等的充分必要条件是两个串的长度相等且字母相同。( )A、错误B、正确参考答案：B31. 一个具有767个结点的完全二叉树，其叶子结点个数为( )。A.383B.384C.385D.386参考答案：B32. 深度为k的二叉树至多有2k-1个结点。( )A、错误B、正确参考答案：A33. 在指定结点之后插入新结点时，双链表比单链表更方便。( )A.正确B.错误参考答案：B34. 删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。( )A、错误B、正确参考答案：A35. 对于顺
8、序存储的线性表，访问结点和增加、删除结点的时间复杂度为( )。A.O(n) O(n)B.O(n) O(1)C.O(1) O(n)D.O(1) O(1)参考答案：C36. 栈的插入和删除操作在( )进行。A.栈顶B.栈底C.任意位置D.指定位置参考答案：A37. 链式栈与顺序栈相比，一个比较明显的优点是( )A.插入操作更加方便B.通常不会出现栈满的情况C.不会出现栈空的情况D.删除操作更加方便参考答案：B38. 在二叉树中插入结点，则此二叉树便不再是二叉树了。( )A.正确B.错误参考答案：B39. 顺序存储结构是通过( )表示元素之间的关系的;链式存储结构是通过( )表示元素之间的关系的。A
9、.物理上相邻，指针B.逻辑上相邻，指针C.逻辑上相临，结点D.物理上相邻，结点参考答案：A40. 数据的存储结构是数据的逻辑结构在计算机存储器上的实现，它是依赖于计算机的。( )A.正确B.错误参考答案：A41. 深度为h的满m叉树的第k层的结点(1=A.mk-1B.mk-1C.mh-1D.mh-1参考答案：A42. 内部排序是根据关键词的大小重新安排各( )的顺序。A.关键词B.数据项C.文件D.数据元素参考答案：B43. 产生冲突现象的两个关键字称为该散列函数的同义字。( )A、错误B、正确参考答案：B44. 下面哪些方法可以判断出一个有向图是否有环(回路)?( )A.求最短路径B.求关键
10、路径C.拓扑排序D.广(宽)度优先遍历参考答案：C45. 若用n表示图中顶点数目，则有( )条边的无向图成为完全图。A.nB.n-1C.n(n-1)2D.n(n+1)2参考答案：C46. 不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。( )A.正确B.错误参考答案：A47. 若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是( )。A.10B.11C.12D.15参考答案：A48. 一个队列的入队序列是1、2、3、4，则队列的首次输出元素是( )。A.1B.2C.3D.4参考答案：A49. 数据的逻辑结构是指各数据元素之间的逻辑关系。( )A.正确B.错误参考答案：A50. 在一个单链表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参考答案：D
西北工业大学21春《数据结构》离线作业2参考答案89
