2017年北京联合大学制造业信息化技术801计算机综合之数据结构考研导师圈点必考题汇编
● 摘要
一、填空题
1． 有向图G=（V ，E ）, 其中V （G ）=[0, 1，2，3，4, 5}, 用
【答案】50; 4
2． 数据结构是研讨数据的_____和_____以及它们之间的相互关系，并对与这种结构定义相应的_____，设计出相应的_____。
；算法 【答案】逻辑结构；物理结构；操作（运算）
3． 当两个栈共享一存储区时，栈利用一维数组
当栈1空时
，
【答案】为_____，栈2空时
， 表示，两栈顶指针为则为_____，栈满时为_____。 【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。
4． —棵左子树为空的二叉树在前序线索化后，其中的空链域的个数为 _____。
【答案】2
【解析】只有根结点的做指针为空和最右边的叶结点的右指针为空。
5． 以下是用类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:
p->Rchild=head:head->Lchild=p
6． 从平均时间性能而言，_____排序最佳。
【答案】快速
【解析】快速算法的平均时间复杂度为nlogn 。
7． 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。
【答案】模式匹配；模式串
8． 在一棵m
阶
的个数是_____。 【答案】
【解析】m
阶树除根结点和叶子结点外，结点中关键字个数最多是最少
9． 从用户的观点看，文件的逻辑结构通常可以区分为两类：一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件:另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____，_____和_____。B+树适用于组织_____的索引结构，m
阶
个关键码。
【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织；
10．对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。 【答案】
【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。
树每个结点至多有_____个儿子，除根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的t->Lchild!=null: t->Lchild: 关键字的个数是_____；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字
二、选择题
11．下面关于哈希（Hash ，杂凑）查找的说法正确的是（ ）。
A. 哈希函数构造的越复杂越好，因为这样随机性好，冲突小
B. 除留余数法是所有哈希函数中最好的
C. 不存在特别好与坏的哈希函数，要视情况而定
D. 若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单地将该元素删去即可
【答案】C
【解析】若数据结构中存在关键字和K 值相等的记录，则必定在
不需要进行比
较便可直接取得所查记录。在此，称这个对应关系f 为哈希（Hash ）函数，哈希函数的选择要视具体情况而定。
12．内部异常（内中断）可分为故障（fault ）、陷讲（trap ）和终止（abort ）三类。下列有关内部异常的叙述中，错误的（ ）。
A. 内部异常的产生与当前执行指令相关
B. 内部异常的检测由CPU 内部逻辑实现
C. 内部异常的响应发生在指令执行过程中
D. 内部异常处理后返回到发生异常的指令继续执行
【答案】D
【解析】内中断分为：①由软中断指令启动的中断；②在一定条件下由CPU 自身启动的中断。D 项错误，如突然掉电引发的内中断经处理后不会继续执行。
13．下列选项给出的是从根分别到达两个叶节点路径上的权值序列，能属于同一棵哈夫曼树的是（ ）。
A.24，10，5 和24，10，7
B.24，10，5 和24，12，7
C.24，10，10和24，14，11
D.24，10，10和 24，14，6
【答案】D
【解析】哈夫曼树是带权路径长度最短的二叉树。由根节点出发到两个叶子节路径中，第二个被访问的两个结点的权值要么相等，要么和为根节点的权值，故B 项错误。同理，通过第三个被访问的节点排除A 项。C 项，由两条路径可推出三个叶子节点的权值分别是：3、10和11，而根据哈夫曼树的定义可知，权值为3的节点应该和权值为10的结点结合，故C 项错误。D 项，反推出有四个叶子节点，权值分别为：5、5、6和8，满足哈夫曼树的条件。
14．n 个结点的线索二叉树上含有的线索数为（ ）。
【答案】C
的存储位置上，由此，
相关内容
相关标签