西北工业大学21秋《数据结构》离线作业2-001答案_10.docx

西北工业大学21秋《数据结构》离线作业2-001答案1. 已知一个散列表如图所示，其散列函数为H(key)=key%11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为( )A.2B.3C.8D.9参考答案：C2. B+树应用在( )文件系统中A.顺序B.散列C.VSAMD.ISAM参考答案：C3. 在一个单链表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参考答案：D4. 向二叉搜索树中插入一个元素时，其时间复杂度大致为( )A.O(log2n)B.O(n)C.O(1)D.O(2n)参考答案：A5. 二叉排序树上左子树上所有结点的值均小于它的根结点的值 )A.正确B.错误参考答案：A6. 已知函数Sub(s,I,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s若字符串S=″SCIENCESTUDY″，则调用函数Scopy(P,Sub(S,1,7))后得到( )。

A、P=″SCIENCE″B、P=″STUDY″C、S=″SCIENCE″D、S=″STUDY″参考答案：A7. 一个队列的入队序列是a、b、c、d，则队列的输出序列是( )A.dcbaB.cbdaC.adcbD.abcd参考答案：D8. 在关键字序列(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参考答案：B9. 快速排序是排序算法中平均性能最好的一种排序 )A.正确B.错误参考答案：A10. 归并排序的辅助存储空间代价为O(1) )A.正确B.错误参考答案：B11. 快速排序方法在( )情况下最不利于发挥其长处A.被排序的数据量太大B.被排序数据中含有多个相同值C.被排序数据已基本有序D.被排序数据数目为奇数参考答案：C12. 下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是( )A.直接选择排序B.直接插入排序C.快速排序D.堆排序参考答案：C13. 数据的逻辑结构在计算机存储器内的表示，称为数据的逻辑结构。

)A、错误B、正确参考答案：A14. 任何有向网的拓扑排序的结果是唯一的 )A.正确B.错误参考答案：B15. 设有100个关键字，用折半查找法进行查找时，最大比较次数为( )A.7B.6C.50D.25参考答案：A16. 完全二叉树中的叶子结点只可能在最后两层中出现 )A.正确B.错误参考答案：A17. 一棵左右子树均不空的二叉树在前序线索化后，其中空的链域的个数是( )A.不确定B.2C.1D.0参考答案：C18. 深度为k的二叉树至多有2k-1个结点 )A、错误B、正确参考答案：A19. 在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是( )A.O(1)B.O(n)C.O(n2)D.O(nlog2n)参考答案：B20. 顺序存储结构是通过( )表示元素之间的关系的;链式存储结构是通过( )表示元素之间的关系的A.物理上相邻，指针B.逻辑上相邻，指针C.逻辑上相临，结点D.物理上相邻，结点参考答案：A21. 具有线性结构的数据结构是( )A.赫夫曼树B.栈C.图D.树参考答案：B22. 指针p所指的元素是双向循环链表L的尾元素的条件是( )。

A.p==LB.p==NULLC.p->prior==LD.p->next==L参考答案：D23. 设某完全无向图中有n个顶点，则该完全无向图中有( )条边A.n(n-1)/2B.n(n-1)C.n2D.n2-1参考答案：A24. 在单链表中设置头结点的作用是( )A.主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断另外，不论链表是否为空，链表指针不变B.便于查找C.便于连接D.快速插入记录参考答案：A25. 对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1 )A、错误B、正确参考答案：B26. 插入、删除只能在同一端进行的线性表，称为( )A.队列B.栈C.循环队列D.循环栈参考答案：B27. 设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为( )A.21B.23C.41D.62参考答案：C28. 链表与顺序存储结构相比，在链表中进行插入、删除操作的效率高 )A.正确B.错误参考答案：A29. 设有50行60列的二维数组A[50][60]，其元素长度为4字节，按行优先顺序存储，基地址为200，则元素A[18][25]的存储地址为( )。

A.3700B.4376C.3900D.4620参考答案：D30. 程序一定是算法 )A.正确B.错误参考答案：B31. 下面程序段的时间复杂度为( )for(i=0; i＜m; i++)for(j=0; j＜n; j++)A[i][j]=i*j;A、O(m2)B、O(n2)C、O(m*n)D、O(m+n)参考答案：C32. 一个栈的入栈序列是abcde，则栈的不可能的输出序列是( )A.edcbaB.decbaC.dceabD.abcde参考答案：C33. 下面哪些方法可以判断出一个有向图是否有环(回路)?( )A.求最短路径B.求关键路径C.拓扑排序D.广(宽)度优先遍历参考答案：C34. 数据结构中的任一数据元素至多只有一个前驱和一个后继，该数据结构是( )A.线性表B.树形结构C.广义表D.图结构参考答案：A35. 平衡二叉树的平衡因子只可能是-1、0、1 )A.正确B.错误参考答案：A36. 线性表(a1，a2，...，an)以链式方式存储，访问第i位置元素的时间复杂度为( )A.O(0)B.O(1)C.O(n)D.O(n2)参考答案：C37. 广义表(a，b，c，d)的表头是( )。

A.(b，c，d)B.(a，b，c，d)C.aD.(a)参考答案：B38. 若链串结点中的指针占4个字节，每个字符占1个字节，则结点大小为2的链串的存储密度为2/6 )A、错误B、正确参考答案：B39. 结构的存储密度定义为数据本身所占的存储量与整个结构所占的存储量之比 )A.正确B.错误参考答案：A40. 以下数据结构中，属于线性结构的是( )A.广义表B.二叉树C.稀疏矩阵D.串参考答案：A41. 如果入栈序列是1，3，5，…，97，99，且出栈序列的第一个元素为99，则出栈序列中第30个元素为47 )A、错误B、正确参考答案：B42. 若一棵满三叉树中含有121个结点，则该树的深度为6 )A、错误B、正确参考答案：A43. 如果要求一个线性表既能较快地查找、又能适应动态变化的要求，则可采用的查找方法是( )A.顺序查找B.折半查找C.基于属性的查找D.分块查找参考答案：D44. 数据的不可分割的最小标识单位是( )A.数据项B.数据记录C.数据元素D.数据变量参考答案：A45. 二叉树索化后，仍不能有效求解的问题是( )A.后序线索二叉树中求后序后继B.前序线索二叉树中求前序后继C.中序线索二叉树中求中序后继D.中序线索二叉树中求中序前驱参考答案：A46. 线性链表不具有的特点是( )A.随机访问B.不必事先估计所需存储空间大小C.插入与删除时不必移动元素D.所需空间与线性表长度成正比参考答案：A47. 从未排序序列中挑选元素，并将其依次插入已排序序列(初始时为空)的一端的方法，称为( )。

A.希尔排序B.归并排序C.插入排序D.选择排序参考答案：D48. 算法分析的两个主要方面是( )A.空间复杂度和时间复杂度B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性参考答案：A49. 引入二叉线索树的目的是( )A.加快查找结点的前驱或后继的速度B.使二叉树的遍历结果唯一C.为了能方便的找到双亲D.为了能在二叉树中方便的进行插入与删除参考答案：A50. 对线性表进行折半查找时，要求线性表必须( )A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且结点按关键字有序排序D.以链接方式存储，且结点按关键字有序排序参考答案：C。