当前位置：问答库＞考研试题

华 研 考 试 网 ww w. ed uk y. ne t中 国 考 研 专 业 课 知 名 品 牌

华 研 考 试 网 ww w. ed uk y. ne t中 国 考 研 专 业 课 知 名 品 牌

华 研 考 试 网 ww w. ed uk y. ne t中 国 考 研 专 业 课 知 名 品 牌

华 研 考 试 网 ww w. ed uk y. ne t中 国 考 研 专 业 课 知 名 品 牌

华 研 考 试 网 ww w. ed uk y. ne t中 国 考 研 专 业 课 知 名 品 牌

华 研 考 试 网 ww w. ed uk y. ne t中 国 考 研 专 业 课 知 名 品 牌

南昌大学 2003 年攻读硕士学位研究生 入 学 考 试 试 题 报考专业:计算机应用 数据结构部分 一. 单项选择题.(每题 2 分,共 8 分) 1.对由 n 个记录组成的文件排序,如果 n 较小(n<50)且记录的规模较大,则采用( A.直接插入 A. K B.直接选择 C.快速 C.1/2K(K-1) C. a[5,8] C. 3,4,6,5,2,1 D.堆 )次探测. D.1/2K(K+1) )的起始地址相同. D. a[0, 9] )不是合法的出栈序列. D. 2,3,4,1,5,6 )排序方法节省时间. 考试科目:数据结构操作系统(A) 2.假定有 K 个关键字互为同义词,若用线性探测法把这些同义词存入散列表中,至少要进行( B. K2(K 的平方) B. a[3,10] B. 4,5,3,1,2,6 3.二维数组 a[0…8, 1…10]按行存放时元素 a[8, 5]的起始地址与按列存放时元素( A. a[8,5] A. 5,4,3,6,1,2 4.有 6 个元素按 6,5,4,3,2,1 的顺序进栈,下列( 林.(9 分) 3. 图的广度遍历算法中既可以在一个点入队时对其访问,也可以在顶点出队时对其访问,请问前一种 方法有何优点?后一种方法可能产生什么问题?并以下图为例说明.(6 分) V0 V1 V2………Vn Vn+1 四. 算法题.(共 31 分) 1. 清除重复结点. 单链表中数据域的值相同的结点称为重复结点.如线性表(2,1,1, 3,2,1,) 清除重复 结点后为(2,1, 3).试用 C 语言写一函数清除单链表 head 中的重复结点,并指出每个工作指针的作 用.( 15 分) 华 研 少?(假设查找表的长度为 n.) (9 分) 考 2. 顺序查找,二分法查找和分块查找三种方法对查找表中元素各有什么要求? 平均的查找长度各是多 试 网 ww 1. 设二叉树 的 后根 序 列 为 HDEBIFGCA, 中 根 序 列是 DHBEAIFCG, 画出此二叉树和它所 对应的 森 w. 三. 简答与画图题(共 24 分) ed uk y. 4. 高度为 h 的完全二叉树上至少有_______个结点, 至多有_______个结点. ne 队列长度的最大值是____________. t中 3. 用数组 Q[0..n-1]存放循环队列, f, r 分别为队头,队尾指针,则队列长度的计算公式是__________. 国 考 2. 高度为 6 的 AVL 树至少有________结点.(设空二叉树高度为 0) 研 .rchild; ______________↑ q:=p 专 针域 lchild 与 rchild 分别指向该结点的左,右孩子,则执行下列语句可找到结点 P 业 课 1. (假定该后继结点存在):↑的中序(对放序)后继结点 q↑设 P 指向二叉树中某个 S 结点,结点有二个指 知 二.填空题(每题 3 分,共 12 分) 名 品 牌

2. 找第 k 项. n 个元素的第 k 项是把它们从小到大的排序后的第 k 个元素.如(16,12,99,95,18,87,10) 的第 4 项是 18.假定 n 个整数放在数组 a [1..n] 中,试写一算法,不经对整个数组排序,找到第 k 项.并写 出此算法在最好和最坏情况下的时间复杂度. (提示,利用快速排序中的划分方法.) (16 分) 操作系统部分 一.名词解释(每题 2 分,共 10 分) 1. 分时与分时系统 2. 进程控制块 3. 系统颠簸(抖动) 4. 位示图 5. 设备驱动程序 一. 简答题(每题 4 分,共 20 分) A.n B.m C.m-n 发进程,它们( ) A. 必定无关 华 研 3.在操作系统中,一方面每个进程具有独立性,另一方面进程之间又具有相互制约性.对于任何两个并 B.必定相关 C.可能相关 D.可能相同 4.一个虚拟存储器系统中,设主存的容量为 16MB,辅存的容量为 1GB,而地址寄存器的位数 32 位.在这 样的系统中,虚存的最大容量是( A.1GB B.16MB ). C.1GB+16MB D.4GB ) D.其他结构文件 5.采用直接存取法来读写磁盘上的物理记录时,效率最高的是( A.连续结构的文件 A.先来先服务 B.索引结构的文件 C.链接结构文件 ) 6.下列算法中可用于进程调度,磁盘调度,I/O 调度的是( B. SSTF 服务 C.时间片轮转 考 试 网 ww 则信号量的初始值为( ). w. 2.设有 n 个进程共用一个相同的程序段(临界区),如果每次最多允许 m 个进程(m

8.死锁的 4 个必要条件无法破坏的是( A.互斥条件 B.请求与保持条件 ). C.非抢夺条件 D 循环等待条件 ). 9.文件系统采用多级目录结构后,对于不同用户的文件,其文件名( A.应该相同 B.应该不同 C.可以不同,也可以相同 ). D.受系统约束 10 最容易开成很多小碎片的可变分区分配算法是( A.首次适应算法 B.最佳适应算法 C.最坏适应算法 D.以上算法都不会 四,改错题(划出下列句子中的错误的地方并改正,简单的否定无分.每小题 2 分,共 10 分) 1. 进程有三个状态:运行态,就绪态和等待态. 2. 在分区存储管理方案中,作业的大小只受主存加辅存之和大小的 限制,可以实现虚拟存储. 3. 如果 CPU 正在执行一个 P 操作的时候,一个最高级中断到来,那么中断处理进程会抢夺 CPU. 4. 为了正确地按名存取,操作系统规定不同的文件均不能有相同的文件名. 外围设备. 五,计算题(25 分) V(S1); 网 ww Y:=Y+Z; Z:=Y+1; P(S2); . . . 间分配如下图所示. 程序 A 程序 B 程序 C Y:=Z+Y; w. Y:=1; 试 考 华 研 2. 设在单机系统内存中存放三道程序 A,B 和 C,按 A,B,C 的优先次序运行,其内部计算机 I/O 操作的时 计算 30m->I/O 40ms->计算 10ms 计算 60m->I/O→ 30ms->计算 10ms 计算 20m->I/O 40ms-→>计算 20ms 试画出按多道运行时的时间关系图(设有两个通道,取名为通道 1, 通道 2,调度程序的执行时间忽 略不计),并计算完成这三道程序共花多少时间及比单道程序运行节省多少时间.(9 分) 3. 桌子有一个盘子,每次只能放入一个水果,爸爸专向盘中放苹果,妈妈专向盘中放桔子,女儿专等吃盘 ed P(S1); X:=X+Y; V(S2); Z:=X+Z; . . . uk . . X:=1; X:=X+1; y. . . ne . . t中 进程 P1 进程 P2 国 考 结束后,X=?,Y=?,Z=? (6 分) 研 1. 设有两个优先权相同的进程,P1,P2 如下,令信号量 S1,S2 的初值均为 0,已知 Z=2,试问,P1,P2 执行 专 业 课 知 名 品 5. 通常,一个 CPU 可以连接多个通道,一个通道可以连接多个设备控制器,一个设备控制器可连接多台 牌

中的苹果,儿子专等吃盘中的桔子.试用 P, V 操作写出他们能正确同步的并发程序.(10 分). 华 研 考 试 网 ww w. ed uk y. ne t中 国 考 研 专 业 课 知 名 品 牌