《西北工业大学21秋《数据结构》在线作业一答案参考79》由会员分享，可在线阅读，更多相关《西北工业大学21秋《数据结构》在线作业一答案参考79（13页珍藏版）》请在装配图网上搜索。
1、西北工业大学21秋数据结构在线作业一答案参考1. 分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。( )A.正确B.错误参考答案：A2. 设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有( )个空指针域。A.2m-1B.2mC.2m+1D.4m参考答案：B3. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。A.插入B.选择C.交换D.二路归并参考答案：A4. 对于3个结点a、b、c，可构成不同的二叉树的棵数为( )。A.3
2、2B.30C.28D.24参考答案：B5. 若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是( )。A.10B.11C.12D.15参考答案：A6. 通常将链串的结点大小设置为大于1是为了( )。A、提高串匹配效率B、提高存储密度C、便于插入操作D、便于删除操作参考答案：A7. 抽象数据类型是指数据逻辑结构及与之相关的操作。( )A、错误B、正确参考答案：B8. 已知广义表LS=(a，b，c)，(d，e，f)，运算head和tail函数取出元素e的运算是( )。A.head(tail(LS)B.tail(head(LS)C.head(tail(head(tail(LS)D.head
3、(tail(tail(head(LS)参考答案：C9. 在一个长度为n的单链表L中，删除链表中*p的前驱结点的时间复杂度为O(n)。( )A、错误B、正确参考答案：B10. 如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用( )。A.深度优先搜索算法B.广度优先搜索算法C.求最小生成树的prim算法D.拓扑排序算法参考答案：B11. 已知指针p指向某单链表中的一个结点，则判别该结点有且仅有一个后继结点的条件是p-next-next=null。( )A、错误B、正确参考答案：B12. 下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。A.选择B.冒泡C.归并D.
4、堆参考答案：C13. 若哈希表(散列表)的负载因子l，则可避免冲突的产生。( )A.正确B.错误参考答案：B14. 在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度(即x与元素的平均比较次数，假定查找每个元素的概率都相等)为( )。A.nB.n/2C.(n+1)/2D.(n-1)/2参考答案：C15. 一个关键字序列为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，
5、84参考答案：C16. 删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。( )A、错误B、正确参考答案：A17. 指针p所指的元素是双向循环链表L的尾元素的条件是( )。A.p=LB.p=NULLC.p-prior=LD.p-next=L参考答案：D18. 在指定结点之后插入新结点时，双链表比单链表更方便。( )A.正确B.错误参考答案：B19. 分块查找在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中的元素个数有关。( )A.正确B.错误参考答案：A20. 不含任何字符的串称为空串。( )A、错误B、正确参考答案：B21. 若一个有向图的邻接距阵中
6、，主对角线以下的元素均为零，则该图的拓扑有序序列( )。A.一定存在B.一定不存在C.不一定存在D.不确定参考答案：A22. 最佳二叉排序树是AVL树(平衡二叉排序树)。( )A.正确B.错误参考答案：A23. 在一个单链表中，已知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参考答案：B24. 在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系( )。A.不一定相同B.都相
7、同C.都不相同D.互为逆序参考答案：B25. 下列存储表示中，哪一个不是树的存储形式( )。A.双亲表示法B.孩子链表表示法C.顺序存储表示法D.孩子兄弟表示法参考答案：C26. 右图中的拓扑序列为( )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参考答案：D27. 下列程序段for(i=1; iA.O(1)B.O(0)C.O(1+n)D.O(n)参考答案：D28. 已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目
8、为k。( )A、错误B、正确参考答案：A29. 按层次次序将一颗有n个结点的完全二叉树的所有结点从1到n编号，当iA.2i-1B.2iC.2i+1D.不确定参考答案：B30. 深度为5的二叉树至多有( )个结点。A.16B.32C.31D.10参考答案：C31. 一棵左右子树均不空的二叉树在前序线索化后，其中空的链域的个数是( )。A.不确定B.2C.1D.0参考答案：C32. 已知循环队列的存储空间为数组data21，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为( )。A.5B.6C.16D.17参考答案：C33. 设某棵二叉树中有2000个结点，则该二叉树的最小高度为(
9、 )。A.9B.10C.11D.12参考答案：C34. 队列的插入操作是在( )。A.队尾B.队头C.队列任意位置D.队头元素后参考答案：A35. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为( )。A、3，2，6，1，4，5B、3，4，2，1，6，5C、1，2，5，3，4，6D、5，6，4，2，3，1参考答案：B36. 已知函数Sub(s,I,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=SCIENCESTUDY，则调用函数Scopy(P,Sub(S,1,7)后得到( )。A、P=SCIE
10、NCEB、P=STUDYC、S=SCIENCED、S=STUDY参考答案：A37. 一棵含18个结点的二叉树的高度至少为( )。A、3B、4C、5D、6参考答案：C38. 在链表的结点中，数据元素所占的存储量和整个结点所占的存储量之比称作存储密度。( )A、错误B、正确参考答案：B39. 算法分析的两个主要方面是( )。A.空间复杂度和时间复杂度B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性参考答案：A40. 算法分析的目的是( )。A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易读性和文档性参考答案：C41. 取顺序表的第i个
11、元素的时间与i的大小无关。( )A.正确B.错误参考答案：A42. 线性表的唯一存储形式就是链表。( )A.正确B.错误参考答案：A43. 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是( )。A.nB.2n-1C.2nD.n-1参考答案：A44. 用有向无环图描述表达式(A+B)*(A+B)/A)，至少需要顶点的数目为( )。A.5B.6C.8D.9参考答案：A45. 广义表运算式tail(a，b)，(c，d)的操作结果是( )。A.dB.c，dC.(c，d)D.(c，d)参考答案：D46. 若一棵满三叉树中含有121个结点，则该树的深度为6。( )A、错误B、正确参考答案：
12、A47. 非空的双向循环链表中任何结点的前驱指针均不为空。( )A.正确B.错误参考答案：A48. 若链串结点中的指针占4个字节，每个字符占1个字节，则结点大小为2的链串的存储密度为2/6。( )A、错误B、正确参考答案：B49. 有关二叉树下列说法正确的是( )。A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为2参考答案：B50. 用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为( )。A.n-1B.nC.n+lD.2n参考答案：C51. 判断线索二叉树中某结点p有右子女的条件是( )。A.p-rtag=1B.p-r
13、tag=0C.p-lchild!=NULLD.p!=NULL参考答案：B52. 在对含n个结点的二叉树进行先序、中序和后序遍历时，其时间复杂度( )。A.都不相同B.完全相同C.先序和中序相同，而与后序不同D.中序和后序相同，而与先序不同参考答案：B53. 向顺序栈中压入新元素时，应当( )A.先移动栈顶位置，再存入元素B.先存入元素，再移动栈顶位置C.先后 次序无关紧要D.同时进行参考答案：A54. 对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。( )A、错误B、正确参考答案：B55. 链接存储结构属静态存储方式。( )A.正确B.错误参考答案：B56.
14、设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数为( )A.3B.4C.5D.1参考答案：B57. 若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为O(n)。( )A、错误B、正确参考答案：A58. 在一个单链表中，若删除*p结点的后继结点，则执行操作( )。A.q=p-next; p-next=q-next; free(q)B.p=p-next; p-next=p-next-next; free(p)C.p-next=q-next; free(p-next)D.p=p-next-next; free(p-next)参考答案：A59. n个顶点的连通图至少有( )条边。A.n-1B.nC.n+1D.0参考答案：A60. 对线性表进行二分查找时，要求线性表必须( )。A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且结点按关键字有序排列D.以链接方式存储，且结点按关键字有序排列参考答案：C
西北工业大学21秋《数据结构》在线作业一答案参考79
