一单项选择题（本大题共10道小道小题，每小题3分，共30分）1. 算法的时间复杂度取决于【 】A. 问题的规模B. 待处理数据的初始状态C. 软件和硬件的组合D. 操作系统2. 向一个栈顶指针为top的链栈中插入一个s结点，则执行 【 】A.top->next=s;B.s->next=top->next;top->next=s;C.s->next=top;top=s;D.s->next=top;top=top->next;3.广义表（a）的表头是【 】A.aB. (a)C. ()D. (a)4. 由带权为8、2、5、7的叶子结点构造一棵哈夫曼树，该树的带权路径长度为 【 】A. 37B. 32C. 46D. 435. 采用邻接表存储的图，其BFS算法类似于二叉树的【 】A. 中序遍历B. 先序遍历C. 后序遍历D. 按层遍历6. 在非空m阶B_树上，除根结点之外的所有其他非终端结点【 】A. 至少有2/m棵子树B. 至多有2/m棵子树C. 至少有2/m棵子树D. 至多有2/m棵子树7. 对线性表进行顺序查找时，要求线性表的存储结构为【 】A. 散列存储B. 顺序存储或者链式存储C. 压缩存储D. 索引存储8. 在关键字“基本有序”的情况下，最佳排序算法为 【 】A. 快速排序B. 冒泡排序C. 直接插入排序D. 基数排序9. 折半查找法和二叉排序树的时间性能【 】A. 与处理数据量有关B. 相同C. 不相同D. 不确定10. 串是一种特殊的线性表，其特殊性体现在【 】A. 可以顺序存储B. 数据元素是一个字符C. 可以链接存储D. 数据元素可以是多个字符二、填空题（本大题共10小题，每小题2分，共20分）1. 在具有n个单元的循环队列中，队满时共有_个元素。2. 单链表中设置头结点的目的是_。3. 消除递归_需要使用栈。4. 在具有n(n1)个结点的k叉树中，有_个空指针。5. 深度为5的二叉树至多有_个结点。6. 一个连通图的_是一个极小连通子图。7. 对稀疏图进行DFS遍历时，应该采用_作为其存储结构。8. 在哈希表中，装填因子越大，则_。9. 在堆排序和快速排序中，若原始记录接近有序，则应该选择_。10. 设关键字序列为3, 7, 6, 9, 7, 1, 4, 5, 20，对其排序的最少交换次数为_。三、简答题（本大题共6道小题，共56分）1. 若中序序列为ABC，试问有多少种不同的形态的二叉树可以得到这一遍历结果？画出所有的二叉树。（9分）2. 对于下图，请给出：（1） 对应的邻接矩阵，并给出V1、V2、V3的出度和入度;（2） 邻接表和逆邻接表;（3） 强连通分量。（10分）3. 已知关键字序列为9, 6, 2, 5, 4, 3, 1, 10, 7, 11, 8，试回答： （1） 按表中元素的顺序，构造一棵平衡二叉排序树。 （2） 在等概率的情况下，求查找成功的ASL值。（10分）4. 在采用线性探测再散列法解决冲突的散列表中，所有同义词在表中是否一定相邻？试说明理由。（9分）5. 有关键字25, 50, 55, 20, 30, 45, 40, 15, 10, 35，判断其是否为堆，若不是堆，请调整为一个小根堆。要求写出调整过程。（9分）6. 什么是内部排序？稳定性指的是什么？（9分）四、算法阅读题（本大题共3道小题，每小题8分，共24分）【说明】结构定义structListNodeelemtypedata;structListNode*next; ;structBtreeNodeelemtypedata;structBtreeNode*lchild, *rchild; ;1. 下面算法的功能是将队列中的数据元素进行逆置。设栈和队列的元素类型均为int。请在空白处填入正确的语句。Voidunknown(queue&q) _;intd;InitStack(s);while(_)Dequeue(q,d);Push(s,d); while(!StackEmpty(s) _;Enqueue(q,d); 2. 下面的算法是统计单链表中数据域的值为X的结点个数。请在空白处填入正确的语句。intCountNodeX(structListNode*head,Elemtypex) structListNode*p; _;p=head;while(_)if(_)n+;p=p->next; _; 3. 下面的算法完成了对一棵二叉树中所有的左、右子树的相互交换。请在空白入填入正确的语句。VoidTNodeExchang(structBTreeNode*root) if(_)TNodeExchang(root->lchild); _;structBTreeNode*p;p= _;root->lchild=root->rchild;root->rchild= _; 五、算法设计题（本大题共3道小题，共20分）1. 已知Head是带头结点的单链表的头指针，试编写逆序输出表中各元素的递归算法。假设数据为整数。VoidFindLinkData(structListNode*head) （7分）2. 试设计一个算法，求出指定结点在给定的二叉排序树中的层次。 【要求】1. 给出算法的设计思想; 2. 给出算法代码。（7分）intpLevel(structBTreeNode*root,structBTreeNode*p) /求指定结点p在以root为根的二叉树中的层次 3. 给出一棵二叉树的前序序列和后序序列，能否唯一地确定一棵二叉树？试证明你的论断。（6分）