西北工业大学22春《数据结构》综合作业二答案参考18

《西北工业大学22春《数据结构》综合作业二答案参考18》由会员分享，可在线阅读，更多相关《西北工业大学22春《数据结构》综合作业二答案参考18（14页珍藏版）》请在装配图网上搜索。

1、西北工业大学22春数据结构综合作业二答案参考1. 与单链表相比，双链表的优点之一是( )。A.插入、删除操作更简单B.可以进行随机访问C.可以省略表头指针或表尾指针D.顺序访问相邻结点更灵活参考答案：C2. 归并排序的辅助存储空间代价为O(1)。( )A.正确B.错误参考答案：B3. 向一个有127个元素原顺序表中插入一个新元素并保存原来顺序不变，平均要移动( )个元素。A.8B.63.5C.63D.7参考答案：B4. 设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有( )个空指针域。A.2m-1B.2mC.2m+1D.4m参考答案：B5. 从未排序序列中依次取出

2、一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。A.插入B.选择C.交换D.二路归并参考答案：A6. 二叉树中结点只有一个孩子时无左右之分。( )A、错误B、正确参考答案：A7. 带行表的三元组表是稀疏矩阵的一种( )。A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构参考答案：A8. 若用n表示图中顶点数目，则有( )条边的无向图成为完全图。A.nB.n-1C.n(n-1)2D.n(n+1)2参考答案：C9. 在k叉树中，无父母的结点称为( )。A.祖先B.根C.子孙D.叶参考答案：B10. 设结点A有3个兄弟结点且结点B

3、为结点A的双亲结点，则结点B的度数为( )A.3B.4C.5D.1参考答案：B11. 若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是( )。A.1234B.4132C.4231D.4213参考答案：C12. 对线性表进行二分查找时，要求线性表必须( )。A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且结点按关键字有序排列D.以链接方式存储，且结点按关键字有序排列参考答案：C13. 稀疏矩阵压缩存储后，必会失去随机存取功能。( )A.正确B.错误参考答案：A14. 队列允许在队尾删除，在队头插入。( )A.正确B.错误参

4、考答案：A15. 对长度为n的关键字序列进行堆排序的空间复杂度为( )。A.O(log2n)B.O(1)C.O(n)D.O(n*log2n)参考答案：B16. 结构就是用户定义的，( )的一个集合体。参考答案：不同数据类型17. 设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行( )趟的分配和回收才能使得初始关键字序列变成有序序列。A.3B.4C.5D.8参考答案：A18. 按层次次序将一颗有n个结点的完全二叉树的所有结点从1到n编号，当iA.2i-1B.2iC.2i+1D.不确定参考答案：B19. 先序遍历一棵二叉排序树得到的结点序列不一定是有序的序

5、列。( )A.正确B.错误参考答案：A20. 下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序?( )A.堆B.哈夫曼树C.二叉排序树D.AVL树参考答案：A21. 循环队列SQ采用数组空间SQ.base0，n-1存储其元素值，已知其头尾指针分别是front和rezr，则判断此循环队列Q为满队列的条件是( )。A.Q.front=Q.rearB.Q.rear!=Q.frontC.Q.front=(Q.rear+1)%nD.Q.front!=(Q.rear+1)%n参考答案：C22. 为使平均查找长度达到最小，当由关键字集合05，11，21，25，37，40

6、，41，62，84构建二叉排序树时，第一个插入的关键字应为( )。A.5B.37C.41D.62参考答案：B23. 下列排序中，某一趟结束后未必能选出一个元素放在其最终位置上的是( )。A.直接插入排序B.冒泡排序C.快速排序D.堆排序参考答案：A24. 邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。( )A.正确B.错误参考答案：B25. 已知循环队列的存储空间为数组data21，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为( )。A.5B.6C.16D.17参考答案：C26. 有关二叉树下列说法正确的是( )。A.

7、二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为2参考答案：B27. 取顺序表的第i个元素的时间与i的大小无关。( )A.正确B.错误参考答案：A28. 数据结构是带有结构的数据元素的集合。( )A.正确B.错误参考答案：A29. 若有18个元素的有序表存放在一堆数组A19中，第一个元素放A1中，现进行二分查找，则查找A3的比较序列的下标依次为( )。A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，3参考答案：D30. 下列四种基本的逻辑结构中，数据元素之间关系最弱的是( )。A.集合B.线性结构C.树形结构D.图状结构

