第 1 页，共 11 页任课教师签名：命题教师签名： 系主任签名： 主管院长签名：湛江师范学院2007年－2008学年度第1学期期末考试试题A 卷(考试时间:120分钟)考试科目： 数据结构请将所有答案填写在答题卡上，交卷时请将所有试卷上交一、单选题(每小题2分，共40分)1．下列算法的时间复杂度是（ B ）。
for ( i=0; i<n; i++) c[i][j]=i+j;A O(1)B O(n)C O(log 2n)D O(n 2) 2．每一个存储结点不仅含有一个数据元素，还包含一个指针，该存储方式是（ B ）存储方式。
A 顺序B 链式C 索引D 散列 3．指针p 指向以L 为头指针的循环链表的首元素的条件是（ A ）。
A p==L B p->next==L C L->next==pD p->next==NULL4．4个元素进S 栈的顺序是A 、B 、C 、D ，进行两次Pop(S,x)操作后，栈顶元素的值是（ B ）。
A AB BC CD D5．经过下列栈的运算后GetTop(S)的值是（ A ）。
InitStack(s); Push(s,a); Push(s,b); Pop(s); A a B b C 1 D 26．栈的特点是（B ）。
A 先进先出B 后进先出C 后进后出 D 不进不出7．经过下列运算后GetHead(Q)的值是（ A ）InitQueue(Q); EnQueue(Q,a); EnQueue(Q,b);A aB bC 1D 28．一维数组的元素起始地址loc[0]=1000，元素长度为4，则loc[2]为（ C ）。
A 1000B 1010C 1008D 1020 9．二叉树第i层上最多有（ C ）个结点。
A 2iB 2i-1C 2i-1D i210．满二叉树（ A ）二叉树。
A 一定是完全B 不一定是完全C 不是D 不是完全11．二叉树按二叉链表存储，每个结点包含三个域（lchild、data、rchild），若p指针指向二叉树的根结点，经过运算while( p->rchild!=null ) p=p->rchild，则（ A ）。
A p指向二叉树的最右下方的结点B p指向二叉树的最左下方的结点C p仍指向根结点D p为null12．在具有n个结点的完全二叉树中，结点i(2i<n)的左孩子结点是（ A ）。
A 是2iB 不存在C 是2i+1 D是2i-113．有N个顶点的无向图的邻接矩阵是用（ A ）数组存储。
A N行N列B 一维C 任意行N列D N行任意列14．连通分量是（ A ）的极大连通子图。
A 无向图B 有向图C 树D 图15．最小生成树的构造可使用（A ）算法。
A prim算法B 卡尔算法C 迪杰斯特拉算法D 哈夫曼算法16．查找表是以（A ）为逻辑结构。
A 集合B 图C 文件D 树17．散列查找是由键值（ A ）确定散列表中的位置，进行存储或查找。
A 的散列函数值B 本身C 平方D 相反数18．索引顺序表的特点是顺序表中的数据（ D ）。
A 有序B 无序C 块间有序D 散列第2 页，共11 页第 3 页，共 11 页19．排序是根据（ C ）的大小重新安排各元素的顺序。
A 数组B 关键字C 元素D 结点 20．不稳定的排序方法是指在排序中，关键字值相等的不同记录间的前后相对位置（ C ）。
A 保持不变B 保持相反C 不定D 无关二、填空题(每空2分，共20分)1．已知带表头结点的单链表L ，指针P 指向L 链表中的一个结点（非首结点、非尾结点），则删除P 结点的直接后继结点的语句序列是 P->next=P->next->next ；删除尾结点的语句序列是 while(p->next->next) p=p->next; p->next=NULL; 。
2．栈S 经过运算InitStack(s); Push(s,a); Pop(s,x)后，x 的值是 a 。
3．队列Q 经过运算InitQueue(q); EnQueue(q,a); OutQueue(Q,x)后，EmptyQueue(q)的值是 TRUE 。
4．根结点的层数为 1 。
5．在树与二叉树之间的转换方法中，树的根变为二叉树的 根 。
6．将下列按关键字的值从小到大的直接选择排序算法补充完整。
Select ( list r, int n ) {for ( i=1; 语句1 i<=n ; i++) {k=i;for ( j=i+1; 语句2 j<=n ; j++)if ( r[k].key > r[j].key) 语句3 k=j; ; if ( i != k )swap ( r[k] , r[i] ); } }7．两个不同的元素存入同一个散列表，当这两个元素的散列函数相同时，称为 冲突 。
第 4 页，共 11 页三、应用题(每题6分，共30分)1．二叉树的基本形态有几种，请画出所有形态。
的前序、中序和后2．写出图1所示二叉树序遍历序列。
答：前序：ABDECF 中序：DBEACF 后序：DEBFCA3．根据图2所示邻接表，写出该图从C 点出发的深度和广度优先搜索序列。
答：深度：CDBAFE广度：CDABFE4．A 、B 、C 三个元素进S 栈的顺序是A 、B 、C ，出栈的序列是C 、B 、A ，请写出相应的操作序列。
答：A 入栈（Push(S,A)），B 入栈（Push(S,B)），C 入栈（Push(S,C)），C 出栈（Pop(S)），B 出栈（Pop(S)），A 出栈（Pop(S)）。
第 5 页，共 11 页5．假设通信的电文由字符集a 、b 、c 、d 、e 、f 、g 中的字母构成。
它们在电文中出现的频度分别为0.31、0.16、0.10、0.08、0.11、0.20、0.04，为这7个字母设计哈夫曼树。
答：图1四、程序设计题 10分建一个单链表，将10个学生的成绩放入单链表（学生的成绩从键盘上输入），然后再将单链表中的学生成绩打印出来。
#include "stdafx.h"#include<malloc.h> /* malloc()等 */#include<stdio.h> /* EOF(=^Z 或F6),NULL */ #include<math.h>#include<process.h> /* exit() */ /* 函数结果状态代码 */ #define TRUE 1 #define FALSE 0#define OK 1typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等*/typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */ typedef int ElemType;struct LNode{ElemType data;struct LNode *next;};typedef struct LNode *LinkList; /* 另一种定义LinkList的方法*/ Status InitList(LinkList *L){ /* 操作结果：构造一个空的线性表L */*L=(LinkList)malloc(sizeof(struct LNode)); /* 产生头结点,并使L指向此头结点*/if(!*L) /* 存储分配失败*/exit(OVERFLOW);(*L)->next=NULL; /* 指针域为空*/return OK;}Status ListInsert(LinkList L,ElemType e){ /* 在带头结点的单链线性表L中第i个位置之前插入元素e */int j=0;LinkList p=L,s;while(p&&p->next) /* 寻找第i-1个结点*/{p=p->next;}s=(LinkList)malloc(sizeof(struct LNode)); /* 生成新结点*/s->data=e; /* 插入L中*/p->next=s;s->next=NULL;return OK;}第6 页，共11 页第 7 页，共 11 页Status ListTraverse(LinkList L,void(*vi)(ElemType)){ /* 操作结果:依次对L 的每个数据元素调用函数vi()。
一旦vi()失败,则操作失败 */ LinkList p=L->next; while(p) {vi(p->data); p=p->next; }printf("\n");return OK; }void visit(ElemType c) /* 与main2-1.c 不同 */ {printf("%d ",c); }int main(int argc, char* argv[]) {LinkList L; int i,e;i=InitList(&L);printf("请输入10个学生的成绩：\n"); for(i=1;i<=10;i++) { scanf("%d",&e); ListInsert(L,e); }printf("在L 的表尾依次插入10个学生的成绩后，输出链表结果：L=");ListTraverse(L,visit); //************************* return 0; }第 8 页，共 11 页答题卡一、 单选题：（40分，每题2分）二、 填空题：（20分，每空2分）1．删除P 结点的直接后继结点的语句序列是：第 9 页，共 11 页删除尾结点的语句序列是：2．3．4．5．6．语句1：语句2：语句3：7．三、应用题（30分，每题6分）第10 页，共11 页第 11 页，共 11 页四、程序设计题，10分。