注：本套试卷由强连通计算机考研完成解析，但难免有疏漏，如果发现错误请及时与我们反馈。 勘误：对微信公众号“强连通计算机考研”回复“重邮802勘误”。

1、对于双向循环链表，每个结点有两个指针域 next 和 prior，分别指向前驱和后继。在 p 指针所指向的结点之后插入 s 指针所指结点的操作应为( )。 A. p->next = s; s->prior = p; p->next->prior = s; s->next = p->next; B. p->next = s; p->next->prior = s; s->prior = p; s->next = p->next; C. s->prior = p; s->next = p->next; p->next = s; p->next->prior = s; D. s->prior = p; s->next = p->next; p->next->prior = s; p->next = s;

2、由 abc，3 个结点可以构造出多少种不同的二叉树?( ) A. 2   B. 3   C. 4   D. 5

3、设有数组 A[i,j]，数组的每个元素长度为 3 字节，i 的值为 1 到 8 ，j 的值为 1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5， 8]的存储首地址为( )。 A. BA+141   B. BA+180   C. BA+222   D. BA+225

4、一个栈的输入序列为 1 2 3，则下列序列中不可能是栈的输出序列的是( )。 A. 2 3 1   B. 3 2 1   C. 3 1 2   D. 1 2 3

5、下述编码中哪一个不是前缀码( )。 A.(00，01，10，11)    B.(0，1，00，11) C.(0，10，110，111)    D.(1，01，000，001)

6、当一棵有 n 个结点的二叉树按层次从上到下，同层次从左到右将数据存放在 一维数组 A[1…n]中时，数组中第 i 个结点的左孩子为( )。 A. A[2i](2i=rear[i] == Q->front__________ ) return 0; Q->data __________ = x;Q->rear[i] = __________;return 1;}

11、高度为 8 的平衡二叉树的结点数至少有________个。 12、文件由_____组成；记录由_____组成。 13、对于一个具有 n 个结点的单链表，在已知的结点*p 后插入一个新结点的时间复杂度为_____,在给定值为 x 的结点后插入一个新结点的时间复杂度为______。 14、在 n 个记录的有序顺序表中进行折半查找，最大比较次数是______。 15、求从某源点到其余各顶点的 Dijkstra 算法在图的顶点数为 10，用邻接矩阵表示图时计算时间约为 10ms，则在图的顶点数为 40，计算时间约为______ms。

1、一个线性表为 B=(12，23，45，57，20，03，78，31，15，36)，设散列表 为 HT[0…12]，散列函数为 H(key)= key % 13 并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。

2、已知二叉树的存储结构为二叉链表，阅读下面算法。

对于如下所示的二叉树 (1)画出执行上述算法后所建立的结构 (2)说明该算法的功能

3、假设以 I 和 O 分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由 I 和 O 组成的序列，称可以操作的序列为合法序列，否则称为非法序列。 (1)下面所示的序列中哪些是合法的? A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO (2)通过对(1)的分析，写出一个算法，判定所给的操作序列是否合法。(假 定被判定的操作序列已存入一维数组 char A[ ]中, 若操作序列合法，返回 true， 否则返回 false)。

4、已知一个连通图如下图所示，试给出图的邻接矩阵和邻接表存储示意图，若从顶点 v1 出发对该图进行遍历，分别给出一个按深度优先遍历和广度优先遍历的顶点序列：(1) 图的邻接矩阵 (2) 邻接表存储示意图 (3) 从 v1 开始的深度优先遍历的顶点序列、广度优先遍历的顶点序列 (4) 分析在深度遍历过程中，分别使用邻接矩阵和邻接表存储的算法复杂度 (5) 讨论在图遍历问题中，这两种存储方式的优劣

5、一棵二叉树的先序序列为 ABCDGEF，中序序列为 CBDGAFE。 (1)请画出该二叉树。 (2)将二叉树转换为相应的森林。

6、请阅读下列算法，回答问题