《计算机软件技术》 复习资料（课程代码：11049）习题汇总：（一）1.线性表的链式存储结构与顺序存储结构相比优点是 CD 。

A. 所有的操作算法实现简单 B. 便于随机存取 C. 便于插入和删除 D. 便于利用零散的存储器空间2.线性表是具有n 个 C 的有限序列。

A. 表元素B. 字符C. 数据元素D. 数据项E. 信息项3.若长度为n 的线性表采用顺序存储结构，在其第I 个位置插入一个新元素的算法的时间复杂度为 C 。

（1≤I ≤n+1）A. O(0)B. O(1)C. O(n)D. O(n 2)4.设A 是一个线性表(a 1,a 2,…,a n )，采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为 B ，平均每删除一个元素需要移动的元素个数为A ；若元素插在a i 与a i+1之间(0≤I ≤n-1)的概率为)1()(2+-n n i n ，则平均每插入一个元素所要移动的元素个数为 C ； A. 21-n B.2n C. 312+n D. 413+n 5.下列函数中，按它们在∞→n 时的无穷大阶数，最大的是 D 。

A. log nB. nlog nC. 2n/2D. n!6.所指的结点之后，其语句应为： D 。

A. s->next=p+1; p->next=s;B. (*p).next=s; (*s).next=(*p).next;spnextnext nextC. s->next=p->next; p->next=s->next;D. s->next=p->next; p->next=s;7.将两个各有n个元素的有序表归并为一个有序表时，其最少的比较次数是 A 。

A. nB. 2n-1C. n-1D. 2n8.用单链表表示的链式队列的队头在链表的 A 位置。

A. 链头B. 链尾C. 链中9.若用单链表表示队列，则应该选用 B 。

A. 带尾指针的非循环链表B. 带尾指针的循环链表C. 带头指针的非循环链表D. 带头指针的循环链表10.在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印，先放入打印缓冲区的数据先被打印。

该缓冲区应该是一个 B 结构。

A. 堆栈B. 队列C. 数组D. 线性表11.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。

当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为 B 。

A. 1和5 B. 2和4C. 4和2D. 5和112.设栈的输入序列为1,2，…,10，输出序列为a1,a2,…,a10，若a5=10，则a7为 C 。

（未要求一次性全部输入或输出）A. 4B. 8C.不确定D.713.设栈的输入序列是1,2,3,4，则 D 不可能是其出栈序列。

A． 1243 B. 2134 C. 1432 D. 431214.以下 ABD 是C语言中”abcd321ABCD”的子串。

A. abcdB. 321ABC. “abcABC”D. “21AB”15.若串S=”software”，其子串的数目是 B 。

A. 8B. 37C. 36D. 916.设高为h的二叉树只有度为0和2的结点，则此类二叉树的结点数至少为 B ，至多为 F 。

高为h的完全二叉树的结点数至少为 E ，至多为 F 。

A． 2h B. 2h-1 C. 2h+1 D.h+1E. 2h-1F. 2h-1G. 2h+1-1H. 2h+117.一棵有124个叶结点的完全二叉树，最多有 B 个结点。

A. 247B. 248C. 249D. 25118.若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是 C 。

A. 满二叉树B. 哈夫曼树C. 堆D. 二叉查找树19.前序遍历和中序遍历结果相同的二叉树为 F ；前序遍历和后序遍历结果相同的二叉树为 B 。

A. 一般二叉树B. 只有根结点的二叉树C. 根结点无左孩子的二叉树D. 根结点无右孩子的二叉树E. 所有结点只有左孩子的二叉树F. 所有结点只有右孩子的二叉树20.假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行 D 次探测。

A. K-1次B. K 次C. K+1次D. K(K+1)/2次21.在n 个记录的有序顺序表中进行折半查找，最大的比较次数是⎣⎦1log 2+n 。

22.在下述排序算法中，所需辅助存储空间最多的是 B ，所需辅助存储空间最小的是 C ，平均速度最快的是 A 。

A.快速排序B. 归并排序C. 堆排序23.在文件局部有序或文件长度较小的情况下，最佳内部排序的方法是 A 。

A. 直接插入排序B. 冒泡排序C. 简单选择排序24.快速排序在最坏情况下时间复杂度是O(n 2)，比 A 的性能差。

A. 堆排序B. 冒泡排序C. 简单选择排序25.若需在O(nlogn)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是 C 。

A. 快速排序B. 堆排序C. 归并排序D. 希尔排序26.如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用B 方法最快。

A. 冒泡排序B. 快速排序C. 希尔排序D. 堆排序E. 简单选择排序27.以下结点序列是堆的为 A 。

A. 100,90,80,60,85,75,20,25,10,70,65,50B. 100,70,50,20,90,75,60,25,10,85,65,8028.若要尽可能快地完成对实数数组的排序，且要求排序是稳定的，则应选 C 。

A. 快速排序B. 堆排序C. 归并排序D. 希尔排序29.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为 A 排序法。

A. 插入排序B. 交换排序C. 选择排序D. 归并排序30.直接插入排序在最好情况下的时间复杂度为 B 。

A. O(logn)B. O(n)C. O(nlogn)D. O(n 2)31. 从未排序的序列中，依次取出元素，与已排序序列的元素比较后，放入已排序序列中的恰当位置上，这是 (1) 排序。

从未排序的序列中，挑选出元素，放在已排序序列的某一端位置，这是 (2) 排序。

逐次将待排序的序列中的相邻元素两两比较，凡是逆序则进行交换，这是 (3) 排序。

如果整个排序过程都在内存中进行，称为(4) 排序。

排序算法的复杂性与排序算法的 (5) 有关。

供选答案：(1): A. 选择 B. 插入C. 比较D. 归并(2): A. 选择 B. 插入C. 比较D. 归并(3): A. 冒泡 B. 交换C. 比较D. 散列(4): A. 外部 B. 内部C. 外存D. 内存(5): A. 运算量大小与占用存储多少B. 运算量大小与处理的数据量大小C. 并行处理能力和占用存储多少D. 占用存储多少和处理的数据量大小答案：BAABA32.操作系统是对计算机资源进行的 (1) 系统软件，是 (2) 的接口。

在处理机管理中，进程是一个重要的概念，它由程序块、 (3) 和数据块三部分组成，它有3种基本状态，不可能发生的状态转换是 (4) 。

虚拟存储器的作用是允许程序直接访问比内存更大的地址空间，它通常使用 (5) 作为它的一个主要组成部分。

供选答案：(1): A. 输入和输出 B. 键盘操作C. 管理和控制D. 汇编和执行(2): A. 软件和硬件 B. 主机和外设C. 高级语言和机器语言D. 用户和计算机(3): A. 进程控制块 B. 作业控制块C. 文件控制块D. 设备控制块(4): A. 运行态转换为就绪态 B. 就绪态转换为运行态C. 运行态转换为等待态D. 等待态转换为运行态(5): A. 软盘 B. 硬盘C. CDROMD. 寄存器答案：CDADB33. A 是信息的载体，它能够被计算机识别、存储和加工处理。

A. 数据B. 数据元素C. 结点D. 数据项34.下列程序段的时间复杂度为 C 。

for(i=1;i<n;i++){y=y+1;for(j=0;j<=(2*n);j++) x++;}供选答案：A. O(n-1)B. O(2n)C. O(n2)D. O(2n+1)35.下面程序段的时间复杂度为 D 。

i=1;while(i<=n) i=i*2;供选答案：A. O(1)B. O(n)C. O(n2)D. O(log2n)36.下面程序段的时间复杂度为 B 。

a=0;b=1;for(i=2;i<=n;i++){s=a+b;b=a;a=s;}供选答案：A. O(1)B. O(n)C. O(log2n)D. O(n2)37.数据结构是一门研究非数值计算的程序设计问题中，计算机的 A 以及它们之间的关系和运算等的学科。

A.操作对象B. 计算方法C. 逻辑存储D. 数据映象38.在数据结构中，从逻辑上可以把数据结构分成 C 。

A. 动态结构和静态结构B. 紧凑结构和非紧凑结构C. 线性结构和非线性结构D. 内部结构和外部结构39.算法分析的目的是 C 。

A. 找出数据结构的合理性B. 研究算法中输入和输出的关系C. 分析算法的效率以求改进D. 分析算法的易懂性和文档性40.算法分析的两个主要方面是 D 。

A. 间复杂性和时间复杂性B. 正确性和简明性C. 可读性和文档性D. 数据复杂性和程序复杂性41.一个线性顺序表第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址为 B 。

A. 110B. 108C. 100D. 12042.若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为P1,P2,P3,…,P n，若P1=n，则P i 为 C 。

A. iB. n-iC. n-i+1D.不确定43.对于一个栈，给出输入项A,B,C。

如果输入项序列由A,B,C所组成，则不可能产生的输出序列是 A 。

A. CABB. CBAC. ABCD. ACB44.设有如下的单链表的按序号查找的算法，其时间复杂度为 B 。

LinkNode *GetNode(Linklist head, int i){int j;ListNode *p;P = head; j=0;while(p->next && j<i){p = p->next;j++;}if(i==j)return(p);elsereturn(NULL);}供选答案：A. O(n2)B. O(2n)C. O(n3)D. O(logn)45.二维数组A mn按行序为主顺序存放在内存中，每个数组元素占1个存储单元，则元素a ij的地址计算公式是 C 。