数据结构习题

1、一算法的基本概念【例1】算法是指（）。(A)计算机程序 （B）计算机的计算方法(C)计算机的存取方式 （D）解决问题的有限运算序列【答案】D【例2】算法的基本特性不包括（）。（A）输入性 （B）确定性（C）高效性 （D）可执行性【答案】C【例3】算法的工作量大小和实现算法所需的存储单元多少分别称为算法的（ ）和 （）。（1） （A）可执行性 （B）时间复杂度 （C）空间复杂度 （D）计算机的效率（2） （A）确定性 （B）时间复杂度 （C）空间复杂度 （D）存储的合理性【答案】（1）B （2）C【例4】时间复杂性最好，执行时间最短的是（）。（A）O(log2n) （B）O(nlog2n)（C）

2、O(n) （D）O(n³)【答案】A【例5】下面程序段的时间复杂度是（）。For(int a=0;a<n;a+) For(int b=1;b<m;b+) Aab=1;（A）O(n) （B）O(n×m)（C）O(n+m) （D）O(n+m-1)【答案】B【例6】下列程序段的时间复杂度为（）。For(i=1;i<n;i+) y=y+1; for(j=0;j<=(2*n);j+) x+; （A）O(n-1) （B） O(n)（C）O(n2) （D） O(2n+1)【答案】C【例7】下列程序段的时间复杂度为（）。 i=1; while(i<=n)i=i

3、*2; （A）O(1) （B） O(n)（C）O(log2n) （D） O(2n)【答案】C【例8】算法的执行遵循“输入计算_”的模式，算法的_体现算法的功能。【答案】输出 输出【例9】式子a*(3a2+6a-3)的时间复杂度是_。【答案】O(a3)【例10】当有非法数据输入时，算法能做出适当的处理，体现了算法的_。【答案】健壮性【考点解析】一个算法必须能够处理非法数据的输入，且不能产生不可预测的结果，这是算法的健壮性所必须的，处理非法数据的能力体现了算法的健壮性。【例11】算法分析的目的是（ ）。 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系C.分析算法的效率以求改进 D.分析

4、算法的易懂性和文档性【答案】C二 数据结构基础【例1】数据的存储结构是指（ ）。（A）存储在外存中的数据（B）数据所占的存储空间量（C）数据在计算机中的顺序存储方式（D）数据的逻辑结构在计算机中的表示【答案】D【例2】数据处理的最小单位是（）。（A）数据（B）数据元素（C）数据对象（D）数据项【答案】D【例3】在数据结构中，从逻辑上可以把数据结构分为（）。（A）线性结构和非线性结构（B）内部结构和外部结构（C）动态结构和静态结构（D）紧凑结构和非紧凑结构【答案】A【例4】数据的逻辑关系是指数据元素的（）。（A）结构 （B）关联（C）数据项 （D）存储方式【答案】B【考点解析】逻辑结构反映的是数

5、据元素之间的逻辑关系，所以答案选B。而数据项是指是数据的不可分割的最小单位；存储方式反映的是数据的存储结构。【例5】能够被计算机识别、存储和加工处理的信息的载体是（ ）。（A）数据 （B）数据项（C）数据对象 （D）结点【答案】A【考点解析】数据元素是数据的基本单位。数据元素也称为元素、顶点、记录。有时一个数据元素可以由若干个数据项组成，数据项是具有独立意义的最小标识单位，而数据是各种存储信息的总称。【例6】数据逻辑结构包括集合、线性结构、树型结构和（ ）。（A）图状结构 （B）存储结构（C）算法描述 （D）基本运算【答案】A【例7】任何两个结点之间没有逻辑关系的是（ ）。（A）图状结构 （B

6、）线性结构（C）集合 （D）树型结构【答案】C【例8】数据的存储结构的四种基本类型是（ ）。（A）顺序、链接、索引、散列（B）链接、向量、索引、顺序（C）集合、链接、索引、散列（D）顺序、链接、索引、数组【答案】A三线性表【例1】以下有关顺序存储结构的叙述中，（）是不正确的。（A）逻辑上相邻的结点物理上可以不邻接（B）存储密度大（C）插入、删除运算操作不方便（D）可以通过计算机直接确定第i个结点的存储结构【答案】A【例2】带头结点的链表和不带头结点的链表都可以用来表示线性表，前者最主要的好处是（）。（A）节省存储空间（B）可以加快对表元素的查找（C）使空表和非空表的处理统一（D）可以提高存取表

