2017年燕山大学信息科学与工程学院810数据结构考研冲刺密押题
● 摘要
一、填空题
1．
每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是
中序序列是
前庁序列是_____。 【答案】
【解析】树的抑序序列对应二叉树的前序序列. 该二叉树转换成森林吋含三棵树. 其第一棵树的前序是。
2． G 是一个非连通无向图，共有28条边，则该图至少有_____个顶点。
【答案】9
【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。
3． 实现字符串拷贝的函数strcpy 为：
【答案】
4． 己知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查找90时，需_____次查找成功，查找47时_____成功，查找100时，需_____次才能确定不成功。
【答案】2；4；3
【解析】二分法查找元素次数列表
查
找100是找到115就停止了。
5． 对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度，当它为一棵_____ 时. 具有最大高度
【答案】完全；只有一个叶结点的二叉树
第 2 页，共 67 页 .
，则它的后庁序列是_____。设上述二叉树是由某棵树转换而成，则该树的
6．
【答案】5 =_____
7． 以下是用类C 语言写山的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild 域作为前链域，指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack , 栈顶
head 为双向循坏链表的头指针。 指针为top , P , t 为辅助指针，试填充算法中的空格，使算法完整。
void leafchain（BiTree Abt）
{p={BiTree）malloc （sizeof （BiTNode ））;
If （!p ）{print£（“OVERFLOW\n”; exit （1）; }
head=p; top=0;
if （bt ）
{top++; stack[top]=bt;
while （top ）
{t=stack[top]; top--;
if （it->Lchild && !t->Rchild）{ （1） ; （2） ; （3） ; }
else {if（ （4） ）{top++; stack[top]= （5） ; }
if （ （6） ）{top++; stack[top]= （5） ; }
}
}
（8） ; （9） ; } }
【答案】
p->Rchild=t:t->Lchild=p:p=t: t->Rchild!=null:t->Rchild: t->Lchild!=null: t->Lchild: p->Rchild=head:head->Lchild=p
8． 设有一个10阶对称矩阵A 采用压缩存储方式， （以行为主序存储：）则的地址为_____。
【答案】33
【解析】设存储的元素的行标为i ，列标为j 。若的地址为将代入得33。
9． 数组的存储结构采用_____存储方式。 则【答案】顺序存储结构
【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。
10．在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_____; 对于有向图来说等于该顶点的_____。
【答案】度；出度
第 3 页，共 67 页 则的地址为若
11．—棵左子树为空的二叉树在前序线索化后，其中的空链域的个数为 _____。
【答案】2
【解析】只有根结点的做指针为空和最右边的叶结点的右指针为空。
12．在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。 【答案】
要加“虚结点”。
设编号为
和
的结点在顺序存储中的下标为
和
。
13．空格串是指_____，其长度等于_____。
【答案】由空格字符（值32）所组成的字符串；空格个数
14．顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。 【答案】
【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监视哨。
15．用循环链表表示的队列长度为n ，若只设头指针，则出队和入队的时间复杂度分别是_____和_____；若只设尾指针，则出队和入队的时间复杂度分别是_____和_____。 【答案】
【解析】队列的出队操作即删除队头的元素，队列的入队操作即在队尾添加元素，循环链表只设头指针，出队时，只要把头结点的下一个结点删除就好了，入队时，要把新的结点插入队尾，必须把队列遍历，找到队尾指针，才能插入。循环队列只设尾指针，出队时只要把为指针的下一个结点或者下下个结点删除即可，入队时，只要在尾指针的后面插入新的结点，并更新尾结点即可。
，
则结点
和
在同一层上的条件是 【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，
二、选择题
16．float 型数据通常用IEEE754单精度浮点数格式表示。若编译器将float 型变量x 分配在一个32位浮点寄存器FR1中，且x=-8.25, 则FR1的内容是（ ）。
A.C1040000H
B.C2420000H
C.C1840000H
D.C1C20000H
【答案】A
第 4 页，共 67 页
相关内容
相关标签