一、名词解释（5*3=15分）
aov网队列栈哈夫曼树生成树。
二、 填空题（1*16=16分）
1. 根据数据元素之间关系的不同特性，通常有下列四类基本结构资料个人收集整理，勿做商业用途。
2. 数据元素之间的关系在计算机中可用顺序映像和非顺序映像表示，由此得到两种存储结构是资料个人收集整理，勿做商业用途。
3. 用具有n个元素的一维数组存储一个循环队列，该循环队列的最大长度为 __
一棵高度为5的二叉树中最少含有 __个结点，最多含有 __个结点；资料个人收集整理，勿做商业用途。
4. 在无向图g的邻接矩阵a中，若(vi,vj)属于图g的边的集合，则对应元素a[i][j]等于___否则等于资料个人收集整理，勿做商业用途。
5. 二分查找的存储结构仅限于___且是。
6. 在对一组记录(54，38，96，23，15，72，60，45，83)进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较___次。资料个人收集整理，勿做商业用途。
7. 设顺序表中有n个关键字，采用顺序的方法查找，其平均查找长度为___
8. 二叉树第i（i≥1）层上最多有___个结点。
三、选择题（1*10=10分）
1. 在一个不带头结点的单链表hl中，若要向表头插入一个由指针p指向的结点，则执行___
a、l=p; p->next=hl;
b、p->next=hl; hl=p;
c、p->next=hl; p=hl;
d、p->next=hl->next; hl->nxet=p;
2. 在一个长度为n的顺序存储的线性表中，删除第i个元素 （1≤i≤n+1）时，需要从前向后依次移动个元素___资料个人收集整理，勿做商业用途。
a、n-i b、n-i+1 c、n-i-1 d、i
3. 在一个顺序队列中，队首指针指向队首元素的位置。__
a、当前 b、后一个 c、前一个 d、后面。
4. n个结点的线索二叉树中线索的数目为___
a、(n-1)个 b、n个 c、（n+1）个 d、(n+2)个
5. 设数组a[m]为循环队列q的存储空间，front为队头指针，rear为队尾指针，则判定q为空队列的条件是___资料个人收集整理，勿做商业用途。
a.(rear-front)%m= =rear
c.(rear-front)%m= =rear+1)%m
6. 假设一棵完全二叉树按层次遍历的顺序依次存放在数组bt[m]中，其中根结点存放在bt[0]，若bt[i]中的结点有左孩子，则左孩子存放在___资料个人收集整理，勿做商业用途。
7. 连通图是指图中任意两个顶点之间___
a.都连通的无向图b.都不连通的无向图。
c.都连通的有向图d.都不连通的有向图。
8. 左图所示带权无向图的最小生成树的权为 。
a.14 b.15 c.17d.18
9. 栈的插入和删除操作在___进行。
a.栈顶 b.栈底 c.任意位置 d.指定位置资料个人收集整理，勿做商业用途。
10. 以下说法正确的是 。
a．连通图的生成树是该连通图的一个极小连通子图。
b．无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的。
c．任何一个有向图，其全部顶点可以排成一个拓扑序列。
d．有回路的图不能进行拓扑排序。
四、计算和应用题（共21分）
1．假设用于通信的电文仅由8个字母组成，字母在电文**现的频率分别为0.08, 0.18, 0.
02, 0.06, 0.35, 0.
10, 0.16, 0.05。
试为这8个字母设计哈夫曼编码。并计算其平均编码长度（即wpl）。资料个人收集整理，勿做商业用途。
2．使用普里姆算法构造如下图所示的图g的一棵最小生成树。（画出构造过程）
3．待排序关键字（34,12,28,45,66,7,3,21），写出希尔排序的每趟结果。
五、算法填空（9*2=18分）
1.如果希望循环队列中的向量单元都能得到利用，则可设置一个标志域tag,每当尾指针和头指针值相同时，以tag的值为0或1来区分队列状态是“空”还是“满”。请对下列函数填空，使其分别实现与此结构相应的入队列和出队列的算法。
资料个人收集整理，勿做商业用途。
int enqueue(cirqueue *q,datatype x){
if( (1) )return 0;
q->data[q->rear]=x;
q->rear=(q->rear+1)% maxqsize
return 1;
int dequeue(cirqueue *q,datatype *x){
if( (3) )return 0;
x=q->data[q->front];
q->front= (4) ;
return 1;
2.下列算法利用二分查找方法在有序表r中插入元素x，并保持表r的有序性，其中参数*n为表r的长度。请在空缺处填入合适的内容，使其成为一个完整的算法。
资料个人收集整理，勿做商业用途。
void bininsert(seqlist r,int *n,datatype x)
int low=1,high=*n,mid,i;
while(low<=high)
mid= (1) ;
if (else (2) ;
for(i=*n; (3) ;i--)
r[i+1]=r[i];
n++;
六、算法设计题（2*10=20分）
1. 编写递归算法，将二叉树中所有结点的左右子树相互交换。
2. 给出图的邻接表存储结构，编写一深度优先遍历算法实现对存放在邻接表中图遍历。
数据结构与算法
本章知识要点 算法的基本概念 数据结构的定义 线性表的定义和存储 树 二叉树的定义和存储 查找与排序算法。算法 algorithm 是一组有穷的规则，规定了解决某一特定类型问题的一系列运算，是对解题方 与完整的描述。算法是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中...
算法与数据结构
学院专业姓名学号。实验1 线性表的操作 12学时 问题描述 假设一个班级内有n个学生，定义一个学生类和一个班级类。学生类中包括学号 姓名 性别 年龄 专业等属性 班级类包括一个学生对象链表。定义如下 class student class myclass student stu head 链表表头指...
算法与数据结构
1 简述算法的概念及其五个重要特性。2 下图是用邻接表存储的图，请画出此图，写出其邻接矩阵以及从c点开始分别按广度优先搜索和深度优先搜索遍历该图的结果。给定一棵用二叉链表表示的二叉树，其根指针为root，编写求此二叉树叶结点个数的算法，要求先写出二叉链表的类型定义。2.编写简单选择排序的算法。1 用...