7、元素的速度【答案】C【例3】下面关于线性表的叙述中，正确的是（）。（A）线性表采用顺序存储，不必占用一片连续的存储单元（B）线性表采用顺序存储，不便于进行插入和删除操作（C）线性表采用链接存储，必须占用一片连续的存储单元（D）线性表采用链接存储，不便于进行插入和删除操作【答案】B【例4】在线性表中，用一组地址连续的存储单元依次存储线性表的数据元素，这种称为线性表的（）。（A）顺序结构 （B）链接结构（C）循环结构 （D）线性结构【答案】A【例5】用数组表示线性表最大的优点是（ ）。（A）便于随机插入和删除操作（B）便于随机存取（C）不需要占用一片连续的存储空间（D）动态的分配内存【答案】B【例

8、6】试编程实现在顺序表L的第i个位子上插入值XVoid InsertList(Sqlist*L，DataType x，int I) int j; if(I<1 | I>l.length+1) printf(“Position error”); return ERRORif(l.length>=ListSize) printf(“overflow”); exit(overflow); for(j=l.length-1;j>=I-1;j-) l.dataj+1=l.dataj; l.dataI-1=x; l.length+;【例7】试编程求二叉树T的叶子结点数（二叉链表存储

9、）。 Int count_node(treenodeptr T) /*n 的初值为0*/ if(T!=NULL) if(T->Lchild = NULL&& T->Rchild = NULL)n=n+1; count_node(treenodeptr T->Lchild); count_node(treenodeptr T->Rchild); Return (n);四.栈、队列和递归例题解析【例1】栈的插入和删除操作进行在（ ）。（A）栈顶 （B）栈底（C）任意位置 （D）指定位置【答案】A【例2】当利用大小为m的数组顺序存储一个栈时，假定用top=m表

10、示栈空，则向栈插入一个元素时，首先应执行（ ）语句修改top指针。（A） top+ （B）top-（C） top = 0 （D）top = 1【答案】B【例3】若让元素a,b,c依次进栈，则出栈次序不可能出现的情况是（ ）。（A）c,b,a （B）b,a,c（C）c,a,b （D）a,c,b【答案】C【例4】以下不属于栈的基本运算的是（ ）。（A）取栈顶元素 （B）取栈底元素（C）初始化栈 （D）判断栈为空【答案】B【例5】若进栈序列为1，2，3，4，假设进栈过程中可以出栈，则下列不可能的一个出栈序列是（ ）。（A）1，4，3，2 （B）2，4，3，1（C）3，4，2，1 （D）3，1，4，2

11、【答案】D【例6】循环队列采用数组data1:n来存储元素的值,并用front和rear分别为其头尾指针,为区别队列的空满,牺牲一个空间不用,则在任意时刻,至少可知一个空的元素的下标是( front).入队时可用语句(rear=(1+rear) mod n)求出新元素在数组data中的下标.【例7】循环队列采用数组data0:m-1来存储元素的值, 用front和rear分别为其头尾指针,则当前队列中的元素的个数是( ). A.(rear-front+m)%m B.rear-front+1C. rear-front-1 D. rear-front【答案】A【例8】一般情况,将递归算法转变成非递

12、归算法应设置( ). A.栈 B.队列 C.堆栈或队列 D.数组【答案】A五.链表的结构及其基本运算【例1】下列是链表的特点的是（ ）。（A）可随机访问任意一个结点 （B）插入和删除不需要移动任何元素（C）需要事先估计存储空间 （D）链表的元素在空间上必须相邻【答案】B【例2】如果经常使用的操作是取第i个结点及其前驱，则为了节省时间应当采取（ ）存储方式。（A）顺序表 （B）单链表（C）双向链表 （D）循环链表【答案】A【例3】对于线性表，下列情况下应当采用双向链表的是（ ）。（A）经常需要随机地储取元素 （B）经常需要访问某个结点及其该结点的前驱（C）表中元素需要占据一片连续的存储空间 （D

