2022年数据结构C语言版期末考试试题.docx

《2022年数据结构C语言版期末考试试题.docx》由会员分享，可在线阅读，更多相关《2022年数据结构C语言版期末考试试题.docx（53页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - “ 数据结构” 期末考试试题一、单项题 每道题 2 分,共 12 分 1在一个单链表 HL中,如要向表头插入一个由指针 p 指向的结点,就执行 ； A HL ps p 一next HL B p 一next HL；HLp3 C p 一next Hl；pHL； D p 一next HL一next;HL 一next p； 2n 个顶点的强连通图中至少含有 ； A.nl 条有向边 B.n 条有向边 C.nn1 2 条有向边 D.nn 一 1 条有向边 3. 从一棵二叉搜寻树中查找一个元素时,其时间复杂度大致为 ； A.O1 B.On C.O1Ogzn

2、D.On2 4由权值分别为 3,8,6,2,5 的叶子结点生成一棵哈夫曼树,它的带权路径长度为 ； A24 B48 C 72 D 53 5当一个作为实际传递的对象占用的储备空间较大并可能需要修改时,应最好把它说明为 参数,以节约参数值的传输时间和储备参数的空间； ； A.整形 B.引用型 C.指针型 D.常值引用型6向一个长度为 n 的次序表中插人一个新元素的平均时间复杂度为 AOn BO1 COn2 DO10g2n 二、填空题 每空 1 分,共 28 分 1数据的储备结构被分为、和四种； 2在广义表的储备结构中, 单元素结点与表元素结点有一个域对应不同,各自分别为域和域；3中缀表达式 3 十

3、 x*2.4 56 所对应的后缀表达式为； 4 在一棵高度为 h 的 3 叉树中,最多含有结点；5假定一棵二叉树的结点数为18,就它的最小深度为,最大深度为 6在一棵二叉搜寻树中, 每个分支结点的左子树上全部结点的值肯定该结点的值,右子树上全部结点的值肯定该结点的值； 7当向一个小根堆插入一个具有最小值的元素时,该元素需要逐层调整,直到被调整到位置为止； 8 表示图的三种储备结构为、和；名师归纳总结 9对用邻接矩阵表示的具有n 个顶点和 e 条边的图进行任一种遍历时, 其时间第 1 页,共 38 页- - - - - - -精选学习资料 - - - - - - - - - 复杂度为, 对用邻接

4、表表示的图进行任一种遍历时,其时间复杂度为； 10 从有序表 12,18,30,43,56,78,82,95 中依次二分查找 43 和 56 元素 时,其查找长度分别为和 11假定对长度 n144 的线性表进行索引次序查找, 并假定每个子表的长度均 为,就进行索引次序查找的平均查找长度为,时间复杂度为 12一棵 B树中的全部叶子结点均处在上； 13每次从无序表中次序取出一个元素,把这插入到有序表中的适当位置,此种排序方法叫做排序；每次从无序表中选择出一个最小或最大元素,把它交换到有序表的一端,此种排序方法叫做排序； 14 快速排序在乎均情形下的时间复杂度为,三、运算题 每道题 6 分,共 24

5、 分 最坏情形下的时间复杂度为； 1假定一棵二叉树广义表表示为abc ,d ,c ,8 ,分别写出对它进行先序、中序、后序和后序遍历的结果；先序：中序；后序： 2已知一个带权图的顶点集 V和边集 G分别为：0 ,1,2,3,4,5 ； V E=0,18 ,0 ,25,0 ,32 ,1 ,56,2 ,325,2 ,413,3 ,59 ,4 ,510 ,就求出该图的最小生成树的权；最小生成树的权； 3假定一组记录的排序码为46,79,56,38,40,84,50,42 ,就利用堆排序方法建立的初始堆为； 4有 7 个带权结点,其权值分别为3,7,8,2,6,10,14,试以它们为叶子结点生成一棵哈

6、夫曼树,求出该树的带权路径长度、高度、双分支结点数；带权路径长度：高度：双分支结点数：；四、阅读算法,回答疑题 每道题 8 分,共 16 分 1VOldACList&L InitListL；,ai； InsertRearL;25； InsertFrontL,50 ； IntaL45 ,8,12,15,36; forinti0; i5; i+ if ai20InsertFrontL elselnsertRearL,ai； 2该算法被调用执行后,得到的线性表L 为：void AGQueue&Q 名师归纳总结 - - - - - - -第 2 页,共 38 页精选学习资料 - - - - - - -

