数据结构-复习资料.pdf

《数据结构-复习资料.pdf》由会员分享，可在线阅读，更多相关《数据结构-复习资料.pdf（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1/10 1.快速排序在最坏情况下的时间复杂度为（D）。AO(log2n)BO(nlog2n)CO(n)D.O(n2)2设一棵二叉树的深度为 k，则该二叉树中最多有（D）个结点。A.2k-1 B.2k C.2k-1 D.2k-1 3二叉树中第 i(i1)层上的结点数最多有（C）个。A.2i B.2i C.2i-1 D.2i-1 4设指针变量 p 指向单链表结点 A，则删除结点 A 的后继结点 B 需要的操作为（A）。A.p-next=p-next-next B.p=p-next C.p=p-next-next D.p-next=p 5设栈 S 和队列 Q 的初始状态为空，元素 E1、E2、E3

2、、E4、E5 和 E6 依次通过栈 S，一个元素出栈后即进入队列 Q，若 6 个元素出列的顺序为 E2、E4、E3、E6、E5 和 E1，则栈 S 的容量至少应该是（C）。A.6 B.4 C.3 D.2 6.设有以下四种排序方法，则（B）的空间复杂度最大。A.冒泡排序 B.快速排 C.堆排序 D.希尔排序 7设结点 A 有 3 个兄弟结点且结点 B 为结点 A 的双亲结点，则结点 B 的度数数为（B）。A.3 B.4 C.5 D.1 8根据二叉树的定义可知二叉树共有（B）种不同的形态。A.4 B.5 C.6 D.7 9对一个算法的评价，不包括如下（A）方面的内容。A并行性 B健壮性和可读性 C

3、正确性 D时空复杂度 10在二叉排序树中插入一个结点的时间复杂度为（C）。AO(1)BO(n)CO(log2n)DO(n2)11.队列是一种（B）的线性表。A先进后出 B先进先出 C只能插入 D只能删除 2/10 12采用开放定址法处理散列表的冲突时，其平均查找长度（C）。A低于链接法处理冲突 B.与链接法处理冲突相同 C高于链接法处理冲突 D高于二分查找 13.设有序顺序表中有 n 个数据元素，则利用二分查找法查找数据元素 X 的最多比较次数不超过（A）。A.log2n+1 Blog2n-1 C.log2n D.log2(n+1)14.从数据结构上讲，字符串是比较特殊的（C）。A堆栈 B 队

4、列 C线性表 D二叉树 15函数 substring(“DATASTRUCTURE”，5，9)的返回值为（A）。ASTRUCTURE BDATA CASTRUCTUR DDATASTRUCTURE 16队列是一种（B）的线性表。A先进后出 B先进先出 C只能插入 D只能删除 17对一个算法的评价，不包括如下（A）方面的内容。A并行性 B健壮性和可读性 C正确性 D时空复杂度 18.从二叉搜索树中查找一个元素时，其时间复杂度大致为（C）。A.O(n)B.O(1)C.O(log2n)D.O(n2)19采用开放定址法处理散列表的冲突时，其平均查找长度（C）。A低于链接法处理冲突 B.与链接法处理冲突

5、相同 C高于链接法处理冲突 D高于二分查找 20.设有序顺序表中有 n 个数据元素，则利用二分查找法查找数据元素 X 的最多比较次数不超过（A）。A.log2n+1 Blog2n-1 C.log2n D.log2(n+1)21下列四种排序中（D）的空间复杂度最大。A.堆 B冒泡排序 C.希尔排序 D.快速排序 22设某二叉树中度数为 0 的结点数为 N0，度数为 1 的结点数为 Nl，度数为 2的结点数为 N2，则下列等式成立的是（B）。3/10 A.N0=N1+1 B N0=N2+1 C.N0=Nl+N2 D.N0=2N1+l 23时间复杂度不受数据初始状态影响而恒为 O(nlog2n)的是

