数据结构冲刺卷

1、以下各阶时间复杂度中,性能最优的是( )。

2、链表不具有的特点是( B )

3、将长度为n的单链表连接在长度为m的单链表之后,其算法的时间复杂度为(B)。

4、(4分)若已知一个栈的入栈序列是1, ....其输出序列为p.p.....,都1=n,则p为(C)。

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

6、(3分)下列关于无向连通图特性的叙述中,正确的是(B)。

7、(3分)若一棵具有n(n>0)个结点的二叉树的先序序列与后序序列正好相反,那么这棵:二叉树- -定是(C) 。

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

9、(3分)若图G为n个顶点的有向图,则图G中最多有(A)条边。.

10、线性表采用链式存储时,其地址()

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

12、栈和队列都是()。

13、若一个栈的输入序列是1、2……N,输出序列的第一个元素是N,则第I个输出元素为()。

14、一棵有 n 个顶点的生成树有且仅有( )条边。

15、下面叙述正确的是

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

17、衡量查找算法效率的主要标准是

18、假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为

19、创建一个包括n个结点的有序单链表的时间复杂度是（ ）。

20、对22个记录的有序表作折半查找，当查找失败时，至少需要比较（ ）次关键字。

21、设哈夫曼树中有199个结点，则该哈夫曼树中有（ ）个叶子结点。

22、当在一个有序的顺序存储表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（ ）

23、设循环队列的存储空间为 Q(1:35),初始状态为 front=rear=35。现经过一系列入队与退队运算后,front=15,rear=15,则循环队列中的元素个数为()。

24、设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（ ）。

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

26、设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（ ）。

27、链表是一种采用（ ）存储结构存储的线性表。

28、设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ ）个空指针域。

29、difference(A,B,C)表示求集合A和B的差集C。若A={b,c,d},B={c,e},则difference(A,B,C)运算后C=（ ）。

30、以下叙述错误的是（ ）。

31、数据采用链式存储结构时，要求( )

32、哈希查找的基本思想是根据()来决定元素的存储地址

33、有n个十进制整数进行基数排序,其中最大的整数为5位,则基数排序过程中临时建立的队数个数是( ) 。

34、算法能正确的实现预定功能的特性称为算法的（ ）。

35、线性链表不具有的特点是

36、一个队列的入队序列是a,b,c,d，则队列输出序列是

37、在一个长度为n的顺序表的第i个元素（1≤i≤n）之前插入一个元素时，需向后移动()个元素。

38、已知一个有序表为{13，18，24，35，47，50，62，83，90，115，134}，当二分查找为18的元素时，需()次比较可查找成功。

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

40、单链表不具备的特点是( )。 (3.0分)

41、设某有向图的邻接表中有n个表头结点和m个边结点,则该图中有( )条有向边。

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

43、给定一个无序的单链表,要求的空间复杂度为O(1),则建立一个长度为n的有序单链表的时间复杂度为( )

44、设顺序表的长度为11,则顺序查找的平均比较次数为( )。

45、在数据结构中,从逻辑上可以把数据结构分成( )。 (5.0分)

46、下列排序方法中,( )所需的辅助空间最大。 (2.0分)

47、在具有n个结点的单链表上查找值为x的元素时，其时间复杂度为（）。（1分）

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

49、一棵深度为 h 的满 k 叉树有如下性质：第 h 层上的结点都是叶子结点， 其余各层上的每个结点都有 k 棵非空子树。 如果按层次顺序（同层自左至右） 从 1 开始对全部结点编号，则：第 i 层结点数目是（ ）

50、任何一棵二叉树的叶结点在前（先）序、中序和后序遍历序列中的相对次序（ ）