2022年数据结构题库

1、无向图G的邻接矩阵一定是(A)。

2、(3分)对线性表进行二分查找时,要求线性表必须是(C)。

3、与数据存储结构无关的概念是( 。

4、以下说法正确的是( )

5、设某顺序表中第一个元素的地址是se(下标从1开始),每个结点占m个单元,则第i个结点的地址为

6、在下面的程序段中,x=x+1;的语句频度为( )。for( i=1;i<=n;i++)  for(j=1;j<=n;j++) x=x+1;

7、算法分析的目的是

8、设森林T中有4棵树,其结点个数分别为n1,n2,n3,n4,那么当森林T转换成一棵二叉树后,则根结点的右子树上有( )个结点

9、下述哪一条是顺序存储结构的优点

10、对序列{15,9,7,8,20,-1,4}进行排序,进行一趟后数据的排列变为{9,15,7,8,20,-1,4},则采用的排序方法是

11、顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第五个元素的地址是(   )

12、用邻接表表示图进行广度优先遍历时，通常借助（ ）来实现算法。

13、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（ ）。

14、对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数最多为（ ）。

15、若一组记录的排序码为（46, 79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。

16、按照二叉树的定义，具有三个节点的二叉树有（ ）种

17、设单链表中指针p指向结点a，若要删除p之后的结点（若存在），则需修改指针的操作为（）。

18、下列叙述中正确的是()

19、一棵二叉树共有 25 个结点,其中 5 个是叶子结点,则度为 1 的结点数为()

20、下列与队列结构有关联的是()。

21、设某棵树的度为 3,其中度为 3,2,1 的结点个数分别为 3,0,4。则该树中的叶子结点数为()

22、深度为k的完全二叉树中最少有（ ）个结点。

23、设无向图G中有n个顶点，则该无向图的最小生成树上有（ ）条边。

24、程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的时间复杂度为（ ）。

25、线性链表是通过何种方式表示元素之间的关系（ ）。

26、在一棵平衡二叉树中,每个结点的平衡因子的取值范围是( )。

27、以下关于快速排序的叙述中正确的是( )。

28、在以下排序方法中,平均时间复杂度为O(n2),且是不稳定的是(

29、下述几种排序方法中,要求辅助内存最大的是( )。

30、算法在发生非法操作时可以作出相应处理的特性称为算法的（ ）。

31、在解决计算机主机和打印机之间速度不匹配问题时,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个( )结构。 (4.0分)

32、单链表是由一个一个( )链接而成。 (3.0分)

33、若一个图中有k个连通分量,若按照图的深度优先遍历访问所有顶点,则必须调用( )次深度优先遍历算法。 (5.0分)

34、二叉树的第k层的结点数最多为

35、设二叉排序树上有n个结点,则在二叉排序树上查找结点的最多的时间复杂度()

36、对20个的元素的线性表进行查找时,第一个元素的命中概率为0.5,其他元素命中概率一样(不考虑查找失败),则平均查找长度为。

37、设一组初始记录关键字序列为(Q,H,C,Y,P,A,M,S,R,D,F,X),则按字母升序的第一趟冒泡排序结束后的结果是( )。

38、对于一个具有n个顶点和e条边的有向图和无向图,在其对应的邻接表中,所含边结点分别( )个。

39、算法分析的目的是( )。 (5.0分)

40、*在单链表p结点之后插入s结点的操作是( )

41、设有序表的关键字序列为{1,3,9,12,32,41,45,62,75,77,82,95,100}，当采用二分查找法查找值为82的节点时，经( )次比较后查找成功。

42、*给定排序码值序列为{F，B，J，C，E，A，I，D，C，H}，对其按字母的字典序列的次序进行排列，希尔( Shell )排序的第一趟(d1=5)结果应为（ ）。

43、顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（ ）。（1分）

44、对于长度为 18 的顺序存储的有序表，若采用二分查找，则查找第 15 个元素的查找长度为 （） 。（1分）

45、有一个结构体及其变量定义如下： struct date{Int year; int month; int day;}birthday;此时要调用变量中的 year，正确的书写格式是（ ）

46、设 al，a2， a3 为三个结点； p , 10 , 20 代表地址，则如下的链表存储结构称为（ ）

47、若栈采用顺序存储方式存储，现两栈共享空间 V[m]，top[i]代表第 i 个栈( i =1,2)栈顶，栈 1 的底在 v[0]，栈 2 的底在 V[m-1]，则栈满的条件是（ ）

48、用链式存储的栈，在进栈操作时，将要进栈的结点放在链表的（ ）

49、队列的“先进先出”特性是指（ ）

50、n 个顶点的无向图的邻接表最多有（ ）个表结点。