算法与数据结构习题3

《算法与数据结构习题3》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法与数据结构》习题3一、单项选择题1.将一棵有100个结点的完全二叉树从根开始，每层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶子结点的编号为（）。A．48B．49C．50D．512.在待排序的元素序列基本有序的前提下，效率最高的排序算法是（）。A、选择排序B、插入排序C、快速排序D、归并排序3．下述哪一条是顺序存储结构的优点？（）A．存储密度大B．插入运算方便C．删除运算方便D．可方便用于各种逻辑结构的存储表示4．对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。A．O(n)O(n)B.O(

2、n)O(1)C.O(1)O(n)D.O(1)O(1)5.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）A．head==NULLB．head→next==NULLC．head→next==headD．head!=NULL第10页共10页6.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。A.不确定B.n-i+1C.iD.n-i7.有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？（）A.543612B.453126C.346521D

3、.2341568.一个具有n个顶点的连通无向图的生成树中有（）条边。A、n-1B、nC、n/2D、n+19.设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。A．线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈10.设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）。A．求子串B．联接C．匹配D．求串长第10页共10页11.串‘ababaaababaa’的next数组为（）。A．012345678999B．012121111212C．011234223456D．012301

4、232234512.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。A.13B.33C.18D.4013.已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为（）。A．-A+B*C/DEB.-A+B*CD/EC．-+*ABC/DED.-+A*BC/DE二、填空题1.在树形结构中，树根结点没有前驱结点，其余每个结点有且只有_______个前驱结点；叶子结点没有_______结点。2.若按层次顺序将一棵

5、有n个结点的完全二叉树的所有结点编号为1到n，那么，当i为_______且不等于1时，结点i的左兄弟是结点i-1，否则结点i没有左兄弟；当i<=（n-1）/2时，结点i的右子女是_______，否则结点i没有右子女。3.在单链表中，除了首元结点外，任一结点的存储位置由指示。4.将下列表达式的复杂度由小到大重新排序后的正确顺序为。A、2nB、n！第10页共10页C、n5D、10000E、n*log2n三、判断题1.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（）2.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

6、（）3.链表中的头结点仅起到标识的作用。（）4.顺序存储结构的主要缺点是不利于插入或删除操作。（）5．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（）6.即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作，所得的输出序列也一定相同。（）7.为了很方便的插入和删除数据，可以使用双向链表存放数据。（）8.链表的物理存储结构具有同链表一样的顺序。（）9.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。（）10.有n个数顺序（依次）进栈，出栈序列有Cn种，Cn=[1/（n+1）

7、]*（2n）!/[(n!)*(n!)]。（）11.栈与队列是一种特殊操作的线性表。（）12.串是一种数据对象和操作都特殊的线性表。（）13.数组不适合作为任何二叉树的存储结构。（）14.从逻辑结构上看，n维数组的每个元素均属于n个向量。（）四、简答题1.编写一个算法，对于输入的十进制非负整数，将它的二进制表示打印的算法写出来。2.写一个递归算法来计算并返回链表的长度，并在程序中做出相应的文字说明。3.给出栈的最常用的5种操作，并说明它们的功能。4.线性表有两种存储结构：一是顺序表，二是链表。试问：如果有第10页共10页n个线性表

8、同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？5.描述以下概念的区别：空格串与空串，并举例说明。6.从概念上讲，树，森林和二叉树是三种不同的数据结构，将树、森林转化为二叉树的基本目的是什么？并