《数据结构与算法》期末试卷（三）.PDFVIP

《数据结构与算法》期末试卷（三） 一、 单选题（每小题2 分，共8 分） 1、在一个长度为n 的顺序线性表中顺序查找值为x 的元素时，查找成功时的平 均查找长度（即x 与元素的平均比较次数，假定查找每个元素的概率都相等）为 ( B ) 。 A n B n/2C (n+1)/2D (n-1)/2 2 、在一个单链表中,若q 所指结点是p 所指结点的前驱结点,若在q 与p 之间插入 一个s 所指的结点,则执行( A ) 。 A s→link=p→link; p→link=s;B p→link=s; s→link=q; C p→link=s→link; s→link=p;D q →link=s; s→link =p; 3、 栈的插入和删除操作在（ ）进行。 A 栈顶 B 栈底 C 任意位置 D 指定位置 4 、 由权值分别为11，8，6，2 ，5 的叶子结点生成一棵哈夫曼树，它的带权路 径长度为（ ） A 24 B 71 C 48 D 53 二、 填空题（每空1 分，共32 分） 1、数据的逻辑结构被分为__________ 、___________ 、________和________ 四种。 2 、一种抽象数据类型包括______________和_____________两个部分。 3、在下面的数组a 中链接存储着一个线性表，表头指针为a[o].next，则该线 性表为_________________________________________________ 。 a 0 1 2 34 5 6 7 8 data 60 56 42 38 74 25 next 4 3 7 6 2 0 1 4 、在以HL 为表头指针的带表头附加结点的单链表和循环单链表中，判断链 表为空的条件分别为________________和____________________ 。 5、用具有 n 个元素的一维数组存储一个循环队列，则其队首指针总是指向 队首元素的___________ ，该循环队列的最大长度为__________ 。 6、当堆栈采用顺序存储结构时，栈顶元素的值可用———————表示； 当堆栈采用链接存储结构时，栈顶元素的值可用_______________表示。 7、一棵高度为5 的二叉树中最少含有_________个结点，最多含有________ 个结点； 一棵高度为 5 的理想平衡树中，最少含有_________个结点，最多含有 _________个结点。 8、在图的邻接表中，每个结点被称为____________ ，通常它包含三个域： 一是_____________ ；二是___________ ；三是_____________ 。 9 、在一个索引文件的索引表中，每个索引项包含对应记录的_________和 ___________两项数据。 10、 假定一棵树的广义表表示为 A （B （C ，D （E ，F ，G ），H （I，J ）））， 则树中所含的结点数为_________ 个，树的深度为_________, 树的度为 ________, 结点H 的双亲结点为________,孩子结点为_______________ 。 11、 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为 _________,整个堆排序过程的时间复杂度为________________ 。 12、 在对m 阶