本次考试150分满分。依旧是120数据结构与30分计算机组成原理。

数据结构共有八个大题。第一题选择题15个选择，30分，第二题填空题10个填空题，共15个空30分，三四五六是四道简答题各个10分，七八是两道应用题，第七题第一问写出思路，第二问请用C/C++语言写出程序。第八题同样前两问，第三问求时间复杂度和空间复杂度。计算机组成原理，共四道大题。第一题4个选择，8分。第二题，4道小填空题，每道填空1空，(选填共计16分)，第三题简答题七分，第四题简答题七分。

计算机组成原理

(整体来说，在没学过汇编原理，但是复习的不错的同学，这部分拿28分我觉得一点都不过分)

第一题(4小题，每题2分，共8分)

1.short 16位int 32位，unsigned short s = -0X(一个用16进制表示的正数前面加了个负号)，然后unsigned int x = s;求x的16进制。编码的话用的是补码。

2.忘记了

3.忘记了

4.问Cache用的什么硬件。(A 、DRAM B、SRAM 。。。。。)SRAM是对的

(整个四道是非常基础的题目。没有难题，辅导资料上的题目会做，这个一定会做)

第二题(4小题每题两分共八分，第一题两空，每空各一分)

1、某机采用微程序控制方式，32个微命令，直接控制方式/直接编码方式，操作控制字段多少位，那么四个互斥类14，8，5，3个微命令字段编码方式，操作控制字段多少位

2、忘记了

3、(-25.125)，题目说求IEEE754(32)的变种，即小数点只去七位，整个共16位。

4、求中断顺序，A(1011)，B(0100)，C(1111)，D(0101)，求一个中断码后面的顺序

第三题(共七分，第一问1分，第二问三个空，各两分)

主要考了指令格式再顺带了一部分汇编，(PS列出了三种指令格式)。(每一种格式都是32位的，内部分法不一样，分了op,rs,rd等字段)

1.让我们求指令有多少种操作码(操作码有6位，但答案并不是64，第一种指令的操作码题目说了默认000000，然后根据后面一个6位的字段来一起操作，所以是64-1+64=127种操作码)

2.让我们写三个空(全是汇编的，但是除了第三空问的是整段程序运行下来，某个地址的值是多少不会汇编不会算，前两空求某地址指令的汇编助记符(addi $5 $5 $4这种,大致长这样)，它是可以仿照上面的空去模仿的，很简单)

第四题(共七分，第一问三空，各两分，第二问1分)

1.地址码共32位按照(20-标记号，7-组号，5-组内地址号)，题目画了一张图，图里说明Cache是2路组相连。还有一些零散已装填的cache标记和对应的有效位，这个第二问用得到。第一问求Cache总容量是多少？Cache中一行多长？Cache是几路组相连？

2.给了6个地址码，对照图中的装填情况问Cache命中率是多少？(这个Cache块中有效位有些有0，有些有1，这个是考点) ，

数据结构

(前两道大题只有一道知道叶节点个数求正则二叉树的形状王道没有可以错，其他都很简单，各个章节都考了一点。)

第一题(选择15道，共计30分)

1.给出一个超简单的for循环求它的时间复杂度，答案是O(n)

2.

3.

4.当序列更有序的时，下列哪一种算法反而时间复杂度更高(快排)

5.m*n的二维数组存到了一维数组里。A[0][0]放在150，每个数组节点占一位，A[2][2]放在182，A[2][3]放在197，求问A[3][4]放在哪里

6.快速排序空间复杂度是多少

7.DJsta算法哪一种说法是错误的 A采用动态规划(应该是贪心算法)

8.

9.

10.

11.

12.5个叶节点的正则二叉树有多少种形态

13.

14.

15.

第二题(共10道题，15个填空，共计30分)

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.给出四种排序方法，问哪两种是稳定排序

第三题(二叉树考点，简答题，两问，共10分)

1.前序和层序能否确定唯一一颗二叉树(否，会出现子树无法确定的情况)

2.中序和层序能否确定唯一一颗二叉树(可，可以确定根节点和子树并且能够递归确定每一个节点)

第四题(AVL树考点，简答题，两问，共10分)

1.给出一棵AVL树，并给出三个数字，依次插入，画出插入每个数字后的AVL树样貌

2.另外给出一棵AVL树，并给出三个数字，依次删除，画出删除每个数字后的AVL树样貌(王道上没讲，但可以百度啊，一定要会)

第五题(静态链表考点，简答题，两问，共10分)

该静态链表(从逻辑上看，可以看成两个都带头节点的链表，a[0]就是备用数组的头结点，a[1]就是正常数组的头结点，采用数字0作为空指针，通过链表来模拟队列)给出了相关结构体定义，和初始化的程序。

1.编写Enqueue()函数

2.编写Dequeue()函数

第六题(链表逆置考点，简答题，五个填空，共10分)

Void Inverse(LinkList L)

//Linklist的结构体未给你，但你应该比较熟悉才行，L是不带头结点且默认非空

//LinkList == LNode * 一般方便区分变量作用

{

LNode *l, *p, *r;//left,right,p节点

l = L;

p = L->next;//有一空

while (p != NULL//有一空)

{

r = p->next;

p->next = l;

l = p;//有一空

p = r;//有一空

}

L->next = NULL;//有一空

return;

}

对上述函数进行五个填空，该函数极大还原了考试函数，只要能搞定这个函数，这分拿的就没问题。

第七题(图论的一个考点很难(似乎是深度遍历+拓扑排序遍历的一种算法)，算法题，10分)

给了图的邻接表结构定义，实现DFS来判断节点E是否在节点A的环中

1、给出算法的基本设计思想

2、根据设计思想，采用C或C++语言描述算法，关键之处给出注释

第八题(链表查找考点，算法题，10分)

该链表L有序，查找一个L[i] = i的节点，i>=1且i<=n,注该链表值中有负数。(求解时要求时间越快越好)

1、给出算法的基本设计思想

2、根据设计思想，采用C或C++语言描述算法，关键之处给出注释

3、标明该算法的时间复杂度和空间复杂度