苏州大学2018年硕士研究生入学考试初试试题（B卷）科目代码：872 科目名称：数据结构与操作系统满分：150分一、数据结构部分1、（15分）判断题，判断下列说法是否正确，如错误，指出错误之处。
（1）对于哈希（散列）查找，若采用线性探测法解决冲突，则装填因子α可以大于1。
（2）在A VL树上进行查找，平均查找长度为。
（3）一棵完全二叉树的高度为h，则该树至少有个结点。
（4）一个线性表，如果在对其进行操作的过程中表的长度经常发生变化，则采用顺序存储结构较合适。
（5）在使用后缀表达式计算表达式值时，应用队列存放操作数和操作符。
2、（15分）若要对一个序列进行排序，且需要对其进行次插入操作，以及次查找最大值的操作。
现有堆和二叉排序树两种数据结构，分别从平均情况和最坏情况下分析各数据结构的时间复杂度。
（1）若考虑平均情况，则应采用哪种数据结构，时间复杂度分别为多少，并进行分析。
（2）若考虑最坏情况，则应采用哪种数据结构，时间复杂度分别为多少，并进行分析。
3、（15分）一个线性表的元素均为正整数，使用带头指针的单链表实现。
编写算法：判断该线性表是否符合：所有奇数在前面，偶数在后面。
4、（15分）一棵用二叉链表实现的二叉树，其每个结点包括以下部分内容：结点值data，左孩子lchild和右孩子rchild，还有一个size存储该结点子树上的结点总数，现size还未赋值。
编写算法：为size赋值。
5、（15分）一棵采用孩子-兄弟表示法的树，编写算法：统计树中度为k的结点的个数。
二、操作系统部分1、（15分）简答题。
（1）什么是物理设备和逻辑设备，说明它们之间的关系。
（2）进程在CPU中执行时，操作系统有哪些操作模式，为什么要区分这些操作模式？（3）死锁解除的方法有哪些？请设计应用于手机操作系统的死锁解除方法。
2、（15分）采用动态优先级调度算法（优先数高的优先级低），根据运行时间和等待时间对优先数进行动态老化，具体老化算法如下：（a）处于等待状态的进程优先数p根据等待时间进行变化，每毫秒减一；（b）处于运行状态的进程优先数p根据运行时间进行变化，每毫秒加二；（c）优先数相同的进程按以下顺序调度：1）运行中的进程；2）先进入就绪队列的进程；（d）优先数p每隔1毫秒重新计算；（e）采用抢占式调度策略。
第 2 页第 1 页(a) 2 (b) 4(c) 6(a) I S = 2 A ，R = 1 Ω (b) I S = -2 A ，R = 1 Ω(c) I S = 2 A ，R = 2 Ω2018 年攻读硕士学位研究生招生考试试题(答案书写在本试题纸上无效。
考试结束后本试题纸须附在答题纸内交回) 共 6 页 提示：本考场可携带使用计算器考试科目: 适用专业:（873）电 路电 气 工 程第 3 页4Ω+ 6ΩU Su 1 -R 1u o1 R 2R u u oiRR图 3.24、电路如图 3.3 所示，求 U S ，计算图中元件功率各为多少？并验算功率是否平衡。
（12 分）2AR 1 aR 2 bd- 5u 1 +c图 3.35、应用戴维南定理求解图示 3.4 电路中的电流 I 。
（12 分）2018 年攻读硕士学位研究生招生考试试题(答案书写在本试题纸上无效。
考试结束后本试题纸须附在答题纸内交回) 共 6 页考试科目:（873）电 路适用专业:电 气 工 程二、简答题（共 5 题，每题 4 分，共 20 分）1、在电路等效变换过程中，受控源的处理与独立源有哪些相同？有什么不同？2、额定电压相同、额定功率不等的两个白炽灯，能否串联使用？3、实际应用中，我们用高内阻电压表测得某直流电源的开路电压为 225V ，用足够量程的电流表测 得该直流电源的短路电流为 50A ，问这一直流电源的戴维南等效电路参数？4、何谓串联谐振电路的谐振曲线？说明品质因数 Q 值的大小对谐振曲线的影响。
5、三相四线制供电体系中，为什么规定中线上不得安装保险丝和开关？三、分析计算题（共 9 题）1、列出图 3.1 所示电路的结点电压方程。
（10 分）图 3.12018 年攻读硕士学位研究生招生考试试题(答案书写在本试题纸上无效。
考试结束后本试题纸须附在答题纸内交回) 共 6 页考试科目: （873）电路适用专业:电气工程图3.6第6 页第5 页。
2018浙江大学878专业课试题回忆版2018浙江大学878专业课试题回忆版写在前面：如果有错误，那就我也没招了。
以下提供了一些不负责并且可能不靠谱的复习建议，请理智阅读。
第一部分程序设计语言（C）一．单选题（一题2分，15题，一共30分）1.下列不能正确表述x属于[-5,0]的是A.x>=-5&&x<=0B.x<=0&&x>=-5B.!(x<-5&&x>0) D.-5<=x<=02.下面选项中与while括号中等价的是while(x%3){........}A.x%3!=0B.x%3==1C.x%3==2D.x%3==3后面的题记不起来了，但是比较难的考点是二维数组的存储方式和两个下标怎么对应到一维线性的位置，就是a[-1][3]这样的访问为何不越界。
stdin和stdout 的可读性和可写性，还有static变量的特性，但是这个题最后返回的是一个局部变量，题目不难，就是很考耐心，一定要慢慢读题，慢慢阅读代码。
选择题和填空题最喜欢就是字符串数组指针数组数组指针二维指针，这个务必要看，要看明白了，今年C语言有30+的题目考点在上面，还有一个题是解析++p->c 这个表示意思（p是指向结构体数组第二位的指针，c 是结构体成员），还有就是指针和地址的差别，为什么两个字符串常量相减是错的（可以从字符串常量在C 程序的存储位置来理解），有一题是”1234”[2]这样的操作。
剩下的没啥难题了应该。
二．读程序（一题6分，5题，一共30分）第一个题的考点是将插入排序的两个循环的内层循环封装成一个函数。
题目看起来吓人，自己脑子跑起来也比较容易出错。
第二个题的考点是进制转换，16进制转化成10进制，但是他不是真的做转换，会加入一些无关的信息，让你模拟起来也比较恶心。
第三个的考点是char*s[]={“computer”,“science”};chat*p=s;然后p[1]++是什么东西。
南京工业大学2018 年硕士研究生入学考试初试试题（A 卷）科目代码：828 科目名称：数据结构与操作系统满分：150 分注意: ①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回！第一部分：数据结构（共90 分）一、单项选择题（下列每题给出的四个选项中，只有一项符合试题要求。
每小题2分，共30 分）1、通常所说的时间复杂度是指__________。
A.语句的频度B.算法的时间消耗C.渐进时间复杂度D.最坏的时间复杂度2、等概率条件下,在由 n 个结点构成的顺序表上做插入结点操作,需平均移动的结点数为__________。
A.nB.(n-1)/2C.n/2D.(n+1)/23、向具有 n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是__________。
A.O(1)B.O(n)1 / 10C.O(n2)D.O(log2n)4、从一个栈顶指针为 top 的链栈中删除一个结点时,用 x 保存被删除的结点,20 应执行列命令。
A.x=top; top=top->nextB.top=top->next;=top->dataB.C.x=top->data;D,x=top->data;top=top->next5、循环队列 SQ 队满的条件是__________。
A.SQ->rear=SQ->froat;B.(SQ->rear+1)%MAXLEN=SQ->froatC.SQ->rear+2=SQL->froatD.(SQ->rear+2)%MAXLEN=SQL->froat6、某队列允许在两端进行入队操作,但仅允许在一端进行出队操作(称为输出受限的双端队列),若五个元素 a,b,c,d,e 依次进队,则不可能得到的出队顺序是__________。