6、（B）。A.冒泡排序 B.堆排序 C.希尔排序 D.快速排序 1字符串必须以字符0表示串值的终结。2哈夫曼树中没有度数为 1 的结点。3冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。4设初始记录关键字基本有序，则快速排序算法的时间复杂度为 O(nlog2n)。5 分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。6 如果两个关键字的值不等但哈希函数值相等，则称这两个关键字为同义词。7有向图的邻接表和逆邻接表中表结点的个数不一定相等。8如果某个有向图的邻接表中第 i 条单链表为空，则第 i 个顶点的出度为零。9线性表中的所有元素都有一个前驱元素和后继元素。10带权无向

7、图的最小生成树是唯一的。11.线性表中的所有元素都有一个前驱元素和后继元素。12.非空的双向循环链表中任何结点的前驱指针均不为空。13 图的邻接矩阵法：n 个顶点需要 n*n 个单元存储边(弧)；空间效率为 O(n2)。14稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非 0 元素。15入栈操作和入队列操作在链式存储结构上实现时需要考虑栈溢出的情况。16中序遍历一棵二叉排序树可以得到一个有序的序列。17顺序表查找指的是在顺序存储结构上进行查找。4/10 1设指针变量 p 指向单链表中结点 A，指针变量 s 指向被插入的结点 X，则在结点 A 的后面插入结点 X 需要执行的语句序列：s-

8、next=p-next;p-next=s;。2.具有 n 个顶点，_ n（n1）/2_条边的图，称为完全无向图；具有 n 个顶点，_ n(n-1)_条弧的有向图，称为完全有向图。3.设输入序列为 1、2、3，则经过栈的作用后可以得到_5_种不同的输出序列。4.设二叉树中结点的两个指针域分别为 lchild 和 rchild，则判断指针变量 p 所指向的结点为叶子结点的条件是_ p-lchild=0&p-rchild=0 _。5.设二叉树中结点的两个指针域分别为 lchild 和 rchild，则判断指针变量 p 所指向的结点为叶子结点的条件是_ p-lchild=0&p-rchild=0_。6

9、.设一组初始记录关键字序列为(20，18，22，16，30，19)，则以 20 为中轴的一趟快速排序结果为_19,18,16,20,30,22_。7.for(i=1，t=1，s=0；i=n；i+)t=t*i；s=s+t；的时间复杂度为_ O(n)_。8.设有 n 个结点的完全二叉树，如果按照从自上到下、从左到右从 1 开始顺序编号，则第 i 个结点的双亲结点编号为_i/2_，右孩子结点的编号为_ 2i+1 _。9.设某无向图中顶点数和边数分别为 n 和 e，所有顶点的度数之和为 d，则e=_2d_。10.设有向图 G 的二元组形式表示为 G=（V，E），V=1，2，3，4，5，E=，则该图的一

10、种拓扑排序序列为_1,3,2,4,5_。11.设查找表中有 100 个元素，如果用二分法查找方法查找数据元素 X，则最多需要比较_7_次就可以断定数据元素 X 是否在查找表中。5/10 12设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则以 d=4 为增量的一趟希尔排序结束后的结果为_ 49，13，27，50，76，38，65，97 _。13设某棵二叉树的中序遍历序列为 ABCD，后序遍历序列为 BADC，则其前序遍历序列为_BADC_。14完全二叉树中第 5 层上最少有_1_个结点，最多有_16_个结点。15设有一组初始记录关键字序列为(50，16，23，68

11、，94，70，73)，则将它们调整成初始堆只需把16 与_50_相互交换即可。16.子串的定位运算通常称为串的_串匹配_，是串处理中最重要的运算之一 若 n 为主串长度，m 为子串长度，则串的匹配算法时间复杂度为_m*n_。17 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_ O(log2n)_，整个堆排序过程的时间复杂度为_ O(nlog2n)_。18.具有 n 个顶点，_ n（n1）/2_条边的图，称为完全无向图；具有 n 个顶点，_ n(n-1)_条弧的有向图，称为完全有向图。19 一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用

