旧数据结构导论试卷一

《旧数据结构导论试卷一》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构导论试题一（课程代码：2142）一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1．算法指的是【A】A．对特定问题求解步骤的一种描述。B．计算机程序C．排序方法D．数据处理2．在数据结构课程里决定选取何种存储结构时，一般不考虑【A】A．各结点的值如何B．结点个数的多少C．对数据有哪些运算D．所用编程语言实现这种结构是否方便3．线性表采用链接存储时，其地址【D】A．必须是连续的B．部分地址必须是连续的．C．一定是不连续的D．连

2、续与否均可以4．设线性表有n个元素，在顺序表上实现比在链表上实现效率高的算法是【A】A．输出第i(0≤i≤n—1)个元素值B．交换第0个元素与第1个元素的值C．顺序输出这n个元素的值D．输出与给定值x相等的元素在线性表中的序号5．在一个以head为头指针的非空循环单链表中，尾结点指针p满足【A】A.p->next==headB.p->next==NULLC.p==NULLD.p==head6．若用一个大小为6的数组来实现循环队列，且队尾指针rear和队头指针front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和fron

3、t的值分别为多少【B】A.1和5B.2和4C.4和2D.5和17．若一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素是【D】A．不确定B．n-iC．n-i-1D．n-i+18．对特殊矩阵采用压缩存储的目的主要是为了【D】A．表达变得简单B．对矩阵元素的存取变得简单C．去掉矩阵中的多余元素D．减少不必要的存储空间9．设二叉树有n个结点，则其深度为【D】A．n一1B．nC．D．不能确定10．按照二叉树的定义，具有3个结点的二叉树有【C】A．3种B．4种C．5种D．6种11．对具有n个结点的完全二叉树按层次顺序编号，则

4、编号为i的结点（2i>n）的左孩子结点的编号是【B】A．iB．2i+1C．2i-1D．不存在12．对一棵二叉排序树采用中根遍历进行输出的结点序列一定是【B】A．递增或递减序列B．递增序列C．无序序列D．递减序列13．在一个有序表为（10,13,19,21,32,42,48,65,79,81,85,99,108），当二分查找值为85的结点时，要次查找成功。【A】A．2B．3C．4D．514．堆的形状是一棵【A】A．二叉排序树B．满二叉树C.完全二叉树D．判定树15．一组关键码序列为{46，79，56，38，40，84}，则利用快速排序方法，以第1

5、个记录为基准得到的第一趟排序序列为【A】A．38，40，46，56，79，84B．40，38，46，79，56，84C．40，38，46，56，79，84D．40，38，46，84，56，79二、填空题（本大题共15小题，每小题2分，共30分）请在每小题的空格中填上正确答案。错填、不填均无分。1．数据元素之间逻辑关系的整体称为数据的逻辑结构，它是数据的组织形式。2．对同一个问题可以设计出求解它的不同算法，因此，通常从四个方面来评价算法的质量，它们是：正确性、易读性、健壮性和高效率。3．在一个长度为n的顺序表中删除第i个结点时，需要移动N-I+1

6、个结点。4．线性表的常见链式存储结构有单链表、循环链表和双链表。5．一个具有n个结点的单链表，在指针p所指结点后插入一个新结点的时间复杂性为O（n）。6．用push表示入栈操作，用pop表示出栈操作。设有一个空栈，现有输入序列为1、2、3、4、5，经过push,push,pop,push,pop,push,push后，输出的序列是2,3,。7．循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列的元素个数是__(rear-front+(m-1))%(m-1)_____。8．一个矩阵A中，如果非零元素

7、个数远远小于矩阵的元素个数，并且非零元素的分布没有规律，则称A为稀疏矩阵。9．假设根结点的层数为１，具有ｎ个结点的二叉树的最大高度是_1_____。10．拥有100个结点的完全二叉树的最大层数为___99__________。11．设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为。12．从空树开始，用序列{20,35,40,15,30,25,38}构造成一棵二叉排序树后值15在此树的第___2____层上。13．在8个结点的有序顺序表中进行二分查找，最大的比较次数是。14．排序的方法有很多种，直接插入排序方法

8、是从未排序序列依次取出元素，与已经排序序列中的元素作比较，将其放入已排序序列的正确位置上。15．对n个元素进行冒泡排序，在所有元素有序的情况下比较的次