发布时间 : 星期三 文章数据结构习题1更新完毕开始阅读0c9897303968011ca30091a9
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->next;p->next=s; B、(*p).next=s;(*s).next=(*p).next; C、s->next=p->next;p->next=s->next; D、s-> next=p+1; p->next=s; 3、线性表Ｌ＝(a1, a2,?, an)，下列说法正确的是 。 A、每个元素都有一个直接前驱和一个直接后继 B、线性表中至少要有一个元素 C、表中诸元素的排列顺序必须是由小到大或由大到小 D、除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继 4、设栈的输入序列是（1、2、3、4），则 不可能是其出栈序列。 A、1243 B、2134 C、4312 D、1432 5、设有两个串p 和q，求p 在q中首次出现的位置的运算称作 。 A、连接 B、求子串 C、模式匹配 D、求串长 6、对二叉排序树进行 遍历，可以得到该二叉树所有结点构成的从小到大排序序列。 A、前序 B、中序 C、后序 D、按层次 7、按照二叉树的定义，具有3个结点的二叉树有 种。 A、5 B、6 C、4 D、3 8、一个n个顶点的连通无向图，其边的个数至少为 。 A、nlog2n B、n C、n+1 D、n-1 9、直接插入排序在最好情况下的时间复杂度为 。 A、O(log2n) B、O(n) C、O(nlog2n) D、O(n2) 10、在一棵二叉树第h层上最多有 个结点。 A、2h-1 B、2h+1 C、2h-1 D、2h 二、填空题：（本题共10小题，每小题2分，满分20分） 1、数据结构中评价算法的两个重要指标是算法的时间复杂度和______________________。 2、在线性表的单链表存储中，若一个元素所在结点地址为p，则其后继结点的地址为______________________。 3、队列是特殊的线性表，其特殊性在于______________________。 4、设二维数组a[8][10]的基地址为2000，每个元素占3个存储单元，若以行序为主序顺序存储，则元素a[6][5]的存储地址为______________________。 5、对于一棵完全二叉树采用顺序存储，设一个结点的编号为i(根结点的编号为1,若它的左孩子结点存在，则其编号为______________________。 39