《数据结构》综合练习演示教学Word格式.docx

《数据结构》综合练习演示教学Word格式.docx

《《数据结构》综合练习演示教学Word格式.docx》由会员分享，可在线阅读，更多相关《《数据结构》综合练习演示教学Word格式.docx（11页珍藏版）》请在冰点文库上搜索。

A.便于随机存取B.存储密度高

C.无需预分配空间D.便于进行插入和删除操作

4.假设在顺序表{a0,a1,……,an－1}中，每一个数据元素所占的存储单元的数目为4，且第0个数据元素的存储地址为100，则第7个数据元素的存储地址是（D）。

A.106B.107C.124D.128

5.在线性表中若经常要存取第i个数据元素及其前趋，则宜采用（A）存储方式。

A.顺序表B.带头结点的单链表

C.不带头结点的单链表D.循环单链表

6.在链表中若经常要删除表中最后一个结点或在最后一个结点之后插入一个新结点，则宜采用（C）存储方式。

A.顺序表B.用头指针标识的循环单链表

C.用尾指针标识的循环单链表D.双向链表

7.在一个含有n个结点的有序单链表中插入一个新结点，使单链表仍然保持有序的算法的时间复杂度是（C）。

O

（1）B.O（log2n）C.O（n）D.O（n2）

8.要将一个顺序表{a0,a1,……,an-1}中第i个数据元素ai（0≤i≤n-1）删除，需要移动（B）个数据元素。

A.iB.n-i-1C.n-iD.n-i+1

9.在栈中存取数据的原则是（B）。

A.先进先出B.先进后出

C.后进后出D.没有限制

10.若将整数1、2、3、4依次进栈，则不可能得到的出栈序列是（D）。

A．1234B.1324C.4321D.1423

11.在链栈中，进行出栈操作时（B）。

A．需要判断栈是否满B.需要判断栈是否为空

C.需要判断栈元素的类型D.无需对栈作任何差别

12.在顺序栈中，若栈顶指针top指向栈顶元素的存储单元，且顺序栈的最大容量是maxSize，则顺序栈的判空条件是（B）。

A．top==0B.top==-1C.top==maxSizeD.top==maxSize-1

13.在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize。

则顺序栈的判满的条件是（C）。

14.在队列中存取数据元素的原则是（A）。

A．先进先出B.先进后出

15.在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判空条件是（A）。

A．front==rearB.front!

=rear

C.front==rear+1D.front==（rear+1）%maxSize

16.在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判满条件是（D）。

C.front==rear+1D.front==（rear+1）%maxSize

17.在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的长度是（C）。

A．rear-frontB.rear-front+1

C.（rear-front+maxSize）%maxSizeD.（rear-front+1）%maxSize

18.设长度为n的链队列采用单循环链表加以表示，若只设一个头指针指向队首元素，则入队操作的时间复杂度为（B）。

A．O

（1）B．O（n）C．O（log2n）D．O（n2）

19.串的长度是指（A）

A.串中包含的字符个数B.串中包含的不同字符个数

C.串中除空格以外的字符个数D.串中包含的不同字母个数

20.设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（C）　

　A．求子串 

B．联接 

C．模式匹配 

D．求串长

21.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主进行存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（B）。

A.13B.33C.18D.40

22.7.有一个二维数组A[1..6,0..7]，每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组占用的存储空间大小是（D）个字节。

A.48B.96C.252D.288

23.在哈夫曼树中，任何一个结点它的度都是（C）。

A.0或1B.1或2C.0或2D.0或1或2

24.对一棵深度为h的二叉树，其结点的个数最多为（D）。

A.2hB.2h-1C.2h-1D.2h-1

C.只有一个根结点D.任意一棵二叉树

25.假设一棵二叉树中度为1的结点个数为5，度为2的结点个数为3，则这棵二叉树的叶结点的个数是（C）

A．2B.3C.4D.5

26.若某棵二叉树的先根遍历序列为ABCDEF，中根遍历序列为CBDAEF，则这棵二叉树的后根遍历序列为（B）。

