1.栈和队列的主要区别在（D）
A.逻辑机构不一样
B.存储结构不一样
C.包含的元素不一样
D.插入、删除操作的限定不一样
2.循环队列存储在数组A[0...n]中，则入队时的操作是（D）
A.rear=rear+1
B.rear=(rear+1)mod(n-1)
C.rear=(rear+1)mod n
D.rear=(rear+1)mod(n+1)
3.在一个链队列中，假设队头指针为front，队尾指针为rear，x所指向的元素需要入队，则需要执行的操作为（D）
A.front=x; front=front->next;
B.x->next=front->next; front=x;
C.rear->next=x;rear=x;
D.rear->next=x;x->next=NULL; rear=x;
4.若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是(D)
A.hcabdegf
B.eafgbhcd
C.dbcahefg
D.abcdhefg
5.十字链表是(B)的存储结构
A.无向图
B.有向图
C.无向图和有向图
D.都不是
6.设图的邻接矩阵A如下所示，各顶点的度依次是（C）
A.1,2,1,2
B.2,2,1,1
C.3,4,2,3
D.4,4,2,2
解析：
- 对于顶点 0 ，其所在行元素之和为 0+1+0+1=2（出度），所在列元素之和为 0+0+0+1=1（入度），度为 2+1=3 。
- 对于顶点 1 ，其所在行元素之和为 0+0+1+1=2（出度），所在列元素之和为 1+0+1+0=2（入度），度为 2+2=4 。
- 对于顶点 2 ，其所在行元素之和为 0+1+0+0=1（出度），所在列元素之和为 0+1+0+0=1（入度），度为 1+1=2 。
- 对于顶点 3 ，其所在行元素之和为 1+0+0+0=1（出度），所在列元素之和为 1+1+0+0=2（入度），度为 1+2=3 。
7.对长度为3的顺序表进行查找，若查找第一个元素的概率为1/2，查找第二个元素的概率为1/3，查找第三个元素的概率为1/6，则查找任一元素的平均查找长度为(A)
A.5/3
B.2
C.7/3
D.4/3
解析：平均查找长度（ASL）是所有查找过程中进行关键字比较次数的期望值。对于顺序表，若查找第 i 个元素的概率为 Pi ，查找第 i 个元素需要比较的次数为 Ci ，则平均查找长度
本题中，顺序表长度 n=3 ：
- 查找第一个元素的概率 P1=21 ，查找第一个元素需比较 1 次，即 C1=1 。
- 查找第二个元素的概率 P2=31 ，查找第二个元素需比较 2 次，即 C2=2 。
- 查找第三个元素的概率 P3=61 ，查找第三个元素需比较 3 次，即 C3=3 。
根据公式计算平均查找长度：
ASL=P1*C1+P2*C2+P3*C3=1/2×1+1/3×2+1/6×3=5/3
8.已知一个有序表(13,18,24,35,47,50,62,83,90,115,134)，当二分查找值为90的元素时，查找成功的比较次数为(B)
A.1
B.2
C.4
D.6
9.已知一个长度为16的顺序表L，其元素按关键字顺序排列，若采用折半查找法查找一个L中不存在的元素，则关键字的比较次数最多是(B)
A.4
B.5
C.6
D.7
解析：折半查找的过程可以用一棵判定树来描述。对于长度为 n 的有序顺序表，判定树的高度 h=⌈log2(n+1)⌉ （⌈⌉ 表示向上取整） 。
在折半查找中，查找失败时关键字的比较次数最多为判定树的高度。本题中顺序表长度 n=16 ，则判定树的高度 h=⌈log2(16+1)⌉=⌈log2 17⌉ 。
因为 log2 16=4 ，log2 32=5 ，16<17<32 ，所以 ⌈log2 17⌉=5 ，即关键字的比较次数最多是 5 次。
10.当采用分块查找时，数据的组织方式是(B)
A.数据分成若干块，每块内数据有序
B.数据分成若干块，每块内数据不必有序但块间必须有序，每块内最大(或最小)的数8据组成索引块
C.数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块
D.数据分成若干块，每块(除最后一块外)中数据个数需相同
解析：
分块查找的数据组织方式是将数据分成若干块，每块内数据不必有序 ，但块间必须有序。同时，把每块内最大（或最小）的数据组成索引块，索引块是有序的。通过先在索引块中查找确定目标元素可能所在的块，再在该块内进行顺序查找。