《西北工业大学21秋《数据结构》在线作业三满分答案33》由会员分享，可在线阅读，更多相关《西北工业大学21秋《数据结构》在线作业三满分答案33（13页珍藏版）》请在金锄头文库上搜索。
1、西北工业大学21秋数据结构在线作业三满分答案1. 归并排序的辅助存储空间代价为O(1)。( )A.正确B.错误参考答案：B2. 已知一个散列表如图所示，其散列函数为H(key)=key%11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为( )。A.2B.3C.8D.9参考答案：C3. 在线性表的下列运算中，不改变数据元素之间结构关系的运算是( )。A、插入B、删除C、排序D、定位参考答案：D4. 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是( )。A.希尔排序B.快速排序C.插入排序D.选择排序参考答案：D5. 二叉树中结点只有一个孩子时无左右之分。( )A、错误
2、B、正确参考答案：A6. 如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为( )。A.插入排序B.归并排序C.冒泡排序D.堆排序参考答案：A7. 假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的所有弧的时间复杂度是( )A.O(n)B.O(e)C.O(n+e)D.O(n*e)参考答案：C8. 若要在单链表中的结点p之后插入一个结点s，则应执行的语句是( )。A.s-next=p-next; p-next=sB.p-next=s; s-next=p-nextC.p-next=s-next; s-next=pD.
3、s-next=p; p-next=s-next参考答案：A9. 在一个长度为n的循环链表中，删除其元素值为x的结点的时间复杂度为O(n)。( )A、错误B、正确参考答案：B10. 某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是( )。A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子参考答案：B11. 如果某种排序算法是不稳定的，则这种算法不可用。( )A.正确B.错误参考答案：A12. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为( )。A.O(n) O(n)B.O(n) O(1)C.O(1) O(n)D.O(1) O(1)参考答案
4、：C13. 结构的存储密度定义为数据本身所占的存储量与整个结构所占的存储量之比。( )A.正确B.错误参考答案：A14. 栈的插入和删除操作在( )进行。A.栈顶B.栈底C.任意位置D.指定位置参考答案：A15. 由带权为9，2，5，7的四个叶子结点构造一颗哈夫曼树，该树的带权路径长度为( )。A.23B.37C.46D.44参考答案：D16. 采用分快查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分( )个结点最佳。A.10B.25C.6D.625参考答案：B17. 四个元素进入队列QU的顺序是U、V、X、Y，进行DeQueue(QU
5、，x)操作后，队头元素是( )。A.YB.XC.VD.U参考答案：C18. 一个关键字序列为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，56，79，40，84参考答案：C19. 下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。A.选择B.冒泡C.归并D.堆参考答案：C20. 将一个A1.100，1.100的三对角矩阵，按行优先次序存入一维数组B1.298中，A中元素A66，65在数
6、组B中的位置K为( )。A.199B.197C.195D.193参考答案：C21. 指针p所指的元素是双向循环链表L的尾元素的条件是( )。A.p=LB.p=NULLC.p-prior=LD.p-next=L参考答案：D22. 在指定结点之后插入新结点时，双链表比单链表更方便。( )A.正确B.错误参考答案：B23. 下列陈述中正确的是( )。A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树中必有度为2的结点D.二叉树中最多只有两棵子树，并且有左右之分参考答案：D24. 二叉树中的叶子结点就是二叉树中没有左右子树的结点。( )A、错误B、正确参考答案：B25. 已知
7、含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于( )。A.1.0B.2.9C.3.4D.5.5参考答案：B26. 下列四种排序中( )的空间复杂度最大。A.插入排序B.冒泡排序C.堆排序D.归并排序参考答案：C27. 下列四种基本的逻辑结构中，数据元素之间关系最弱的是( )。A.集合B.线性结构C.树形结构D.图状结构参考答案：A28. 与单链表相比，双链表的优点之一是( )。A.插入、删除操作更简单B.可以进行随机访问C.可以省略表头指针或表尾指针D.顺序访问相邻结点更灵活参考答案：C29. 用有向无环图描述表达式(A+B)*(A+B)/A)
8、，至少需要顶点的数目为( )。A.5B.6C.8D.9参考答案：A30. 将森树转成二叉树，根结点没有右子树。( )A.正确B.错误参考答案：B31. 稀疏矩阵常用的压缩存储方法有两种，它们是( )。A.散列和十字链表B.二维数组和三维数组C.三元组和散列D.三元组和十字链表参考答案：D32. 在关键字序列(12，23，34，45，56，67，78，89，91)中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为( )。A.4，4，3B.4，3，3C.3，4，4D.3，3，4参考答案：B33. 下面哪些方法可以判断出一个有向图是否有环(回路)?( )A.求最短路径B.求关键路径
9、C.拓扑排序D.广(宽)度优先遍历参考答案：C34. 在队列中，允许进行删除操作的一端称为队尾。( )A、错误B、正确参考答案：B35. 数据的存储结构是数据的逻辑结构在计算机存储器上的实现，它是依赖于计算机的。( )A.正确B.错误参考答案：A36. AVL树是一种平衡的二叉排序树，树中任一结点的( )A.左、右子树的高度均相同B.左、右子树高度差的绝对值不超过1C.左子树的高度均大于右子树的高度D.左子树的高度均小于右子树的高度参考答案：B37. 不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。( )A.正确B.错误参考答案：A38. 数据项是数据的基本单位。( )A
10、.正确B.错误参考答案：A39. 队列允许在队尾删除，在队头插入。( )A.正确B.错误参考答案：A40. 对某二叉树进行前序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果为( )A.DBFEACB.DFEBCAC.BDFECAD.BDEFAC参考答案：B41. 在文本编辑程序中查找某一特定单词在文本中出现的位置，可以利用串的定位操作。( )A、错误B、正确参考答案：B42. 在链表的结点中，数据元素所占的存储量和整个结点所占的存储量之比称作存储密度。( )A、错误B、正确参考答案：B43. 若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的( )。A.
11、层次遍历算法B.前序遍历算法C.中序遍历算法D.后序遍历算法参考答案：C44. 删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。( )A、错误B、正确参考答案：A45. 判断线索二叉树中某结点p有右子女的条件是( )。A.p-rtag=1B.p-rtag=0C.p-lchild!=NULLD.p!=NULL参考答案：B46. 若进栈序列为a，b，c，则通过入出栈操作可能得到的a，b，c的不同排列个数为( )。A、4B、5C、6D、7参考答案：B47. 下列关于数据结构基本概念的叙述中，正确的是( )。A.数据的逻辑结构分为表结构和树结构B.数据的存储结构分为线性结构和非线
12、性结构C.数据元素是数据的基本单位D.结点是有独立含义的数据最小单位参考答案：C48. 结构就是用户定义的，( )的一个集合体。参考答案：不同数据类型49. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是( )。A.6B.4C.3D.2参考答案：C50. 设有一个10阶的对称矩阵A1010，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组BA00存入B0中，则A85在B中( )A.32B.33C.41D.65参考答案：C51. 内部排序是根据关键词
13、的大小重新安排各( )的顺序。A.关键词B.数据项C.文件D.数据元素参考答案：B52. 在一个图中所有顶点的度数之和等于所有边数的( )倍。A.1/2B.2C.1D.4参考答案：B53. 若一棵满三叉树中含有121个结点，则该树的深度为6。( )A、错误B、正确参考答案：A54. 一个具有767个结点的完全二叉树，其叶子结点个数为( )。A.383B.384C.385D.386参考答案：B55. 设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为( )A.O(nlog2e)B.O(n+e)C.O(ne)D.O(n2)参考答案：B56. 数据结构中的任一数据元素至多只有一个前驱和一个后继，该数据结构是( )。A.线性表B.树形结构C.广义表D.图结构参考答案：A
