数据结构

1、下列排序方法中,哪一个是稳定的排序方法?( B )。

2、数据序列(8,9,10,4,5,6,20,1,2)只能是下列排序算法中的( C )的两趟排序后的结果。

3、下述哪一条是顺序存储结构的优点?( A )。

4、以下数据结构中,( A )是非线性数据结构

5、(3分)在一棵二叉树中,度为2的结点数为15,度为1的结点数为3,则叶子结点数为(B) 。

6、(3分)下列关于无向图广度优先搜索序列的叙述中,正确的是(C) 。

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

8、(4分)判定-一个栈ST (最多元素为m)为栈满的条件是(D)。

9、算法分析的两个主要方面是() 。

10、(4分)在一个单链表中,若删除p指向结点的后继结点,则执行的操作为(A)。

11、在图G中求两个结点之间的最短路径可以采用的算法是(A)。

12、下列选项中( )可能是在二叉排序树中查找 35 时所比较的关键字序列。

13、设有两个串p和q,其中q是p的子串,求q在p中首次出现的位置的算法称为()。

14、由三个结点构成的二叉树，共有（ ）种不同的形态

15、设有100个元素，用折半查找法进行查找时，最大、最小比较次数分别时

16、对于一个具有n个结点的单链表,在已知的结点*p后插入一个新结点的时间复杂度和在给定值为x的结点后插入一个新结点的时间复杂度分别为

17、线性表的链式存储结构是一种（ ）存储结构

18、用冒泡排序方法对n个记录按排序码值从小到大排序时，当初始序列是按排序码值从大到小排列时，与码值总比较次数是

19、最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（ ）。

20、向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 的元素个数为（ ）。

21、n（n≥2）个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是（ ）。

22、由3个结点可以构造出多少种不同的二叉树？（ ）

23、在栈顶一端可进行的全部操作是（ ）。

24、在数据结构中，与所使用的计算机无关的是数据的（）结构

25、下列各种排序算法中平均时间复杂度为O(n2)是（ ）。

26、对n个记录的文件进行快速排序，所需要的辅助存储空间大致为（ ）。

27、时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（ ）。

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

29、求单链表中当前结点的后继和前趋的时间复杂度分别是（ ）。

30、为实现快速排序法,待排序序列最好采用的存储方式是( )。

31、算法的计算量大小称为算法的（ ）。

32、栈和队列都是( )。 (4.0分)

33、假设顺序表中的每个数据元素在存储器中占用d个字节的存储单元,若第一个元素a0的存储地址为Loc(a0),则ai的存储地址为( )。 (3.0分)

34、在一个长度为n的顺序表中删除一个结点的平均移动次数为( )。 (3.0分)

35、双向链表的每一个结点有( )个地址域(指针域/引用域)。 (3.0分)

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

37、算法是( )。

38、设无向图G中有n个顶点e条边,则其对应的邻接表中的表头结点和表结点的个数分别为( )。

39、设无向图G中有50个顶点,则该无向图的最小生成树上有( )条边。

40、设输入序列为1、2、3、4、5、6,则通过栈的作用后可以得到的输出序列为( )。

41、下列关键字序列中,( )是堆。

42、i = 1;While(i <= n) i = i * 3;

43、队和栈的主要区别是（）。（1分）

44、已知一个有序表为（11，22，33，44，55，66，77，88，99），则折半查找55需要比较（ ）次。（1分）

45、有结构体定义及结构体类型数组如下： struct worklist{Int no;Char name[20]; char sex;}person[5];需要给结构体数组中第 2 个变量的 no 成员赋值为 5，正确的写法是（ ）

46、分析以下程序段，其时间复杂度为 T（n）=（ ） i=1;While(i<=n) i=3*i;

47、已知输入序列为 abcd 经过队列后能得到的输出序列有（ ）

48、树中所有结点的度等于所有结点数加（ ）。

49、表示一个有 100 个顶点，1000 条边的无向图的邻接矩阵有（ ）个非零矩阵元素。

50、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为