一、选择题： （共30分，每题2分）
1. 采用链式存储结构表示数据时，相邻的数据元素的存储地址（        ）。 
A. 一定不连续        B. 不一定连续     
C. 一定连续        D. 部分连续，部分不连续
2. 在一个单链表中，若*p节点不是最后节点，在*p之后插入节点*s，则执行（        ）。
A. s->next = p; p->next = s;    B. s->next = p->next ; p->next = s;
C. s->next = p->next ; p = s;    D. p->next = s; s->next = p;
3. 用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j 沿链移动的操作为(          )。
A. j=j->next        B. j=r[j].next          C .j=j+1          D. j=r[j]-> next
4. 向一个栈顶指针为HS的链栈（带头结点）中插入一个s所指结点时，则执行（        ）。
A. s->next = HS ;  HS = s;                B.  HS->next = s;
C. s -> next = HS->next ; HS->next = s;      D.  s->next = HS ; HS = HS->next;
5. 已知一个推入堆栈的字符序列顺序是a,b,c,d,e, 下列哪个字符序列是不能通过堆栈操作得到的字符序列（          ）。
A. e,d,c,b,a      B. d,e,c,b,a      C. d,c,e,a,b      D. a,b,c,d,e
6. 循环队列存储在数组]中，则入队时的操作为（      ）。
A. rear=rear+1              B. rear=(rear+1) mod (m-1)
C. rear=(rear+1) mod m      D. rear=(rear+1)mod(m+1)
7. 在一个具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队空的条件是（          ）。
A. front = = (rear +1) % n      B. front = = rear   
C. front = =0              D. (front +1) % n = = rear   
8. 对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概念的，插入一个元素时平均要移动表中的（        ）个元素。
A. (n－1)/2      B. n          C. n/2        D. (n＋1)/2
9. 对广义表 A=（（a,(b)）,(c,()),d）执行操作gettail(gethead(gettail(A))) 的结果是：（          ） 。
A.（）      B. （（））      C. d        D. (d)
10. 构造哈希表的关键字的输入序列为(25,21,30,13,4,43,35,64,5,17,2,8)，哈希函数H(key)=key%15，采用链地址法解决冲突。查64的关键字比较次数是（          ）。 
A.  1            B.  2              C. 4              D .  3  数据结构与算法考研真题
11. 下图是一个二叉树后序遍历的结果是 （            ）。
A、  abcdef      B、 cfabde   
C、  dbaecf      D、 cbfade
12. 现有以下按前序和中序遍历二叉树的结果：
  前序：GAHFDBCE  中序：AHGBDCFE，该二叉树的后序遍历序列为 (                ) 。
A . GHABCDEF            B. HABCDEFG           
C. ABCDEFGH              D. HABCGDEF
13. 一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是（            ）。   
A .  39        B. 119      C.  111      D. 239
14. 一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（          ）。
A . 是一棵满二叉树          B. 所有的结点均无右孩子   
C. 所有的结点均无左孩子    D. 只有一个叶子结点   
15. 任何一个连通图的最小生成树  (            )。
A．只有一棵      B. 有一棵或多棵    C. 一定有多棵      D. 可能不存在
二、填空题：（共28分，每空2分）
1. 已知某二叉树的先序遍历次序为abcdefg，中序遍历次序为badcgfe，则该二叉树的后序遍历次序为____________，层次遍历次序为___________。
 
2. 对于长度为n的关键字有序的线性表，若进行顺序查，则平均时间复杂度为________；若采用二分法查，则平均时间复杂度为________；
3.在一棵度为3的树中，度为3的结点个数为3，度为2的结点个数为2，度为1的结点个数为1，则度为0的结点个数为________。
4. 在一棵m阶B-树中，除根结点外非叶结点至少有________棵子树，至多有________棵子树。
5. 分别采用堆排序、快速排序、冒泡排序和归并排序，对初态为有序的表，则最省时间的是________算法，最费时间的是________算法
6. 如图所示的有向无环图可以排出________种不同的拓扑序列。
7. 给定一组数据{6，2，7，10，3，12}，以它构造一棵哈夫曼树，则树高为__________，带权路径长度WPL的值为__________。
8. 已知一组待排序的记录关键字初始排列如下：56,26,86,35,75,19,77,58,48,42；
则快速排序一趟排序的结果是                    ，希尔排序（初始步长为3）一趟排序的结果是                    。
三、简答题：（共52分）
1. 按关键字13、24、37、90、53、34的次序构造一棵平衡二叉树，回答以下问题：（8分）
（1）该平衡二叉树的高度是多少？   
（2）其根节点的关键字是什么？
（3）其中经过了哪些调整？（指出调整名称和次数）
2. 根据下图G以及它的存储，分别写出广度和深度遍历结果。设第一个访问结点是1。（6分）
3. 下图所示的AOE网络用于描述一项工程，其中的顶点表示事件，边代表一次活动，边上的权值表示完成该活动所需的时间，试回答以下问题：（6分）
(1) 完成整个工程所需的总时间是多少？
(2) 给出整个工程的关键活动和关键路径。                 
4. 设散列表的长度为13，散列函数为H（k）=k%13，给定的关键码序列为19，14，23，01，68，20，84，27。试画出用线性探查法解决冲突时所构成的散列表。（5分）
0    1    2    3    4    5   6  7  8   9  10    11    12
5. 下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，画出所有可能的选择。（7分）
6. 已知关键字序列（60，20，31，1，5，44，55，61，200），写出对它进行第一趟快速排序（以第一个关键字为基准）后的序列的值，并指出它的稳定性（6分）

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。