计算机软件技术基础复习大纲

《计算机软件技术基础复习大纲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《软件技术基础》复习大纲题型1.选择(2分1个，20’)2.填空(1空1分，20’)3.综合题(8题，60’)重点在数据结构部分和操作系统部分。第三章1线性表1.顺序存储结构的元素地址的计算。2.顺序存储结构的插入和删除操作。3.顺序存储结构的优缺点。4.(重点)链式存储结构，熟悉单链表和双向循环链表的特点以及基本操作。第三章2栈与队列熟悉栈和队列的特点顺序栈的基本操作，压栈，出栈,top指针如何移动？循环队列的队满，队空，插入数据，删除数据front和rear指针如何移动？voidpush(seqstack&s,intx){if(s.top==maxlen-1)cout<<"栈满";el

2、se{s.top++;s.stack[s.top]=x；}}voidpop(seqstack&s){if(s.top==0)cout<<"栈空";else{s.top--;}}循环队列上五种运算实现(1)队列初始化voidiniqueue(seqqueue&q){q.front=q.rear=maxsize-1;//头、尾指针相同时为空}(2)进队列voidenqueue(seqqueue&q,elemtypex)//将元素x插入到队列q中{if((q.rear+1)%maxsize==q.front)cout<<”overflow”;//队列已满else{q.rear=(q.rear+1

3、)%maxsize;q.queue[q.rear]=x;}//插入队列}(3)出队列voiddlqueue(seqqueue&q){if(q.rear==q.front)cout<<”underflow”;//队列为空elseq.front=(q.front+1)%maxsize;//队头元素出队列}7(4)取队头元素（注意得到的应为头指针后面一个位置值）elemtypegethead(seqqueueq){if(q.rear==q.front){cout<<”underflow”；returnNULL;}elsereturnq.queue[(q.front+1)%maxsize];}(5

4、)判队列空否intempty(seqqueueq){if(q.rear==q.front)reurn1;elsereturn0;}第三章2栈与队列设一数列的顺序为1,2,3,4,5通过栈操作,不可能得到的序列是()A.23451B.54123C.23145D.15432第三章3数组会计算二维数组中元素按行和按列存放，某个元素地址。例题：在二维数组a[1..30,1..40]中，按行优先存放，每个元素占8个存储单元，假定该数组的首地址为3000，计算：数组元素a[12,15]的字节地址。注意:1.数组下界是0还是12.按行存储还是按列存储用三元组表示稀疏矩阵第四章树形结构（重点）二叉树，满二

5、叉树，完全二叉树，二叉排序树和森林的概念和性质。二叉树的性质：A、二叉树的第i层上至多有2i-1（i1）个结点。B、深度为h的二叉树中至多含有2h-1个结点。C、若在任意一棵二叉树中，有n0个叶子结点，有n2个度为2的结点，则：n0=n2+1D、包含n个结点的二叉树边数为n-1二叉树的遍历。已知一棵二叉树的先序序列和中序序列分别为ABDHEICFJK和DHBEIACJFK，请画出此二叉树，并写出其后序遍历序列结果。利用哈夫曼树求字符的哈夫曼编码。要传输的电文是{CAS；CAT；SAT；AT}要传输的字符集是D={C，A，S，T，；}每个字符出现的频率是W={2，4，2，3，3}求每个字符

6、的哈夫曼编码。第5章图了解图的一些基本术语。例如：弧，边，连通分量，网等。图与2个存储结构(邻接表和邻接矩阵)之间的相互表示。图的广度和深度优先遍历(了解)图的应用（重点）掌握利用dijkstra算法求单源最短路径。第6章1查找了解二分查找。重点掌握哈希表查找方式：线性探查法和平方探查法，会计算ASL。第6章2排序（重点）排序方法插入排序选择排序交换排序归并排序线性插入排序对半插入排序简单选择排序堆排序冒泡排序快速排序熟练掌握各种排序算法排序。能够分析各种排序算法，掌握各种排序算法的特点，是否稳定，能否用链表表示等。例如快速排序在最好情况下，最坏情况下，平均情况下的时间复杂度。第6章2排序

7、（重点）第7章操作系统引论了解操作系统的历史，单道系统，分时操作系统，多道批处理操作系统，实时操作系统的特点。操作系统的基本特征。第8章处理器管理作业的概念，生命周期，状态转换。进程的概念，和程序的区别，状态转换。进程同步与互斥中：临界资源，临界区概念。同步与互斥的概念。P,V原语。当有n个并发进程共享某个临界资源时，互斥信号量的取值范围是。A-1~1B-1~(n-1)C-(n-1)~1D-(n-1)~(n-1)死锁产生