内蒙古工业大学谢秀兰计算机软件基础小抄

《内蒙古工业大学谢秀兰计算机软件基础小抄》由会员分享，可在线阅读，更多相关《内蒙古工业大学谢秀兰计算机软件基础小抄（4页珍藏版）》请在装配图网上搜索。

1、1、 数据是现实世界客观存在的实体或事情的属性值。是信息的载体。2、 硬件系统的组成：运算器、控制器、存储器、输入设备输出设备。3、 数据对象：具有相同性质的数据元素的集合。4、 数据结构： 数据结构是指同一数据对象中各数据元素间存在的关系。S=(D,R) D是一个数据元素的非空有限集合，R是定义在D上的关系的非空有限集合。5、 算法表示：算法名（参量表）6、线性表的基本运算有： (1)插入：在两个确定元素之间插入一个新元素。(2)删除：删除线性表中某个元素。(3)查找：按某种要求查找线性表中的一个元素，需要时可以进行更新。(4)排序：按给定要求对表中元素重新排序。7、插入 设在长度为n的线性

2、表中第i个元素前插入一个元素x，其中存放线性表的向量为V1:m(mn)，算法如下： INSERTLIST(V,n,i,x)1. if (in+1) then 参数错 return2. for j=n to i step(-1)3. Vj+1Vj4. end (j)5. Vi x6. n n+17. return 8、回收一个由p指针指向的结点，放回空白链表的算法为： RET(p)1、 next(p) av 2、 av p3、 return9、设有顺序s1:m,top为栈顶指示器，其插入（进栈）和删除（退栈）运算如下： PUSH(s,m,top,x)/将元素x入栈/1. if(top=m)the

3、n“上溢”，return2. toptop+13. stop x4. returnPOP(s,top,y)/退栈，将栈顶元素送入y中/1. if(top=0)then“下溢”，return2. y stop3. toptop-1 4. return10、 设CQ0:m-1表示最大容量为m的循环队列，其中头、尾指示(front,rear)均按顺时针方向前进，rear=front=n-1为初态。循环队列的插入和删除算法如下： ADDCQ(CQ,m,front,rear,x)/将x插入队列CQ中/1. if(front=(rear+1)mod m) then “队满” return2. rear (

4、rear+1) mod m3. CQrearx4. returnDELCQ(CQ,m,front,rear,y)/删除队首元素送入y中/1. if(front=rear) then “队空”return2. front (front+1) mod m3. y CQfront4. return 11、设A，B分别为某稀疏矩阵转置前后的三元组表，i为行下标，j为列下标，v为元素值。变量m为稀疏矩阵行数，n为稀疏矩阵列数，tu为非零元素个数。本算法要求把A中的行下标、列下标交换后送到B中，并且使B中行下标仍按递增顺序存放。TRANSMAT(A，B) 1if(tu0) then 2q1 /q为转置以后

5、B的行号/ 3for col1 to n 4 for p1 to tu /p为转置前A的行号/5 if Apjcol then 6 BqiApj; BqjApi; 7 Bq v Apv；qq+1 8 end(p) 9 end(col) 10 return 12、树的定义：树是由n个(n0)结点组成的有限集合T，其中有且仅有一个结点称为根结点(root)，其余结点可以分为m(m0)个互不相交的有限集合T1,T2,Tm，其中每一个集合Ti本身又是一棵树，称为根结点root的子树。用二元组关系来定义树为 Tree(T，R)其中数据元素集合T及关系R组成。13、树结构中的术语:结点(node)：表示树

6、中的元素。结点的度(degree)：结点拥有的子树数。叶子(leaf)：度为零的结点，又称端结点。孩子(child)：除根结点外，每个结点都是其前趋结点的孩子。双亲(parents)：对应上述孩子结点的上层结点称为这些结点的双亲。兄弟(sibling)：同一双亲的孩子。结点的层次(level)：从根结点开始算起，根为第一层，根的直接后继结点为第二层，其余各层依此类推。 深度(depth)：树中结点的最大层次数。森林(forest)：是m(m0)棵互不相交的树的集合。有序树：树中结点在同层中按从左至右有序排列、不能互换的称为有序树，反之称为无序树。 14、二叉树的基本性质 (1)二叉树的第i层上

