数据结构期末复习题.docx

数据结构期末复习题.docx

《数据结构期末复习题.docx》由会员分享，可在线阅读，更多相关《数据结构期末复习题.docx（5页珍藏版）》请在冰点文库上搜索。

数据结构期末复习题

数据结构期末复习题

数据结构期末复习题一、单选题1．设有两个串T和P，求P在T中首次出现的位置的串运算称作（）。

A.联接B.求子串C.字符定位D.子串定位2．88的整型数组A，其每个数组元素占2个字节，已知A[0][0]在内存中的地址是100，按列主序，A[5][6]的地址是（）。

A.192B.206C.92D.1063．一个具有767个结点的完全二叉树，其叶子结点个数为（）。

A.383B.384C.385D.3864．具有65个结点的完全二叉树的高度为（）。

（根的层次号为0）A.8B.7C.6D.55．一个数组元素a[i]与（）的种元素e的运算是（）A.head（tail（LS））B.tail（head（LS））C.head（tail（head（tail（LS））））D.head（tail（tail（head（LS））））8．串S=software,其子串的数目是（）。

A.8B.37C.36D.99.当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。

A.n-2B.n-1C.nD.n+110.设有一个n*n的对称矩阵A，将其上三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么第i行的对角元素A[i][i]存放于B中（）处。

A.（i+3）*i/2B.（i+1）*i/2C.（2n-i+1）*i/2D.（2n-i-1）*i/211．在单链表中，指针p指向元素为x的结点，实现删除x的后继的语句是（）。

A.p=p-next;B.p-next=p-next-next;C.p-next=p;D.p=p-next-next;12．下列算法的时间复杂度为（）。

for（i=1；im；i++）for（j=i+1；jn；j++）a[i][j]=i*j;A.O（m*n）B.O（n2）C.O（m2）D.O（m+n）13．研究数据结构就是研究（）。

A.数据的逻辑结构B.数据的存储结构C.数据的逻辑结构和数据的存储结构D.数据的逻辑结构、存储结构及其数据的抽象运算。

14.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。

A.数据元素具有同一特点B.不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致。

C.每个数据元素都一样。

D.数据元素所包含的数据项的个数要相等。

15．假定一个顺序循环队列的队首和队尾指针分别用front和rear表示，则判队空的条件是（）。

A.front+1==rearB.front==rear+1C.front==0D.front==rear16.假定一个顺序循环队列存储于数组A[n]中，队首和队尾指针分别用front和rear表示，则判断队满的条件是（）。

A.（rear-1）%n==frontB.（rear+1）%n==frontC.rear==（front-1）%nD.rear==（front+1）%n17．若采用邻接矩阵法存储一个N个顶点的无向图，则该邻接矩阵是一个（）。

A．上三角矩阵B.稀疏矩阵C.对角矩阵D.对称矩阵18.如果待排序序列中两个数据元素具有相同的值，在排序后它们的位置发生颠倒，则称该排序是不稳定的。

（）就是不稳定的排序方法。

A．起泡排序B．归并排序C．直接插入法排序D．简单选择排序19．在一棵具有5层的满二叉树中结点数为（）。

A．31B.32C.33D.1620.5阶B树中，每个结点最多有（）个关键码。

A．2B．3C．4D．521、在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为（）A．O（n）B．O

（1）C．O（n2）D．O（log2n）22、设单链表中结点的结构为（data,link）。

已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作？

（）A．s-link=p-link;p-link=s；B．q-link=s;s-link=p；C．p-link=s-link;s-link=p；D．p-link=s;s-link=q；23、若让元素1，2，3依次进栈，则出栈次序不可能出现（）种情况。

A．3，2，1B．2，1，3C．3，1，2D．1，3，224、一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程（）A．较快B．较慢C．相同25、树中所有结点的度等于所有结点数加（）A．0B．1C．-1D．226、在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（）A．nB．n-1C．n+1D．2*n27、对长度为n的有序单链表，若搜索每个元素的概率相等，则顺序搜索到表中任一元素的平均搜索长度为（）A．n/2B．（n+1）/2C．（n1）/2D．n/428、在无向图中定义顶点Vi与Vj之间的路径为从Vi到达Vj的一个（）A．顶点序列B．边序列C．权值总和D．边的条数29、如果只想得到1024个元素组成的序列中的前5个最小元素，那么用（）方法最快。

