考研真题

下列对顺序存储的有序表(长度为 n)实现给定操作的算法中平均时间复杂度为O(1)的是（）。

现有非空双向链表 L，其结点结构为

“s- > next=p-> next;p- > next=s”，后，还要执行（）。prer是指向直接前驱结点的指针，next是指向直接后继结点的指针。若要在L中指针p所指向的结点(非尾结点)之后插入指针s指向的新结点，则在执行了语句序列：

若采用三元组表存储结构存储稀疏矩阵M。则除三元组外，下列数据中还需要保存的是（  ） 。

 I、M 的行数           II、M中包含非零元素的行数

III、M 的列数            IV、M 中包含非零元素的列数

在有6 个字符组成的字符集 S 中,各个字符出现的频次分别为 3,4,5,6,8,10,为 S 构造的哈夫曼树的加权平均长度为(       )。

已知一棵二叉树的树形如图，若其后序遍历为 f,d,b,e,c,a，则其先序列为（      ）。

已知无向连通图G中各边的权值均为1.下列算法中定能够求出图G中从某顶点到其余各个顶点最短路径的是(     )。

I. 普利姆算法

II. 克鲁斯卡尔算法

III.图的广度优先搜索

下列关于非空B树的叙述中，正确的是(     )。

I  插入操作可能增加树的高度

II 删除操作一定会导致叶结点的变化

III 查找某关键字一定是要查找到叶结点

IV 插入的新关键字最终位于叶结点中

对含有600个元素的有序顺序表进行折半查找，关键字之间的比较次数最多是（    ）。

现有长度为5，初始为空的散列表HT，散列表函数H(K)=(k+4)%5用线性探查再散列法解决冲突。若将关键字序列2022,12,25依次插入HT中，然后删除关键字25，则HT中查找失败的平均查找长度(     )。

下列排序算法中，不稳定的是(   )

I 希尔排宁         II 归并排序      III 快速排序      IV 堆排序        V 基数排序

使用快速排序算法对数据进行升序排序，若经过一次划分后得到的数据序列是 68,11,70,23,80,77,48,81,93,88，则该次划分的轴枢(       )

若机器M的主频为1.5Ghz,在M上执行程序p的指令条数为5*105,p的平均CPI为1.2,则p在M 上的指令执行速度和用户CPU时间分别为(       ）。

若short型变量x=-8190，则x的机器数为(     ）。

已知float型变量用IEEE754单精度浮点数格式表示。若float型变量x的机器数为8020  0001H，则 x 的值(       )。

某计算机的CPU有30根地址线，按字节编址，CPU和主存芯片连接时，要求主存芯 片占满所有可能存储地址空间并且RAM区和ROM区所分配的容量大小比为3:1。若RAM 在连续低地址区，ROM在连续高地址区，则ROM的地址范围(       )。

己知 x、y为 int 类型，当 =100，y=200 时，执行 x-y 指令的到的溢出标志OF 和借位标志 CF 分别为 0,1,那么当 x=10，y=-20 时，执行该指令得到的 OF 和CF 分别是(   )。

某运算类型指令中有一个地址码为通用寄存器编号，对应通用寄存器中存放的是操作数或操作数地址,CPU 区分两者的依据是( )。

数据通路由逻辑元件和时序元件组成，以下是组合逻辑元件的是()。

I算术逻辑部件ALU

II程序计数器PC

III通用寄存器

IV多路选择器MUX

采用取指、解码,执行,存储,写入 5 段流水线,RIS3C 处理器,SO,S1,S2,S3,t2为寄存器编号，

 I1: add S2 S1 SO        //[R[S2]]               R[S1]+R[S0]

 I2: add load(S3)0(S2)   //[R[S2]]                R[S1]+R[SO][1] 

 I3: beq t2 S3 L1          //if R[t2]==R[S3]     jump to Ll

 I4: add t2 t3 I0            //[R[t2]]                    R[t2]+I0

如采用旁路技术处理数据相关，即采用专用数据通路技术处理器，则在 I1~I4执行过程中，发生流水线阻塞的有(  ）。

若有存储总线宽度为 64 位，总线时钟频率为 1GHZ，在总线上传输一个数据支地址需要一个的时钟周期，不支持突发传送，若该总线连接 CPU 和主存，主存每次准备一个 64 位数据需要 6ns，主存块大小为 32B，则读取一个主存块时间为（）。