软件基础练习答案一、单选题1、向顺序栈中压入新元素时，应当（A）。A先移动栈顶指针，再存入元素B先存入元素，再移动栈顶指针C先后次序无关紧要D同时进行2、一个对象序列的排序码为46，79，56，38，40，84，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（ C ）。A38，46，79，56，40，84 B38，79，56，46，40，84 C40，38，46，56，79，84 D38，46，56，79，40，843、线性链表不具有的特点是（A）。A随机访问B不必事先估计所需存储空间大小C插入与删除时不必移动元素D所需空间与线性表长度成正比4、设有一个10阶的对称矩阵A1010，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组B 中，A00存入B0中，则A85在B 中（ C ）位置。A32 B33 C41 D655、具有65个结点的完全二叉树的高度为（C）。（根的层次号为0）A8 B7 C6 D56、若待排序对象序列在排序前已按其排序码递增顺序排序，则采用（A）方法比较次数最少。A直接插入排序B快速排序C归并排序D直接选择排序7、对有14个数据元素的有序表R14进行折半搜索，搜索到R3的关键码等于给定值，此时元素比较顺序依次为（ C ）。AR0，R1，R2，R3 BR0，R13，R2，R3CR6，R2，R4，R3 DR6，R4，R2，R38、与数据元素本身的形式、内容、相对位置、个数无关的是数据的（B）A存储结构 B 逻辑结构 C 算法 D 操作9、链式栈与顺序栈相比，一个比较明显的优点是（B）A插入操作更加方便 B 通常不会出现栈满的情况C 不会出现栈空的情况D 删除操作更加方便10、对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是（C）A直接选择排序 B 直接插入排序 C 快速排序 D 起泡排序11、若采用邻接矩阵法存储一个N个顶点的无向图，则该邻接矩阵是一个（D）A上三角矩阵 B 稀疏矩阵 C 对角矩阵 D 对称矩阵12、在一个顺序存储的循环队列中，队头指针指向队头元素的（A）A前一个位置 B 后一个位置 C 队头元素位置 D 队尾元素的前一位置13、用链表表示线性表的优点是（C）A便于随机存取 B 花费的存储空间比顺序表少C 便于插入与删除D 数据元素的物理顺序与逻辑顺序相同14、对5个不同的数据元素进行直接插入排序，最多需要进行（B）次比较。A 8B 10C 15D 2515、下列存储形式中，（D）不是树的存储形式A双亲表示法 B 左子女右兄弟表示法C 广义表表示法D 顺序表示法16、在一棵具有5层的满二叉树中结点数为（A）A 31B 32C 33D 1617、设有100个数据元素，采用折半搜索时，最大比较次数为（B）A 6B 7C 8D 1018、在DOS操作系统中，文件系统采用链接结构，但链接指针不是存放在文件的物理块中，而是存放在( B )A.文件目录中B.文件分配表FAT中C.磁盘上D.磁盘上的某些磁盘块中19、页式存储管理是将主存分成大小相同的区域，称为块。把作业的地址空间分成大小相等的页。页与块的关系是( B )A.页大于块B.两者相等C.块大于页D.不确定的20、处于等待状态的进程，当它的等待事件结束后，( A )A.转换成就绪状态B.就立即执行C.只要有处理机，21、在操作系统中，存储管理主要是对( A )的管理。A.内存资源B.外存资源C.内存和外存资源D.所有存储资源二、填空题22、在计算机系统中把系统中的两个或两个以上的进程无限期地等待_永远不会发生的事件_称为死锁。23、文件是一个逻辑上具有完整意义的_.一组相关信息的有序集合_。24、自动地与数据库文件名同名的索引文件是_。25、数据流图由数据流、加工、_、数据流的源点和终点组成。26、进程存在的标志是_ PCB(进程控制块)_，它随进程的创建而建立，进程的消亡而撤消。27、计算机系统中所有的(硬件)和（软件），统称为计算机资源。28、操作系统的功能和任务主要有以下五个方面处理机管理，存储器管理，(设备管理)，（文件管理），（作业管理）。29、操作系统按用户的使用环境及访问方式可分为（多道批处理操作系统），（分时OS），（实时OS）。30、一个进程的活动情况至少可以划分为三种基本状态：（运行状态）。（就绪状态）和（等待状态）。31、深度为k的完全二叉树至少有（2K-1）个结点，至多有（2K-1）个结点。若按自上而下从左到右次序给结点编号（从1开始）。则编号最小的叶子结点的编号是（2K-1。）三、名词解释32.数据结构33.多道程序设计34.数据的逻辑独立性35.模块设计36. 操作系统37. 堆38. 死锁39. 硬件四、判断题（）1、数据的基本单位是数据项。（）2、数组元素之间的关系，既不是线性的，也不是树形的。（）3、对于有n个对象的待排序序列进行归并排序，所需平均时间为O（nlog2n）。（）4、用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。（）5、在霍夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应当特殊处理。（）6、线性表采用顺序存储表示时，必须占用一片连续的存储单元。（）7、由树转化成二叉树，其根的右子女指针总是空的。（）8、直接选择排序是一种稳定的排序方法。（）9、算法的运行时间涉及加、减、乘、除、转移、存、取、等基本运算。要想准确地计算总运算时间是不可行的。（）10、二维数组是数组元素为一维数组的线性表，因此它是线性结构。（）11、顺序表用一维数组作为存储结构，因此顺序表是一维数组。（）12、通常使用两个类来协同表示单链表，即链表的结点类和链表类。（）13、栈和队列都是顺序存取的的线性表，但它们对存取位置的限制不同。（）14、在使用后缀表表示实现计算器时用到一个栈的实例，其作用是暂存运算对象。（）15、具有n个结点的完全二叉树的高度为log2n+1。（）16、为度量一个搜索算法的性能，需要在时间和空间方面进行权衡。（）17、闭散列法通常比开散列法时间效率更高。（）18、一棵m阶B树中每个结点最多有m个关键码，最少有2个关键码。五、简答题1、已知某二叉树的前序序列为EBADCFHGI，中序序列为ABCDEFGHI，请给出二叉树的后序序列。解：构造出的二叉树如下：后序序列为ACDBGIHFE。六、综合算法题1、一个一维整数数组Am中有n (nm)个非空整数，它、们相继存放于数组的前端并已按非递减顺序排列，针对下列三种情况，分别编写相应的函数。（1）在数组A 中插入一个新的整数x ，并使得插入后仍保持非递减有序。要求x 插在值相等的整数后面。（5分）void InsertSort (int A , int m , int & n , int x)解：插入函数如下：void InsertSort (int A , int m , int & n , int x) if (nint I,j ;for (i=0 ; ifor (j=n-1 ; j=I ; j- )Aj+1 = A j ;A I =x ;n+;elsecerr（2）将数组中所有整数原地逆置，即利用原数组空间将数组中全部元素反转。void reverse (int A , int n )解：逆置函数如下：void reverse (