A．起泡排序B．快速排序C．堆排序D．直接选择排序30、设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均探查次数不超过1.5，则散列表项应能够至少容纳（）个表项。

（设搜索成功的平均搜索长度为Snl={1+1/（1-）}/2其中为装填因子）A．400B．526C．624D．676二、填空题1．在程序运行过程中不能扩充的数组是分配的数组。

这种数组在声明它时必须指定它的大小。

2．将一个n阶三对角矩阵A的三条对角线上的元素按行压缩存放于一个一维数组B中，A[0][0]存放于B[0]中。

对于任意给定数组元素A[I][J]，如果它能够在数组B中找到，则它应在位置。

3．链表适用于查找。

4．队列的插入操作在进行，删除操作在进行。

5．设有一个顺序栈S，元素S1，S2，S3，S4，S5，S6依次进栈，如果6个元素的出栈顺序为S2，S3，S4，S6，S5，S1，则顺序栈的容量至少应为。

6．通常程序在调用另一个程序时，都需要使用一个来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。

7．广义表A（（a，b，c），（d，e，f））的表尾为。

8．在一棵树中，结点没有前驱结点。

9．一棵树的广义表表示为a（b（c，d（e，f），g（h）），i（j，k（x，y））），结点k的所有祖先的结点数为个。

10．根据一组记录（56，42，50，64，48）依次插入结点生成一棵AVL树（高度平衡的二叉搜索树）时，当插入到值为的结点时需要进行旋转调整。

11.快速排序算法的最坏情况的时间复杂度是。

12.文件可以有多种不同的组织方式：

顺序文件、散列文件、和倒排文件。

13.B－树的一个变体用于文件的动态索引结构，被称为。

14.冒泡排序算法的最坏情况的时间复杂度是。

15.一棵树中结点的后根序列与对应二叉树中结点的___序列相同。

16．在具有n个结点的中根线索二叉树中，非空指针的个数是。

17.给出所有不同形态的二叉树，它们的先根序列和后根序列完全相同：

______。

18.已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为____________。

19.对于一个具有N个结点和E条边的无向图，若采用邻接表表示，则顶点表的大小为N，所有边链表中边结点的总数为。

20．判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用。

21.一棵树的广义表表示为a（b（c,d（e,f）,g（h））,i（j,k（x,y））），结点f的层数为________。

假定树根结点的层数为0。

22.一棵树按照左子女-右兄弟表示法转换成对应的二叉树，则该二叉树中树根结点肯定没有________子女。

23.含有n个结点的树有多少条边________。

24.一个连通图的生成树是该图的连通子图。

若这个连通图有N个顶点,则它的生成树有条边。

25.能够成功完全拓扑排序的图一定是一个____________。

26.数组是一种态的数据结构，其上未定义运算。

7.一棵树中结点的后根序列与对应二叉树中结点的_____序列相同。

27．在具有n个结点的中根线索二叉树中，非空指针的个数是。

三、判断题（）1.连通分量是无向图中的极小连通子图；（）2.强连通分量是有向图中的极大强连通子图；（）3.霍夫曼树一定是完全二叉树。

（）4.有n个结点的不同的二叉树有n！

棵。

（）5.折半搜索只适用于有序表，包括有序的顺序表和有序的链表。

（）6.二维数组可以视为数组元素为一维数组的一维数组。

（）7.链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，通常存储器中还有空闲存储空间，就不会产生存储溢出的问题。

（）8．在用单链表表示的链式队列中，队头在链表的链尾位置。

（）9．凡是递归定义的数据结构都可以用递归算法来实现它的操作。

（）10．当向一个小根堆（最小堆）中插入一个具有最小值的元素时，该元素需要逐层向上调整，直到被调整到堆顶位置为止。

（）11．对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（n）。

（）12．进行折半搜索的表必须是顺序存储的有序表。

（）13．一棵m阶B树中每个结点最多有m个关键码，最少有2个关键码。

（）14．在散列法中采取开散列（链地址）法来解决冲突时，其装载因子的取值一定在（0，1）之间。

（）15．一棵3阶B树是平衡的3路搜索树，反之，一棵平衡的3路搜索树是3阶B树。

