2 三个结点的二叉树和三个结点的树一样，都具有三种不同的形态。 3中序序列和后序序列相同的二叉树为：空树和缺右子树的单支树 。
4对于两棵具有相同关键字集合而形状不同的二叉排序树，中序遍历后得到的关键字排列顺序相同。 5 序列{30，40，50，15，25，35，38，10}是堆 。
6 对于无向图的生成树，从同一顶点出发所得的生成树相同 。
7 若设哈希表长m=14，哈希函数H(key)=key，表中已有4个结点。 addr(15)=4 addr(38)=5 addr(61)=6 addr(84)=7 其余地址为空，如用二次探测再散列处理冲突，关键字为49的结点的地址是9。
8一个深度为k的，具有最少结点数的完全二叉树按层次，(同层次从左向右)用自然数依此对结点编号则，则编号最小的叶子的序号是2+1 ；编号是i的结点所在的层次号是「log2 i|+1。（「log2 i|表示向上取整」（根所在的层次号规定为1层）。
9在一棵7阶B树中，一个结点中最多有6棵子树，最少有3棵子树。 10算法可以没有输入，但是必须有输出 。 四、画出树的孩子兄弟表示法示意的树或森林。（4分）
B C ∧ ∧ F ∧ ∧ G ∧ ∧ I ∧ k-2
A ∧ ∧ D E 五、要求题（本大题共2小题，共12分） ∧ H 设关键字的输入序列为{4，5，7，2，1，3，6} 1．（8分）从空树开始构造平衡二叉树，画出每加入一个新结点时二叉树的形态，若发生不平衡，
指明需做的平衡旋转类型及平衡旋转的结果。
2． （4分）上面的数据作为待排序的数据，写出用快速排序进行一趟划分后的数据序列 六、按要求做题（本大题共2小题，共12分）
1画出无向图G的邻接表存储结构，根据邻接表存储结构写出深度优先和广度优先遍历序列。（7分）
V8 V4 V2 V5 V6 V3 V7 V1 2 用prim算法求下图的最小生成树，写出最小生成树的生成过程。（5分）
V1 50 V2 40 65 50 V5 70 60 52 V4 V3 42 30 V6 45 V7 V2 V5 V4 V6 V1 V3 31 V7 V1 50 V2 V5 V4 V6 V7 V3
七、算法分析设计题（本大题共5小题，共30分）
1．写出程序段的功能,并给出一个测试用例（一个输入数据和一个输出结果）(5分)。 void conversion() { Stack s; int n; SElemType e; initstack(s);
printf(\ scanf(“%d”,&n); while(n) {push(s,n%8); n=n/8; }
while(!stackempty(s)) {pop(s,e); printf(“%d”,e); } }
2.下面是一个使用栈stack实现对二叉树进行非递归先根遍历的函数,请在标号处填写合适的语句。(每空1分，共5分) 程序:
Void preorder(bitree *T) {bitree *stack[m]; int top; if(T!=NULL) {top=1;
stack[top]=(1); while( (2) ) {p=stack[top]; top--;
32
printf(“%d”,p->data);
if(p->rchild!=NULL){ (3) ; stack[top]=p->rchild;} if( (4) ) { top++; (5) ;}
} } }
⑴ ⑵ ⑶ ⑷ ⑸
3.请在标号处填写合适的语句。完成下列程序。(每空1分，共5分) int Binary_Search(S_TBL tbl，KEY kx)
{ /* 在表tbl中查找关键码为kx的数据元素，若找到返回该元素在表中的位置，否则，返回0 */
int mid，flag=0；
low=1；high=length； while( ⑴ &!flag ) { /* 非空，进行比较测试 */
mid= ⑵ ； if(kx ⑶ ； else if(kx>tbl.elem[mid].key) ⑷ ； else { flag= ⑸ ；break；} } return flag; } ⑴ ⑵ ⑶ ⑷ ⑸ 4.下面是一个采用直接选择排序方法进行升序排序的函数，请在标号处填写合适的语句。(每空1分，共5分) 程序： Void seletesort(int A[n],int n) { int i,j,t,minval,minidx; for(i=1;i<=n-1;i++) { minval=A[i+1]; (1) for(j=i+2;j<=n;j++) if( (2) ) { (3) ; minidx=j;} 33 if( (4) ) {t=A[i+1]; (5) A[minidx]=t; } } } ⑴ ⑵ ⑶ ⑷ ⑸ 5 试写出求有向无环图的关键路径算法的设计思路（10分） 数据结构试卷A答案 选择题（本大题共20小题，每题1分，共20分；答案填在下表内） 1 C 11 : C 2 B 12 A 3 : C 13 : B 4 : D 14 : D 5 : B 15 : B 6 : D 16 : A 7 : B 17 : C 8 : C 18 : A 9 : A 19 C 10 : C 20 D 二、填空题（本大题共5小题，每空1分，共12分；答案填在下表内） 1 2 3 4 5 6 有穷性 确定性 可行性 可读性 健壮性 效率 n(n-1) 'student' 队列 先进先出 (a) (a) 三、判断题（对的打“√”，错的打“×”。每小题1分，共10分） 1）true ; 2）flase; 3）true; 4）true; 5）flase; 6）flase ; 7）true; 8）true; 9）flase; 10）true 四、画出树的孩子兄弟表示法示意的树或森林。（4分） D E F G 34 A B C H I 其他形式的树形结构酌情给分。 五、要求题（本大题共2小题，共12分） 1. 5 2.一趟划分后的数据序列 3 1 2 4 7 5 6 2 7 4 六、按要求做题（12分） 1 4 7 5 7 5 4 7 4 5 2 遍历序列v1 v2 v4 v8 v5 v3 v6 v7(或1 2 4 8 5 3 6 7) 1 .DFS4 BFS遍历序列v1 v2 v3 v4 v5 v6 v7 v8(或1 2 3 4 5 6 7 8) 1 5 邻接点的顺序可以不同，可以有不同的深度优先和广度优先遍历序列。（5分，如有错误酌情扣分。） 5 2 6 2 2 1 3 V3 7 V3 V1 V1 V1 V3 50 50 50 1 4 V2 V7 V4 V2 V7 V2 V4 V7 V4 4 50 50 40 40 40 30 V6 V5 V6 V6 V5 V5 3 4 6 2 5 2 1 3 V1 5 V37 V3 V1 1 3 7 V7 V4 V7 V2 V4 V2 七、算法设计题（30分） 1.将十进制转化成八进制数（5分） 测试用例：输入10 输出12 2（5分，每空1分）（1）T (2) top>0 (3) top++ (4) p->lchild!=NULL 35 V5 6 V5 V6