发布时间 : 星期四 文章江苏技术师范学院 - 数据结构复习题及答案更新完毕开始阅读1f7315d4195f312b3169a577
解1： 0-1 13 2： 0-2 8 3： 0-2-3 13 4： 0-2-3-4 19 5： 0-2-3-4-5 21 6： 0-1-6 20
0 8 13 1 5 9 5 2 32 2 30
3 6 4 7 17 6 6 已知某二叉树先序遍历的结果为：ABDGECFH，其中序遍历的结果为：
DGBEAHFC，试画出这棵二叉树。
2、方案1；哈夫曼编码
先将概率放大100倍，以方便构造哈夫曼树。
w={7,19,2,6,32,3,21,10}，按哈夫曼规则：<{【[(2,3)，6],(7,10)】,32}，(19,21)>
7 、对关键字序列（7，4，1，14，100，30，5，9，20，134），设哈希函数为h(k)=k % 13,试给出表长为13的哈希表（用线性探测开放定址法处理冲突），并求出在等概率情况下，查找成功的平均查找长度。
解：H(7)=7 mod 13 =7 H(4)=4 mod 13 =4 H(1)=1 mod 13 =1
H(14)=14 mod 13 =1 冲突 H1=（14+1） mod 13 =2 H(100)=100 mod 13 =9 H(30)=30 mod 13 =4 冲突 H1=（30+1）mod 13=5 H(5)=5 mod 13 =5 冲突 H1=（5+1）mod 13=6 H(9)=9 mod 13 =9 冲突 H1=（9+1）mod 13=10 H(20)=20 mod 13 =7 冲突 H1=（20+1）mod 13=8
《数据结构》试卷 第 5 页 共 9 页
H(134)=134 mod 13 =4 冲突 H1=（134+1）mod 13=5 冲突 H1=（134+2）mod 13=6 冲突 H1=（134+3）mod 13=7 冲突 H1=（134+4）mod 13=8 冲突 H1=（134+5）mod 13=9 冲突 H1=（134+6）mod 13=10 冲突 H1=（134+7）mod 13=11 冲突
在等概率情况下：ASL=（1*4+5*2+1*8）/10=2.2
6. 已知图1所示的有向图，请给出该图的:(8分)
(1) 每个顶点的入/出度； (2) 邻接矩阵； (3) 邻接表； 顶点 入度 出度 1 2 3 4 (4) 逆邻接表。 5 6
1、对图1所示带权无向图采用prim算法，从顶点①开始构造最小生成树。（写出加入生成树顶点集合S和选择边Edge的顺序）
分。
3 25 2 1 15 5 20 14 6 4 16 10 图1
2 3 6 7 8 5 12 《数据结构》试卷 第 6 页 共 9 页
S： 顶点号 ①③ ①③② ①③②④ ①③②④⑦ ①③②④⑦⑤ ①③②④⑦⑤⑥
Edge： （顶点，顶点，权值） （ 1 ，2 ，2 ） （ 1 ， 5 ，5 ） （ 2 ， 4 ，3 ） （ 2 ， 7 ，6 ） （ 2 ， 5 ，8 ） ( 7, 6 , 10 )
3、设散列表的长度为11，散列函数为H(k)=k，给定的关键码序列为56,74,23,11,69, 22,59,29。试画出用线性探查法解决冲突时所构成的散列表。
0 11 1 56 2 23 3 69 4 22 5 59 6 7 29 8 74 9 10
2. 假设在树中，结点x是结点y的双亲时，用(x,y)来表示树边。已知一棵树边的集合为：{(i,m),(i,n),(b,e),(e,i),(b,d),(a,b), (g,k),(c,g),(c,f), (h,l),(c,h),(a,c)}用树形表示法画出此树。
3．简述树和二叉树之间的区别与联系？
树和二叉树逻辑上都是树形结构，区别有二点：一是二叉树的度至多为2，树无此限制；二是二叉树有左右子树之分，即使在只有一个分枝的情况下， 也必须指出是左子树还是右子树，树无此限制。二叉树不是树的特例。
五、算法设计题
1、将一个带头结点的单链表A分解成两个具有相同结构的链表B，C。其中B表的结点是A表中值小于0的结点，而C表的结点为A表中值大于等于0的结点（链表A的元素类型为整形，要求B、C表利用A表的结点。）
算法思路是：先创建两个表头结点B和C，pb和pc分别指向B和C的最后结点。扫描单链表A的所有结点，对于结点*pa, 若其data域值小于0，则将*pa链接到B链表后；否则将*pa链接到C链表后。算法如下：
typedef struct node{ int data;
struct node *next; } Lnode;
《数据结构》试卷 第 7 页 共 9 页
void split(Lnode *A, Lnode *B, Lnode *C); {Lnode *pa=A->next, *pb,*pc; B=new Lnode; //创建头结点 C=new Lnode; //创建头结点 pb=B;pc=C;
while(pa!=NULL){
if (pa->data<0){ //小于0的数据插入B队列 pb->next=pa;pb=pa; }
else { //大于0的数据插入C队列 pc->next=pa; pc=pa; }
pa=pa->next; }
pb->next=pc->next=NULL;
2. list指向带头结点的非空线性链表，链结点的构造为（data,link）.请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点。
解：LinkedList delinsert（LinkedList list）
∥list是非空线性链表，链结点结构是（data，link），data是数据域，link是链域。
∥本算法将链表中数据域值最小的那个结点移到链表的最前面。 {p=list->link；∥p是链表的工作指针
pre=list； ∥pre指向链表中数据域最小值结点的前驱。 q=p； ∥q指向数据域最小值结点，初始假定是第一结点 while （p->link!=null）
{if（p->link->data
if (q!=list->link) ∥若最小值是第一元素结点，则不需再操作 {pre->link=q->link； ∥将最小值结点从链表上摘下； q->link= list->link；∥将q结点插到链表最前面。 list->link=q； }
}∥算法结束
[算法讨论] 算法中假定list带有头结点，否则，插入操作变为q->link=list；list=q。
3，已知二叉树采用二叉链表存储，试编写一个算法，计算二叉树中叶子结点的个数。
2. 解：
int LeafCount_BiTree(Bitree T)//求二叉树中叶子结点的数目 {
if(!T) return 0; //空树没有叶子
《数据结构》试卷 第 8 页 共 9 页
else if(!T->lchild&&!T->rchild) return 1; //叶子结点
else return Leaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加上右子树的叶子数
}//LeafCount_BiTree
4. 写出求二叉树深度的算法。
1．int Get_Depth(Bitree T) //求子树深度的递归算法 {
if(!T) return 0; else {
m=Get_Depth(T->lchild); n=Get_Depth(T->rchild); return (m>n?m:n)+1; }
}//Get_Depth
5．已知11个元素的有序表为（05,13,19,21,37,56,64,75,80,88,92）, 请写出折半查找的算法程序，查找关键字为key的数据元素
2．解：折半查找的C程序有很多参考资料，注意此题要求是整型量。 折半查找的一个递归算法如下，形式非常简洁！
int Search_Bin_Recursive(SSTable ST, int key, int low, int high) //折半查找的递归算法 {
if(low>high) return 0; //查找不到时返回0 mid=(low+high)/2;
if(ST.elem[mid].key= =key) return mid; else if(ST.elem[mid].key>key)
return Search_Bin_Recursive(ST, key, low, mid-1); else return Search_Bin_Recursive(ST, key, mid+1, high); }
}//Search_Bin_Recursive }
《数据结构》试卷 第 9 页 共 9 页