西北工业大学21秋《数据结构》平时作业一参考答案66

西北工业大学21秋数据结构平时作业一参考答案1. 下面关于线性表的叙述错误的是( )。A.线性表采用顺序存储必须占用一片连续的存储空间B.线性表采用链式存储不必占用一片连续的存储空间C.线性表采用链式存储便于插入和删除操作的实现D.线性表采用顺序存储便于插入和删除操作的实现参考答案：D2. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用( )存储方式最节省运算时间。A.单链表B.给出表头指针的单循环链表C.双链表D.带头结点的双循环链表参考答案：D3. 通常将链串的结点大小设置为大于1是为了( )。A、提高串匹配效率B、提高存储密度C、便于插入操作D、便于删除操作参考答案：A4. 已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为k。( )A、错误B、正确参考答案：A5. 设有100个关键字，用折半查找法进行查找时，最大比较次数为( )。A.7B.6C.50D.25参考答案：A6. 若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是( )。A.1234B.4132C.4231D.4213参考答案：C7. 在二叉树的第i层上至多可以有2i个结点。( )A、错误B、正确参考答案：A8. 设串s1=Data Structures with Java，s2=it，则子串定位函数index(s1,s2)的值为( )。A、15B、16C、17D、18参考答案：D9. 算法分析的两个主要方面是( )。A.正确性与健壮性B.时间复杂度与空间复杂度C.数据复杂性与程序复杂性D.可读性与可用性参考答案：B10. 分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。( )A.正确B.错误参考答案：A11. 下列四种基本的逻辑结构中，数据元素之间关系最弱的是( )。A.集合B.线性结构C.树形结构D.图状结构参考答案：A12. 按层次次序将一颗有n个结点的完全二叉树的所有结点从1到n编号，当iA.2i-1B.2iC.2i+1D.不确定参考答案：B13. 由于排序过程中涉及的存储器不同，可以将排序方法分为( )。A、稳定排序B、不稳定排序C、内部排序D、外部排序参考答案：CD14. 下列关于数据结构基本概念的叙述中，正确的是( )。A.数据的逻辑结构分为表结构和树结构B.数据的存储结构分为线性结构和非线性结构C.数据元素是数据的基本单位D.结点是有独立含义的数据最小单位参考答案：C15. 通用的处理哈希冲突的方法有( )。A、开放定址法B、再哈希法C、链地址法D、建立公共溢出区参考答案：ABCD16. 一棵含999个结点的完全二叉树的深度为12。( )A、错误B、正确参考答案：A17. 算法分析的两个主要方面是( )。A.空间复杂度和时间复杂度B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性参考答案：A18. 二叉排序树上左子树上所有结点的值均小于它的根结点的值。( )A.正确B.错误参考答案：A19. 栈的插入和删除操作在( )进行。A.栈顶B.栈底C.任意位置D.指定位置参考答案：A20. 在对含n个结点的二叉树进行先序、中序和后序遍历时，其时间复杂度( )。A.都不相同B.完全相同C.先序和中序相同，而与后序不同D.中序和后序相同，而与先序不同参考答案：B21. 高度为5的完全二叉树中含有的结点数至少为( )。A、16B、17C、31D、32参考答案：A22. 在一个长度为n的单链表L中，删除链表中*p的前驱结点的时间复杂度为O(n)。( )A、错误B、正确参考答案：B23. 求图的最小(代价)生成树问题，考虑的是下面的哪一种图?( )A.有向图B.无向图C.带权的有向图D.带权的无向图参考答案：D24. 深度为5的二叉树至多有( )个结点。A.16B.32C.31D.10参考答案：C25. 连通网的最小生成树是其所有生成树中( )。A.顶点集最小的生成树B.边集最小的生成树C.顶点权值之和最小的生成树D.边的权值之和最小的生成树参考答案：D26. 在长度为n的顺序表的第i(1in+1)个位置上插入一个元素，元素的移动次数为( )。A、n-i+1B、n-iC、iD、i-1参考答案：A27. 某二叉树的前序和后序序列正好相同，则该二叉树一定是( )的二叉树。A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子参考答案：A28. 设二维数组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参考答案：C29. 采用邻接表存储的图的广度优先遍历算法类似于二叉树的( )。A.先序遍历B.中序遍历C.后序遍历D.按层遍历参考答案：D30. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是( )。A.单链表B.静态链表C.线性链表D.顺序存储结构参考答案：C31. 一个栈的入栈序列是abcde，则栈的不可能的输出序列是( )。A.edcbaB.decbaC.dceabD.abcde参考答案：C32. 二维数组A的每个元素是由6个字符组成的串，其行下标i=0，1，8，列下标为j=1，2，10。设每个字符占一个字节，若按行先存储，元素A8，5的起始地址与A按列存储时起始地址相同的元素是( )。A.A8，5B.A3，10C.A5，8D.A0，9参考答案：B33. 广义表(a，b，c，d)的表头是( )。A.(b，c，d)B.(a，b，c，d)C.aD.(a)参考答案：B34. 用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。A.逆拓扑有序B.拓扑有序C.无序的D.A和B参考答案：A35. 指针p所指的元素是双向循环链表L的尾元素的条件是( )。A.p=LB.p=NULLC.p-prior=LD.p-next=L参考答案：D36. 不含任何字符的串称为空串。( )A、错误B、正确参考答案：B37. 在目标串T0.n-1=“xwxxyxy”中，对模式串P0.m-1=“xy”进行子串定位操作的结果是( )。A.1B.2C.3D.5参考答案：C38. 对于哈希函数H(key)=key%13，被称为同义词的关键字是( )。A、35和41B、23和39C、15和44D、25和51参考答案：D39. 右图中的拓扑序列为( )A.C1，C2，C6，C7，C5，C4，C3B.C1，C2，C6，C3，C4，C5，C7C.C1，C4，C2，C3，C5，C6，C7D.C5，C7，C4，C1，C2，C6，C3参考答案：D40. 下面哪些方法可以判断出一个有向图是否有环(回路)?( )A.求最短路径B.求关键路径C.拓扑排序D.广(宽)度优先遍历参考答案：C41. 按排序过程中依据的原则分类，快速排序属于( )。A.插入类的排序方法B.选择类的排序方法C.交换类的排序方法D.归并类的排序方法参考答案：C42. 四个元素进入队列QU的顺序是U、V、X、Y，进行DeQueue(QU，x)操作后，队头元素是( )。A.YB.XC.VD.U参考答案：C43. 若一个有向图的邻接距阵中，主对角线以下的元素均为零，则该图的拓扑有序序列( )。A.一定存在B.一定不存在C.不一定存在D.不确定参考答案：A44. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则节省时间的存储方式是( )。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表参考答案：A45. 已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于( )。A.1.0B.2.9C.3.4D.5.5参考答案：B46. 用ISAM组织文件适合于( )。A.磁盘B.磁带C.外存储器D.光盘参考答案：A47. 若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是( )。A.10B.11C.12D.15参考答案：A48. 栈下溢是指在栈空时进行出栈操作。( )A、错误B、正确参考答案：B49. 设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为( )A.O(nlog2e)B.O(n+e)C.O(ne)D.O(n2)参考答案：B50. 已知函数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参考答案：A51. 产生冲突现象的两个关键字称为该散列函数的同义字。( )A、错误B、正确参考答案：B52. 在指定结点之前插入新结点时，双链表比单链表更方便。( )A.正确B.错误参考答案：A53. 线性表中的所有元素都有一个前驱元素和后继元素。( )A.正确B.错误参考答案：A54. 已知一个散列表如图所示，其散列函数为H(key)=key%11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为( )。A.2B.3C.8D.9参考答案：C55. 一个队列的入队序列是a、b、c、d，则队列的输出序列是( )。A.dcbaB.cbdaC.adcbD.abcd参考答案：D56. 在二叉树中插入结点，则此二叉树便不再是二叉树了。( )A.正确B.错误参考答案：B57. 中序遍历二叉排序树可以得到一个有序的序列。( )A.正确B.错误参考答案：A58. 若哈希表(散列表)的负载因子l，则可避免冲突的产生。( )A.正确B.错误参考答案：B59. 在一个长度为n的循环链表中，删除其元素值为x的结点的时间复杂度为O(n)。( )A、错误B、正确参考答案：B60. 健壮的算法不会因非法的输人数据而出现莫名其妙的状态。( )A.正确B.错误参考答案：A