往年数据结构

1、下面给出的四种排序法中( D )排序法是不稳定性排序法。

2、下列数据中,( C )是非线性数据结构。

3、已知有向图G=(V. E), 其中V={V1, v2, V3,V4}. E={,,,}, 图G的拓扑序列是(A) 。

4、无向图中所有顶点的度数之和与所有边数之比是(C) 。

5、(3分)假设有一个有序关键字序列为,(05,, 13, 19,21. 37. 56,64, 75, 80,88,92}, 当二分查找关键字值为64的结点时,查找成功的比较次数是(B)。

6、(10分)已知关键字序列为(66,82, 25, 51, 98, 108}, 利用快速排序方法,以第- 一个元素为基准得到的一 趟排序结果为(D)。

7、串是()。

8、表达式a*(b+c)-d的后缀表达式是

9、当待排序的整数是有序序列时，采用 ( ) 方法比较好，其时间复杂度为O(n)

10、算法的时间复杂度取决于

11、在一棵二叉树上第4层的结点数最多为

12、当待排序的整数是有序序列时，无论待排序序列排列是否有序，采用 （ ）方法的时间复杂度都是O(n2)

13、数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要

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

15、在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为

16、栈和队列共同点是

17、链接存储的特点是利用什么来表示数据元素之间的逻辑关系

18、在一棵二叉树中，度为0的结点数为n0，度为2的结点数为n2，则n0=

19、若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（ ）种情况。

20、在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（ ）。

21、设有10阶矩阵A，其对角线以上的元素aij均取值为-3，其他矩阵元素为正整数，现在将矩阵A压缩存放在一维树组F[m]中，则 m为（ ）。

22、采用邻接表存储的图的深度优先遍历算法类似于二叉树的（ ）

23、一个栈的初始状态为空。现将元素 1、2、3、4、5、A、B、C、D、E 依次入栈,然后再依次出栈,则元素出栈的顺序是()

24、设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过（ ）次比较。

25、关于哈夫曼树，下列叙述正确的是（ ）。

26、设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（ ）。

27、线性表（ a1,a2,...,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ ）。

28、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度（ ）。(1<=i<=n+1)。

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

30、对于100个长度不等的初始归并段,构建5路最佳归并树时,需要增加( )个虚段。

31、在单链表中删除结点p的后继结点,正确的操作是( )。 (3.0分)

32、对于顺序表的优缺点,以下说法不正确的是( )。 (3.0分)

33、将10个元素散列到1000000个单元的哈希表,则( )产生冲突。

34、具有线性结构的数据结构是( )。

35、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量,以下解释错误的是( )

36、由二叉树的前序和后序遍历序列( )惟一确定这棵二叉树。

37、设一组初始记录关键字序列(5,2,6,3,8),以第一个记录关键字5为基准进行一趟快速排序的结果为( )。

38、设有n个待排序的记录关键字,则在堆排序中需要( )个辅助记录单元。

39、用链接方式存储的队列,在进行删除运算时( )。

40、设某无向图有20个顶点,则该无向图的邻接表中有( )个表头结点。

41、在一棵度为4的树T中,若有20个度为4的结点,20个度为3的结点,1个度为2的结点,10个度为1的结点,则树T的叶结点个数是( )。

42、当待排序序列基本有序时,以下排序方法中,( )最不利于其优势的发挥。 (2.0分)

43、顺序表中，插入一个元素所需移动的元素平均数是（）。（1分）

44、一个向量第一个元素的地址是 100，每个元素的长度为 2，则第 5 个元素的地址是（ ）

45、以下链表结构中，从当前结点出发能够访问到任一结点的是（ ） 分值：6 分

46、设一个链表最常用的操作是在末尾插入结点，则选用（ ）最节省时间。

47、后缀表达式“4 5 * 3 2 + -”的值为（ ）

48、设有一个顺序栈 S，元素 1, 2, 3, 4, 5, 6 依次进栈，如果 6 个元素的出栈顺序为 2, 3, 4, 6, 5, 1，则顺序站的容量至少可以存储（ ）个元素

49、在一棵二叉树的二叉链表中，空指针域等于所有非空指针域数加（ ）

50、对于一个具有 n 个顶点和 e 条边的无向图，若采用邻接表示，则顶点表向量的大小和所有邻接表中的结点总数分别是（）。