2019年西安交通大学814数据结构真题

一大题

avl的题 告诉11个数 然后 进行排序 求平均长度

二大题

哈希表公共溢出区告诉12个数 然后求平均长度

三（1）写图的邻接表结构

（2）对一个图进行dfs与bfs

（3）prim算法

四编程题

 将一个链表进行逆置求时间复杂空间复杂

问答题三个

 1、三个调度。然后进程挂起是靠那个调度完成的 为什么？

大题一

（1）用lru调度进行22个关键数的页面置换

（2）设计一个lru （用计数器和栈） 有标志位（我好像见过原题）

二 pv 100个学生 50台计算机  两个学生必须一组才能去申请一个电脑 然后管理员才让他们进去。 然后上机操作 操作完了要让老师检查。然后管理员才让走。

计算机组成原理。

第一道大题告诉16位指令 15-11 指令 10-8是寻址方式 7-5通用寄存器 4-0是地址。有000是一次间接寻址 001 010 011分布是寄存器间接寻址 变址寻址 相对寻址

第一问指令数量  寄存器数量。还有多少种寻址方式

第二问问各个寻址的范围

第三问问一个指令的数据是多少。那个画成2进制然后是相对寻址

第二道大题。10位 阶补尾补 各带一个符号位，第一问 写正数负数的最大值最小值

第二问写出x=（-23/32）*2^7 与y=（23/32）*2^6

第三问 x+y=？

第四问把第三问结果表示出来

代码题1 输入有限个x y 。x y代表二伟空间一个点，寻找一个最小矩形，包含所输入的所有点

要求输出该矩形左下顶点和右上的顶点

2.判断一个字符串是否是回文串（其中有空格，需要排除空格），第一问递归解决。第二问用栈解决

3.一个无序序列，找出其中的逆序对，要求O(nlogn)，如果不能在这个时间复杂度下实现，自己写一个程序，声明其时间复杂度

大题

第一个满k叉树的分支节点数为n  其叶子结点满足(K-1)n+1

数归法证明

第二个是用队列的基本操作实现栈的push和pop

最后一题，hash表，10个数据，表长17，哈希函数H1(key)＝key％17，冲突解决采用双重散列H2(key)＝(key%7＝＝0 ? 8:key%7)，第一问画表，第二问求查找成功ASL

还有个是支撑树定义最小支撑树 mst什么的，我不懂

还有4个任务 a b c d，问分别用哪些数据类型可以解决，写出基本算法

还有个相似二叉树算法

填空题有

广义表

快排递归时间复杂度

深度优先搜索邻接两种复杂度