12、二分查找，查找关键字 62 时的比较次数为_2_，查找成功时的平均查找长度_ ASL=91*1+2*2+3*4+4*2)=25/9_。20设有一组初始记录关键字序列为(50，16，23，68，94，70，73)，则将它们调整成初始堆只需把16 与_50_相互交换即可。1阅读下面的算法 LinkList mynote(LinkList L)/L是不带头结点的单链表的头指针 if(L&L-next)q=L;L=Lnext;p=L;S1:while(pnext)p=pnext;6/10 pnext=q;qnext=NULL;return L;请回答下列问题：1）说明语句 S1 的功能；答：查询链表的

13、尾结点 2）设链表表示的线性表为（a1,a2,an）,写出算法执行后的返回值所表示的线性表_（a2,a3,an,a1）_。2.阅读下面算法：void ABC(BTNode*BT)if（BT）ABC(BT-left);coutdataright);该算法的功能是：_递归地后序遍历链式存储的二叉树。_。3阅读下面算法 void conversion()Stack s;int n;SElemType e;initstack(s);printf(Please input number:);scanf(“%d”,&n);while(n)push(s,n%6);n=n/6;while(!stackempt

14、y(s)7/10 pop(s,e);printf(“%d”,e);1)指出该算法的功能。答：十进制转六进制 2)若输入数据为 10，则输出结果为_14_。4.阅读下列函数 int arrange(int a,int 1,int h,int x)/1 和 h 分别为数据区的下界和上界 int i,j,t；i=1；j=h；while(ij)while(i=x)j-；while(i=x)i+；if(ij)t=aj；aj=ai；ai=t；if(aix)return i；else return i1；指出该算法的功能是。答：调整整数数组 a中的元素并返回分界值 i，使所有x 的元素均落在a1.i上，使所

15、有x 的元素均落在 ai1.h上。5.阅读下列算法 void quickpass(int r,int s,int t)int i=s,j=t,x=rs;while(ij)8/10 while(ij&rj%2=0)j=j-1;if(ij)ri=rj;i=i+1;while(ij&ri%2=1)i=i+1;if(i0)&(flag=1)flag=0;for(j=1;jrj.keyL-rj+1.key)flag=1;x=L-rj;L-rj=L-rj+1;L-rj+1=x;m-;该算法的功能是：_冒泡排序_。7.阅读下列算法 int arrange(int a,int 1,int h,int x)in

16、t i,j,t；i=1；j=h；/1 和 h 分别为数据区的下界和上界 while(ij)while(i=x)j-；9/10 while(i=x)i+；if(ij)t=aj；aj=ai；ai=t；if(ainext)for(q=p-next,s=q;q!=0;)if(q-data=p-data)s-next=q-next;free(q);q=s-next;else s=q,q=q-next;指出该算法的功能。答：在单链表中删除值相同的多余结点 9.阅读以下二叉树操作算法，指出该算法的功能。Template void BinTree ：unknown(BinTreeNode*t)BinTreeN

17、ode*p=t,*temp;if(p!=NULL)temp=pleftchild;pleftchild=prightchild;prightchild=temp;unknown(pleftchild);10/10 unknown(prightchild);该算法的功能是：_左右子树交换_。1.用克鲁斯卡尔算法分析下列无向网，画出最小生成树。2已知一个图 G 的顶点集 V 各边集 E，当它用邻接矩阵或邻接表表示时，分析按深度优先和广度优先搜索遍历得到的顶点序列。3.散列表为 HT，散列函数为 H（key）=key%d，用线性探查法解决冲突，求散列表。4.用 prim 算法画出下图的最小生成树（假设从 V1 开始计算）。编写程序。V1 V3 V7 V2 V4 V5 V6 45 42 52 65 50 60 30 70 50 40