2018年武汉轻工大学数学与计算机学院810数据结构考研基础五套测试题-一、填空题1 按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_的排序方法。【答案】稳定 2 中缀式运算结果为_。 【答案】【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。 3 完善算法:求KMP 算法.next 数组。 k :_；next1:0； k :_；END ；【答案】0；nextk 4 G 是一个非连通无向图，共有28条边，则该图至少有_个顶点。【答案】9【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。5 个有2001个结点的完全二叉树的高度是_。【答案】11【解析】完全二叉树的高度 6 数据结构是研讨数据的_和_以及它们之间的相互关系，并对与这种结构定义相应的_, 设计出相应的_。【答案】逻辑结构；物理结构；操作(运算) ；算法(c-d)对应的前缀式为_，若a=l，b=2, c=3, d=4, 则后缀式的7 一个字符串中_称为该串的子串。【答案】任意个连续的字符组成的子序列 8 设用希尔排序对数组98，36，-9，0，47，23，1，8，10，7进行排序，给出的步长(也称增量序列) 依次是4， 2， 1则排序需_趟，写出第一趟结束后，数组中数据的排列次序_。【答案】3; (10，7，-9，0，47，23，1，8，98，36) 9 一个算法具有5个特性: _、_、_、有零个或多个输入、有一个或多个输出。【答案】有穷性；确定性；可行性 10有五个数据依次入找:1，2，3，4，5。在各种出栈的序列中，以3，4先出栈的序列有_。(3在4之前出栈)【答案】3个【解析】以3，4先出栈的序列有34521、34215、34251共3个。 11设m 、n 均为自然数，m 可表示为一些不超过n 的自然数之和，f(m，n) 为这种表示方式的数目。例f(5，3) 5, 有5种表示方式:32, 311，221，2111，11111。以下是该函数的程序段，请将未完成的部分填入，使之完整。 _； _；，_) 执行程序，f(6，4) _。【答案】1; 1; f(m, n 1) ; n 9 12模式串【答案】01122312的next 函数值序列为_。二、单项选择题13设系统缓冲区和用户工作均采单, 从外读入1个数据块到系统缓冲区的时间为100, 从系统缓冲区读入1个数据块到用户工作区的时间为5, 对用户工作区中的1个数据块行分析的时间为90(如下图所示) 。进程从外设读入并分析2个数据块的最短时间是（ ） 图A.200B.295C.300D.390【答案】C【解析】数据块1从外设到用户工作区的总时间为105, 在这段时间中数据块2没有进行操作。在数据块1进行分析处理时, 数据块2从外设到用户工作区的总时间为105, 这段时间是并行的。再加上数据块2进行处理的时间90, 总共是300, 故答案为C 。 14某计算机主存容量为64KB ，其中ROM 区为4KB ，其余为RAM 区，按字节编址. 现要用2K 8位的ROM 芯片和4K 4位的RAM 芯片来设计该存储器，则需要上述规格的ROM 芯片数和RAM 芯片数分别是（ ）A.1、15B.2、15C.1、30D.2、30【答案】D【解析】主存储器包括RAM 和ROM 两部分，由于ROM 区为4KB ，则RAM 区为60KB. 存储容量的扩展方法有字扩展、位扩展、字和位同时扩展三种. 选用2Kx8位的ROM 芯片，只需采用2片芯片进行字扩展便可得到4KB 的ROM 区；选用4Kx4位的RAM 芯片，需采用(60)/4*2片芯片进行字和位同时扩展便可得60KB 的RAM 区. 15若磁盘转速为7200转/分, 平均寻道时间为8ms , 每个磁道包含1000个扇区, 则访问一个扇区的平均存取时间大约是（ ）。 A. B.-一、填空题-考研试题-