A.FEDCBAB.CDBFEAC.CDBEFAD.DCBEFA

27.在有n个结点的二叉树的二叉链表存储结构中有（C）个空的指针域。

A．n-1B.nC.n+1D.0

28.利用二叉链表存储树，则根结点的右指针是（C）。

A．指向最左孩子B．指向最右孩子C．空D．非空

29.引入二叉线索树的目的是（A）。

A．加快查找结点的前驱或后继的速度B．为了能在二叉树中方便的进行插入与删除

C．为了能方便的找到双亲D．使二叉树的遍历结果唯一

30.设F是一个森林，B是由F变换得的二叉树。

若F中有n个非终端结点，则B中右指针域为空的结点有（C）个。

A．n−1B．nC．n+1D．n+2

31.在一个有

个顶点的有向图中，若所有顶点的出度之和为

，则所有顶点的入度之和为（A）。

A.

　　　　B.

　　　　C.

　　　　D.

32.具有6个顶点的无向图至少应有（　A　）条边才能确保是一个连通图。

A.5　　　　B.6　　　　C.7　　　　D.8

33.一个有n个顶点的无向图最多有（　C　）条边。

34..n个顶点的连通图用邻接距阵表示时，该距阵至少有（B）个非零元素。

A．nB．2（n-1）C．n/2D．n2

35.对某个无向图的邻接矩阵来说，下列叙述正确的是（A）。

A.第

行上的非零元素个数和第

列上的非零元素个数一定相等

B.矩阵中的非零元素个数等于图中的边数

C.第

行与第

列上的非零元素的总数等于顶点

的度数

D.矩阵中非全零行的行数等于图中的顶点数

.32.任何一个无向连通图的最小生成树（B）。

A.只有一棵　　　B.有一棵或多棵　　　C.一定有多棵　　　D.可能不存在

36.下面（B）方法可以判断出一个有向图是否有环。

A．深度优先遍历B．拓扑排序C．求最短路径D．求关键路径

37.对线性表进行二分查找时，要求线性表必须（B）

A.以顺序方式存储B.以顺序方式存储，且结点按关键字值有序排列

C.以链接方式存储D.以链接方式存储，且结点按关键字值有序排列

38.用二分查找法查找具有n个结点的顺序表时，查找每个结点的平均比较次数是（D）

A.O（n2）B.O（nlog2n）C.O（n）D.O（log2n）

39.若有一个长度为64的有序表，现用二分查找方法查找某一记录，则查找不成功，最多需要比较（B）次。

A.9B.7C.5D.3

40.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为（D）

A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构

41.设哈希表长为14，哈希函数是H（key）=key%11，表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的元素加到表中，用二次探测法解决冲突，则放入的位置是（D）。

A．8B．3C．5D．9

42.下面给出的四种排序算法中，（B）是不稳定的排序。

　　A．插入排序 

B．堆排序 

C．二路归并排序 

D．冒泡排序

43.在下列排序算法中，哪一种算法的时间复杂度与初始排序序列无关（D）。

　　A．直接插入排序B．冒泡排序 

C．快速排序 

D．直接选择排序

44.关键字序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中（C）的两趟排序后的结果。

　　A．选择排序 

B.冒泡排序 

C.插入排序 

D.堆排序

45.一组记录的关键字为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为支点得到的一次划分结果为（C）。

　　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）

46.在对一组关键字序列{15，33,55，100，65，50，40，95}，进行直接插入排序时，把65插入，需要比较（A）次。

A.2B.4C.6D.8

47.从待排序的序列中选出关键字值最大的记录放到有序序列中，该排序方法称为（B）。

A.希尔排序B.直接选择排序C.冒泡排序D.快速排序

48.当待排序序列基本有序时，以下排序方法中，（B）最不利于其优势的发挥。

A.直接选择排序B.快速排序C.冒泡排序D.直接插入排序

49..在待排序序列局部有序时，效率最高的排序算法是（B）。

