《西北工业大学21春《数据结构》离线作业2参考答案7》由会员分享，可在线阅读，更多相关《西北工业大学21春《数据结构》离线作业2参考答案7（11页珍藏版）》请在金锄头文库上搜索。
1、西北工业大学21春数据结构离线作业2参考答案1. 如果某种排序算法是不稳定的，则这种算法不可用。( )A.正确B.错误参考答案：A2. 下面哪些方法可以判断出一个有向图是否有环(回路)?( )A.求最短路径B.求关键路径C.拓扑排序D.广(宽)度优先遍历参考答案：C3. 删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。( )A、错误B、正确参考答案：A4. 设某完全无向图中有n个顶点，则该完全无向图中有( )条边。A.n(n-1)/2B.n(n-1)C.n2D.n2-1参考答案：A5. 某二叉树的前序和后序序列正好相同，则该二叉树一定是( )的二叉树。A.空或只有一个结点
2、B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子参考答案：A6. 在一个单链表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参考答案：D7. 不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。( )A.正确B.错误参考答案：A8. 任何一个递归过程都可以转换成非递归过程。( )A.正确B.错误参考答案：A9. 循环队列SQ采用数组空间SQ.base0，n-1存储其
3、元素值，已知其头尾指针分别是front和rezr，则判断此循环队列Q为满队列的条件是( )。A.Q.front=Q.rearB.Q.rear!=Q.frontC.Q.front=(Q.rear+1)%nD.Q.front!=(Q.rear+1)%n参考答案：C10. 稀疏矩阵压缩存储后，必会失去随机存取功能。( )A.正确B.错误参考答案：A11. 算法分析的两个主要方面是( )。A.正确性与健壮性B.时间复杂度与空间复杂度C.数据复杂性与程序复杂性D.可读性与可用性参考答案：B12. 带行表的三元组表是稀疏矩阵的一种( )。A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构参考
4、答案：A13. 与单链表相比，双链表的优点之一是( )。A.插入、删除操作更简单B.可以进行随机访问C.可以省略表头指针或表尾指针D.顺序访问相邻结点更灵活参考答案：C14. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的( )。A.先序遍历B.中序遍历C.后序遍历D.按层遍历参考答案：C15. 在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是堆排序。( )A、错误B、正确参考答案：A16. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p之前插入s所指结点，则执行( )。A.s-next=p-next; p-next=sB.q-next=s; s-next
5、=pC.p-next=s; s-next=qD.p-next=s-next; s-next=p参考答案：B17. 设有100个关键字，用折半查找法进行查找时，最大比较次数为( )。A.7B.6C.50D.25参考答案：A18. 向顺序栈中压入新元素时，应当( )A.先移动栈顶位置，再存入元素B.先存入元素，再移动栈顶位置C.先后 次序无关紧要D.同时进行参考答案：A19. 二维数组A的每个元素是由6个字符组成的串，其行下标i=0，1，8，列下标为j=1，2，10。设每个字符占一个字节，若按行先存储，元素A8，5的起始地址与A按列存储时起始地址相同的元素是( )。A.A8，5B.A3，10C.A
6、5，8D.A0，9参考答案：B20. 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是( )。A.nB.2n-1C.2nD.n-1参考答案：A21. 已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于( )。A.1.0B.2.9C.3.4D.5.5参考答案：B22. 在线性表的下列运算中，不改变数据元素之间结构关系的运算是( )。A、插入B、删除C、排序D、定位参考答案：D23. 快速排序方法在( )情况下最不利于发挥其长处。A.被排序的数据量太大B.被排序数据中含有多个相同值C.被排序数据已基本有序D.被排序数据数目为奇数参考答
7、案：C24. n个结点的线索二叉树上含有的线索数为( )。A.n-1B.n+1C.nD.2n参考答案：B25. 高度为5的完全二叉树中含有的结点数至少为( )。A、16B、17C、31D、32参考答案：A26. 深度为h的满m叉树的第k层的结点(1=A.mk-1B.mk-1C.mh-1D.mh-1参考答案：A27. 取顺序表的第i个元素的时间与i的大小无关。( )A.正确B.错误参考答案：A28. 对于3个结点a、b、c，可构成不同的二叉树的棵数为( )。A.32B.30C.28D.24参考答案：B29. 数据的逻辑结构是指数据的各数据项之间的逻辑关系。( )A.正确B.错误参考答案：B30.
8、 任何有向网的拓扑排序的结果是唯一的。( )A.正确B.错误参考答案：B31. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( )A.正确B.错误参考答案：B32. 归并排序的辅助存储空间代价为O(1)。( )A.正确B.错误参考答案：B33. 无向图的邻接矩阵可用一维数组存储。( )A.正确B.错误参考答案：A34. 深度为5的二叉树至多有( )个结点。A.16B.32C.31D.10参考答案：C35. 下列描述中正确的是( )。A.选择合适的数据结构是解决应用问题的关键步骤B.线性表的逻辑顺序与存储顺序总是一致的C.每种数据结构都具备查找、插入和删除三种基本运算D.数据结构实质
9、上包括逻辑结构和存储结构两方面的内容参考答案：A36. 具有65个结点的完全二叉树其深度为(根的层次号为1)( )。A.8B.7C.6D.5参考答案：B37. 健壮的算法不会因非法的输人数据而出现莫名其妙的状态。( )A.正确B.错误参考答案：A38. 数据的逻辑结构是指各数据元素之间的逻辑关系。( )A.正确B.错误参考答案：A39. 分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。( )A.正确B.错误参考答案：A40. 已知函数Sub(s,I,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能
10、为复制串t到s。若字符串S=SCIENCESTUDY，则调用函数Scopy(P,Sub(S,1,7)后得到( )。A、P=SCIENCEB、P=STUDYC、S=SCIENCED、S=STUDY参考答案：A41. 已知指针p指向某单链表中的一个结点，则判别该结点有且仅有一个后继结点的条件是p-next-next=null。( )A、错误B、正确参考答案：B42. 完全二叉树中的叶子结点只可能在最后两层中出现。( )A.正确B.错误参考答案：A43. 在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系( )。A.不一定相同B.都相同C.都不相同D.互为逆序参考答案：B44. 散列函
11、数有一个共同的性质，即函数值应当以下面的哪一项来取其值域的每个值?( )A.最小概率B.最大概率C.平均概率D.同等概率参考答案：D45. 结构的存储密度定义为数据本身所占的存储量与整个结构所占的存储量之比。( )A.正确B.错误参考答案：A46. 若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列3，2，5，6，4，1。( )A.正确B.错误参考答案：A47. 可以用队列实现数值转换算法。( )A.正确B.错误参考答案：A48. 含n个顶点的无向连通图中至少含有n条边。( )A、错误B、正确参考答案：A49. 对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的左孩子的编号为98。( )A、错误B、正确参考答案：B50. 插入、删除只能在同一端进行的线性表，称为( )。A.队列B.栈C.循环队列D.循环栈参考答案：B
