《西北工业大学21春《数据结构》在线作业二满分答案25》由会员分享，可在线阅读，更多相关《西北工业大学21春《数据结构》在线作业二满分答案25（14页珍藏版）》请在金锄头文库上搜索。
1、西北工业大学21春数据结构在线作业二满分答案1. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是( )。A.(rear+1)%n=frontB.rear=frontC.rear+1=frontD.(rear-l)%n=front参考答案：B2. 队列的修改是按先进先出的原则进行的。( )A、错误B、正确参考答案：B3. 一棵含18个结点的二叉树的高度至少为( )。A、3B、4C、5D、6参考答案：C4. 若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是( )。A.1234B.4132C.4231D.4
2、213参考答案：C5. 已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于( )。A.1.0B.2.9C.3.4D.5.5参考答案：B6. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是( )。A.9B.11C.15D.不能确定参考答案：C7. 在一个单链表中，已知q结点是p结点的前驱结点，若在q和p之间插入结点s，则执行操作：( )A.s-next=p-next; p-next=sB.s-next=p; q-next=sC.q-next=s; s-next=pD.p-next=s; s-next=q参考答案：B8
3、. 数组的逻辑结构不同于下列( )的逻辑结构。A.线性表B.栈C.队列D.树参考答案：D9. 下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序?( )A.堆B.哈夫曼树C.二叉排序树D.AVL树参考答案：A10. 在对含n个结点的二叉树进行先序、中序和后序遍历时，其时间复杂度( )。A.都不相同B.完全相同C.先序和中序相同，而与后序不同D.中序和后序相同，而与先序不同参考答案：B11. 若用n表示图中顶点数目，则有( )条边的无向图成为完全图。A.nB.n-1C.n(n-1)2D.n(n+1)2参考答案：C12. 在存储数据时，通常不仅要存储各数据元素的
4、值，而且还要存储( )。A.数据的处理方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法参考答案：C13. 若进栈序列为a，b，c，且进栈和出栈可以穿插进行，则可能出现6个不同的出栈序列。( )A、错误B、正确参考答案：A14. 一个具有4个顶点的无向完全图有6条边。( )A、错误B、正确参考答案：B15. 邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。( )A.正确B.错误参考答案：B16. 由带权为9，2，5，7的四个叶子结点构造一颗哈夫曼树，该树的带权路径长度为( )。A.23B.37C.46D.44参考答案：D17.
5、若要在单链表中的结点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参考答案：A18. 设二维数组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参考答案：C19. 若查找每个记录的概率
6、均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。A.(n-1)2B.n2C.(n+1)2D.n参考答案：C20. head指向的带表头结点的单链表为空的判定条件是( )。A.head-next=headB.head-next=NULLC.head=NULLD.head!=NULL参考答案：B21. 一棵树可以只有1个结点。( )A、错误B、正确参考答案：B22. 线性表中的所有元素都有一个前驱元素和后继元素。( )A.正确B.错误参考答案：A23. 若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是( )。A.10B.11C.12D.1
7、5参考答案：A24. 连通网的最小生成树是其所有生成树中( )。A.顶点集最小的生成树B.边集最小的生成树C.顶点权值之和最小的生成树D.边的权值之和最小的生成树参考答案：D25. 用ISAM组织文件适合于( )。A.磁盘B.磁带C.外存储器D.光盘参考答案：A26. 假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的所有弧的时间复杂度是( )A.O(n)B.O(e)C.O(n+e)D.O(n*e)参考答案：C27. 已知完全二叉树T的第5层只有7个结点，则该树共有15个叶子结点。( )A、错误B、正确参考答案：A28. 内部排序是根据关键词的大小重新安排各( )的顺序
8、。A.关键词B.数据项C.文件D.数据元素参考答案：B29. 散列函数有一个共同的性质，即函数值应当以下面的哪一项来取其值域的每个值?( )A.最小概率B.最大概率C.平均概率D.同等概率参考答案：D30. 在目标串T0.n-1=“xwxxyxy”中，对模式串P0.m-1=“xy”进行子串定位操作的结果是( )。A.1B.2C.3D.5参考答案：C31. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为( )。A.O(n) O(n)B.O(n) O(1)C.O(1) O(n)D.O(1) O(1)参考答案：C32. 线性表的唯一存储形式就是链表。( )A.正确B.错误参考答案：A3
9、3. 下列说法中，不正确的是( )。A.数据元素是数据的基本单位B.数据项是数据中不可分割的最小可标识单位C.数据可由若干个数据元素构成D.数据项可由若干个数据元素构成参考答案：D34. 按层次次序将一颗有n个结点的完全二叉树的所有结点从1到n编号，当iA.2i-1B.2iC.2i+1D.不确定参考答案：B35. 链接存储结构属静态存储方式。( )A.正确B.错误参考答案：B36. 邻接表法只能用于有向图存储。( )A.正确B.错误参考答案：B37. 任何一个无向连通图的最小生成树( )。A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在参考答案：B38. 下列程序段for(i=1; i
10、A.O(1)B.O(0)C.O(1+n)D.O(n)参考答案：D39. AOV网的含义是以顶点表示活动的网。( )A.正确B.错误参考答案：A40. 设串sl=DataStructureswithJava，s2=it，则子串定位函数index(s1,s2)的值为( )A.15B.16C.17D.18参考答案：D41. 若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列3，2，5，6，4，1。( )A.正确B.错误参考答案：A42. 对5个不同的数据元素进行直接插入排序，最多需要进行( )次比较A.8B.10C.15D.25参考答案：B43. 若进栈序列为a，b，c，则通过入出栈操作可
11、能得到的a，b，c的不同排列个数为( )。A、4B、5C、6D、7参考答案：B44. 具有65个结点的完全二叉树其深度为(根的层次号为1)( )。A.8B.7C.6D.5参考答案：B45. 已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为( )。A、q-next=s-next; s-next=pB、s-next=p; q-next=s-nextC、p-next=s-next; s-next=qD、s-next=q; p-next=s-next参考答案：A46. 线性表是具有n个( )的有限序列。A.字符
12、B.数据元素C.数据项D.表元素参考答案：B47. 非空的双向循环链表中任何结点的前驱指针均不为空。( )A.正确B.错误参考答案：A48. 对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )。A.顺序表B.用头指针表示的循环单链表C.用尾指针表示的循环单链表D.单链表参考答案：C49. 哈希表不需要进行比较便可以直接取得所查记录。( )A.正确B.错误参考答案：A50. 深度为h的满m叉树的第k层的结点(1=A.mk-1B.mk-1C.mh-1D.mh-1参考答案：A51. 取顺序表的第i个元素的时间与i的大小无关。( )A.正确B.错误参考答案：A52. 在单链表中设置头
13、结点的作用是( )。A.主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表指针不变B.便于查找C.便于连接D.快速插入记录参考答案：A53. 依次在初始为空的队列中插入元素X，Y，Z，W以后，紧接着作了两次删除操作，此时的队头元素是( )A.XB.YC.ZD.W参考答案：C54. 在一个长度为n的单链表L中，删除链表中*p的前驱结点的时间复杂度为O(n)。( )A、错误B、正确参考答案：B55. B+树应用在( )文件系统中。A.顺序B.散列C.VSAMD.ISAM参考答案：C56. 若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为O(n)。( )A、错误B、正确参