13、）表中元素的个数不变【答案】B【例4】与单链表相比，双向链表的优点之一是（ ）。（A）插入、删除操作更加简单 （B）可以随机访问（C）可以省略表头指针或表尾指针 （D）顺序访问相邻结点更加灵活【答案】D【例5】带头结点的单链表head为空的判定条件是（ ）。（A）head = = Null （B）headNext = = Null （C）headNext = = head （D）head ! = Null【答案】B【例6】单链表中，增加头结点的作用是（ ）。 A.方便运算的实现 B.用于标志单链表C.使单链表中至少有一个结点 D.用于标志起始结点【答案】A【例7】在( )运算中,使用顺序表比链

14、表好. A.插入 B.删除 C.根据序号查找 D.根据元素值查找【答案】C六.树与森林【例1】下面关于树的叙述正确的是（ ）。（A）一棵树中只有一个无前驱的结点 （B）一棵树的度为树中各个结点的度数之和减一（C）一棵树中，每个结点的度数之和等于结点数 （D）一棵树中每个结点的度数之和与边的条数不相等【答案】A【例2】下面关于二叉树的叙述错误的是（ ）。（A）二叉树第i（i1）层上至少有2i-1个结点 （B）一棵二叉树中的结点个数大于0 （C）对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则叶结点数为n0=n2+1 （D）具有n个结点的完全二叉数的深度为log 2 n+1【答案

15、】B【例3】在一棵非空二叉树的中序遍历序列中，根结点的左边（ ）。（A）只有右子树上的所有结点（B）只有右子树上的部分结点 （C）只有左子树上的所有结点 （D）只有左子树上的部分结点【答案】C【例4】已知某二叉树的前序遍历序列是aBEgCFK，中序遍历序列是EgBaFCK，则它的后序遍历序列是（ ）。（A）aCFKEBg （B）gEBFKCa （C）KCFagEB （D）aBCEFKg【答案】B【例5】含有15个结点的二叉树的最小深度是（ ）,假设根结点的层次为0。（A）3 （B）4 （C）5 （D）6【答案】A【例6】在一棵具有35个结点的完全二叉树中，该树的深度为_。假定根结点的层次为0。

16、【答案】5【例7】某棵树的度为4 ，其中度为1、2、3和4的结点的个数分别为4、2、1、1，则这棵树中叶子结点的个数为_。【答案】8【例8】深度为k的完全二叉树至少有_个结点，至多有_个结点。【答案】2k-1 2k-1【例9】在一棵二叉树中，叶子结点的个数为n0 ，度为2的结点个数为n2 ,则有n0 =_。【答案】n2+1【例10】设森林F中有三棵树，第一棵、第二棵、第三棵树的结点个数分别是m1、m2、m3，则与森林对应的二叉树根结点的右子树上的结点数是（ ）。 A.m1 B.m1+m2 C.m3 D.m2+m3 【答案】D七. 查找【例1】若搜索每一个元素的概率相等，则在长度为n的顺序表上搜

17、索到表中任一元素的平均搜索长度为（ ）。（A）n （B）n+1 （C）(n-1)/2 （D）(n+1)/2【答案】D【例2】对长度为10的顺序表进行搜索，若搜索前面5个元素的概率相同，均为1/8，搜索后面5个元素的概率相同，均为3/40，则搜索到表中任一元素的平均搜索长度为（ ）。（A）5.5 （B）5 （C）39/8 （D）19/4【答案】C【例3】对长度为3的顺序表进行搜索，若搜索第一个元素的概率为1/2，搜索第二个元素的概率为1/3，搜索第三个元素的概率为1/6，则搜索到表中任一元素的平均搜索长度为（ ）。（A）5/3 （B）2（C）7/3 （D）4/3【答案】A【考点解析】根据题意可以得到搜索到表中任一元素的平均搜索长度为： 1*1/2+2*1/3+3*1/6=5/3【例4】有一个有序表为2，7，9，12，32，40，43，64，69，78，80，96，120，当用二分查找值为80的结点时，（ ）次比较后查找成功。（A）1 （B）2 （C）4 （D）8