C、后根 D、层次
8、用邻接表表示图进行深度优先遍历时，其非递归算法通常采用 ( A )来实现算法。
A、栈 B、队列 C、树 D、图
9、广度优先遍历类似于二叉树的( D )。 A、先序遍历 B、中序遍历 C、后序遍历 D、层次遍历
10、在一个有向图中，所有顶点的人度之和等于所有顶点的出度 之和的( B )。 A、1／2倍 B、1倍 C、2倍 D、4倍
11、任何一个带权无向连通图的最小生成树( B )。 A、只有一棵 B、一棵或多棵 C、一定有多棵 D、可能不存在
12、设非空单链表的数据域为data，指针域为next，指针P指向单链表的第i个结点，s指向生成的新结点，现将s结点插入到单链表中，使其成为第i结点，下列算法段能正确完成上述要求 的是( C )。 A、s->next=p->；p->next=s
B、p->next=s；s->next=p->next；
C、S->next=p->next；p->next=s；交换p->data和s->data D、p=s；s->next=p
二、填空题（每空2分，共20分）
1、数据的逻辑结构反映_____成分数据逻辑关系______。
2、对于队列，只能在___队尾_____插入元素，在____队头_____删除元素。 3、算法是一运算序列，它应有：有限性、____确定性____、可行性、可以无任何输入，但必须___有输出____。
4、由一棵二叉树的前序序列和____中序序列____可唯一确定这棵二叉树的结构。
5、如果图的存储结构用____邻接表/邻接矩阵___表示，从某指定顶点作为初始点进行广度优先搜索，得到的广度优先搜索序列唯一。
6、用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度____递增___的次序来得到最短路径的。
7、线性表(a1，a2，a3，??an)(n>=1)中，每个元素占c个存储单元，m为a1首地址，则按顺序存储方式存储线性表，ai存储地址是_____m+(i-1)*c___。 8、n个结点的无向图，最多有___n*(n-1)/2__条边。 三、应用题 (本大题共4小题，每小题8分，共32分)
1、用Prim算法求下图连通的带权图的最小代价生成树，在算法执行的某一刻，已选取的顶点集合U=[1，2，3]，边的集合 TE=[(1，2)，(2，3)]，要选取下一条权值最小的边，应当从哪些边中选择?
2、若用插入排序方法对线性表(25，84，21，47，]5，27，68，35，20)进行排序时，请给出前四趟排序结点序列的变化情况。 答：25
25 84 21 25 84 21 25 47 84 3、已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，请画出该二叉树。
A / \\
BDCE FHG 中 DECB HGF 后
4、设将整数a，b，c，d依次进栈，请回答：若入、出栈次序为 Push(a)，Pop()，Push(b)，Push(c)，Pop()，Push(d)，Pop()， 则出栈的字符序列是什么? 答：acd
四、算法设计 (本大题共3小题，每小题8分，共24分)
1、二叉树以二叉链表为存储结构，类型声明如下，请写出一个求二叉树中结点个数的算法。
typedef struct node{ datatype data；
struct node *Lchild； struct node *Rchild； }BinaTree；
答：int f(BinaTree *t){
if(t = = NULL) return; else
return f(t->left)+ f(t->right)+1;
}
2、设线性表用顺序结构实现，声明如下： typedef struct sqlist{ char data[maxsize]； int n；
}Sqlist;
请写一个算法，判断其是否回文?(顺读与倒读 一样如：“ababbaba\为回文) 答：
解法1：形参和实参直接传递结构变量 #include
#define MAXLENGTH 100
typedef struct sqlist{
char data[MAXLENGTH]; int n; }Sqlist;
void f(Sqlist a){ int i;
if(a.n<=0)return;
for(i=0;i<(a.n)/2;i++){
if(a.data[i]!=a.data[a.n-i]){
printf(\return;
}
printf(\ } }
void main(){ Sqlist s;
printf(\输入n: \ scanf(\
printf(\输入字符串: \ scanf(\ f(s); }
解法2：形参是指针变量，实参是结构变量地址值 void f(Sqlist *a){ int i;
if(a->n<=0)return; for(i=0;i<(a->n)/2;i++)
if(a->data[i]!=a->data[a->n-i-1]){ printf(\ return; }
printf(\}
void main(){
Sqlist s;
printf(\ scanf(\ printf(\ scanf(\ f(&s); }
解法3：类似解法2，为指针变量定义了类型List #include
#define MAXLENGTH 100
typedef struct sqlist *List;
typedef struct sqlist{
char data[MAXLENGTH]; int n; }Sqlist;
void f(List a){ int i;
if(a->n<=0)return; for(i=0;i<(a->n)/2;i++)
if(a->data[i]!=a->data[a->n-i-1]){ printf(\ return; }
printf(\}
void main(){ Sqlist s;
printf(\ scanf(\ printf(\ scanf(\ f(&s); }
3、阅读下列程序，判断它是用什么方法实现排序(升序)的?并完善下列程序。 #include
void bubble(int[],int);
main(){