《西北工业大学21秋《数据结构》平时作业一参考答案36》由会员分享，可在线阅读，更多相关《西北工业大学21秋《数据结构》平时作业一参考答案36（13页珍藏版）》请在金锄头文库上搜索。
1、西北工业大学21秋数据结构平时作业一参考答案1. 一个栈的入栈序列是abcde，则栈的不可能的输出序列是( )。A.edcbaB.decbaC.dceabD.abcde参考答案：C2. 链接存储结构属静态存储方式。( )A.正确B.错误参考答案：B3. 任何一个递归过程都可以转换成非递归过程。( )A.正确B.错误参考答案：A4. 在长度为n的顺表表的第i个位置上插入一个元素(1in+1)，元素的移动次数为( )。A.n-i+1B.n-iC.iD.i-1参考答案：C5. 队列允许在队尾删除，在队头插入。( )A.正确B.错误参考答案：A6. 下列程序段for(i=1; iA.O(1)B.O(0
2、)C.O(1+n)D.O(n)参考答案：D7. 完全二叉树中的叶子结点只可能在最后两层中出现。( )A.正确B.错误参考答案：A8. 栈和队列都是限制存取点的线性结构。( )A.正确B.错误参考答案：A9. 用ISAM组织文件适合于( )。A.磁盘B.磁带C.外存储器D.光盘参考答案：A10. 设s1=“abc”，则strlen(s1)=( )。A.3B.2C.1D.0参考答案：A11. 用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为( )。A.n-1B.nC.n+lD.2n参考答案：C12. n个结点的线索二叉树上含有的线索数为( )。A.n-1B.n+1C.nD.2n参考答案
3、：B13. 在一个长度为n的单链表L中，删除链表中*p的前驱结点的时间复杂度为O(n)。( )A、错误B、正确参考答案：B14. 设串sl=DataStructureswithJava，s2=it，则子串定位函数index(s1,s2)的值为( )A.15B.16C.17D.18参考答案：D15. 如果某种排序算法是不稳定的，则这种算法不可用。( )A.正确B.错误参考答案：A16. 一个有向无环图的拓扑排序序列( )是唯一的。A.可能B.不一定C.三者均不对D.一定参考答案：B17. 对线性表进行折半查找时，要求线性表必须( )。A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且结点
4、按关键字有序排序D.以链接方式存储，且结点按关键字有序排序参考答案：C18. 深度为h的满m叉树的第k层的结点(1=A.mk-1B.mk-1C.mh-1D.mh-1参考答案：A19. 不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。( )A.正确B.错误参考答案：A20. 下列说法中，不正确的是( )。A.数据元素是数据的基本单位B.数据项是数据中不可分割的最小可标识单位C.数据可由若干个数据元素构成D.数据项可由若干个数据元素构成参考答案：D21. 设二维数组A0.m-10.n-1按行优先顺序存储且每个元素占c个单元，则元素Aij的地址为( )。A.LO
5、C(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参考答案：C22. 设某棵二叉树中有2000个结点，则该二叉树的最小高度为( )。A.9B.10C.11D.12参考答案：C23. 依次在初始为空的队列中插入元素X，Y，Z，W以后，紧接着作了两次删除操作，此时的队头元素是( )A.XB.YC.ZD.W参考答案：C24. 具有65个结点的完全二叉树其深度为(根的层次号为1)( )。A.8B.7C.6D.5参考答案：B25. 如果求一个连通图中以某个顶点为根的高度最小的生成树，应采
6、用( )。A.深度优先搜索算法B.广度优先搜索算法C.求最小生成树的prim算法D.拓扑排序算法参考答案：B26. 假设一棵完全二叉树含1000个结点,则其中度为2的结点数为512个。( )A、错误B、正确参考答案：A27. 已知指针p指向某单链表中的一个结点，则判别该结点有且仅有一个后继结点的条件是p-next-next=null。( )A、错误B、正确参考答案：B28. 四个元素进入队列QU的顺序是U、V、X、Y，进行DeQueue(QU，x)操作后，队头元素是( )。A.YB.XC.VD.U参考答案：C29. 取顺序表的第i个元素的时间与i的大小无关。( )A.正确B.错误参考答案：A3
7、0. 在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是( )。A.O(1)B.O(n)C.O(n2)D.O(nlog2n)参考答案：B31. 在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是堆排序。( )A、错误B、正确参考答案：A32. 若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为O(n)。( )A、错误B、正确参考答案：A33. 数据项是数据的基本单位。( )A.正确B.错误参考答案：A34. 不含任何字符的串称为空串。( )A、错误B、正确参考答案：B35. 右图中的拓扑序列为( )A.C1，C2，C6
8、，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参考答案：D36. 数据的逻辑结构描述数据元素之间的逻辑关系，与存储方式无关。( )A、错误B、正确参考答案：B37. 邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。( )A.正确B.错误参考答案：B38. 算法分析的两个主要方面是( )。A.空间复杂度和时间复杂度B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性参考答案：A39. n个顶点的连通图至少有( )条边。A.n
9、-1B.nC.n+1D.0参考答案：A40. 一棵含18个结点的二叉树的高度至少为( )。A、3B、4C、5D、6参考答案：C41. 栈是一种操作受限的线性结构，其操作的主要特征是( )。A、先进先出B、后进先出C、进优于出D、出优于进参考答案：B42. 若有向图的邻接矩阵中，主对角线以下元素均为零，则该图的拓扑有序序列( )。A.存在B.可能不存在C.不存在D.不一定存在参考答案：A43. 快速排序是排序算法中平均性能最好的一种排序。( )A.正确B.错误参考答案：A44. 按排序过程中依据的原则分类，快速排序属于( )。A.插入类的排序方法B.选择类的排序方法C.交换类的排序方法D.归并类
10、的排序方法参考答案：C45. 在有向图中，以顶点v为终点的边的数目称为v的入度。( )A、错误B、正确参考答案：B46. 任何一棵二叉树的叶结点在前序、中序和后序遍历序列中的相对次序( )。A.稍有改变B.发生改变C.不能确定D.不发生改变参考答案：D47. 算法分析的目的是( )。A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易读性和文档性参考答案：C48. 如果要求一个线性表既能较快地查找、又能适应动态变化的要求，则可采用的查找方法是( )。A.顺序查找B.折半查找C.基于属性的查找D.分块查找参考答案：D49. 算法分析的目的是( )。A
11、、辨别数据结构的合理性B、评价算法的效率C、研究算法中输入与输出的关系D、鉴别算法的可读性参考答案：B50. 程序一定是算法。( )A.正确B.错误参考答案：B51. 一个好的算法有( )设计要求。A、正确性B、可读性C、健壮性D、效率与低存储量要求参考答案：ABCD52. 在一个单链表中，已知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参考答案：B53. 非空的双向循环链表中任何结点的
12、前驱指针均不为空。( )A.正确B.错误参考答案：A54. 在长度为n的顺序表的第i(1in+1)个位置上插入一个元素，元素的移动次数为( )。A、n-i+1B、n-iC、iD、i-1参考答案：A55. 具有n个结点的连通图至少有( )条边。A.n-1B.nC.n(n-1)/2D.2n参考答案：A56. 若一个广义表的表头为空表，则此广义表亦为空表。( )A.正确B.错误参考答案：B57. 数据元素及其关系在计算机存储器内的表示，称为数据的( )。A.逻辑结构B.存储结构C.线性结构D.非线性结构参考答案：B58. 若要在单链表中的结点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参考答案：A59. 链式栈与顺序栈相比，一个比较明显的优点是( )A.插入操作更加方便B.通常不会出现栈满的情况C.不会出现栈空的情况D.删除操作更加方便参考答案：B60. 采用分快查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分( )个结点最佳。A.10B.25C.6D.625参考答案：B
