《计算机软件技术基础》复习题及答案(完美打印版)

计算机软件技术基础试题 。 A. 所有的操作算法实现简单 B. 便于随机存取 C. 便于插入和删除 D. 便于利用零散的存储器空间 n 个 的有限序列。 A. 表元素 B. 字符 C. 数据元素 D. 数据项 E. 信息项 n 的线性表采用顺序存储结构，在其第I 个位置插入一个新元素的算法的时间复杂度为 。（ 1 I n+1） A. O(0) B. O(1) C. O(n) D. O( 是一个线性表 (a1,a n)，采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为 ，平均每删除一个元素需要移动的元素个数为 ；若元素插在 之间 (0 I 概率为)1( )(2 nn 平均每插入一个元素所要移动的元素个数为 ； A. 2123 12 4 13 它们在 n 时的无穷大阶数，最大的是 。 A. B. . 2n/2 D. n! s 所指结点加到 p 所指的结点之后，其语句应为： 。 A. s-p+1; p-s; B. (*p)s; (*s)*p)C. s-p-p-s-D. s-p-p-s; 最少的比较次数是 。 A. n B. 2. D. 2n 一个无头结点链表 过程，作为参数的两个链表都是按结点的 由大到小链接的。合并后新链表的结点仍按此方式链接。请填 写下述空框，使程序能正确运行。 # h, *p; h = (); h- p = h; = & = if( /*较大的元素先插入 */ p- (1) ; p = (2) ; (3) ; p- (4) ; p = (5) ; (6) ; s p if( (7) ; if( (8) ; h-h); 参考答案： C C D D A (1) (2) p-(3) ha=4) (5) p-6) hb=7) p- (8) p- 中所有元素 (a1,a n)与表 B 的一个顺 序 子 表 (bk,b k+完 全 相 同 （ 即a1=bk,a2=,a n=bk+则称表 A 包含在表 B 中。设 带头结点的单链表，分别表示有序表 ，下面的函数用于判别表 中，若是，则返回 则返回 提示：用递归实现） # # # * (1) ; (2) ) if( (3) ; (4) ; (5) ; 参考答案： (1) if(2) & 3) (4) (5) 数 n)建立一个具有 n 个结点的循环链表；函数n,I,m)对由 n)所建立的具有 删除链表中的所有结点。参数 n(n0)指明循环链表的结点个数，参数 I(1 I n)指明起始结点，参数 m（ m0 是步长），指明 从起始结点或前次被删除并输出的结点之后的第 如，对于下图所示的具有 6个结点的循环链表，在调用 ,3,2)后，将输出 5,1,3,6,4,2。请在空框处填上适当内容，每框只填一个语句。 # n) *p, *q; ; if(n0) (); p = =1; I; q = (); (1) ; (2) ; p- n; (3) ; /*建立从尾链到首的环形结构 */ n, j, m) p, *q; j; p = n); I1;p = p-(4) ; (5) ; %8d”,q - (6) ; q); j=j+1; 参考答案： (1) p- q; (2) p = q; (3) p- 4) j=0 (5) q=p-(6) p- q-数 ,B)用于求两集合之差 C=当且仅当 中的一个元素，且不是 B 中的元 素时， e 是 C 中的一个元素。集合用有序链表实现，用一个空链表表示一个空集合，表示非空集合的链表根据元素之值按递增排列，执行 C=后，表示集合 A 和 B 的链表不变，若结果集合 C 非空，则表示它的链表应根据元素之值按递增序排列。函数 用于在链表中添加结点。 # x) ); x; A ,B) C,*C=); (1) ) - - A=A- (2) ) A=A-B=B- 3) ; (4) ) - A=A- (5) ; ; C=C- ); 参考答案： (1) A!= B!=2) A-B-3) B=B-(4) A!=5) 充空格，使其成为完整的算法。其功能是在一个非递减的顺序存储线性表中(从下标 1 处开始存储 )，删除所有值相等的多余元素。 #0 *表长 */ L) i,j; i=1,j=2; (1) ) -i!=L-j) if(j!=(i+1) (2) ; L- (3) ; (4) ; if(jL- (5) ; 参考答案： (1) 2) k=j;k+)L-k-(=L-k; (3) i+,j=i+1; (4) j+; (5)L- A 位置。 A. 链头 B. 链尾 C. 链中 14. 若用单链表表示队列，则应该选用 B 。 A. 带尾指针的非循环链表 B. 带尾指针的循环链表 C. 带头指针的非循环链表 D. 带头指针的循环链表 常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印，先放入打印缓冲区的数据先被打印。该缓冲区应该是一个 B 结构。 A. 堆栈 B. 队列 C. 数组 D. 线性表 的数组来实现循环队列，且当前 值分别为 0 和 3。当从队列中删除一个元素，再加入两个元素后， B 。 A. 1 和 5 B. 2 和4 C. 4 和 2 D. 5 和1 ,2， ,10 ，输出序列为a1,a 10，若 0，则 C 。 A. 4 B. 8 ,2,3,4，则 D 不可能是其出栈序列。 A 1243 B. 2134 C. 1432 D. 4312 D 是 a 子串。 A. B. 321C. “ D. “21 20. 若串 S=”， 其 子 串 的 数 目 是 C 。 A. 8 B. 37 C. 36D. 9 1:100,1:100的三对角矩阵，按行优先存入一维数组 B1:298中， A 中元素 5(即该元素的下标 )在 B 。 A. 198 B. 195 C. 197 D. 196 h 的二叉树只有度为 0 和 2 的结点，则此类二叉树的结点数至少为 B ，至多为 F 。高为 h 的完全二叉树的结点数至少为 E ，至多为 F 。 A 2h B. 2 C. 2h+1 E. 2 F. 2 G. 2h+1 H. 2h+1 24 个叶结点的完全二叉树，最多有 B 个结点。 A. 247 B. 248 C. 249 D. 251 该二叉树是 C 。 A. 满二叉树 B. 哈夫曼树 C. 堆 D. 二叉查找树 F ；前序遍历和后序遍历结果相同的二叉树为 B 。 A. 一般二叉树 B. 只有根结点的二叉树 C. 根结点无左孩子的二叉树 D. 根结点无右孩子的二叉树 E. 所有结点只有左孩子的二叉树 F. 所有结点只有右孩子的 二叉树 n 个结点的完全二叉树，已经顺序存储在一维数组 A1.，下面的算法是将 A 中顺序存储变为二叉链表存储的完全二叉树。请填写适当语句在下面的空格内，完成上述算法。 #0 *p, ,n) (1) ; p-I; (2) ) (3) ; p- (4) ) (5) ); p- p ,n) p,A,1,n); 参考答案： (1) p=() (2) 2*,2*I,n) (4) 2*I+1,2*I+1,n 线性表应该 C 。 A. 元素按值有序 B. 采用顺序存储结构 C. 元素按值有序，且采用顺序存储结构 D. 元素按值有序，且采用链式存储结构 256 个元素的线性表分成 16 块最好，每块的最佳长度是 16 ；若每块的长度为 8，其平均检索长度 为 21 。 个关键字互为同义词，若用线性探测法把这 K 个关键字存入散列表中，至少要进行 D 次探测。 A. B. K 次 C. K+1 次 D. K(K+1)/2 次 30.在 n 个记录的有序顺序表中进行折半查找，最大的比较次数是 1n。 术广泛应用于查找过程，选择 数的标准是 和 。处理冲突的技术有优有劣，其共同标准是 。 需辅助存储空间最多的是 B ，所需辅助存储空间最小的是 C ，平均速度最快的是 A 。 B. 归并排序C. 堆排序 佳内部排序的方法是 A 。 A. 直接插入排序 B. 冒泡排序C. 简单选择排序 (比 A 的性能差。 A. 堆排序 B. 冒泡排序 C. 简单选择排序 (时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是 C 。 A. 快速排序 B. 堆排序 C. 归并排序 D. 希尔排序 000个元素组成的序列中第 5个最小元素之前的部分排序的序列，用 B 方法最快。 A. 冒泡排序 B. 快速排序 C. 希尔排序 D. 堆排序 E. 简单选择排序 A 。 A. 100,90,80,60,85,75,20,25,10,70,65,50 B. 100,70,50,20,90,75,60,25,10,85,65,80 要求排序是稳定的，则应选 C 。 A. 快速排序 B. 堆排序 C. 归并排序 D. 希尔排序 后将其放在已排序序列的合适位置，该排序方法称为 A 排序法。 A. 插入排序 B. 交换排序 C. 选择排序 D. 归并排序 B 。 A. O( B. O(n) C. O( D. O(将空白部分填上： 将任意序列调整为最大堆通过不断调用 数，即 i=n/2;i0;i, n); 其中 下标 1开始），n 为序列元素的个数。 , n) /*将以 调整元素放在 组中，最大元素下标为 n*/ (1) ; 2* (3) = (4) ; (5) = 参考答案： (1) (2) ; (3) (4) = 2; (5) 41. 表是一种数据结构，链表是一种 (1) 。队列和栈都是线性 表，栈的操作特性是 (2) ，队列的操作特性是 (3) 。今有一空栈 S，对下列待进栈的数据元素序列a,b,c,d,e,f 依次进栈、进栈、出栈、进栈、进栈、出栈的操作，则此操作完成后，栈 S 的栈顶元素为 (4) ，栈底元素为 (5) 。 供选答案： (1): A. 非顺序存储线性表 B. 非顺序存储非线性表 C. 顺序存储线性表 D. 顺序存储非线性表 (2): A. 随机进出 B. 先进后出 C. 先进 先出 D. 出优于进 (3): A. 随机进出 B. 先进后出 C. 后进后出 D. 进优于出 (4): A. f B. c C. a D. b (5): A. b B. c C. a D. d 答案： (1) 进行管理，以方便用户、提高计算机使用效率的一种系统软件。它的主要功能有：处理机管理、存储管理、文件管理、 (2) 管理和 设备管理等。 最常用的两类操作系统。前者是一个具有图形界面的窗口式的 (3) 系统软件，后者是一个基本上采用 (4) 语言编制而成的的系统软件。在 (5) 操作系统控制下，计算机能及时处理由过程控制反馈的信息并作出响应。 供选答案： (1): A. 应用软件 B. 系统软硬件 C. 资源 D. 设备 (2): A. 数据 B. 作业 C. 中断 D. I/O (3): A. 分时 B. 多任务 C. 多用户 D. 实时 (4): A. B. 宏 C. 汇编 D. C (5): A. 网络 B. 分时 C. 批处理 D. 实时 答案： 按从大到小的顺序输出输入整数中互不相等的那些整数。 程序一边读入整数，一边构造一个从大到小顺序链接的链表，直至不能从键盘读入整数，然后顺序输出链表上各表元的整数值。主函数每读入一个整数，就调用函数 ，函数 将还未出现在链表上的整数按从大到小的顺序插入到链表中。 为了插入方便，链表在表首有一个辅助表元。 阅读下列 C 代码，在 (n) 处填入相应的字句以完成上述功能。 # x) u, *v, *p; u = v = u- (1) & x /*寻找插入位置 */ u=v;v=u- v=| (2) ) /*判断是否要插入表元 */ p = (); p- x; /*生成新表元 */ (3) = v; (4) = p;/*插入新表元 */ x; *p; /*首先建立只有辅助表元的空链表 */ (); (5) = n” ); %d” ,&x) = 1) /*反复读入整数插入链表 */ x); p=p!=p=p-*输出链表 */ %dt” ,p- n” ); 答案： (1) v != v (2) x v- x != v-3) p-4) u-5) 以访问的最小数据信息单位是 (1) ，可以引用的最小命名数据单位是 (2) 。 线性表是最简单的一种数据结构，有顺序和链接两 种存储方式。线性表按链接方式存储时，每个结点的包括 (3) 两部分。 线性表的查找有 (4) 和 (5) 两种，但 (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. 浏览 答案： 入到链表，或从链表删除一个整数。 阅读下面的 C 代码，将应填入 (n) 处的字名写在答卷的对应栏内。 # x) /*将 x 按从小到大的次序插入链表 */ u, *v=*p; v != & x v = v-*寻找插入位置 */ if(v != & x = v-*已有，被忽略 */ p = ();p-x; /*生成新表元 */ if(v = p; (1) ; (2) ; x) /*从链表中删除值为 x 的表元 */ u, *v; v = v != & x u=v;v=v- if(v != & x = v- /*找到值为 x 的表元 */ if(v = (3) ; (4) ; /*释放空间 */ 没有找到 !n” ); x, *p; ) n 输入 1：将整数插入到链表。 n 输入 2：从链表删除一个整数。 n” ); 其它整数，结束程序。 n” ); d,& (5) ) 输 入 整数： ” ); %d” ,&x); if(1) x); x); p=p!=p=p- %4d” ,p- 答案： (1) u- p; (2) p- v (3) u- v-4) v) (5) = 1 & = 2 46. 从未排序的序列中，依次取出元素，与已排序序列的元素比较后，放入已排序序列中的恰当位置上，这是 (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. 占用存储多少和处理的数据量大小 答案： (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. D. 寄存器 答案： 8. A 是信息的载体，它能够被计算机识别、存储和加工处理。 A. 数据 B. 数据元素 C. 结点 D. 数据项 C 。 i=1;& j+; if(i=j) p); 供选答案： A. O( B. O(2n) C. O( D. O(个数组元素占 1 个存储单元，则元素 C 。 A. = (m+( B. = (m+( C. = (n+( D. = (n+( 61. 以下哪一个不是队列的基本运算 C 。 A. 从队尾插入一个新元素 B. 从队列中删除第 i 个元素 C. 判断一个队列是否为空 D. 读取队头元素的值 n 的顺序表中，向第 i 个元素之前插入一个新元素，需向后移动 B 个元素。 A. B. C. D. i 向前移动 A 个元素。 A. B. C. D. i n 个单元的顺序存储的循环队列中，假定 别为队首指针和队尾指针，则判断队空的条件是 B 。 A. B. C. =D. 查找成功的情况下，需平均比较 D 个结点。 A. n B. n/2 C. (2 D. (n+1)/2 a,b,c,d,e，则栈不可能的输出序列是 C 。 A. B. C. D. 7. 栈结构通常采用的两种存储结构是 A 。 A. 顺序存储结构和链表存储结构 B. 散列方式和索引方式 C. 链表存储结构和数组 D. 线性存储结构和非线性存储结构 T（最多元素为 空的条件是 B 。 A. C. A 。 A. B. . . = 知 q 所指结点是 p 所指结点的前驱结点，若在 p 和 q 之间插入 s 结点，则应执行 C 。 A. s- p-p-s; B. p- s-s-p; C. q- s; s-p; D. p- s; s-q; /*前驱结点指针 */ /*后继结点指针 */ 下面给出的算法是要把一个 为非空双向链表中的 正确完成要求的算法段是 C 。 A q-p; q-p-p-q; p-q; B. p-q, q-p; p-q; q-p-C. q-p-q-p;p-q;p-q; D. 以上均不对 特殊性体现在 B 。 A. 可以顺序存储 B. 数据元素是一个字符 C. 可以链接存储 D. 数据元素可以是多个字符 p和 q，求 q 在 p 中首次出现的位置的运算称作 B 。 A. 连接 B. 模式匹配 C. 求子串 D. 求串长 ， ，函数x,y)返回 x 和 y 串的连接串， s,I,j)返回串 s) 返回串 s 的长度，则,s1,2) 的结果是 D 。 A. B. . 5. 常对数组进行的两种基本操作是 C 。 A. 建立和删除 B. 索引和修改 C. 查找和修改 D. 索引和查找 。 A. 二维数组和三维数组 B. 三元组和散列 C. 三元组和 十字链表 D. 散列和十字链表 先根次序遍历得到的结点序列为 B 。 A. B. . D. 为 0 的结点个数为 为 2 的结点数为 A 。 A. B. . D. 序遍历结点的访问 顺序是 其后序遍历结点的访问顺序是 A 。 A B. . D. D 不是树的存储形式。 A. 双亲表示法 B. 孩子链表表示法 C. 孩子兄弟表示法 D. 顺序存储表示法 81. 已知一棵二叉树的中序序列为 序序列为 该二叉树为 B 。 82. 已知一棵权集 W=2,3,4,7,8,9的哈夫曼树，其加权路径长度 。 A. 20 B. 40 C. 80 D. 160 m 的树中有 的结点， 的结点， ， m 的结点，问这棵树中叶子结点为 。 A. 1+ B. 1+1) C. n1+ +. m 棵二叉树中， 不是完全二叉树。 h 的二叉树上只有度为 0 或度为 2 的结点，则此类二叉树中所包含的结点数至少为 B 。 A. 2h B. 2 C. 2h+1 D. h+1 。 A. B. C. D. 序遍历序列是 其前序遍历序列为 D 。 A. B. C. . 2 是由有序树 T 转换而来的二叉树，则 2 中结点的 A 。 A. 前序 B. 中序 C. 后序 D. 层次序 叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。下面结论正确的是 A 。 A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B. 树的先根遍历序列与其对应的二叉树的后序遍历序列相同 C. 树的先根遍历序列与其对应的二叉树 的中序遍历序列相同 D. 以上均不对 90. 深度为 5 的二叉树至多有 个结点。 A. 16 B. 32 C. 31 D. 10 91. 在一非空二叉树的中序遍序序列中，根结点的右边 A 。 A. 只有右子树的所有结点 B. 只有右子树的部分 C. 只有左子树的部分结点 D. 只有左子树的所有结点 92. 树最适合用来表示 。 A. 有序数据元素 B. 无序数据元素 C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据 93. 设 n， m 为一棵二叉树上的两个结点，在中序遍历时， n 在 m 前的条件是 C 。 A. n 在 m 的右方 B. n 是 m 的祖先 C. n 在 m 的左方 D. n 是 m 的子孙 m 个树叶 ,n 个结点，深度为 h，则 D 。 A. n=h+m B. h+m=2n C. m= D. n=2序为 该二叉树后序为 。 A. B. . D. 20,16,13,14,19)，经过下列过程将这些记录排序。 20,16,13,14,19 16,20,13,14,19 13,16,20,14,19 13,14,16,20,19 13,14,16,19,20 所用的排序方法是 A 。 A. 直接插入排序 B. 冒泡排序 C. 希尔排序 D. 堆排序 个序列用快速排序的方法进行排序，以序列的第一 个元素为基础进行划分，在第一趟划分过程中，元素移动次数最多的是 A 序列。 A. 70,75,82,90,23,16,10,68 B. 70,75,68,23,10,16,90,82 C. 82,75,70,16,10,90,68,23 D. 23,10,16,70,82,75,68,90 坏情况下，执行的时间为 D 。 A. O(n) B. O( C.O( D. O(键码（即关键字）比较的次数与记录的初始排列次序无关的是 D 。 A. 希尔排序 B. 冒泡排序 C. 直接插入排序 D. 直接选择排序 归并的趟数为 。 A. n B. n C. D. 101. 一组记录的排序代码为46,79,56,38,40,84，则 利用堆排序的方法建立的初始堆为 B 。 A. 79,46,56,38,40,80 B. 84,79,56,38,40,46 C. 84,79,56,46,40,38 D. 84,56,79,40,46,38 102. 一组记录的排序代码为46,79,56,38,40,84，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为 。 A. 38,40,46,56,79,84 B.