必胜高考网_全国高考备考和志愿填报信息平台

必勝高考網 > 計算機類 > 計算機等級 > 資訊 >

計算機三級《數據庫技術》背誦資料:數據結構算法

時間: 家輝2 資訊

  順序存儲計算公式 Li=L0+(i-1)×K 順序結構可以進行隨機存取;插人、刪除運算會引起相應節點的大量移動

  鏈式存儲結構:a、指針域可以有多個,可以指向空,比比順序存儲結構的存儲密度小

  b、邏輯上相鄰的節點物理上不一定相鄰。 c、插人、刪除等不需要大量移動節點

  4、順序表:一般情況下,若長度為n的順序表,在任何位置插入或刪除的概率相等,元素移動的平均次數為n/2(插入)和(n-1)/2(刪除)。

  5、鏈表:線性鏈表(單鏈表和雙向鏈表等等)和非線性鏈表

  線性鏈表也稱為單鏈表,其每個一節點中只包含一個指針域,雙鏈表中,每個節點中設置有兩個指針域。(注意結點的插入和刪除操作)

  6、棧:“后進先出”(LIFO)表。棧的應用:表達式求解、二叉樹對稱序周游、快速排序算法、遞歸過程的實現等

  7、隊列:“先進先出”線性表。應用:樹的層次遍歷

  8、串:由零個或多個字符組成的有限序列。

  9、多維數組的順序存儲:

  10、稀疏矩陣的存儲:下三角矩陣順序存儲

  其他常見的存儲方法還有三元組法和十字鏈表法

  11、廣義表:由零個或多個單元素或子表所組成的有限序列。廣義表的元素可以是子表,而子表的元素還可以是子表

  12、樹型結構:非線性結構。常用的樹型結構有樹和二叉樹。

  二叉樹與樹的區別:二叉樹不是樹的特殊情況,樹和二叉樹之間最主要的區別是:二叉樹的節點的子樹要區分左子樹和右子樹,即使在節點只有一棵子樹的情況下也要明確指出該子樹是左子樹還是右子樹。

  13、樹(森林)與二叉樹之間的轉換(要會轉換)

  14、二叉樹和樹的周游(遍歷)

  二叉樹的周游主要有以下3種方式:前序法(NLR)、對稱序法(LNR)、后序法(LRN)

  周游樹和樹林:深度優先和按廣度優先兩種方式進行。深度優先方式又可分為按先根次序和按后根次序周游

  樹與二叉樹周游之間的對應關系:按先根次序周游樹正好與按前序法周游樹對應的二叉樹等同,后根次序周游樹正好與按對稱序法周游對應的二叉樹等同

  按廣度優先方式就是層次次序周游

  15、二叉樹的存儲和線索

  二叉樹的存儲結構:二叉樹的llink一rlink法存儲表示

  線索二叉樹:在有n個節點的二叉樹的且llink - rlink法存儲表示中,必定有n+1個空指針域

  16、哈夫曼樹:一類帶權路徑長度最短的樹。樹的帶權路徑長度為樹中所有葉子節點的帶權路徑長度之和WPL。

  17、查找:

  (1)順序查找:平均查找長度為(n +1 )/2次,時間復雜度為O(n)

  (2)二分法查找:線性表節點必須按關鍵碼值排序,且線性表是以順序存儲方式存儲的。查找成功比較次數log2n,查找失敗比較次數log2n+1

  (3)分塊查找:先是塊間查找,然后塊內查找。

  (4)散列表(哈希表Hash)的存儲和查找:處理沖突的方法:開地址法(線性探測法)、拉鏈法等

  負載因子(裝填因子)=表實際存儲的結點個數/表的最大能存儲結點個數(即表長)

  二叉排序樹:每個結點左子樹的所有關鍵碼值都小于該結點關鍵碼值,右子樹所有結點關鍵碼值都大于該結點關鍵碼值。對稱周游二叉排序樹,得到一個有序序列,時間復雜度O(log2n)

  B樹和B+樹:M階樹,每個結點至多有M-1個關鍵碼,至少有M/2(取上界)-1個關鍵碼。B樹適合隨機查找,不適合順序查找。B+樹適合順序查找。

  18、排序

  直接插人排序、希爾排序、直接選擇排序、堆排序、起泡排序、快速排序等排序算法要了解。

  直接選擇排序、希爾排序、快速排序和堆排序是不穩定排序,其他排序為穩定排序