（）16.若让元素1，2，3依次进栈，则出栈次序不可能出现2，1，3的情况。

（）17.假定一个链式队列的对头和对尾指针分别为front和rear，则判断对空的条件为front==rear（）18.在一个顺序存储的循环队列中,队头指针指向队头元素的后一个位置。

（）19.对于AOE网络，加速任一关键活动都能使整个工程提前完成。

（）20.由树转化成二叉树，其根的右子女指针总是空的。

四、问答题1．高度为h的满二叉树,如果按层次自上而下，同层从左到右的次序从1开始编号，试问:

（1）该树上有多少个结点？

（2）编号为i的结点的父结点（若存在）的编号是多少？

2．右图所示的二叉搜索树上

（1）依次插入28和33，画出结果二叉搜索树

（2）依次删除30和56，画出结果二叉搜索树。

3．设有n个顶点的无向连通加权图G。

（1）以顶点1为起始顶点，用普里姆算法求图G的一棵最小代价生成树，并画出之。

（2）计算该生成树的代价。

4．设有有向图如下所示。

用迪杰斯特拉算法求以顶点1为源点的单源最短路径。

要求写出一维数组d在执行该算法的过程中各步的状态。

数组d中保存最短路径的长度。

5．设有关键字序列20，40，30，60，50，70，90，对其进行直接插入排序和快速排序。

快速排序的分割元素为序列左起第一个元素。

（1）分别指出每个算法的稳定性。

（2）分别写出两种算法的排序过程。

6．设有向图G如下图所示，给出其邻接矩阵和邻接表两种存储结构；给出对上题的有向图进行拓扑排序的各种可能的拓扑序列。

7．对于一个nn的矩阵A的任一矩阵元素a[i][j]，按行存储时和按列存储时的地址之差是多少。

（若设两种存储的开始存储地址LOC（0，0）及元素所占存储单元d相同）8．设有一个求解汉诺塔（Hanoi）的递归算法voidHANOI（intn,intpeg1,intpeg2,intpeg3）{if（n==1）coutmovepeg1topeg3end1;else{HANOI（n-1,peg1,peg3,peg2）;coutmovepeg1topeg3end1;HANOI（n-1,peg2,peg1,peg3）;}}假定采用HANOI（3，1，2，3）去调用上述算法，则写出整个输出结果的前四行内容。

9．已知一棵二叉树的中序和前序序列如下，求该二叉树的后序序列。

中序序列：

c，b，d，e，a，g，i，h，j，f前序序列：

a，b，c，d，e，f，g，h，i，j后序序列：

10．对下面的有向图从顶点V1开始进行遍历，试画出遍历得到的DFS生成森林和BFS生成森林。

V1V3V4V2V5V6V7V811．设有150个表项要存储到散列表中，要求利用线性探查法解决冲突，同时要求找到所需表项的平均比较次数不超过2次。

试问散列表m至少需要设计多大？

设是散列表的装载因子，则有ASLsucc=）（a+11121m12.画出具有四个结点，高度为3的所有二叉树形，并指出其中哪些是完全二叉树。

13.设有树如下图所示，请画出其对应的二叉树14.已知对某二叉树的先序和中序遍历的序列分别为：

AFEGCBD和EFGCADB，试画出该二叉树的逻辑结构，并求其后序遍历的结点序列。

15.设有关键字序列：

18，22，32，45，47，51，77，83，86。

现采用对半搜索方法分别查找关键字45和48，则在算法执行中，它们分别与序列中哪些元素进行比较，请将与之比较的元素依次填入下表中：

16.设有权值W={3，4，6，8，11，13,23,45}，试构造一棵哈夫曼树，并计算该树的带权路径长度。

12345搜索45搜索4817.设散列表为HT[13],散列函数为H（key）=key%13。

用闭散列法解决冲突,对下列关键码序列12,23,45,57,20,03,78,31,15,36造表。

采用线性探查法寻找下一个空位,画出相应的散列表,并计算等概率下搜索成功的平均搜索长度和搜索不成功的平均搜索长度。

0123456789101112搜索成功时的平均搜索长度为：

ASLsucc=搜索不成功时的平均搜索长度为：

ASLunsucc=