(2003-2004学年第2学期)
单项选择题1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 一、
1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（ c）。 (A)、正确性 (B). 可行性 (C). 健壮性 (D). 输入性 2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（ d ）。
for(i=n-1；i>=0；i--)
for(j=0；j （C）、有序顺序表和有序单链表都可以 （D）、无限制 4．顺序存储结构的优势是（ d ）。 （A）、利于插入操作 （B）、利于删除操作 （C）、利于顺序访问 （D）、利于随机访问 5．深度为k的完全二叉树，其叶子结点必在第（ c ）层上。 （A）、k-1 （B）、k （C）、k-1和k （D）、1至k 6．具有60个结点的二叉树，其叶子结点有12个，则度过1的结点数为（ ） （A）、11 （B）、13 （C）、48 （D）、37 7．图的Depth-First Search(DFS)遍历思想实际上是二叉树（ a ）遍历方法的推广。 （A）、先序 （B）、中序 （C）、后序 （D）、层序 8．在下列链队列Q中，元素a出队的操作序列为（ a b ） front a b c d ∧ Q （A）、p=Q.front->next; p->next= Q.front->next; （B）、p=Q.front->next; Q.front->next=p->next; （C）、p=Q.rear->next; p->next= Q.rear->next; （D）、p=Q->next; Q->next=p->next; 9． Huffman树的带权路径长度WPL等于（ c ） （A）、除根结点之外的所有结点权值之和 （B）、所有结点权值之和 （C）、各叶子结点的带权路径长度之和 （D）、根结点的值 第 1 页 共 8 页 10．线索二叉链表是利用（ c ）域存储后继结点的地址。 （A）、lchild （B）、data （C）、rchild （D）、root 二、填空题 1． 逻辑结构决定了算法的 设计 ，而存储结构决定了算法的 实现 。 2． 栈和队列都是一种 特殊 的线性表，栈的插入和删除只能在 栈顶 进行。 3． 线性表（a1,a2,…,an）的顺序存储结构中，设每个单元的长度为L，元素ai 的存储地址LOC(ai)为 4． 已知一双向链表如下(指针域名为next和prior)： y x q e p 现将p所指的结点插入到x和y结点之间，其操作步骤为： ； ； ； ； 5．n个结点无向完全图的的边数为 ， n个结点的生成树的边数为 。 6．已知一有向无环图如下： D A C E B F G 任意写出二种拓扑排序序列： 、 。 7．已知二叉树的中序遍历序列为BCA，后序遍历序列为CBA，则该二叉树的先序遍历序列为 ，层序遍历序列为 。 三、应用题 1． 设散列函数H(k)=k % 13,设关键字系列为{22,12,24,6,45,7,8,13,21},要求用线性探测法处理冲突。(6分) (1) 构造HASH表。 (2) 分别求查找成功和不成功时的平均查找长度。 第 2 页 共 8 页 2． 给定表（19,14,22,15,20,21,56,10）.（8分） （1） 按元素在表中的次序，建立一棵二叉排序树 （2） 对(1)中所建立的二叉排序树进行中序遍历，写出遍历序列。 （3） 画出对(2)中的遍历序列进行折半查找过程的判定树。 3． 已知二个稀疏矩阵A和B的压缩存储三元组表如下： A B i 1 2 2 4 5 j 3 4 5 2 2 V -5 6 2 -1 9 i 2 3 4 5 5 j 5 3 1 2 5 V 2 7 3 -9 8 写出A-B压缩存储的三元组表。（5分） 4． 已知一维数组中的数据为（18,12,25,53,18）, 试写出插入排序（升序）过程。并指出具有n个元素的插入排序的时间复杂度是多少？(5分) 5． 已知一网络的邻接矩阵如下，求从顶点A开始的最小生成树。(8分，要有过程) A B C D E F A651B653C572D15764E366F246（1）求从顶点A开始的最小生成树。 （2）分别画出以A为起点的DFS生成树和BFS生成树。 6．已知数据六个字母及在通信中出现频率如下表： A 0.15 B 0.15 C 0.1 D 0.1 E 0.2 F 0.3 把这些字母和频率作为叶子结点及权值，完成如下工作(7分，要有过程)。 （1） 画出对应的Huffman树。 第 3 页 共 8 页 （2） 计算带权路径长度WPL。 （3） 求A、B、C、D、E、F的Huffman编码。 7． 已知有如下的有向网： A 2 5 B 3 E 6 4 10 6 1 2 C D 求顶点A到其它各顶点的最短路径（采用Dijkstra算法，要有过程）。（6分） 三、 设计题（30分，每题10分,用C语言写出算法，做在答题纸 上） 1． 已知线性表（a1,a2,…,an）以顺序存储结构为存储结构，其类型定义如下： #define LIST_INIT_SIZE 100 //顺序表初始分配容量 typedef struct { Elemtype *elem; //顺序存储空间基址 int length; //当前长度（存储元素个数） }SqList; 设计一个算法，删除其元素值为x的结点（假若x是唯一的）。并求出其算法的平均时间复杂度。其算法函数头部如下： Status ListDelete(Sqlist &L,Elemtype x) { …… } 2．设顺序栈如左图所示。 其中结点定义如下： top typedef struct { Elemtype *base; //栈底指针 Elemtype *top; //栈顶指针 }Stack; 设计算法，将栈顶元素出栈并存入e中． base 3．设二叉链树的类型定义如下： typedef int Elemtype; typedef struct node{ Elemtype data; 第 4 页 共 8 页 an … a2 a1 struct node *lchild, *rchild; }BinNode, *BinTree; 试写出求该二叉树叶子结点数的算法: Status CountLeaves(BinTree &root,int &n) {//n is the number of leaves …… } 答案： 选择题（每题1分） 1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 一、填空题 1．设计、实现 2．特殊、栈顶 3．LOC（a1）+(i-1)*L 4．p->next=q->next;q->next->prior=p; q->next=p;p->prior=q; 5．n(n-1)/2、n-1 6．ADCBFEG、ABCDEFFG 7．ABC、ABC 二、应用题 1 （1）Hash表（4分） 0 1 2 3 4 5 6 7 8 9 地址 13 21 6 45 7 22 关键安 7 1 2 3 1 探测次数 1 （2）查找成功的平均查找长度：（1分） （5*1+1*2+2*3+1*7）/9=20/9 查找不成功的平均查找长度：（1分） （2+1+9+8+7+6+5+4+3+2+1）/13= 2（1）、构造（3分） 19 14 22 10 15 20 56 21 (2)、10 14 15 19 20 21 22 56（2分） （3）、（3分） 第 5 页 共 8 页 10 8 3 11 24 1 12 12 1 3、(5分，每行0.5) i j v 1 3 -5 2 4 6 3 3 7 4 1 3 4 2 -1 5 2 18 5 5 8 4、 初始关键字： [18] 12 25 53 18 第 一 趟：[12 18] 25 53 18 第 二 趟：[12 18 25] 53 18 第 三 趟：[12 18 25 53] 18 第 四 趟：[12 18 18 25 53] O（n2）（1分）。 5、7分 （1）4分 A B 1 C 3 2 5 D 4 E F （2）4分 6、(1) 3分 第 6 E 页 共 8 页 F A B C D 4分） （ （2）WPL=0.1*3+0.1*3+0.2*2+0.15*3+0.15*3+03*21= (1分) （3）A：010 B：011 C：110 D：111 E：00 F；10 （3分） 12、A-B：（A、B） 1分 A-C：（A、D、C） 2分 A-D：（A、D） 1分 A-E：（A、D、E） 2分 三，设计题（20分） 1、(10分) Status ListDelete(Sqlist &L,ElemType x) { int i,j; for(i=0;i if(L->elem[i]==x) break; if(i=L->length) return ERROR; for(j=i;j 设元素个数记为n，则平均时间复杂度为： 1nn1E(ni) ni122（10分） void pop(Stack &S,Elemtype &e) { if(S.top==S.base) return ERROR; S.top--; e=*s.top; } 2、（10分） voidCountLeaves(BinTree T,int &n) { if(T) { if((!(T->lchild)&&!( T->rchild)) n++; CountLeaves (T->lchild,n); CountLeaves (T->rchild,n); 第 7 页 共 8 页 } } 第 8 页 共 8 页 因篇幅问题不能全部显示，请点此查看更多更全内容