计算机考研数据结构试卷四(练习题含答案).pdfVIP

计算机考研数据结构试卷四（练习题含答案）

（PS：其他正在整理，敬请期待）

数据结构试卷4

一、选择题

1．设一维数组中有n个数组元素，则读取第i个数组元素的平均时

间复杂度为（）。(A)O(n)(B)O(nlog2n)(C)O(1)(D)O(n2)

2．设一棵二叉树的深度为k，则该二叉树中最多有（）个结点。

kk-1k

(A)2k-1(B)2(C)2(D)2-13．设某无向图中有n个顶点e条边，则该无

向图中所有顶点的入度之和为（）。(A)n(B)e(C)2n(D)2e4．在二叉排序

树中插入一个结点的时间复杂度为（）。

2

(A)O(1)(B)O(n)(C)O(log2n)(D)O(n)

5．设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）

条有向边。(A)n(B)n-1(C)m(D)m-1

6．设一组初始记录关键字序列为(345，253，674，924，627)，则用

基数排序需要进行（）趟的分配和回收才能使得初始关键字序列变成有序

序列。(A)3(B)4(C)5(D)87．设用链表作为栈的存储结构则退栈操作（）。

(A)必须判别栈是否为满(B)必须判别栈是否为空(C)判别栈元素的类型(D)

对栈不作任何判别8．下列四种排序中（）的空间复杂度最大。

(A)快速排序(B)冒泡排序(C)希尔排序(D)堆

9．设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，

度数为2的结点数为N2，则下列等式成立的是（）。

(A)N0=N1+1(B)N0=Nl+N2(C)N0=N2+1(D)N0=2N1+l

10.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元

素某的最多

比较次数不超过（）。(A)log2n+1(B)log2n-1(C)log2n(D)log2(n+1)

二、填空题

1．设有n个无序的记录关键字，则直接插入排序的时间复杂度为

________，快

速排序的平均时间复杂度为_________。

2．设指针变量p指向双向循环链表中的结点某，则删除结点某需要

执行的语句

序列为

_________________________________________________________（设结

点中的两个指针域分别为llink和rlink）。

3．根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的

高度为

____________。

4．深度为k的完全二叉树中最少有____________个结点。

5．设初始记录关键字序列为(K1，K2，…，Kn)，则用筛选法思想建

堆必须从第

______个元素开始进行筛选。

6．设哈夫曼树中共有99个结点，则该树中有_________个叶子结点；若

采用二

叉链表作为存储结构，则该树中有_____个空指针域。

7．设有一个顺序循环队列中有M个存储单元，则该循环队列中最多

能够存储

________个队列元素；当前实际存储________________个队列元素

（设头指针F指向当前队头元素的前一个位置，尾指针指向当前队尾元素

的位置）。8．设顺序线性表中有n个数据元素，则第i个位置上插入一

个数据元素需要移

动表中_______个数据元素；删除第i个位置上的数据元素需要移动

表中_______个元素。

9．设一组初始记录关键字序列为(20，18，22，16，30，19)，则以

20为中轴的

一趟快速排序结果为______________________________。

10．设一组初始记录关键字序列为(20，18，22，16，30，19)，则根

据这些

初始关键字序列建成的初始堆为________________________。

11．设某无向图G中有n个顶点，用邻接矩阵A作为该图的存储结构，

则顶

点i和顶点j互为邻接点的条件是_____