往年数据结构样卷

1、下列关于算法输出的叙述中,正确的是( )。

2、(4分)若栈采用链式存储结构,则下列说法中正确的是(B)。

3、(4分)栈结构通常采用的两种存储结构是(A)。

4、(3分)在散列查找中处理)冲突时,可以采用开放定址法。下列不是开放定址法的是(D) 。

5、(4分)已知一个长度为13的有序表,按二分查找法对该表进行查找,在表内各元素等概率情况下,查找成功的平均查找长为(A)。

6、(3分)设有一组关键字(19.14, 23.1.6.20.4275.1109),用散列函数H(key)=key%13构造散列表,用拉链法解决冲突,散列地址为1的链中记录个数为(C) 。

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

8、以下说法正确的是()。

9、给定排序码值序列为{F，B，J，C，E，A，I，D，C，H}，对其按字母的字典序列的次序进行排列，快速排序的第一趟排序结果为

10、假设以行序为主序存储二维数组A=array[1...100,1...100],设每个数组元素占2个存储单元,基地址为10,则LOC[5,5]=

11、关于顺序表的说法不正确的是？

12、在一个图中，所有顶点的度数之和等于所有边数的（ ）倍

13、通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ ）。

14、下面程序段的时间复杂性的量级为（）。Int fun(int n){I=1,s=1;While(s

15、下面程序段的时间复杂性的量级为（）For (i=1;i<=n;i++) For(j=1;j<=I;j++) For(k=1;k<=j;k++) x=x+1;

16、假定利用数组A[N]顺序存储一个栈，top表示栈顶指针，已知栈未满，则x入栈时所执行的操作是（ ）。

17、设有两个串p和q，求p和q首次出现的位置的运算称作( )

18、表长为n的顺序存储的线性表，当在任意位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为（D、 ），删除一个元素需要移动元素的平均个数为（ ）

19、设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为（ ）。

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

21、下列算法suanfa1中语句"x=x*2；"的执行次数是（ ）。
void suanfa1(int n)
{ int i,j,x=1；
for(i=1；i<=n；i++)
for(j=i；j<=n；j++)
x=x*2；
printf("%d",x)；
}

22、设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（ ）。

23、下列程序段的时间复杂度为（ ）。
for(i=0； i

24、下面叙述正确的是（ ）。

25、以下排序方法中,( )不需要进行关键字的比较。

26、链表的特点是利用( )来表示数据元素之间的逻辑关系。 (3.0分)

27、含n个顶点的连通图中的任何一条简单路径,其长度不可能超过( )。 (4.0分)

28、二叉树的深度为k,则二叉树最多有( )个结点。 (3.0分)

29、下面叙述正确的是( )。

30、下面程序段的时间复杂度为( )。 i=1; while(i<=n) i=i*3;

31、队列的插入操作是在( )。

32、采用稀疏矩阵的三元组表形式进行压缩存储,若要完成对三元组表进行转置,只要将行和列对换,这种说法( )。

33、对广义表L=((a,b),((c,d),(e,f)))执行head(tail(head(tail(L))))操作的结果是( )。

34、二叉数有1000个结点,它的深度至少为( )。

35、用链接方式存储的带头结点的队列,在进行插入运算时

36、如果让元素1,2,3,4,5,6,7依次进栈,则出栈次序不可能出现( )的情况

37、数据的最小单位是( )。

38、已知一组关键字为 (19,14,23,1,68,20,84,27,55,11,10,79),散列函数H(key)=keyi%13,用链地址法处理冲突,则这些单链表中,具有最多结点数的链表的结点数是( )?

39、数据的运算定义在数据的逻辑结构上,只有确定了( ),才能具体实现这些运算。 (5.0分)

40、用二分查找法查找具有n个结点的顺序表时,查找每个结点的平均比较次数是( )。 (5.0分)

41、线性表的顺序存储结构是一种( )的存储结构，线性表的链式存储结构是一种( )存储结构。

42、*给定排序码值序列为{F，B，J，C，E，A，I，D，C，H}，对其按字母的字典序列的次序进行排列，希尔( Shell )排序的第一趟(d1=5)结果应为（ ）。

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

44、两类存储结构为（ ）

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

46、判定一个非循环的顺序队列 Q（最多元素为 MAXSIZE）为满队列的条件是（ ）

47、数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为（ ）

48、在一棵具有 35 个结点的完全二叉树中，该树的深度为（ ）

49、在一棵深度为 k 的完全二叉树中，所含结点个数至少（ ）

50、已知某二叉树的前序遍历序列是 ABDEFGC，中序序列是 DEBGFAC，则对应的二叉树为（ ）图 A 图 B 图 C 图 D