7、 - - InitQueueQ； inta56 ,12,5,15,8 ； forint i0;i5; i+QInsertQ,ai； QInsertQ,QDeleteQ ； QInsertQ,20 ； QInsertQ,QDeleteQ 十 16 ； while.QueueEmptyQcoutQDeleteQ” ； 该算法被调用后得到的输出结果为：五、算法填空,在画有横线的地方填写合适的内容 每道题 6 分,共 12 分 1从一维数组 An 中二分查找关键字为 K 的元素的递归算法,如查找胜利就返回对应元素的下标,否就返回一 1； IntBinschElemTypeA,Intlow ,int h

8、igh,KeyTypeK iflowhigh int midlow+high 2； ifKAmid.key； else if KdataXreturn 1; 根结点的层号为 1 向子树中查找 x 结点 else int clNodeLevelBT 一left ,X； ifcl1return cl+1; int c2； if；如树中不存在 X 结点就返回 o else return 0； 名师归纳总结 - - - - - - -第 3 页,共 38 页精选学习资料 - - - - - - - - - 六、编写算法 8 分 按所给函数声明编写一个算法, 从表头指针为 HL的单链表中查找出具有最大值

9、的结点,该最大值由函数返回,如单链表为空就中止运行； EIemType MaxValueLNOde*HL; “ 数据结构” 期末考试试题答案一、单项题 每道题 2 分,共 12 分 1评分标准；选对者得2 分,否就不得分；A B 2B 3C 4D 5B 6二、填空题 每空 1 分,共 28 分 1 2 3 4 5 6 7 8 9 10 11 12 13 14次序结构链接结构索引结构散列结构 次序无先后 值 或 data 子表指针 或 sublist 3 x 2 4 5 6 一* 十3h一 1 2 5 18 小于大于 或大于等于 向上堆顶邻接矩阵邻接表边集数组 次序无先后 On 2 Oe 1 3

10、 13 O 同一层插人选择Onlog 2n On2 三、运算题 每道题 6 分,共 24 分 1先序： a,b,c,d,e,f ,e 2 分 中序： c,b,d,a,f ,8,e 2 分 后序： c,d,b,e,f ,e,a 2 分 2 最小生成树的权： 31 6 分 384 ,79,56,42,40,46,50,38 6 分 4带权路径长度： 131 3 分 高度： 5 2 分 双分支结点数： 6 1 分四、阅读算法,回答疑题 每道题 8 分,共 16 分 评分标准：每道题正确得 8 分,显现一处错误扣 4 分,两处及以上错误不得分； 1 236 ,12,8,50,25,5,15 5 15

11、8 6 20 28 五、算法填空,在画有横线的地方填写合适的内容 每道题 6 分,共 12 分 名师归纳总结 - - - - - - -第 4 页,共 38 页精选学习资料 - - - - - - - - - 1feturn mid 2 分 returnBinschA,low,mid 一 1,K 2 分 returnBmschA,mid+1,high ,K 2 分 2NodeLevelBT 一right ,X 3 分 c2=1returnc2 十 1 3 分六、编写算法 8 分 评分标准：请参考语句后的注释,或依据情形酌情给分； ElemType MaxValueLNodeO* HL； if

12、HL=NUlL 2 分 cerrLinked llst is empty.” data ；3 分 LNOde*p=HI 一next ；4 分 whileP.：NULL 7 分 ifmaxdatamaxp 一data ； pp 一next ； returnmax；8 分 数据结构复习资料一、填空题名师归纳总结 1. 数据结构是一门讨论非数值运算的程序设计问题中运算机的操作对象数据元素的有限集合, R以及它们之间的关系和运算等的学科；2. 数据结构被形式地定义为（D, R ）,其中D 是是 D上的关系有限集合；储备结构和数据的运算3. 数据结构包括数据的规律结构、数据的第 5 页,共 38 页-

