889
一、选择40分
都是非常基础的题目，但是考的面比较广
今年尤其考到了外部排序的选择题，我是瞎蒙的根本没复习外部排序
二、填空题40分
1、ADT 中的DSP 分别指什么：
2、判断循环双链表为空的条件:
3、给一个广义表求长度，还有如何将一个原子从广义表中摘除
4、知先序遍历ABC和中序遍历ACB求后序遍历:
5、给一个堆，且是大根堆，在堆中插入50，求调整后大根堆的层次遍历:
6、基数排序是根据_____位优先的排序；
7、给一个有序数组求用二分查找数组中没有的数所需要的比较次数：
8、在一棵树中查找从根节点到树中任意一个结点的路径所需要的时间复杂度:
9、剩下的等想起来再加
三、简答题40分
1、已知1、2、3、4、5通过任意组合构成一颗二叉排序树：
（1）写出高度最高的4颗二叉排序树；
（2）写出高度最低的4棵二叉排序树；
2、已知一个函数
p(n){
if(n > 1){
f(n);
p(n - 1); p( n - 1);
}
else f(n);
}
f(n)的运行时间为常数，当n = 1时p(1)的运行时间为1秒，求p(7)的运行时间；
3、图论：
(1)用邻接表储存50个节点100条边的图，其中指针占8字节，节点信息占20字节，边信息占10字节，节点编号占6字节，边信息储存在表节点中，
图的其他信息有三个各占4字节，求总的储存空间
(2)求一个图中的各连通分量的时间复杂度，图储存在邻接表中，说明你的理由
4、给出14个长度不一的归并长度，画出最优5路归并树，并求树的WPL；
具体数我忘了随便编一个吧，只要是有序递增且不相等就行
如：3，4，7，14，16，22，32，37，43，54，67，73，78，80
四、编程题30分
1、写一个函数，作用是对一个没有0的数组，将负数排在正数前面，并给出时间复杂度；
2、对一个非递减有序单链表，删除其中重复的结点；
3、对一个二叉树，每个结点对应着一个权值，
tpedef struct BiTNode
{
int w;
BiTNode *lchild;
BiTNode *rchild;
}BiTNode , BiTree*;
写一个递归函数，其值返回由根节点到各叶节点经过的权值最大的和，给出函数头 ：int maxF(BiTree T);
813
数据结构部分
一、填空题
1、L是单向循环链表的指向头结点的指针，判断链表是否为空的条件是______
2、一颗排序二叉树有n个结点，深度为d，则插入一个结点的时间复杂度为____
3、链队列的入队的时间复杂度是_____
4、
二、判断题
1、哈夫曼树是一颗平衡二叉树
2、在拓扑排序中，如果在之前，说明存在一条从到的路径。
3、
三、选择题
1、给出了一种结构
typedef struct{
……
}LNode, *List
问定义一个这种类型的指针的语句是？
A、LNode L B、List L C、List *L D、都不对
2、适合存储边稠密图的结构是
A、邻接表 B、邻接矩阵 C、逆邻接表 D、都不对
四、简答题
1、给出了一个静态链表SAPCE[MAXSIZE]，大概这样
（图片在附件里，是SPACE.jpg）
（1）画出对应的链表。（应该是这么问的，我就把静态链表看成链式存储结构画了出来）
（2）画出从静态链表中删除H后的SPACE[MAXSIZE]；
（3）定义了静态链表结点类型，请写出删除函数void free( position k)
typedef intposition;
typedefstruct{
elemtype data;
position k;
}SPACE[MAXSIZE]；
（4）和顺序表相比，静态链表的主要优点是？
（5）和链式存储结构相比 ，静态链表的主要优点是？
2、给了一种表达式树，A*(B+C*D)的表达式树如图
(图片是表达式树.jpg)
（1）写出前序、中序、后序遍历的序列
（2）写出A*(B+C*D)的后缀表达式
（3）构造表达式树需要一个栈和后缀表达式，问栈的元素的类型是什么？简要说说构造表达式树的方法。
（4）按照上述方法，画出构造表达式树时栈内元素的变化情况。
3、
（1）说明希尔排序为什么比直接插入排序效率高
（2）给了一个包含10个数的序列，增量序列分别是5、3、1，写出每一趟排序后的结果。
（3）给了希尔排序的算法的代码，要求补全。
（4）若要排序大块文件的话，希尔排序的效率特别低，请设计一种方法，使得每次只需要移动一趟。（这题我也记得很模糊，具体问法参考一下其他的回忆试题）
五、算法题
1、定义循环队列的结构
typedef struct{
int MAXSIZE；
int front; //指向队头元素
int num; //指出队内元素个数
elemtype * Elems;// 指向存储队列区域的指针。
}*Queue;
（1）写出建立一个队列的函数QueueCreateQueue(int MAXSIZE)
(2)写出删除队列的函数void DeleteQueue(Queue Q);
(3)写出将一个元素入队的函数 void EnQueue(Queue Q, elemtypek)
(4)写出返回队头元素并将其删除的函数elemtype DeQueue(Queue Q)
3、有向无权图的顶点用数字表示。现要计算从源点S到其他顶点的最短路径。LAST[MAXSIZE]是一个数组，LAST[w]=v表明从S到点w的最短路径的最后一条弧是
（1）找出源点S是哪一点。
（2）写出从源点到其他各点的最短路径
（3）补全利用BFS寻找源点到其他各点最短路径的代码。（不难）
计算机组成原理部分
一、填空题
1、计算机内的浮点数使用补码表示。X=,Y=,则按照浮点数加减的方法，X-Y=____。（尾数部分是我乱给的。两个数都带有负号。我不知道为啥说用补码表示，尾数却不是用补码表示。）
file:///C:/Users/ADMINI~1/AppData/Local/Temp/msohtmlclip1/01/clip_image004.png
2、四个中断源，优先级为1>2>3>4。给出了四个中断源的屏蔽字，分别是1111、1110、0110、0100，问现在优先级从高到低是？
3、4GB的地址空间，页大小是4KB,一个页表项是4B，存放所有的页表项需要____级页表。
二、选择题
1、
3、内存和I/O统一编址。地址共有16位，分别为A0~A15，内存容量64Kb。现用64K*8的存储芯片构成内存。I/O使用的地址从FC00~FFFF，问这个芯片的片选逻辑是？
A、A15~A12进行与操作的结果
B、A15~A11进行与操作的结果
C、A15~A10……
D、A15~A9……
4、某条指令采用变址寻址加一级间接寻址。变址寄存器的内容是2000H，形式地址是1000H，内存地址1000H的内容是某个数，2000H的内容是某个数，3000H的是1000H，则最终读取到的数是？
A B C D
三、应用题
1、一个机器，地址有8位，按字节编址。CACHE的字块大小16B，cache总容量为32B。
（1）直接地址映像下访问cache的地址中，标记位、块号、块内地址分别有几位？
（2）2路组相联，标记位、块号、块内地址分别有几位？
（3）以3个地址为例（应该是让你自己举出3个地址），说明直接地址映像的命中率比2路组相联的高。
2、一个8位的机器，现要构成一个主存系统，大小为64KB，用R/~W控制读写（高写低读）。前8KB是系统区，用ROM。接下来的24KB是用户区，用RAM。最后2KB是系统工作区。现在可用的芯片有：8K*8的ROM，16K*1的SRAM，8K*8的SRAM, 2K*8的SRAM，一个2-4地址译码器（低使能），一个与非门。问如何构成这个主存系统？注意画出与CPU的连接（感觉这题有点bug。而且当时我固定认为与非门就是双输入的，吃了思维僵化的亏。）
