数据结构

1、若要求尽可能快地对序列进行稳定的排序,则应选( B )。

2、下列排序算法中,其中( D )是稳定的。

3、(4分)在带头结点的双向循环链表中插入一个新结点,要修改的指针域数量是(C)。

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

5、(3分)下列选项中,其平均查找性能与基于二叉排序树的查找相当的是(A) 。

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

7、(3分)顺序查找表长为n的线性表,在等概率情况下, 查找成功的平均查找长度是(B) 。

8、(10分)有一组记录的关键序列为(46,79,56,38,40,84). 利用快速排序的方法,以第一一个纪录为基准得到的一 趟排序结果为(A)。

9、折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中（ ）比较大小，查找结果是失败

10、最大容量为n的循环队列,队尾指针为rear,队头指针为front,则队空的条件是

11、一个具有n个顶点的无向图最多有( )边

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

13、对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则占用的存储空间为

14、不含任何结点的空树

15、折半搜索与二叉排序树的时间性能（ ）。

16、对n个不同的关键字由小到大进行冒泡排序，在下列（ ）情况下比较的次数最多。

17、设广义表L=((a,b,c))，则L的长度和深度分别为（ ）。

18、二维数组A的每个元素是由10个字符组成的串，其行下标i=0,1,…,8,列下标j=1,2,…,10。若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素（ ）的起始地址相同。设每个字符占一个字节。

19、广义表A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))的值为（ ）。

20、队列的特点是（）。

21、数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为（ ）。

22、设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ ）。

23、设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（ ）。

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

25、设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（ ）个元素。

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

27、队列的删除操作是在( )。 (4.0分)

28、若一颗二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是( )。 (3.0分)

29、若串S=”abcdefghi”,其非空子串数目是( )。

30、对n个不同的记录按排序码值从小到大次序重新排列,用直接插入排序方法,初始序列在 ( ) 情况下,排序码值总比较次数最多。

31、在下列对顺序表进行的操作中,算法时间复杂度为O(1)的是( )。

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

33、函数substr(“DATASTRUCTURE”,5,9)的返回值为( )。

34、设一条单链表的头指针变量为head且该链表没有头结点,则其判空条件是( )。

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

36、折半查找有序表(4,6,10,12,20,30,50,70,88,100)。若查找表中元素128,则它将依此与表中( )比较大小,查找结果失败。

37、数据表中有10000个元素,如果仅要求求出其中最大的10个元素,则采用( )算法最节省时间。

38、由4个结点可以构造出多少种不同的二叉树?

39、设F是一个森林,B是由F变换得到二叉树。若F中有n个非终端(叶子)结点,则B中右指针域为空的结点有( )个。

40、下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。 (2.0分)

41、折半查找有序表(4,6,10,12,20,30,50,70,88,100)。若查找表中元素58,则它将依次与表中 ( )比较大小,查找结果是失败。 (5.0分)

42、在数据的存放无规律而言的线性表中进行检索的最佳方法是( )。 (5.0分)

43、算法是（）。（1分）

44、一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当用二分查找值为82的结点时，查找成功时的比较次数为（ ）。（1分）

45、下列排序方法中，平均时间性能为O(nlogn)且空间性能最好的是（）。（1分）

46、不带头结点的单链表 L 为空的条件是（ ）

47、一个顺序栈一旦被声明，其最大占用空间的大小（ ）

48、为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时，只有当（ ）时，才产生上溢。

49、设无向图 G 中顶点数为 n，则图 G 至多有（）条边。

50、深度为5的二叉树至多有____个结点