当前位置：文档之家 › 2006年苏州大学计算机真题

2006年苏州大学计算机真题

  • 格式：pdf
  • 大小：176.39 KB
  • 文档页数：2

苏州大学考研论坛出品/forum-118-1.html
苏州大学2006年研究生招生考试试题
专业：计算机
一、数据结构部分
注意：算法可用类C、类C++、类JAVA或类PASCAL任一语言编写，并有类型说明。

1、（15分）名词解释：
（1）堆栈
（2）最小生成树
（3）折半（二分）查找
（4）堆排序
（5）连通分量
2、（15分）双端队列是限定插入和删除操作在表的两端进行的线性表。

假设依次输入数据元素为1、2、
3、
4、5和6，请问通过使用（a）队列；（b）双端队列，能否得到下列输出序列？
（1）1 2 3 4 5 6 （2）2 4 3 6 5 1 （3）1 5 2 4 3 6
（4）4 2 1 3 5 6 （5）1 2 6 4 5 3 （6）5 2 6 3 4 1
3、（15分）试设计一个算法，将二叉树的叶子结点按从左到右的顺序放入一个线性表。

假设二叉树采用二叉链表存储结构，线性表采用动态分配顺序存储结构。

4、（15分）子串的定位操作index（s，t）通常称为串的模式匹配（其中t称为模式），试编写一个模式匹配算法，匹配过程为：先匹配模式的首尾字符，若匹配成功，调用函数substr（取子串）来检查模式的首尾之间的字符是否与目标的相应字符相匹配，若匹配不成功，则进行下一次匹配。

5、（15分）请采用递归方式对一个单链表进行归并排序。

假设单链表中每个元素皆为整数，试设计算法完成此操作。

二、操作系统部分
6、（15分）请判断以下的说法是否正确，并说明理由。

（1）在单CPU的计算机系统中，进程是不能并行操作的。

（2）当死锁发生后，参与死锁的所有进程都占有资源。

（3）存储管理中的请求式分页系统必定需要重定位机制的支持。

7、（15分）请解释以下的概念
（1）中断
（2）虚拟设备
（3）中级调度
（4）Cache
（5）LRU算法
8、（15分）在虚拟存储技术中，系统将进程运行时所缺的页面调入内存的时机有预调页策略和请求式调页策略两种。

请说明这两种策略的原理，并结合具体的实例比较这两种策略的优劣。

2006年苏州大学论坛资源共享计划Wednesday, December 27, 2006。

合集下载

2006-2007 学年考试试卷答案(A卷)

2006-2007 学年考试试卷答案(A卷)

《计算机网络技术》试卷A答案一、填空题（15分）1. 物理（2分） 2 语法（2分） 3. CSMA/CD （2分）4 192.168.1.128 (3分)5 10Mbps 100m (4分)6 32 （2分）二、选择题（每题1.5分，共45分）三、问答题（16分）1、以间接方式发送，对主机A来说，接收其IP数据报的下一站是路由器R1的接口0。

（2分）因为主机A发送IP数据报主机B时，会把目的主机B的IP地址和主机A本身的子网掩码相与，即128.116.78.129和255.255.255.128相与，得到一个网络地址：128.116.78.128；而主机A把其IP地址和子网掩码相与可以得到其所在网络的网络地址202.116.78.0，前后得到的网络地址不一致，因此主机A可以知道主机B与其本身不在同一网络，因此会把IP数据报发送至其默认网关，即路由器R1的接口0。

（6分）2、发起的ARP进程的作用是根据主机B的IP地址IP2得到主机B的硬件地址MAC2。

（2分）在此ARP进程运行时，A向其所在的网络发送ARP请求广播报文，请求的内容是“我的IP地址是IP1，硬件地址是MAC1，我想知道IP地址为IP2的主机的硬件地址”。

主机A所在网络上的所有主机都接收到此请求且都会把A的IP地址和硬件地址的信息填入其ARP cache，但只有B会发回相应的ARP响应。

（6分）四、应用题（24分）1、（1）主机H1和路由器R1接口0、1的IP地址配置错误。

