数据结构

1、在一个图G中,所有顶点的度数之和等于所有边数的。

2、当采用分块查找时,数据的组织方式为()。

3、给定一段文本中的4个字符(u, v, w. x)及其出现频率(fu, fv, fw, fx) ,若对应的哈夫曼编码为u:00, v:010,w:011, x:1,则下列哪组频率可能对应(fu, fv, fw. fx) ? (B)。

4、若带头结点的单链表的头指针为head,则判断链表是否为空的条件是(B)。

5、(4分)顺序表中有10个数据元素,若第- 一个元素的存储地址是1000, 则最后-一个元素地址是1036,第5个元素的地址是(B)。

6、(2分)在具有6个顶点的无向图G至少应有(D )条边才能确保是一一个连通图。

7、设散列表长m=13.散列函数h (key). =key%11。 表中已有4个结点: h (15) =4, h (27) =5,h (39) =6,h(51) =7,其余地址为空,若采用二C次探查法处理冲突,则关键字为49的结点地址是(D)。

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

9、(6分)数据的逻辑结构可以分为()。

10、设指针P指向双链表的某一结点, 则双向链表结构的对称性可用(A)式来刻画。

11、对含有 10 个数据元素的有序查找表执行折半查找,当查找失败时,至少需要比较( )次。

12、设循环队列中数组的下标范围是0~n-1,其头尾指针分别为f和r,则其元素的个数为()。

13、在平衡二叉树中,每个结点的平衡因子的取值范围为( )。

14、字符串采用结点大小为1的链表作为其存储结构,是指()。

15、若SUBSTR(S,i,k)表示求S中从第i个字符开始的连续k个字符组成的子串的操作,则对于S=“Beijing&Nanjing”,SUBSTR(S,4,5)=()。

16、已知线性表L=(a1,a2,…,ai,…,an),下列说法正确的是()。

17、两个字符串相等的条件是()。

18、线性表是()。

19、具有n(n>0)个结点的完全二叉树的深度为

20、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用(B)存储方式最节省运算时间

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

22、为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。

23、下面关于二分查找叙述正确的是（ ）

24、下述几种排序方法中，要求内存量最大的是（ ）

25、一棵二叉树第五层的结点数最多为（ ）

26、设栈的顺序存储空间为 S(1:m),初始状态为 top=0。现经过一系列正常的入栈与退栈操作后,top=m+1,则栈中的元素个数为()。

27、下列排序法中,每经过一次元素的交换会产生新的逆序的是()。

28、设循环队列的存储空间为 Q(1:100),初始状态为空。现经过一系列正常操作后,front=49,则循环队列中的元素个数为()。

29、设有100个元素的有序表,采用折半查找方法,成功时最大的比较次数是()

30、对n个不同的关键字进行递增冒泡排序,在下列哪种情况下比较的次数最多( )。

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

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

33、若某棵二叉树的结点的前序排列和后序排列序列相同,则该二叉树( )。 (3.0分)

34、对某二叉树进行先序遍历的结果为ABDEFC,中序遍历的结果为DBFEAC,则后序遍历的结果是( )。 (3.0分)

35、不含任何结点的空树( )。

36、对n个不同的记录按排序码值从小到大次序重新排列,用快速排序方法,在 ( ) 情况下排序码值总比较次数最多。

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

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

39、设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n,则这棵二叉中共有( )个结点。

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

41、如果X是二叉中序线索中有一个左孩子的结点,且X不为根,则X的前驱为( )。

42、下面程序段执行的时间复杂度为( )。 public static void main(String[] args) { int i=1,n=100; while(i<=n){ i= i *2; } System.out.println(i); } (5.0分)

43、对一组数据(84, 47, 25, 15, 21) 排序,数据的排列次序在排序的过程中的变化为: (1)15 47 25 84 21 (2)15 21 25 84 47 (3)15 21 25 84 47 (4)15 21 25 47 84 则采用的排序是( )。 (2.0分)

44、在对一组关键字序列{70,55,100,15,33,65,50,40,95},进行直接插入排序时,把65插入,需要比较( )次。 (2.0分)

45、线性结构通常采用的两种存储结构是（ ）

46、在长度为 n 的顺序表中，若要删除第 i (1≤i≤n ）个元素，则需要向前移动元素的次数为（ ）

47、利用数组 a[N]存储一个顺序栈时，用 top 标识栈顶指针，已知栈未满，当元素 x 进行进栈时执行的操作是（ ）

48、一个递归算法必须包括（ ）。

49、下列命题正确的是（ ）

50、n 个顶点的强连通图，若该连通图含有最少的边，其形状是（ ）。