第一篇:数据结构笔试面试总结
一、线性表:
线性表的定义和抽象数据类型:线性表可以是有序、无序表;抽象类型包括数据和操作两个部分,数据部分可以用顺序,链接,散列,索引任何一种方法存储到计算机中;线性表的顺序存储结构和链接存储结构(单链表,双向链表,带表头的附加结点的线性链表,循环链表);操作:初始化单链表,删除单链表中的所有结点,使之成为一个空表,得到单链表的长度,检查单链表是否为空,得到单链表多种第及个结点中的元素,遍历一个单链表,从单链表中查找出等于给定值的第一个元素,更新单链表中等于给定值的第一个元素,向单链表中按照给定条件插入一个元素,从单链表中删除符合给定条件的第一个元素,对单链表进行数据排序.二、稀疏矩阵、集合、广义表
稀疏矩阵:非零元素的个数远远小于零元素个数,对于每个非零元素的表示是通过三元组(主序:行号,辅序:列号,元素值),采用顺序或链式方式存储。
广义表:线性表的推广,表或表中表。采用动态链接结构。递归的数据结构。
三、栈和队列
栈:只允许在表的一端进行插入和删除运算,对栈进行运算的成为栈顶,另一端为栈底。向栈插入元素叫进栈,删除元素叫出栈。栈是先进后出。栈顶指针为-1表示栈为空,进栈,栈顶指针+1,出栈,栈顶指针-1.递归数据结构。
队列:在一端进行插入,在另一端进行删除,插入的一端叫做队尾(rear),进行删除的一端叫做队首(front),先进先出。
四、树
非线性数据结构。
结点的度和树的度;分支结点和叶子结点;孩子结点和双亲结点;结点的层数和树的深度;有序树和无序树;森林;
树的性质;
二叉树:度为2的有序树。存储结构:顺序存储,数组;链接存储结构:指针;
二叉树的遍历:前序遍历:DLR
中序遍历:LDR
后序遍历:LRD
树的遍历:先根遍历,后根遍历,按层遍历
五:图
顶点的度依附于顶点的边的数目记为td(v);
顶点的出度od(v);
顶点的入度id(v);
td(v)=od(v)+id(v);
性质:n个顶点的无向图最多有n(n-1)/2 条边;n个顶点的有向图最多有n(n-1)条边;
六:查找:
查找:
1、顺序查找
2、二分查找
3、分块查找
4、数表的动态查找(二叉排序树查找、平衡二叉树AVL树、B树、B+树)
5、哈希查找
查找有静态查找和动态查找两种,静态查找只在数据结构里查找是否存在某 个记录而不改变数据结构。实现静态查找的数据结构称为静态查找表;动态查找 要在查找过程中插入数据结构中不存在的记录,或者从数据结构中删除已存在的记录。实现动态查找的数据结构称为动态查找表。衡量查找算法的标准是平均查 找长度,它是指在查找过程中进行的关键码比较次数的平均值。实现动态查找的 数据结构称为动态查找表。
静态查找表的查找方法主要有顺序查找、折半查找和索引查找等。顺序查找 不要求查找表中的记录有序,效率不是很高,适合于记录不是很多的情况。折半 查找要求查找表中的记录有序,查找效率很高,适合于记录比较多的情况。索引查找要求查找表分段有序,适合于记录非常多的情况。动态查找表主要介绍了二 叉排序树。二叉排序树是一棵二叉树,其左子树结点关键码的值小于根结点关键 码的值,右子树结点关键码的值大于根结点关键码的值。二叉排序树上的操作主要有查找、插入和删除等操作。
在哈希表中查找记录不需要进行关键码的比较,而是通过哈希函数确定记录 的存放位置。哈希函数的构造方法很多,主要有直接定址法、除留余数法、数字 分析法和平方取中法等。由于同义词会产生哈希冲突,解决哈希冲突的方法主要 有开放地址法和链表法等,其中开放地址法主要有线性探测法和二次探测法等。查找又称检索,是在程序设计中对数据结构中的记录进行处理时经常采用的 一种操作。同排序一样,查找是对关键码进行处理,关键码分为主关键码和次关键码,以主关键码进行的查找是最经常、也是最主要的查找。
1.顺序查找法
即从第一个元素顺序到最后一个元素依次与待查的值进行比较,如果相等,查找成功,否则继续比较,直到所有元素都比较过了,如果还没有匹配的值,查找失败。查找适用于数据量少、不要求已经排序的数据,它的时间复杂度为O(N);
2.二分查找
又称折半查找,适用于数据量大、已经排序的数据,它的时间复杂度为O(Log2(N))。
二分查找的基本思想是(设R[low..high]是当前的查找区间):
(1)首先确定该区间的中点位置:mid=(low+high)/
2(2)然后将待查的K值与R[mid].key比较:若相等,则查找成功并返回此位置,否则须确定新的查找区间,继续二分查找,具体方法如下:
①若R[mid].key>K,则由表的有序性可知R[mid..n].keys均大于K,因此若表中存在关键字等于K的结点,则该结点必定是在位置mid左边的子表R[1..mid-1]中,故新的查找区间是左子表R[1..mid-1]。
②类似地,若R[mid].key 因此,从初始的查找区间R[1..n]开始,每经过一次与当前查找区间的中点位置上的结点关键字的比较,就可确定查找是否成功,不成功则当前的查找区间就缩小一半。这一过程重复直至找到关键字为K的结点,或者直至当前的查找区间为空(即查找失败)时为止。 3.分块查找 分块查找(Blocking Search)又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法 分块查找表的存储结构由“分块有序”的线性表和索引表组成。 (1)“分块有序”的线性表 表R[1..n]均分为b块,前b-1块中结点个数为s=n/b,第b块的结点数小于等于s;每一块中的关键字不一定有序,但前一块中的最大关键字必须小于后一块中的最小关键字,即表是“分块有序”的。 (2)索引表 抽取各块中的最大关键字及其起始位置构成一个索引表ID[l..b],即:ID[i](1≤i≤b)中存放第i块的最大关键字及该块在表R中的起始位置。由于表R是分块有序的,所以索引表是一个递增有序表。 分块查找的基本思想是: (1)首先查找索引表,索引表是有序表,可采用二分查找或顺序查找,以确定待查的结点在哪一块。 (2)然后在已确定的块中进行顺序查找,由于块内无序,只能用顺序查找。 4.对查找算法的总结 (1)若n较小(如n≤40),可采用顺序查找。(2)若文件初始状态有序,且n较大,则应采用时间复杂度为O(Log2(N))的二分查找方法。(3)若文件初始状态分块有序,且n较大,则应采用分块查找。 七:排序 1、简单排序算法 (1)冒泡法 这是最原始,也是众所周知的最慢的算法。根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R:凡扫描到违反本原则的轻气泡,就使其向上“飘浮”。如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止。 (2)选择法 这种方法提高了一点性能(某些情况下),这种方法类似我们人为的排序习惯:从数据中选择最小的同第一个值交换,再从剩下的部分中选择最小的与第二个交换,这样往复下去。 (3)插入法 插入法较为复杂,它的基本工作原理是抽出牌,在前面的牌中寻找相应的位置插入,然后继续下一张。 2、高级排序算法 (1)快速排序 快速排序的基本思想是基于分治策略的。将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。首先我们选择一个中间值middle(程序中我们使用数组中间值),然后把比它小的放在左边,大的放在右边(具体的实现是从两边找,找到一对后交换)。然后对两边分别使用这个过程。 (2)Shell排序(希尔排序) 首先需要一个递减的步长gap,最后的步长必须是1。工作原理是首先对相隔较远的元素的所有内容排序,然后再使用同样的方法对相隔近些的元素的排序,以此类推。 (3)归并排序 把数据等分成两部分, 各自用归并排序排好后再合并,它在归并时耗费O(n)的空间。 3、对排序算法的总结 (1)若n较小(如n≤40),可采用插入排序或选择排序。当记录规模较小时,插入排序较好;反之,因为选择移动的记录数少于插人,应选选择排序为宜。(2)若文件初始状态基本有序(指正序),则应选用插人、冒泡或随机的快速排序为宜;(3)若n较大,则应采用时间复杂度为O(N?猳g2(N))的排序方法:快速排序、堆排序或归并排序。 快速排序是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;快速排序不适合用于“几乎已排好序”或“几乎正好倒序”的数据。在此最坏情况下,时间复杂度为O(N2)。堆排序所需的辅助空间少于快速排序,并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。归并排序是稳定的,而且适用于数据量特别大以至于无法在内存中容纳,需要通过外存来进行的外部排序。 堆和栈有什么区别: 1、栈区(stack)— 由编译器自动分配释放,存放函数的参数值,局部变量的值等。其操作方式类似于数据结构中的栈。 2、堆区(heap)— 一般由程序员分配释放,若程序员不释放,程序结束时可能由OS回收。注意它与数据结构中的堆是两回事,分配方式倒是类似于链表 一、单项选择题 下列各题备选项中,只有一项是正确的,请将所选答案序号填入题目的括号内。(共15分,每小题1分) 1、储蓄机构的设置要求熟悉储蓄业务的工作人员不少于(C)。A、二人B、三人C、四人D、五人 2、可疑支付交易里所称“短期”,是指(B)个营业日以内。A、五B、十C、十五D、七 3、教育储蓄的对象(储户)为在校小学(B)及以上学生。A、三年级B、四年级C、五年级 4、信用社的(B)是信用社的一定会计期所获得的经营成果。A.资产B.利润C.收入D.费用 5、信用社固定资产有偿转让、清理、报废和盘亏、毁损的净损失应计入(C)。 A、营业外收入B、其他营业支出C、营业外支出D、营业费用 6、工作人员在办理业务时如发现假票、假证或其他诈骗犯罪活动线索及可疑情况要及时报告(A)。 A、主管领导和保卫部门B、公安部门C、稽核部门D、纪检部门 7、人民币由(A)统一印制、发行。A、中国人民银行B、印币厂C、银监会 8、专项中央银行票据的发行到兑付,一般是2年,最长可延长到(B)年。A、3年B、4年C、5年 9、银行汇票金额起点为(D)元。A、200元B、300元C、400元D、500元 10、下面有关计算机的叙述中,正确的是(B)A:计算机的主机只包括CPUB:计算机程序必须装载到内存中才能执行 C:计算机必须具有硬盘才能工作D:计算机键盘上字母键的排列方式是随机的11、教育储蓄的对象(储户)为在校小学(C)年级及以上学生。A、二年级B、三年级C、四年级D、五年级 12、票据贴现的贴现期限最长不得超过(D)个月,贴现期限为从贴现之日起到票据到期日止。 A、三个月 B、四个月C、五个月D、六个月 13、安全保卫责任制的原则应坚持(C)。A、领导负责的原则;B、谁出问题,谁负责的原则; C、谁主管,谁负责的原则; D、领导与直接责任人共同负责的原则。 14、权责发生制.收付实现制等不同的记账准则与会计处理方法存在的基础是(C)这一原则。 A、持续经营B、会计主体C、会计分期D、货币计量 15、固定资产净残值率一般按固定资产原值的(B)确定。A、2—5%B、3—5%C、4—5% 二、多项选择题 下列每题给出的五个选项中,有二至五项是符合试题要求的,请将所选答案序号填入题目的括号内,多选、少选或错选均不得分。(共30分,每小题2分) 1、根据《商业银行法》规定,信用社可以经营下列业务(ABCDE)。 A、吸收公众存款B、发放短期、中期、长期贷款 C、办理国内外结算D、发行金融债券E、代理收付款项及代理保险业务 2、手持式点钞法有(BCD)。A、扇面B、单指多张C、多指多张D、单指单张 3、信用社固定资产的认定标准是(B C) A、使用年限在二年以上B、单位价值超过2000元C、使用年限在一年以上D、单位价值在1000元以上 4、信用社的结算原则:(ACD)A、恪守信用,履约付款 B、先收后付,收妥抵用C、谁的钱进谁的账,由谁支配D、银行不垫款 5、储蓄会计档案保管期限分为(ACE)。A、5年B、10年C、15年D、20年E、永久 6、下列权利哪些可以质押?(ABCDE)A、汇票 B、支票C、存款单D、债券E、提单 7、某信用社建造一座营业大楼,2001年12月竣工验收,因网点迁置未批复,直到2002年6月方投入使用,则固定资产转入日期及计提折旧日期分别为(AD)A、2001年12月B、2002年1月C、2002年6月D、2002年7月 8、信用社存款按其存款的对象大致可分为三大类,即(ABC)。A、财政性存款B、企事业单位存款C、储蓄存款D、教育存款 9、信用社日常出纳业务使用的印章有(ACD)。A、个人名章B、公章C、现金收讫章D、现金付讫章 10、人民法院有权对单位、个人存款进行(ABC)。A、查询B、冻结C、扣划D、支取 11、根据《商业银行法》规定,信用社可以经营下列业务(ABCDE)。 A、吸收公众存款B、发放短期、中期、长期贷款 C、办理国内外结算D、发行金融债券 E、代理收付款项及代理保险业务 12、下列财产哪些可以作为抵押物? A、抵押的房屋 B、抵押人的交通运输工具C、抵押人的耕地D、抵押人的自留地 13、在神码版综合业务系统中,柜员间款项交接需必用的交易有(A B C) A、款项交接交出0425B、交接确认0475C、确认交接0415D、款项交接查询046414、在神码版综合业务系统中,复核柜员可有下列哪些业务类型权限(B C D) A、现金业务B、事中复核C、查询业务D、特殊业务 15、下列哪些行为容易导致终端的损坏(AC)。 A、关掉电源后马上再开B、电源严格按照规定标准C、不注意防尘D、市电有小幅度波动 三、判断题 下列各项中,你认为正确的在括号内划“√”,错误的划“×”,全部划“√”或者全部划“×”,记为0分。(共 15分,每小题1分) 1、转账结算按区域分为同城支付和异地结算。(×) 2、存款人开立的帐户办理存款人本身的业务,可以出租和转让帐户。(×) 3、操作系统的功能可以用两句话来概括:对内管理计算机资源,对外为用户提供方便和友好的人——机界面。(√) 4、会计检查的种类按检查的方式可分为:直接检查 和实地检查。(×) 5、信用社要建立低值易耗品管理卡,每件在200元以上的物品都要进行登记管理,并定期核对,保证帐实相符。(√) 6、耕地、宅基地、自留地、自留山等集体所有的土地所有权和使用权可以做抵押。(×) 7、人民银行货币政策目标是保持币值的稳定,并以此促进经济增长。(√) 8、企业及个体工商户流动资金贷款期限最长不得超过一年。(√) 9、抵押贷款限额最高不得超过抵押物评估价值的60%。(×) 10、任何单位和个人购买商业银行股份总额10%以上的,应当事先经银行业监督管理机构批准。(×) 11、企业事业单位可以根据需要,可以选择几家商业银行的营业场所开立多个基本账户。(×) 12、冻结单位存款的期限不超过六个月,逾期不办理继续冻结手续的,视为自动撤销冻结。(√) 13、热启动的操作方法是先按下Ctrl、Alt两键的同时再按下Shift键。(×) 14、对已与第三人设定抵押、担保、交易或诉讼查封以及其他权益纠纷的资产,不得实行以资抵贷。(√) 15、至下午下班时间后,柜员现金碰库未平,可不作网点签退。(×) 四、解释题(共6分,每小题3分) 1、什么是会计账簿? 是以会计凭证为依据,全面、连续、系统 科学的反映各项经济业务的簿籍。 2、什么是抗辩权? 是指债权人行使债权时,债务人根据法定事由,对抗债权人行使请求的权利。 五、简答题(共12分,每小题4分) 1、会计内部控制的原则是什么? A、规范化原则B、授权分责原则C、监督制约原则D、帐务核对原则E、安全谨慎原则 2、对重要空白凭证应怎样进行管理? A.重要空白凭证一律纳入表外科目核算B.重要空白凭证管理要贯彻“印证分管,证押分管”的原则 C.柜面使用时应当逐份销号D.单位销户时必须将剩余的重要空白凭证交回注销,不得短缺 3、出纳工作的基本制度有哪些? 答:根据出纳工作的性质和任务,出纳工作的主要有以下10项基本制度:分管制度、四双制度、复核制度、双先制度、登记制 度、日清日结制度、交接制度、查库制度、报告制度和持证上岗制度。 主要能力优势:为人诚实正直、谦逊自信,乐于接受挑战。学习能力强,善于与人沟通,有服务意识和团队合作精神。勤奋好学,工作稳健、认真、细心、忠于职守。 应聘理由:热爱银行工作,虽然不是金融、经济类专业,但是我学习能力强,具备一定的知识素养和工作技能,相 信经过培训后能很快适应新工作。银行发展空间较大,特别是银行规范的制度和责任分工,更有利于员工的职业发展。多年的心理学专业知识储备使我学会如何更好地与人沟通,了解对方需求。此外,吃苦耐劳的品质和较 强的抗压能力使我能更好地胜任工作和服务客户。 4安庆是我的家乡,毕业后从事自己喜欢的工作服务家乡、报答社会一直是我的理想。 1)作一个自我介绍2)你为什么选择交行3)交行是国企,你为什么不去外企?4)你为什么选择柜员这个职位? 1、面试官让你作一个自我介绍。这绝不是一个流水账就可以打发的,面试官面对很多面试者,如何引起他们的兴趣,让他们对 自己留有印象?这是我们需要考虑的问题。因此我们的自我介绍可以1)重点突出自己与众不同的经历,比如有过出国交流经历,做过学生干部,参加过科研活动,得过什么奖项;或者是个人选择有关的,比如,我为何选择本科毕业后来复旦读硕士,我对自己的未来有了怎么样的规划,等;2)可以突出自己具备的素质。一般招聘公司都会写出自己想招的人的素质,如领导能力,创新能力等,我们在自我介绍的时候,可以有针对性的突出自己有这些方面的能力,有的放矢。如果对方明显要求了科研能力,这时候说自己发表过哪些学术文章远比强调自己参加了什么学术活动好。 2、你为什么选择交行? 这几乎是每个公司都爱问的问题,然后并不是每个人都会轻松对答。这个问题的核心是:你为什么选择我们,而非别人?这样最好从独特性来回答,以交行为例,可以说如下几点: 1)交行是最先上市的国内银行;产品多样化,创新能力强;发展有潜力,三季度的收入是90亿,被调高评级,etc;因此我认为交行是具备高的发展潜力的,我能有机会加入这样的银行,我也可以随之发展自己,获得发展空间;2)交行的管培项目做得最早,最为全面,体现了对人才的重视,所以我愿意加入。这些需要自己对公司的背景,近年的发展作过一些homework,然而这也是非常容易的,随便到公司网站上,或者搜一下新闻,就可以得到。面试官关注的是你到底对我们的公司有没有了解。 3、交行是国企,你为什么不去外企? 这样的问题,关键是认清这两者之间并无内在的冲突关系,将他们对立起来是没有道理的。我将这类问题归结为邓小平的“计划经济和市场经济”观点。“计划与市场,不是社会主义与资本主义的本质区别”同样,我们找工作,国企与外企不是我们最为关注的问题,我们关注的,公司本身如何,能否为我们提供发展空间,我们能否为公司作贡献,随公司的发展而成长。这样的问题可以变形,比如室友一次问我去面日企的时候,被问“为什么选择日企”该如何回答,我也是这样帮她分析的。、你为什么选择管培这个项目? 这样的问题,一般可以归结为两个方面,1)我了解这个项目涵盖的工作内容,我喜欢2)我具备做好这个工作的能力,是比较优势的理性选择。拿交行为例,可以说,这个项目有轮岗,我可以全面接触银行业务,迅速积累经验;并且我符合这个岗位所需要的素 质要求,我自信有能力可以做好。总之,要让面试官知道你是对认真思考过的,知道自己要什么,同时也表现出你对自己的自信。 1、在校期间的学生活动 这个问题是一个很大的问题,我谈到自己以前组织话剧社团的事情。这种问题一般是想听到领导能力和组织能力。相信每个人都会有自己的例子。他们问得很详细,因此又衍生出很多子问题,比如:1)如何调动成员的积极性?2)活动经费从何处来3)如果别人和你的意见不一致,你如何协调?4)课外活动和学业如何协调? 问这些问题,一方面为了证实你说的例子是真的还是假的,另一方面考察你的领导能力和组织能力。所以建议大家不要编造例子,即使编造,也要事前考虑的细致一点,否则很容易被问的露出马脚。同时,建议大家在讲述例子的时候,尽量绘声绘色一点,如果讲的平平淡淡,面试官也没有兴趣听下去了。 2、学术能力 学术问题: 1)你的研究兴趣是什么? 我理解的就是,其实面试官对这类问题的答案是并不太关心的。能够影响他们的决策或打分的更多的是你的表述方法和表达能力。比如,我的回答是,研究兴趣并非一直不变的,我的研究兴趣是从宏观到微观再到微观。然后展开说了下为什么经历了这样的变化。他们貌似还听的下去。我自己认为这类问题是可以由面试者主导的,控制面试的气氛并引导面试官询问有利于自己的问题,比如,你的兴趣为什么发生了这样的变化? 2)你对外汇储备的看法,多还是少?有什么深远影响? 这样的问题仁者见仁,是属于非常好说的宏观问题。分析的有道理就可以了。注意有条理性,先告诉面试官:我认为有如下几个方面的影响,分别是什么。然后再展开细说,如果他不要求你细说,则简明扼要的表达观点。他对哪个观点感兴趣,他会追问的。他追问我的问题就是:1)冲销操作有哪些?我国的冲销存在哪些问题?2)如果你认为外汇储备过高,你觉得可以采用什么的解决办法? 《数据结构与算法》课程学习总结报告 本学期开设的《数据结构与算法》课程已经告一段落,现就其知识点及其掌握情况、学习体会以及对该门课程的教学建议等方面进行学习总结。 一、《数据结构与算法》知识点 第一章是这门学科的基础章节,从整体方面介绍了“数据结构和算法”,同时引入相关的学术概念和术语,如数据、数据元素、数据类型以及数据结构的定义。重点是数据结构的括逻辑结构、存储结构和运算集合的含义及其相互联系。数据结构和两大逻辑结构的4四种常用存储方法;逻辑结构分为四类:集合型、线性、树形和图形结构,数据元素的存储结构分为:顺序存储、链接存储、索引存储和散列存储四类。难点是算法复杂度的分析方法和性能的分析。 第二章详细地分析了顺序表。介绍了顺序表的相关概念及其有关运算。基本运算有:初始化表、求表长、排序、元素的查找、插入及删除等。元素查找方法有:简单顺序查找、二分查找和分块查找。排序方法有:直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序及归并排序等,在各种算法思想的先分析后,要弄清各种算法的时间复杂度与空间性能的优点和缺点,在什么特定的场合适合哪种算法思想。最后介绍了顺序串的概念,顺序串是顺序表的一个特例;区别在于组成顺序串的数据元素是一组字符,其重点在于串的模式匹配。 第三章介绍链表。链表中数据元素的存储不一定是连续的,还可以占用任意的、不连续的物理存储区域。与顺序表相比,链表的插入、删除不需要移动元素,给算法的效率带来较大的提高,且在存储空间上有动态申请的优点。这一章中介绍了链表的节点结构、静态与动态链表的概念、链表的基本运算(如求表长、插入、查找、删除等)、单链表的建立(头插法和尾插法)以及双向循环链表的定义、结构、功能和基本算法。弄清其个运算的算法思想及其时间复杂度和空间性能。最后介绍了链表之中存储结构在实际中的相关应用。 第四章,堆栈是运算受限制的线性结构。其基本运算方法与顺序表和链表运算方法基本相同,不同的是堆栈须遵循“先进后出”的规则,对堆栈的操作只能在栈顶进行;堆栈在文字处理,匹配问题和算术表达式的求值问题方面的应用。 第五章,队列是一种够类似堆栈的线性结构。其基本运算方法与顺序表和链表运算方法基本相同,不同的是堆栈须遵循“先进先出”的规则,对堆栈的操作只能在栈顶进行;其运算有入队、出队等操作。在介绍队列时,提出了循环队列的概念,以避免“假溢出”的现象。 第六章介绍了特殊矩阵和广义表的概念与应用。其中,特殊矩阵包括对称矩阵、三角矩阵、对角矩阵和稀疏矩阵,书中分别详细介绍了它们的存储结构。其中三元组和十字链表这两种结构尤为重要;对着两种结构的建立了应用要掌握。稀疏矩阵的应用包括转置和加法运算等。最后介绍了广义表的相关概念及存储结构,关于它的应用,课本中举了m元多项式的表示问题。 第七章二叉树的知识是重点内容。在介绍有关概念时,提到了二叉树的性质以及两种特殊的二叉树:完全二叉树和满二叉树。接着介绍二叉树的顺序存储和链接存储以及生成算法。重点介绍二叉树的遍历算法(递归算法、先序、中序和后序遍历非递归算法)和线索二叉树。二叉树的应用:基本算法、哈弗曼树、二叉排序树和堆排序,其中关于二叉排序树和哈弗曼书的构建是重点。 第八章介绍了树。树与二叉树是不同的概念。教材介绍了树和森林的概念、遍历和存储结构,还有树、森林和二叉树的相互关系,树或森林怎样转化成二叉树,二叉树又如何转换为树和森林等算法。 第九章,散列结构是一种查找效率很高的一种数据结构。本章的主要知识点有:散列结 构的概念及其存储结构、散列函数、两种冲突处理方法、线性探测散列和链地址散列的基本算法以及散列结构的查找性能分析。 最后一章介绍了图的概念及其应用,是本书的难点。图的存储结构的知识点有:邻接矩阵、邻接表、逆邻接表、十字链表和邻接多重表。图的遍历包括图的深度优先搜索遍历和广度优先搜索遍历。其余知识点有:有向图、连通图、生成树和森林、最短路径问题和有向无环图及其应用。有向无环图重点理解AOV网和拓扑排序及其算法。 二、对各知识点的掌握情况 总体来看,对教材中的知识点理解较为完善,但各个章节均出现有个别知识点较为陌生的现象,对某些具体的问题和应用仍有一些模糊与措手。各个章节出现的知识点理解和掌握情况明确一下。 第一章中我对数据和数据结构的概念理解较为透彻,熟悉数据结构的逻辑结构和存储结构。算法的时间、空间性能分析是重点,同样也是难点,尤其是空间性能分析需要加强。在某些强大与复杂的算法面前的处理有些棘手。 第二章,顺序表的概念、生成算法理解较为清晰,并且熟悉简单顺序查找和二分查找,对分块查找较为含糊。删除方面的问题比较容易些。排序问题中,由于冒泡排序在大一C语言课上已经学习过,再来学习感觉相对轻松些。对插入排序和选择排序理解良好,但是,在实际运用中仍然出现明显不熟练的现象。由于在归并排序学习中感觉较吃力,现在对这种排序方法仍然非常模糊,所以需要花较多的时间来补习。此外串的模式匹配也是较难理解的一个地方。 第三章链表中,除对双向循环链表这一知识点理解困难之外,在对链表进行插入删除和排序相关操作上同顺序表的操作基本相当。其他的知识点像单链表的建立和基本算法等都较为熟悉。 第四章和第五章有关堆栈以及队列的知识点比较少,除有关算法较为特殊以外,其余算法都是先前学过的顺序表和链表的知识,加上思想上较为重视,因此这部分内容是我对全书掌握最好的一部分。在一些实际问题的应用与处理方面,对其进行存储结构的选择还是需要认真考虑的。在算法的时间复杂度和空间性能的分析仍有些困难。 第六章的学习感觉较为困难的部分在于矩阵的应用上。在矩阵的存储结构中,使用三元组表发相对较为简单,而使用十字链表就有些困难了。但在某些问题的处理上又必须或从节省空间考虑采用十字链表来处理,想矩阵的加法运算。广义表的定义还是比较容易理解的,其存储结构也不难掌握,关于应用也只局限于在多项式的表示上。 第七章是全书的重点。在这一章中概念和定义都很多,有些很昏人但都很重要,要区分开来。二叉树的性质容易懂却很难记忆。对二叉树的存储结构和遍历算法这部分内容掌握较好,能够熟练运用。关于二叉排序树和的哈弗曼树却相对有些压力,其生成和对其关键字的插入和删除时重点。 第八章关于树的分析,首先要明确树和二叉树的区别,以及书中的相关定义和概念。关于二叉树、树和森林之间的转换和遍历方法是重点,但不算是难。接着就是数的存储结构的选择及转化为二叉树的算法,这部分有些吃力。再就介绍了特殊的树-B树,关于对B树的操作,插入关键字是中带领和难点。 第九章散列结构这一章理解比较完善的知识点有:基本概念和存储结构。散列函数中直接定址法和除留余数法学得比较扎实,对数字分析法等方法则感觉较为陌生。对两种冲突处理的算法思想的理解良好,问题在于用C语言描述上。 最后一章,图及其应用中,相关定义及其概念很多,容易混淆,这就要慢慢来,仔细分辨。图的邻接矩阵、邻接表表示法及其之间的转换时重点和难点。而对十字链表和邻接多重表的表示法则较为陌生。感觉理解较为吃力的内容有图的遍历(包括深度和广度优先遍历),以及最小生成树的问题。最短路径、AOV网、关键路径、AOE网和拓扑排序的学习也是相对较轻松的。,三、学习体会 在学习开始,王教授就明确提出它不是一种计算机语言,不会介绍新的关键词,而是通过学习可以设计出良好的算法,高效地组织数据。一个程序无论采用何种语言,其基本算法思想不会改变。联系到在大一和大二上学期学习的C和C++语言,我深刻认识到了这一点。“软件开发好比写作文,计算机语言提供了许多华丽的辞藻,而数据结构则考虑如何将这些辞藻组织成一篇优秀的文章来。”在学习这门课中,要熟悉对算法思想的一些描述手段,包括文字描述、图形描述和计算机语言描述等。因此,计算机语言基础是必须的,因为它提供了一种重要的算法思想描述手段——机器可识别的描述。 这门课结束之后,我总结了学习中遇到的一些问题,最为突出的,书本上的知识与老师的讲解都比较容易理解,但是当自己采用刚学的知识点编写程序时却感到十分棘手,有时表现在想不到适合题意的算法,有时表现在算法想出来后,只能将书本上原有的程序段誊写到自己的程序中再加以必要的连接以完成程序的编写。针对这一情况,我会严格要求自己,熟练掌握算法思想,尽量独立完成程序的编写与修改工作,只有这样,才能够提高运用知识,解决问题的能力。 四、对《数据结构与算法》课程教学的建议 1、建议在上课过程中加大随堂练习的分量,以便学生能当堂消化课堂上学习的知识,也便于及时了解学生对知识点的掌握情况,同时有助于学生保持良好的精神状态。 2、建议在课时允许的情况下,增加习题课的分量,通过课堂的习题讲解,加深对知识点的掌握,同时对各知识点的运用有一个更为直观和具体的认识。 以上便是我对《数据结构与算法》这门课的学习总结,我会抓紧时间将没有吃透的知识点补齐。今后我仍然会继续学习,克服学习中遇到的难关,在打牢基础的前提下向更深入的层面迈进! Linux笔试面试知识点总结 在Linux的笔试中常会考察一些知识点。这里我们就来总结一下有可能出现的知识点都有哪些。 1.在Linux系统中,以文件方式访问设备。 2.Linux内核引导时,从文件 /etc/fstab 中读取要加载的文件系统。3.Linux文件系统中每个文件用 i节点(inode)来标识。 4.全部磁盘块由四个部分组成,分别为引导块、专用块、i节点表块和数据存储块。 5.链接分为:硬链接和符号链接。 6.超级块包含了i节点表和空闲块表 等重要的文件系统信息。 7.某文件的权限为:drw-_r--_r--,用数值形式表示该权限,则该八进制数为: 644,该文件属性是 目录。/*rwx---421,8.前台起动的进程使用Ctrl+c终止。 9.静态路由设定后,若网络拓扑结构发生变化,需由系统管理员修改路由的设置。 10.网络管理的重要任务是:控制和监控。 11.安装Linux系统对硬盘分区时,必须有两种分区类型:文件系统分区和交换分区。 13.编写的Shell程序运行前必须赋予该脚本文件执行权限。 14.系统管理的任务之一是能够在分布式环境中实现对程序和数据的安全保护、备份、恢复和更新。 15.系统交换分区是作为系统 虚拟存储器 的一块区域。 16.内核分为进程管理系统、内存管理系统、I/O管理系统和文件管理系统等四个子系统。 17.内核配置是系统管理员在改变系统配置硬件时要进行的重要操作。 18.在安装Linux系统中,使用netconfig程序对网络进行配置,该安装程序会一步步提示用户输入主机名、域名、域名服务器、IP地址、网关地址 和 子网掩码 等必要信息。 19.唯一标识每一个用户的是用户ID和用户名。.RIP协议是最为普遍的一种内部协议,一般称为动态路由信息协议。 21.在Linux系统中所有内容都被表示为文件,组织文件的各种方法称为文件系统。 22.DHCP可以实现动态IP地址分配。/*Dynamic Host Configuration Protocol, DHCP*/ 23.系统网络管理员的管理对象是服务器、用户和服务器的进程以及系统的各种资源。 24.网络管理通常由监测、传输和管理三部分组成,其中管理部分是整个网络管理的中心。 25.当想删除本系统用不上的设备驱动程序时必须编译内核,当内核不支持系统上的设备驱动程序时,必须对内核升级。Ping命令可以测试网络中本机系统是否能到达 一台远程主机,所以常常用于测试网络的连通性。/*icmp,27.vi编辑器具有两种工作模式:命令模式和输入模式。/*命令模式、输入模式、底行模式,徐波 28.可以用ls –al命令来观察文件的权限,每个文件的权限都用10位表示,并分为四段,其中第一段占 1 位,表示文件类型,第二段占3位,表示文件所有者对该文件的权限。 29.进程与程序的区别在于其动态性,动态的产生和终止,从产生到终止进程可以具有的基本状态为:运行态、就绪态和等待态(阻塞态)。 30.DNS实际上是分布在internet上的主机信息的数据库,其作用是实现IP地址和域名之间的转换。 31.Apache是实现www.xiexiebang.com的域名是 bns.com.cn,如果要配置一域名服务器,应在 named.conf 文件中定义DNS数据库的工作目录。 71.Sendmail邮件系统使用的两个主要协议是: SMTP和POP,前者用来发送邮件,后者用来接收邮件。 72.DHCP是动态主机配置协议的简称,其作用是:为网络中的主机分配IP地址。73.目前代理服务器使用的软件包有很多种,教材中使用的是 squid。 74.rm命令可删除文件或目录,其主要差别就是是否使用递归开关-r或-R。75.mv 命令可以移动文件和目录,还可以为文件和目录重新命名。 76.路由选择协议(RIP)的跳数表示到达目的地之前必须通过的网关数,RIP接受的最长距离是15跳。 77.ping命令用于测试网络的连通性,ping命令通过 ICMP 协议(internet控制信息协议)来实现。 78.nfs 协议用于实现Unix(/linux)主机之间的文件系统共享。79.在Linux操作系统中,设备都是通过特殊的 文件 来访问。 80.shell不仅是 用户命令的解释器,它同时也是一种功能强大的编程语言。bash是Linux的缺省shell。 81.用 >;>;符号将输出重定向内容附加在原文的后面。82.增加一个用户的命令是:adduser 或useradd。83 进行字符串查找,使用grep命令。84.使用 * 每次匹配若干个字符。 85./sbin 目录用来存放系统管理员使用的管理程序 ㈠、一台配置较低的Linux服务器(内存、硬盘比较小)的/data分区内创建文件时,系统提示磁盘空间不足,用df-h命令查看了一下磁盘使用情况,发现/data分区只使用了66%,还有12G的剩余空间,按理说不会出现这种问题。 分析问题: 后来用df-i查看了一下/data分区的索引节点(inode),发现已经用满(IUsed=100%),导致系统无法创建新目录和文件。 inode译成中文就是索引节点,每个存储设备(例如硬盘)或存储设备的分区被格式化为文件系统后,应该有两部份,一部份是inode,另一部份是 Block,Block是用来存储数据用的。而inode呢,就是用来存储这些数据的信息,这些信息包括文件大小、属主、归属的用户组、读写权限等。inode为每个文件进行信息索引,所以就有了inode的数值。操作系统根据指令,能通过inode值最快的找到相对应的文件。 而这台服务器的Block虽然还有剩余,但inode已经用满,因此在创建新目录或文件时,系统提示磁盘空间不足。 ㈡ 1.Linux链接概念 Linux链接分两种,一种被称为硬链接(Hard Link),另一种被称为符号链接(Symbolic Link)。默认情况下,ln命令产生硬链接。 【硬连接】 硬连接指通过索引节点来进行连接。在Linux的文件系统中,保存在磁盘分区中的文件不管是什么类型都给它分配一个编号,称为索引节点号(Inode Index)。在Linux中,多个文件名指向同一索引节点是存在的。一般这种连接就是硬连接。硬连接的作用是允许一个文件拥有多个有效路径名,这样用户就可以建立硬连接到重要文件,以防止“误删”的功能。其原因如上所述,因为对应该目录的索引节点有一个以上的连接。只删除一个连接并不影响索引节点本身和其它的连接,只有当最后一个连接被删除后,文件的数据块及目录的连接才会被释放。也就是说,文件真正删除的条件是与之相关的所有硬连接文件均被删除。 【软连接】 另外一种连接称之为符号连接(Symbolic Link),也叫软连接。软链接文件有类似于Windows的快捷方式。它实际上是一个特殊的文件。在符号连接中,文件实际上是一个文本文件,其中包含的有另一文件的位置信息。 2.通过实验加深理解 [oracle@Linux]$ touch f1 #创建一个测试文件f1 [oracle@Linux]$ ln f1 f2 #创建f1的一个硬连接文件f2 [oracle@Linux]$ ln-s f1 f3 #创建f1的一个符号连接文件f3 [oracle@Linux]$ ls-li #-i参数显示文件的inode节点信息 total 0 9797648-rw-r--r--2 oracle oinstall 0 Apr 21 08:11 f1 9797648-rw-r--r--2 oracle oinstall 0 Apr 21 08:11 f2 9797649 lrwxrwxrwx 1 oracle oinstall 2 Apr 21 08:11 f3-> f1 从上面的结果中可以看出,硬连接文件f2与原文件f1的inode节点相同,均为9797648,然而符号连接文件的inode节点不同。 [oracle@Linux]$ echo “I am f1 file” >>f1 [oracle@Linux]$ cat f1 I am f1 file [oracle@Linux]$ cat f2 I am f1 file [oracle@Linux]$ cat f3 I am f1 file [oracle@Linux]$ rm-f f1 [oracle@Linux]$ cat f2 I am f1 file [oracle@Linux]$ cat f3 cat: f3: No such file or directory 通过上面的测试可以看出:当删除原始文件f1后,硬连接f2不受影响,但是符号连接f1文件无效 3.总结 依此您可以做一些相关的测试,可以得到以下全部结论: 1).删除符号连接f3,对f1,f2无影响; 2).删除硬连接f2,对f1,f3也无影响; 3).删除原文件f1,对硬连接f2没有影响,导致符号连接f3失效; 4).同时删除原文件f1,硬连接f2,整个文件会真正的被删除。 ㈢超级用户登录后的操作提示符是“#”;普通用户登录后的操作提示符是“$” ㈣$ id uid=501(chris)gid=105(sales)groups=105(sales),4(adm),7(lp),请问这是什么意思呢? 当前用户的用户名是chris,标志他的唯一id是501这个udi,这个用户属于sales这个主组。组用一个唯一的序号标示,是105,这个用户还属于sales adm ip这三个辅组。 一个用户创建用户的时候一般会分配一个组给他。这个就是gid,主组。但是这样并不满足很多要求。于是在之后又能让这个用于加入很多组。这些组是辅组 C++笔试和面试总结 给大家分享一下我的笔试和面试经历吧!笔试主要的题型有选择题、填空题、程序填空题、程序设计题目。选择和填空题的题目主要包含以下: C语言部分: 1.逻辑运算的短路特性(考的很多)2.++、--运算符 3.位运算 4.强制类型转换 5.程序结构控制 6.数组和指针的使用 7.结构体有关(字节对齐、位段结构体)8.文件操作 9.字符串常用相关操作(非常重要)10.递归 C++部分: 1.面向对象语言特性 2.名字空间 3.函数参数传递方式以及之间的区别 4.引用 5.构造函数与析构函数的调用顺序 6.基类成员在派生类中的可见性 7.const和static的作用(有时也会考自动类型转换和explict关键字)8.多继承(考得少)9.运算符重载 10.静态联编和动态联编 11.函数模板与类模板 12.IO常用操作 13.异常处理(考的较少)14.STL容器(非常重要,比如map内部结构是什么,map内部怎么排序)数据结构部分: 1.链表的创建和元素的插入删除以及时间复杂度 2.栈和队列的特性 3.字符串KMP匹配算法 4.二叉树的构建(考得少)5.二叉树的遍历(递归和非递归算法)6.完全二叉树节点之间的数量和序号关系(大概是5条)7.哈夫曼树构建及其编码(腾讯2014校招考题)8.数和森林的转换(考的比较少,但也比较简单,会画图即可)9.排序(直接插入、选择、冒泡、快排、Shell、二路归并(2014校招腾讯考题))10.查找(包括直接查找、折半查找、建立索引、构建散列函数)11.伙伴地址(腾讯2014校招考题)12.二叉排序树和平衡二叉树的概念 Unix部分: 1.常用Shell命令 2.Shell脚本编程 软件工程部分: 1.软件过程 2.测试类型 3.面向对象常见概念(包含与继承、覆盖/重写/重载、多态)4.UML 操作系统部分: 1.进程同步、通信、多线程 2.死锁 3.信号 4.临界区、原子锁、互斥量、管道 数据库部分: 1.关系和视图的概念; 2.关系的交、并、差运算和选择、投影、连接、除运算 3.索引及其作用 4.SQL语句基本操作(尤其是语句查询、非常重要)5.游标(作用和使用)6.事务(概念)计算机网络技术部分: 1.按照作用范围对网络的划分(WAN、LAN、MAN、PAN)2.局域网的拓扑结构 3.IP地址分类 4.子网掩码 5.TCP和UCP协议的中文名称以及数据传输特点比较 6.域名服务器及FTP工作原理 7.OSI模型七层结构及各层作用和各层使用的协议 常见程序设计题(算法居多)1. C语言字符串操作(非常重要)2. 线性结构排序(一种排序的多方法实现)3. 递归的使用 4. SQL语句设计 5. 公司内部相关 我的面试总结 面试根据各个公司的情况不同而不同,一般会分为几轮面试。技术类面试的时候 衣物不要太花哨,简单朴素整洁就好,头发一定要整齐,面试的时候一般要准备一支黑色签字笔、一张稿纸、一份简历、一份成绩单原件(必须盖过章)、一份四六级成绩单的复印件。 首先在一面的时候很可能遇到群面,即群体面试,说明你命运比较悲惨。一般是6 人一小组,一般采取刷一半留一半原则,在群体面试(以我在神州数码面试为例)中,第一轮肯定是自我介绍,在这轮面试中一定要仔细聆听他人的自我介绍的一些信息,比如来自哪个学校?学什么专业?家住哪里?因为自我介绍完毕后他很可能问你其中某个同学的已经告知大家的信息,因为他要测试你的团队合作能力,然后逐个介绍自己所做的项目,这个凭自己发挥了,最后他们会给你们设计一个任务(比如举办一场晚会),让你们群体讨论合作完成,每个人都有一个相应的角色。尤其要注意的是,一般在群面中第一个发言的和发言最少的往往就是炮灰,最可能被刷掉。然后就说单面吧,单面也是先自我介绍,自我介绍时尤其注意,时间最好不要超过3分钟,关于个人信息的就描述一下自己出生于哪个省份,来自于哪个学校(如果是个985或者211一定要说明),学什么专业,技术爱好,然后就是简述一下自己做过的项目。接下来面试官就会仔细阅读你的四六级通过情况、专业课达标情况,最后就是你的项目里面的技术细节问题,一定要如实回答,会什么写什么,不会的千万不要写。一面结束了,如果在24小时之内你没有收到下一轮面试通知,那你很可能已经被刷掉(当然还有可能因为指标太少问题,时间更长,你才能接到下一轮面试)。进入下轮面试一般情况是公司所需的技术考核,这轮面试一般来说难度是最大的,这个就靠的是你平时的基本功了,如果本轮面试通过,那么恭喜你已经有八成的几率被录取。最后一轮一般是Offer面谈,如果前面你有比较好的offer,那么你一定要要求比这个offer高出1~2万,但如果之前没有像样儿的Offer,那么你先让人力的说明Offer,如果很满意就签吧,如果不是十分满意,不要很快把三方给公司,要以学校方面或者考试等为由使出缓兵之计,尽量将时间拖延至最大,以抽出时间进行下一个公司的应聘。因为如果你把三方已签,再想签约别的公司的话,就意味着要毁约,当然违约金不可避免,况且毁约是一件相当麻烦的事情,因为现在毁约的话,在公司要经过好多的部门审核(以我实习结束办理手续为例,要经过财务部、仓库、企信办、人力资源等19个部门的签字),过程相当麻烦,这很可能让你赔了夫人又折兵。 简历制作 再说说简历制作问题吧,简历整体要模块划分。第一栏就是个人信息模块,我想强调的是把自己的名字字体放大加粗加黑一下吸引眼球,然后下面列举个人的出生地、来自学校、专业、出生年月、应聘类型(C++还是嵌入式开发)、联系方式、邮箱地址、英语级别(通过四级/六级),如果是应聘国企最好加上政治面貌,而且在四级或者六级成绩比较好的话最好列举出自己的成绩。还有如果学校是985或者211,那么在页眉加一张有校园校徽并且具有985或者211信息的图片,以提升面试官的第一印象。第二栏应该就是列举出你会使用的技术,这个很重要,列举时按照熟练程度依次往下列举,掌握最成熟的放在最前面,不会使用的千万不要去写,如果被问到但没掌握那直接就被挂掉了。列举的时候最好将关键字加粗加黑放大,让人一看便知你所掌握的技术,具体到某一个你所应聘公司所需要的技术,那么他可能就会考核你。第三栏就是你在学校所做过的项目(这个必须有,也能决定你是否会进入面试环节),项目中使用的关键技术一定要突出说明。而且尤其要注意,一般写项目不要太多,最好是两个或者是三个,最好有一个你自己独立去完成的项目(该项目不是老师带着你去做的)。第四栏就是你所在学校参加的校园活动或者你的实习经历(如果是国企,最好写多一点,否则拣最重要的三四条写)。第五栏就是个人评价,主要描述一下你的团队精神,学习能力,敬业精神即可,阐述个三四行左右即可,关于个人喜好方面的只需点到即可。 我的建议 从现在开始,每天练习一道关于C语言字符串操作的编程题目(比如自己可以实现一下C语言字符串的库函数),每隔一天练习一道排序算法题目(注意使用多种方法,包括递归和非递归),每隔两天练习SQL查询语句。其余的计划根据个人的安排而执行,题目自己从网上找。第二篇:笔试面试
第三篇:数据结构总结[推荐]
第四篇:Linux笔试面试知识点总结
第五篇:C和LINUX笔试面试总结