《西北工业大学22春《数据结构》综合作业一答案参考93》由会员分享，可在线阅读，更多相关《西北工业大学22春《数据结构》综合作业一答案参考93（13页珍藏版）》请在装配图网上搜索。
1、西北工业大学22春数据结构综合作业一答案参考1. 具有线性结构的数据结构是( )A.赫夫曼树B.栈C.图D.树参考答案：B2. 内部排序是根据关键词的大小重新安排各( )的顺序。A.关键词B.数据项C.文件D.数据元素参考答案：B3. 在链表的结点中，数据元素所占的存储量和整个结点所占的存储量之比称作存储密度。( )A、错误B、正确参考答案：B4. 若一个有向图的邻接距阵中，主对角线以下的元素均为零，则该图的拓扑有序序列( )。A.一定存在B.一定不存在C.不一定存在D.不确定参考答案：A5. 若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为O(n)。( )
2、A、错误B、正确参考答案：A6. 若用n表示图中顶点数目，则有( )条边的无向图成为完全图。A.nB.n-1C.n(n-1)2D.n(n+1)2参考答案：C7. 对长度为n的关键字序列进行堆排序的空间复杂度为( )。A.O(log2n)B.O(1)C.O(n)D.O(n*log2n)参考答案：B8. 链式栈与顺序栈相比，一个比较明显的优点是( )A.插入操作更加方便B.通常不会出现栈满的情况C.不会出现栈空的情况D.删除操作更加方便参考答案：B9. 链式队列Q为空的判定条件：( )A.Q.front=Q.rearB.Q.front=QC.Q=Q.rearD.没有正确参考答案：A10. 在计算机
3、内实现递归算法时所需的辅助数据结构是( )。A、栈B、队列C、树D、图参考答案：A11. 不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。( )A.正确B.错误参考答案：A12. 取顺序表的第i个元素的时间与i的大小无关。( )A.正确B.错误参考答案：A13. 算法分析的目的是( )。A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易读性和文档性参考答案：C14. 允许对队列进行的操作有( )。A.对队列中的元素排序B.取出最近进队的元素C.在队头元素之前插入元素D.删除队头元素参考答案：D15. 二叉树是
4、度为2的有序树。( )A、错误B、正确参考答案：A16. 一棵含999个结点的完全二叉树的深度为12。( )A、错误B、正确参考答案：A17. 任何一个无向连通图的最小生成树( )。A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在参考答案：B18. 在对含n个结点的二叉树进行先序、中序和后序遍历时，其时间复杂度( )。A.都不相同B.完全相同C.先序和中序相同，而与后序不同D.中序和后序相同，而与先序不同参考答案：B19. 对5个不同的数据元素进行直接插入排序，最多需要进行( )次比较A.8B.10C.15D.25参考答案：B20. n个顶点的强连通图中至少含有( )。A.n-1条有向
5、边B.n条有向边C.n(n-1)/2条有向边D.n(n-1)条有向边参考答案：B21. 高度为5的完全二叉树中含有的结点数至少为( )。A、16B、17C、31D、32参考答案：A22. 一个有向无环图的拓扑排序序列是( )。A.一定唯一的B.一定不唯一的C.不一定唯一的D.都不对参考答案：C23. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。( )A.正确B.错误参考答案：B24. 用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。A.逆拓扑有序B.拓扑有序C.无序的D.A和B参考答案：A25. 一个队列的入队序列是1、2、3、
6、4，则队列的首次输出元素是( )。A.1B.2C.3D.4参考答案：A26. 散列函数有一个共同的性质，即函数值应当以下面的哪一项来取其值域的每个值?( )A.最小概率B.最大概率C.平均概率D.同等概率参考答案：D27. 在对链队列作出队操作时，不会改变front指针的值。( )A、错误B、正确参考答案：A28. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是( )。A.(rear+1)%n=frontB.rear=frontC.rear+1=frontD.(rear-l)%n=front参考答案：B29. 在一个图中所有顶点的度数之和等于所有边数的( )倍。A
7、.1/2B.2C.1D.4参考答案：B30. 对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。( )A、错误B、正确参考答案：B31. 通常将链串的结点大小设置为大于1是为了( )。A、提高串匹配效率B、提高存储密度C、便于插入操作D、便于删除操作参考答案：A32. 链表中的表头指针与表头结点起到相同的作用。( )A.正确B.错误参考答案：B33. 稀疏矩阵常用的压缩存储方法有两种，它们是( )。A.散列和十字链表B.二维数组和三维数组C.三元组和散列D.三元组和十字链表参考答案：D34. 队列的插入操作是在( )。A.队尾B.队头C.队列任意位置D.队头元素
8、后参考答案：A35. 算法有以下几种特性( )。A、有穷性B、确定性C、可行性D、输入和输出参考答案：ABCD36. 如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用( )。A.深度优先搜索算法B.广度优先搜索算法C.求最小生成树的prim算法D.拓扑排序算法参考答案：B37. 下列描述中正确的是( )。A.选择合适的数据结构是解决应用问题的关键步骤B.线性表的逻辑顺序与存储顺序总是一致的C.每种数据结构都具备查找、插入和删除三种基本运算D.数据结构实质上包括逻辑结构和存储结构两方面的内容参考答案：A38. 用链表表示线性表的优点是( )A.便于随机存取B.花费的存储空间比顺序表少C
9、.便于插入与删除D.数据元素的物理顺序与逻辑顺序相同参考答案：C39. 数据的逻辑结构是指数据的各数据项之间的逻辑关系。( )A.正确B.错误参考答案：B40. 由带权为9，2，5，7的四个叶子结点构造一颗哈夫曼树，该树的带权路径长度为( )。A.23B.37C.46D.44参考答案：D41. 线性表中的所有元素都有一个前驱元素和后继元素。( )A.正确B.错误参考答案：A42. 以下关于线性表的说法不正确的是( )。A.线性表中的数据元素可以是数字、字符、记录等不同类型B.线性表中包含的数据元素个数不是任意的C.线性表中的每个结点都有且只有一个直接前趋和直接后继D.存在这样的线性表：表中各结
10、点都没有直接前趋和直接后继参考答案：C43. 若链串结点中的指针占4个字节，每个字符占1个字节，则结点大小为2的链串的存储密度为2/6。( )A、错误B、正确参考答案：B44. 在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为( )。A.O(n)B.O(n+e)C.O(n2)D.O(n3)参考答案：B45. n个结点的线索二叉树上含有的线索数为( )。A.n-1B.n+1C.nD.2n参考答案：B46. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为( )。A.1和5B.2
11、和4C.4和2D.5和1参考答案：B47. 设某完全无向图中有n个顶点，则该完全无向图中有( )条边。A.n(n-1)/2B.n(n-1)C.n2D.n2-1参考答案：A48. 下面关于串的叙述中，哪一个是不正确的?( )A.空串是由空格构成的串B.模式匹配是串的一种重要运算C.串是字符的有限序列D.串既可以采用顺序存储，也可以采用链式存储参考答案：A49. 若进栈序列为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参考答案：B50. 若要在单链表中的结点p
12、之后插入一个结点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参考答案：A51. 插入、删除只能在同一端进行的线性表，称为( )。A.队列B.栈C.循环队列D.循环栈参考答案：B52. 二叉树中除叶结点外，任一结点X，其左子树根结点的值小于该结点X的值;其右子树根结点的值大于等于该结点X的值，则此二叉树一定是二叉排序树。( )A.正确B.错误参考答案：B53. 对线性表进行二分查找时，要求线性表必须( )。A.以顺
13、序方式存储B.以链接方式存储C.以顺序方式存储，且结点按关键字有序排列D.以链接方式存储，且结点按关键字有序排列参考答案：C54. 一棵左右子树均不空的二叉树在前序线索化后，其中空的链域的个数是( )。A.不确定B.2C.1D.0参考答案：C55. 对于3个结点a、b、c，可构成不同的二叉树的棵数为( )。A.32B.30C.28D.24参考答案：B56. 栈下溢是指在栈空时进行出栈操作。( )A、错误B、正确参考答案：B57. 线性表是具有n个( )的有限序列。A.字符B.数据元素C.数据项D.表元素参考答案：B58. 设某算法的问题规模函数f(n)=300n2+8000n+900，则它的渐进时间复杂度为( )A.O(n3)B.O(n2)C.O(n)D.O(1)参考答案：B59. 含n个顶点的无向连通图中至少含有n条边。( )A、错误B、正确参考答案：A60. 对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的左孩子的编号为98。( )A、错误B、正确参考答案：B
西北工业大学22春《数据结构》综合作业一答案参考93
