2022年电大数据结构期末复习指导 .docx
《2022年电大数据结构期末复习指导 .docx》由会员分享,可在线阅读,更多相关《2022年电大数据结构期末复习指导 .docx(34页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、精选学习资料 - - - - - - - - - 一、单项选择题(每道题 2 分,共 30 分)1. 数据结构中,与所使用的运算机无关的是数据的()结构;A. 规律 B. 物理 C. 储备 D. 规律与物理2. 下述各类表中可以随机拜访的是();A. 单向链表 B. 双向链表 C. 单向循环链表 D. 次序表3. 在一个长度为 n 的次序表中为了删除第 5 个元素,从前到后依次移动了 15 个元素;就原次序表的长度为();A. 21 B. 20 C. 19 D. 25 4. 元素 2,4,6 按次序依次进栈,就该栈的不行能的输出序列是();A. 6 4 2 B. 6 2 4 C. 4 2 6
2、D. 2 6 4 5. 一个队列的入队序列是5, 6,7,8,就队列的输出序列是();A. 5 6 7 8 B. 8 7 6 5 C. 7 8 6 5 D.可能有多种情形q 所指结点是p 所指结点6. 串函数 StrCmp(“d” ,“D” )的值为();A0 B 1 C -1 D3 7在一个单链表中,p、q 分别指向表中两个相邻的结点,且的直接后继,现要删除q 所指结点,可用语句();A p=q-next B p-next=q C p-next=q-next D q-next=NULL8. 设一棵哈夫曼树共有n 个非叶结点,就该树一共有()个结点;A. 2*n-1 B. 2*n +1 C.
3、2*n D. 2*n-1 9. 对如图 1 所示二叉树进行中序遍历,结果是();A. dfebagc B. defbagc C. defbacg D.dbaefcg a d b g c c f e 图 1 10 . 任何一个无向连通图的最小生成树();A. 至少有一棵 B. 只有一棵 C.肯定有多棵 D.可能不存在11设有一个 10 阶的对称矩阵 A ,采纳压缩储备的方式,将其下三角部分以行序为主序储备到一维数组 B 中(数组下标从 1 开头),就矩阵中元素 A 8,5在一维数组 B 中的下标是();A 33 B32 C85 D 41 12 . 一组记录的关键字序列为(37, 70,47,29
4、,31,85),利用快速排序,以第一个关键字为分割元素,经过一次划分后结果为(); A 31,29,37, 85,47,70 B29,31,37,47,70, 85 C 31,29,37,70,47,85 D 31,29,37,47,70,85 13 . 对 n 个元素进行冒泡排序,要求按升序排列,程序中设定某一趟冒泡没有显现元素交换,就终止排序过程;对某 n 个元素的排序共进行了 3n-6 次元素间的比较就完成了排1 / 21 名师归纳总结 - - - - - - -第 1 页,共 21 页精选学习资料 - - - - - - - - - 序,就();A. 原序列是升序排列B. 原序列是降序
5、排列C. 对序列只进行了 2 趟冒泡D. 对序列只进行了 3 趟冒泡14在一个栈顶指针为 top 的链栈中删除一个结点时,用 x 储存被删除的结点,应执行();A.x=top-data;top=top-next; B.top=top-next ; x=top ;C.x=top ;top=top-next ; D.x=top-data;15串函数 StrCat(a,b)的功能是进行串(); A 比较 B复制 C赋值 D连接二、填空题(每道题2 分,共 24 分)s 所指的新结点,应执行s-next=p-1在一个单向链表中p 所指结点之后插入一个next ;和 _操作;2依据数据元素间关系的不同特
6、性,通常可分为_、四类基本结构;3在一个链队中,设 f 和 r 分别为队头和队尾指针,就删除一个结点的操作为_ ;结点的指针域为 next 4._ 遍历二叉排序树可得到一个有序序列;5. 一棵有 2n-1 个结点的二叉树,其每一个非叶结点的度数都为 个叶结点;2,就该树共有 _6. 如图 1 所示的二叉树,其中序遍历序列为 _ _;a b c d g e h f i 图 1 7. 对稀疏矩阵进行压缩储备,矩阵中每个非零元素所对应的三元组包括该元素的_ 、_和_三项信息;8 . 有一个有序表 2,3,9,13,33,42,45,63,74,77,82,95,110,用折半查找法查找值为82 的结
7、点,经 _次比较后查找胜利;9 . 图的深度优先搜寻和广度优先搜寻序列不是唯独的;此断言是 _的; 回答正确或不正确 10哈希法既是一种储备方法,又是一种;1144.在对一组记录 55,39,97,22,16,73,65,47,88 进行直接插入排序时,当把第 7 个记录 65 插入到有序表时,为查找插入位置需比较 _次;2 / 21 名师归纳总结 - - - - - - -第 2 页,共 21 页精选学习资料 - - - - - - - - - 12栈和队列的操作特点分别是 _和 _;三、综合题(每道题 10 分,共 30 分)1已知序列 11 ,19,5,4, 7,13,2,10 ,(1)
8、试给出用归并排序法对该序列作升序排序时的每一趟的结果;( 2)对上述序列用堆排序的方法建立初始堆(要求小根堆,以二叉树描述建堆过程);2设有序表为(13, 19, 25, 36, 48, 51,63,84,91,116,135,200),元素的下标依次为 1,2, ,12. (1)说出有哪几个元素需要经过3 次元素间的比较才能胜利查到(2)画出对上述有序表进行折半查找所对应的判定树(树结点用下标表示)(3)设查找元素5,需要进行多少次元素间的比较才能确定不能查到. 3 1 设有查找表 5,14,2,6,18,7,4,16,3, 依次取表中数据,构造一棵二叉排序树 . (2)说明如何通过序列的二
9、叉排序树得到相应序列的排序结果,对上述二叉排序给出中 序遍历的结果 . 四、程序填空题(每空 2 分,共 16 分)1以下冒泡法程序对存放在a1 ,a2 , , an 中的序列进行冒泡排序,完成程序中的空格部分,其中 n 是元素个数,程序按升序排列;Void bsort NODE a , int NODE temp ; int i,j,flag;j+ ; forj=1;( 1) flag=0; fori=1;( 2); i+ ifai.keyai+1.key flag=1; temp=ai;(3);( 4); ifflag= =0break; 程序中 flag 的功能是( 5)7以下程序是后序
10、遍历二叉树的递归算法的程序,完成程序中空格部分(树结构中左、右指针域分别为left 和 right ,数据域为data,其数据类型为字符型,BT 指向根结点);Void Postorder struct BTree Node *BT ifBT.=NULL 3 / 21 名师归纳总结 - - - - - - -第 3 页,共 21 页精选学习资料 - - - - - - - - - (1);(2);(3); 试卷答案;一、单项选择题(每道题 2 分,共 30 分)1A 2 D 3 B 4 B5A 6 C 7 C 8 B 9 A 10 A 11A 12 D 13 D 14 A 15 D 二、填空题
11、(每道题 2 分,共 24 分)1.p-next=s;2. 集合、线性、树形、图状 3. f=f-next ;4. 中序 5.n 6. dgbaechhif 7. 行号、列号、元素值 8.4 次 9. 正确 10查找方法 113 次 12先进后出 先进先出三、综合题(每道题 10 分,共 30 分)11 初始 11,19,5,4, 7,13, 2,10 第一趟 11,194 ,57 ,132 ,10 其次趟 4 ,5,11,192 ,7,10, 13 第三趟 2,4,5,7, 10,11,13,19 2 10 4 19 7 11 5 2 10 4 19 7 2 11 2 5 13 13 11
12、4 / 21 名师归纳总结 4 2 4 5 第 4 页,共 21 页- - - - - - -精选学习资料 - - - - - - - - - 2 113,36,63,135 2 1 2 3 4 6 7 9 10 11 12 5 8 33 次31 2 5 14 4 6 18 3 7 16 2 中序遍历 中序 2,3, 4,5,6,7,14,16,18 四、程序填空题(每空 2 分,共 16 分)1(1)j=n-1 5 / 21 名师归纳总结 - - - - - - -第 5 页,共 21 页精选学习资料 - - - - - - - - - (2)inext= =head Dhead-next=
13、 =NULL 3链表所具备的特点是();A可以随机拜访任一结点 B占用连续的储备空间C插入删除元素的操作不需要移动元素结点 D 可以通过下标对链表进行直接拜访4非空的单向循环链表的尾结点满意()(设头指针为head,指针p 指向尾结点); Ap-next = =NULL Bp= =NULLCp= =head D p-next= =head 5数据结构中,与所使用的运算机无关的是数据的()结构; A物理 B规律 C储备 D 规律与物理6算法的时间复杂度与()有关; A所使用的运算机 B运算机的操作系统C算法本身 D数据结构7设有一个长度为 n 的次序表,要在第 i 个元素之前插入一个元素(也就是
14、插入元素作为新表的第 i 个元素),就移动元素个数为(); A n-i+1 Bn-i Cn-i-1 Di 8设有一个长度为 n 的次序表,要删除第 i 个元素需移动元素的个数为(); An-i+1 Bn-i Cn-i-1 Di 9在一个单链表中,p、q 分别指向表中两个相邻的结点,且 q 所指结点是 p 所指结点的直接后继,现要删除 q 所指结点,可用的语句是(); Ap=q-next Bp-next=q C q-next=NULL D p-next=q-next 10在一个单链表中 p 所指结点之后插入一个 s 所指的结点时,可执行();Ap=s next Bp next=s next ;C
15、s next=p next ; p next=s ; Dp next= s ; s next= p next 11从一个栈顶指针为 top 的链栈中删除一个结点时,用变量 x 储存被删结点的植,就执行();Ax=top-data; top=top next ; B x=top-data;Ctop=top-next; x=top-data; Dtop=top-next; x=data ;6 / 21 名师归纳总结 - - - - - - -第 6 页,共 21 页精选学习资料 - - - - - - - - - 12在一个链队中,假设f和 r分别为队头和队尾指针,就删除一个结点的运算为(); A
16、r=f next ; Br=r next ; C f=f next ; Df=r next ;13在一个链队中,假设 f 和 r 分别为队头和队尾指针,就插入 s 所指结点的运算为(); A f-next=s;f=s ;B s-next=r; r=s ;C r-next=s; r=s ;D s-next=f ;f=s ;14元素 1,3,5,7 按次序依次进栈,就该栈的不行能输出序列是()(进栈出栈可以交替进行); A7,5,3,1 B7, 5,1,3 C3,1,7,5D1,3,5,7 15设有一个 18 阶的对称矩阵 A,采纳压缩储备的方式,将其下三角部分以行序为主序存储到一维数组 B 中(
17、数组下标从 1 开头),就矩阵中元素 a10,8 在一维数组 B 中的下标是();A18 B45 C 53D58 16在 C语言中,次序储备长度为 3 的字符串,需要占用()个字节; A 4 B3 C6 D12 17一棵有 n 个结点采纳链式储备的二叉树中,共有()个指针域为空; An B n+1 Cn-1 D n-2 18在一棵二叉树中,如编号为 i 的结点存在左孩子,就左孩子的次序编号为();A2i B2i-1 C2i+1 D2i+2 19设一棵哈夫曼树共有 n 个叶结点,就该树有()个非叶结点;An B2n C n-1 D n+1 20一棵具有 35 个结点的完全二叉树,最终一层有()个
18、结点; A 4 B6 C16 D8 21一棵完全二叉树共有 5 层,且第 5 层上有六个结点,该树共有()个结点; A30 B20 C 21 D23 22在一个无向图中,全部顶点的度数之和等于边数的()倍; A3 B2 C2.5 D 1.5 23已知如图 1 所示的一个图,如从顶点 a 动身,按深度优先搜寻法进行遍历,就可能得到的一种顶点序列为(); Aabecdf Bacfebd Caedfcb D aebcfd a b e c d f 图 1 24已知如图3 所示的一个图,如从顶点V1 动身,按广度优先法进行遍历,就可能得到的7 / 21 名师归纳总结 - - - - - - -第 7 页
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022年电大数据结构期末复习指导 2022 电大 数据结构 期末 复习 指导
限制150内