7、至多有2i-1(i1)个结点。(2)深度为h的二叉树中至多含有2h-1个结点。(3)在任意二叉树中，若有n0个叶子结点，n2个度为2的结点，则必有：n0n2+1。15、一般树转换为二叉树16、二叉树遍历DLR：先序遍历 LDR：中序遍历 LRD：后序遍历例：先序：ABCDEFG中序：CBDAEGF后序：CDBGFEA 17、遍历算法PREORDER(p)/先序遍历/1. if(pnil) then2. write(data(p)，/访问根结点/3. PREORDER(Lchild(p)；/遍历左子树/4. PREORDER(Rchild(p) /遍历右子树/5. return INORDER(

8、p) /中序遍历/1. if(pnil) then2. INORDER(Lchild(p)；/遍历左子树/3. write(data(p)；/访问根结点/4. INORDER(Rchild(p) /遍历右子树/5. returnPOSTORDER(p)/后序遍历/1. if(p nil) then2.POSTORDER(Lchild(P); /遍历左子树/3. POSTORDER(Rchild(p)；/遍历右子树/4. write(data(p) /访问根结点/5. return 18、将序列10，18，3，8，12，2，7，3构成一棵二叉排序树的过程。19、哈夫曼树的构造20、图的存储结构：

9、邻接矩阵和邻接表21、对分查找算法如下： BINSEARCH(r，n，K)1low1；highn /上下界指示器赋初值/2while(lowhigh)do3mid (low+high)div 2 /div为整除/4case5Krmidkey：(查找成功，return)6Krmidkey：low mid+17Krmidkey：high mid-18end(case)9end(while)10return22、简单选择排序：简单选择排序的基本操作是：在当前无序序列中选择一个关键字最小的记录，并将它和最前端的记录交换。重复上述操作，使记录区的前端逐渐形成一个由小到大的有序区。算法如下： SELSOR

10、T(r，n)1. for i=1 to n-12. ji 3. for ki+1 to n4. if(rj.keyrk.key) then jk 5. end(k)6. if(ji) then rirj /ri与rj交换/7. end(i) 8. Return23、冒泡排序算法如下： BUBBSORT(r，n)1. Fn 2. while(F0) do3. kF-1；F04. for j1 to k5. if rjrj+1 then rjrj+1；Fj6. end(j)7. end(do)8. return算法分析； 若原始序列已按关键字排序，则比较次数与移动次数最小：比较次数：C1n-1 (

11、进行一次扫描)移动次数：M10 当原始记录为逆序时，比较次数与移动次数为最大值： 比较次数： 移动次数：平均的时间复杂度为O(n2)。交换记录时需要一个辅助单元，因此空间复杂度为O(1)。24、操作系统分类：多道批处理系统、分时系统、实时系统。25、操作系统的功能：处理机管理、存储管理、设备管理、文件管理功能、用户接口功能。26、操作系统的特性：并发性、共享性、不确定性（异步性）、虚拟性、可靠及安全性、可维护性、扩充性 27、段表：与分页管理相似，系统为每个作业建立一个段映象表(SMT)，简称段表，段表中包括：段号、段的长度、段在主存中的起始地址、段的状态以及存取权限等。28、作业：作业是用户

12、在一次算题过程中或一个事务处理中要求计算机系统所做工作的集合。29、进程和程序区别： 进程是程序的执行，因此属于动态的概念；而程序是一组指令的集合，是属于静态的概念。 进程既然是程序的执行，因此它是有生命过程的，进程有诞生(创建进程)、执行（调度进程）和死亡(撤消进程)，因此进程的存在是暂时的，而程序的存在是永久的。 30、作业状态：提交、收容、执行、完成 (1)提交状态：用户向机房提交作业或通过终端键盘将作业输入，其作业所处的状态为提交状态。(2)收容状态：作业的全部信息已输入外存储器中等待运行，又称后备状态。(3)执行状态：作业被作业调度程序选中进入内存，称为执行状态。(4)完成状态：作业

13、执行完毕，释放其占用的全部资源，准备退出系统。31、进程三种基本状态： (1)就绪状态：这类进程已具备各种必需的资源，只等待获得CPU。(2)运行状态：系统根据某种调度算法，将CPU分配给某一个就绪进程使之运行，该进程就处于运行状态。(3)阻塞状态：进程在运行中由于要等待IO设备或发生其他错误时，就转入阻塞状态。原因消除后，重新回到就绪状态。32、死锁：死锁是指计算机系统中多个并发执行的进程竞争使用有限的系统资源而处于的一种僵持状态，若无外力作用将无法解除这种状态。产生死锁的原因为： 系统资源不足。进程推进的顺序不当。产生死锁的必要条件为： 所涉及的资源是非共享的。进程在等待新资源时，继续占用

14、已分配到的资源。一个进程占有的资源不能被别的进程强行抢占。一个进程获得的资源同时被另一个进程所请求，从而形成一个进程资源的循环链。解决死锁的方法： 死锁的预防死锁的避免死锁的检测和恢复33、文件：在逻辑上具有完整意义的数据或字符序列的集合。按用途分类： 系统文件库文件用户文件按存取权限分类：可执行文件：用户可以执行该文件，但不允许读也不允许修改该文件。只读文件：允许读出、执行该文件，但不准修改该文件。读写文件：允许读、写、执行该文件。不保护文件：可以被系统中任一用户使用的文件。34、开放系统互联参考模型OSI共分为7层： 物理层、数据链路层、网络层、传送层、会话层、表示层、应用层。36、TCP

15、IP采用分层模式，由4个层次组成：(1)应用层 (2)传输层(TCP) (3)网间网层(IP) (4)网络接口层。37、软件生命周期：软件从产生、发展到淘汰要经历定义、开发和维护三大阶段。更详细划分，又可分为六个或七个阶段。具体来说，即定义阶段的可行性论证与开发计划、需求分析，开发阶段的概要设计、详细设计和编码，维护阶段的测试、运行维护。38、详细设计：描述程序处理过程的工具称为详细设计的工具，它们可以分为图形、表格和语言三类。几种常用的表示工具。1程序流程图2盒图(NS图)3PAD图4过程设计语言(PDL)39、运算的时间分析 设pi是在第i个元素前插入一个元素的概率，则在长为n的表中插入一

16、个元素所需的平均移动次数为在等概率情况下，pi=1/(n+1)，则有在长度为n的线性表中删除一个元素所需移动次数的平均值为其中qi是删除第i个元素的概率。在等概率情况下，qi=1/n，则有35、转发器是最简单的互联设备没有“智能”。网桥是互联网络中最简单的具有“智能”的中继系统。运算符：* / * + - ；优先数：3 2 2 1 1 0￥例如有两个进程P1，P2都对某公共变量count作加1运算，如果当时进程按下列方式交替运行： P1：R1count; P2：R2count; P1：RlR1+1;countR1; P2：R2R2+1; countR2; 虽然P1，P2都对count作了加1运算，但count中只增加1。用PV操作实现进程互斥PV操作对信号量s(整型数)操作的定义为： P操作P(s)1. ss-12. if(s0)then3. status(q) “blocked” /将进程q置为 “阻塞”/4. insert(Q，q) /将q插入阻塞队列Q中/5. return V操作V(s)1. ss+12. if(s0)then3. remove(Q，R) /将R移出阻塞队列Q/4. status(R)“ready” /将R置为“就绪”/5. insert(RL，R) /将R插入就绪队列RL/6. Return