发布时间 : 星期日 文章DS复习题更新完毕开始阅读34159958f111f18582d05a1e
26．设有向图的顶点个数为n，则该图是有向完全图的条件是边的条数满．．．足 。
A．n (n-1) B．n(n-1)/2 C．n(n+1)/2 D．n(n+1) 27．一个有n个顶点的无向连通图的生成树，其边的条数为 。 ．．．．．
A．n-1 B．n C．n+1 D．nlogn 28．在线索化二叉树中，t所指结点没有左子树的充要条件是 。
A．t->lchild==NULL B．t->ltag==1 C．t->ltag==0 D.以上都不对 29．下列四个序列中，哪一个是堆 。
A．75,65,30,15,25,45,20,10 B．75,65,45,10,30,25,20,15 C．75,45,65,30,15,25,20,10 D．75,45,65,10,25,30,20,15 30．下列排序在一趟结束后不一定能选出一个元素放在其最终位置上的
是 。
A．选择排序 B．归并排序 C．冒泡排序 D．快速排序 31．一组记录的关键字为46，79，56，38，40，84，利用快速排序的方法，以
第一个记录为基准得到的一次划分结果为 。
A．38，40，46，56，79，84 B．40，38，46，79，56，84 C．40，38，46，56，79，84 D．40，38，46，84，56，79 32．下列叙述中，不符合m阶B树定义要求的是 。
A．根节点最多有m棵子树 B．所有叶结点都在同一层上
C．各结点内关键字均升序或降序排列 D．叶结点之间通过指针链接 三、应用题
1．设某棵二叉树的先序遍历序列为ABDFCEGH，中序遍历序列为BFDAGEHC，要求画出此二叉树并给出该二叉树的后序遍历序列。
2．设有无向连通网络G如下图所示
（1）画出其邻接矩阵存储；
（2）从顶点①搜索所得的深度优先搜索（DFS）序列和广度优先搜索（BFS）序列；
（3）请采用普里姆或克鲁斯卡尔算法画出G的最小生成树。
3．已知世界六大城市为:北京(Pe)、纽约(N)、巴黎(Pa)、 伦敦(L) 、 东京(T) 、 墨西哥(M),下表给定了这六大城市之间的交通里程:
世界六大城市交通里程表(单位:百公里)
PE PE N 109 PA 82 L 81 T 21 M 124
N PA L T M 109 82 81 21 124 58 55 108 32 58 3 97 92 55 3 95 89 108 97 95 113 32 92 89 113 （1）．画出这六大城市的交通网络图; （2）．画出该图的邻接表表示法;
（3）．画出该图按权值递增的顺序来构造的最小(代价)生成树. 4．已知某系统在通信联络中只可能出现4种字符：a,b,c,d,其概率分别为1,3,5,7。要求：
（1） 画出对应的哈夫曼树(要求左子树根结点的权小于等于右子树根结点的权) 。
（2）为这4个字符设计哈夫曼编码（要求左分支为0，右分支为1）。 （3）计算该哈夫曼树的最小加权路径长度WPL。
5．已知某系统在通信联络中只可能出现8种字符a,b,c,d,e,f,g，h，其概率分别为5，25，3，6，10，11，36，4。要求：
(1) 画出对应的哈夫曼树(要求左子树根结点的权值小于等于右子树根结点的权值) 。
(2)为8个字符设计哈夫曼编码(规定左子树编码为0，右子树编码为1)。 (3)计算该哈夫曼树的最小加权路径长度WPL。 6．已知一个二叉树的顺序存储结构图如下：
（1）请画出该二叉树； （2）写出该二叉树先序、中序遍历序列； （3）将其转化成等价的树或森林。
下标 1 结点 A 2 B 3 C 4 D 5 E 6 7 F 8 9 10 G 11 H 12 13 14 I 15 J 7．已知一有向网的邻接矩阵如下，如需在其中一个结点建立娱乐中心，要求该结点距其它各结点的最长往返路程最短，相同条件下总的往返路程越短越好，问娱乐中心应选址何处？给出解题过程。
V1?02???3?V2??032?????V3?4?0?4????V4?1??01??V5??1??03???V6???25?0?
8．AOE网可用来估算工程的完成时间，图3是某项工程AOE网的邻接表表示（V1地址为1），其中表结点第一个域为顶点，第二个域为权值。顶点V i表示事件，数字i表示事件的编号，边的数字（权值）表示活动所需的天数，求：
（1）分别画出此项工程对应的邻接矩阵和AOE网。
（2）以顶点V1出发广度遍历图G（邻接表表示）所得的顶点序列。 （3）给出图G的一个拓扑排序序列。
（4）计算此项工程各事件（顶点）的ve（vi）和vl (vi)的函数值，各活动弧
的e(ai)和l(ai)的函数值，即各事件和各活动弧的最早开始时间和最迟开始时间？
（5）根据计算结果确定此工程的关键路径及完成此工程的工期（即所需的
最少天数）？
9．给定一组关键字序列（SUN，MON，TUE，WED，THU，FRI，SAT），建立一个长度为10的哈希表，哈希函数为H(K)=(K中第一个字母在字母表中的序号)%7。要求：，并计算：对以下
（1）分别用线性探测和链地址两种方法处理冲突，画出所对应构造的哈希表
（散列表）。
（2）设每个记录的查找概率相等，分析并计算在以上两种处理冲突方法所构造的哈希表中进行查找时，查找成功的平均查找长度（ASLsucc）以及查找不成功的平均查找长度(ASLunsucc)。
10．将关键字序列（7，8，30，11，18，9，14），散列存储到散列表中，散列表的存储空间是一个下标从0开始的一个一维数组，散列函数为H(Key)=(Key×3) % P。处理冲突采用线性探测再散列法，已知装填因子为0.7。要求： （1）画出所构造的散列表（哈希表）。
（2）分别计算等概率情况下，查找成功和查找不成功的平均查找长度。 四、算法分析与设计题
1. 下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。
typedef struct {int s[100]; int top;} sqstack; void push(sqstack &stack,int x)
{ if (stack.top==m-1) printf(“overflow”); else {____________________;
_________________;}
}
2.二叉搜索树的查找——递归算法:
bool Find(BTreeNode* BST,ElemType &item) {
if (BST==NULL)
return false; //查找失败 else {if (item==BST->data){
item=BST->data;//查找成功 return ___________;} else if(item
return Find(______________,item); else return Find(_______________,item);
}//if }
3.下面程序段的功能是实现二分查找算法，请在下划线处填上正确的语句。
struct record{int key; int others;}; int bisearch(struct record r[ ], int k) {int low=0,mid,high=n-1;
while(low<=high) {
________________________________; if(r[mid].key==k) return(mid+1); else if(____________) high=mid-1; else low=mid+1;} return(0); }
4．下面是一趟快速排序的算法，待排序记录存放在记录数组r中，请在横线上填空，把算法补充完整。
int QKPass(RecordType r［］, int low， int high) { x= r［low］； /* 选择基准记录*/ while ( low { while (low< high && r［high］.key>=x.key ) high--； if (low while (low low++; if ( low r［low］=x； /*将基准记录保存到low=high的位置*/ return low; /*返回基准记录的位置*/ } /* QKPass */ 5．(1) 将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表 仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。 (2) 设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、 C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A的元素类型为整型，要求B、C表利用A表的结点）。 (3) 已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、 空间复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据 元素。 6．设计判断两个二叉树是否相同的算法。 7．已知带有表头结点的单链表，结点结构为: 假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data值，并返回1；否则，只返回0。要求： （1）描述算法的基本设计思想。 （2）根据设计思想，采用C程序设计语言描述算法，关键之处请给出简要注 释。 8．利用二叉树递归遍历算法，编写统计二叉树中叶子结点数目的算法。二叉树采用二叉链表存储的类型定义如下： typedef char datatype; typedef struct Node { datatype data; struct Node *lchild,*rchild; }BiTree; 9．设二叉排序树按照二叉链表存储，编写算法InsertBST(BSTree *&bst, KeyType k)在二叉排序树中插入一个结点。二叉排序树的链式存储结构的类型定义如下：typedef int KeyType; typedef struct Node { KeyType key; struct Node *lchild,*rchild; }BSTree;