13、- - - - - -精选学习资料 - - - - - - - - - 这三个方面的内容；4. 数据结构按规律结构可分为两大类,它们分别是 线性结构 和 非线性结构；5. 线性结构中元素之间存在 一对一 关系,树形结构中元素之间存在 一对多 关系,图形结构中元素之间存在 多对多 关系；6 在线性结构中,第一个结点 没有 前驱结点,其余每个结点有且只有 1 个前驱结点；最终一个结点 没有 后续结点,其余每个结点有且只有 1 个后续结点；7. 在树形结构中,树根结点没有 前驱 结点,其余每个结点有且只有 1 个前驱结点；叶子结点没有 后续 结点,其余每个结点的后续结点数可以 任意多个；8. 在图形

14、结构中,每个结点的前驱结点数和后续结点数可以 任意多个；9数据的储备结构可用四种基本的储备方法表示,它们分别是 次序、 链式 、 索引 和 散列；10. 数据的运算最常用的有5 种,它们分别是 插入 、 删除、修改、 查找 、排序；11. 一个算法的效率可分为时间效率和空间效率；12. 在次序表中插入或删除一个元素,需要平均移动元素个数与表长和该元素在表中的位置有关；表中一半 元素,详细移动的13. 线性表中结点的集合是 有限 的,结点间的关系是 一对一 的；14. 向一个长度为 n 的向量的第 i 个元素 1 i n+1 之前插入一个元素时,需向后移动 n-i+1 个元素；15. 向一个长度

15、为 n 的向量中删除第 i 个元素 1 i n 时,需向前移动 n-i 个元素；名师归纳总结 16. 在次序表中拜访任意一结点的时间复杂度均为 O1,因此,次序表也称为第 6 页,共 38 页随机存取的数据结构；- - - - - - -精选学习资料 - - - - - - - - - 17. 次序表中规律上相邻的元素的物理位置 素的物理位置 不肯定 相邻；必定相邻；单链表中规律上相邻的元18在单链表中,除了首元结点外,任一结点的储备位置由 其直接前驱结点的链域的值 指示；19 在 n 个结点的单链表中要删除已知结点 时间复杂度为 O（n）；*p,需找到它的 前驱结点的地址 ,其20. 向量、

16、栈和队列都是 线性 结构,可以在向量的 任何 位置插入和删除元素；对于栈只能在 栈顶 插入和删除元素； 对于队列只能在 队尾 插入和 队首 删除元素；21. 栈是一种特别的线性表,答应插入和删除运算的一端称为 栈顶；不允许插入和删除运算的一端称为 栈底；22. 队列 是被限定为只能在表的一端进行插入运算,在表的另一端进行删除运算的线性表；23. 不包含任何字符 （长度为 0）的串称为空串；由一个或多个空格 （仅被匹配的主串称为目标串,子串由空格符） 组成的串称为空白串；24. 子串的定位运算称为串的模式匹配；称为模式；名师归纳总结 - - - - - - -25. 假设有二维数组A6 8,每个

17、元素用相邻的6 个字节储备,储备器按字节编址；已知 A的起始储备位置（基地址）为 1000,就数组 A的体积（储备量）为 288 B ；末尾元素 A57的第一个字节地址为 1282 ；如按行储备时,元素A14的第一个字节地址为 8+4 6+1000=1072 ；如按列储备时,元素A47的第一个字节地址为 6 74 61000）1276 ；26 由个结点所构成的二叉树有5种形状；27. 一棵深度为6 的满二叉树有n1+n2=0+ n 2= n 0-1=31 个分支结点和26-1 =32第 7 页,共 38 页精选学习资料 - - - - - - - - - 个叶子；注：满二叉树没有度为 1 的结

18、点,所以分支结点数就是二度结点数；28 一棵具有个结点的完全二叉树,它的深度为 9；（ 注：用 log 2n +1= 8.xx +1=929设一棵完全二叉树有 700 个结点,就共有 350 个叶子结点；答：最快方法：用叶子数n/2 350 30 设一棵完全二叉树具有 1000 个结点,就此完全二叉树有 500 个叶子结点,有 499 个度为 2 的结点,有 1 个结点只有非空左子树,有 0 个结点只有非空右子树；答：最快方法：用叶子数n/2 500 ,n2=n0-1=499； 另外,最终一结点为2i属于左叶子,右叶子是空的,所以有1 个非空左子树；完全二叉树的特点打算不行能有左空右不空的情形

