《西北工业大学21秋《数据结构》在线作业一答案参考61》由会员分享，可在线阅读，更多相关《西北工业大学21秋《数据结构》在线作业一答案参考61（14页珍藏版）》请在金锄头文库上搜索。
1、西北工业大学21秋数据结构在线作业一答案参考1. 高度为5的完全二叉树中含有的结点数至少为( )。A、16B、17C、31D、32参考答案：A2. 设根结点层次为1，某二叉树的结点前序序列和后序序列正好相反，则该二叉树一定是( )。A.高度等于其结点数B.空或只有一个结点C.任一结点无左子女D.任一结点无右子女参考答案：A3. 链式队列Q为空的判定条件：( )A.Q.front=Q.rearB.Q.front=QC.Q=Q.rearD.没有正确参考答案：A4. 若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是( )。A.10B.11C.12D.15参考答案：A5. 对线性表进行折半
2、查找时，要求线性表必须( )。A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且结点按关键字有序排序D.以链接方式存储，且结点按关键字有序排序参考答案：C6. 如果要求一个线性表既能较快地查找、又能适应动态变化的要求，则可采用的查找方法是( )。A.顺序查找B.折半查找C.基于属性的查找D.分块查找参考答案：D7. 一个有向无环图的拓扑排序序列( )是唯一的。A.可能B.不一定C.三者均不对D.一定参考答案：B8. 对长度为n的关键字序列进行堆排序的空间复杂度为( )。A.O(log2n)B.O(1)C.O(n)D.O(n*log2n)参考答案：B9. 对于双向链表，在两个结点之间插入
3、一个新结点需修改的指针共( )个，单链表为( )个。A.4，1B.4，2C.1，4D.2，4参考答案：B10. 由于排序过程中涉及的存储器不同，可以将排序方法分为( )。A、稳定排序B、不稳定排序C、内部排序D、外部排序参考答案：CD11. 若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是( )。A.1234B.4132C.4231D.4213参考答案：C12. 若进栈序列为a，b，c，则通过入出栈操作可能得到的a，b，c的不同排列个数为( )。A、4B、5C、6D、7参考答案：B13. 依次在初始为空的队列中插入元素X，Y，Z，
4、W以后，紧接着作了两次删除操作，此时的队头元素是( )A.XB.YC.ZD.W参考答案：C14. 按排序过程中依据的原则分类，快速排序属于( )。A.插入类的排序方法B.选择类的排序方法C.交换类的排序方法D.归并类的排序方法参考答案：C15. AVL树是一种平衡的二叉排序树，树中任一结点的( )A.左、右子树的高度均相同B.左、右子树高度差的绝对值不超过1C.左子树的高度均大于右子树的高度D.左子树的高度均小于右子树的高度参考答案：B16. 在单链表中设置头结点的作用是( )。A.主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表
5、指针不变B.便于查找C.便于连接D.快速插入记录参考答案：A17. 一个加权的无向连通图的最小生成树( )。A.有一颗或多颗B.只有一颗C.一定有多颗D.可能不存在参考答案：A18. 含n个顶点的无向连通图中至少含有n条边。( )A、错误B、正确参考答案：A19. 对5个不同的数据元素进行直接插入排序，最多需要进行( )次比较A.8B.10C.15D.25参考答案：B20. 循环队列SQ采用数组空间SQ.base0，n-1存储其元素值，已知其头尾指针分别是front和rezr，则判断此循环队列Q为满队列的条件是( )。A.Q.front=Q.rearB.Q.rear!=Q.frontC.Q.f
6、ront=(Q.rear+1)%nD.Q.front!=(Q.rear+1)%n参考答案：C21. 下列四种排序中( )的空间复杂度最大。A.插入排序B.冒泡排序C.堆排序D.归并排序参考答案：C22. 假设三维数组A1098按行优先顺序存储，若每个元素占3个存储单元，且首地址为100，则元素A987的存储地址是501。( )A、错误B、正确参考答案：A23. 归并排序是一种稳定的排序方法。( )A.正确B.错误参考答案：A24. 在链队列中，假设f和r分别为队首和队尾指针，则删除一个结点的操作是( )。A.r=r-nextB.r=f-nextC.f=r-nextD.f=f-next参考答案：
7、D25. 一个队列的入队序列是a、b、c、d，则队列的输出序列是( )。A.dcbaB.cbdaC.adcbD.abcd参考答案：D26. 数据的逻辑结构是指数据的各数据项之间的逻辑关系。( )A.正确B.错误参考答案：B27. 字符串“sgabacbadfgbacst”中存在有6个与字符串“ba”相同的子串。( )A、错误B、正确参考答案：A28. 数据的逻辑结构描述数据元素之间的逻辑关系，与存储方式无关。( )A、错误B、正确参考答案：B29. 对于哈希函数H(key)=key%13，被称为同义词的关键字是( )。A、35和41B、23和39C、15和44D、25和51参考答案：D30.
8、以下( )不是队列的基本运算。A.从队尾插入一个新元素B.从队列中删除第i个元素C.判断一个队列是否为空D.读取队头元素的值参考答案：B31. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是( )。A.(rear+1)%n=frontB.rear=frontC.rear+1=frontD.(rear-l)%n=front参考答案：B32. 已知循环队列的存储空间为数组data21，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为( )。A.5B.6C.16D.17参考答案：C33. 任何一个递归过程都可以转换成非递归过程。( )A.正确B.错误参考
9、答案：A34. 若已知一个栈序列是1，2，3，.，n，其输出序列为p1，p2，p3，.，pn，若p1=n，则pi为( )。A.iB.n-iC.n-i+1D.不确定参考答案：C35. 在一个图中所有顶点的度数之和等于所有边数的( )倍。A.1/2B.2C.1D.4参考答案：B36. 由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多。( )A、错误B、正确参考答案：A37. 一个好的算法有( )设计要求。A、正确性B、可读性C、健壮性D、效率与低存储量要求参考答案：ABCD38. 为使平均查找长度达到最小，当由关键字集合05，11，21，25，37，40，41，62，8
10、4构建二叉排序树时，第一个插入的关键字应为( )。A.5B.37C.41D.62参考答案：B39. 设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为( )。A.21B.23C.41D.62参考答案：C40. 在数据结构中，数据的逻辑结构可以分成( )。A、内部结构和外部结构B、线性结构和非线性结构C、紧凑结构和非紧揍结构D、动态结构和静态结构参考答案：C41. 队列的插入操作是在( )。A.队尾B.队头C.队列任意位置D.队头元素后参考答案：A42. 数据的逻辑结
11、构在计算机存储器内的表示，称为数据的逻辑结构。( )A、错误B、正确参考答案：A43. 在二叉树的第i层上至多可以有2i个结点。( )A、错误B、正确参考答案：A44. 删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。( )A、错误B、正确参考答案：A45. n个顶点的强连通图中至少含有( )。A.n-1条有向边B.n条有向边C.n(n-1)/2条有向边D.n(n-1)条有向边参考答案：B46. 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是( )。A.nB.2n-1C.2nD.n-1参考答案：A47. 下列描述中正确的是( )。A.选择合适的数据结构是解
12、决应用问题的关键步骤B.线性表的逻辑顺序与存储顺序总是一致的C.每种数据结构都具备查找、插入和删除三种基本运算D.数据结构实质上包括逻辑结构和存储结构两方面的内容参考答案：A48. 最佳二叉排序树是AVL树(平衡二叉排序树)。( )A.正确B.错误参考答案：A49. 在k叉树中，度为0的结点称为( )。A.祖先B.根C.子孙D.叶参考答案：D50. 串S=”I am a worker的长度是10。( )A、错误B、正确参考答案：A51. 数组是同类型值的集合。( )A.正确B.错误参考答案：B52. 一个队列的入队序列是1、2、3、4，则队列的首次输出元素是( )。A.1B.2C.3D.4参考
13、答案：A53. 数据的存储结构是数据的逻辑结构在计算机存储器上的实现，它是依赖于计算机的。( )A.正确B.错误参考答案：A54. 快速排序方法在( )情况下最不利于发挥其长处。A.被排序的数据量太大B.被排序数据中含有多个相同值C.被排序数据已基本有序D.被排序数据数目为奇数参考答案：C55. 线性表是具有n个( )的有限序列。A.字符B.数据元素C.数据项D.表元素参考答案：B56. 按照二叉树的定义，具有3个结点的二叉树有( )种。A.3B.4C.5D.6参考答案：C57. 邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。( )A.正确B.错误参考答案：B58. 设某算法的问题规模函数f(n)=300n2+8000n
