计算机软件技术基础试题库.docx
- 文档编号:1611410
- 上传时间:2023-05-01
- 格式:DOCX
- 页数:25
- 大小:72.58KB
计算机软件技术基础试题库.docx
《计算机软件技术基础试题库.docx》由会员分享,可在线阅读,更多相关《计算机软件技术基础试题库.docx(25页珍藏版)》请在冰点文库上搜索。
计算机软件技术基础试题库
一、单项选择题
(1)一个算法应该是()。
A)程序B)问题求解步骤的描述
C)要满足五个基本属性D)A和C
(2)算法指的是()。
A)计算机程序B)解决问题的计算方法
C)排序算法D)解决问题的有限运算序列。
(3)与数据元素本身的形式、内容、相对位置、个数无关的是数据的()。
A)存储结构B)逻辑结构C)算法D)操作
(4)从逻辑上可以把数据结构分为()两大类。
A)动态结构、静态结构B)顺序结构、链式结构
C)线性结构、非线性结构D)初等结构、构造型结构
(5)下列叙述中正确的是()。
A)一个逻辑数据结构只能有一种存储结构
B)数据的逻辑结构属于线性结构,存储结构属于非线性结构
C)一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理的效率
D)一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理的效率
(6)数据的基本单位是( )
A)数据项B)数据类型C)数据元素D)数据变量
(7)下列程序的时间复杂度为( )
i=0;s=0;
while(s {i++;s=s+i;} A)O( )B)O( )C)O(n)D)O(n2) (8)下列程序段的渐进时间复杂度为()。 for(inti=1;i<=n;i++) for(intj=1;j<=m;j++) A[i][j]=i*j; A)O(m2)B)O(n2)C)O(m*n)D)(m+n) (9)程序段如下: sum=0; for(i=1;i<=n;i++) for(j=1;j<=n;j++) sum++; 其中n为正整数,则最后一行的语句频度在最坏情况下是()。 A)O(n)B)O(nlogn)C)O(n3)D)O(n2) (10)在下面的程序段中,对x的赋值语句的频度为()。 for(i=1;i>=n;i++) for(j=1;j>=n;j++) x: =x+1; A)O(2n)B)O(n)C)O(n2)D)O(log2n) (11)程序段for(i: =n-1;i<=1;i--) for(j: =1;j>=i;j++) if(a[j]>a[j+1]) {t=a[j];a[j]=a[j+1];a[j+1]=t;} 其中n为正整数,则最后一行的语句频度在最坏情况下是()。 A)O(n)B)O(nlogn)C)O(n3)D)O(n2) (12)设有一个递归算法如下: intfact(intn) {/*大于等于0*/ if(n<=0)return1; elsereturnn*fact(n-1); } 则计算fact(n)需要调用该函数的次数为()。 A)nB)n+1C)n+2D)n-1 (13)下述程序段中语句①的频度是( )。 s=0; for(i=1;i for(j=0;j<=i;j++) s+=j; A) B) C) D) (14)若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则最节省运算时间的存储方式是( )。 A)单链表B)仅有头指针的单循环链表 C)双链表D)仅有尾指针的单循环链表 (1)求循环链表中当前结点的后继和前驱的时间复杂度分别是( )。 A)O(n)和O (1)B)O (1)和O (1)C)O (1)和O(n)D)O(n)和O(n) (15)求单链表中当前结点的后继和前驱的时间复杂度分别是( )。 A)O(n)和O (1)B)O (1)和O (1) C)O (1)和O(n)D)O(n)和O(n) (16)非空的单循环链表的头指针为head,尾指针为rear,则下列条件成立的是( )。 A)rear->next==headB)rear->next->next==head C)head->next==rearD)head->next->next==rear (17)从一个长度为n的顺序表中删除第i个元素(1≤i≤n)时,需向前移动的元素的个数是( )。 A)n-iB)n-i+1C)n-i-1D)i (18)已知一个有序表为(13,18,24,35,47,50,62,83,90,115,134),当二分检索值为90的元素时,检索成功需比较的次数是( )。 A)1B)2C)3D)4 (19)假设以行优先顺序存储三维数组R[6][9][6],其中元素R[0][0][0]的地址为2100,且每个元素占4个存储单元,则存储地址为2836的元素是( )。 A)R[3][3][3]B)R[3][3][4]C)R[4][3][5]D)R[4][3][4] (20)设有一个10阶的对称矩阵A,采用压缩存储方式以行序为主序存储,a00为第一个元素,其存储地址为0,每个元素占有1个存储地址空间,则a45的地址为( )。 A)13B)35C)17D)36 (21)线性表采用链式存储时,节点的存储的地址()。 A)必须是不连续的B)连续与否均可 C)必须是连续的D)和头节点的存储地址相连续 (22)用链表表示线性表的优点是()。 A)便于随机存取B)花费的存储空间比顺序表少 C)数据元素的物理顺序与逻辑顺序相同D)便于插入与删除 (23)链表不具有的特点是()。 A)插入、删除不需要移动元素B)可随机访问任一元素 C)不必事先估计存储空间D)所需空间与线性长度成正比 (24)在长度为n的顺序表中删除第i个元素(1≤i≤n)时,元素移动的次数为()。 A)n-i+1 B)i C)i+1 D)n-i (25)采用顺序搜索方法查找长度为n的顺序表示,搜索成功的平均搜索长度为()。 A)n B)n/2 C)(n-1)/2 D)(n+1)/2 (26)将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为()。 A)O (1)B)O(n)C)O(m)D)O(m+n) (27)若不带头结点的单链表的头指针为head,则该链表为空的判定条件是()。 A)head==NULL B)head->next==NULLC)head! =NULL D)head->next==head (28)某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用()存储方式最节省运算时间。 A)单链表B)仅有头指针的单循环链表 C)双链表D)仅有尾指针的单循环链表 (29)若允许表达式内多种括号混合嵌套,则为检查表达式中括号是否正确配对的算法,通常选用的辅助结构是( )。 A)栈B)线性表C)队列D)二叉排序树 (30)顺序栈S中top为栈顶指针,指向栈顶元素所在的位置,elem为存放栈的数组,则元素e进栈操作的主要语句为( )。 A)s.elem[top]=e;s.top=s.top+1;B)s.elem[top+1]=e;s.top=s.top+1; C)s.top=s.top+1;s.elem[top+1]=e;D)s.top=s.top+1;s.elem[top]=e; (31)循环队列sq中,用数组elem[0··25]存放数据元素,sq.front指示队头元素的前一个位置,sq.rear指示队尾元素的当前位置,设当前sq.front为20,sq.rear为12,则当前队列中的元素个数为( )。 A)8B)16C)17D)18 (32)链式栈与顺序栈相比,一个比较明显的优点是()。 A)插入操作更加方便B)通常不会出现栈满的情况 C)不会出现栈空的情况D)删除操作更加方便 (33)一个递归的定义可以用递归过程求解,也可以用非递归过程求解,但单从运行时间来看,通常递归过程比非递归过程()。 A)较快B)较慢C)相同D)不定 (34)若已知一个栈的入栈序列是1,2,3,4……n,其输出序列为p1,p2,p3,……pn,若p1==n,则pi为()。 A)iB)n==iC)n-i+1D)不确定 (35)一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是()。 A)edcbaB)decbaC)dceabD)abcde (36)若进栈序列为1,2,3,4,5,6,且进栈和出栈可以穿插进行,则不可能出现的出栈序列是()。 A)2,4,3,1,5,6 B)3,2,4,1,6,5 C)4,3,2,1,5,6 D)2,3,5,1,6,4 (37)对于栈操作数据的原则是()。 A)先进先出B)后进先出C)后进后出D)不分顺序 (38)栈和队列的共同点是()。 A)都是先进先出B)都是先进后出 C)只允许在端点处插入和删除元素D)没有共同点 (39)一个队列的入队序列是1,2,3,4,则队列的输出序列是()。 A)4,3,2,1B)1,2,3,4C)1,4,3,2D)3,2,4,1 (40)设数组data[m]作为循环队列SQ的存储空间,front为队头指针,rear为队尾指针,则执行出对操作后其头指针front值为()。 A)front=front+1B)front=(front+1)%(m-1) C)front=(front-1)%mD)front=(front+1)%m (41)引起循环队列队头位置发生变化的操作是()。 A)出队B)入队 C)取队头元素D)取队尾元素 (2)设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear,则当前队列中的元素个数为()。 A)(rear-front+m)%mB)rear-front+1C)(front-rear+m)%mD)(rear-front)%m (42)二维数组A[12][18]采用列优先的存储方法,若每个元素各占3个存储单元,且A[0][0]地址为150,则元素A[9][7]的地址为()。 A)429 B)432 C)435 D)438 (43)设有一个10阶的对称矩阵A[10][10],采用压缩方式按行将矩阵中下三角部分的元素存入一维数组B[]中,A[0][0]存入B[0]中,则A[8][5]在B[]中()位置。 A)32B)33 C)41D)65 (44)若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1..(n(n+1))/2]中,则在B中确定aij(i A)i*(i-1)/2+jB)j*(j-1)/2+iC)i*(i+1)/2+jD)j*(j+1)/2+i (45)对稀疏矩阵进行压缩存储目的是()。 A)便于进行矩阵运算B)便于输入和输出 C)节省存储空间D)降低运算的时间复杂度 (46)对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是()。 A)(e,f) B)((e,f)) C)(f) D)() (47)设广义表L=((a,b,c)),则L的长度和深度分别为()。 A)1和1B)1和3C)1和2D)2和3 (48)树中所有结点的度之和等于所有结点数加()。 A)0B)1C)-1D)2 (49)在一棵具有n个结点的二叉链表中,所有结点的空域个数等于()。 A)nB)n-1C)n+1D)2*n (50)某二叉树的先序序列和后序序列正好相反,则该二叉树一定是()的二叉树。 A)空或只有一个结点B)高度等于其节点数 C)任一结点无左孩子D)任一结点无右孩子 (51)含有10个结点的二叉树中,度为0的结点数为4,则度为2的结点数为( ) A)3B)4C)5D)6 (52)除第一层外,满二叉树中每一层结点个数是上一层结点个数的( ) A)1/2倍B)1倍C)2倍D)3倍 (53)对一棵有100个结点的完全二叉树按层编号,则编号为49的结点,它的父结点的编号为( ) A)24B)25C)98D)99 (54)可以惟一地转化成一棵一般树的二叉树的特点是( ) A)根结点无左孩子B)根结点无右孩子C)根结点有两个孩子D)根结点没有孩子 (55)设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少为()。 A)2hB)2h-1C)2h+1D)h+1 (56)在一棵度为3的树中,度为3的节点个数为2,度为2的节点个数为1,则度为0的节点个数为()。 A)4B)5C)6D)7 (57)设森林F对应的二叉树为B,它有m个结点,B的根为p,p的右子树结点个数为n,森林F中第一棵子树的结点个数是()。 A)m-nB)m-n-1C)n+1D)条件不足,无法确定 (58)将一株有100个节点的完全二叉树从上到下,从左到右依次进行编号,根节点的编号为1,则编号为49的节点的左孩子编号为()。 A)98B)89C)50D)没有孩子 (59)下列图示的顺序存储结构表示的二叉树是(A) (60)树最适合用来表示()。 A)有序数据元素B)无序数据元素 C)元素之间具有分支层次关系的数据D)元素之间无联系的数据 (61)在一个非空二叉树的中序遍历序列中,根结点的右边()。 A)只有右子树上的所有结点B)只有右子树上的部分结点 C)只有左子树的上的部分结点D)只有左子树上的所有结点 (62)任何一棵二叉树的叶结点在先序、中序和后序遍历序列中相对次序()。 A)不发生改变B)发生改变C)不能确定D)以上都不对 (63)深度优先遍历类似于二叉树的()。 A)先序遍历B)中序遍历C)后序遍历D)层次遍历 (64)广度优先遍历类似于二叉树的()。 A)先序遍历B)中序遍历C)后序遍历D)层次遍历 (65)任何一个无向连通图的最小生成树()。 A)只有一棵B)一棵或多棵C)一定有多棵D)可能不存在 (注,生成树不唯一,但最小生成树唯一,即边权之和或树权最小的情况唯一) (66)在分析折半查找的性能时常常加入失败节点,即外节点,从而形成扩充的二叉树。 若设失败节点i所在层次为Li,那么查找失败到达失败点时所做的数据比较次数是()。 A)Li+1B)Li+2C)Li-1D)Li (67)向一个有127个元素原顺序表中插入一个新元素并保存原来顺序不变,平均要移动()个元素。 A)8B)63.5C)63D)7 (68)由同一组关键字集合构造的各棵二叉排序树()。 A)其形态不一定相同,但平均查找长度相同 B)其形态不一定相同,平均查找长度也不一定相同 C)其形态均相同,但平均查找长度不一定相同 D)其形态均相同,平均查找长度也都相同 (69)衡量查找算法效率的主要标准是()。 A)元素的个数B)所需的存储量C)平均查找长度D)算法难易程度 (70)适合对动态查找表进行高效率查找的组织结构是()。 A)有序表B)分块有序表C)二叉排序树D)快速排序 (3)能进行二分查找的线性表,必须以( )。 A)顺序方式存储,且元素按关键字有序 B)链式方式存储,且元素按关键字有序 C)顺序方式存储,且元素按关键字分块有序 D)链式方式存储,且元素按关键字分块有序 (71)为使平均查找长度达到最小,当由关键字集合{05,11,21,25,37,40,41,62,84}构建二叉排序树时,第一个插入的关键字应为( ) A)5B)37C)41D)62 (72)对关键字序列(56,23,78,92,88,67,19,34)进行增量为3的一趟希尔排序的结果为 ( )。 A)(19,23,56,34,78,67,88,92) B)23,56,78,66,88,92,19,34) C)(19,23,34,56,67,78,88,92) D)(19,23,67,56,34,78,92,88) (73)用某种排序方法对关键字序列{35,84,21,47,15,27,68,25,20}进行排序时,序列的变化情况如下: 20,15,21,25,47,27,68,35,84 15,20,21,25,35,27,47,68,84 15,20,21,25,27,35,47,68,84 则采用的方法是()。 A)直接选择排序B)希尔排序C)堆排序D)快速排序 (74)一组记录的排序码为(46,79,56,38,40,84),则利用快速排序的方法,以第一个记录为基准得到的第一次划分结果为()。 A)38,40,46,56,79,84B)40,38,46,79,56,84C)40,38,46,56,79,84D)40,38,46,84,56,79 (75)快速排序在最坏情况下的时间复杂度是( ) A)O(n2log2n)B)O(n2)C)O(nlog2n)D)O(log2n) (76)下列排序算法中不稳定的是()。 A)直接选择排序B)折半插入排序C)冒泡排序D)快速排序 (77)对待排序的元素序列进行划分,将其分为左、右两个子序列,再对两个子序列进行同样的排序操作,直到子序列为空或只剩下一个元素为止。 这样的排序方法是()。 A)直接选择排序B)直接插入排序C)快速排序D)冒泡排序 (78)将5个不同的数据进行排序,至多需要比较()次。 A)8B)9C)10D)25 (79)排序算法中,第一趟排序后,任一元素都不能确定其最终位置的算法是( )。 A)选择排序B)快速排序C)冒泡排序D)插入排序 (80)排序算法中,不稳定的排序是( )。 A)直接插入排序B)冒泡排序C)堆排序D)选择排序 (81)排序方法中,从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较,将其放入已排序序列的正确位置上的方法,称为(). A)希尔排序B)冒泡排序C)插入排序D)选择排序 (82)从未排序序列中挑选元素,并将其依次插入已排序序列(初始时为空)的一端的方法,称为()。 A)希尔排序B)归并排序C)插入排序D)选择排序 (83)对n个不同的排序码进行冒泡排序,在下列哪种情况下比较的次数最多。 () A)从小到大排列好的B)从大到小排列好的 C)元素无序D)元素基本有序 (84)对n个不同的排序码进行冒泡排序,在元素无序的情况下比较的次数为()。 A)n+1B)nC)n-1D)n(n-1)/2 (85)快速排序在下列哪种情况下最易发挥其长处。 () A)被排序的数据中含有多个相同排序码 B)被排序的数据已基本有序 C)被排序的数据完全无序 D)被排序的数据中的最大值和最小值相差悬殊 (86)对有n个记录的表作快速排序,在最坏情况下,算法的时间复杂度是()。 A)O(n)B)O(n2)C)O(nlog2n)D)O(n3) (87)若一组记录的排序码为(46,79,56,38,40,84),则利用快速排序的方法,以第一个记录为基准得到的一次划分结果为()。 A)38,40,46,56,79,84B)40,38,46,79,56,84 C)40,38,46,56,79,84D)40,38,46,84,56,79 (88)下列关键字序列中,()是堆。 A)16,72,31,23,94,53B)94,23,31,72,16,53 C)16,53,23,94,31,72D)16,23,53,31,94,72 (89)堆是一种()排序。 A)插入B)选择C)交换D)归并 (90)堆的形状是一棵()。 A)二叉排序树B)满二叉树C)完全二叉树D)平衡二叉树 (91)若一组记录的排序码为(46,79,56,38,40,84),则利用堆排序的方法建立的初始堆为()。 A)79,46,56,38,40,84B)84,79,56,38,40,46 C)84,79,56,46,40,38D)84,56,79,40,46,38 (92)下述几种排序方法中,要求内存最大的是()。 A)插入排序B)快速排序C)归并排序D)选择排序 (93)有一组数据(15,9,7,8,20,-1,7,4),用堆排序的筛选方法建立的初始堆为()。 A)-1,4,8,9,20,7,15,7B)-1,7,15,7,4,8,20,9 C)-1,4,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机软件 技术 基础 试题库