for(I=1;I<=n;I++)
for(j=1;j<=n;j++) a[I][j]=0;
for(I=1;I<=n;I++)
{ p=adjlist[I].firstarc; while (p!=NULL) { a[I][p->adjvex]=1; p=p->nextarc; } }}
习
一、选择题：
题七
1、对有18个元素的有序表作二分（折半）查找，则查找A[3]的比较序列的下标为_____。 A、 1、2、3 B、 9、5、2、3 C、 9、5、3 D、 9、4、2、3 2、从具有n个结点的二叉排序树中查找一个元素时，最坏情况下的时间复杂性为_____。 A、O(n) B、O(1) C、O(log2n) D、O(n2)
3、有数据{53，30，37，12，45，24，96}，从空二叉树开始逐个插入数据来开成二叉排序树，若希望高度最小，则应选择下面哪个序列输入_____。 A、45,24,53,12,37,96,30 B、37,24,12,30,53,45,96
C、12,24,30,37,45,53,96 D、30,24,12,37,45,96,53
4、利用逐点插入法建立序列{50，72，43，85，75，20，35，45，65，30}对应的二叉排序树以后，查找元素35要进行_____元素间的比较。 A、4次 B、5次 C、7次 D、10次
5、在非空m阶B-树上，除根结点以外的所有其他非终端结点_____
A、至少有?m/2?棵子C、至少有 棵子树 足够大)中进行顺序查找，其查找不成功_____。
A、(n+1)/2 B、n/2+1 C、n D、n+1
7、采用二分检索方法检索长度为n的有序表，检索每个元素时的平均比较次数与对应的判定树高度（设高度≥2相比较为_____。
A、小于 B、大于 C、等于 D、大于等于 8、对线性表进行二分检索时，要求线性表必须_____。
A、以顺序存储方式存储 B、以链式存储方式存储
C、以顺序存储方式存储且数据有序 D、以链式存储方式存储且数据有序 9、在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为_____。 A、 N B、log2n C、(h+1)/2 D、h 10、分块查找的时间效率_____。
A、低于二分查找 B、高于顺序查找而低于二分查找 C、高于顺序查找 D、低于顺序查找而高于二分查找
二、填空题 1、一个无序序列可以通过构造一棵_____树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。
35
?m/2?B、至多有?m/2?棵子树 D、至多有 ? m / 2 ? 棵子树 6、在顺序表(n的平均长度是
2、已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用二分法查找90时，需进行_____次查找可确定成功；查找47时需进行_____次查找可确定成功；查找100时，需进行_____次查找可确定成功。
3、在一棵二叉排序树上实施 遍历后，其关键字序列是一个有序表。
4、对长度为n的查找表进行查找时，假定查找第I个元素的概率为pi，查找长度（即在查找过程中依次同有关元素比较的总次数）为ci,则在查找成功情况下的平均查找长度的计算公式为 。
5、一棵深度为h的B-树，任一个叶子结点所处的层数为 ，当向B-树中插入一个新关键字时，为检索插入位置需读取 个结点。 参考答案： 一、
选择题
1、D 2、A 3、B 4、A 5、C 6、D 7、C 8、C 9、D 10、B 二、 填空题：
1、二叉排序树 2、2 4 3 3、中序 4、 (p1c1+p2c2+…+pncn) 5、h h
习
一、
选择题：
题八
1、采用简单选择排序，比较次数与移动次数分别是_____
A、O(n) ,O(log2n) B、O(log2n),O(n2) C、O(n2),O(n) D、O(nlog2n),O(n) 2、归并排序中，归并的趟数是_____。
A、O(n) B、O(log2n) C、O(nlog2n) D、O(n2)
3、在待排序的元素序列基本有序的前提下，效率最高的排序方法是_____。
A、插入排序 B、选择排序 C、快速排序 D、归并排序 4、直接插入排序在最好情况下的时间复杂度为_____。
A、O(log2n) B、O(n) C、O(nlog2n) D、O(n2)
5、就平均性能而言，目前最好的内排序方法是_____排序法。
A、冒泡 B、希尔插入 C、交换 D、快速 6、若对n个元素进行直接插入排序，则进行第I趟排序过程前，有序表中的元素个数为_____。 A、 I B、I+1 C、I-1 D、1
7、若对n个元素进行直接选择排序，则进行任一趟排序的过程中，为寻找最小值元素所需要的时间复杂性为_____。
A、O(1) B、O(nlog2n) C、O(n2) D、O(n)
8、一组记录的关键字为{45，80，55，40，42，85}，则利用快速排序方法并以第一记录为基准得到一次划分结果是 _____。
A、40，42，45，55，80，85 B、42，40，45，80，55，85
C、42，40，45，55，80，85 D、42，40，45，85，55，80
9、从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）一端的方法称为 _____。
A、希尔排序 B、归并排序 C、插入排序 D、选择排序
二、填空题：
1、基于关键字比较大小的排序算法中，_____排序算法的平均时间复杂度最优。 2、对用数组存储的线性表（16，15，32，11，6，30），用快速排序算法进行由小到大排序，
36
若排序下标范围为0~5，选择元素16作为支点，调用一趟快速排序算法后，元素16在数组中的下标位置为_____。
3、排序有哪几种方法_____、_____、_____、_____、_____。 4、对n个元素进行冒泡排序时，最少的比较次数是_____。 5、在二路归并排序中，对n个记录进行归并的趟数为_____。
6、_____方法是对序列中的元素通过适当的位置交换将有关元素一次性地放置在其最终位置上。
参考答案 一、 选择题：
1、C 2、B 3、A 4、B 5、D 6、A 7、D 8、C 9、D 二、填空题：
1、快速排序 2、3 3、插入排序 交换排序 选择排序 归并排序 基数排序 4、n-1 5、[log2n] 6、快速排序
三、算法设计：
1、写出用快速排序将关键字序列{54,23,89,48,64,50,25,90,34}排序过程的每一趟结果。 初始状态： 54 23 89 48 64 50 25 90 34 第一趟排序后： [34 23 25 48 50 54 [64 90 89] 第二趟排序后： [25 23] 34 [48 50] 54 64 [90 89]
第三趟排序后： 23 25 34 48 50 54 64 89 90 2、有一种简单的排序算法，叫做计数排序（count sorting）。这种排序算法对一个待排序的表（用数组表示）进行排序，并将排序结构存放到另一种新的表中。必须注意的是，表中所有待排序的关键字互不相同。计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小。假设对某一个记录，统计出计数值为C，那么，这个记录在新的有序表中的合适的存放位置即为C。 ⑴给出适用于计数排序的数据表定义。
⑵使用Pascal或C语言编写实现计数排序的算法。 ⑶对于有n个记录的表，关键字比较次数是多少？
⑷与简单选择排序相比，这种方法是否更好？为什么？ typedef int key[mazsize]; 算法：
void countsort(key oldlist,key newlist ,int n) { int I,j,count; for(I=0;I for(j=0;j newlist[count]=oldlist[I]; }} 基本练习题 1、 试编写出在不带头结点的单链表上实现线性表基本运算LENGTH（L）的算法。 2、 试分别以顺序表和单链表作存储结构，各写一个实现线性表的就地（即使用尽可能少的 37 附加空间）逆置的算法，在原表的存储空间内将线性表（a1,a2,a3 …,an）逆置为(an,an-1,…,a2,a1)。 3、 已知单链表L中的结点是按值非递减有序排列的，试写一算法将值为X的结点插入表L 中，使得L仍然有序。 4、 试编写实现两个串的判等运算EQUAL（S，T）。 5、 给定权值7，18，3，32，5，26，12，8，构造相应的哈夫曼树。 6、 试编写算法交换二叉树中所有结点的左、右子树。（自选存储结构） 7、 试编写从上往下，从左往右的层次遍历二叉树的算法。（已做过实验） 8、 试编写二叉树中序（或前序、后序）遍历的非第归算法。（参考教材） 9、 试写一个判别给定二叉树是否为二叉排序树的算法。 10、 11、 设计一个用链表表示的直接选择排序（或直接插入排序）算法。 插入排序中找插入位置的操作可以通过二分查找的方法来实现。试据此写一个改进 后的插入排序算法。（参考教材P207页） 12、 对下面的有向图，试给出：（1）邻接矩阵，（2）邻接表，（3）逆邻接表，（4）强连通分量，（5）从①出发的深度优先遍历序列，（6）从⑥出发的广度优先遍历序列。 13、 有一带权无向图的顶点集合为{V1，V2，V3，V4，V5，V6，V7，V8}，已知其邻 接矩阵的三元组表示如下图。 （1） 画出该无向图的邻接表。 （2） 画出所有可能的最小生成树。 （3） 根据你给的邻接表分别写出从V1出发进行深度优先遍历和广度优先遍历的顶 点序列。 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 8 2 5 1 6 8 4 5 6 3 5 7 1 3 4 2 3 7 4 6 2 12 2 12 3 5 8 2 4 8 10 8 2 2 10 3 4 7 8 7 5 第12题图 38 模拟试题 一、 选择题：（本题共10小题，每小题2分，满分20分） 1、研究数据结构就是研究 。 A、数据的逻辑结构 B、数据的存储结构 C、数据的逻辑结构和存储结构 D、数据的逻辑结构、存储结构及其数据在运算上的实现 2、已知指针p指向单链表中某一结点，将新生成的由s所指结点加到p所指结点之后，其语句应为 。 A、 s-> next=p+1; p->next=s; B、s->next=p->next;p->next=s; C、s->next=p->next;p->next=s->next; D、(*p).next=s;(*s).next=(*p).next; 3、设栈S和队列Q的初始状态为空，元素e1、e2、e3 、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2 、e4 、e3 、e6、e5、e1，则栈S的容量至少应该是 。 A、6 B、4 C、3 D、2 4、在含有n个结点和e条边的无向图的邻接矩阵中，零元素的个数为 ______________。 A、e B、n2-2e C、n2-e D、2e 5、在长度为n的顺序表中删除第i个元素（1≤ i ≤n），元素的移动次数为 。 A、n – i B、n – i + 1 C、 i D、 i – 1 6、.高度为5的完全二叉树中含有的结点数至少为 。 A、16 B、17 C、31 D、32 7、通常所说的三元组表是稀疏矩阵的一种 。 A、散列存储结构 B、链式存储结构 C、索引存储结构 D、顺序存储结构 8、具有6个顶点的无向图至少需要 条边才能确保是一个连通图。 A、6 B、7 C、5 D、8 9、一组记录的关键字为{45，80，55，40，42，85}，则利用快速排序方法并以第一记录为基准得到一次划分结果是 。 A、40，42，45，55，80，85 B、42，40，45，80，55，85 C、42，40，45，55，80，85 D、42，40，45，85，55，80 10、若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其查找成功的平均长度ASL为 。 A、（n-1）/2 B、n/2 C、n D、(n+1)/2 二、填空题：（本题共10小题，每小题2分，满分20分） 1、数据的逻辑结构有４种基本类型，即集合、 、树形结构和图形结构。 2、程序段for(i=1;i<=n;i=2*i);的时间复杂度T(n)= 。 3 、 两 个 字 符 串 相 等 的 充 分 必 要 条 是 。 39 件