2017年华东理工大学信息科学与工程学院815计算机专业基础综合之数据结构考研导师圈点必考题汇编
● 摘要
一、选择题
1． 无向图G=（V , E ）, 其中：V={a, b , c , d , e , f ）}, E={（a , b ）, （a , e ）, （a , c ），，（b , e ）, （c , f ），（f , d ）（e , d ）, 对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。
A.a , b , e , c , d , f B.a , c , f , e , b , d C.a , e , b , c , f , d D.a , e , d , f , c , b
【答案】D
【解析】图的深度优先遍历过程是：从图中某个初始顸点V 出发，首先访问初始顶点V ，然后选择一个与顶点V 相邻且没被访问过的顶点U 为初始顶点。再从U 出发进行深度优先搜索，直到图中与当前顶点V 邻接的所有顶点都被访问过为止。
，，，，，根据E={（a , b ）（a ，e ）（a ，c ）（b ，e ）（c , f ）（f ，d ）, （e ，d ）}可知各顶点之间的邻接关系。依据上面的原则遍历，得出遍历顺序a , e ，d ，f ，c , b 。
2． 分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（ ）。
【答案】C
【解析】二叉排序树：左右子树都是二叉排序树，且保证右子树都比根结点大，左子树都比根结点小。据以上两点建立二叉排序树。
3． 某计算机采用微程序控制器，共有32条指令，公共的取指令微程序包含2条微程序，各指令对应的微程序平均由4条微指令组成，采用断定法（下址字段法）确定下条微指令的地址，则微指令中下址字段的位数至少是：（ ）
A.5 B.6 C.8 D.9
【答案】C
【解析】所以至少需要8位才能表示完130个地址。
4． 假定有k 个关键字互为同义词，若用线性探测法把这k 个关键字存入哈希表中，至少要进行多少次探测？（ ）
【答案】D
【解析】至少探测次数
5． 有六个元素6, 5, 4, 3, 2, 1顺序入栈，下列不是合法的出栈序列的是（ ）。
A.543612 B.453126 C.346521 D.234156 【答案】C
【解析】根据栈的后进先出的特点，对于C 选项中前两个元素得出栈顺序可以看出，4在5和6前先出栈，又根据入栈顺序，4在5和6后入栈，因此4出栈时，5和6必定在栈内，且5在6之上，所以出栈时5要比6先出找。
6．
协议对
A.011111000011111010
B.011111000111110101111110 C.01111100011111010
D.011111000111111001111101 【答案】A
组帧后对应的比特串为（ ）
HDLC 协议对比特串进行组帧时，HDLC 数据帧以位模式0111 1110标识每一个帧的【解析】
开始和结束，因此在帧数据中凡是出现了 5个连续的位“1”的时候，就会在输出的位流中填充一个“0”。所以答案为A 。
7． 静态链表中指针表示的是（ ）。
A. 下一元素的地址 B. 内存储器的地址 C. 下一元素在数组中的位置 D. 左链或右链指向的元素的地址 【答案】C
【解析】静态链表的一般结构为：
这种结构是预先分配一个较大的空间，类似于一次申请一个较大的数组，但是元素的增删操作都不会移动元素，只需要移动next 成员就行。因此，静态链表中的指针实际上表示的就是下一个元素在数组中的位置。
8． 下列选项中的英文缩写均为总线标准的是（ ）。
A.PCI 、CRT 、USB 、EISA B.ISA 、CPI 、VESA 、EISA C.ISA 、SCSI 、RAM 、MIPS D.ISA 、EISA 、PCI 、PCI-Express 【答案】D
【解析】选项A 中的CRT 和USB 、选项B 中的CPI 、选项C 中的RAM 和MIPS 均不是总线标准的英文缩写，只有选项D 中的英文缩写均为总线标准。
9． 对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是（ ）
A.
B.
C.
D.
【答案】D
【解析】拓扑排序方法如下：
（1）从有向图中选择一个没有前驱（即入度为0）的顶点并且输出它； （2）从图中删去该顶点，并且删去从该顶点发出的全部有向边； （3）重复上述两步，直到剩余的网中不再存在没有前趋的顶点为止。 对于此有向图进行拓扑排序所有序列为：和
10．下列各类存储器中，不采用随机存取方式的是（ ）。
A.EPROM B.CDROM C.DRAM D.SRAM 【答案】B
所以选D
【解析】随机存取方式是指存储器的任何一个存储单元的内容都可以存取，而且存取时间与存储单元的物理位置无关。CDROM 是只读的光盘存储器，采用串行存取方式而不是随机存取方式。
二、判断题
11．串长度是指串中不同字符的个数。（ ）
【答案】
【解析】不是，串长度是指串中字符的总个数。需要注意的是，在计算字符串的长度时，不要漏掉了空格。
12．哈希表的结点中只包含数据元素自身的信息，不包含任何指针。（ ）
【答案】×
【解析】哈希表的结点中可以包括指针，指向其元素。如哈希链表。
13．两分法插入排序所需比较次数与待排序记录的初始排列状态相关。（ ）
【答案】×
相关内容
相关标签