2022年数据结构练习.pdf

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

1、数据结构练习填空题1、 在顺序表中访问任意一个元素的时间复杂度均为O(1), 因此顺序表也称为随机存取的数据结构。2. 二维数组 a43( 下标从 0 开始), 假设 a00 的地址为 50, 数据以行序优先方式存储 ,每个元素的长度为2 字节, 则 a21 地址就是 64 。3、直接插入排序用监视哨的作用就是防止数组下标越界。4、 已知广义表 Ls=(a, (b, c), (d, e), 运用 head 与 tail 函数取出 Ls中的原子 d 的运算就是Head(Head(Tail(Tail(LS)。5. 对有 14 个元素的有序表A1 、14 进行折半查找 , 当比较到 A4时算法结束。

2、被比较元素除A4 外, 还有A3 A5 A7。6、在 AOV 网中, 顶点表示活动, 边表示活动之间的先后关系。7、有向图 G可进行拓扑排序的判别条件就是有向无环图。8、若串 S1=ABCDEFGHIJK,S2=451223,S3=#, 则执行 Substring(S1,Strlength(S3),Index(S2,12,1) 的结果就是 DEF。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 18 页 - - - - - - - - - - 数据结构练习选择题1、 在下列存储形式中 , 哪一

3、个不就是树的存储形式？( D)A. 双亲表示法 B . 孩子链表表示法C.孩子兄弟表示法 D .顺序存储表示法2、 查找 n 个元素的有序表时 , 最有效的查找方法就是 ( C ) 。A. 顺序查找 B . 分块查找C.折半查找 D . 二叉查找3、 将所示的 s 所指结点加到 p 所指结点之后 , 其语句应为 ( D)。A.s-next=p+1 ; p-next=s;B.(*p) 、next=s; (*s)、next=(*p) 、next;C.s-next=p-next ; p-next=s-next;D.s-next=p-next ; p-next=s;精品资料 - - - 欢迎下载 -

4、- - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 18 页 - - - - - - - - - - 数据结构练习4、 在有向图的邻接表存储结构中, 顶点 v 在链表中出现的次数就是( C )。A、 顶点 v 的度 B 、 顶点 v 的出度C、 顶点 v 的入度 D 、 依附于顶点 v 的边数5、算法的时间复杂度为O(nlog2n) 、空间复杂度为O(1)的排序算法就是( A)。A、堆排序B、快速排序C、归并排序D、直接选择1. 设矩阵A 就是一个对称矩阵 , 为了节省存储 , 将其下三角部分 ( 如右图所示 )按行序存放在一维数组

5、B 1, n(n-1)/2 中, 对下三角部分中任一元素 ai,j(i j), 在一维数组 B 中下标 k 的值就是 (B ): . i(i-1)/2+j-1 . i(i-1)/2+j . i(i+1)/2+j-1 .i(i+1)/2+j 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 3 页，共 18 页 - - - - - - - - - - 数据结构练习2、 由一个长度为 11 的有序表 ,按二分查找法对该表进行查找, 在表内各元素等概率情况下 , 查找成功的平均查找长度就是( C) 。A.29/1

6、1 B、 31/11 C、 33/11 D、35/113、 AVL 树就是一种平衡的二叉排序树, 树中任一结点的 ( B ) 。A、 左、右子树的高度均相同B、 左、右子树高度差的绝对值不超过1 C、 左子树的高度均大于右子树的高度D、 左子树的高度均小于右子树的高度4、 下列四种排序方法中 , 不稳定的方法就是 ( D ) 。A、 直接插入排序 B 、 冒泡排序C、 归并排序 D、 堆排序5、 设树的度为 4, 其中度为 1,2,3,4 的结点个数分别为4, 2, ,1, 1, 则T 中的叶子数为 ( D )。A. 5 B . 6 C .7 D . 8 精品资料 - - - 欢迎下载 - -

7、 - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 4 页，共 18 页 - - - - - - - - - - 数据结构练习判断题1、 顺序存储方式的优点就是存储密度大, 且插入、删除运算效率高。( F) 2、数组不适合作任何二叉树的存储结构。( F) 3、广义表的取表尾运算 , 其结果通常就是个表 , 但有时也可就是个原子。 ( F) 4、在含有 n 个结点的树中 , 边数只能就是 n-1 条。( T ) 5、所谓一个排序算法就是否稳定, 就是指该算法在各种情况下的效率就是否相差不大。 ( F) 6、简单选择排序在最好情况下的时间复杂度为O(

8、n)。( F) 7、在二叉排序树中插入一个新结点, 总就是插入到叶结点下面。( F) 8、采用线性探测处理冲突 , 当从哈希表中删除一个记录时, 不应将该记录所在位置置空 , 因为这会影响以后的查找。( T) 9、n 个数存放在一维数组A1、n 中, 在进行顺序查找时 , 这 n个数的排列有序或无序 , 其平均查找长度不同。 ( F ) 10、广义表中原子个数即为广义表的长度。( F) 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 5 页，共 18 页 - - - - - - - - - - 数据结构练

9、习将下列由三棵树组成的森林转换为二叉树。给定下列图 , 完成以下问题(1) 画出该图的邻接矩阵与邻接表(2) 根据所画的邻接表 , 从顶点 B 出发, 画出图的深度优先搜索树(3) 根据普里姆 (Prim )算法, 求它的最小生成树 (不必写出全部过程 ,在生成树中标出边生成的次序即可)精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 6 页，共 18 页 - - - - - - - - - - 数据结构练习(1) 邻接矩阵 :邻接表 :精品资料 - - - 欢迎下载 - - - - - - - - - -

10、 - 欢迎下载 名师归纳 - - - - - - - - - -第 7 页，共 18 页 - - - - - - - - - - 数据结构练习(2) 深度优先搜索树为 :(3)最小生成树 :精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 8 页，共 18 页 - - - - - - - - - - 数据结构练习输入一个正整数序列 (53,17,12,66,58,70,87,25,56,60), 试完成下列各题:(1) 构造一棵二叉排序树 , 计算查找成功的平均查找长度;(2) 依此二叉排序树 , 如何得到

11、一个从大到小的有序序列;(3) 画出在此二叉排序树中 , 删除“66”后的树结构 。(1)二叉排序树如下 :平均查找长度 ASL=(1+2X2+4X3+3X4)/10=2、9精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 9 页，共 18 页 - - - - - - - - - - 数据结构练习(2) 按照右子树根节点左子树的顺序遍历该二叉树,即可得到从大到小的顺序(3)331760122558705687将序列 25, 34, 12, 7, 15, 47, 65, 79,47+,16 中的关键字按升序重

12、新排列 , 请写出(1) 冒泡排序一趟扫描的结果(2) 以第一个元素为分界点的快速排序一趟扫描的结果(3) 堆排序所建的初始堆与第一趟排序结果。(1)25、12、7、15、34、47、65、47+、16、79(2)16、15、12、7、25、47、65、79、47+、34(3)初始堆 : 79、47+、65、34、16、47、12、7、25、15精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 10 页，共 18 页 - - - - - - - - - - 数据结构练习第一趟排序后 : 65、47+、47、

13、34、16、15、12、7、25、79(最好划出二叉树表示 )程序填空题下列算法就是建立单链表的算法, 请填写适当的语句 , 完成该功能。typedef struct Lnode ElemType data; struct Lnode *next; LNode, *LinkList; Status CreatList_L(LinkList &L, int n) / 正序输入 n 个元素的值 ,建立带表头结点的单链线性表L L=(LinkList) malloc(sizeof(LNode); if(!L) return ERROR; L-next=NULL; 精品资料 - - - 欢迎下载 -

14、- - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 11 页，共 18 页 - - - - - - - - - - 数据结构练习 p= ( 1 ) ; for(i=0;idata); (2) ; (3) ; p-next=NULL; return OK; /CreatList_L 1、 L2、 p-next = s3、 p = s精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 12 页，共 18 页 - - - - - - - - - - 数据结构练习用链

15、表实现的简单选择排序。设链表头指针为L, 链表无头结点 , 请填写适当的语句 , 完成该功能。void SelectSort(LinkList L) p=L; while(p) q=p; r=q-next; while( r ) if( (1) ) q=r; r= (2) ; tmp=q-data; q-data=p-data; p-data=tmp; p= (3) ; 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 13 页，共 18 页 - - - - - - - - - - 数据结构练习 1、 q-

16、data r-data2、 r-next3、 p-next1、栈与队列的共同特点就是( A)。A、只允许在端点处插入与删除元素B、都就是先进后出C、都就是先进先出D、没有共同点2、用链接方式存储的队列, 在进行插入运算时 ( D)、A、仅修改头指针B、头、尾指针都要修改精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 14 页，共 18 页 - - - - - - - - - - 数据结构练习 C 、仅修改尾指针D、头、尾指针可能都要修改3、以下数据结构中哪一个就是非线性结构？( D) A 、 队列 B 、

17、 栈 C 、 线性表 D 、 二叉树4、设有一个二维数组Amn, 假设A00 存放位置在644(10),A22 存放位置在 676(10), 每个元素占一个空间 , 问A33(10)存放在什么位置？脚注(10)表示用 10 进制表示 ( C ) 。 A . 688 B . 678 C . 692 D . 6965、树最适合用来表示 ( C )。 A、有序数据元素 B、无序数据元素 C、元素之间具有分支层次关系的数据 D 、元素之间无联系的数据1、二叉树的第 k 层的结点数最多为 ( D)、A.2k-1 B、2K+1 C、2K-1 D、 2k-1精品资料 - - - 欢迎下载 - - - - -

18、 - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 15 页，共 18 页 - - - - - - - - - - 数据结构练习2、若有 18 个元素的有序表存放在一维数组A19 中, 第一个元素放 A1 中, 现进行二分查找 , 则查找 A3的比较序列的下标依次为 ( D ) A、 1, 2, 3 B、 9, 5, 2, 3 C、 9, 5, 3 D、 9, 4, 2, 33、对 n 个记录的文件进行快速排序,所需要的辅助存储空间大致为(C)A、 O(1) B、 O(n) C 、 O(1og2n) D、 O(n2)4、对于线性表 (7,34,55,25,6

19、4,46,20,10)进行散列存储时 , 若选用 H(K)=K %9作为散列函数 ,则散列地址为 1的元素有 ( D)个,A.1 B.2 C.3 D.45、设有 6 个结点的无向图 , 该图至少应有 ( A )条边才能确保就是一个连通图。A、5 B 、6 C 、7 D 、8精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 16 页，共 18 页 - - - - - - - - - - 数据结构练习请画出下图的邻接矩阵与邻接表。(注意:最好从编号大的开始写起) 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 17 页，共 18 页 - - - - - - - - - - 数据结构练习画出向小根堆中加入数据4, 2, 5, 8, 3 时, 每加入一个数据后堆的变化。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 18 页，共 18 页 - - - - - - - - - -