西北工业大学21秋《数据结构》在线作业一答案参考39

西北工业大学21秋数据结构在线作业一答案参考1. 一个具有4个顶点的无向完全图有6条边。( )A、错误B、正确参考答案：B2. 深度为5的二叉树至多有( )个结点。A.16B.32C.31D.10参考答案：C3. 一个有向无环图的拓扑排序序列( )是唯一的。A.可能B.不一定C.三者均不对D.一定参考答案：B4. 采用邻接表存储的图的广度优先遍历算法类似于二叉树的( )。A.先序遍历B.中序遍历C.后序遍历D.按层遍历参考答案：D5. 对于哈希函数，冲突只能尽可能得少，不可能完全避免。( )A.正确B.错误参考答案：A6. 某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为( )。A.3B.2C.4D.5参考答案：C7. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是( )。A.单链表B.静态链表C.线性链表D.顺序存储结构参考答案：C8. 线性表的链接实现有利于( )运算。A.插入B.读表元C.查找D.定位参考答案：A9. 下面关于线性表的叙述错误的是( )。A.线性表采用顺序存储必须占用一片连续的存储空间B.线性表采用链式存储不必占用一片连续的存储空间C.线性表采用链式存储便于插入和删除操作的实现D.线性表采用顺序存储便于插入和删除操作的实现参考答案：D10. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则节省时间的存储方式是( )。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表参考答案：A11. 平衡二叉树的平衡因子只可能是-1、0、1。( )A.正确B.错误参考答案：A12. 由带权为9，2，5，7的四个叶子结点构造一颗哈夫曼树，该树的带权路径长度为( )。A.23B.37C.46D.44参考答案：D13. 稀疏矩阵常用的压缩存储方法有两种，它们是( )。A.散列和十字链表B.二维数组和三维数组C.三元组和散列D.三元组和十字链表参考答案：D14. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p之前插入s所指结点，则执行( )。A.s-next=p-next; p-next=sB.q-next=s; s-next=pC.p-next=s; s-next=qD.p-next=s-next; s-next=p参考答案：B15. 具有65个结点的完全二叉树其深度为(根的层次号为1)( )。A.8B.7C.6D.5参考答案：B16. 按排序过程中依据的原则分类，快速排序属于( )。A.插入类的排序方法B.选择类的排序方法C.交换类的排序方法D.归并类的排序方法参考答案：C17. 队列的队尾位置通常是随着入队操作而变化的。( )A、错误B、正确参考答案：B18. 无向图的邻接矩阵可用一维数组存储。( )A.正确B.错误参考答案：A19. 在下列各种文件中，不能进行顺序查找的文件是( )。A.顺序文件B.索引文件C.散列文件D.多重表文件参考答案：C20. 在一个单链表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参考答案：D21. 中序遍历的递归算法平均空间复杂度为( )。A.2(n)B.n(2)C.0(n)D.2n参考答案：C22. 后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。( )A.正确B.错误参考答案：A23. 如果某种排序算法是不稳定的，则这种算法不可用。( )A.正确B.错误参考答案：A24. 一棵树可以只有1个结点。( )A、错误B、正确参考答案：B25. 下列关于数据结构基本概念的叙述中，正确的是( )。A.数据的逻辑结构分为表结构和树结构B.数据的存储结构分为线性结构和非线性结构C.数据元素是数据的基本单位D.结点是有独立含义的数据最小单位参考答案：C26. 已知一组关键字为25，48，36，72，79，82，23，40，16，35，其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是( )。A.25，36，48，72，23，40，79，82，16，35B.25，36，48，72，16，23，40，79，82，35C.25，36，48，72，16，23，35，40，79，82D.16，23，25，35，36，40，48，72，79，82参考答案：D27. 已知指针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参考答案：A28. 设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为( )A.O(nlog2e)B.O(n+e)C.O(ne)D.O(n2)参考答案：B29. 设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有( )个空指针域。A.2m-1B.2mC.2m+1D.4m参考答案：B30. 下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是( )。A.直接选择排序B.直接插入排序C.快速排序D.堆排序参考答案：C31. 任何一个递归过程都可以转换成非递归过程。( )A.正确B.错误参考答案：A32. 已知函数Sub(s,I,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=SCIENCESTUDY，则调用函数Scopy(P,Sub(S,1,7)后得到( )。A、P=SCIENCEB、P=STUDYC、S=SCIENCED、S=STUDY参考答案：A33. 假设一棵完全二叉树含1000个结点,则其中度为2的结点数为512个。( )A、错误B、正确参考答案：A34. 设有50行60列的二维数组A5060，其元素长度为4字节，按行优先顺序存储，基地址为200，则元素A1825的存储地址为( )。A.3700B.4376C.3900D.4620参考答案：D35. 对线性表进行折半查找时，要求线性表必须( )。A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且结点按关键字有序排序D.以链接方式存储，且结点按关键字有序排序参考答案：C36. 下列四种排序中( )的空间复杂度最大。A.插入排序B.冒泡排序C.堆排序D.归并排序参考答案：C37. 设串s1=Data Structures with Java，s2=it，则子串定位函数index(s1,s2)的值为( )。A、15B、16C、17D、18参考答案：D38. 不含任何字符的串称为空串。( )A、错误B、正确参考答案：B39. 在存储数据时，通常不仅要存储各数据元素的值，而且还要存储( )。A.数据的处理方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法参考答案：C40. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是( )。A.9B.11C.15D.不能确定参考答案：C41. 指针p所指的元素是双向循环链表L的尾元素的条件是( )。A.p=LB.p=NULLC.p-prior=LD.p-next=L参考答案：D42. 设二维数组A0.m-10.n-1按行优先顺序存储且每个元素占c个单元，则元素Aij的地址为( )。A.LOC(A00)+(j*m+i)*cB.LOC(A00)+(j-1)*m+i-1*cC.LOC(A00)+(i*n+j)*cD.LOC(A00)+(i-1)*n+j-1*c参考答案：C43. 在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是堆排序。( )A、错误B、正确参考答案：A44. 在线性表的下列运算中，不改变数据元素之间结构关系的运算是( )。A、插入B、删除C、排序D、定位参考答案：D45. 若用n表示图中顶点数目，则有( )条边的无向图成为完全图。A.nB.n-1C.n(n-1)2D.n(n+1)2参考答案：C46. 以下数据结构中，属于线性结构的是( )。A.广义表B.二叉树C.稀疏矩阵D.串参考答案：A47. 若要在单链表中的结点p之后插入一个结点s，则应执行的语句是( )。A.s-next=p-next; p-next=sB.p-next=s; s-next=p-nextC.p-next=s-next; s-next=pD.s-next=p; p-next=s-next参考答案：A48. 完全二叉树中的叶子结点只可能在最后两层中出现。( )A.正确B.错误参考答案：A49. 若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是( )。A.1234B.4132C.4231D.4213参考答案：C50. 在文本编辑程序中查找某一特定单词在文本中出现的位置，可以利用串的定位操作。( )A、错误B、正确参考答案：B51. 程序一定是算法。( )A.正确B.错误参考答案：B52. 求图的最小(代价)生成树问题，考虑的是下面的哪一种图?( )A.有向图B.无向图C.带权的有向图D.带权的无向图参考答案：D53. 二叉树中的叶子结点就是二叉树中没有左右子树的结点。( )A、错误B、正确参考答案：B54. 一个关键字序列为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参考答案：C55. 数据结构是带有结构的数据元素的集合。( )A.正确B.错误参考答案：A56. 归并排序的辅助存储空间代价为O(1)。( )A.正确B.错误参考答案：B57. 算法有以下几种特性( )。A、有穷性B、确定性C、可行性D、输入和输出参考答案：ABCD58. 深度为15的满二叉树上，第11层有211个结点。( )A、错误B、正确参考答案：A59. 健壮的算法不会因非法的输人数据而出现莫名其妙的状态。( )A.正确B.错误参考答案：A60. 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是( )。A.nB.2n-1C.2nD.n-1参考答案：A