2022年数据结构冲刺卷

1、无向图G的邻接矩阵一定是(A)。

2、设一个栈的输入序列是 1,2,3,4,5,则下列序列中,是栈的合法输出序列的是( D )。

3、(3分)若某二叉树的后序遍历序列为dabec,中序遍历序列是debac,则它的前序遍历序列是(B)。

4、下列排序方法中稳定的是(A)。

5、在含有10个关键字的3阶B-树中进行查找,至多访问的结点个数为(B)。

6、在带头结点的循环链表中,将头指针改设为尾指针(rear)后,其头结点和尾结点的存储位置分别是()。

7、一棵具有 1028 个结点的二叉树的深度 h 为( )。

8、设有串s1=”welcome to zdsoft colleage!”和s2=”so”,那么s2在s1中的索引位置是

9、已知A[m]中每个数组元素距其最终位置不远，采用下列 ( ) 排序方法最节省时间

10、一棵含有n个结点的树，（ ）形态达到最大深度

11、用带头结点的单链表表示队长大于1的队列时,其队头指针指向队头结点,其队尾指针指向队尾结点,则在进行删除操作时

12、用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R[1..n]，结点R[i]若有左孩子，其左孩子的编号为结点

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

14、顺序查找法适合于存储结构为（ ）的线性表

15、索引顺序表的特点是顺序表中的数据

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

17、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（ ）。

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

19、某二叉树共有 12 个结点,其中叶子结点只有 1 个。则该二叉树的深度为(根结点在第 1层)()

20、设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（ ）。

21、队列是一种（ ）的线性表。

22、设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则下列属于该有向图G的一种拓扑排序序列的是（ ）。

23、设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（ ）。。

24、设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置（ ）脚注(10)表示用10进制表示。

25、设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是（ ）。

26、设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（ ）。

27、设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（ ）。

28、设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（ ）趟的分配和回收才能使得初始关键字序列变成有序序列。

29、深度为k的完全二叉树中最少有（ ）个结点。

30、下列程序段的时间复杂度为（ ）。
i=0，s=0；
while (s

31、concat(s,t)表示连接运算。将串t连接在串s之后，形成新的串s。若s="beg",t="in",则concat(s,t)之后，s="( )"。

32、从未排序序列中挑选元素,并将其依次插入已排序序列的一端的方法,称为( )。

33、在单链表中删除结点p的后继结点,正确的操作是( )。 (3.0分)

34、由权值3,6,7,2,5的叶子结点生成的一颗哈夫曼树,它的带权长度为( )。 (3.0分)

35、设有10000个互不相等的无序整数,若仅要求找出其中前10个最大整数,最好采用 ( ) 排序方法。

36、算法分析不研究()

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

38、设某有向图中有n个顶点,则该有向图对应的邻接表中有( )个表头结点。

39、设某有向图中有n个顶点e条边,则该图中所有顶点的入度之和为( )。

40、设用链表作为栈的存储结构则退栈操作( )。

41、设带有头结点的单向循环链表的头指针变量为head,则其判空条件是( )。

42、设某棵二叉树的高度为10,则该二叉树上叶子结点最多有( )。

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

44、设有序表的关键字序列为{1,3,9,12,32,41,45,62,75,77,82,95,100}，当采用二分查找法查找值为82的节点时，经( )次比较后查找成功。

45、下面程序段的时间复杂度是（）。for（i=0;i（1分）

46、递归函数调用时，处理参数及返回地址，要用一种称为（ ）的数据结构。

47、DLR--前序遍历（根在前，从左往右，一棵树的根永远在左子树前面，左子树又永远在右子树前面 ）LDR--中序遍历（根在中，从左往右，一棵树的左子树永远在根前面，根永远在右子树前面） LRD--后序遍历（根在后，从左往右，一棵树的左子树永远在右子树前面，右子树永远在根前面） 一，

48、在一棵二叉树的二叉链表中，空指针域等于所有非空指针域数加（ ）

49、图的深度优先遍历类似于树的（ ）遍历，它所用到的数据结构是（ ）

50、G 是一个简单的非连通无向图，共有 28 条边，则该图至少有（ ）个顶点。