《计算机软件技术基础》复习题含答案总结.docx
- 文档编号:16970538
- 上传时间:2023-07-20
- 格式:DOCX
- 页数:50
- 大小:62.10KB
《计算机软件技术基础》复习题含答案总结.docx
《《计算机软件技术基础》复习题含答案总结.docx》由会员分享,可在线阅读,更多相关《《计算机软件技术基础》复习题含答案总结.docx(50页珍藏版)》请在冰点文库上搜索。
《计算机软件技术基础》复习题含答案总结
《计算机软件技术基础》复习题
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(n2)
4.设A是一个线性表(a1,a2,…,an),采用顺序存储结构,则在等概率的前提下,平均每插入一个元素需要移动的元素个数为B,平均每删除一个元素需要移动的元素个数为
A;若元素插在ai与ai+1之间(0≤I≤n-1)的概率为
,则平均每插入一个元素所要移动的元素个数为C;
A.
B.
C.
D.
5.下列函数中,按它们在
时的无穷大阶数,最大的是D。
A.lognB.nlogn
C.2n/2D.n!
6.将下图所示的s所指结点加到p所指的结点之后,其语句应为:
D。
A.s->next=p+1;p->next=s;
B.(*p).next=s;(*s).next=(*p).next;
C.s->next=p->next;p->next=s->next;
D.s->next=p->next;p->next=s;
7.将两个各有n个元素的有序表归并为一个有序表时,其最少的比较次数是A。
A.nB.2n-1
C.n-1D.2n
13.用单链表表示的链式队列的队头在链表的A位置。
A.链头B.链尾C.链中
14.若用单链表表示队列,则应该选用B。
A.带尾指针的非循环链表B.带尾指针的循环链表
C.带头指针的非循环链表D.带头指针的循环链表
15.在解决计算机主机与打印机之间速度不匹配问题时,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则从该缓冲区中取出数据打印,先放入打印缓冲区的数据先被打印。
该缓冲区应该是一个B结构。
A.堆栈B.队列
C.数组D.线性表
16.若用一个大小为6的数组来实现循环队列,且当前rear和front的值分别为0和3。
当从队列中删除一个元素,再加入两个元素后,rear和front的值分别为B。
A.1和5B.2和4
C.4和2D.5和1
17.设栈的输入序列为1,2,…,10,输出序列为a1,a2,…,a10,若a5=10,则a7为C。
(未要求一次性全部输入或输出)
A.4B.8C.不确定D.7
18.设栈的输入序列是1,2,3,4,则D不可能是其出栈序列。
A.1243B.2134C.1432D.4312
19.以下ABD是C语言中”abcd321ABCD”的子串。
A.abcdB.321ABC.“abcABC”D.“21AB”
20.若串S=”software”,其子串的数目是B。
A.8B.37C.36D.9
22.设高为h的二叉树只有度为0和2的结点,则此类二叉树的结点数至少为B,至多为F。
高为h的完全二叉树的结点数至少为E,至多为F。
A.2hB.2h-1C.2h+1D.h+1
E.2h-1F.2h-1G.2h+1-1H.2h+1
23.一棵有124个叶结点的完全二叉树,最多有B个结点。
A.247B.248C.249D.251
24.若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序,则该二叉树是C。
(记)
A.满二叉树B.哈夫曼树
C.堆D.二叉查找树
25.前序遍历和中序遍历结果相同的二叉树为F;前序遍历和后序遍历结果相同的二叉树为B。
A.一般二叉树B.只有根结点的二叉树
C.根结点无左孩子的二叉树D.根结点无右孩子的二叉树
E.所有结点只有左孩子的二叉树F.所有结点只有右孩子的二叉树
29.假定有K个关键字互为同义词,若用线性探测法把这K个关键字存入散列表中,至少要进行D次探测。
A.K-1次B.K次
C.K+1次D.K(K+1)/2次
30.在n个记录的有序顺序表中进行折半查找,最大的比较次数是
。
32.在下述排序算法中,所需辅助存储空间最多的是B,所需辅助存储空间最小的是C,平均速度最快的是A。
A.快速排序B.归并排序C.堆排序
33.在文件局部有序或文件长度较小的情况下,最佳内部排序的方法是A。
A.直接插入排序B.冒泡排序C.简单选择排序
34.快速排序在最坏情况下时间复杂度是O(n2),比A的性能差。
A.堆排序B.冒泡排序C.简单选择排序
35.若需在O(nlogn)的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是C。
A.快速排序B.堆排序
C.归并排序D.希尔排序
36.如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列,用
B方法最快。
A.冒泡排序B.快速排序
C.希尔排序D.堆排序E.简单选择排序
37.以下结点序列是堆的为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
38.若要尽可能快地完成对实数数组的排序,且要求排序是稳定的,则应选C。
A.快速排序B.堆排序
C.归并排序D.希尔排序
39.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较,然后将其放在已排序序列的合适位置,该排序方法称为A排序法。
A.插入排序B.交换排序
C.选择排序D.归并排序
40.直接插入排序在最好情况下的时间复杂度为B。
A.O(logn)B.O(n)
C.O(nlogn)D.O(n2)
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.占用存储多少和处理的数据量大小
答案:
BAABA
47.操作系统是对计算机资源进行的
(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.寄存器
答案:
CDADB
48.A是信息的载体,它能够被计算机识别、存储和加工处理。
A.数据B.数据元素C.结点D.数据项
49.下列程序段的时间复杂度为C。
for(i=1;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) 50.下面程序段的时间复杂度为D。 i=1; while(i<=n)i=i*2; 供选答案: A.O (1)B.O(n)C.O(n2)D.O(log2n) 51.下面程序段的时间复杂度为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) 52.数据结构是一门研究非数值计算的程序设计问题中,计算机的A以及它们之间的关系和运算等的学科。 A.操作对象B.计算方法C.逻辑存储D.数据映象 53.在数据结构中,从逻辑上可以把数据结构分成C。 A.动态结构和静态结构B.紧凑结构和非紧凑结构 C.线性结构和非线性结构D.内部结构和外部结构 54.算法分析的目的是C。 A.找出数据结构的合理性 B.研究算法中输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 55.算法分析的两个主要方面是D。 A.间复杂性和时间复杂性B.正确性和简明性 C.可读性和文档性D.数据复杂性和程序复杂性 56.一个线性顺序表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址为B。 A.110B.108C.100D.120 57.若已知一个栈的入栈序列是1,2,3,…,n,其输出序列为P1,P2,P3,…,Pn,若P1=n,则Pi为C。 A.iB.n-iC.n-i+1D.不确定 58.对于一个栈,给出输入项A,B,C。 如果输入项序列由A,B,C所组成,则不可能产生的输出序列是A。 A.CABB.CBAC.ABCD.ACB 59.设有如下的单链表的按序号查找的算法,其时间复杂度为B。 LinkNode*GetNode(Linklisthead,inti){ intj; ListNode*p; P=head;j=0; while(p->next&&j p=p->next; j++; } if(i==j) return(p); else return(NULL); } 供选答案: A.O(n2)B.O(2n)C.O(n3)D.O(logn) 60.二维数组Amn按行序为主顺序存放在内存中,每个数组元素占1个存储单元,则元素aij的地址计算公式是C。 A.LOC(aij)=LOC(a11)+[(i-1)*m+(j-1)] B.LOC(aij)=LOC(a11)+[(j-1)*m+(i-1)] C.LOC(aij)=LOC(a11)+[(i-1)*n+(j-1)] D.LOC(aij)=LOC(a11)+[(j-1)*n+(i-1)] 61.以下哪一个不是队列的基本运算C。 A.从队尾插入一个新元素B.从队列中删除第i个元素 C.判断一个队列是否为空D.读取队头元素的值 62.在一个长度为n的顺序表中,向第i个元素之前插入一个新元素,需向后移动B个元素。 A.n-iB.n-i+1C.n-i-1D.i 63.从一个长度为n的顺序表中删除第i个元素时,需向前移动A个元素。 A.n-iB.n-i+1C.n-i-1D.i 64.在具有n个单元的顺序存储的循环队列中,假定front和rear分别为队首指针和队尾指针,则判断队空的条件是B。 A.front=rear+1B.front=rearC.front+1=rearD.front=0 65.从一个具有n个结点的单链表中查找其值等于x的结点时,在查找成功的情况下,需平均比较D个结点。 A.nB.n/2C.(n-1)/2D.(n+1)/2 66.一个栈的入栈序列是a,b,c,d,e,则栈不可能的输出序列是C。 A.edcbaB.decbaC.dceabD.abcde 67.栈结构通常采用的两种存储结构是A。 A.顺序存储结构和链表存储结构B.散列方式和索引方式 C.链表存储结构和数组D.线性存储结构和非线性存储结构 68.判断一个顺序栈ST(最多元素为mo)为空的条件是B。 A.ST->top<>0B.ST->top=0C.st->top<>moD.st->top==mo 69.不带头结点的单链表head为空表的判定条件是A。 A.head==NILLB.head->next==NULLC.head->next==headD.head! =NULL 70.在一个单链表中,已知q所指结点是p所指结点的前驱结点,若在p和q之间插入s结点,则应执行C。 A.s->next=p->next;p->next=s; B.p->next=s->next;s->next=p; C.q->next=s;s->next=p; D.p->next=s;s->next=q; 71.假设双向链表结点的类型如下: typedefstructLinknode{ intdata; structLinknode*lLink;/*前驱结点指针*/ structLinknode*rLink;/*后继结点指针*/ } 下面给出的算法是要把一个q所指新结点,作为非空双向链表中的p所指的结点前驱结点插入到该双向链表中,能正确完成要求的算法段是C。 A.q->rLink=p;q->lLink=p->lLink;p->lLink=q;p->lLink->rLink=q; B.p->lLink=q,q->rLink=p;p->lLink->rLink=q;q->lLink=p->lLink; C.q->lLink=p->lLink;q->rLink=p;p->lLink->rLink=q;p->lLink=q; D.以上均不对 72.串是一种特殊的线性表,其特殊性体现在B。 A.可以顺序存储B.数据元素是一个字符 C.可以链接存储D.数据元素可以是多个字符 73.设有两个串p和q,求q在p中首次出现的位置的运算称作B。 A.连接B.模式匹配C.求子串D.求串长 74.设串s1=”ABCDEFG”,s2=”PQRST”,函数con(x,y)返回x和y串的连接串,subs(s,I,j)返回串s的从序号i的字符开始的j个字符组成的子串,len(s)返回串s的长度,则con(sub(s1,2,len(s2)),sub(s1,len(s2),2))的结果是D。 A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF 75.常对数组进行的两种基本操作是C。 A.建立和删除B.索引和修改C.查找和修改D.索引和查找 76.稀疏矩阵一般的压缩存储方法有两种,即C。 A.二维数组和三维数组B.三元组和散列 C.三元组和十字链表D.散列和十字链表 77.对下图所示的二叉表,按先根次序遍历得到的结点序列为B。 A.ABCDHEIFGB.ABDHIECFG C.HDIBRAFCGD.HIDBEFGAC 78.在一棵二叉树上,度为0的结点个数为n0,度为2的结点数为n2,则n0=A。 A.n2+1B.n2-1 C.n2D.n2/2 79.某二叉树前序遍历结点的访问顺序是ABCDEFG,中序遍历结点的访问顺序是CBDAFGE,则其后序遍历结点的访问顺序是A。 A.CDBGFEAB.CDGFEAB C.CDBAGFED.CDBFAGE 80.在下列存储形式中,D不是树的存储形式。 A.双亲表示法B.孩子链表表示法 C.孩子兄弟表示法D.顺序存储表示法 81.已知一棵二叉树的中序序列为cbedahgijf,后序序列为cedbhjigfa,则该二叉树为 B。 82.已知一棵权集W={2,3,4,7,8,9}的哈夫曼树,其加权路径长度WPL为C。 A.20B.40C.80D.160 83.已知一棵度为m的树中有n1个度为1的结点,n2个度为2的结点,…,nm个度为m的结点,问这棵树中叶子结点为C。 A.1+ni(I-1)B.1+ni(I+1)C.n1+n2+…+nmD.m·nm 84.如下图所示的4棵二叉树中,C不是完全二叉树。 85.设高度为h的二叉树上只有度为0或度为2的结点,则此类二叉树中所包含的结点数至少为B。 A.2hB.2h-1C.2h+1D.h+1 86.如下图所示的二叉树的中序遍历序列是C。 A.abcdgefB.dfebagcC.dbaefcgD.defbagc 87.已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,则其前序遍历序列为 D。 A.acbedB.decabC.deabcD.cedba 88.如果T2是由有序树T转换而来的二叉树,则T中结点的前序就是T2中结点的A。 A.前序B.中序C.后序D.层次序 89.树的基本遍历策略可分为先根遍历和后根遍历;二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。 这里,我们把由树转化得到的二叉树叫做这棵树对应的二叉树。 下面结论正确的是A。 A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B.树的先根遍历序列与其对应的二叉树的后序遍历序列相同 C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D.以上均不对 90.深度为5的二叉树至多有C个结点。 A.16B.32C.31D.10 91.在一非空二叉树的中序遍序序列中,根结点的右边A。 A.只有右子树的所有结点B.只有右子树的部分 C.只有左子树的部分结点D.只有左子树的所有结点 92.树最适合用来表示C。 A.有序数据元素B.无序数据元素 C.元素之间具有分支层次关系的数据D.元素之间无联系的数据 93.设n,m为一棵二叉树上的两个结点,在中序遍历时,n在m前的条件是C。 A.n在m的右方B.n是m的祖先 C.n在m的左方D.n是m的子孙 94.对一个满二叉树,m个树叶,n个结点,深度为h,则D。 A.n=h+mB.h+m=2n C.m=h-1D.n=2h-1 95.如果某二叉树的前序为stuwv,中序为uwtvs,则该二叉树后序为C。 A.uwvtsB.vwuts C.wuvtsD.wutsv 96.设待排序的记录为(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.堆排序 97.对下列4个序列用快速排序的方法进行排序,以序列的第一个元素为基础进行划分,在第一趟划分过程中,元素移动次数最多的是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 98.用快速排序的方法对包含几个关键字的序列进行排序,最坏情况下,执行的时间为 D。 A.O(n)B.O(log2n)C.O(nlog2n)D.O(n2) 99.在所有排序方法中,关键码(即关键字)比较的次数与记录的初始排列次序无关的是 D。 A.希尔排序B.冒泡排序C.直接插入排序D.直接选择排序 100.在归并排序过程中,需归并的趟数为C。 A.nB. 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},则利用快速排序的方法,以第一个记录为基准得到的一次划分结果为C。 A.{38,40,46,56,79,84}B.{40,38,46,79,56,84} C.{40,38,46,56,79,84}D.{40,38,46,84,56,79} 103.每次把待排序的区间划分为左、右两个子区间,其中左区间中元素的排
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机软件技术基础 计算机软件 技术 基础 复习题 答案 总结