2017年中国地质大学(武汉)计算机学院952软件综合之数据结构考研题库
● 摘要
一、填空题
1． 在一个无向图的的邻接表中，若表结点的个数是m , 则图中边的条数是_____条。
【答案】m/2
【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。
2． 一个有2001个结点的完全二叉树的高度是_____。
【答案】11
【解析】完全二叉树的高度
3． 假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素中的存储位置k=_____。（注：矩阵元素下标从1开始）
【答案】93
【解析】对于上三角矩阵，将代入得93。
4． 设数组的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素
为_____。
【答案】9174；8788
【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，
则它的存储地址为
若以列序为主存储顺序，则它的存储地址为
5． 顺序栈用
【答案】存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。 的存储地址为_____；若以列序为主序顺序存储，则元素的存储地址在B
【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。
6． 循环队列的引入，目的是为了克服_____。
【答案】假溢出时大量移动数据元素
【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。
7． 属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
8． 在有n 个顶点的有向图中，每个顶点的度最大可达。
【答案】2（n-l ）
【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n-1。
9． —棵有个结点的满二叉树有_____个度为1的结点、有_____个分支（非终端）结点和_____个叶子，该满二叉树的深度为_____。 【答案】
或
【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。
10．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_____和_____; 而又根据指针的连接方式，链表又可分成_____和_____。
【答案】单链表；双链表；（动态）链表；静态链表
【解析】线性表的链式存储结构根据每个结点包含的指针个数分为单链表和双链表，单链表只包含一个指针，指向后续元素，双链表包括两个指针，指向前一个元素和后续元素。根据指针的连接方式，链表可分为动态链表和静态链表。静态链表的指针指向下一个元素的编号，动态链表的指针指向下一个元素的物理位置。
11．设正文串长度为n ，模式串长度为m ，则串匹配的KMP 算法的时间复杂度为_____。 【答案】
12．G 是一个非连通无向图，共有28条边，则该图至少有_____个顶点。
【答案】9
【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。
二、选择题
13．某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为
2字节，逻辑地址结构为：
逻辑地址空间大小为
（ ）。
A.64
B.128
C.256
D.512
【答案】B
【解析】地址空间分为逻辑地址空间和物理地址空间。页的大小为
采用二级页表，一页可存放
要个页面来保存页表项，故本题答案为B 。
字节，页表项大小为页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是字节，页表项大小为2B ，字节，故最少需
’个页表项，本题中逻辑地址空间大小为
14．下列各类存储器中，不采用随机存取方式的是（ ）。
A.EPROM
B.CDROM
C.DRAM
D.SRAM
【答案】B
【解析】随机存取方式是指存储器的任何一个存储单元的内容都可以存取，而且存取时间与存储单元的物理位置无关。CDROM 是只读的光盘存储器，采用串行存取方式而不是随机存取方式。
15．下列给出的指令系统特点中，有利于实现指令流水线的是（ ）。
I. 指令格式规整且长度一致
II. 指令和数据按边界对齐存放
III. 只有Load / Store指令才能对操作数进行存储访问
A.
仅
B.
仅
C.
仅
D.
【答案】D
【解析】特点I 和III 都是RISC 机的特征，而特点II 则有利于指令和数据的存放，所以以上三个特点都有利于实现指令流水线。
16．对于100Mbps 的以太网交换机，当输出端口无排队直通（cut-throughswitching ）方式转发一个以太网帧（不包括前导码）时，引入的转发延迟至少是（ ）
A.
B.
C.
D.
【答案】B
【解析】直通交换方式是指以太网交换机可以在各端口间交换数据。它在输入端口检测到一个数据包时，检查该包的包头，获取包的目的地址，启动内部的动态查找表转换成相应的输出端口，在输入与输出交叉处接通，把数据包直通到相应的端口，实现交换功能。通常情况下，直通交换方式只检查数据包的包头即前14个字节，由于不需要考虑前导码，只需要检测目的地址的6B ，所以最短的传输延迟是
17．下列关于USB 总线特性的描述中，错误的是（ ）。
A. 可实现外设的即插即用和热插拔
B. 可通过级联方式连接多台外设
C. 是一种通信总线，可连接不同外设