2023年数据结构试题

1、 下列关于有向带权图G的叙述中,错误的是 。

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

3、假设以数组A[60]存放循环队列的元素,其期指针是front=47. 当前队列有50个元素,则队列的尾指针值为(B) 。

4、分别用以下序列生成二叉排序树,其期三个序列生成的二叉排序树是相同的,不同的序列是(A)。

5、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用(A)存储方式最节省时间。

6、插入和删除只能在一端进行的线性表是

7、一个具有N个顶点的无向图中，要连通全部顶点至少要（ ）条边

8、数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要

9、在存储结构上，如果用带头节点单链表实现队列（假定front和rear分别为队首和队尾指针），则删除一个结点的操作为

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

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

12、线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。

13、算法的时间复杂度取决于（ ）。

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

15、下面程序段的时间复杂性的量级为（ ）。For(int i=0;i

16、在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链接的表头指针向量大小至少为（ ）

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

18、排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（ ）

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

20、设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为（ ）。

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

22、设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（ ）。

23、设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（ ）。

24、二路归并排序的时间复杂度为（ ）。

25、设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列（ ）存储方式最节省运算时间。

26、设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为（ ）。

27、某算法的时间复杂度为O{N^2}，表明该算法的( ).

28、用n个关键字构造一棵二叉排序树,其最低高度为( )。

29、在二叉排序树的()序列是一个递增有序序列。

30、序列{3,2,4,1,5,6,8,7}是第一趟递增排序后的结果,则采用的排序方法可能是( )。

31、下述排序算法中，稳定的是

32、栈和队列的共同点是( )。 (4.0分)

33、若一组记录的排序码值序列为{40,80,50,30,60,70},利用堆排序方法进行排序,初建的大顶堆是 ( ) 。

34、在具有n个结点的单链表上查找值为x的元素时,其时间复杂度为( )。

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

36、设一组初始记录关键字序列(5,2,6,3,8),以第一个记录关键字5为基准进行一趟快速排序的结果为( )。

37、设二叉排序树中有n个结点,则在二叉排序树的平均平均查找长度为( )。

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

39、算法分析的两个主要方面是( )。 (5.0分)

40、一组记录的关键字为(46,79,56,38,40,84),则利用快速排序的方法,以第一个记录为支点得到的一次划分结果为( )。 (2.0分)

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

42、若有一个长度为64的有序表,现用二分查找方法查找某一记录,则查找不成功,最多需要比较( )次。 (5.0分)

43、*散列表的地址区间为0~16，散列函数H( k)=k%17，采用线性探测法解决地址冲突，将关键字26、25、72、38、1、18、59依次存储到散列表中。元素59存放在散列表中的地址为（ ）

44、一个队列的入队序列是1，2，3，4，则队列的出队序列是（）。（1分）

45、有结构体定义及结构体类型数组如下： struct worklist{Int no;Char name[20]; char sex;}person[5];需要给结构体数组中第 2 个变量的 no 成员赋值为 5，正确的写法是（ ）

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

47、一棵完全二叉树按层次遍历的序列为 ABCDEFGHI，后序遍历中结点 B 的直接后继是结点（ ）

48、设无向图 G 中有五个顶点，各顶点的度分别为 2、4、3、1、2，则 G 中边数为（）

49、设图 G 中顶点数为 n，则图 G 至少有（）条边。

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