2022年数据结构样卷

1、在带权图的最短路径问题中,路径长度是指。

2、下列数据中,( C )是非线性数据结构。

3、对数据进行顺序存储时,存储单元的地址( A )。

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

5、一棵二叉树的前序遍历序列为ABCDEFG,它的中序遍历序列可能是( B )

6、已知有向图G=(V. E), 其中V={V1, v2, V3,V4}. E={,,,}, 图G的拓扑序列是(A) 。

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

8、(4分)下列关于队列的叙述中,错误的是(D)。

9、在下列查找方法中,平均查找长度与结点数量无直接关系的是(C) 。

10、在一个具有n个单元的顺序栈中,假定以地址低端(即0单元)作为栈底,以top作为栈顶,当做出栈处理时,top变化为()。

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

12、一个栈的输入序列为123…n,若输出序列的第一个元素是n,输出第i(1<=i<=n)个元素是()。

13、串是一种特殊的线性表,其特殊性体现在()。

14、假定在一棵二叉树中,度为 2 的结点的数目为 6,则该二叉树中叶子结点的数目是( )。

15、空的单循环链表L的尾结点*p,满足()。

16、在稀疏矩阵的三元组顺序表中,每个三元组表示

17、在查找过程中，若同时还要增、删工作，这种查找称为

18、如果含有n个顶点的图形成一个环,则它有( )棵生成树

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

20、某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那么下面关于数据对象、数据元素、数据项描述正确的是

21、链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（ ）。

22、数组A[0..4,-1..-3,5..7]中含有元素的个数（ ）。

23、对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（ ）。

24、按照二叉树的定义，具有三个节点的二叉树有（ ）种

25、若广义表A满足heaD(A)=tail(A),则A为（ ）。

26、在数据结构中，从逻辑上可以把数据结构分为（）

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

28、设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（ ）。

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

30、设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是（ ）。

31、关于哈夫曼树，下列叙述正确的是（ ）。

32、非线性结构是数据元素之间存在一种：( )。

33、下列算法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)；
}

34、算法在发生非法操作时可以作出相应处理的特性称为算法的（ ）。

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

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

37、研究数据结构就是研究( )。

38、设有两个串S1和S2,求串S2在S1中首次出现位置的运算称作( )

39、设有6个结点的无向图,该图至少应有( )条边才能确保是一个连通图。

40、根据初始关键字序列(19,22,01,38,10)建立的二叉排序树的高度为( )。

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

42、若一组记录的排序码为(46,79,56,38,40,84),则利用堆排序的方法建立的初始堆为( )。

43、若对n阶矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依此存放于一维数组B[1..(n(n+1)/2]中,则在B中确定a[i][j](i

44、在一个有N个元素的有序单链表中查找具有给定关键字的结点，平均情况下的时间复杂性为（ B ）。（1分）

45、后缀表达式“4 5 * 3 2 + -”的值为（ ）

46、顺序栈包含两部分，数组 data[10]和栈顶 top，当 top 值为（ ）表示栈空。

47、在实现某个系统中成员之间的隶属关系时，可以采用（ ）存储结构。

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

49、线性表的顺序存储结构是一种______的存储结构

50、下面有关算法说法错误的是（ ）。