56242 主站蜘蛛池模板: 中国玩具展_玩具展|幼教用品展|幼教展|幼教装备展 | 杭州网络公司_百度SEO优化-外贸网络推广_抖音小程序开发-杭州乐软科技有限公司 | 生产加气砖设备厂家很多,杜甫机械加气砖设备价格公道 | 流量卡中心-流量卡套餐查询系统_移动电信联通流量卡套餐大全 | 月嫂_保姆_育婴_催乳_母婴护理_产后康复_养老护理-吉祥到家家政 硫酸亚铁-聚合硫酸铁-除氟除磷剂-复合碳源-污水处理药剂厂家—长隆科技 | 电缆接头_防水接头_电缆防水接头 - 乐清市新豪电气有限公司 | 2025第九届世界无人机大会| 凝胶成像仪,化学发光凝胶成像系统,凝胶成像分析系统-上海培清科技有限公司 | 电气控制系统集成商-PLC控制柜变频控制柜-非标自动化定制-电气控制柜成套-NIDEC CT变频器-威肯自动化控制 | 钢化玻璃膜|手机钢化膜|钢化膜厂家|手机保护膜-【东莞市大象电子科技有限公司】 | 珠海冷却塔降噪维修_冷却塔改造报价_凉水塔风机维修厂家- 广东康明节能空调有限公司 | 京港视通报道-质量走进大江南北-京港视通传媒[北京]有限公司 | 振动台-振动试验台-振动冲击台-广东剑乔试验设备有限公司 | 超声骨密度仪-动脉硬化检测仪器-人体成分分析仪厂家/品牌/价格_南京科力悦 | 中高频感应加热设备|高频淬火设备|超音频感应加热电源|不锈钢管光亮退火机|真空管烤消设备 - 郑州蓝硕工业炉设备有限公司 | 聚丙烯酰胺PAM-聚合氯化铝PAC-絮凝剂-河南博旭环保科技有限公司 巨野电机维修-水泵维修-巨野县飞宇机电维修有限公司 | 深圳办公室装修-写字楼装修设计-深圳标榜装饰公司 | 除甲醛公司-甲醛检测-广西雅居环境科技有限公司 | 步进_伺服_行星减速机,微型直流电机,大功率直流电机-淄博冠意传动机械 | 外贸网站建设-外贸网站设计制作开发公司-外贸独立站建设【企术】 | 二手Sciex液质联用仪-岛津气质联用仪-二手安捷伦气质联用仪-上海隐智科学仪器有限公司 | 济南拼接屏_山东液晶拼接屏_济南LED显示屏—维康国际官网 | 微量水分测定仪_厂家_卡尔费休微量水分测定仪-淄博库仑 | 生产自动包装秤_颗粒包装秤_肥料包装秤等包装机械-郑州鑫晟重工科技有限公司 | 液氮罐_液氮容器_自增压液氮罐_杜瓦瓶_班德液氮罐厂家 | 工业机械三维动画制作 环保设备原理三维演示动画 自动化装配产线三维动画制作公司-南京燃动数字 聚合氯化铝_喷雾聚氯化铝_聚合氯化铝铁厂家_郑州亿升化工有限公司 | 深圳宣传片制作-企业宣传视频制作-产品视频拍摄-产品动画制作-短视频拍摄制作公司 | 自动气象站_气象站监测设备_全自动气象站设备_雨量监测站-山东风途物联网 | 右手官网|右手工业设计|外观设计公司|工业设计公司|产品创新设计|医疗产品结构设计|EMC产品结构设计 | 经济师考试_2025中级经济师报名时间_报名入口_考试时间_华课网校经济师培训网站 | 哔咔漫画网页版在线_下载入口访问指引| 光伏支架成型设备-光伏钢边框设备-光伏设备厂家 | 煤棒机_增碳剂颗粒机_活性炭颗粒机_木炭粉成型机-巩义市老城振华机械厂 | 北京西风东韵品牌与包装设计公司,创造视觉销售力! | 扬尘监测_扬尘监测系统_带证扬尘监测设备 - 郑州港迪科技有限公司 | 常州翔天实验仪器厂-恒温振荡器-台式恒温振荡器-微量血液离心机 恒温恒湿箱(药品/保健品/食品/半导体/细菌)-兰贝石(北京)科技有限公司 | 百度网站优化,关键词排名,SEO优化-搜索引擎营销推广 | 碳钢法兰厂家,非标法兰,定制异型,法兰生产厂家-河北九瑞管道 | 工业风机_环保空调_冷风机_工厂车间厂房通风降温设备旺成服务平台 | 执业药师报名时间,报考条件,考试时间-首页入口 | 风信子发稿-专注为企业提供全球新闻稿发布服务 |