学习资料 A．中序遍历 C．后序遍历 6.
已
知
有
向
图
G=(V,E)
，
其
中
V={V1,V2,V3,V4,V5,V6,V7}
，
B．先序遍历 D．按层次遍历
E={
A．V1,V3,V4,V6,V2,V5,V7 C．V1,V3,V4,V5,V2,V6,V7
7. 顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（ ）。在此假定N为线性表中结点数，且每次查找都是成功的。 A．N+1 C．log2N
8. 下面关于m阶B树说法正确的是（ ）。
①每个结点至少有两棵非空子树； ②树中每个结点至多有m一1个关键字；
③所有叶子在同一层上； ④当插入一个数据项引起B树结点分裂后，树长高一层。 A．①②③ C．②③④
9. 已知一个线性表（38，25，74，63，52，48），假定采用h(k)=k%7计算Hash地址进行散列存储，若利用链地址法处理冲突，则在该Hash表上进行查找的平均查找长度为（ ）。 A．1.0 C．4/3
10. 在排序算法的实施过程中，使用辅助存储空间为O（1）的有（ ）。 A．简单排序法 C．归并排序法 二、填空题
1. n（n大于1）个结点的各棵树中，其中深度最大的那棵树的深度是n，它共有________个叶子结点和________个非叶子结点。
2.设一棵后序线索树的高是50，结点x是树中的一个结点，其双亲是结点y,y的右子树高度是60，x是y的左孩子。则确定x的后继最多需经过________中间结点（不含后继及x本身） 3.高度为2（第2层为叶子）的3阶B-树中，最多有________个关键字。
4.分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为无序的表，则平均情况下最省时间的是________算法。
5.简单选择排序和起泡排序中比较次数与序列初态无关的算法有________。 仅供学习与参考
B.快速排序法 D.基数排序法
B．7/6 D．3/2
B．②③ D．③
B．2log2N D．N
B．V1,V3,V2,V6,V4,V5,V7 D．V1,V2,V5,V3,V4,V6,V7
学习资料
6. 串的链式存储结构是将存储区域分成一系列大小相同的结点,每个结点有两个域 域和 域。其中 域用于用于存放数据， 域用于存放下一个结点的指针 三．判断
1. 顺序存储的线性表可以随机存取。 （ ）
2. 即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同。 （ ）
3. 十字链表是无向图的一种存储结构。（ ）
4. 折半查找方法适用于排列连续顺序文件的查找。（ ）
5. 在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（ ） 四、应用题
1. 用十字链表表示一个有k个非零元素的m x n的稀疏矩阵，则其总的结点数为多少？
2. G=(V,E)是一个带有权的连通图,则：
（1）．请回答什么是G的最小生成树；
（2）．G为下图所示,请找出G的所有最小生成树。
3. 请分别叙述在一个连续顺序文件中采用顺序查找法，折半查找法和分块查找法查找一个记录，该文件中记录应该满足什么条件？
4. 设待排序文件之排序码为（88，33，22，55，99，11，66），采用顺序存储。请用直接选择排序算法对上述文件进行排序，用图示说明排序过程。
仅供学习与参考
学习资料
东北农业大学网络教育学院 数据结构专升本作业题参考答案
作业题一参考答案： 一、单项选择题
1、C 2、B 3、D 4、C 5、B 6、B 7、A 8、C 9、D 10、D 二、填空题 1、非零元很少
2、操作受限（或限定仅在表尾进行插入和限定仅在表头进行删除操作或限制存取点或特殊），先进先出(或后进后出) 3、简单选择排序 4、O(n2)，O(e)，O(n) 5、邻阵矩阵，邻接表 三、算法 答： int count = 0; void onechild ( Btree t) { if ( t!=NULL) { onechild ( t->lchild ); onechild ( t->rchild );
if ( t->lchild!=NULL && (t->rchild!=NULL || t->lchild!=NULL && t->rchild==NULL )
count++;
} }
四、应用题 1、 答：
仅供学习与参考
学习资料
2、 答： （1） （3） C （5） C
G
B 1 5 2
F
A 3 D C 4 1 5 G
2 B A E 6 F 3 D 4
（6）
1 G 2 F A 3 D C 1 G 2 F 4
（4） A 3 D G C 1 C 1 G 2 F
（2）
3、答：由于地址空间为10，且从100开始，故散列函数选为H（key）=key%7+100。
仅供学习与参考
学习资料
用线性探测再散列解决冲突，ASLsucc=27/10
4、答：成功查找平均比较查找长度为：（n+1）/n[log2（n+1）]-1。
作业题二参考答案： 一、单项选择题
1、C 2、C 3、B 4、C 5、D 6、C 7、C 8、B 9、A 10、C 二、填空题 1、2n0-1 2、6，261 3、 ?log2k?+1 4、25 5、N-1
6、最优二叉树，最小的二叉树 7、根结点，各子树 三、应用题
1、
答：不唯一，型对即可
1 9 6 3 2 22 13 7 4
此树的带权路径长度WPL =9*1+6*2+4*3+(1+2)*4=45 2、 答：
仅供学习与参考
数据结构专升本模拟题及参考答案讲课讲稿