因为主机H1和路由器R1接口0的IP和子网掩码255.255.255.128相与的结果为128.30.33.128，与子网1的网络地址不一致；而路由器R1接口的接口1的IP地址和子网掩码255.255.255.128相与的结果为128.30.33.0，与子网2的网络地址不一致。

主机H1和路由器R1的IP地址可以配置为128. 30.33.1至128.30.33.126之间除主机H2的IP地址128.30.33.11外的任何IP地址。

计算理论试卷06年解析

计算理论试卷06年解析

(a)F 正则语言对于有限次并才是封闭的，可数可能是可数无穷次(b)F 如果状态q只有自循环的一条路，那么进入这个状态就不能停机，自然不会接受任何语言。

如果状态q除了自循环还可以接受其他字符转移到其他状态，那么自然可能接受某个包含有限字符的语言。

(c)T 可以直接用上下文无关文法生成。

S→aSb，S→aSbb，然后来生成这个语言。

(d)T 假设接受L的下推自动机是M，那么M接受x的时候输出no，不接受x的时候输出yes，于是就可以判定是否x∈L的补。

(e)F 递归语言包含于递归可枚举语言，但是递归语言的补语言也是递归的。

(f)T 一个语言就是相应字符串的集合，如果可以按次序列举这些字符串。

根据定理5.7.2，语言是递归的当且仅当其是以字典序Turing可枚举。

因此选T。

(g)T 我们构造一个特殊的通用图灵机来半判定这个语言。

但这个通用图灵机收到“M”之后，随机生成2008个不同的输入，然后逐个对“M”模拟尝试。

如果2008个输入都接受了，那么停机，否则其中一个不接受通用图灵机也不会停机。

因此这个通用图灵机半判定了这个语言。

(h)F 只能判断L是可半判定而已。

如果L是可判定的，应该存在图灵机，如果x∈L则停机给出yes，否则停机给出no。

(i)F 首先如果A可以多项式时间归约到B，那么如果B∈P，那么A∈P。

而有限的语言不一定属于P。

例如整数划分问题，限定只能有10个数，每个数不超过100，那么可以接受的语言是有穷的，可是整数划分问题不属于P，因为其界限不是输入长度的多项式。

（详见课本6.2.3）因此不能说归约到又穷语言就属于P。

(j)T ≤p这个符号表示多项式时间归约。

假设B不是NP的，因为B可以多项式时间归约到C，那么C也不是NP的，那么和C是NPC的矛盾，因此B一定是NP的。

又因为A可以多项式时间归约到B，而A是NPC的，所以B是NPC。

解析：题目的意思应该是w中a的个数和b的个数的差是奇数，也就是a的个数和b的个数的和是奇数，也就是|w|是奇数。

苏州大学计算机专业研究生复试上机题目

苏州大学计算机专业研究生复试上机题目

苏州大学计算机专业研究生复试上机题目苏州大学计算机科学与技术学院研究生复试C（上机）题目1、2009年上级复试题（1）用IE浏览器从FTP上下载org.dat，并保存在D盘的根目录下。

（2）此文件中按文本方式存放了一段其他文章，其中有若干长度小于15的十进制或八进制数字，数字之间用“,”分开，数字内部存在且仅存在空格。

（3）八进制数以起始位“0”作为标示与十进制数区分。

（4）顺序读取这些数字将他们转变为十进制数后按从大到小的顺序排序后，输出到D盘根目录下new.txt，每个数字一行。

eg：_235_,34__2,_043_1_,1_3 分别是：十进制235，十进制342.，八进制431，十进制13。

_代表空格。

2、2008年上级复试题（1）用IE从FTP上下载org.dat，并保存在D盘的根目录中。

（2）此文件中按文本方式存放了一段其他文章，其中有若干长度小于15的英文单词，单词之间用空格分开，无其他符号。

（3）顺序读取这段文章的不同的单词（大小写敏感），同时在读取的过程中排除所有的单词THE以及变形，即这些单词不能出现在读取的结果中。

