下载文档原格式
数据结构习题答案 2 第一节概论 2 第二节线性表 5 第三节栈和队列16 第五节树19 第七节查找25 第八节排序29 操作系统练习题参考答案32数据结构习题答案第一节概论一、选择题1．要求同一逻辑结构的所有数据元素具有相同的特性，这意味着( )。
A．数据元素具有同一的特点~B．不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等2．数据结构是一门研究非数值计算的程序设计问题中计算机的( (1) )以及它们之间的( (2) )和运算的学科。
(1) ~A．操作对象 B．计算方法 C．逻辑存储 D．数据映像(2) A．结构~B．关系 C．运算 D．算法3．数据结构被形式地定义为(D，R)，其中D是( (1) )的有限集合，R是D上( (2) )的有限集合。
(1) A．算法~B．数据元素 C．数据操作 D．逻辑结构(2)A．操作 B．映像 C．存储~D．关系4．在数据结构中，从逻辑上可以把数据结构分为( )。
A．动态结构和静态结构 B．紧凑结构和非紧凑结构~C．线性结构和非线性结构 D．内部结构和外部结构5．线性表的顺序存储结构是一种( )的存储结构。
~A．随机存取 B．顺序存取 C．索引存取 D．Hash存取6．算法分析的目的是( )。
A．找出数据结构的合理性 B．研究算法中的输入和输出的关系~C．分析算法的效率以求改进D．分析算法的易懂性和文档性7．计算机算法指的是( (1) )，它必须具备输入、输出和( (2) )等五个特征。
(1) A．计算方法 B．排序方法~C．解决某一问题的有限运算序列 D．调度方法(2) A．可行性、可移植性和可扩充性~B．可行性、确定性和有穷性 C．确定性，有穷性和稳定性 D．易读性、稳定性和安全性8．线性表若采用链表存储结构，要求内存中可用存储单元的地址( )。
A．必须是连续的 B．部分必须是连续的 C．一定是不连续的~D．连续不连续都可以9．在以下的叙述中，正确的是( )。
计算机软件技术基础所有题目答案自学精编W O R D版IBM system office room 【A0816H-A0912AAAHH-GX8Q8-GNTHHJ8】数据结构习题答案2第一节概论2第二节线性表5第三节栈和队列16第五节树19第七节查找25第八节排序29操作系统练习题参考答案32数据结构习题答案第一节概论一、选择题1．要求同一逻辑结构的所有数据元素具有相同的特性，这意味着( )。
A．数据元素具有同一的特点~B．不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等2．数据结构是一门研究非数值计算的程序设计问题中计算机的( (1) )以及它们之间的( (2) )和运算的学科。
(1) ~A．操作对象 B．计算方法 C．逻辑存储 D．数据映像(2) A．结构~B．关系 C．运算 D．算法3．数据结构被形式地定义为(D，R)，其中D是( (1) )的有限集合，R是D上( (2) )的有限集合。
(1) A．算法~B．数据元素 C．数据操作 D．逻辑结构(2)A．操作 B．映像 C．存储~D．关系4．在数据结构中，从逻辑上可以把数据结构分为( )。
A．动态结构和静态结构 B．紧凑结构和非紧凑结构~C．线性结构和非线性结构 D．内部结构和外部结构5．线性表的顺序存储结构是一种( )的存储结构。
~A．随机存取 B．顺序存取 C．索引存取 D．Hash存取6．算法分析的目的是( )。
A．找出数据结构的合理性 B．研究算法中的输入和输出的关系~C．分析算法的效率以求改进D．分析算法的易懂性和文档性7．计算机算法指的是( (1) )，它必须具备输入、输出和( (2) )等五个特征。
(1) A．计算方法 B．排序方法~C．解决某一问题的有限运算序列 D．调度方法(2) A．可行性、可移植性和可扩充性~B．可行性、确定性和有穷性 C．确定性，有穷性和稳定性 D．易读性、稳定性和安全性8．线性表若采用链表存储结构，要求内存中可用存储单元的地址( )。
第1章数据结构一、选择题1.算法指的是（D）。
A计算机程序B解决问题的计算方法C排序方法D解决问题的有限运算序列2.在数据的树形结构中，数据元素之间为（C ）的关系。
A 0:0B 1:1C 1:nD m:n3.数据的存储结构包括顺序、链接、散列和（A）4种基本类型。
A索引B数组C集合D向量4.一个数组元素a[i]与（B）的表示等价。
A &a+iB *(a+i)C *a+iD a+i7.下面程序的时间复杂性的量级为（C）。
int i=0，s1=，s2=0；while（i++<n）{if (i%2) s1+=i;else s2+=i;}A.O(1)B.O(1bn)C.O（n）D.O(2n)8.下面程序段的时间复杂度为（D ）。
for(int i=0;i<m;i++)for(int j=0;j<n;j++)a[i][j]=i*j;A.O(m2)B.O(n2)C.O(m+n)D.O(m*n)9.执行下面程序段时，S语句的执行次数为（B）。
for(int i=1;i<=n;i++)for(int j=1,j<=i;j++)S;A.n(n-1)/2B.n(n+1)/2C.n2/2D.n10.在一个长度为n的顺序存储结构的线性表中，向第i个元素（1≤i≤n+1）位置插入一个元素时，需要从后向前依次后移（B）个元素。
A.n-iB.n-i+lC.n-i-lD.i11. 在一个长度为n的顺序存储结构的线性表中，删除第i个元素（1≤i≤n+1）时，需要从前向后依次后移（A）个元素。
A.n-iB.n-i+lC.n-i-lD.i12.在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为（C）。
A.(n+1)/2B.n/2C.nD.n+113.在一个顺序表的表尾插入一个元素的时间复杂度为（B）。
A. O(n)B. O(1)C. O(n*n)D. O(lbn)14.在一个顺序表中的任何位置插入一个元素的时间复杂度为（A）。
《计算机软件技术基础》复习题——答案1.线性表的链式存储结构与顺序存储结构相比优点是一CD2. 线性表是具有n 个C 的有限序列。
A.表元索B.字符C.数据元索E.信息项3. 若长度为n 的线性表采用顺序存储结构，在其第I 个位置插入一个新元索的算法的时间复杂度为 C (lWIWn+1)A. 0(0)B. 0(1)C. 0(n)D. 0(n 2)4. 设A 是一个线性表(g 弧…,弘)，采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需耍移动的元素个数为 B ,平均每删除一•个元素需要移动的元索个数为A ；若元索插在eh 与茹】之间(OWTWn-1)的概率为"匸"，则平均每插入一个 n(n +1)元素所要移动的元索个数为C5•下列函数屮，按它们在 ms 时的无穷人阶数，最大的是—D6•将卜•图所示的s 所指结点加到p 所指的结点之后，其语句应为：DA.所有的操作算法实现简单B.便于随机存取C.便于插入和删除 1).便于利川零散的存储器空间D.数据项C.2n + \D ・3n +14A . C. 10g/7n/2 B. nlog/7 D. n! nextnextnextA. 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. n B. 2n~l C. n~lD. 2n8. 卜面的程序段是合并两个无头结点链表(ha 和hb)为一个无头结点链表ha 的过程，作为 参数的两个链表都是按结点的data 域由人到小链接的。
![[07326]计算机软件技术基础题库(含答案)](https://img.taocdn.com/s1/m/2a22619ab4daa58da0114ab3.png)
[4] 操作系统的功能不包含（）。
A 处理机管理B 存储管理C 文件管理D 电子邮件管理[5] 在平均情况下速度最快的排序方法为（）。
A 简单选择排序B 冒泡排序C 堆排序D 快速排序[9] 采用段式存储管理的系统中，若地址用24位表示，其中8位表示段号，则允许每段的最大长度是（）。
A 2^24B 2^16C 2^8D 2^8[14] 若根据查找表建立长度为m的线性哈希表，采用线性探测再哈希法处理冲突，假定对一个元素第一次计算的哈希地址为d，则下一次的哈希地址为（）。
A dB d+1C （d+1）/mD （d+1）%m[15] 在一棵完全二叉树中，若编号为i的结点存在右子树，则右子结点编号为（）。
A 2iB 2i-1C 2i+1D 2i+2[19] 在下列文件的物理结构中，不利于文件长度动态增长的是（）。
A 顺序结构B 链接结构C 索引结构D HASH结构[24] 下列关系代数中按照二维表列进行运算的关系运算为（）。
A 并B 差C 投影D 选择E 链接[41] 什么是数据模型？答案：数据模型(data model)是描述数据如何表示、如何访问的抽象模型，常用来定义特定领域的数据元素和数据元素之间的关系。
（1分）在程序设计语言中，数据模型也常常称为数据结构。
在数据库领域中建立的数据模型称为数据库模型。
（1分）数据库模型(database model)是描述数据库结构和使用的方法和技术。
（1分）斐波那契（Fibonacci）数列的定义为：它的第一项和第二项均为1，以后各项为前两项之和。
若斐波那契数列中第n项用Fib(n)表示，则计算公式为：试根据下面程序填写出计算Fib(n)的递归算法和非递归算法。
递归算法如下： int Fib（int n）{if （n==1||n==2） 1； /*终止递归条件*/ return Fib（n-1）+ Fib（n-2））；} 非递归算法如下：int Fib1（int n）{ a，b，c；/*c代表当前项，a和b分别代表当前项前面的第二项和第一项*/ a=b= ；（n==1||n==2） return 1；elsefor（int i=3；i<=n；i++）{c= ； /*求出当前项*/ a= ； /*把前面第一项赋给前面第二项*/ b= ； /*把当前项赋给前面第一项*/ } return c； /*返回所求的第n项*/ }[21] 集合可以用下列哪些表示方法表示（）。
1数据库的三级模式和两级映像体系结构中，模式/内模式映像存在于概念级和内部级之间，用于定义概念模式和内模式间的对应性，其主要作用是什么。
答：作用是保证了数据与程序的物理独立性，模式/内模式之间的映像是数据的全局逻辑结构和数据的存储结构之间的映像，当数据库的存储结构发生了变化，由于模式/内模式之间的映像使数据的逻辑结构可以保持不变，因此应用程序可以不必修改。
2简述逻辑数据的独立性答：逻辑数据独立性是指应用程序与数据库的逻辑结构之间的相互独立性。
当数据的逻辑结构改变时，通过修改外模式——模式映像，保持数据的局部逻辑结构不变，应用程序是依据数据的局部逻辑结构编写的，所以应用程序不必修改。
即模式变，应用程序不变。
3何谓算法？它与程序有何区别？答：算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。
算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。
它与程序的区别⑴一个程序不一定满足有穷性，但算法是有穷性的。
⑵程序中指令必须是机器可以执行的，而算法中的指令则无此限制。
⑶算法代表了对问题的解，而程序是算法在机器上的特定实现。
4试说明栈和队列的异同。
答：相同：从数据结构的角度看，都是线性结构，都可以通过顺序表，列表实现。
不同点：⑴队列先进先出，栈先进后出。
⑵对插入和删除操作的"限定"。
栈是限定只能在表的一端进行插入和删除操作的线性表。
队列是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。
⑶遍历数据速度不同。
栈只能从头部取数据也就最先放入的需要遍历整个栈最后才能取出来，而且在遍历数据的时候还得为数据开辟临时空间，保持数据在遍历前的一致性队列怎不同，他基于地址指针进行遍历，而且可以从头或尾部开始遍历，但不能同时遍历，无需开辟临时空间，因为在遍历的过程中不影像数据结构，速度要快的多。
5何谓进程？请图示具有基本进程状态的状态转移图，并指出转移原因。
《计算机软件技术基础》参考答案A一、单项选择题(每空1分，共50分)1-5 CBCBD 6-10 ADDCB11-15 ACABB 16-20 BLJCI21-25 CCABC 26-30 BADAB31-35 BCDBA 36-40 DDCDA41-45 DDCAC 46-50 BBCAB评分标准：本题每空1分，多选、少选、错选均不得分。
二、本题10分(1) v != NULL或v(2) x > v->val 或x != v->val(3) p->next(4) u->next(5) head->next评分标准：本题10分，每空2分，在(3)-(5)中未写出next扣1分三、本题10分(1) A!=NULL && B!=NULL(2) A->data==B->data(3) B=B->next;(4) A!=NULL(5) last->next=NULL;评分标准：本题10分，每空2分，在(2)中未写出data扣1分，在(3)和(5)中未写出next扣1分四、本题10分解：(1) A、B、C三个进程之间存在互斥的制约关系。
因为打印机属于临界资源，必须一个进程使用完之后另一个进程才能使用。
(2)mutex：用于互斥的信号量，初值为1。
各进程的代码如下：进程A 进程B 进程C... … ...... … ...P(mutex) P(mutex) P(mutex)申请打印机申请打印机申请打印机使用打印机使用打印机使用打印机V(mutex) V(mutex) V(mutex)… … …评分标准：本题10分，(1)题3分，(2)题7分，其中给出信号量含义和初值1分，三个进程代码各2分五、本题10分解：FIFO淘汰算法：内存块为3时，缺页中断（或称缺页次数、页面故障）为9；内存块为4时，缺页中断为10。
LRU淘汰算法：内存块为3时，缺页中断为10评分标准：本题10分，FIFO淘汰算法两种情况各3分,LRU淘汰算法1分,要求有分析过程六、本题10分解：段式存储管理的地址转换过程为：（1）根据逻辑地址中的段号查段表的相应栏目；（2）根据段内地址<段长度，检查地址是否越界；（3）若不越界，则绝对地址=该段的主存起始地址+段内地址。
《计算机软件技术基础》试题1.线性表的链式存储结构与顺序存储结构相比优点是一CD2. 线性表是具有n 个 C的有限序列。
A.表元索B.字符C.数据元索E.信息项3. 若长度为n 的线性表采用顺序存储结构，在其第I 个位置插入一个新元索的算法的时间复杂度为 C (lWIWn+1)A. 0(0)B. 0(1)C. 0(n)D. 0(n 2)4. 设A 是一个线性表(g 弧…,弘)，采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需耍移动的元素个数为 B ,平均每删除一•个元素需要移动的元索个数为A ；若元索插在eh 与茹】之间(OWTWn-1)的概率为"匸"，则平均每插入一个 n(n +1)元素所要移动的元索个数为C5•下列函数屮，按它们在 ms 时的无穷人阶数，最大的是—D 6•将卜•图所示的s 所指结点加到p 所指的结点之后，其语句应为：DA.所有的操作算法实现简单B.便于随机存取C.便于插入和删除 1).便于利川零散的存储器空间D.数据项C.2n + \3D ・3n +14A . C. 10g/7n/2 B. nlog/7 D. n! nextnextnextA. 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. n B. 2n~l C. n~lD. 2n8. 卜面的程序段是合并两个无头结点链表(ha 和hb)为一个无头结点链表ha 的过程，作为 参数的两个链表都是按结点的data 域由人到小链接的。
合并后新链表的结点仍按此方式链 接。
数据结构习题答案第一节概论一、选择题1．要求同一逻辑结构的所有数据元素具有相同的特性，这意味着( )。
A．数据元素具有同一的特点 *B．不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等2．数据结构是一门研究非数值计算的程序设计问题中计算机的( (1) )以及它们之间的( (2) )和运算的学科。
(1) A．操作对象 B．计算方法 *C．物理存储 D．数据映像(2) A．结构 *B．关系 C．运算 D．算法3．数据结构被形式地定义为(D，R)，其中D是( (1) )的有限集合，R是D上( (2) )的有限集合。
(1) A．算法 *B．数据元素 C．数据操作 D．逻辑结构(2)A．操作 B．映像 C．存储 *D．关系4．在数据结构中，从逻辑上可以把数据结构分为( )。
A．动态结构和静态结构 B．紧凑结构和非紧凑结构 *C．线性结构和非线性结构 D．内部结构和外部结构5．线性表的顺序存储结构是一种( )的存储结构。
*A．随机存取 B．顺序存取 C．索引存取 D．Hash存取6．算法分析的目的是( )。
A．找出数据结构的合理性 B．研究算法中的输入和输出的关系 *C．分析算法的效率以求改进 D．分析算法的易懂性和文档性7．计算机算法指的是( (1) )，它必须具备输入、输出和( (2) )等五个特征。
(1) A．计算方法 B．排序方法 *C．解决某一问题的有限运算序列D．调度方法(2) A．可行性、可移植性和可扩充性 *B．可行性、确定性和有穷性 C．确定性，有穷性和稳定性 D．易读性、稳定性和安全性8．线性表若采用链表存储结构，要求内存中可用存储单元的地址( )。
A．必须是连续的 B．部分必须是连续的 C．一定是不连续的 *D．连续不连续都可以9．在以下的叙述中，正确的是( )。
A．线性表的线性存储结构优于链式存储结构 *B．二维数组是它的每个数据元素为一个线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出10．根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的数据组织形式，其中解释错误的是( )。
[4] 操作系统的功能不包含（）。
A 处理机管理B 存储管理C 文件管理D 电子邮件管理[5] 在平均情况下速度最快的排序方法为（）。
A 简单选择排序B 冒泡排序C 堆排序D 快速排序[9] 采用段式存储管理的系统中，若地址用24位表示，其中8位表示段号，则允许每段的最大长度是（）。
A 2^24B 2^16C 2^8D 2^8[14] 若根据查找表建立长度为m的线性哈希表，采用线性探测再哈希法处理冲突，假定对一个元素第一次计算的哈希地址为d，则下一次的哈希地址为（）。
A dB d+1C （d+1）/mD （d+1）%m[15] 在一棵完全二叉树中，若编号为i的结点存在右子树，则右子结点编号为（）。
A 2iB 2i-1C 2i+1D 2i+2[19] 在下列文件的物理结构中，不利于文件长度动态增长的是（）。
A 顺序结构B 链接结构C 索引结构D HASH结构[24] 下列关系代数中按照二维表列进行运算的关系运算为（）。
A 并B 差C 投影D 选择E 链接[41] 什么是数据模型？答案：数据模型(data model)是描述数据如何表示、如何访问的抽象模型，常用来定义特定领域的数据元素和数据元素之间的关系。
（1分）在程序设计语言中，数据模型也常常称为数据结构。
在数据库领域中建立的数据模型称为数据库模型。
（1分）数据库模型(database model)是描述数据库结构和使用的方法和技术。
（1分）斐波那契（Fibonacci）数列的定义为：它的第一项和第二项均为1，以后各项为前两项之和。
若斐波那契数列中第n项用Fib(n)表示，则计算公式为：试根据下面程序填写出计算Fib(n)的递归算法和非递归算法。
递归算法如下： int Fib（int n）{if （n==1||n==2） 1； /*终止递归条件*/ return Fib（n-1）+ Fib（n-2））；} 非递归算法如下：int Fib1（int n）{ a，b，c；/*c代表当前项，a和b分别代表当前项前面的第二项和第一项*/ a=b= ；（n==1||n==2） return 1；elsefor（int i=3；i<=n；i++）{c= ； /*求出当前项*/ a= ； /*把前面第一项赋给前面第二项*/ b= ； /*把当前项赋给前面第一项*/ } return c； /*返回所求的第n项*/ }[21] 集合可以用下列哪些表示方法表示（）。
A 列举法B 图表法C 流程图D 性质描述法E 递归法答案： AD[22] 数据库管理系统的功能有（）。
A 定义数据库B 管理数据库C 建立数据库D 维护数据库E 数据通讯[24] 根据操作系统在用户面前的使用环境以及访问方式，可将操作系统分为（）。
A 多道批处理操作系统B 分时操作系统C 实时操作系统D 手工操作系统E 并行操作系统[41] 进程间同步和互斥的含义是什么?并举例说明。
答案：同步：并发进程之间存在的相互制约和相互依赖的关系。
互斥：若干进程共享一资源时，任何时刻只允许一个进程使用。
（写对一个得1.5分，举例各1分）[44] 算法的基本特征是什么？答案：算法具有：有穷性、确定性、可行性（能行性）。
（2分）有穷性是指任何算法在经过有限的步骤之后总会结束，步骤的数量是一个合理的数字。
实际上，算法的有穷性包含了时间的含义。
如果某种算法从理论上可以实现，但是运行时间过长(例如要运行200年)则可能失去了实际的应用价值。
（1分）确定性是指算法的每一个步骤都是精确定义的，在任何情况下这些步骤都是严密的、清晰的。
该特征是指算法不允许出现模棱两可的解释、不允许有多种不同的理解，不同的人、不同的环境下对同一种算法的理解应该是明确的、唯一的。
（1分）可行性是指算法的每一个步骤都是可以实现的，即使人们用笔和纸进行手工运算，那么在有限的时间内也是可以完成的。
（[45] 什么是数据结构？数据结构对算法有哪些影响？答案：数据结构是指相互有关联的数据元素的集合.前后件关系是数据元素之间的一个基本关系，但前后件关系所表示的实际意义是随具体对象的不同而不同。
一般来说，数据元素之间的任何关系都可以用前后件关系来描述。
[7] 在对n个元素进行冒泡排序的过程中，最坏情况下的时间复杂度为（）。
A O（1）B O（lbn）C O（n2）D O（n）[25] 数据库中的常用的数据模型有（）。
A 网状模型B 层次模型C 关系模型D 概念模型E 结构模型[26] 一个结点的子树的个数称为该结点的。
答案：度[27] 顺序存储结构是通过表示元素之间的逻辑关系的。
答案：顺序表[35] 在二维数组a[10,20]中，每个元素占8个存储单元，假定该数组的首地址为2000，则数组元素a[6,15]的字节地址为__ __ ___。
答案： 3080[36] 黑箱法答案：黑箱法是指一个系统内部结构不清楚.或根本无法弄清楚时（1分）,从外部输入控制信息,使系统内部发生反应后输出信息（1分）,再恨据其输出信息来研究其功能和特性的一种方法（1分）。
[21] 常见的哈希码构造方法有（）。
A 截段法B 穷举法C 分段叠加法D 除法E 乘法答案： ACDE[27] 根据操作系统在用户面前的使用环境和访问方式，UNIX系统是一种__ __ ___操作系统。
答案：分时[36] 机器语言答案：机器语言(machine language)也称为机器代码指令(machine code instruction)，是指直接用二进制的机器代码指令编写的、由处理器执行的程序就是机器语言程序。
[37] 树的深度答案：树的深度是指树的所有结点中最大的层次，又称树的高度。
[38] 操作系统答案：操作系统(operating system，OS)是位于计算机系统中的硬件和软件之间的接口，负责管理和协调计算机硬件的操作和计算机有限资源的共享。
[41] 什么是需求分析？任务是什么？答案：需求分析是准确的理解用的需求将其转换成需求定义（1分），然后由需求定义转换成形式化的功能规约（1分）。
需求分析的困难表现在问题的复杂性、交流的障碍、不完备和不一致性、需求易变性（1分）。
任务：问题识别（功能需求、性能需求、环境需求、用户界面需求）分析综合导出逻辑结构、编写文档（需求规格说明书、初步用户手册、确认测试计划、完善修改软件开发计划）（2分）[42] 软件生命周期是什么？它包含哪些阶段？答案：软件生命周期(SDLC，Systems Development Life Cycle,SDLC)是软件的产生直到报废的生命周期,周期内有问题定义、可行性分析、总体描述、系统设计、编码、调试和测试、验收与运行、维护升级到废弃等阶段,这种按时间分程的思想方法是软件工程中的一种思想原则，即按部就班、逐步推进，每个阶段都要有定义、工作、审查、形成文档以供交流或备查，以提高软件的质量.[4] 结构化分析(SA方法)采用下列哪种思想进行分析（）。
A 自底向上逐层抽象B 自底向上逐层分解C 自顶向下逐层分解D 自顶向下逐层抽象[8] 深度为5的二叉树至少有( )个结点。
A 2B 3C 5D 10[9] 引入多道程序的目的是（）。
A 提高实时响应速度B 增强系统交互能力C 为了充分利用主存储器D 充分利用CPU，减少CPU等待时间[10] 在一棵树中，下面哪种结点没有父结点（）。
A 子结点B 叶子结点C 根结点D 空结点[12] 若要从1000个元素中得到10个最小元素，最好采用的方法为（）。
A 直接插入排序B 简单选择排序C 堆排序D 哈希表[13] 在一棵具有n个结点的二叉树的第i层上，最多具有多少个结点（）。
A 2iB 2i+1C 2i-1D 2n[14] 链表不具有的特点是（）。
A 可随机访问任一元素B 插入删除不需要移动元素C 不必事先估计存储空间D 所需空间与链表的长度成正比[15] 在一个顺序表中的任何位置插入一个元素的时间复杂度为（）。
A O(n)B O(n/2)C O(1)D O(n2)[17] 若对n个元素进行直接插入排序，在进行第i趟排序时，为寻找插入位子最多需要进行元素的比较的次数为（）。
（假定第0号元素放有待查的键值）A iB i-1C i+1D 1[19] DIMENSION A(N,M)语句的波兰表示正确的是（）。
A N M A DIMB (N M) A DIMC A( N M) DIMD DIM N M A[24] 数据的数据库管理具有的特点是（）。
A 数据的结构化B 数据的独立性C 数据的完整性D 数据的安全性E 数据的并发性[25] 编译程序一般需包含以下哪些程序模块（）。
A 词法分析程序B 加工程序C 优化修饰部分D 装配程序或者链接程序E 语法分析程序[26] __ __ ___是位于用户与操作系统之间的一层数据库管理软件，它为用户或应用程序提供访问数据库的方法，包括数据库的建立、查询、更新以及各种数据库控制等。
答案：数据库管理系统[27] 进程在运行过程中有3种基本状态，它们是运行态、就绪态和__ _。
答案：等待待态[29] __ __ ___的主要思想是，扫描数据序列，找到最小的数据，将该数据交换到序列最前面的位置，然后对其余数据序列重复前面的步骤直到数据全部排序为止。
答案：选择排序算法[31] 死锁是因而引起的一种现象。
答案：竞争资源[32] 若经常需要对线性表进行插入和删除运算，则最好采用__ __ ___存储结构。
答案：链式[33] 计算复杂度表示应用一种算法需要付出多大的努力或成本是多少。
计算成本可以用多种不同的标准衡量，__ __ ___和空间成本是两个最常用的成本标准。
答案：时间成本[40] 数据建模答案：数据建模(data modeling)是采用特定的方法和技术创建具体的数据模型的过程，用于定义和描述数据集合。
如果在数据库中建立数据模型，那么这种建模技术称为数据库建模.[44] 什么是集合结构？说出集合结构的典型操作答案：集合(set)是一种用于存储数据的简单数据结构，数据元素之间没有特定的顺序而且不能重复（1分）。
如果集合中的数据元素在使用过程中不再改变，那么这种集合称为静态集合，静态集合只能执行查询操作（1分）。
如果集合中的数据元素可以在使用过程中改变，那么这种集合称为动态集合，动态集合可以执行插入、删除、更新等操作（1分）。
集合结构的典型操作包括：build(x1, x2, …, xn)：创建一个包含了x1, x2, …, xn数据的集合；element_of(x, S)：检查S集合中是否存储数据x；empty(S)：检查S集合是否为空；size(S)：返回S集合中的数据元素的数量；enumerate(S)：按照任意顺序列出S集合中的数据；[1] 一个进程被唤醒，其含义是（）。
