发布时间 : 星期三 文章05到09年福建专升本数据结构真题详解更新完毕开始阅读6de880d43186bceb19e8bb2a
A． q=p->left; r=p->right; q->right=r; r->left=q; 正确的
B． q=p->right; r=p->left; q->right=r; r->left=q; 把A的p和q反过来，结果错了。
C． q=p->left; r=p->right; q->left=r; r->right=q; 错误，与B一样，只是把p和q反过来。 D．q=p->left; r=p->right; q->right=r->left; 什么也没有变化。
7．会引起循环队列队头位置发生变化的操作是 A．出队列
8．如图1所示，若从顶点1出发进行广度优先搜索，则得到的访问序列是 A． 1,8,3,4,5,6,7,2 B． 1,2,3,7,5,6,4,8 C． 1,2,5,4,3,6,7,8 D．1,2,3,4,5,6,7,8
9．下列排序算法中，不受数据初始状态影响，时间复杂度为O(n*logn)的是 A．堆排序
10．用指针实现二叉树，在n个节点的二叉树中含有多少个空指针？ A．n
11．用一棵二叉搜索树进行( )得到的是有序序列。 A．前序遍历
12．合并排序算法的时间复杂度是 A．O(n2)
二、 填空题（共7小题，每空2 分，共16分）
13．在一个长度为n的顺序表的第i（1<=i<=n）个元素之前插入一个元素，需要
B．O(nlogn)
C．O(logn)
D．O(n)
B．中序遍历
C．后序遍历
D．层次遍历
B．n-1
C．n+1
D．2n
B．冒泡排序
C．直接选择排序
D．快速排序
B．入队列
C．取队首元素
D．取队尾元素
后移___n-i+1____个元素。
14．设某哈夫曼树有n个叶子节点，则该哈夫曼树的总结点数为__2n-1__。
15．设有一个序列8,53,37,28，当使用直接插入排序从小到大排序时，比较次数是____5____。
16．设SQ为循环队列，存储在数组queue[0…m-1]中，则SQ入队操作对其队尾指针rear的修改是___ (rear+1)%m___。
17．设待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序是__稳定的____，否则称为___不稳定的___。
18．在一个具有n个顶点的无向图中，要连通所有的顶点至少需要__n-1____条边。
19．在有向图中，以顶点v为起点的弧的数目称为v的___出度__。
三、 应用题（共4小题，每小题10 分，共40分）
20．已知关键字序列(12,77,21,65,38,7,40,53)，采用直接插入排序按递增排序，给出每一趟的结果。 12,77,21,65,38,7,40,53 12,21,77,65,38,7,40,53 12, 21,65, 77,38,7,40,53 12, 21, 38,65, 77, 7,40,53 7,12, 21, 38,65, 77, 40,53 7,12, 21, 38,40,65, 77, 53 7,12, 21, 38,40,53,65, 77
21．已知散列表长度为10（散列空间0..9），使用线性重新散列技术解决冲突，
现有一组单词(SUN, MON, TUE , WED , THU, FRI, SAT)，其对应的散列函数值分别为(3,2,6,3,2,5,6)，请画出这组单词插入后的散列表。 0 1 2 MON 3 SUN 4 WED 5 THU 6 TUE 7 FRI 8 SAT 9 22．假设一个二叉树的先序为EBADCFHGIKJ，中序序列是ABCDEFGHIJK， （1） 画出二叉树；（2）写出后序序列。
先序为EBADCFHGIKJ，中序序列是ABCDEFGHIJK，根是E E
/ \\
ABCD FGHIJK 中 BADC FHGIKJ 先序 根B 根F
/ \\ / \\
A CD GHIJK 中 A DC HGIKJ 先序
根D 根H / / \\ C G IJK 中 IKJ 先 根I \\ JK中 KJ先 根K / J
最后结果： E