数据结构课程习题汇编解答

《数据结构课程习题汇编解答》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、选择题1、若入栈序列的元素顺序为A、B、C、D、E，判断下列哪一个出栈序列是不可能的。（）A．A、B、C、D、E　　　　B.B、C、D、E、A　　C．E、A、B、C、DD.D、C、B、A、E2、某程序的时间复杂度为（3n+nlog2n+n2+8）,其数量级表示为（）。A．O（n）B．O（nlog2n）C．O（n2）D．O（log2n）3、一个循环队列的队首和队尾指针分别是front和rear,则判别队空的条件是（）A．front+1==rearB．front==rear+1C．front==0D．front==rear4、一个非空广

2、义表的表头（　　）A．不可能是子表　B．只能是子表　C．只能是原子　D.可以是子表或原子5、一个有顺序表有255个对象，采用顺序搜索法查表，平均搜索长度为（）A128B127C126D2556、设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均探查次数不超过1.5，则散列存储空间应能够至少容纳（）个表项。（搜索成功的平均搜索长度为Snl=(1+1/(1-a))/2,其中a为装填因子A400B526C624D6767、在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数

3、为()。A.4B.5C.6D.78．以下哪个数据结构不是多型数据类型（）A．栈B．广义表C．有向图D．字符串9．以下数据结构中，（）是非线性数据结构A．树B．字符串C．队D．栈10.下列数据中，（）是非线性数据结构。A．栈B.队列C.完全二叉树D.堆11．连续存储设计时，存储单元的地址（）。A．一定连续B．一定不连续C．不一定连续D．部分连续，部分不连续12．对稀疏矩阵进行压缩存储目的是（）。A．便于进行矩阵运算B．便于输入和输出C．节省存储空间D．降低运算的时间复杂度13．以下属于逻辑结构的是（）。A．顺序表B.哈希表C.有序表D

4、.单链表14．从一棵B_树删除元素的过程中，若最终引起树根结点的合并，则新树高度是（）。A．原树高度加1B．原树高度减1C．原树高度D．不确定15．在一个具有n个顶点的无向图中，要连通所有顶点则至少需要（）条边。A．nB．2nC．n-1D．n+116．在某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用()存储方式最节省运算时间。A单链表B、仅有头指针的单循环链表C、双链表D、仅有尾指针的单循环链表17．下列4种排序方法中，不稳定的方法是（　　）。A．直接插入排序　　B．冒泡排序　　C．归并排序　　D．直

5、接选择排序18．串是一种特殊的线性表，其特殊性体现在（）A.可以顺序存储B.数据元素是一个字符C.可以链接存储D.数据元素可以是多个字符19．在一个图中，所有顶点的度数之和等于所有边数的（）倍。A.1/2B.1C.2D.420．有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，（）次比较后查找成功。A.1B.2C.4D.821．一棵左右子树不空的二叉树在先序线索化后，其空指针域数为（）。A.0B.1C.2D.不确定22．在下列排序算法中，在待排序的数据表已经为有序

6、时，花费时间反而最多的是（）。A.快速排序B.希尔排序C.冒泡排序D.堆排序23．向顺序栈中压入新元素时，应当（）。A．先移动栈顶指针，再存入元素B．先存入元素，再移动栈顶指针C．先后次序无关紧要D．同时进行24．在线索二叉树中，下面说法不正确的是()A.在中序线索树中，若某结点有右孩子，则其后继结点是它的右子树的左支末端结点。B.线索二叉树是利用二叉树的n+1个空指针来存放结点前驱和后继信息的。C.每个结点通过线索都可以直接找到它的前驱和后继D.在中序线索树中，若某结点有左孩子，则其前驱结点是它的左子树的右支末端结点。25．广义表

7、A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（）。Head(Tail(Head(Tail(Tail(A)))))A.(g)B.(d)C.cD.d26．有三个数字1,2,3,将它们构成二叉树，中序遍历序列为1,2,3的不同二叉树有()种。A.5B.6C.7D.827．一个算法应该是（）。A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C.28.下面关于算法说法错误的是（）A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C.算法的可行性是指指令不能有二义性D.以上几个

8、都是错误的29.下面说法错误的是（）(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（