31842-2019年西安交通大学814数据结
构真题回忆
814.
数据结构。

选择五个。

忘了
-大题avIl的题告诉11个数然后进行排序求平均长度
二大题哈希表公共溢出区告诉12个数然后求平均长度
三(1) 写图的邻接表结构
(2)对一个图进行dfs与bfs
(3) prim算法
四编程题将一个链表进行逆置求时间复杂空间复杂
oS填空10个吧。

忘了
问答题三个1、三个调度。

然后进程挂起是靠那个调度完成
的为什么?
2、3、忘了。

大题一(1) 用ru调度进行22个关键数的页面置换(2) 设
计一个ru (用计数器和栈) 有标志位(我好像见过原题)
二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=?
第四问把第三问结果表示出来
915
[题型分布与分值]
选择10*2
判断5*2.
填空5*2
简答7道应该是15*2+16*1+7*4
编程题15*2+10*1
代码题1输入有限个xy。

xy代表二伟空间一个点，寻找-
个最小矩形，包含所输入的所有点
要求输出该矩形左下顶点和右上的顶点2.判断一个字符串是否是回文串(其中有空格,需要排除空
格)，第一问递归解决。

第二问用栈解决
3.-个无序序列，找出其中的逆序对,要求O(nlogn), 如果
不能在这个时间复杂度下实现，自己写一个程序,声明其时间复杂度
.大题
第一个满k叉树的分支节点数为n其叶子结点满足(K-1)n+1数归法证明
第二个是用队列的基本操作实现栈的push和pop
后题, hash表, 10个数据，表长17,哈希函数H1(ke
y) = key%17,冲突解决采用双重散列H2(key)= (key%7 =
=0 ? 8:key%7),第一问画表，第二问求查找成功ASL
还有个是.支撑树定义
最小支撑树mst什么的，我不懂
还有4个任务abcd,问分别用哪些数据类型可以解决，写出基本算法
还有个相似二叉树算法
填空题有
广义表
快排递归时间复杂度
深度优先搜索邻接两种复杂度。