8、参考答案：A31. 从未排序序列中挑选元素，并将其依次插入已排序序列(初始时为空)的一端的方法，称为( )。A.希尔排序B.归并排序C.插入排序D.选择排序参考答案：D32. 用有向无环图描述表达式(A+B)*(A+B)/A)，至少需要顶点的数目为( )。A.5B.6C.8D.9参考答案：A33. 下面关于串的叙述中，哪一个是不正确的?( )A.空串是由空格构成的串B.模式匹配是串的一种重要运算C.串是字符的有限序列D.串既可以采用顺序存储，也可以采用链式存储参考答案：A34. 二维数组A的每个元素是由6个字符组成的串，其行下标i=0，1，8，列下标为j=1，2，10。设每个字符占一个字节，若

9、按行先存储，元素A8，5的起始地址与A按列存储时起始地址相同的元素是( )。A.A8，5B.A3，10C.A5，8D.A0，9参考答案：B35. 链式队列Q为空的判定条件：( )A.Q.front=Q.rearB.Q.front=QC.Q=Q.rearD.没有正确参考答案：A36. 设串s1=Data Structures with Java，s2=it，则子串定位函数index(s1,s2)的值为( )。A、15B、16C、17D、18参考答案：D37. 串是一种特殊的线性表，其特殊性体现在( )。A.数据元素是一个字符B.数据元素可以是多个字符C.可以顺序存储D.可以链接存储参考答案：A3

10、8. 采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为( )。A.n/2B.nC.(n-1)/2D.(n+1)/2参考答案：D39. 链式栈与顺序栈相比，一个比较明显的优点是( )A.插入操作更加方便B.通常不会出现栈满的情况C.不会出现栈空的情况D.删除操作更加方便参考答案：B40. 通用的处理哈希冲突的方法有( )。A、开放定址法B、再哈希法C、链地址法D、建立公共溢出区参考答案：ABCD41. 二叉树中必有度为2的结点。( )A、错误B、正确参考答案：A42. 抽象数据类型的三个组成部分分别为( )。A、数据对象、数据关系和基本操作B、数据元素、逻辑结构和存储结构C、数据

11、项、数据元素和数据类型D、数据元素、数据结构和数据类型参考答案：A43. 在二叉树中插入结点，则此二叉树便不再是二叉树了。( )A.正确B.错误参考答案：B44. 最小生成树问题是构造带权连通图(网)的最小代价生成树。( )A.正确B.错误参考答案：A45. 对于双向链表，在两个结点之间插入一个新结点需修改的指针共( )个，单链表为( )个。A.4，1B.4，2C.1，4D.2，4参考答案：B46. 若进栈序列为a，b，c，则通过入出栈操作可能得到的a，b，c的不同排列个数为( )。A、4B、5C、6D、7参考答案：B47. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6

12、依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是( )。A.6B.4C.3D.2参考答案：C48. 对某二叉树进行前序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果为( )A.DBFEACB.DFEBCAC.BDFECAD.BDEFAC参考答案：B49. 设有100个关键字，用折半查找法进行查找时，最大比较次数为( )。A.7B.6C.50D.25参考答案：A50. 设某完全无向图中有n个顶点，则该完全无向图中有( )条边。A.n(n-1)/2B.n(n-1)C.n2D.n2-1参考答案：A51.

13、下列程序段for(i=1; iA.O(1)B.O(0)C.O(1+n)D.O(n)参考答案：D52. 在含100个结点的完全二叉树中，叶子结点的个数为36。( )A、错误B、正确参考答案：A53. 向顺序栈中压入新元素时，应当( )A.先移动栈顶位置，再存入元素B.先存入元素，再移动栈顶位置C.先后 次序无关紧要D.同时进行参考答案：A54. 在下列各种文件中，不能进行顺序查找的文件是( )。A.顺序文件B.索引文件C.散列文件D.多重表文件参考答案：C55. 指针p所指的元素是双向循环链表L的尾元素的条件是( )。A.p=LB.p=NULLC.p-prior=LD.p-next=L参考答案：

14、D56. 对于3个结点a、b、c，可构成不同的二叉树的棵数为( )。A.32B.30C.28D.24参考答案：B57. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为( )。A.O(n) O(n)B.O(n) O(1)C.O(1) O(n)D.O(1) O(1)参考答案：C58. 在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为( )。A.O(n)B.O(n+e)C.O(n2)D.O(n3)参考答案：B59. 求图的最小(代价)生成树问题，考虑的是下面的哪一种图?( )A.有向图B.无向图C.带权的有向图D.带权的无向图参考答案：D60. 按排序过程中依据的原则分类，快速排序属于( )。A.插入类的排序方法B.选择类的排序方法C.交换类的排序方法D.归并类的排序方法参考答案：C