19、,所以非空右子树数0.31在数据的存放无规律而言的线性表中进行检索的正确方法是 次序查找（线性查找）；32. 线性有序表（ a1,a2,a3, , a256 是从小到大排列的,对一个给定的值 k,用二分法检索表中与 k 相等的元素,在查找不胜利的情形下, 最多需要检索 8 次；设有 100 个结点,用二分法查找时,最大比较次数是 7；33. 假设在有序线性表 a20 上进行折半查找, 就比较一次查找胜利的结点数为 1；比较两次查找胜利的结点数为 2；比较四次查找胜利的结点数为 8；平均查找长度为3.7；解：明显,平均查找长度 O（log 2n）topm0 B）17. 判定一个栈 ST（最多元素

20、为 m0）为空的条件是 ST-top0 ST-top=0 ST-top=m0 （C ）18. 在一个图中,全部顶点的度数之和等于图的边数的倍；（ A1/2 B. 1 C. 2 D. 4 B）19. 在一个有向图中,全部顶点的入度之和等于全部顶点的出度之和的倍；（B A1/2 B. 1 C. 2 D. 4 ）20. 有 8 个结点的无向图最多有条边； A14 B. 28 C. 56 D. 112 （C）21. 有 8 个结点的有向完全图有条边； A14 B. 28 C. 56 D. 112 名师归纳总结 （B）22在表长为的链表中进行线性查找,它的平均查找长度为第 14 页,共 38 页. ;

21、. （）; - - - - - - -精选学习资料 - - - - - - - - - . n ; . （）（A）23折半查找有序表（ 4,6,10,12,20,30,50,70,88,100）；如查找表中元素 58,就它将依次与表中比较大小,查找结果是失败；A20,70,30,50 B30,88,70,50 C20,50 D30,88,50 （C）24对 22 个记录的有序表作折半查找,当查找失败时,至少需要比较次关键字；A3 B4 C5 D 6 随机（A）25. 链表适用于查找次序,也能二分法 DA次序 B二分法 C数据结构与算法复习题一、选择题；1在数据结构中,从规律上可以把数据结构分为

22、 C ；A动态结构和静态结构 B紧凑结构和非紧凑结构C线性结构和非线性结构 D内部结构和外部结构2数据结构在运算机内存中的表示是指 A ；A数据的储备结构 B数据结构 C数据的规律结构 D 数据元素之间的关系名师归纳总结 3在数据结构中,与所使用的运算机无关的是数据的 A 结构； C ；A规律 B储备 C规律和储备 D物理4在储备数据时,通常不仅要储备各数据元素的值,而且仍要储备第 15 页,共 38 页A数据的处理方法 B数据元素的类型- - - - - - -精选学习资料 - - - - - - - - - C数据元素之间的关系 D数据的储备方法5在打算选取何种储备结构时,一般不考虑 A

23、；A各结点的值如何 B结点个数的多少C对数据有哪些运算 D所用的编程语言实现这种结构是否便利；6以下说法正确选项 D ；A数据项是数据的基本单位 B数据元素是数据的最小单位 C数据结构是带结构的数据项的集合 D一些表面上很不相同的数据可以有相同的规律结构7算法分析的目的是 C ,算法分析的两个主要方面是 A ；（1）A找出数据结构的合理性 B讨论算法中的输入和输出的关系分析算法的易读性和文档性C分析算法的效率以求改进 C正确性和简明性（2）A空间复杂度和时间复杂度 B数据复杂性和程序复杂性 C可读性和文档性 D2 8下面程序段的时间复杂度是 On；s =0; for I =0; in; i+

24、forj=0;jn;j+ s +=Bij; sum = s ; 9下面程序段的时间复杂度是 On*m ；名师归纳总结 - - - - - - -第 16 页,共 38 页精选学习资料 - - - - - - - - - for i =0; in; i+ forj=0;jm;j+ Aij 0; Olog3n ；10下面程序段的时间复杂度是i 0 ；while （i=n ）i = i * 3； B ；11在以下的表达中,正确选项A线性表的次序储备结构优于链表储备结构 B二维数组是其数据元素为线性表的线性表 C栈的操作方式是先进先出 D队列的操作方式是先进后出12通常要求同一规律结构中的全部数据元素具有相同的特性,这意味着