A.直接选择排序B.直接插入排序C.快速排序D.归并排序

50.数据表中有10000个元素，如果仅要求求出其中最大的10个元素，则采用（D）算法最节省时间。

A．冒泡排序B．快速排序C．简单选择排序D．堆排序

二、填空题

1.一个串的任意连续字符组成的子序列称为串的子串，该串称为主串。

2.若两个串的长度相等且对应位置上的字符也相等，则称两个串相等。

3.寻找子串在主串中的位置，称为模式匹配。

其中，子串又称为模式串。

4.设数组A[1..5,1..6]的基地址为1000，每个元素占5个存储单元，若以行序为主序顺序存储，则元素A[5,5]的存储地址为1140。

5.一个n×

n的对称矩阵，如果以相同的元素只存储一次的原则进行压缩存储，则其元素压缩后所需的存储容量为n（n+1）/2。

6.对矩阵压缩的目的是为了节省存储空间。

7.循环顺序队列是将顺序队列的存储区域看成是一个首尾相连的环，首尾相连的状态是通过数学上的求模（或取余）运算来实现的。

8.一棵具有100个结点的完全二叉树，其叶结点的个数为50。

9.以{5，9，12，13，20，30}为叶结点的权值所构造的哈夫曼树的带权路径长度是217。

10.有m个叶结点的哈夫曼树中，结点的总数是2m-1。

11.若一棵完全二叉树的第4层（根结点在第0层）有7个结点，则这棵完全二叉树的叶子结点总数是11。

12.在深度为k的完全二叉树中至少有k个结点，至多有2k-1个结点。

13.假定待查找记录个数为n,则在等概率的情况下，顺序查找在查找成功情况下的平均查找长度为（n+1）/2；

在查找失败情况下的平均查找长度为n+1。

14.对线性表进行二分查找时，要求线性表必须以顺序方式存储，且数据有序。

15.分块查找分为两个阶段，分别是确定待查元素所在的块和在块内查找待查的元素。

16.哈希法存储中，冲突指的是不同关键字值对应到相同的存储地址。

17.一棵二叉排序树用中序遍历输出的信息是递增序列。

18.哈希法存储的基本思想是根据关键字来决定存储地址。

19.若用

表示图中顶点数，则有　

　条边的无向图称为完全图。

20.

个顶点的连通无向图至少有　

　条边，至多有　

　条边。

21.若有向图

的邻接矩阵为：

则顶点

的入度是　3　。

22.对于一个有向图，若一个顶点的度为

，出度为

，则对应逆邻接表中该顶点单链表中的边结点数为　

　。

23.在求最小生成树的两种算法中，　克鲁斯卡尔　算法适合于稀疏图。

24.数据结构中的迪杰斯特拉算法是用来求　某个源点到其余各顶点的最短路径　。

25.执行排序操作时，根据使用的存储器可将排序算法分为内排序和外排序。

26.在对一组记录序列{50,40,95,20,15,70,60,45,80}进行直接插入排序时，当把第7个记录60插入到有序表中时，为寻找插入位置需比较3次。

27.在直接插入排序和直接选择排序中，若初始记录序列基本有序，则选用直接插入排序。

28.在对一组记录序列{50,40,95,20,15,70,60,45,80}进行直接选择排序时，第4次交换和选择后，未排序记录为{50,70,60,95,80}。

29.n个记录的冒泡排序算法所需的最大移动次数为3n（n-1）/2，最小移动次数为0。

30.m阶B-树上的结点至多有m棵子树。

3、解答题（知识点）

1、循环队列的特点

2、二叉树的遍历、树和二叉树的转换

3、Huffman编码

4、图的存储及遍历

5、最小生成树

6、拓扑排序

7、折半查找

8、二叉排序树及平衡二叉树

9、哈希表

10、希尔排序，快速排序、堆排序、二路归并排序,写出一趟的结果、判断稳定否。

（参考课件）

4、算法设计

参考实验及书上经典算法