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.若经常需要对线性表进行插入和删除运算，则最好采用__存储结构，若经常需要对线性表
进行查找运算，则最好采用____存储结构。
8.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为____。
9.对于一个单链表存储的线性表，在表头插入结点的时间复杂度为____，在表尾插入结点的时间复杂度为____。
10.在线性表的单链表存储中，若一个元素所在结点的地址为p，则其后的断结点的地址为____。
11.在以HL为头指针的带头结点的单链表和循环单链表中，链表为空的条件分别为____和____。
12.在____链表中，既可以通过设定一个头指针，也可以通过设定一个尾指针来确定它，即通过头指针或尾指针可以访问到该链表的每个结点。
13.在一个单链表中删除指针p所指向结点的后继结点时，需要把____的值赋给p->next指针域。
14.在一个单链表中指针p所指向结点的后面插入一个指针q所指向的节点时，首先把____的值赋给p->next，然后把____的值赋给p->next。
15.假定指向单链表中第一个结点的头指针为head，则像该单链表的表头插入指针p所指向的新结点时，首先执行____赋值操作，然后执行____赋值操作。
16.访问一个顺序表和一个单链表中第i个元素的时间复杂度分别为____和____。
17.在一个带头结点的循环单链表中，在表头插入或删除与在其它位置插入和删除，其操作过程是否相同？________。
18.在双向链表中每个结点包含有两个指针域，一个指向其____结点，另一个指向其____结点。
19.在一个双向链表中指针p所指向的结点之后插入一个指针q所指向的结点时，需要对p->next->prior指针域赋值为____。
20.在一个双向链表中删除指针p所指向的结点时，需要对p->next->prior指针域赋值为____。 21.栈又称为____表，队列又称为____表。
22.在一个用一维数组a[N]表示的顺序栈中，该栈所含元素的个数最少为____个，最多为____个。
23.像一个顺序栈插入一个元素时，首先使____后移一个位置，然后把新元素____到这个位子。
24.从一个栈删除元素时，首先取出____，然后再使____减一。
25.一个顺序栈存储一个一维数组a[M]中，栈顶指针用top表示，当栈顶指针等于____时为空栈，栈顶指针为____时为满栈。
26.假定一个链栈的栈顶指针为top，每个结点包含值域data和指针域next，当p所指向的结点入栈时，则首先执行____操作，然后执行____操作。
27. 假定一个链栈的栈顶指针为top，每个结点包含值域data和指针域next，当进行出栈运算时（假定栈非空），需要把栈顶指针修改为____的值。 28.设元素1，2，3，4，5依次进栈，若要在输出端得到序列34251，则应进行的操作序列为Push(s,1),Push(s,2),____,Pop(s),Push(s,4),Pop(s),____,____,Pop(s),Pop(s)。
29.设元素a，b，c，d依次进栈，若要在输出端得到序列cbda，则应进行的操作序列为push(s,a),push(s,b),push(s,c),____,____，____pop(s),pop(s)。 30.队列的插入操作在____进行，删除操作在____进行。
31.一个顺序循环队列存在于a[M]中,假定队首和队尾指针分别为front和rear，则判断对空的条件为____，判断对满的条件为____。
32.一个顺序循环队列存在于a[M]中,假定队首和队尾指针分别为front和rear，则求出队首和
队尾指针的下一个位置的计算公式分别为________和________。
33.在一个用一维数组a[N]存储的顺序循环队列中，该队列中的元素个数最少为____个，最多为____个。
34.向一个顺序循环队列中插入元素时，需要首先移动____，然后再向它所指位置____新元素。
35.在一个空链队列中，假定队首和队尾指针分别为f和r，当向他插入一个新结点*p时，则首先执行____操作，然后执行____操作。
36.在一个带头结点的循环链队列中，假定队首和队尾指针分别为f和r，当向它插入一个新结点*p时，则首先执行____操作，然后执行____操作。
37.假定front和rear分别为一个链队列的对首和队尾指针，则该链队列中只有一个结点的条件为________。
38.在一个链栈中，若栈顶指针等于NULL则为____；在一个链队列中，若对首和队尾的指针相同，则表示该队列为____或该队列____。
39.一个二维数组A[15，10]采用行优先方式存储，每个数据元素占用4个存储单元，以该数组第3列第0行的地址（即A[3，0]的地址）1000为首地址，则A[12，9]的地址为____。 40.在二维数组a[10,20]中，每个元素占8个存储单元，假定该数组的首地址为2000，则数组元素a[6,15]的字节地址为____。 41.有一个8×8的下三角矩阵A，若将其进行顺序存储于一维数组a[N]中，则N的值为____。 42.有一个10×10的下三角矩阵A，若将其进行顺序存储于一维数组a[N]中，则Aij（1≤i≤10,1≤j≤i）存储于a中的下标位置为____。
43.有一个8×8的下三角矩阵A，若将其进行顺序存储，每个元素占用4个字节，则A5，4元素的相对字节地址为（相对首元素地址而言）____。 44.一种数据结构的元素集合K和它的二元关系R为：
K={a,b,c,d,e,f,g,h}
R={
46.在一棵树中，____结点没有前驱结点，其余每个结点有并且只有一个____，可以有人以多个____结点。
47.如图1.3所示为一棵树，该树的叶子结点数为____个，单支结点数为____个，双分支结点数为____个，三分支结点数为____个。
48.如图1.3所示的一棵树，结点K的所有祖先的结点数为____个，结点B的所有子孙结点数为____个。
49.如图1.3所示的一棵树，结点D和X的层数分别为____和____。 50.如图1.4所示的一棵树，则树中所含的结点数为____个，树的深度为____，树的度为____。 51.如图1.4所示的一棵树，则度为3，2，1，0的结点数分别为____，____，____。 52.如图1.4所示一棵树，则结点H的双亲为____，孩子结点为____。
53.在一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为____。 54.对于一棵二叉树，若一个结点的编号i，若它的左孩子结点存在，则其编号为____，若右孩子结点存在，则其编号为____，若双亲结点存在，则其编号为____。 55.在一棵二叉树中，第5层上的结点数最多为____。
56.假定一棵二叉树的结点数为18，则它的最小深度为____，最大深度为____。
57.如图1.5所示为一棵二叉树，则E结点的双亲结点数为____，左孩子结点为____，右孩子结点为____。
58.如图1.5所示为一棵二叉树，它含有双支结点____个，单分支结点____个，叶子结点____