《计算机软件技术基础》复习题(含答案).doc 28页

'《计算机软件技术基础》复习题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.nlognC.2n/2D.n!spnextnextnext6.将下图所示的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-1C.n-1D.2n28 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和4C.4和2D.5和117.设栈的输入序列为1,2，…,10，输出序列为a1,a2,…,a10，若a5=10，则a7为C。（未要求一次性全部输入或输出）A.4B.8C.不确定D.718.设栈的输入序列是1,2,3,4，则D不可能是其出栈序列。A．1243B.2134C.1432D.431219.以下ABD是C语言中”abcd321ABCD”的子串。A.abcdB.321ABC.“abcABC”D.“21AB”20.若串S=”software”，其子串的数目是B。A.8B.37C.36D.922.设高为h的二叉树只有度为0和2的结点，则此类二叉树的结点数至少为B，至多为F。高为h的完全二叉树的结点数至少为E，至多为F。A．2hB.2h-1C.2h+1D.h+1E.2h-1F.2h-1G.2h+1-1H.2h+123.一棵有124个叶结点的完全二叉树，最多有B个结点。A.247B.248C.249D.25124.若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是C。（记）A.满二叉树B.哈夫曼树C.堆D.二叉查找树25.前序遍历和中序遍历结果相同的二叉树为F；前序遍历和后序遍历结果相同的二叉树为B。A.一般二叉树B.只有根结点的二叉树28 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,50B.100,70,50,20,90,75,60,25,10,85,65,8038.若要尽可能快地完成对实数数组的排序，且要求排序是稳定的，则应选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.插入28 C.比较D.归并(2):A.选择B.插入C.比较D.归并(3):A.冒泡B.交换C.比较D.散列(4):A.外部B.内部C.外存D.内存(5):A.运算量大小与占用存储多少B.运算量大小与处理的数据量大小C.并行处理能力和占用存储多少D.占用存储多少和处理的数据量大小答案：BAABA47.操作系统是对计算机资源进行的(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.寄存器答案：CDADB48.A是信息的载体，它能够被计算机识别、存储和加工处理。A.数据B.数据元素C.结点D.数据项49.下列程序段的时间复杂度为C。for(i=1;inext&&jnext;j++;}if(i==j)return(p);elsereturn(NULL);28 }供选答案：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.i63.从一个长度为n的顺序表中删除第i个元素时，需向前移动A个元素。A.n-iB.n-i+1C.n-i-1D.i64.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队空的条件是B。A.front=rear+1B.front=rearC.front+1=rearD.front=065.从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较D个结点。A.nB.n/2C.(n-1)/2D.(n+1)/266.一个栈的入栈序列是a,b,c,d,e，则栈不可能的输出序列是C。A.edcbaB.decbaC.dceabD.abcde67.栈结构通常采用的两种存储结构是A。A.顺序存储结构和链表存储结构B.散列方式和索引方式C.链表存储结构和数组D.线性存储结构和非线性存储结构68.判断一个顺序栈ST（最多元素为mo）为空的条件是B。A.ST->top<>0B.ST->top=0C.st->top<>moD.st->top==mo69.不带头结点的单链表head为空表的判定条件是A。A.head==NILLB.head->next==NULLC.head->next==headD.head!=NULL70.在一个单链表中，已知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;/*后继结点指针*/}28 下面给出的算法是要把一个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.BCDEFEF75.常对数组进行的两种基本操作是C。A.建立和删除B.索引和修改C.查找和修改D.索引和查找76.稀疏矩阵一般的压缩存储方法有两种，即Ｃ。A.二维数组和三维数组B.三元组和散列C.三元组和十字链表D.散列和十字链表77.对下图所示的二叉表，按先根次序遍历得到的结点序列为B。A.ABCDHEIFGB.ABDHIECFGC.HDIBRAFCGD.HIDBEFGAC78.在一棵二叉树上，度为0的结点个数为n0，度为2的结点数为n2，则n0=A。A.n2+1B.n2-1C.n2D.n2/279.某二叉树前序遍历结点的访问顺序是ABCDEFG，中序遍历结点的访问顺序是CBDAFGE，则其后序遍历结点的访问顺序是A。A．CDBGFEAB.CDGFEABC.CDBAGFED.CDBFAGE80.在下列存储形式中，D不是树的存储形式。A.双亲表示法B.孩子链表表示法C.孩子兄弟表示法D.顺序存储表示法81.已知一棵二叉树的中序序列为cbedahgijf，后序序列为cedbhjigfa，则该二叉树为B。82.已知一棵权集W={2,3,4,7,8,9}的哈夫曼树，其加权路径长度WPL为Ｃ。A.20B.40C.80D.16083.已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，…，nm个度为m的结点，问这棵树中叶子结点为Ｃ。A.1+ni(I-1)B.1+ni(I+1)C.n1+n2+…+nmD.m·nm84.如下图所示的4棵二叉树中，Ｃ不是完全二叉树。85.设高度为h的二叉树上只有度为0或度为2的结点，则此类二叉树中所包含的结点数至少为B。A.2hB.2h-1C.2h+1D.h+128 86.如下图所示的二叉树的中序遍历序列是Ｃ。A.abcdgefB.dfebagcC.dbaefcgD.defbagc87.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，则其前序遍历序列为D。A.acbedB.decabC.deabcD.cedba88.如果T2是由有序树T转换而来的二叉树，则T中结点的前序就是T2中结点的A。A.前序B.中序C.后序D.层次序89.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。下面结论正确的是A。A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同B.树的先根遍历序列与其对应的二叉树的后序遍历序列相同C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同D.以上均不对90.深度为5的二叉树至多有Ｃ个结点。A.16B.32C.31D.1091.在一非空二叉树的中序遍序序列中，根结点的右边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的子孙94.对一个满二叉树，m个树叶,n个结点，深度为h，则D。A.n=h+mB.h+m=2nC.m=h-1D.n=2h-195.如果某二叉树的前序为stuwv，中序为uwtvs，则该二叉树后序为Ｃ。A.uwvtsB.vwutsC.wuvtsD.wutsv96.设待排序的记录为(20,16,13,14,19)，经过下列过程将这些记录排序。20,16,13,14,1916,20,13,14,1913,16,20,14,1913,14,16,20,1913,14,16,19,20所用的排序方法是A。A.直接插入排序B.冒泡排序C.希尔排序D.堆排序97.对下列4个序列用快速排序的方法进行排序，以序列的第一个元素为基础进行划分，在第一趟划分过程中，元素移动次数最多的是A序列。A.70,75,82,90,23,16,10,68B.70,75,68,23,10,16,90,8228 C.82,75,70,16,10,90,68,23D.23,10,16,70,82,75,68,9098.用快速排序的方法对包含几个关键字的序列进行排序，最坏情况下，执行的时间为D。A.O(n)B.O(log2n)C.O(nlog2n)D.O(n2)99.在所有排序方法中，关键码（即关键字）比较的次数与记录的初始排列次序无关的是D。A.希尔排序B.冒泡排序C.直接插入排序D.直接选择排序100.在归并排序过程中，需归并的趟数为Ｃ。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}，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为Ｃ。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.每次把待排序的区间划分为左、右两个子区间，其中左区间中元素的排序码均小于等于基准元素的排序码，右区间中元素的排序码均大于等于基准元素的排序码，此种排序方法叫做B。A.堆排序B.快速排序C.冒泡排序D.希尔排序104.一组记录的排序码为一个字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W}，按归并排序方法对该序列进行一趟归并后的结果为D。A.D,F,Q,X,A,B,N,P,C,M,W,YB.D,F,Q,A,P,X,B,N,Y,C,M,WC.D,Q,F,X,A,P,N,B,Y,M,C,WD.D,Q,F,X,A,P,B,N,M,Y,C,W105.一组记录的排序码为{25,48,16,35,79,82,23,40,36,72}，其中，含有5个长度为2的有序表，按归并排序方法对该序列进行一趟归并后的结果为A。A.16,25,35,48,23,40,79,82,36,72B.16.25,35,48,79,82,23,36,40,72C.16,25,48,35,79,82,23,36,40,72D.16,25,35,48,79,23,36,40,72,82106.设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用Ｃ排序法。A.冒泡排序B.快速排序C.堆排序D.希尔排序107.在待排序的元素序列基本有序的前提下，效率最高的排序方法是A。A.插入排序B.选择排序C.快速排序D.归并排序28 108.用某种排序方法对线性表{25,84,21,47,15,27,68,35,20}进行排序时，元素序列的变化情况如下：(1)25,84,21,47,15,27,68,35,20(2)20,15,21,25,47,27,68,35,84(3)15,20,21,25,35,27,47,68,84(4)15,20,21,25,27,35,47,68,84则所采用的排序方法是D。A.选择排序B.希尔排序C.归并排序D.快速排序109.快速排序方法在Ｃ情况下最不利于发挥其长处。A.要排序的数据量太大B.要排序的数据中含有多个相同值C.要排序的数据已基本有序D.要排序的数据个数为整数110.设有一个已按各元素的值排好序的线性表，长度大于2，对给定的值K，分别用顺序查找法和二分查找法查找一个与K相等的元素，比较的次数分别为s和b。在查找不成功的情况下，正确的s和b的数量关系是B。A.总有s=bB.总有s>bC.总有s0，则继续执行；若S<0则C。A.将进程阻塞，插入等待队列B.将队列中的一个进程移出，使之处于运行状态C.将队列中的一个进程移出，使之处于就绪状态D.将进程变为挂起状态142.在进程的调度算法中，D是动态优先数的确定算法。A.按进程使用的资源进行调度B.按进程在队列中等待的时间进行调度C.按时间片轮转调度D.非剥夺方式优先数调度143.作业控制块JCB的内容不包括C。A.作业的状态B.作业进入系统的时间C.作业对进程的要求D.作业对资源的要求144.设有一组作业，它们的提交时刻及运行时间如下表所示：作业号提交时刻运行时间(分钟)19:007029:403039:5010410:105则在单道方式下，采用短作业优先调度算法，作业的执行顺序为D。A.1,3,4,2B.4,3,2,1C.4,1,2,3D.1,4,3,2145.有如下三个作业：A1以计算为主，A2以输入/输出为主，A3是计算和输入/输出兼顾，在作业调度中，若采用优先级调度算法，为尽可能使处理器和外部设备并行工作，则它们的优先级从高到低的排列顺序是C。A.A1,A2,A3B.A2,A3,A1C.A3,A2,A1D.A2,A1,A3146.下面几个选项中，作业里肯定没有的是D。A.程序B.初始数据C.作业说明书D.通道程序147.作业调度程序不能无故或无限地拖延一个作业的执行，这是作业调度的A。A.公平性原则B.平衡资源使用原则C.极大的流量原则D.必要条件148.作业调度是A。A.从输入进挑选作业进入主存B.从读卡机挑选作业进输入井C.从主存中挑选作业进程处理器D.从等待设备的队列中选取一个作业进程149.用户通过D直接在终端控制作业的执行。A.C语言B.汇编语言C.操作控制命令D.作业控制语言150.在作业调度算法中，C兼顾了短作业与长作业。A.先来先服务B.计算时间最短优先28 C.均衡调度D.最高响应比优先151.某作业的任务是某紧急事务处理，应选择C算法较为合适。A.先来先服务B.短作业优先C.优先数调度D.响应比高者优先152.现有三个同时到达的作业J1、J2和J3，它们的执行时间分别为T1、T2和T3，且T1