全部来自 AI 原创生成并经逐题审校的题目，带 精品 标记的为 AI 复审通过。整卷生成请去组卷。
某计算机按字节编址，主存容量 4GB，Cache 数据区容量 64KB，块大小 32B，采用 8 路组相联映射。程序运行统计：访存共 2000 次，其中命中 Cache 1900 次，Cache 命中时访问时间为 10ns，一次缺失的额外开销为 100ns（即缺失时访问时间为 10ns+100ns）。则主存地址中 Tag 字段位数为____，平均访问时间为____。A. 19 位；15ns B. 20 位；14.5ns C. 19 位；14.5ns D. 20 位；15ns
登录后查看答案
某计算机主存容量 2GB，按字节编址；Cache 数据区容量 32KB，主存块大小为 32B，采用 2 路组相联映射。则主存地址共____位，其中标记（Tag）字段为____位，组号字段为____位，块内地址字段为____位。
某五段指令流水线（IF、ID、EX、MEM、WB）每段耗时均为 1 个时钟周期，转移指令在 EX 段才修改 PC，故每次转移执行被判定为发生跳转时造成 2 个周期的流水线损失。现连续执行 10 条彼此独立、无数据冒险的指令，其中第 4 条为转移指令且实际发生跳转（其后已被取入流水的 2 条指令作废，从转移目标处继续取指）。该程序段共需多少个时钟周期才能全部执行完？ A. 12 B. 14 C. 16 D. 18
某计算机按字节编址，虚拟地址 32 位，页大小 8KB；TLB 共 64 项，采用 2 路组相联。物理主存容量 1GB；Cache 数据区容量 32KB，主存块大小 32B，采用 4 路组相联映射。则 TLB 标记字段为____位，Cache 主存地址标记（Tag）字段为____位。
某计算机采用五段指令流水线（IF、ID、EX、MEM、WB），每段耗时均为 1 个时钟周期。现连续执行 20 条指令，其中所有相邻指令之间均不存在数据冒险，仅第 6 条为转移指令，其在 EX 段修改 PC，导致其后已取出的 2 条指令作废（即产生 2 个周期的损失），流水线随后继续无冒险地执行剩余指令。执行完这 20 条指令共需要 ____ 个时钟周期。
对一棵二叉树采用二叉链表存储，现要求输出其「之字形」层序遍历序列：第1层自左至右，第2层自右至左，第3层自左至右，如此交替。某同学准备借助一个辅助队列完成整层结点的收集，再对需要反向输出的层借助另一个辅助结构调整输出顺序。关于实现该算法，下列说法正确的是： A. 收集层结点用队列，反向输出层借助栈，整棵树只需一次自上而下的层序扫描，时间复杂度 O(n) B. 收集层结点用队列，反向输出层只能再递归遍历该层结点一次，时间复杂度变为 O(n²) C. 反向输出层必须改用双端队列逐个插队首，否则无法得到正确序列 D. 收集层结点必须改用栈，否则无法保证同层结点按从左到右的顺序被访问
判断：某计算机主存按字节编址，Cache 数据区容量 64KB，块大小 32B，采用 8 路组相联映射，主存地址共 28 位。某同学认为：该 Cache 共有 64KB/(32B×8)=256 组，组号占 8 位，块内地址占 5 位，故主存标记字段占 28−8−5=15 位；且当某次访问在 TLB 中命中时，CPU 无需再访问内存中的页表即可完成地址转换。
判断：在每段耗时 1 个时钟周期的五段流水线（IF、ID、EX、MEM、WB）中，若连续执行的 n 条指令之间不存在任何数据冒险和控制冒险，则执行完这 n 条指令共需 n+5 个时钟周期。
判断：在某五段指令流水线（IF、ID、EX、MEM、WB）中，若第 5 条指令需要使用第 4 条 load 指令刚从存储器读出的数据作为源操作数，则即使采用全部数据前递技术，也必须在两条指令之间插入 1 个气泡（停顿 1 个时钟周期）。
将关键字序列 33, 8, 20, 46, 59, 72, 85 依次存入长度为 11 的散列表，散列函数为 H(key)=key mod 11，用线性探测法处理冲突。查找成功时的平均查找长度 ASL成功=____，查找失败时的平均查找长度 ASL失败=____（均用分数表示）。
将关键字序列 16, 23, 9 依次存入长度为 7 的散列表，散列函数为 H(key)=key mod 7，用二次探测法处理冲突（探测序列为 H、H+1²、H+2²、…，均对 7 取模）。则查找成功的平均查找长度 ASL 为多少？ A. 2 B. 7/3 C. 3 D. 8/3
判断：设哈夫曼树中仅有度为0和度为2的结点，若叶子结点数为 n，则该树总结点数为 2n−1，且 WPL 等于各非叶（分支）结点权值之和；这一性质对任何哈夫曼树都成立，因此计算 WPL 时必须逐个计算每个叶子的「权值×路径长度」再求和，不能借助分支结点权值求和得到。
在带头结点的单链表 L 上实现就地逆置，采用「摘下结点头插法」：p 指向首元结点后先将 L->next 置空，随后循环中每次取下 p 所指结点插入 L 的头部。则循环体内正确的操作顺序是（ ） A. 先用 q 保存 p->next，再执行 p->next=L->next、L->next=p，最后 p=q B. 先执行 p->next=L->next，再用 q 保存 p->next、L->next=p，最后 p=q C. 先执行 L->next=p->next，再执行 p->next=L->next、L->next=p D. 先执行 p=q，再执行 p->next=L->next、L->next=p
判断下列说法是否正确：在一棵二叉排序树（BST）中删除一个左、右子树均非空的结点 p 时，可以先用 p 在整棵树中的中序前驱结点 s（即 p 的左子树中最右侧结点）的关键字值覆盖 p 的关键字值，再转而删除结点 s，且删除后所得的二叉树仍然满足 BST 的性质，该方法时间复杂度为 O(h)（h 为树高）。
设二叉树采用二叉链表存储，结点类型为 BiTNode（含 data 域及 lchild、rchild 指针）。给出如下递归算法，功能是交换二叉树中每个结点的左、右子树：void swap(BiTree T){ if(T==NULL) ____; BiTree tmp=T->lchild; T->lchild=T->rchild; T->rchild=tmp; swap(T->lchild); swap(T->rchild);} 则空位处应填写的语句是「return;」。若树中共有 n 个结点，该算法的时间复杂度为 O(n)。
判断题：在一棵含 n 个带权叶子结点的哈夫曼树中，权值越大的叶子结点离根越近；并且，哈夫曼树是一棵高度必为 n-1 的二叉树（即每个叶子都位于最深层）。
某采用树形目录结构的文件系统中，根目录为 /，其下有目录 usr 和 etc；usr 下有目录 local 和 bin；local 下有目录 share 和文件 a.txt；etc 下有文件 passwd。某用户当前工作目录为 /usr/local，则文件 a.txt 的相对路径（相对当前目录）与文件 passwd 的绝对路径分别为（ ） A. share/a.txt 和 /etc/passwd B. ./share/a.txt 和 usr/etc/passwd C. a.txt 和 /etc/passwd D. local/share/a.txt 和 /usr/etc/passwd
某算法对n个元素排序时：相邻两趟处理中，元素比较次数与初始序列有关，且某一趟若无任何交换发生即可提前结束；其最坏情况比较次数为n(n-1)/2。该排序算法是（） A. 冒泡排序 B. 简单选择排序 C. 直接插入排序 D. 快速排序
某计算机采用偶校验方式，每个字节的最高位为校验位，其余7位为有效数据位。若有效数据为 1100111（即 0x67 的低7位），则加上校验位后该字节的完整8位编码是（ ）。 A. 01100111 B. 11100111 C. 11001110 D. 11000111
判断：第二代计算机以晶体管为主要逻辑器件；某小组据此认为，只要一台计算机使用了晶体管，它就一定属于第二代计算机，这一看法是正确的。