数据结构练习(8页).doc

上传人:1595****071 文档编号:37115907 上传时间:2022-08-30 格式:DOC 页数:8 大小:177.50KB
返回 下载 相关 举报
数据结构练习(8页).doc_第1页
第1页 / 共8页
数据结构练习(8页).doc_第2页
第2页 / 共8页
点击查看更多>>
资源描述

《数据结构练习(8页).doc》由会员分享,可在线阅读,更多相关《数据结构练习(8页).doc(8页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、-一、二、三、 数据结构练习-第 8 页四、 选择题1、下面关于线性表的叙述错误的是( D )。 A.线性表采用顺序存储必须占用一片连续的存储空间B.线性表采用链式存储不必占用一片连续的存储空间C.线性表采用链式存储便于插入和删除操作的实现D.线性表采用顺序存储便于插入和删除操作的实现2、栈是一种特殊的线性表,具有( B )性质 A先进先出 B.先进后出 C.后进后出 D.顺序进出3、顺序循环队列中(数组大小为n),队头指示front指向队列的第一个元素,队尾指示rear指向队列最后一个元素的后一个位置,则循环队列中存放了n-1个元素,即循环队列满的条件是 ( B )。 A(rear+1)%n

2、=front-1 B.(rear+1)%n=front C. (rear)%n=front D.rear+1=front 4、在一个单链表中,若删除p所指结点的后续结点,则执行( A )。 A p-next=p-next-next B. p=p-next;p-next-next C.p-next=p-next D.p=p-next-next5、设某二叉树中度数为0的结点数为N0,度数为1的结点数为Nl,度数为2的结点数为N2,则下列等式成立的是( A )。 A. N0=N2+1 B.N0=Nl+N2 C. N0=N1+1 D.N0=2N1+l6、设有6个结点的无向图,该图至少应有( D )条边

3、才能确保是一个连通图。A.8 B.6 C.7 D.57、设有向无环图G中的有向边集合E=,则下列属于该有向图G的一种拓扑排序序列的是( A )。A.1,2,3,4 B. 2,3,4,1 C.1,4,2,3 D. 1,2,4,3 8、已知一个有向图如下所示,则从顶点a出发进行深度优先遍历,不可能得到的DFS序列为( A )。A.a d b e f c B. a d c e f b C.a d c e b f D.a d e f b cbecfad 9、适用于折半查找的表的存储方式及元素排列要求是( D )A.链式方式存储,元素无序 B.链式存储方式,元素有序C.顺序存储方式,元素无序D.顺序存储

4、方式,元素有序10、设一组初始记录关键字序列为(345,253,674,924,627),则用基数排序需要进行( C )趟的分配和回收才能使得初始关键字序列变成有序序列。 A. 5 B. 4 C. 3 D. 8 11、栈和队列的共同特点是( A )。 A.只允许在端点处插入和删除元素B.都是先进后出 C.都是先进先出D.没有共同点12、用链接方式存储的队列,在进行插入运算时( D ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改13、以下数据结构中哪一个是非线性结构?( D ) A. 队列 B. 栈 C. 线性表 D. 二叉树14、树最适合用来

5、表示( C )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据15、二叉树的第k层的结点数最多为( D). A 2k-1 B.2K+1 C.2K-1 D. 2k-116、设某棵二叉树的中序遍历序列为ABCD,前序遍历序列为CABD,则后序遍历该二叉树得到序列为( A )。 (A) BADC(B) BCDA(C) CDAB(D) CBDA17、下列四种排序中( C )的空间复杂度最大。 (A) 插入排序(B) 冒泡排序(C) 堆排序(D) 归并排序18、对于线性表(7,34,55,25,64,46,20,10)进行散列存储时,若选用H(K)=K

6、 %9作为散列函数,则散列地址为1的元素有( D )个, A 1 B2 C3 D419、设有6个结点的无向图,该图至少应有( A )条边才能确保是一个连通图。 A.5 B.6 C.7 D.820、设哈夫曼树中的叶子结点总数为m,若用二叉链表作为存储结构,则该哈夫曼树中总共有( B)个空指针域。 (A) 2m-1(B) 2m(C) 2m+1(D) 4m21. 对一个算法的评价,不包括如下( B )方面的内容。 A健壮性和可读性 B并行性 C正确性 D时空复杂度22. 在带有头结点的单链表HL中,要向表头插入一个由指针p指向的结点,则执行( A )。A. p-next=HL-next; HL-ne

7、xt=p; B. p-next=HL; HL=p;C. p-next=HL; p=HL; D. HL=p; p-next=HL;23. 对线性表,在下列哪种情况下应当采用链表表示?(B )A.经常需要随机地存取元素 B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变24. 一个栈的输入序列为1 2 3,则下列序列中不可能是栈的输出序列的是( C )A. 2 3 1B. 3 2 1C. 3 1 2 D. 1 2 325. AOV网是一种( D )。A有向图 B无向图 C无向无环图 D有向无环图26. 下面程序的时间复杂为( B )for(i=1,s=0;

8、 i=n; i+) t=1;for(j=1;j=i;j+) t=t*j;s=s+t; (A) O(n)(B) O(n2)(C) O(n3)(D) O(n4)27设某有向图的邻接表中有n个头结点和m个表结点,则该图中有(C )条有向边。 C(A) n(B) n-1(C) m(D) m-128设连通图G中的边集E=(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c),则从顶点a出发可以得到一种深度优先遍历的顶点序列为( B )。(A) abedfc(B) acfebd(C) aebdfc(D) aedfcb29. 快速排序在最坏情况下的时间复杂度为( D)。AO(lo

9、g2n) BO(nlog2n) C0(n) D0(n2)30. 从二叉搜索树中查找一个元素时,其时间复杂度大致为( C )。A. O(n) B. O(1) C. O(log2n) D. O(n2)五、 填空题 1、数据的物理结构主要包括 顺序储存结构和 链式储存结构 两种情况。2、设顺序线性表中有n个数据元素,删除第i个位置上的数据元素需要移动表中 n-i 个元素。3、用一维数组存放完全二叉树:ABCDEFGHI,则中序遍历该二叉树的结点序列为( HDIBEAFCG )。4、设待排序的7记录的排序码为312,126,272,226,28,165,123,从小到大直接插入排序,一趟排序的结果是:

10、( 28,126,272,226,312,165,123 )。5. 数据的逻辑结构有四种基本形态,分别是_集合_、_线性_、_树_和_图_。6 一个算法的效率可分为_时间_效率和_空间_效率。7. 在树型结构中,树根结点没有_前趋_结点,其余每个结点的有且只有_一_个前趋驱结点;叶子结点没有_后继_结点;其余每个结点的后续结点可以_多_。 8. 对于一个有n个结点的二叉树,当它为一棵_完全_二叉树时具有最小高度,即为_log2n_,当它为一棵单支树具有_最大_高度,即为_n_。9. 在一棵二叉排序树上按_中序_遍历得到的结点序列是一个有序序列。 10. 对于一棵具有n个结点的完全二叉树,若一个

11、结点的编号为i(1in),则它的左孩子结点的编号为_2i_,右孩子结点的编号为_2i+1_,双亲结点的编号为_i/2_。 11. 在线性表的散列存储中,处理冲突的常用方法有_开放定址法_和_链式法_两种。12、若用链表存储一棵二叉树时,每个结点除数据域外,还有指向左孩子和右孩子的两个指针。在这种存储结构中,n个结点的二叉树共有_2n_个指针域,其中有_n-1_个指针域是存放了地址,有_n+1_个指针是空指针。13. 在堆排序的过程中,对任一分支结点进行筛运算的时间复杂度为_O(log2n)_,整个堆排序过程的时间复杂度为_O(nlog2n)_。11、 14. 在快速排序、堆排序、归并排序中,_

12、归并_排序是稳定的。12、 15. 设无向图G中有n个顶点e条边,所有顶点的度数之和为m,则e和m有_m=2e 关系。16 已知一有向图的邻接表存储结构如下:从顶点1出发,DFS遍历的输出序列是 ,BFS遍历的输出序列是 三、应用题 1、假定有四个元素A, B, C, D依次进栈,进栈过程中允许出栈,请写出所有可能的出栈序列。2、设散列表的地址范围是 0.4 。现采用除余法为散列函数H(key)= key MOD 5, 并采用拉链法解决地址冲突,请画出元素1,13,20,5,14,33依次插入散列表的存储结构。3、下图所示的森林:(1) 将树(a)转换为相应的二叉树(2)将二叉树(b)转换为森

13、林; agbcdfagehacbdefag图a 树 图b 树 4、有向图如下所示。应用Dijkstra算法,求源点1到其它点的最短路径。图3.2 有向图迭代Sudist2dist3dist4dist5初始12345有5个权值5,3,7,11,4,试构造一棵有5个叶子结点的哈夫曼树并计算哈夫曼树的带权路径长度WPL。6、请画出下图的邻接表。 (5分)7、设有有向图G,要求给出用普里姆算法构造的最小生成树。661215127810510ADBCEFa 8、 设有一个输入数据的序列是 46, 25, 78, 62, 12, 80 , 试画出从空树起,逐个输入各个数据而生成的二叉排序树。四、程序填空1

14、、如下为二分查找的非递归算法,试将其填写完整。Int Binsch(ElemType A ,int n,KeyType K)int low=0;int high=n-1;while (low=high)int mid=_;if (K=Amid.key) return mid; /查找成功,返回元素的下标 else if (Kasq-rear=x; sq-rear= ;3、求第n项Fibonacci级数的值 1 n=1 Fibona(n)= 1 n=2 Fibona(n-1)+ Fibona(n-2) n2int Fibona ( int n ) int m; if ( ) return (1)

15、; else if (n= =2) return(1); else m= ; return (m);4、以下 程 序是后序遍历二叉树的递归算法的程序,完成程序中空格部分(树结构中,左、右指针域分别为left和right,数据域data为字符型,BT指向根结点)。void fostorder (struct BTreeNode *BT) if (BT!=NULL)(1)_;(2)_;(3)_;四、算法设计题 1、设计算法,在顺序表test中插入元素a到第i个位置。要求考虑表满情况。2、设计算法,实现二叉树的递归先序遍历。3、设计算法,实现n个整数的快速排序。4、统计出单链表HL中结点的值等于给定值X的结点数。5、 设计判断两个二叉树是否相同的算法。6、设计两个自小到大有序单链表ha,hb的合并排序算法,合并后的单链表头指针为hc。7、实现对n个整数自小到大的直接插入排序 。

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 教育专区 > 高考资料

本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

工信部备案号:黑ICP备15003705号© 2020-2023 www.taowenge.com 淘文阁