西北工业大学22春《数据结构》离线作业1答案参考86

西北工业大学22春数据结构离线作业1答案参考1. 两个串相等的充分必要条件是两个串的长度相等且字母相同。( )A、错误B、正确参考答案：B2. 链接存储结构属动态存储方式。( )A.正确B.错误参考答案：A3. 若一个有向图的邻接距阵中，主对角线以下的元素均为零，则该图的拓扑有序序列( )。A.一定存在B.一定不存在C.不一定存在D.不确定参考答案：A4. 通常将链串的结点大小设置为大于1是为了( )。A、提高串匹配效率B、提高存储密度C、便于插入操作D、便于删除操作参考答案：A5. 求图的最小(代价)生成树问题，考虑的是下面的哪一种图?( )A.有向图B.无向图C.带权的有向图D.带权的无向图参考答案：D6. 二叉排序树上左子树上所有结点的值均小于它的根结点的值。( )A.正确B.错误参考答案：A7. 一棵含999个结点的完全二叉树的深度为12。( )A、错误B、正确参考答案：A8. 已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为( )。A、q-next=s-next; s-next=pB、s-next=p; q-next=s-nextC、p-next=s-next; s-next=qD、s-next=q; p-next=s-next参考答案：A9. 假设三维数组A1098按行优先顺序存储，若每个元素占3个存储单元，且首地址为100，则元素A987的存储地址是501。( )A、错误B、正确参考答案：A10. 队列允许在队尾删除，在队头插入。( )A.正确B.错误参考答案：A11. 抽象数据类型是指数据逻辑结构及与之相关的操作。( )A、错误B、正确参考答案：B12. 快速排序是排序算法中平均性能最好的一种排序。( )A.正确B.错误参考答案：A13. 用有向无环图描述表达式(A+B)*(A+B)/A)，至少需要顶点的数目为( )。A.5B.6C.8D.9参考答案：A14. 设某完全无向图中有n个顶点，则该完全无向图中有( )条边。A.n(n-1)/2B.n(n-1)C.n2D.n2-1参考答案：A15. 下列陈述中正确的是( )。A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树中必有度为2的结点D.二叉树中最多只有两棵子树，并且有左右之分参考答案：D16. 不含任何字符的串称为空串。( )A、错误B、正确参考答案：B17. 采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为( )。A.n/2B.nC.(n-1)/2D.(n+1)/2参考答案：D18. 由于排序过程中涉及的存储器不同，可以将排序方法分为( )。A、稳定排序B、不稳定排序C、内部排序D、外部排序参考答案：CD19. 一个栈的入栈序列是abcde，则栈的不可能的输出序列是( )。A.edcbaB.decbaC.dceabD.abcde参考答案：C20. 对于哈希函数H(key)=key%13，被称为同义词的关键字是( )。A、35和41B、23和39C、15和44D、25和51参考答案：D21. 设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行( )趟的分配和回收才能使得初始关键字序列变成有序序列。A.3B.4C.5D.8参考答案：A22. 按照二叉树的定义，具有3个结点的二叉树有( )种。A.3B.4C.5D.6参考答案：C23. 线性表的唯一存储形式就是链表。( )A.正确B.错误参考答案：A24. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为( )。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参考答案：B25. 深度为k的二叉树至多有2k-1个结点。( )A、错误B、正确参考答案：A26. 向顺序栈中压入新元素时，应当( )A.先移动栈顶位置，再存入元素B.先存入元素，再移动栈顶位置C.先后 次序无关紧要D.同时进行参考答案：A27. 如果最常用的操作是取第i个结点及其前驱，则采用( )存储方式最节省时间。A.单链表B.双链表C.单循环链表D.顺序表参考答案：D28. 若哈希表(散列表)的负载因子l，则可避免冲突的产生。( )A.正确B.错误参考答案：B29. 具有65个结点的完全二叉树其深度为(根的层次号为1)( )。A.8B.7C.6D.5参考答案：B30. 对长度为n的关键字序列进行堆排序的空间复杂度为( )。A.O(log2n)B.O(1)C.O(n)D.O(n*log2n)参考答案：B31. 二叉树中除叶结点外，任一结点X，其左子树根结点的值小于该结点X的值;其右子树根结点的值大于等于该结点X的值，则此二叉树一定是二叉排序树。( )A.正确B.错误参考答案：B32. 一棵树可以只有1个结点。( )A、错误B、正确参考答案：B33. 设某算法的问题规模函数f(n)=300n2+8000n+900，则它的渐进时间复杂度为( )A.O(n3)B.O(n2)C.O(n)D.O(1)参考答案：B34. 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。( )A.正确B.错误参考答案：A35. 分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。( )A.正确B.错误参考答案：A36. 已知完全二叉树T的第5层只有7个结点，则该树共有15个叶子结点。( )A、错误B、正确参考答案：A37. 平衡二叉树的平衡因子只可能是-1、0、1。( )A.正确B.错误参考答案：A38. 对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。( )A、错误B、正确参考答案：B39. 深度为5的二叉树至多有( )个结点。A.16B.32C.31D.10参考答案：C40. 连通网的最小生成树是其所有生成树中( )。A.顶点集最小的生成树B.边集最小的生成树C.顶点权值之和最小的生成树D.边的权值之和最小的生成树参考答案：D41. 基数排序需要进行关键字的比较。( )A.正确B.错误参考答案：B42. 对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的左孩子的编号为98。( )A、错误B、正确参考答案：B43. 栈和队列都是限制存取点的线性结构。( )A.正确B.错误参考答案：A44. 若一棵满三叉树中含有121个结点，则该树的深度为6。( )A、错误B、正确参考答案：A45. 在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是( )。A.O(1)B.O(n)C.O(n2)D.O(nlog2n)参考答案：B46. 若一个广义表的表头为空表，则此广义表亦为空表。( )A.正确B.错误参考答案：B47. 假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的所有弧的时间复杂度是( )A.O(n)B.O(e)C.O(n+e)D.O(n*e)参考答案：C48. 有关二叉树下列说法正确的是( )。A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为2参考答案：B49. 哈希表不需要进行比较便可以直接取得所查记录。( )A.正确B.错误参考答案：A50. 已知循环队列的存储空间为数组data21，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为( )。A.5B.6C.16D.17参考答案：C