计算机二级vf公共基础知识.doc

第一章数据结构与算法

1、问题处理方案的正确而完整的描述称为
答案：算法
2、算法的四个特征：
答案:确定性、可行性、有穷性、拥有足够的情报
3、算法的复杂度主要包括：时间复杂度和复杂度。
答案：空间
4、算法的时间复杂度是
答案：指执行算法所需要的计算工作量
算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数。
5、算法的空间复杂度是指
空间复杂度用来描述执行算法所需要的内存空间
6、一个算法通常由两种基本要素组成：一是对数据对象的运算和操作，二是算法的
答案：控制结构
7、在同一个问题规模下，如果算法执行所需的基本运算此时取决于某一特定输入时，可以用平均性态和两种方法来分析算法的工作量。
答案：最坏情况复杂性
8、算法设计基本方法主要有：、归纳法、递推、递归和减半递推技术。
答案：列举法
9、数据的存储结构是指
答案：数据的逻辑结构在计算机存储空间的存放形式
10、所谓，是指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算、也包括对数据元素进行分析。
答案：数据处理
11、数据结构是指相互有关联的的集合。
答案：数据元素
12、数据元素之间的任何关系都可以用关系来描述。
答案：前驱和后继
13、常用的存储结构有顺序、链接、等存储结构。
答案：索引
14、一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理效率。
15、数据结构分逻辑结构和存储结构，循环队列属于结构。
答案：存储
16、在数据结构中，没有前驱的结点称为。
答案：根节点
17、在数据结构中，结点及结点间的相互关系是数据的逻辑结构，数据结构按逻辑关系的不同，通常可分为两类。
答案：线性结构和非线性结构
18、在稍微复杂的线性表中，一个数据元素可以由若干个数据项组成，在这种情况下，常把数据元素称为（记录）。
19、在计算机中存放线性表，一种最简单的方法是
答案：顺序存储
20.、在程序设计语言中，通常定义一个来表示线性表的顺序存储空间。
答案：一维数组
21.、栈是一种特殊的线性表，插入和删除操作只能在线性表的一端进行，不需要改变栈底指针。栈是先进后出的线性表，由此可以看出，栈具有记忆功能。栈还可以用链式存储。
22、下列关于栈的描述中错误的是（）
A栈是先进后出的线性表
B栈只能顺序存储
C栈具有记忆作用
D对栈的插入和删除操作中，不需要改变栈底指针
答案：B
23.、下列关于栈的描述正确的是（）
A在栈中只能插入元素不能删除元素
B在栈中只能删除元素不能插入元素
C栈是特殊的线性表，只能在一端插入或删除元素
D栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素
答案：C
24、栈的基本运算有三种：入栈、退栈与
答案:读栈顶元素
25、下列关于队列的叙述中正确的是（）
A在队列中只能插入数据
B在队列中只能删除数据
C队列是先进先出的线性表
D队列是先进后出的线性表
答案：C
26、循环队列主要有两种基本运算：入队运算与退队运算。每进行一次入队运算，队尾指针就
答案：进一
27、应用程序在执行过程中，需要通过打印机输出数据时，一般先形成一个打印作业，将其存放在硬盘中的一个指定
中。当打印机空闲时，就会按先来先服务的方式从中取出待打印的作业进行打印。
答案：队列
28、递归算法一般需要利用实现。
答案：栈
29、对长度为n的线性表进行插入一个新元素或删除一个元素时，在最坏情况下所需要的比较次数为
答案：n
30、下列对于线性链表的描述中正确的是（）
A存储空间不一定是连续，且各元素的存储顺序是任意的
B存储空间不一定是连续，且前件元素一定存储在后件元素的前面
C存储空间必须连续，且各前件元素一定存储在后件元素的前面
D存储空间必须连续，且各元素的存储顺序是任意的
答案：A
分析：线性链表属于链式存储结构，在链式存储结构中，存储空间可以不连续，各元素的存储顺序是任意的，元素之间的逻辑关系是由指针域来决定的。
31、在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为；另一部分用于存放指针，称为
答案：数据域指针域
32、在中，每一个结点只有一个指针域，由这个指针只能找到后继结点，但不能找到前驱结点。
33、与单向链表相比，双向链表的优点之一是（）
A更节省存储空间B便于进行随机访问
C更容易访问相邻结点D可以节省头指针和尾指针
34、在实际应用中，带链的栈可以用来收集计算机存储空间中所有空闲的存储结点，这种带链的栈称为
答案：可利用栈
35、为了要在线性链表中插入一个新元素，首先要给该元素分配一个，以便用于存储该元素的值。
答案：新结点
36、在线性链表中删除一个元素后，只需改变被删除元素所在结点的前一个结点的即可。
答案：指针域
37、在中，只要指出表中任何一个结