A.16 B.32 C.31 D.10
73、设一棵二叉树中，度为1的结点数为9，则该二叉树的叶子结点的数目为（ D ） A.10 B.11 C.12 D.不确定
74、在一个图中，所有顶点的度数之和等于图的边数的（ C ）倍。 A.1/2 B.1 C.2 D.4 75、如图所示的4棵树中，是满二叉树的为（ A ）。
A． B． C． D．
76、二维数组A按行优先顺序存储，其中每个元素占1个存储单位。若A[1][1]的存储地址为420，A[3][3]的存储地址为446，则A[5][5]的存储地址为（ C ）。 A．470 C．472
B．471 D．473
77、设有两个均只有头指针的单链表，若要将长度为n的单链表链接到长度为m的单链表之后，则实现该功能的算法的时间复杂度为（ C ）。 A．O(1) C．O(m)
B．O(n) D．O(m+n)
78、设单循环链表中结点的结构为（data, link），且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪个操作？（ D ） A．s =rear; rear=rear->link; delete s; B．rear=rear->link; delete rear; C．rear=rear->link->link; delete rear;
D．s=rear->link->link;rear->link->link=s->link; delete s; 79、从堆中删除一个元素的时间复杂度为（C ）。 A．O(1)
B．O(n) D．O(nlog2n)
C．O(log2n)
80、对于一棵具有n个结点的二叉树，在其二叉链表的存储结构中，所有结点的空指针数等于（ C ）。 A．n
B．n-1 D．2*n
9
C．n+1
81、如图所示的4棵二叉树中，不是完全二叉树的为（ Ｂ ）。
(A) (B) (C) (D)
82、利用逐点插入法建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉搜索树以后，查找元素35要进行（ Ａ ）元素间的比较。 A．4次 C. 7次
B．5次
D．10次
83、在一个带权连通图G中，权值最小的边一定包含在G的（ A ）中。 A．最小生成树
B．生成树
D．深度优先生成树
C．广度优先生成树
84、一个有n个顶点和n条边的无向图一定是（A ）。 A．连通的 C．无回路
B．不连通的 D．有回路
85、对n个关键字的序列进行快速排序，其平均情况下的空间复杂度为（ B ）。 A．O(1) C．O(n)
二、填空题
1.在线性表的顺序存储中，元素之间的逻辑关系是通过（ 元素的存储地址 ）决定的。 2、一个顺序栈存储于一维数组a[m]中，当栈顶指针等于（-1 ）时，则为空栈。 3、有42个结点的二叉树的高度最小是（ 6 ）。
4、在一棵二叉树中，假定度为2的结点有5个，度为1的结点有6个，则叶子结点数有（ 6 ）个。
5、在一个最小堆中，堆顶结点的值是所有结点中的（ 最小值 ）。
6、对于一个具有n个顶点昨e条边的连通图，其生成树中的边数为（ n-1 ）。
B．O(log2n) D．O(nlogn)
?010???7、从邻接矩阵A=101可以看出，若该图是有向图，则共有（ 4 ）条边。
????010??8、直接插入排序在最好情况下的时间复杂度为（ O（1） ）
10
9.在线性表的链式存储中，元素之间的逻辑关系是通过（结点中的指针 ）决定的。 10.在一个长度为n的顺序表中的第i个元素（1≤i≤n）之前插入一个元素时，需向后移动（ n-i+1）个元素。
11.在一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需要向前移动（n-i ）个元素。
12、数据的逻辑结构是从逻辑上描述数据，它与数据的（存储结构 ）无关，是独立于计算机的。
13、数据的逻辑结构是从逻辑上描述数据，它与数据的（ 存储结构 ）无关，是独立于计算机的。
14、在下面程序段中，设n为常数，s=s+p；语句的执行次数为（ n）。 int i=0, s=0; while(++i<=n) { }
15、算法的每一步必须有确切的定义，也就是说，对于每步需要执行的动作必须严格、清楚地给出规定，这是算法的（ 确定性 ）。
16、在下面程序段中，设n为常数，s=s+p；语句的执行次数为（ n ）。 int i=0, s=0; while(++i 17、在带头结点的单链表中，要删除某一指定的结点，必须找到该结点的（ 前驱 ）结点。 18、在一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，若保持数据元素的原有次序不变，需要向前移动（n-i）个元素。 19、递归工作栈中的工作记录通常包括：（返回地址 ）、在本次过程调用时与形参结合的 int p=1; for(int j=1;j<=i; j++) p*=j; s=s+p; int p=1; for(int j=1;j<=i; j++) p*=j; s=s+p; 11 实参值和本层的局部变量值。 20、在一棵二叉树中，假定度为2的结点有5个，度为1的结点有6个，则叶子结点数有（ 6 ）个。 21、在用于表示有向图的邻接矩阵中，对第J列的元素进行累加, 可得到第J个顶点的（ 入 ）度。 22、对于一个具有n个顶点和e条边的有向图，在其对应的邻接表中，所含边结点为（ e）个。 23、如图所示的有向无环图可以排出（ 12 ）种不同的拓扑序列。 b f a c e g d 24、任何一棵树的结点个数减去边数等于（ 1）。3、一个顺序栈存储于一维数组a[m]中，若栈顶指针指向栈顶元素，则当栈顶指针等于（ -1）时，表示空栈。 25、有20个结点的二叉树的高度最大是（ 19 ），设根结点所处层次为0。 26、在用于表示有向图的邻接矩阵中，对第i行的元素进行累加, 可得到第i个顶点的（ 出）度。 27、对于一个具有n个顶点和e条边的无向图，在其对应的邻接表中，所含边结点为（ 2e ）个。 28、在一个带头结点的单循环链表中，结点结构为（数据域data，指针域next），p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为（ p->next->next ）。 29、队列中队尾指针是随着（ 进队 ）操作而发生变化的。 30、以折半搜索方法搜索一个线性表时，此线性表必须是（ 有序的 ）。 31、在平衡的二叉搜索树中，任意结点的平衡因子的绝对值均（ 不超过1 ）。 32、在线性表的链式存储中，元素之间的逻辑关系是通过（ 节点的指针 ）决定的。 33、在一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，若保持元素间的先后关系不变，需要向前移动（ n-i）个元素。 12
相关推荐：
loading