发布时间 : 星期日 文章数据结构习题及答案更新完毕开始阅读
58.在一棵具有35个结点的完全二叉树中，该树的深度为（）。
A.6 B.7 C.5 D.8
59.在一棵完全二叉树中，若编号为i的结点存在左孩子，则左孩子结点编号为（）。 A.2i B.2i-1 C.2i+1 D.2i+2
60.在一棵完全二叉树中，若编号为i的结点存在右孩子，则右孩子结点编号为（）。 A.2i B.2i-1 C.2i+1 D.2i+2
61.在一棵完全二叉树中，对于编号为i（i>1）的结点其双亲结点的编号为（）。 A.（i+1）/2 B.（i-1）/2 C.i%2 D.i/2
62.有如图1.1所示的一棵二叉树，则该二叉树所含单支结点数为（）。 A.2 B.3 C.4 D.5
63.有如图1.2所示的一棵二叉树，则该二叉树的中序遍历序列为（）。 A. ABCDEFG B. CDBGFEA C. CBDAEGF D. ABECDFG
64.有如图1.2所示的一棵二叉树，则该二叉树的先序遍历序列为（）。 A.ABCDEFG B.CDBGFEA C.CBDAEGF D.ABECDFG
65.有如图1.2所示的一棵二叉树，则该二叉树的后序便利序列为（）。 A.ABCDEFG B.CDBGFEA C.CBDAEGF D.ABECDFG 66.利用n个值生成的哈夫曼树中共有（）个结点。
A.n B.n+1 C.2n D.2n-1
67.利用3，6，8，12这4个值作为叶子结点的权，生成一棵哈夫曼树，该树的带权路径长度为（）。
A.55 B.29 C.58 D.38
68.在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有的入度数之和为（）。 A.s B.s-1 C.s+1 D.n
69.在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有的度数之和为（）。 A. s B. s -1 C. s +1 D.2s
70.在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数为（）。 A.n B.e C.n+e D.2e
71.在一个具有n个顶点的无向完全图中，所含的边数为（）。 A.n B.n（n-1） C.n（n-1）/2 D.n（n+1）/2 72.在一个具有n个顶点的有向完全图中，所含的边数为（）。 A.n B.n（n-1） C.n（n-1）/2 D.n（n+1）/2
73.在一个具有n个顶点的无向连通图中，它包含的连通分量的个数为（）。 A.0 B.1 C.n D.n+1
74.若有一个图中包含k个连通分量，若按照深度优先搜索的方法访问所有顶点，则必须调用（）次深度优先搜索遍历的算法。
A.k B.1 C.k-1 D.k+1
75.若要把n个顶点连接为一个连通图，则至少需要（）条边。 A.n B.n+1 C.n-1 D.2n
76.在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为（）。 A.n B.ne C.e D.2e
77.在一个具有n个顶点和e条边的有向图的邻接矩阵中，表示边存在的元素的个数为（）。 A.n B.ne C.e D.2e
78.在一个具有n个顶点和e条边的无向图的邻接矩阵中，边结点的个数为（）。
A.n B.ne C.e D.2e
79.对于一个有向图，若一个顶点的度为k1，出度为k2，则对应邻接表中该顶点单链表的边数结点为（）。 A.k1 B.k2 C.k1-k2 D.k1+k2
80.对于一个有向图，若一个顶点的度为k1，出度为k2，则对应逆邻接表中该顶点单链表的边数结点为（）。 A.k1 B.k2 C.k1-k2 D.k1+k2
81.对于一个无向图，下面（）的说法是正确的。
A.每个顶点的入度等于出度 B.每个顶点的度等于入度和出度之和 C.每个顶点的入度为0 D.每个顶点的出度为0
82.在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的（）。
A.出边数 B.入边数 C.度数 D.度数减一 83.若一个图的边集为{（A，B）（A，C）（B，D）（C，F）（D，E）（D，F）}，则从顶点A开始对该图进行深度优先搜索，得到的顶点序列可能为（）。
A. ABCFDE B. ACFDEB C. ABDCFE D. ABDFEC 84.若一个图的边集为{（A，B）（A，C）（B，D）（C，F）（D，E）（D，F）}，则从顶点A开始对该图进行广度优先搜索，得到的顶点序列可能为（）。 A.ABCDEF B.ABCFDE C.ABDCEF D.ACBFDE 85.若一个图的边集{（1，2）（1，4）（2，5）（3，1）（3，5）（4，3）}，则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为（）。 A.1，2，5，4，3 B.1，2，3，4，5 C.1，2，5，3，4 D.1，4，3，2，5 86.若一个图的边集{（1，2）（1，4）（2，5）（3，1）（3，5）（4，3）}，则从顶点1开始对该图进行广度优先搜索，得到的顶点序列可能为（）。
A. 1，2，3，4，5 B. 1，2，4，3，5 C. 1，2，4，5，3 D. 1，4，2，5，3 87.由一个具有n个顶点的连通图生成的最小树中有（）条边。
A.n B.n-1 C.n+1 D.2n
88.若查找每一个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找长度为（）。 A. n B. n+1 C. (n-1)/2 D. (n+1)/2
89.对长度为n的单链有序表，若查找每个元素的概率相等，则查找任一个元素的平均查找长度为（）。 A. n/2 B.（n+1）/2 C. (n-1)/2 D.n/4
90.对于长度为9的顺序存储的有序表，若采用二分查找，在等概率情况下的平均查找长度为（）的值除以9。
A.20 B.18 C.25 D.22
91.对于长度为18的顺序存储的有序表，若采用二分查找，则查找第15个元素的查找长度为（）。
A.2 B.3 C.4 D.6
92.对于顺序存储的有序表（5，12，20，26，37，42，46，50，64），若采用二分查找，则查找元素26的查找长度为（）。 A.2 B.3 C.4 D.5
93.在分块查找中，若用于保存数据元素的主表长度为n，它被分为k个子表，每个子表的长度均为n/k，若用顺序查找确定块，则分块查找的平均查找长度为（）。
A.n+k B.k+n/k C.（k+n/k）/2 D.（k+n/k）/2+1
94.在分块查找中，若用于保存数据元素的主表长度为144，它被分为12个子表，每个子表的长度均为12，若用顺序查找确定块，则分块查找的平均查找长度为（）。 A.13 B.24 C.12 D.79
95.在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为（）。 A.n B.lbn C.（h+1）/2 D.h
96.在一棵平衡二叉排序树中，每个结点的平衡因子的取值范围是（）。
A.-1~1 B.-2~2 C.1~2 D.0~1
97.若根据查找表（23，44，36，48，52，73，64，58）建立线性哈希表，采用H（K）=K计算哈希地址，则元素64的哈希地址为（）。
A.4 B.8 C.12 D.13
98.若根据查找表（23，44，36，48，52，73，64，58）建立线形哈希表，采用H（K）=K计算哈希地址，则哈希地址为3的元素个数为（）。 A.1 B.2 C.3 D.4
99.若根据查找表建立长度为m的线性哈希表，采用线性探测再哈希法处理冲突，假定对一个元素第一次计算的哈希地址为d，则下一次的哈希地址为（）。 A.d B.d+1 C.（d+1）/m D.（d+1）%m
100.在采用线性探测再哈希法处理冲突的线性哈希表上，假定装填因子a的值为0.5，则查找任一个元素的平均查找长度为（）。 A.1 B.1.5 C.2 D.2.5
101.在哈希查找中，平均查找长度主要与（）有关。
A.哈希表长度 B.哈希元素个数 C.装填因子 D.处理冲突方法 102.若对n个元素进行直接插入排序，则进行第i趟排序过程前，有序表中元素的个数为（）。 A.i B.i+1 C.i-1 D.1
103.若对n个元素进行直接插入排序，在进行第i趟排序时，为寻找插入位子最多需要进行（）次元素的比较，假定第0号元素放有待查的键值。
A. i B.i-1 C.i+1 D.1
104.若对n个元素进行直接插入排序，在进行第i趟排序时,假定元素r[i+1]的插入位置为r[j]，则需要移动元素的次数为（）。 A.j-i B.i-j-1 C.i-j D.i-j+1
105.若对n个元素进行直接插入排序，在进行任意一趟排序的过程中，为寻找插入位置而需要的时间复杂度为（）。 A.O（1） B.O（n） C.O（n2） D. O（lbn）
106.在对n个元素进行直接插入排序的过程中，共需要进行（）趟。 A.n B.n+1 C.n-1 D.2n
107.对n个元素进行直接插入排序的时间复杂度为（）。 A.O（1） B.O（n） C.O（n2） D. O（lbn）
108.在对n个元素进行冒泡排序的过程中，第一趟排序至多进行（）对相邻元素之间的交换。 A .n B.n-1 C.n+1 D.n/2
109.在对n个元素进行冒泡排序的过程中，最坏情况下的时间复杂度为（）。 A.O（1） B.O（lbn） C.O（n2） D.O（n）
110.在对n个元素进行冒泡排序的过程中，至多需要（）趟完成。 A .1 B.n C.n-1 D.n/2
111.在对n个元素进行快速排序的过程中，最好情况下需要进行（）趟。
A.n B.n/2 C.lbn D.2n
112.在对n个元素进行快速排序的过程中，最坏情况下需要进行（）趟。
A.n B.n-1 C.n/2 D.lbn
113.对下列4个序列进行快速排序，各以第一个元素为基准进行第一次划分，则在该次划分过程中需要移动元素次数最多的序列为（）。 A.1，3，5，7，9 B.9，7，5，3，1 C.5，3，1，7，9 D.5，7，9，1，3
114.假定对元素序列（7，3，5，9，1，12，8，15）进行快速排序，则进行第一次划分后，得到的左区间中元素的个数为（）。 A.2 B.3 C.4 D.5
115.在对n个元素进行简单选择排序的过程中，在第i趟需要从（）个元素中选择出最小值元素。
A.n-i+1 B.n-i C.i D.i+1
116.若对n个元素进行简单选择排序，则进行任一趟排序的过程中，为寻找最小值元素所需要的时间复杂度为（）。 A.O（1） B.O（lbn） C.O（n2） D. O（n）
117.假定一个初始堆为（1，5，3，9，12，7，15，10），则进行第一趟堆排序后得到的结果为（）。
A.3，5，7，9，12，10，15，1 B.3，5，9，7，12，10，15，1 C.3，7，5，9，12，10，15，1 D.3，5，7，12，9，10，15，1 118.若一个元素序列基本有序，则选用（）方法较快。 A.直接插入排序 B.简单选择排序 C.堆排序 D.快速排序
119.若要从1000个元素中得到10个最小元素，最好采用（）方法。 A.直接插入排序 B.简单选择排序 C.堆排序 D.快速排序 120.在平均情况下速度最快的排序方法为（）。
A.简单选择排序 B.冒泡排序 C.堆排序 D.快速排序
二﹑填空题
1.数据的逻辑结构可分为____和____两大类。
2.数据的存储结构被分为____，_____，_____和____4种。
3.在下面的程序段中，s=s+p语句被执行次数为____，p*=j语句的执行次数为____,该程序的复杂度为____。 int i=0，s=0； while（++i<=n） { int p=1;
for(int j=1;j<=i;j++) p*=j; s=s+p;
}
4.一种数据结构的元素集合K和它的二元关系R为：K={a,b,c,d,e,f,g,h} R={
5.线性表的两种存储结构分别为____和____。
6.线性表的顺序存储结构称为____，链式存储结构称为____。
7.若经常需要对线性表进行插入和删除运算，则最好采用__存储结构，若经常需要对线性表