算法与数据结构题库附答案

1某算法的时间复杂度是O(n2)表明该算法( )。

A 问题规模是n2B 问题规模与n2成正比

C 执行时间等于n2 D 执行时间与n2成正比

A. 递归部分 B. 结束条件和递归部分C. 迭代部分 D. 结束条件和迭代部分

12. 从逻辑上看可以把数据结构分为__________两大类

A．动态结构、静态结构 B．顺序结构、链式结构

C．线性结构、非线性结构 D．初等結构、构造型结构

13、若在长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为( )。

14. 采用顺序搜素方式搜索长度为n的线性表时在等概率情况下，搜索成功时的平均搜索长度为__________

15、非空的循环单链表first的链尾结点(由p所指向)满足( )。

16、用S表示进栈操作用X表示出栈操作，若元素嘚进栈顺序是1234为了得到1342的出栈顺序，相应的S和X的操作序列为( )

17、含有129个叶结点的完全二叉树，最少有( )个结点

18、一个有向图G的邻接表存儲如图(1)所示，现按深度优先搜索方式从顶点A出发执行一次遍历所得的顶点序列是( )。

19、树最合适用来表示( )

A 有序数据元素B 元素之间具有分支层次关系的数据

C 无序数据元素D 元素之间无联系的数据

20、一棵有124个叶结点的完全二叉树最少有( )个结点。

21、图(1)给出的一棵二叉搜索树对应嘚二叉判定树如图(2)所示，它的搜索成功的平均长度是( )

图(1)二叉搜索树 图(2)二叉判定树

23、对5个不同的数据元素进行直接插入排序，最大需要进荇( )次比较

24、将一个n×n的对称矩阵A的下三角部分按行存放在一个一维数组B中，A[0][0]存放在B[0]中那么第i行的对角元素A[i][i]在B中的存放位置是( )。

26、顺序搜索法适合于存储结构为( )的线性表

A 散列存储 B 顺序存储或链式存储C 压缩存储 D索引存储

27、采用折半搜索方式搜索一个长度为n的有序顺序表时，其平均搜索长度为( )

28、n个结点的线索二叉树中，线索的数目是( )

29、若数据元素序列{11,12,13,7,8,9,23,4,5}是采用下列排序方法之一得到的第二趟排序后的结果，则该排序方法只能是( )

A 插入排序B 选择排序C 交换排序D 归并排序

30、为了增加内存空间的利用率和减少溢出的可能，在两个栈共享一片连续的存储空间时应将两个栈的栈顶分别设在这片存储空间的两端，当( )时才产生上溢

A 两个栈的栈顶同时到达栈空间的中心点

B 其中一个栈的栈頂到达栈空间的中心点

C 两个栈的栈顶在栈空间的某一位置相遇

D 两个栈的栈顶相加超过了栈空间的最大容量

31、设一棵二叉树的中序序列为badce，後序遍历为bdeca则该二叉树前序遍历的顺序是( )。

《数据结构》期末试题及答案

学姩第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上在本试卷上做答无效） 一、选择（每题 1 分，共 10 分） 1.长度为 n 的线性表采用順序存储结构在其第 i 个位置插入一个新元素的算法时间复 杂度为（ ） 2 A.O(0) B.O(1) C.O(n) D.O(n ) 2.六个元素按照 6，54 ，32，1 的顺序入栈下列哪一个是合法的出栈序列？（ ） 5.若一棵二叉树具有 10 个度为 2 的结点5 个度为 1 的结点，则度为 0 的结点个数是 （ ） A.9 B.11 C.15 D. 不确定 6.下列哪一个方法可以判断出一个有向图是否有環（ ） A. 深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第 7 层有 10 个叶子结点的完全二叉树不可能有（ 以顺序方式存储 B. 以顺序方式存储，且数據元素有序 C.以链接方式存储 D.以链接方式存储且数据元素有序 二、填空（每空 1 分，共 15 分） 1.数据结构中评价算法的两个重要指标是 、空间复雜度 2.在单链表中， 指针 P 所指结点有后继的条件是