资源描述：
《数据结构期末练习题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构练习题1一、单项选择题，在括号内填写所选择的标号（每小题1分，共12分）2.以下说法错误的是（）。A.抽象数据类型具有封装性。B.抽象数据类型具有信息隐蔽性。C.使用抽象数据类型的用户可以自己定义对抽象数据类型中数据的各种操作。D.抽象数据类型的一个特点是使用与实现分离。 3.设有一个n´n的对称矩阵A，将其上三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么第i行的对角元素A[i][i]存放于B中（）处。A.(i+3)*i/2B.(i+1)*i/2C.(2n-i+1)*i/2D.(2n-i-1)*i/24.已知单链表A长度为m，单链表B长度为n，
2、若将B联接在A的末尾，其时间复杂度应为（）。A.O(1)B.O(m)C.O(n)D.O(m+n)5.假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为()。A.front==rearB.front!=NULLC.rear!=NULLD.front==NULL 7.在一棵高度为h(假定树根结点的层号为0)的完全二叉树中，所含结点个数不小于()。A.2h-1B.2h+1C.2h-1D.2h 8.一棵树的广义表表示为a(b,c(e,f(g)),d)，当用左子女-右兄弟链表表示时，右指针域非空的结点个数为()。A1B2C3D4 9.向具有n个结点的、结构均衡
3、的二叉搜索树中插入一个元素的时间复杂度大致为()。A.O(1)B.O(log2n)C.O(n)D.O(nlog2n) 10.具有n个顶点的有向无环图最多可包含()条有向边。 A．n-1B．nC．n(n-1)/2D．n(n-1)11.图的广度优先搜索类似于树的（）次序遍历。 A.先根B.中根C.后根D.层次12.如果将所有中国人按照生日（不考虑年份，只考虑月、日）来排序，那么使用下列排序算法中()算法最快。A.归并排序B.希尔排序C.快速排序D.基数排序二、填空题，在横线处填写合适内容（每小题1分，共12分）1.数据结构的存储结构包括顺序、________、索引和散列等四种。2.
4、在程序运行过程中可以扩充的数组是__________分配的数组。这种数组在声明它时需要使用数组指针。3.在链表中进行插入和操作的效率比在顺序存储结构中进行相同操作的效率高。4.栈是一种限定在表的一端进行插入和删除的线性表，又被称为___________表。6.一棵树的广义表表示为a(b(c,d(e,f),g(h)),i(j,k(x,y)))，结点f的层数为_________。假定树根结点的层数为0。7.一棵树按照左子女-右兄弟表示法转换成对应的二叉树，则该二叉树中树根结点肯定没有________子女。8.向一棵二叉搜索树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到
5、根结点的________上。9.设图G=(V,E)，V={1,2,3,4},E={<1,2>,<1,3>,<2,4>,<3,4>206}，从顶点1出发，对图G进行广度优先搜索的序列有________种。10.每次直接或通过基准元素间接比较两个元素，若出现逆序排列就交换它们的位置，这种排序方法叫做__________排序 11.快速排序在平均情况下的空间复杂度为____________ 三、判断题，在每小题前面打对号表示正确或打叉号表示失败（每小题1分，共10分）1.数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。2.顺序表和一维数组一样，都可以按下标随机（
6、或直接）访问。3.在一个顺序存储的循环队列中,队头指针指向队头元素的后一个位置4.用非递归方法实现递归算法时一定要使用递归工作栈。5.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。6.在顺序表中进行顺序搜索时，若各元素的搜索概率不等，则各元素应按照搜索概率的降序排列存放，则可得到最小的平均搜索长度 7.在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越小的结点离树根越近，则得到的是最优二叉搜索树。8.对于AOE网络，加速任一关键活动都能使整个工程提前完成。9.直接选择排序是一种稳定的排序方法。10.闭散列法通常比开散列
7、法时间效率更高。 四、运算题（前2小题，每小题6分，后3小题，每小题8分，共36分）1.设有一个二维数组A[10][20]，按行存放于一个连续的存储空间中，A[0][0]的存储地址是200，每个数组元素占1个存储字，则A[6][2]的存储字地址是多少。A[6][2]的存储字地址：2.已知一棵二叉树的中序和后序序列如下，求该二叉树的高度（假定空树的高度为-1）和度为2、度为1及度为0的结点个数。中序序列：c,b,d,e,a,g,i,h,j,f后序序列：c,e,d,b,i,j,h,g,f,a 高
