20:I[282628,["/_next/static/chunks/008crbu1wvww1.js","/_next/static/chunks/0xv-p7xxdjggv.js","/_next/static/chunks/2rkbnaa60chl0.js","/_next/static/chunks/34nljeldfxvso.js","/_next/static/chunks/3s-91zfhxfz_i.js","/_next/static/chunks/2euoam2_hqd-3.js","/_next/static/chunks/15ht1na675f92.js","/_next/static/chunks/0a42hv2eax_wy.js","/_next/static/chunks/37u8i-n86sk1y.js","/_next/static/chunks/1v5gem7vh1mpz.js","/_next/static/chunks/34t_zvjz0u54e.js","/_next/static/chunks/3w1a7ko-uze7n.js","/_next/static/chunks/2szcdqofrz1rc.js","/_next/static/chunks/3h_1a4ylwg9l-.js"],"Category"] 21:I[332505,["/_next/static/chunks/008crbu1wvww1.js","/_next/static/chunks/0xv-p7xxdjggv.js","/_next/static/chunks/2rkbnaa60chl0.js","/_next/static/chunks/34nljeldfxvso.js","/_next/static/chunks/3s-91zfhxfz_i.js","/_next/static/chunks/2euoam2_hqd-3.js","/_next/static/chunks/15ht1na675f92.js","/_next/static/chunks/0a42hv2eax_wy.js","/_next/static/chunks/37u8i-n86sk1y.js","/_next/static/chunks/1v5gem7vh1mpz.js","/_next/static/chunks/34t_zvjz0u54e.js","/_next/static/chunks/3w1a7ko-uze7n.js","/_next/static/chunks/2szcdqofrz1rc.js","/_next/static/chunks/3h_1a4ylwg9l-.js"],"BackButton"] 22:I[388078,["/_next/static/chunks/008crbu1wvww1.js","/_next/static/chunks/0xv-p7xxdjggv.js","/_next/static/chunks/2rkbnaa60chl0.js","/_next/static/chunks/34nljeldfxvso.js","/_next/static/chunks/3s-91zfhxfz_i.js","/_next/static/chunks/2euoam2_hqd-3.js","/_next/static/chunks/15ht1na675f92.js","/_next/static/chunks/0a42hv2eax_wy.js","/_next/static/chunks/37u8i-n86sk1y.js","/_next/static/chunks/1v5gem7vh1mpz.js","/_next/static/chunks/34t_zvjz0u54e.js","/_next/static/chunks/3w1a7ko-uze7n.js","/_next/static/chunks/2szcdqofrz1rc.js","/_next/static/chunks/3h_1a4ylwg9l-.js"],"ActionButton"] :HL["/favicon.svg","image"] :HL["https://images.pexels.com/photos/3766978/pexels-photo-3766978.jpeg?auto=compress&cs=tinysrgb&h=650&w=940","image"] 1d:["$","footer",null,{"className":"group relative bg-muted-50 dark:bg-muted-800 text-muted-600 body-font overflow-hidden","children":[["$","div",null,{"className":"relative w-full max-w-7xl px-5 py-24 mx-auto ","children":["$","div",null,{"className":"flex flex-col ptablet:flex-row ltablet:flex-row lg:flex-row gap-6 ptablet:gap-0 ltablet:gap-0 lg:gap-0 flex-wrap md:text-left text-center -mb-10 -mx-4","children":[["$","div",null,{"className":"w-full ptablet:w-1/2 ltablet:w-1/4 lg:w-1/4 flex-shrink-0 md:mx-0 mx-auto text-center md:text-left px-4","children":[["$","a",null,{"className":"flex flex-col md:flex-row gap-3 title-font font-medium items-center md:justify-start justify-center text-muted-800 dark:text-white","children":[["$","img",null,{"className":"h-12","src":"/favicon.svg","alt":"dors logo","width":"48","height":"48"}],["$","span",null,{"className":"font-heading font-bold text-2xl","children":"Dors"}]]}],["$","p",null,{"className":"font-sans text-sm w-full max-w-xs mx-auto md:max-w-[220px] md:mx-0 mt-2 text-muted-500 dark:text-muted-400","children":"Dors 是花野猫开发为知识工作者打造的数字花园应用，包含的博客、个人记事本、及其他实用功能。"}]]}],[["$","div","garden",{"className":"w-full ptablet:w-1/2 ltablet:w-1/4 lg:w-1/4 px-4","children":[["$","h2",null,{"className":"font-heading font-semibold text-muted-800 dark:text-white tracking-widest text-sm mb-3","children":"花园"}],["$","ul",null,{"className":"font-sans list-none space-y-2 mb-10","children":[["$","li","posts",{"children":["$","a",null,{"href":"/posts","className":"text-muted-600 dark:text-muted-400 hover:text-primary-500 dark:hover:text-primary-500","children":"花坛——博客"}]}],["$","li","books",{"children":["$","a",null,{"href":"/books","className":"text-muted-600 dark:text-muted-400 hover:text-primary-500 dark:hover:text-primary-500","children":"果园——知识库"}]}]]}]]}],["$","div","workshop",{"className":"w-full ptablet:w-1/2 ltablet:w-1/4 lg:w-1/4 px-4","children":[["$","h2",null,{"className":"font-heading font-semibold text-muted-800 dark:text-white tracking-widest text-sm mb-3","children":"工坊——作者开发的实用工具"}],["$","ul",null,{"className":"font-sans list-none space-y-2 mb-10","children":[["$","li","notes",{"children":["$","a",null,{"href":"/notes","className":"text-muted-600 dark:text-muted-400 hover:text-primary-500 dark:hover:text-primary-500","children":"小记"}]}],["$","li","split-v",{"children":["$","a",null,{"href":"https://split-v.utities.online/","className":"text-muted-600 dark:text-muted-400 hover:text-primary-500 dark:hover:text-primary-500","target":"_blank","rel":"noopener noreferrer","children":"秒切——一键按秒分割视频"}]}],["$","li","uni",{"children":["$","a",null,{"href":"https://uni.utities.online/","className":"text-muted-600 dark:text-muted-400 hover:text-primary-500 dark:hover:text-primary-500","target":"_blank","rel":"noopener noreferrer","children":"中国重点高校地理位置可视化网站"}]}],["$","li","aparecium",{"children":["$","a",null,{"href":"https://aparecium.huayemao.run/","className":"text-muted-600 dark:text-muted-400 hover:text-primary-500 dark:hover:text-primary-500","target":"_blank","rel":"noopener noreferrer","children":"中国行政区划数据查询平台"}]}],["$","li","excel-renamer",{"children":["$","a",null,{"href":"/excel-renamer","className":"text-muted-600 dark:text-muted-400 hover:text-primary-500 dark:hover:text-primary-500","children":"excel 重命名工具"}]}]]}]]}],["$","div","misc",{"className":"w-full ptablet:w-1/2 ltablet:w-1/4 lg:w-1/4 px-4","children":[["$","h2",null,{"className":"font-heading font-semibold text-muted-800 dark:text-white tracking-widest text-sm mb-3","children":"misc"}],["$","ul",null,{"className":"font-sans list-none space-y-2 mb-10","children":[["$","li","rules",{"children":["$","a",null,{"href":"/rules-to-save-my-life","className":"text-muted-600 dark:text-muted-400 hover:text-primary-500 dark:hover:text-primary-500","children":"生活章程"}]}],["$","li","aigc",{"children":["$","a",null,{"href":"/aigc","className":"text-muted-600 dark:text-muted-400 hover:text-primary-500 dark:hover:text-primary-500","children":"画廊"}]}],"$L1e"]}]]}]]]}]}],"$L1f"]}] 23:T1385,在 [HTML Standard](https://html.spec.whatwg.org/multipage/indices.html#elements-3) 中，选中第一个表格元素，运行脚本 ```js [...document.querySelectorAll('[id^="elements-3:the-"][id$="-element"]')].map(e=>e.textContent) ``` 得到的数组 ```js [ "a", "abbr", "address", "article", "area", "aside", "audio", "source", "track", "b", "base", "head", "bdi", "bdo", "blockquote", "body", "html", "br", "button", "canvas", "caption", "table", "cite", "code", "col", "colgroup", "template", "data", "datalist", "option", "dd", "dt", "dl", "div", "del", "details", "summary", "dfn", "dialog", "em", "embed", "fieldset", "legend", "figcaption", "figure", "footer", "form", "header", "hgroup", "hr", "i", "iframe", "img", "picture", "input", "ins", "kbd", "label", "li", "ol", "ul", "menu", "link", "noscript", "main", "map", "mark", "meta", "meter", "nav", "object", "optgroup", "select", "output", "p", "pre", "progress", "q", "rp", "ruby", "rt", "s", "samp", "script", "search", "section", "slot", "small", "video", "span", "strong", "style", "thead", "tbody", "tfoot", "tr", "td", "textarea", "th", "time", "title", "u", "var", "wbr" ] ``` ## 应用消除所有不合法标签 function removeAttributesAndNormalizeTags(html) { // 创建一个临时div元素 var tempDiv = document.createElement("div"); tempDiv.innerHTML = html; removeNonNativeTags(tempDiv); // 获取所有元素 var elements = tempDiv.querySelectorAll("*"); // 移除所有元素的class和id属性 for (var i = 0; i < elements.length; i++) { elements[i].removeAttribute("class"); elements[i].removeAttribute("id"); for (const key in elements[i].dataset) { delete elements[i].dataset[key]; } } // 标准化标签名 for (var i = 0; i < elements.length; i++) { var tagName = elements[i].tagName.toLowerCase(); elements[i].tagName = tagName; } // 返回处理后的HTML return tempDiv.innerHTML; } function removeNonNativeTags(div) { const nativeTagnames = [ "a", "abbr", "address", "article", "area", "aside", "audio", "source", "track", "b", "base", "head", "bdi", "bdo", "blockquote", "body", "html", "br", "button", "canvas", "caption", "table", "cite", "code", "col", "colgroup", "template", "data", "datalist", "option", "dd", "dt", "dl", "div", "del", "details", "summary", "dfn", "dialog", "em", "embed", "fieldset", "legend", "figcaption", "figure", "footer", "form", "header", "hgroup", "hr", "i", "iframe", "img", "picture", "input", "ins", "kbd", "label", "li", "ol", "ul", "menu", "link", "noscript", "main", "map", "mark", "meta", "meter", "nav", "object", "optgroup", "select", "output", "p", "pre", "progress", "q", "rp", "ruby", "rt", "s", "samp", "script", "search", "section", "slot", "small", "video", "span", "strong", "style", "thead", "tbody", "tfoot", "tr", "td", "textarea", "th", "time", "title", "u", "var", "wbr", ]; const elements = div.querySelectorAll("*"); elements.forEach((element) => { if (!element.parentNode) { return; } if (!nativeTagnames.includes(element.tagName.toLowerCase())) { element.outerHTML = element.innerHTML; } element.querySelectorAll("*").forEach((e) => { removeNonNativeTags(e); }); }); } const res = removeAttributesAndNormalizeTags( document.body.firstElementChild.outerHTML ); `}/> 24:T5276, ## 2011年 **【2011年题44】**（12 分）某计算机存储器按字节编址，虚拟（逻辑）地址空间大小为 16MB，主存（物理）地址空间大小为 1MB，页面大小为 4KB；Cache 采用直接映射方式，共 8 行；主存与 Cache 之间交换的块大小为 32B。系统运行到某一时刻时，页表的部分内容和 Cache 的部分内容分别如题 44-a 图、题 44-b 图所示，图中页框号及标记字段的内容为十六进制形式。

请回答下列问题。（1）虚拟地址共有几位，哪几位表示虚页号？物理地址共有几位，哪几位表示页框号（物理页号）？（2）使用物理地址访问 Cache 时，物理地址应划分成哪几个字段？要求说明每个字段的位数及在物理地址中的位置。（3）虚拟地址 001C60H 所在的页面是否在主存中？若在主存中，则该虚拟地址对应的物理地址是什么？访问该地址时是否 Cache 命中？要求说明理由。（4）假定为该机配置一个四路组相联的 TLB 共可存放 8 个页表项，若其当前内容（十六进制）如题 44-c 图所示，则此时虚拟地址 024BACH 所在的页面是否存在主存中？要求说明理由。

**解析：** 1）存储器按字节编址，虚拟地址空间大小为 16MB = 224B，故虚拟地址为 24 位；页面大小为 4KB = 212B，故高 12 位为虚页号。主存地址空间大小为 1MB = 220B，故物理地址为 20 位；由于页内地址为 12 位，故高 8 位为页框号。 2）由于 Cache 采用直接映射方式，所以物理地址各字段的划分如下：

由于块大小为 32B，故字块内地址占 5 位；Cache 共 8 行，故 Cache 字块标记占 3 位；主存字块标记占 20-5-3=12 位。 3）虚拟地址 001C60H 的前 12 位为虚页号，即 001H，查看 001H 处的页表项，其对应的有效位为 1，故虚拟地址 001C60H 所在的页面在主存中。页表 001H 处的页框号为 04H，与页内偏移（虚拟地址后 12 位）拼接成物理地址为 04C60H。物理地址 04C60H = 0000 0100 1100 0110 0000B，主存块只能映射到 Cache 的第 3 行（即第 011B 行），由于该行的有效位 = 1，标记（值为 105H）≠ 04CH（物理地址高 12 位），故不命中。 4）由于 TLB 采用四路组相联，故 TLB 被分为 8/4 = 2 个组，因此虚页号中高 11 位为 TLB 标记、最低 1 位为 TLB 组号。虚拟地址 024BACH = 0000 0010 0100 1011 1010 1100B，虚页号为 0000 0010 0100B，TLB 标记为 0000 0010 010B（即 012H），TLB 组号为 0B，因此，该虚拟地址所对应物理页面只可能映射到 TLB 的第 0 组。组 0 中存在有效位 = 1、标记 = 012H 的项，因此访问 TLB 命中，即虚拟地址 024BACH 所在的页面在主存中。 --- ## 2013年 **【2013年题43】**（9分）某 32 位计算机，CPU 主频为 800MHz，Cache 命中时的 CPI 为 4，Cache 块大小为 32 字节；主存采用 8 体交叉存储方式，每个体的存储字长为 32 位、存储周期为 40ns；存储器总线宽度为 32 位，总线时钟频率为 200MHz，支持突发传送总线事务。每次读突发传送总线事务的过程包括：送首地址和命令、存储器准备数据、传送数据。每次突发传送 32 字节，传送地址或 32 位数据均需要一个总线时钟周期。请回答下列问题，要求给出理由或计算过程。（1）CPU 和总线的时钟周期各为多少？总线的带宽（即最大数据传输率）为多少？（2）Cache 缺失时，需要用几个读突发传送总线事务来完成一个主存块的读取？（3）存储器总线完成一次读突发传送总线事务所需的时间是多少？（4）若程序 BP 执行过程中，共执行了 100 条指令，平均每条指令需进行 1.2 次访存，Cache 缺失率为 5%，不考虑替换等开销，则 BP 的 CPU 执行时间是多少？ **解析：** 1）CPU 的时钟周期是主频的倒数，即 1/800MHz = 1.25ns。总线的时钟周期是总线频率的倒数，即 1/200MHz = 5ns。总线宽度为 32 位，故总线带宽为 4B×200MHz = 800MB/s 或 4B/5ns = 800MB/s。 2）Cache 块大小是 32B，因此 Cache 缺失时需要一个读突发传送总线事务读取一个主存块。 3）一次读突发传送总线事务包括一次地址传送和 32B 数据传送：用 1 个总线时钟周期传输地址；每隔 40ns/8 = 5ns 启动一个体工作（各进行 1 次存取），第一个体读数据花费 40ns，之后数据存取与数据传输重叠；用 8 个总线时钟周期传输数据。读突发传送总线事务时间：5ns + 40ns + 8×5ns = 85ns。 4）BP 的 CPU 执行时间包括 Cache 命中时的指令执行时间和 Cache 缺失时带来的额外开销。命中时的指令执行时间：100×4× 1.25ns = 500ns。指令执行过程中 Cache 缺失时的额外开销：1.2×100×5%×85ns = 510ns。BP 的 CPU 执行时间：500ns + 510ns = 1010ns。 ## 2014年【2014年题45】假设对于 44 题中的计算机 M 和程序 P 的机器代码，M 采用页式虚拟存储管理；P 开始执行时，(R1) = (R2) = 0，(R6) = 1000，其机器代码已调入主存但不在 Cache 中；数组 A 未调入主存，且所有数组元素在同一页，并存储在磁盘同一个扇区。请回答下列问题并说明理由。 1）P 执行结束时，R2 的内容是多少？ 2）M 的指令 Cache 和数据 Cache 分离。若指令 Cache 共有 16 行，Cache 和主存交换的块大小为 32 字节，则其数据区的容量是多少？若仅考虑程序段 P 的执行，则指令 Cache 的命中率为多少？ 3）P 在执行过程中，哪条指令的执行可能发生溢出异常？哪条指令的执行可能产生缺页异常？对于数组 A 的访问，需要读磁盘和 TLB 至少各多少次？ **解析：** 1）R2 里装的是 $i$ 的值，循环条件是 $i < N$（1000），即当 $i$ 自增到不满足这个条件时跳出循环，程序结束，所以此时 $i$ 的值为 1000。（1 分） 2）Cache 共有 16 块，每块 32 字节，所以 Cache 数据区的容量为 16×32B = 512B。（1 分） P 共有 6 条指令，占 24 字节，小于主存块大小（32B），其起始地址为 0804 8100H，对应一块的开始位置，由此可知所有指令都在一个主存块内。读取第一条指令时会发生 Cache 缺失，故将 P 所在的主存块调入 Cache 某一快，以后每次读取指令时，都能在指令 Cache 中命中。因此在 1000 次循环中，只会发生 1 次指令访问缺失，所以指令 Cache 的命中率为 (1000×6-1)/(1000×6) = 99.98%。（2 分） ## 心得笔记 1. 看页表，页号是最左边数组下标，不要把页框号当成页号。页框号代表的是物理块号。 1. 2013年多体交叉数据传输 1. 2014年题 1. 命中率还要考虑循环次数，因为每个循环也要访存取指。 1. 缺页异常要访存的指令才发生，其他指令都是直接取的寄存器中的数据。 ## 4.5.6 地址映射地址映射是指将主存地址空间映射到 cache 的地址空间，即把存放在主存中的程序或数据块载入 cache 块的规则，主要有以下 3 种方法。 1. **全相联（Full Associative Mapping）**：各主存块都可以映射到 cache 的任意数据块。 2. **直接相联（Direct Mapping）**：各主存块只能映射到 cache 中的固定块。 3. **组相联（Set Associative Mapping）**：各主存块只能映射到 cache 固定组中的任意块。 ### 1. 全相联映射 #### （1）全相联映射基本原理全相联映射方式下，主存中的每一个数据块都可以放置到 cache 的任意一个数据块中，是一对多的映射关系。新的主存数据块可以载入 cache 中任何一个空位置，只有 cache 满时才需要进行数据块置换。全相联映射时 cache 利用率最高，但查找成本较高，需要 CAM 提供快速的查找功能。全相联映射逻辑示意如图 4.36 所示。不考虑脏数据位和淘汰计数，cache 的实际容量为 $n \times (1 + s + 8 \times 2^w)$ 位。数据查找时直接将主存块地址和所有 cache 行中的标记字段主存块地址进行并发比较，如果读命中，则输出对应 cache 行数据块副本中块内地址 offset 处的数据；如果写命中，则需要写入数据，同时将脏数据标志位置为 1。由于主存块可以放置在 cache 的任意块中，为了方便后续查找，主存数据块载入时还需要记录若干的标记标志信息，主要包括有效位、主存块地址标记、脏数据标志位、淘汰计数等信息。通常将一个 cache 数据块和相关的标记标志信息一起称为一个 **cache 行/槽（Line/Slot）**，因此 cache 有多少个数据块就对应有多少个 cache 行。主存地址划分为主存块地址（tag）和块内偏移（offset）两部分，两部分字段长度分别为 $s$、$w$。由图可知，cache 块大小 = $2^w$ 字节，cache 副本缓冲区容量 = $n \times 2^w$ 字节，主存容量 = $2^{s+w}$ 字节。 --- ![全相联映射逻辑示意图](/api/files/15d74eb5adb209a0.svg) ![直接相联映射逻辑示意图](/api/files/86be01632bbd4627.svg) ![组相联映射逻辑示意图](/api/files/0554afb9e407be61.svg)25:T7cec,## 2009年 **【2009年题7】** 下列关于无向连通图特性的叙述中，正确的是______。 I. 所有顶点的度之和为偶数 II. 边数大于顶点个数减 1 III. 至少有一个顶点的度为 1 A. 只有 I B. 只有 II C. I 和 II D. I 和 III **解析：** 每条边都连接了两个结点，在计算顶点的度之和时每条边都被计算了两次（出度和入度），故所有顶点的度之和为边数的两倍，I 正确。$n$ 个顶点、$n-1$ 条边可以构成无向连通图，比如树，II 错误。顶点数为 $N$（$N \geqslant 1$）的无向完全图中不存在度为 1 的顶点，III 错误。 --- ## 2010年 **【2010年题7】** 若无向图 G = (V, E) 中含有 7 个顶点，要保证图 G 在任何情况下都是连通的，则需要的边数最少是______。 A. 6 B. 15 C. 16 D. 21 **解析：** 要保证无向图 G 在任何情况下都是连通的，即任意变动图 G 中的边，G 始终保持连通。首先考虑极限不连通情况：6 个顶点构成完全连通子图 G1，需 $n(n-1)/2 = 6\times(6-1)/2 = 15$ 条边，此时第 7 个顶点为孤立点；然后再添加一条边将第 7 个节点与 G1 连接起来，图必连通，共需 16 条边。故选 C。 --- **【2010年题8】** 对右图进行拓扑排序，可以得到不同的拓扑序列的个数是______。 A. 4 B. 3 C. 2 D. 1

**解析：** 拓扑排序的过程如下： 1. 入度为 0 的顶点只有 a，首先输出 a。 2. 去掉 a 后，入度为 0 的顶点有 b 和 e： * 若先输出 e，剩下的入度为 0 的顶点只有 b，输出 b；随后只能依次输出 c、d，得到序列：**aebcd**。 * 若先输出 b，入度为 0 的顶点有 c 和 e： * 选择输出 e，随后依次输出 c、d，得到序列：**abecd**； * 选择输出 c，随后依次输出 e、d，得到序列：**abced**。

综上所述，可以得到 3 个不同的拓扑序列，分别为 aebcd、abecd、abced。故选 B。 ## 2011年 **【2011年题8】** 下列关于图的叙述中，正确的是________。 I. 回路是简单路径 II. 存储稀疏图，用邻接矩阵比邻接表更省空间 III. 若有向图中存在拓扑序列，则该图不存在回路 A. 仅 II B. 仅 I、II C. 仅 III D. 仅 I、III **解析：** 第一个顶点和最后一个顶点相同的路径称为回路；序列中顶点不重复出现的路径称为简单路径；回路显然不是简单路径，故 I 错误；稀疏图是边比较少的情况，此时用邻接矩阵的空间复杂度为 $O(n^2)$，必将浪费大量的空间，而邻接表的空间复杂度为 $O(n+e)$，应该选用邻接表，故 II 错误。存在回路的有向图不存在拓扑序列，若拓扑排序输出结束后所余下的顶点都有前驱，则说明只得到了部分顶点的拓扑有序序列，图中存在回路，故 III 正确。 ## 2012年 **【2012年题5】** 对有 $n$ 个结点、$e$ 条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是________。 A. O(n) B. O(e) C. O(n + e) D. O(ne) **解析：** 广度优先遍历需要借助队列实现。邻接表的结构包括：顶点表；边表（有向图为出边表）。当采用邻接表存储方式时，在对图进行广度优先遍历时每个顶点均需入队一次（顶点表遍历），故时间复杂度为 O(n)，在搜索所有顶点的邻接点的过程中，每条边至少访问一次（出边表遍历），故时间复杂度为 O(e)，算法总的时间复杂度为 O(n + e)。 --- **【2012年题6】** 若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是________。 A. 存在，且唯一 B. 存在，且不唯一 C. 存在，可能不唯一 D. 无法确定是否存在 **解析：** 对角线以下元素均为零，表明只有顶点 $i$ 到顶点 $j\ (i A. d, e, f B. e, d, f C. f, d, e D. f, e, d **解析：** 从 a 到各顶点的最短路径的求解过程：

后续目标顶点依次为 f, d, e。【排除法】对于 A，若下一个顶点为 d，路径 a, b, d 的长度 5，而 a, b, c, f 的长度仅为 4，显然错误。同理可以排除 B。将 f 加入集合 S 后，采用上述的方法也可以排除 D。 --- **【2012年题8】** 下列关于最小生成树的叙述中，正确的是________。 I. 最小生成树的代价唯一 II. 所有权值最小的边一定会出现在所有的最小生成树中 III. 使用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定相同 IV. 使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相同 A. 仅 I B. 仅 II C. 仅 I、III D. 仅 II、IV **解析：** 对于 I，最小生成树的树形可能不唯一（这是因为可能存在权值相同的边），但是代价一定是唯一的，I 正确。对于 II，如果权值最小的边有多条并且构成环状，则总有权值最小的边将不出现在某棵最小生成树中，II 错误。对于 III，设 $N$ 个结点构成环，$N - 1$ 条边权值相等，则从不同的顶点开始普里姆算法会得到 $N - 1$ 中不同的最小生成树，III 错误。对于 IV，当最小生成树唯一时（各边的权值不同），Prim 算法和 Kruskal 算法得到的最小生成树相同，IV 错误。 --- ## 2013年【2013年题7】设图的邻接矩阵 $A$ 如下所示。各顶点的度依次是________。 $$A = \begin{bmatrix} 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix}$$ A. 1, 2, 1, 2 B. 2, 2, 1, 1 C. 3, 4, 2, 3 D. 4, 4, 2, 2 解析：邻接矩阵 A 为非对称矩阵，说明图是有向图，度为入度加出度之和。各顶点的度是矩阵中此结点对应的行（对应出度）和列（对应入度）的非零元素之和。【2013年题8】若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是________。 A. h, c, a, b, d, e, g, f B. e, a, f, g, b, h, c, d C. d, b, c, a, h, e, f, g D. a, b, c, d, h, e, f, g

解析：此题为送分题。只要掌握 DFS 和 BFS 的遍历过程，便能轻易解决。逐个代入，手工模拟，选项 D 是深度优先遍历，而不是广度优先遍历。【2013年题9】下列 AOE 网表示一项包含 8 个活动的工程。通过同时加快若干活动的进度可以缩短整个工程的工期。下列选项中，加快其进度就可以缩短工程工期的是________。

A. c 和 e B. d 和 c C. f 和 d D. f 和 h 解析：找出 AOE 网的全部关键路径为(b, d, c, g)、(b, d, e, h)和(b, f, h)。根据定义，只有关键路径上的活动时间同时减少时，才能缩短工期，即正确选项中的两条路径必须涵盖在所有关键路径之中。利用关键路径算法可求出图中的关键路径共有三条：(b, d, c, g)、(b, d, e, h)和(b, f, h)。由此可知，选项 A 和 B 中并不能包含(b, f, h)这条路径，选项 C 中，并不能包含(b, d, c, g)和(b, d, e, h)这两条路径，只有 C 包含了所有的关键路径，因此只有加快 f 和 d 的进度才能缩短工期 ## 2014年 **【2014年题7】** 对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是________。

A. 3, 1, 2, 4, 5, 6 B. 3, 1, 2, 4, 6, 5 C. 3, 1, 4, 2, 5, 6 D. 3, 1, 4, 2, 6, 5 **解析：** 按照拓扑排序的算法，每次都选择入度为 0 的结点从图中删去，此图中一开始只有结点 3 的入度为 0；删掉结点 3 后，只有结点 1 的入度为 0；删掉结点 1 后，只有结点 4 的入度为 0；删掉结点 4 后，结点 2 和结点 6 的入度都为 0，此时选择删去不同的结点，会得出不同的拓扑序列，分别处理完毕后可知可能的拓扑序列为 3, 1, 4, 2, 6, 5 和 3, 1, 4, 6, 2, 5，选 D。 ## 2017 **【2017年题7】** 已知无向图 G 含有 16 条边，其中度为 4 的顶点个数为 3，度为 3 的顶点个数为 4，其他顶点的度均小于 3。图 G 所含的顶点个数至少是______。 A. 10 B. 11 C. 13 D. 15 **解析：** 无向图边数的两倍等于各顶点度数的总和。由于其他顶点的度均小于 3，可以设它们的度都为 2，设它们的数量是 $x$，可列出方程 $4 \times 3 + 3 \times 4 + 2x = 16 \times 2$，解得 $x = 3$。$4 + 3 + 3 = 11$，B 正确。 --- ## 心得笔记 1. 09年连通图的相关概念经常搞忘记掉。一个图有两个不相连的部分，不是连通图 1. 度数和边数的关系没掌握。 1. 邻接矩阵：每行代表一个顶点与其它各个顶点邻接的情况。不对称的邻接矩阵一定是有向图 1. 邻接表：^ 表示空指针 NULL，链表结点之间没有边。 1. 邻接表用链表有毛用！就应该用动态数组。。。看得烦得很 1. 邻接表的边结点到底是啥 1. 完全图的边数搞不清楚 1. 图的广度优先的时间复杂度搞不清楚 1. 图的 BFS：出队一个元素，访问其邻接点并入队，再将队头元素出队，循环往复。 1. 存在连通图的情况：外侧循环用于遍历所有非连通图。 1. MST 性质搞不清楚 1. 普里姆算法：划分阵营，小心发展。时间复杂度和边数无关，适合处理稀疏图 1. 拓扑排可以用来判断有向图是否存在环，并给出任务的可行执行先后顺序。拓扑排序判断图中有无环的原理：拓扑排序只处理入度为0的点，环内所有顶点入度永远不为0，无法被选出，统计到的顶点数量就会变少。操作完了剩下的定点，说明所有结点入度不为零，而入度有必然来自其它结点的出度，必然是环。 1. 拓扑排序的算法实现搞不清楚，主要是对图的邻接表存储结构又不熟悉了。 1. 确定关键路径的过程搞不清楚 1. 拓扑排序的结果满足？ 1. 邻接矩阵下三角全为0的图，无环，拓扑序列存在 1. 关键路径上的点，就是没有余地延迟的点，一旦延迟，就会导致整个项目延迟 1. 迪杰斯特拉算法每次更新一次set，确定到一个顶点的最短路径，但事先不知道这一轮确定的是到哪个定点的最短路径，可能要直到所有顶点确定完，才能出结果26:Tb87,全屏沉浸式查看图像、视频，干掉状态栏，不是壁纸，胜于壁纸项目地址：https://break.white-noise.online/frame/ --- ## 预设数据 ``` https://sns-img-hw.xhscdn.com/1040g008316h3ngsu1e005ovab1rpguo3j50vlf0?imageView2/2/w/0/format/jpg https://sns-img-hw.xhscdn.com/1040g008316h3ngsu1e1g5ovab1rpguo3imktolo?imageView2/2/w/0/format/jpg https://sns-img-hw.xhscdn.com/1040g008316h3ngsu1e0g5ovab1rpguo3o4rco68?imageView2/2/w/0/format/jpg https://sns-img-hw.xhscdn.com/1040g008316h3ngsu1e205ovab1rpguo3f4hmv3g?imageView2/2/w/0/format/jpg https://sns-bak-v1.xhscdn.com/pre_post/1040g2t031ku7kqjt2ur0472skhjr8fl3horpcl0 ``` ## 开发细节 + [x] 顶部和底部的导航似乎把播放器遮了（移动端测试了似乎没有这个问题）(暂时没复现) + [x] 现有的预置的图像、适配都是 portrait ，根据 orientation 过滤后，播放时桌面端会显示无媒体，但又没有提示清楚具体原因以及 action。另外要预置横向图片。presets 中，既要有纵向的合集，也要有横向的合集。横向媒体：最后一个是视频 + [x] 不要叫 havebreak-frame，叫 digital frame + [x] 合集不要显示秒数了 + [ ] 添加媒体等的方形按钮难看，不符合现在整体的拟态风格设计。 + [ ] frame 点击要默认播放，操作都用上下文菜单。 + [ ] 要支持重置数据，即恢复数据到到预置数据。 + [x] 合集中添加媒体的问题 + [x] 视频暂停后无法继续播放的问题。发现并没有，只是视频加载卡住了 + [x] 总的播放按钮，无法播放 + [x] 目前合集卡片的设计不利于播放。不要显示那么多信息，以媒体图像为主，基本就可以使用 MediaCard 这个组件。用 contextmenu 来触发更多操作即可。描述要有，但要弱化。 + [x] 合集要支持随机播放，也要支持顺序播放，默认是顺序播放，这个不受全局的 settings 的随机播放选项影响。合集的contextmenu 里面有随机和顺序选项。 + [x] frame Gallery 中，打开 lightbox 后，在 lightbox 的菜单中，删媒体的时候会删错（滑到其他媒体后，点删除，删的仍然是打开时的那个条目） + [x] frame 在 feed 中点击媒体时，播放范围应该先是其所属的 collection 内播放，而不是全局媒体 + [x] feed 分 tab ，分别展示全部、图片和视频。但现在图片和视频Tab下，点击一个媒体，仍然是从总的列表中的对应索引下播放，而并没有从当前列表（图片或视频列表）下的当前媒体播放了，这是不对的。 + [ ] 现在合集详情页不能管理媒体 + [ ] 从图片启动的情况下也在随机 + [ ] lightbox 现在不能缩放 video 标签这种方式可能不行, tauri dev 一下看看吧。合集：修改封面和内容重排序合集：编辑放到详情页合集列表：下拉刷新随机重排序27:T99f,data:image/jpeg;base64,/9j/2wBDAAYEBQYFBAYGBQYHBwYIChAKCgkJChQODwwQFxQYGBcUFhYaHSUfGhsjHBYWICwgIyYnKSopGR8tMC0oMCUoKSj/2wBDAQcHBwoIChMKChMoGhYaKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCj/wAARCAB4AHgDASIAAhEBAxEB/8QAGwABAAMBAQEBAAAAAAAAAAAAAAIDBAUBBgj/xAA4EAABAwIDBAkDAgUFAAAAAAABAAIDBBEFEiETMVFxBhQVMzRBYXKRIoHBUrEHMqHh8CRCktHx/8QAGAEBAQEBAQAAAAAAAAAAAAAAAAIBAwT/xAAcEQEBAQADAAMAAAAAAAAAAAAAARECA0ESITL/2gAMAwEAAhEDEQA/AP0Q1mZTMQt9VlJpDGFyocS43JuV0Qnso+IXmyj4j5UEQT2UfEfKbKPiPlQRBPZR8R8pso+I+VBEE9lHxHymyj4j5UEQT2UfEfKbKPiPlQRBMwx8QqzE0brL1DqtHgFkVQflkLD5ImMbJO6HNUq6TuxzVQ3hY1x5sQmfO5sGVrAbC4uSptnqz/uH/FUQRGRz2sk2biSA+wOXXfY6LkQwVR6N0cvakgzSRDLs2XF5gN+9erq6Z2eyfcnvqH09PNNnAlALT5gWstalHDlhGZ2dwGrrAX9dFFeaqEREaIiICIiAiIgxVLrVjQP0hFGq8a32j8oqS6sndjmqlbJ3Y5qlQpzIadr3yRTxtewkhzHi4I9QvY+i+E9Ujg6lCWsLTnLG5jZ19Tb7cl0iATcgXXtyPMrrx7ufD82xmNBYyKAMY1rWNGVrQLADgFmXpJO8krxc2iIiAiIgIiICIiDBVeNb7R+USq8a32j8oqS6sndjmqVdJ3Y5qlQp8FjH8RGYbjNRR9lzSw0zpmSSCUAksy6tFrW+rzPwtfSTpmcKxFtLTOwWoc6URZJMR2UkZtdxkGUhgGu867rXNlox3oNhWK1XWmsbS1LnSOlkZCyQyl9rkh4IuLCxG5dWXBY5cRw6qknke2iY4Njcxh2jy3KXvdbMTY8r6rWPmcd6fDDsTFNTxUFTG7LkkbPJrdrTrZhFvqBFidPhU4l/EJ9HWRU0dDBM99LHU5xOQwgh5dYkZrAM0u0E6+Vr9fFuhGH4nictdLPUskkcH5WtjLWkNa3TM0kaNGihJ0Fw+SmhhNTVMLIo4nSR5GukyB4zO01JDyD6AIO70exB+K4LSV8kTYnVDM4Y12YAE6a8l0FjwbD2YVhsFFFLLLHCMrXSkF1r7tAN25bEpBERGiIiAiIgwVXjW+0flEqvGt9o/KKkurJ3Y5qpWyd2OapUKcbFqurpqQ1EEUk7y8gRsvoACdw18v6rHPiWIxsmyUMziwNLdXWdckEbuGq+maS29tLr3O7it1ji4ZU1dVO1k0MsTTG1xdc6OIvbX7rskFpsd4Xud3EqKAiIjRERAREQEREGCq8a32j8olV41vtH5RUl1ZO7HNUq2TuxzVShTjduDrk0GwNow+7s1wcv2tu13qmp6RtgphKadzrymO1yNwvvtv1At+60yYnh5fMHxlxYHAnZXD9bOsd28eazzYhhLYo70mZj3EtGxA18jrxWsaDjH+vbA2nJY5m0D81jbLmvYjgFmPSKzXPNLZge1msmou0nUW9FqiqsOmna0QN2pYHax3IGUEC/I8tFRHimFvp+ssp/oeB9Qib9V/3/ALoIN6RNLqJrqYh1SP1/ym9j5a7lKTHyynll6o7KwHLd4GaxHppoR/mq9dimGsyjqzruANhGNPqPrxudF1zSwWymCKw0tkFt90HIfjzm07JepkZpDGWukANwbeQKSY+1lVLCYb7NpdcOOpAvbd6WXYbBEwNDImNDXZgALWO6/NeGlgMhkMMWcm+bKL35oMWEYn19j3SRCCzg1oL7kki9uf8AdU1uNdWxZlDsC4vLAH5tPq+y6UdLTxOzRQRMN812tA14/wBT8r19NA9+d8Mbn/qLQT/miDNh+IdclezZFmUXBJ37v+wtyiyKOO+RjW3JJsLan/wfCkjWCq8a32j8olV41vtH5RUl03m8Y5qtC7RRa9p0uL8CpUzSYbSyOe58Vy+9zmPmbrx2GUjj9UV/udNAP2AWy44hLjiEGaOgpo8pbELi9idT/LltfhbSyrbhVG0WbCBu3E6W4cPsttxxCXHEIMPZNHlY0xEhgAbdx0A3Af55Ba4Ymwxhkd8ovvN1O44hLjiEYIlxxCXHEI0RLjiEuOIQES44hVT1EcLbucCfJo3lGMlV45vtCKunzzTOkfvcfhFTHUtdVS0wf5IilTOcP13Lzs/0RFvyrMOz/ROz/RETaZDs/wBE7P8ARETaZDs/0Ts/0RE2mQ7P9E7P9ERNpkOz/RG0QadQiJtMaYogwaIiLB//2Q==28:T99f,data:image/jpeg;base64,/9j/2wBDAAYEBQYFBAYGBQYHBwYIChAKCgkJChQODwwQFxQYGBcUFhYaHSUfGhsjHBYWICwgIyYnKSopGR8tMC0oMCUoKSj/2wBDAQcHBwoIChMKChMoGhYaKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCj/wAARCAB4AHgDASIAAhEBAxEB/8QAGwABAAMBAQEBAAAAAAAAAAAAAAIDBAUBBgj/xAA4EAABAwIDBAkDAgUFAAAAAAABAAIDBBEFEiETMVFxBhQVMzRBYXKRIoHBUrEHMqHh8CRCktHx/8QAGAEBAQEBAQAAAAAAAAAAAAAAAAIBAwT/xAAcEQEBAQADAAMAAAAAAAAAAAAAARECA0ESITL/2gAMAwEAAhEDEQA/AP0Q1mZTMQt9VlJpDGFyocS43JuV0Qnso+IXmyj4j5UEQT2UfEfKbKPiPlQRBPZR8R8pso+I+VBEE9lHxHymyj4j5UEQT2UfEfKbKPiPlQRBMwx8QqzE0brL1DqtHgFkVQflkLD5ImMbJO6HNUq6TuxzVQ3hY1x5sQmfO5sGVrAbC4uSptnqz/uH/FUQRGRz2sk2biSA+wOXXfY6LkQwVR6N0cvakgzSRDLs2XF5gN+9erq6Z2eyfcnvqH09PNNnAlALT5gWstalHDlhGZ2dwGrrAX9dFFeaqEREaIiICIiAiIgxVLrVjQP0hFGq8a32j8oqS6sndjmqlbJ3Y5qlQpzIadr3yRTxtewkhzHi4I9QvY+i+E9Ujg6lCWsLTnLG5jZ19Tb7cl0iATcgXXtyPMrrx7ufD82xmNBYyKAMY1rWNGVrQLADgFmXpJO8krxc2iIiAiIgIiICIiDBVeNb7R+USq8a32j8oqS6sndjmqVdJ3Y5qlQp8FjH8RGYbjNRR9lzSw0zpmSSCUAksy6tFrW+rzPwtfSTpmcKxFtLTOwWoc6URZJMR2UkZtdxkGUhgGu867rXNlox3oNhWK1XWmsbS1LnSOlkZCyQyl9rkh4IuLCxG5dWXBY5cRw6qknke2iY4Njcxh2jy3KXvdbMTY8r6rWPmcd6fDDsTFNTxUFTG7LkkbPJrdrTrZhFvqBFidPhU4l/EJ9HWRU0dDBM99LHU5xOQwgh5dYkZrAM0u0E6+Vr9fFuhGH4nictdLPUskkcH5WtjLWkNa3TM0kaNGihJ0Fw+SmhhNTVMLIo4nSR5GukyB4zO01JDyD6AIO70exB+K4LSV8kTYnVDM4Y12YAE6a8l0FjwbD2YVhsFFFLLLHCMrXSkF1r7tAN25bEpBERGiIiAiIgwVXjW+0flEqvGt9o/KKkurJ3Y5qpWyd2OapUKcbFqurpqQ1EEUk7y8gRsvoACdw18v6rHPiWIxsmyUMziwNLdXWdckEbuGq+maS29tLr3O7it1ji4ZU1dVO1k0MsTTG1xdc6OIvbX7rskFpsd4Xud3EqKAiIjRERAREQEREGCq8a32j8olV41vtH5RUl1ZO7HNUq2TuxzVShTjduDrk0GwNow+7s1wcv2tu13qmp6RtgphKadzrymO1yNwvvtv1At+60yYnh5fMHxlxYHAnZXD9bOsd28eazzYhhLYo70mZj3EtGxA18jrxWsaDjH+vbA2nJY5m0D81jbLmvYjgFmPSKzXPNLZge1msmou0nUW9FqiqsOmna0QN2pYHax3IGUEC/I8tFRHimFvp+ssp/oeB9Qib9V/3/ALoIN6RNLqJrqYh1SP1/ym9j5a7lKTHyynll6o7KwHLd4GaxHppoR/mq9dimGsyjqzruANhGNPqPrxudF1zSwWymCKw0tkFt90HIfjzm07JepkZpDGWukANwbeQKSY+1lVLCYb7NpdcOOpAvbd6WXYbBEwNDImNDXZgALWO6/NeGlgMhkMMWcm+bKL35oMWEYn19j3SRCCzg1oL7kki9uf8AdU1uNdWxZlDsC4vLAH5tPq+y6UdLTxOzRQRMN812tA14/wBT8r19NA9+d8Mbn/qLQT/miDNh+IdclezZFmUXBJ37v+wtyiyKOO+RjW3JJsLan/wfCkjWCq8a32j8olV41vtH5RUl03m8Y5qtC7RRa9p0uL8CpUzSYbSyOe58Vy+9zmPmbrx2GUjj9UV/udNAP2AWy44hLjiEGaOgpo8pbELi9idT/LltfhbSyrbhVG0WbCBu3E6W4cPsttxxCXHEIMPZNHlY0xEhgAbdx0A3Af55Ba4Ymwxhkd8ovvN1O44hLjiEYIlxxCXHEI0RLjiEuOIQES44hVT1EcLbucCfJo3lGMlV45vtCKunzzTOkfvcfhFTHUtdVS0wf5IilTOcP13Lzs/0RFvyrMOz/ROz/RETaZDs/wBE7P8ARETaZDs/0Ts/0RE2mQ7P9E7P9ERNpkOz/RG0QadQiJtMaYogwaIiLB//2Q==29:Tc04,## 连续性的运算与性质 **定理** 设函数 $f(x)$ 和 $g(x)$ 在点 $x_0$ 处连续，则 $f(x)\pm g(x), f(x)\cdot g(x), \frac{f(x)}{g(x)} (g(x_0)\neq 0)$ 在点 $x_0$ 处也连续。 **定理** 设函数 $u=\varphi(x)$ 在点 $x=x_0$ 处连续，且 $\varphi(x_0)=u_0$，而函数 $y=f(u)$ 在点 $u=u_0$ 处连续，则复合函数 $y=f[\varphi(x)]$ 在 $x=x_0$ 处也连续。 **定理** 基本初等函数在其定义域内都是连续的。 **定理** 初等函数在其定义区间内都是连续的。 > 【注】所谓定义区间，是指包含在定义域内的区间。 ## 闭区间上连续函数的性质 **定理**（最值定理）设 $f(x)$ 在闭区间 $[a,b]$ 上连续，则 $f(x)$ 在 $[a,b]$ 上必有最大值与最小值。 **定理**（有界性定理）设 $f(x)$ 在闭区间 $[a,b]$ 上连续，则 $f(x)$ 在 $[a,b]$ 上必有界。 **定理**（介值定理）设 $f(x)$ 在闭区间 $[a,b]$ 上连续，且 $f(a)\neq f(b)$，则对于任意介于 $f(a)$ 与 $f(b)$ 之间的数 $C$，至少存在一点 $\xi \in (a,b)$，使 $f(\xi)=C$。推论若 $f(x)$ 在 $[a,b]$ 上连续，则 $f(x)$ 在 $[a,b]$ 上可取到介于最小值 $m$ 与最大值 $M$ 之间的任何值。 **定理**（零点定理）设 $f(x)$ 在闭区间 $[a,b]$ 上连续，且 $f(a)\cdot f(b)<0$，则至少存在一点 $\xi \in (a,b)$，使 $f(\xi)=0$。 >【注】零点定理的一个重要应用就是证明方程的根的存在性。常考题型 1. 讨论函数的连续性及间断点的类型 2. 有关闭区间上连续函数性质的证明题【例 9】 (2024, 数三) 设函数 $f(x)=\lim_{n\to\infty}\frac{1+x}{1+nx^{2n}}$，则 $f(x)$ (A) 在 $x=1, x=-1$ 处都连续。 (B) 在 $x=1$ 处连续，在 $x=-1$ 处不连续。 (C) 在 $x=1, x=-1$ 处都不连续。 (D) 在 $x=1$ 处不连续，在 $x=-1$ 处连续。解当 $|x|\geqslant 1$ 时，$f(x)=\lim_{n\to\infty}\frac{1+x}{1+nx^{2n}}=0$。当 $|x|<1$ 时，$f(x)=\lim_{n\to\infty}\frac{1+x}{1+nx^{2n}}=1+x$，这里 $\lim_{n\to\infty}nx^{2n}=\lim_{n\to\infty}\frac{n}{(\frac{1}{x^2})^n}=0$。在 $x=-1$ 处，$f(-1-0)=\lim_{x\to -1^-}f(x)=\lim_{x\to -1^-}0=0$， $f(-1+0)=\lim_{x\to -1^+}f(x)=\lim_{x\to -1^+}(1+x)=0$， $f(-1)=0$，则 $f(x)$ 在 $x=-1$ 处连续。在 $x=1$ 处，$f(1-0)=\lim_{x\to 1^-}f(x)=\lim_{x\to 1^-}(1+x)=2$， $f(1+0)=\lim_{x\to 1^+}f(x)=\lim_{x\to 1^+}0=0$，则 $f(x)$ 在 $x=1$ 处不连续，故应选 (D)。 · 40 · 【例 10】设 $f(x)$ 在 $[a,b]$ 上连续，$a

JS 获取所有 HTML 定义的标签

相关内容

408计算机组成原理 存储系统真题

408计算机组成原理缓存真题

计算机考研408数据结构-图专题2009-2020年真题

文章大纲