公共基础复习题Word文档格式.docx
- 文档编号:5143939
- 上传时间:2023-05-04
- 格式:DOCX
- 页数:17
- 大小:29.96KB
公共基础复习题Word文档格式.docx
《公共基础复习题Word文档格式.docx》由会员分享,可在线阅读,更多相关《公共基础复习题Word文档格式.docx(17页珍藏版)》请在冰点文库上搜索。
可行性、确定性、有穷性和拥有足够的情报。
3.算法一般都可以用哪几种控制结构组合而成(顺序、选择、循环)
4.算法的时间复杂度是指(算法执行过程中所需要的基本运算次数)
5.算法的空间复杂度是指(执行过程中所需要的存储空间)
6.算法分析的目的是(分析算法的效率以求改进)
7.下列叙述正确的是(C)
A.算法的执行效率与数据的存储结构无关
B.算法的空间复杂度是指算法程序中指令(或语句)的条数
C.算法的有穷性是指算法必须能在执行有限个步骤之后终止
D.算法的时间复杂度是指执行算法程序所需要的时间
8.数据结构作为计算机的一门学科,主要研究数据的逻辑结构、对各种数据结构进行的运算,以及(数据的存储结构)
9.数据结构中,与所使用的计算机无关的是数据的(C)
A.存储结构
B.物理结构
C.逻辑结构
D.物理和存储结构
10.下列叙述中,错误的是(B)
A.数据的存储结构与数据处理的效率密切相关
B.数据的存储结构与数据处理的效率无关
C.数据的存储结构在计算机中所占的空间不一定是连续的
D.一种数据的逻辑结构可以有多种存储结构
11.数据的存储结构是指(数据的逻辑结构在计算机中的表示)
12.数据的逻辑结构是指(反映数据元素之间逻辑关系的数据结构)
13.根据数据结构中各数据元素之间前后件关系的复杂程度,一般将数据结构分为(线性结构和非线性结构)
14.下列数据结构具有记忆功能的是(C)A.队列B.循环队列C.栈D.顺序表
15.下列数据结构中,按先进后出原则组织数据的是(B)
A.线性链表
B.栈
C.循环链表
D.顺序表
16.递归算法一般需要利用(队列)实现。
17.下列关于栈的叙述中正确的是(D)A.在栈中只能插入数据B.在栈中只能删除数据
C.栈是先进先出的线性表
D.栈是先进后出的线性表
18.栈底至栈顶依次存放元素A、B、C、D,在第五个元素E入栈前,栈中元素可以出栈,则出栈序列可能是(DCBEA)
19.如果进栈序列为e1,e2,e3,e4,则可能的出栈序列是(e2,e4,e3,e1)
20.
由两个栈共享一个存储空间的好处是(节省存储空间,降低上溢发生的机率)
21.
应用程序在执行过程中,需要通过打印机输出数据时,一般先形成一个打印作业,将其存放在硬盘中的一个指定(队列)中,当打印机空闲时,就会按先来先服务的方式从中取出待打印的作业进行打印。
22.下列关于队列的叙述中正确的是(C)A.在队列中只能插入数据B.在队列中只能删除数据
C.队列是先进先出的线性表
D.队列是先进后出的线性表
23.下列叙述中,正确的是(D)A.线性链表中的各元素在存储空间中的位置必须是连续的
B.线性链表中的表头元素一定存储在其他元素的前面C.线性链表中的各元素在存储空间中的位置不一定是连续的,但表头元素一定存储在其他元素的前面D.线性链表中的各元素在存储空间中的位置不一定是连续的,且各元素的存储顺序也是任意的
24.下列叙述中正确的是(A)A.线性表是线性结构
B.栈与队列是非线性结构
C.线性链表是非线性结构
D.二叉树是线性结构
25.线性表L=(a1,a2,a3,……ai,……an),下列说法正确的是(D)
A.每个元素都有一个直接前件和直接后件
B.线性表中至少要有一个元素
C.表中诸元素的排列顺序必须是由小到大或由大到小D.除第一个元素和最后一个元素外,其余每个元素都有一个且只有一个直接前件和直接后件
26.线性表若采用链式存储结构时,要求内存中可用存储单元的地址(连续不连续都可以)
27.链表不具有的特点是(B)A.不必事先估计存储空间
B.可随机访问任一元素
C.插入删除不需要移动元素
D.所需空间与线性表长度成正比
28.非空的循环单链表head的尾结点(由p所指向),满足(p->
next=head)
29.与单向链表相比,双向链表的优点之一是(更容易访问相邻结点)
30.在(D)中,只要指出表中任何一个结点的位置,就可以从它出发依次访问到表中其他所有结点。
A.线性单链表
B.双向链表
C.线性链表
D.循环链表
31.以下数据结构属于非线性数据结构的是(C)A.队列
B.线性表C.二叉树
D.栈
32.树是结点的集合,它的根结点数目是(有且只有1)
33.具有3个结点的二叉树有(5种形态)
34.在一棵二叉树上第8层的结点数最多是(128)注:
2K-1
35.在深度为5的满二叉树中,叶子结点的个数为(16)注:
2n-1
36.在深度为5的满二叉树中,共有(31)个结点。
注:
2n-1
37.设一棵完全二叉树共有699个结点,则在该二叉树中的叶子结点数为(350)
完全二叉树总结点数为N,若N为奇数,则叶子结点数为(N+1)/2;
若N为偶数,则叶子结点数为N/2。
38.设有下列二叉树,对此二叉树中序遍历的结果是(B)
A.ABCDEF
B.DBEAFCC.ABDECF
D.DEBFCA
39.已知二叉树后序遍历序列是dabec,中序遍历序列debac,它的前序遍历序列是(cedba)
40.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历为(DGEBHFCA)
41.若某二叉树的前序遍历访问顺序是abdgcefh,中序遍历访问顺序是dgbaechf,则其后序遍历的结点访问顺序是(gdbehfca)
42.对长度为n的线性表进行顺序查找,在最坏情况下所需要的比较次数为(N)
43.最简单的交换排序方法是(冒泡排序)
44.假设线性表的长度为n,则在最坏情况下,冒泡排序需要的比较次数为(n(n-1)/2)
45.在待排序的元素序列基本有序的前提下,效率最高的排序方法是(冒泡排序)
46.在最坏情况下,下列顺序方法中时间复杂度最小的是(堆排序)
47.希尔排序法属于(插入类排序)
48.堆排序法属于(选择类排序)
49.在下列几种排序方法中,要求内存量最大的是(归并排序)
50.
已知数据表A中每个元素距其最终位置不远,为节省时间,应采用(直接插入排序)
51.算法的基本特征是可行性、确定性、有穷性
和拥有足够的情报。
1.算法的复杂度主要包括时间复杂度和空间复杂度。
2.
实现算法所需的存储单元多少和算法的工作量大小分别称为算法的空间复杂度和时间复杂度。
3.所谓数据处理是指对数据集合中的各元素以各种方式进行运算,包括插入、删除、查找、更改等运算,也包括对数据元素进行分析。
4.数据结构是指相互有关联的数据元素的集合。
5.数据结构分为逻辑结构与存储结构,线性链表属于存储结构。
6.数据结构包括数据的逻辑结构和数据的存储结构。
7.数据结构包括数据的逻辑结构、数据的存储结构以及对数据的操作运算。
8.数据元素之间的任何关系都可以用前趋和后继关系来描述。
9.数据的逻辑结构有线性结构和非线性结构两大类。
10.常用的存储结构有顺序、链接、索引等存储结构。
11.顺序存储方法是把逻辑上相邻的结点存储在物理位置
相邻的存储单元中。
12.栈的基本运算有三种:
入栈、退栈与读栈顶元素。
13.队列主要有两种基本运算:
入队运算与退队运算。
14.在实际应用中,带链的栈可以用来收集计算机存储空间中所有空闲的存储结点,这种带链的栈称为可利用栈。
15.栈和队列通常采用的存储结构是链式存储和顺序存储
。
16.当线性表采用顺序存储结构实现存储时,其主要特点是逻辑结构中相邻的结点在存储结构中仍相邻。
17.循环队列主要有两种基本运算:
入队运算与退队运算。
每进行一次入队运算,队尾指针就进1。
18.当循环队列非空且队尾指针等于对头指针时,说明循环队列已满,不能进行入队运算。
这种情况称为上溢
19.当循环队列为空时,不能进行退队运算,这种情况称为下溢。
20.在一个容量为25的循环队列中,若头指针front=16,尾指针rear=9,则该循环队列中共有18个元素。
注:
当rear<
front时,元素个数=总容量-(front-rear);
当rear>
front时,元素个数=rear-front。
21.在一个容量为15的循环队列中,若头指针front=6,尾指针rear=9,则该循环队列中共有3个元素。
22.顺序查找一般是指在线性表中查找指定的元素。
23.在计算机中存放线性表,一种最简单的方法是顺序存储。
24.在程序设计语言中,通常定义一个一维数组来表示线性表的顺序存储空间。
25.在链式存储方式中,要求每个结点由两部分组成:
一部分用于存放数据元素值,称为数据域,另一部分用于存放指针,称为指针域。
其中指针用于指向该结点的前一个或后一个结点(即前件或后件)。
26.在线性单链表中,每一个结点只有一个指针域,由这个指针只能找到后继结点,但不能找到前驱结点。
27.为了要在线性链表中插入一个新元素,首先要给该元素分配一个新结点,以便用于存储该元素的值。
28.在线性链表中删除一个元素后,只需要改变被删除元素所在结点的前一个结点的指针域即可。
29.用链表表示线性表的突出优点是便于插入和删除操作。
30.在树形结构中,树根结点没有
前件。
31.在树结构中,一个结点所拥有的后件个数称为该结点的度。
叶子结点的度为0。
32.设一棵二叉树中有3个叶子结点,8个度为1的结点,则该二叉树中总的结点数为13。
33.设一棵完全二叉树共有739个结点,则在该二叉树中有370个叶子结点。
34.设一棵完全二叉树共有700个结点,则在该二叉树中有350个叶子结点。
35.在先左后右的原则下,根据访问根结点的次序,二叉树的遍历可以分为三种:
前序遍历、中序遍历和后序遍历。
38.对长度为n的线性表进行插入一个新元素或删除一个元素时,在最坏情况下所需要的比较次数为n。
39.
在长度为n的有序线性表中进行顺序查找。
最坏的情况下,需要的比较次数为
n
40.
在长度为n的有序线性表中进行二分查找。
最坏的情况下,需要的比较次数为log2n。
41.长度为n的顺序存储线性表中,当在任何位置上插入一个元素概率都相等时,插入一个元素所需移动元素的平均个数为n/2。
42.
排序是计算机程序设计中的一种重要操作,常见的排序方法有插入排序、交换排序和选择排序等。
43.快速排序法可以实现通过一次交换而消除多个逆序。
44.快速排序法的关键是对线性表进行分割。
45.冒泡排序算法在最好的情况下的元素交换次数为0。
46.在最坏情况下,冒泡排序的时间复杂度为n(n-1)/2。
47.
对于长度为n的线性表,在最坏情况下,快速排序所需要的比较次数为n(n-1)/2。
48.在最坏情况下,简单插入排序需要比较的次数为n(n-1)/2。
49.在最坏情况下,希尔排序需要比较的次数为O(n1.5)。
括号里是n的1.5次方。
50.在最坏情况下,简单选择排序需要比较的次数为n(n-1)/2。
51.在最坏情况下,堆排序需要比较的次数为o(nlog2n)。
52.对于输入为N个数进行快速排序算法的平均时间复杂度是O(Nlog2N)。
第二章程序设计基础
1.在结构化程序设计思想提出之前,在程序设计中曾强调程序的效率。
与程序的效率相比,人们更重视程序的(C)。
A.安全性
B.一致性C.可理解性D.合理性
2.对建立良好的程序设计风格,下面的描述正确的是(A)
A.程序应简单、清晰、可读性好B.符号名的命名只要符合语法
C.充分考虑程序的执行效率
D.程序的注释可有可无
3.在设计程序时.应采纳的原则之一是(D)。
A.不限制GOTO语句的使用
B.减少或取消注解行
C.程序越短越好
D.程序结构应有助于读者理解
4.程序应该简单易懂,语句构造应该简单直接,不应该为提高效率而把语句复杂化。
5.源程序文档化要求程序应加注释,注释一般分为序言性注释和功能性注释。
6.在编写程序时,需要注意数据说明的风格,以便使程序中的数据说明更易理解和维护。
7.当程序设计语言对输入格式有严格要求时,应保持输入格式与输入语句的一致性
程序设计语言的基本成分是数据成分、运算成分、控制成分和(传输成分)。
8.结构化程序设计方法的主要原则是:
自顶向下、逐步求精、模块化、限制使用goto语句
9.结构化程序设计主要强调的是(B)
A.程序的规模
B.程序的易读性
C.程序的执行效率D.程序的可移植性
10.结构化程序设计的3种结构是(顺序结构、选择结构、循环结构)。
结构化程序设计方法是程序设计的先进方法和工具。
下面为三种基本的控制结构:
顺序结构:
是一种简单的程序设计,它是最基本,最常用的结构
选择结构:
又称为分支结构,包括简单选择和多分支选择结构
重复结构:
又称循环结构,有两类循环语句:
当型循环结构(先判断后执行循环体)和直到型循环结构(先执行循环体后判断)
按结构化程序设计方法设计出的程序具有两大明显的优点:
1、程序易于理解、使用和维护。
2、提高了编程工作效率,降低了软件开发成本。
C.结构化程序设计原则和方法的应用
11.结构化程序设计的主要特点是(每个控制结构只有一个入口和一个出口)
12.下列叙述中,不属于结构化程序设计方法的主要原则的是(B)。
A.自顶向下
B.由底向上
C.模块化
D.限制使用GOTO语句
13.面向对象的模型中,最基本的概念是对象和类
14.类是一个支持集成的抽象数据类型,而对象是类的实例
15.对象实现了数据和操作的结合,是指对数据和数据的操作进行(封装)。
16.封装是一种(信息屏蔽)技术,封装的目的是使对象的定义和实现分离。
17.以下不属于对象的基本特点的是(C)。
A.分类性
B.多态性
C.继承性
D.封装性
对象有如下一些基本特点.即标识惟一性、分类性、多态性、封装性和模块独立性。
18.下面关于对象的描述错误的是(A)A.任何对象都必须有继承性B.对象是属性和方法的封装体
C.对象间的通迅靠消息传递
D.操作是对象的动态属性
19.信息隐蔽的概念与下述哪能一种概念直接相关(模块独立性)
20.可以把具有相同属性的一些不同对象归类,称为
对象类
21.在面向对象方法中,一个对象请求另一对象为其服务的方式是通过发送(消息)
消息:
面向对象的世界是通过对象与对象间彼此的相合合作来推动的,对象间这种合作需要一个机制协助进行,这样的机制称为“消息”。
消息就是一个实例与另一个实例之间传递的信息,它统一了数据流和控制流。
一个消息由下述三部分组成:
1、接收消息的对象的名称。
2、消息标识符(即消息名)3、零个或多个参数。
22.在面向对象方法中,类之间共享属性和操作的机制称为
继承
23.一个类可以从直接或间接的祖先中继承所有属性和方法。
采用此方法提高了软件的可重用性
24.子程序通常分为两类:
过程
和函数,前者是命令的抽象,后者是为了求值。
第三章软件工程
考点一、软件工程基本概念
1.软件是计算机系统中与硬件相互依存的重要部分,包括程序、数据及相关的文档。
其中,程序是软件开发人员根据用户需求开发的、用程序设计语言描述的、适合计算机执行的指令(语句)序列。
2.下列叙述中,正确的是(D)。
A.软件就是程序清单
B.软件就是存放在计算机中的文件C.软件应包括程序清单及运行结果
D.软件包括程序和文档
3.软件按功能可以分为:
应用软件、系统软件、支撑软件(或工具软件)
4.软件工程的出现是由于(软件危机的出现)
5.开发软件所需高成本和产品的低质量之间有着尖锐的矛盾,这种现象称做(软件危机)
6.开发大型软件时,产生困难的根本原因是(大型系统的复杂性)。
7.软件危机出现于20世纪60年代末,为了解决软件危机,人们提出了软件工程学的原理来设计软件这就是软件工程诞生的基础。
8.下列不属于软件工程的3个要素的是(D)
A.工具
B.过程
C.方法
D.环境
9.软件工程过程是把输入转化为输出的一组彼此相关的资源和活动。
通常,将软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期
10.软件生命周期中所花费用最多的阶段是(软件维护)
11.软件开发的结构化生命周期方法将软件生命周期划分成(定义、开发、运行维护)。
12.软件生命周期一般包括可行性研究与需求分析、设计、实现、测试、交付使用以及维护等活动。
软件工程的目标与原则
13.软件工程的理论和技术性研究的内容主要包括:
软件开发技术和软件工程管理。
软件开发技术包括:
软件开发方法学、开发过程、开发工具和软件工程环境,主体内容是软件开发方法学。
软件工程管理包括:
软件管理学、软件工程经济学、软件心理学等内容。
14.软件工程的理论和技术性研究的内容主要包括软件开发技术和(软件工程管理)
15.软件工程的原则包括抽象、信息隐藏、模块化、局部化、确定性、一致性、完备性和可验证性。
软件开发工具与软件开发环境
16.开发软件时对提高开发人员工作效率至关重要的是(先进的软件开发工具和环境)
17.软件开发环境是全面支持软件开发全过程的软件工具集合。
18.在软件生产过程中,需求信息的给出是(软件用户)。
19.需求分析中,开发人员要从用户那里了解(软件做什么)。
20.需求分析阶段的任务是确定(软件系统功能)
21.需求分析的任务是发现需求、求精、建模和定义需求的过程。
需求分析将创建所需的数据模型、功能模型和控制模型
22.需求分析阶段的工作:
需求获取、需求分析、编写需求规格说明书、需求评审
下列工具中属于需求分析常用工具的是(D)。
A)PAD
B)PFD
C)N—S
D)DFD
23.结构化方法的核心和基础是结构化程序设计理论
24.下列不属于结构化分析的常用工具的是(D)。
A)数据流图
B)数据字典
C)判定树
D)PAD图
25.在结构化方法中,用数据流程图(DFD)作为描述工具的软件开发阶段是(B)
A)可行性分析B)需求分析
C)详细设计
D)程序编码
26.数据流图用于抽象描述一个软件的逻辑模型.数据流图由一些特定的图符构成。
下列图符名标识的图符不属于数据流图合法图符的是(A)。
A)控制流
B)加工
C)数据存储
D)源和潭
数据流图中的主要图形元素与说明:
27.在数据流图(DFD)中的箭头代表的是(数据流)
28.在数据流图(DFD)中,带有名字的箭头表示(数据的流向)。
29.在结构化分析方法中,用于描述系统中所用到的全部数据和文件的文档称为数据字典
软件需求规格说明书
30.软件需求规格说明书是需求分析阶段的最后结果
31.下列叙述中,不属于软件需求规格说明书的作用的是(D)
A.便于用户、开发人员进行理解和交流
B.反映出用户问题的结构,可以作为软件开发工作的基础和依据
C.作为确认测试和验收的依据
D.便于开发人员进行需求分析
32.(数据描述)是对软件系统所必须解决的问题做出的详细说明
33.在软件开发中,下面任务不属于设计阶段的是(D)
A)数据结构设计B)给出系统模块结构C)定义模块算法D)定义需求并建立系统模型
34.软件设计包括软件的结构、数据、接口和过程设计,其中软件的过程设计是指(系统结构部件转换成软件的过程描述)。
35.下面不属于软件设计原则的是(C)A.抽象B.模块化
C.自底向上
D.信息隐藏
36.耦合和内聚是评价模块独立性的两个主要标准,其中
内聚反映了模块内各成分之间的联系,耦合反映了模块间互相连接的紧密程度。
37.内聚性是信息隐蔽和局部化概念的自然扩展,一个模块的内聚性越强,则该模块的模块独立性越强。
一个模块与其它模块的耦合
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 公共 基础 复习题