北京理工大学专业课程模拟试题集 数据结构与算法
行序为主序存储时元素A[3, 5]的地址与A按列序为主序存储时元素____________________________的地址相同。 （2分）
10.若无向图中有n个结点，e条边，则它的邻接表需要________个表结点。 （2分） 11.设一个有序表为｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，当采用折半查找值为95的结点时，____次比较后查找结束。 （2分） 12.在队列中，新插入的结点只能添加到________。 （2分）
三、问答题 （共6题,共36分）
1.请用C语言给出循环队列(队列的顺序存储结构)的类型定义。 （6分）
2.画出具有3个结点的所有二叉树。（6分）
3.用一维数组存放的一棵完全二叉树如下：ABCDEFGHIJK。请画出这棵完全二叉树，并写出后序遍历该二叉树的访问结点序列。（6分）
4.根据Kruskal算法构造下图的最小生成树。（6分）
5.以关键字序列{12，2，16，9，10，8，20}为例，写出执行快速排序算法的各趟排序结束时，关键字序列的状态。（6分）
30
北京理工大学专业课程模拟试题集 数据结构与算法
6.设一个有序表为｛1，3，9，12，32，41，62，75，77，82，100｝，当采用折半查找值为80的结点时，几次比较后查找结束？请给出具体查找过程。（6分）
四、算法题 （共2题,共16分）
1.阅读如下算法，给出该算法的功能。（8分） void Unkown(LinkList &L, int n) L=（LinkList）malloc(sizeof (LNode)); L->next=NULL; for (i=n; i>0;--i)
p=(LinkList)malloc(sizeof(LNode)); p->data=i; p->next=L->next; L->next=p;
2.下面算法的功能是：在双向循环链表p所指结点之前插入s所指结点，所插入的元素为e。（8分）
Status ListInsert_Dul(DuLinkList &L, ElemType e)
if(!(s=(DuLinkList)malloc(sizeof(DuLNode)))) return ERROR; s->data = e;
(1)_________________________; (2)_________________________; (3)_________________________; (4)_________________________; return OK;
31
北京理工大学专业课程模拟试题集 计算机组成原理
010048计算机组成原理
模拟试题一
一、单选题 （共15题,共15分）
1.I/O编址方式通常可分统一编址和独立编址，。 （1分）
A.统一编址是将I/O地址看作是存储器地址的一部分，可用专门的I/O指令对设备进行访问
B.独立编址是指I/O地址和存储器地址是分开的，所以对I/O访问必须有专门的I/O指令 C.统一编址是指I/O地址和存储器地址是分开的，所以可用访存指令实现CPU对设备的访问
D.独立编址是将I/O地址看作是存储器地址的一部分，所以对I/O访问必须有专门的I/O指令
2.微程序控制器中，微程序的入口地址是由形成的。 （1分） A.机器指令的地址码字段 B.微指令的微地址码字段 C.机器指令的操作码字段 D.微指令的微操作码字段
3.ROM与RAM的主要区别是。 （1分）
A.断电后，ROM内保存的信息会丢失，RAM则可长期保存而不会丢失 B.断电后，RAM内保存的信息会丢失，ROM则可长期保存而不会丢失 C.ROM是辅助存储器，RAM是主存储器 D.ROM是主存储器，RAM是辅助存储器
4.中央处理器（CPU）是指。 （1分）
A.运算器 B.控制器 C.运算器和控制器 D.运算器和存储器
5.下列说法中是正确的。 （1分）
A.指令周期等于机器周期 B.指令周期小于机器周期 C.指令周期大于机器周期 D.指令周期是机器周期的两倍
6.设计微程序的人员是。 （1分）
A.硬件设计人员 B.系统软件人员 C.应用软件人员 D.用户
32
北京理工大学专业课程模拟试题集 计算机组成原理
7.在存储器堆栈中，保持不变的是。 （1分）
A.栈顶 B.栈指针 C.栈底 D.栈中的数据
8.微操作信号发生器的作用是。 （1分）
A.从主存中取出指令 B.完成指令操作码的分析功能 C.产生控制时序 D.产生各种微操作控制信号
9.在DMA传送方式中，由发出DMA请求。 （1分）
A.外部设备 B.DMA控制器 C.CPU D.主存
10.主机与设备传送数据时，采用，主机与设备是串行工作的。 （1分） A.程序查询方式 B.中断方式 C.DMA方式 D.通道方式
11.CPU响应中断的时间是。 （1分）
A.一条指令结束 B.外设提出中断 C.取指周期结束 D.任一机器周期结束
12.对于低速输入输出设备，应当选用的通道是。 （1分）
A.数组多路通道 B.字节多路通道 C.选择通道 D.DMA专用通道
13.三级时序系统提供的三级时序信号是。 （1分） A.指令周期 机器周期 节拍 B.指令周期 机器周期 时钟周期 C.机器周期 节拍 脉冲
D.指令周期 微指令周期 时钟周期
14.下列数中最小的数为：。 （1分） A.(101001)2 B.(52)8 C.(101001)16
D.(233)4
15.当有中断源发出请求时，CPU可执行相应的中断服务程序。提出中断请求的可以是。分）
A.通用寄存器 B.专用寄存器 C.外部事件 D.Cache
二、判断题 （共10题,共10分）
1
33
（北京理工大学专业课程模拟试题集 计算机组成原理
1.执行基本微操作的控制命令称为微命令。 （1分） ( )
.
2.执行一条指令可分为取指令、分析指令和执行指令三个阶段。 （1分） ( ) 3.对于自底向上生成的堆栈，出栈时应先修改栈指针，再将数据压入堆栈。 （1分）
( )
4.BCD码是有冗余状态的编码。 （1分） ( )
.
5.转子指令是一条零地址指令。 （1分） ( )
6.指令周期即为CPU周期。 （1分） ( )
7.微型机中的系统总线包括数据总线、地址总线、控制总线，所以称它为三总线。 （1分） ( )
8.若操作数在寄存器中，可以采用直接寻址方式获取操作数。 （1分） ( ) 9.在主存和CPU之间增加高速缓冲存储器的目的是解决CPU和主存之间的速度匹配问题。 （1分） ( )
10.返回指令通常是一条零地址指令。 （1分） ( )
三、填空题 （共15题,共15分）
1.输入输出的目的是要实现________和________之间的信息传送。 （1分）
2.DMA数据传送过程可以分为________________________、________________________和________________________三个阶段。 （1分）
.
3.计算机系统通常分为________________和________________。 （1分）
4.计算机硬件由____________、____________、存储器、输入设备和输出设备五大部件组成。（1分）
5.算术左移一位相当于____________。 （1分）
6.在打印机字库中，一个5×7点阵的字符，点阵码占____字节。 （1分） 7.一个16M×32的存储芯片有________条地址线，________条数据线。 （1分） 8.[-0]原表示为________________________________（8位二进制）。 （1分） 9.(2578)10= (_________________________________________________ ___________________________)8421码 （1分）
10.显示器的视频存储器（VRAM）的容量是由____________和____________决定的。 （1分）
11.常见的软拷贝输出设备为________________。 （1分）
12.八进制数37.4Q转换成二进制数为___________________________________。 （1分） 13.寄存器寻址时，操作数在____________中。 （1分） 14.调用子程序时，通常用________保存返回地址。 （1分）
34