（4）将读取的所有单词的首字母转大写后，输出D根目录下new.txt，每个单词一行。

------------------------那段文字可以点右键打开方式中用记事本打开，内容是：The constructor is used to initialize the object The destructor is used to delete the Object the calling seqence of constructor is opposite to the calling sequence of destructor个人感觉今年出题挺有水平的，苏大一个重要的方向就是信息处理，这个应该就是分词技术的基础把，我做的一般，不过听说好象有将近满分的，还当然也有很多兄弟没做出来。

06级计算机专业计算机网络(双语)试卷A参考答案

06级计算机专业计算机网络(双语)试卷A参考答案

学院专业班级学号学生姓名计算机科学与技术专业2006级《计算机网络原理》课程考核试卷参考答案试卷 A （A/B/C）考试方式闭卷（闭卷/开卷）考试时间（120分钟）题号一二三四五六七八总分得分一、选择题（在每个小题四个备选答案中选出一个正确答案，填在题末的括号中）（本大题共 20 小题，每小题 1 分，总计 20 分）1. A2. A3. D4. B5. B6. A7. D8. B9. C 10. C二、填空题（本大题共 12 小题，每空 1 分，总计 30 分）1. WAN、MAN、LAN、HAN或PAN2. 传播3. 100、10Mbps、基带传输、双绞线4. 交换机端口、网卡（或主机）5. 广播、端口、MAC地址、网络层协议6. 隐藏终端、RTS/CTS7. IP地址、端口、套接字(Socket)三、简答题（本大题共6小题，总计分30分）1.应用层：定义用户需要的各种网络应用的信息交互协议。

表示层：定义两个端系统之间交换的信息在计算机网络中传输时的格式会话层：在计算机网络中两个端系统之间建立、组织和协调其交互（会话）传输层：在计算机网络中两个端系统之间传送以报文为单位的数据网络层：在计算机网络中两台主机之间传送以分组或包为单位的数据数据链路层：在两个相邻节点间的线路上，无差错地传送以帧为单位的数据物理层：为两个相邻节点提供一个物理连接，将信息以比特流方式在通信线路上传送。

每一层的名称各0.5分，基本功能各0.5分2. 答：There are ten 4000 Hz signals. We need nine guard bands to avoid any interference.The minimum bandwidth required is 4000 ⋅ 10 + 400 ⋅9 =43,600 Hz. （按计算步骤给分和扣分，每个步骤1分）3. 答：The upstream bandwidth is 37 MHz.Using QPSK with 2 bits/Hz, we get 74Mbps upstream.//4进制的The downstream bandwidth is 200 MHz.Using QAM-64, this is 1200 Mbps.//64进制（每个步骤1分）4.答：The output is 011110111110011111010.（2分）5. 答：LH LH LH HL HL HL LH HL LH HL6. 答：Let t = 0 denote the start of transmission. At t = 1 msec, the first frame has beenfully transmitted. At t = 271 msec, the first frame has fully arrived. At t = 272 msec, theframe acknowledging the first one has been fully sent. At t = 542 msec, the 得分得分得分应用层表示层会话层传输层网络层数据链路物理层学院专业班级学号学生姓名acknowledgement-bearing frame has fully arrived. Thus, the cycle is 542 msec. A total of kframes are sent in 542 msec, for an efficiency of k/542. Hence(a) k = 1, efficiency = 1/542 = 0.18%(b) k = 7, efficiency = 7/542 = 1.29%(c) k = 4, efficiency = 4/542 = 0.74%（每小题2分）7. 答：For a 1-km cable, the one-way propagation time is 5 μsec, so 2τ = 10 μsec. To makeCSMA/CD work, it must be impossible to transmit an entire frame in this interval. At 1Gbps, all frames shorter than 10,000 bits can be completely transmitted in under 10 μsec,so the minimum frame is 10,000 bits or 1250 bytes. （按计算步骤给分和扣分，每个步骤1分）8.答：直通方式：接收到目的地址后立刻查询转发表进行转发。