数据结构-复习资料

1、1. 快速排序在最坏情况下的时间复杂度为（ D ）。AO(log 2n)B O(nlog 2n)CO (n)D. O (n2)2设一棵二叉树的深度为 k，则该二叉树中最多有（ D）个结点。A. 2k-1B. 2 kC.2k-1D. 2 k-13二叉树中第 i(i1) 层上的结点数最多有（C ）个。A. 2iii-1D. 2i-1B. 2C. 24设指针变量 p 指向单链表结点A，则删除结点A 的后继结点 B 需要的操作为（A ）。A. p->next=p->next->nextB. p=p->nextC. p=p->next->nextD. p->ne

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

3、）方面的内容。A 并行性B 健壮性和可读性C 正确性D 时空复杂度10在二叉排序树中插入一个结点的时间复杂度为（C ）。AO(1)BO(n)22C O(log n)DO(n )11. 队列是一种（ B ）的线性表。A先进后出B先进先出C 只能插入D只能删除112采用开放定址法处理散列表的冲突时，其平均查找长度（C ）。A低于链接法处理冲突B.与链接法处理冲突相同C 高于链接法处理冲突D高于二分查找13. 设有序顺序表中有n 个数据元素， 则利用二分查找法查找数据元素X的最多比较次数不超过（A ）。A. log 2n+1Blog 2n-1C. log2nD. log2(n+1)14. 从数据结构

4、上讲，字符串是比较特殊的（ C ）。A堆栈B 队列C线性表D二叉树15函数 substring( “DATASTRUCTURE”， 5，9) 的返回值为（ A ）。ASTRUCTUREB DATACASTRUCTURD DATASTRUCTURE16队列是一种（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采用开放定址法处理散列表的冲突时，其平均查找

5、长度（C ）。A低于链接法处理冲突B.与链接法处理冲突相同C 高于链接法处理冲突D高于二分查找20. 设有序顺序表中有n 个数据元素， 则利用二分查找法查找数据元素X的最多比较次数不超过（A ）。A. log 2n+1Blog 2n-1C. log2nD. log2(n+1)21下列四种排序中（D ）的空间复杂度最大。A. 堆B冒泡排序C. 希尔排序D.快速排序22设某二叉树中度数为 0 的结点数为 N0，度数为 1 的结点数为 Nl ，度数为 2 的结点数为 N2，则下列等式成立的是（ B ）。2A. N =N+1B N =N+1C. N0=N+ND. N0=2N+l0102l2123时间复

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

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

8、的后面插入结点 X 需要执行的语句序列： s->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 和

9、 rchild ，则判断指针变量 p 所指向的结点为叶子结点的条件是 _ p->lchild=0&&p->rchild=0_ _。6. 设一组初始记录关键字序列为 (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

10、_。9. 设某无向图中顶点数和边数分别为 n 和 e，所有顶点的度数之和为 d，则e=_2d_。10. 设有向图 G 的二元组形式表示为 G =（V ，E），V=1 ，2，3，4，5 ，E=<1,2> ，<2,4> ， <4,5>， <1,3>， <3,2>， <3,5> ，则该图的一种拓扑排序序列为_1,3,2,4,5_ 。11. 设查找表中有 100 个元素，如果用二分法查找方法查找数据元素 X ，则最多需要比较 _7_次就可以断定数据元素 X 是否在查找表中。412设一组初始记录关键字序列为(49 ， 38， 65，

11、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， 94， 70， 73) ，则将它们调整成初始堆只需把16 与_50_相互交换即可。16. 子串的定位运算通常称为串的 _串匹配 _，是串处理中最重要的运算之一若 n 为主串长度， m 为子串长度，则串的匹配算法时间复杂度为_

12、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)，查找方法用二分查找，查找关键字 62 时的比较次数为 _2_，查找成功时的平均查找长度 _ ASL=91*1+2*2+3*4+4*2)=25/9_ _。20设有一组初始记录关键字序列为(50 ，16， 23，6

13、8， 94， 70， 73) ，则将它们调整成初始堆只需把16 与_50_相互交换即可。1阅读下面的算法LinkList mynote(LinkList L) /L是不带头结点的单链表的头指针if(L&&L->next)q=L; L=L>next; p=L;S1:while(p>next) p=p >next;5p >next=q; q >next=NULL;return L;请回答下列问题：1） 说明语句 S1 的功能；答：查询链表的尾结点2）设链表表示的线性表为（a1 ,a 2,a n）, 写出算法执行后的返回值所表示的线性表 _（a2,

14、a3 ,an,a1 ）_。2. 阅读下面算法：void ABC(BTNode * BT) if（BT） ABC (BT->left);cout<<BT->data<< ;ABC (BT->right);该算法的功能是： _递归地后序遍历链式存储的二叉树。_。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

15、/6;while(!stackempty(s)6pop(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(i<j)while(i<j && aj>=x)j-；while(i<j && aj>=x)i+；if(i<j)t=aj；aj=ai；ai=t；if(ai&l

16、t;x) return i；else return i1；指出该算法的功能是。答：调整整数数组a 中的元素并返回分界值i ，使所有 x 的元素均落在a1.i上，使所有 x 的元素均落在 ai 1.h上。5. 阅读下列算法void quickpass(int r, int s, int t)int i=s,j=t,x=rs;while(i<j)7while (i<j && rj%2=0) j=j-1; if (i<j) ri=rj;i=i+1; while (i<j && ri%2=1) i=i+1; if (i<j) rj=ri;j

17、=j-1;ri=x;指出该算法的功能。答：所有奇数移到所有偶数之前6. 阅读下面算法：void myMethod(List *L) int m,i,j,flag=1; RecordType x; m=n-1; while(m>0)&&(flag=1) flag=0;for(j=1;j<=m;j+) if(L->rj.key>L->rj+1.key) flag=1;x=L->rj; L->rj=L->rj+1; L->rj+1=x;m-; 该算法的功能是： _冒泡排序 _。7. 阅读下列算法int arrange(int a,

18、 int 1, int h, int x) int i,j,t； i=1 ；j=h ；/1和 h 分别为数据区的下界和上界while(i<j)while(i<j && aj>=x)j-；8while(i<j && aj>=x)i+；if(i<j) t=aj；aj=ai； ai=t；if(ai<x) return i；else return i1；指出该算法的功能。答 :调整整数数组a 中的元素并返回分界值i ，使所有 x 的元素均落在a1.i上，使所有 x 的元素均落在 ai 1.h上。8. 阅读下列算法typedef int datatype;typedef struct node datatype data; struct node *next;lklist; void delredundant(lklist *&head)lklist *p,*q,*s;for(p=head;p!=0;p=p->next)for(q=p->next,s=q;q!=0;