数据结构习题集

《数据结构》习题

一、单项选择题

1．对矩阵进行压缩存储是为了（ A ）

A．节省存储空间 B．提高运算速度 C．便于运算 D．方便存储 2．链式栈与顺序栈相比，一个比较明显的优点是（ B ） A．插入操作更加方便 B．通常不会出现栈满的情况 C．不会出现栈空的情况 D．删除操作更加方便

3．设输入序列为1，2，3，4，5，则借助一个队列可以得到的输出序列是（ C ）[先进先出] A．3，4，1，2，5 B．1，2，3，4，5 C．2，3，4，1，5 D．5，4，3，2，1 4.一个栈的输入序列是6,5,4,3,2,1,可能的输出序列是（ C ）[先进后出] A．4,3,2,1,5,6 B．3,6,2,1,5,4 C．1,2,3,5,4,6 D．5,4,1,3,2,6 5．设输入序列为A，B，C，D。借助一个栈可以得到的输出序列是（A ） A．A，C，D，B B．C，A，D，B C．D，C，A，B D．D，A，B，C

6．将含100个结点的完全二叉树从根开始，每层从左到右依次对结点编号，根结点的编号为1，则编号为71的结点的双亲结点的编号为（ A ）

A．34 B．35 C．36 D．无法确定 7．已知完全二叉树有80个结点，则该二叉树有 （ B ） 个度为1的结点。 A．0 B．1 C．2 D．不确定 8．任何一个无向连通图的最小生成树（ A ）

A．只有一棵 B．有一棵或多棵 C．一定有多棵 D．可能不存在

9．设图G用邻接表存储，对该图进行深度优先搜索遍历，则算法的时间复杂度为 （ ） A． O(n) B． O(n+e) C． O(n2) D． O(n3) 10．用n个键值构造一棵二叉排序树，最低高度为（ ）

A．n/2 B．n C．[㏒2n] D．[㏒2n]+1 11．如果以链表作为栈的存储结构，则执行出栈操作时（ ） A．必须判断栈是否满 B．必须判断栈是否空 C．判断栈元素的类型 D．对栈不作任何判断 12．设数组Data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为 （ ） A．front=front+1 B．front=(front+1)%m

C．rear=(rear+1)%m D．front=(front+1)%(m+1) 13．线性表的长度是指（ ）

A．顺序存储方式下数组所占用的元素个数 B．链表存储方式下的结点个数 C．表中的元素个数 D．所能存储的最大的结点个数 14．设有一个无向图G＝(V，E)和G’=(V’，E’)，如果G’是G的生成树，则下面不正确的说法是（ ） A．G’为G的子图 B．G’为G的连通分量

C．G’为G的极小连通子图且V’=V D．G’是G的一个无环子图

15．在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的键值（ ）

A．一定都是同义词 B．一定都不是同义词 C．都相同 D．不一定都是同义词

16．在有序表A[20]中按二分查找方法查找A[13]依次比较的元素的下标是（ ） A．9，14，12，13 B．9，15，12，13 C．9，14，11，12，13 D．10，15，12，13 17．栈和队列都是（ ）

A．顺序存储的线性表 B．链式存储的线性表 C．限制的线性表 D．限制存储点的非线性结构 18．向顺序栈中压入新元素时，应当（ ）

A．先移动栈顶指针，再存入元素 B．先存入元素，再移动栈顶指针

C． 先后次序无关紧要 D．同时进行

19．若树的先序序列和中序序列正好相同，则一定是一棵 （ ） 的二叉树。

A．结点个数可能大于1且该树无左子树 B．结点个数可能大于1且根结点无左孩子 C．结点个数可能大于1且各结点均无左孩子 D．其中任意一个结点的度不为2

20．下列算法中，在第一趟排序之后，一定能把数据表中最大或最小元素放在其最终位置上的算法是( )

A．归并排序 B．直接插入排序 C．快速排序 D．冒泡排序

21．当初始序列已经按键值有序时，用直接插入算法进行排序，需要比较元素的次数为 （ ）

A．n2 B．n㏒2n C．㏒2n D．n-1 22．下列排序算法中，在最好情况下，时间复杂度为O(n)的算法是（ ）

A．直接选择排序 B．归并排序 C．快速排序 D．冒泡排序 23．下列排序方法中，排序所花费时间不受数据初始排列特性影响的算法是（ ） A．直接插入排序 B．冒泡排序 C．直接选择排序 D．快速排序

24．对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是（ ）

A．直接选择排序 B．直接插入排序 C．快速排序 D．起泡排序 25．对5个不同的数据元素进行直接插入排序，最多需要进行（ ）次比较。 A．8 B．10 C．15 D．25

26．在一个具有n个结点的双链表中插入一个新结点,则该操作的时间复杂性的量级为（ ） A．O(1) B．O(n) C．O(nlog2n) D．O(n2) 27．二分查找法要求被查找的表是 （ ）

A．顺序表 B．分块有序表 C．顺序表且是按键值递增或递减次序排列 D．不受上述任何限制

28．若某线性表中最常用的操作是在最后一个元素之后插人一个元素和删除第1个元素，则采用（ ）存储方式最节省运算时间。

A．单链表 B．仅有头指针的单循环链表 C．仅有尾指针的单循环链表 D．双链表 29．在一个顺序存储的循环队列中，队头指针指向队头元素的（ ）

A．前一个位置 B．后一个位置 C．队头元素位置 D．队尾元素的前一个位置

30．设循环队列用数组A[n]存储，头尾指针为front和rear,求解当前队列中元素个数的公式 ( )

A．rear-front B．front-rear C．n-(front-rear) D．(n+rear-front)％n 31．已知完全二叉树有100个结点，则该完全二叉树共有（ ）个叶子结点。

A． 37 B． 49 C． 50 D．不确定 32．下列存储形式中，（ ）不是树的存储形式。

A．双亲表示法 B．左子女右兄弟表示法 C．广义表表示法 D．顺序表示法 33．在一棵具有5层的满二叉树中结点总数为（ ） A．31 B．32 C．33 D．16 34．设有100个数据元素，采用折半搜索时，最大比较次数为（ ） A．6 B．7 C．8 D．10

35．在顺序存储的线性表(a1,a2,...,an)中,删除任意一个结点时所需移动结点的平均次数为（ ） A．n B．n/2 C．(n-1)/2 D．(n+1)/2 36．下列说法不正确的是（ ）

A．数据元素是数据的基本单位 B．数据项是数据中不可分割的最小标识单位 C．数据可由若干个数据元素构成 D．数据项可由若干个数据元素构成

37．为了方便在线性结构的数据中插入一个数据元素,则其数据结构宜采用（ ）方式 A．顺序存储 B．链式存储 C．索引存储 D．散列存储

38．矩阵A5×6的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[5][5]的地址为 （ ）

A．1120 B．1125 C．1140 D．1145

39．设矩阵A(aij，0≤i,j≤9)的元素满足：aij≠0 (i≥j,0≤i,j≤9) aij =0 (i

A．2384 B．2380 C．2204 D．2200 40．若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个（ ）。 A．上三解矩阵 B．稀疏矩阵 C．对角矩阵 D．对称矩阵 41．设n阶方阵A是对称矩阵，为节省存储空间,将其下三角(包括对角线)以行序为主序存储在一维数组B[1..n(n+1)/2]中,则对任一上三角元素aij(i

A．i(i-1)/2+j B．j(j-1)/2+i C．i(j-1)/2+i D．j(i-1)/2+i 42．对于静态表顺序查找算法，若在表头设置岗哨，则正确的查找方式为（ ） A．从第0个元素往后查找该数据元素 B．从第1个元素往后查找该数据元素 C．从第n个元素开始往前查找该数据元素 D．与查找顺序无关 43．常采用下面几种方式解决散列法中出现的冲突问题（ ）

A．数字分析法、除余法、平方取中法 B．数字分析法、除余法、线性探测法 C．数字分析法、线性探测法、多重散列法 D．线性探测法、多重散列法、链地址法

44．若待排序列已基本有序，要使它们完全有序，从关键码比较次数和移动次数考虑，应当使用的排序方法是（ ） A．归并排序 B．直接插入排序 C．直接选择排序 D．快速排序 45.中序遍历与后序遍历结果相同的二叉树为（ ）

A．根节点无左孩子的二叉树 B．根节点无右孩子的二叉树

C．所有结点只有左子树的二叉树 D．所有结点只有右子树的二叉树 46.下列关于广义表的叙述中错误的是（ ）

A．广义表是线性表的推广 B．广义表至少有一个元素是子表 C．广义表可以是自身的子表 D．广义表可以是空表

47.用快速排序算法对线性表排序,若选择表中第一个元素作为分界元素,则表中按（ ）分布时排序效率最高. A．已经有序 B．部分有序 C．完全有序 D．逆序

48．若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（ ）

A．S1的栈底位置为0，S2的栈底位置为n+1 B．S1的栈底位置为0，S2的栈底位置为n/2 C．S1的栈底位置为1，S2的栈底位置为n D．S1的栈底位置为1，S2的栈底位置为n/2 49．在有n个结点的二叉链表中，值为非空的链域的个数为（ ）

A．n-1 B．2n-1 C．n+1 D．2n+1

50．带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（ ） A．第i行非∞的元素之和 B．第i列非∞的元素之和

C．第i行非∞且非0的元素个数 D．第i列非∞且非0的元素个数

51．在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（ ） A．0(n) B．0(log2n) C．0(nlog2n) D．0(n2)

52．若线性表最常用的操作是存取第i个元素及其前趋的值，则采用（ ）存储方式节省时间。 A．单链表 B．双链表 C．单循环链表 D．顺序表

53．对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（ ）遍历实现编号。

A．先序 B．中序 C．后序 D．从根开始的层次遍历 54．下列排序算法中，（ ）算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。 A．堆排序 B．冒泡排序 C．快速排序 D．SHELL排序 55．一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为（ ） A．0 B．1 C．2 D．不确定

56．在一个长度为n的顺序存储的线性表中，删除第i个元素（1≤i≤n）时，需要从前向后依次前移（ ）个元素。

A． n-i B． n-i+1 C． n-i-1 D． i

57．假定一个顺序队列的队首和队尾指针分别为1和r，则判断队空的条件为（ ）

A． f+1==r B． r＋1==f C． f==0 D． f==r 58．哈夫曼树的带权路径长度WPL等于（ ）

A．除根以外的所有结点的权植之和 B．所有结点权值之和 C．各叶子结点的带权路径长度之和 D．根结点的值

59．一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（ ）

A．{38，46，79，56，40，84} B．{38，79，56，46，40，84} C．{40，38，46，56，79，84} D．{38，46，56，79，40，84} 60．线性链表不具有的特点是（ ）

A． 随机访问 B．不必事先估计所需存储空间大小 C． 插入与删除时不必移动元素 D．所需空间与线性表长度成正比 61．设有一个l0阶的对称矩阵A[10][10]，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组B[n]中，A[0][0]存入B[0]中，则A[8][5]在B[n]中（ ）位置。

A．32 B．33 C．41 D．65

62．设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶子结点，则B中右指针域为空的结点有（ ）个。 A．n-1 B．n C．n+l D．n+2

63．对有14个数据元素的有序表R[0-13]进行折半搜索，搜索到R[3]的关键码等于给定值，此时元素比较顺序依次为( )。

A．R[0]，R[1]，R[2]，R[3] B．R[0]，R[13]，R[2]，R[3] C．R[6]，R[2]，R[4]，R[3] D．R[6]，R[4]，R[2]，R[3]

64.为了最快地对线性结构的数据进行某数据元素的读取操作，则其数据存储结构宜采用( )方式。 A．顺序存储 B．链式存储 C．索引存储 D．散列存储

65.设双链表中结点的前趋指针和后继指针的域名分别为t1和r1，则删除双链表中指针s所指结点的操作为( ) A．s->t1->r1=s->t1;s->r1->t1=s->r1; B．s->t1->r1=s->r1;s->r1->t1=s->t1; C．s->r1=s->t1->r1;s->t1=s->r->t1; D．s->t1=s->t1->r1;s->r1=s->r->t1; 66.假设left和right为双向链表中指向直接前趋结点和直接后继结点的指针域，现要把一个指针s所指的新结点作为非空双链表中q所指地点(中间结点)的直接后继结点插入到该双向链表中，则下列算法段能正确完成上述要求的是( ) A．q->right=s; s->left=q; q->right->left=s; s->right=q->right; B．s->left=q; q->right=s; q->right->left=s; s->right=q->right; C．s->left=q; s->right=q->right; q->right->left=s; q->right=s; D．以上都不对

67.已知一个稀疏矩阵的三元组表如下：(1，2，3)，(1，6，1)，(3，1，5)，(3，2，-1)，(4，5，4)，(5，1，-3)，则其转置矩阵的三元组表中第3个三元组为( )

A．(2，1，3) B．(3，1，5) C．(3，2，-1) D．(2，3，-1) 68.顺序查找法与二分查找法对存储结构的要求是( )

A. 顺序查找与二分查找均只适用于顺序表 B．顺序查找只适用于顺序表 C．顺序查找与二分查找既适用于顺序表，也适用于链表 D．二分查找只适用于顺序表 69.程序段for (i=0;i

70.在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是 ( )

A．p=p->next; B．p->next=p->next->next; C．p->next=p; D．p=p->next->next; 71.在头指针为head且表长大于1的单循环链表中，若指针p->next->next=head,则( )

A．p指向头结点 B．p指向尾结点 C．*p的直接后继是头结点 D．*P的直接后继是尾结点 72.广义表A=(a,(b),(),(c,d,e))的长度为( )

A．4 B．5 C．6 D．7

73.无向图中一个顶点的度是指图中( )

A．通过该顶点的简单路径数 B．与该顶点相邻接的顶点数 C．通过该顶点的回路数 D．与该顶点连通的顶点数

74.已知一个图如下所示，从顶点a出发进行广度优先遍历可能得到的序列为( )

A．a c e f b d B．a c b d f e C．a c b d e f D．a c d b f e

75.设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为( ) A．21 B．23 C．41 D．62 76.下面的二叉树中，( )不是完全二叉树。

77.下列说法错误的是( )。

A．一个图的邻接矩阵表示是唯一的 B．一个图的邻接表表示是不唯一的

C．一个图的生成树必为该图的极小连通子图 D．一个无环有向图的拓扑排序序列必唯一 78.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 A．5 B．6 C．7 D．8 79.二叉树在线索化后，仍不能有效求解的问题是( )

A．先序线索二叉树中求先序后继 B．中序线索二叉树中求中序后继 C．中序线索二叉树中求中序前趋 D．后序线索二叉树中求后序后继

80.数据表A中有10000个元素，如果仅要求求出其中最大的10个元素，则采用( )排序算法最节省时间。 A．堆排序 B．希尔排序 C．快速排序 D．直接选择排序

81．若给定有n个元素的向量，则建立一个有序单向链表的时间复杂性的量级是( ) A．O(1) B．O(n) C．O(n2) D．O(nlog2n)

82．在一个具有n个结点的单链表中查找值为m的某结点，若查找成功，则平均比较( )个结点。 A．n B．n／2 C．(n-1)／2 D．(n+1)／2 83．研究数据结构就是研究( )

A．数据的逻辑结构 B．数据的存储结构 C．数据的逻辑结构和存储结构 D．数据的逻辑结构、存储结构及其数据在运算上的实现

84．设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树中共有( )个结点。 A．13 B．12 C．26 D．25 85.下列四种排序方法中，不稳定的方法是（ ）

A．直接插入排序 B．冒泡排序 C．归并排序 D．直接选择排序 86．下列说法中不正确的是( )

A．无向图中的极大连通子图称为连通分量

B．连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C．图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D．有向图的遍历不可采用广度优先搜索方法 87．下列说法中不正确的是（ ）

A．图的遍历过程中每一顶点仅被访问一次

B．遍历图的基本方法有深度优先搜索和广度优先搜索两种 C．图的深度优先搜索的方法不适用于有向图 D．图的深度优先搜索是一个递归过程

88．对有序表(18，20，25，34，48，62，74，85)用二分查找法查找85，所需的比较次数为( )

A．1次 B．2次 C．3次 D．4次 89．散列表的平均查找长度( )

A．与处理冲突方法有关而与表的长度无关 B．与处理冲突方法无关而与表的长度有关 C．与处理冲突方法有关且与表的长度有关 D．与处理冲突方法无关且与表的长度无关 90.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( ) A．顺序存储结构 B．链式存储结构 C．索引存储结构 D．散列存储结构 91.若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为( ) A．4 B．5 C．6 D．7

92.三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A［３］[4][5]的存储地址为( )

A．356 B．358 C．360 D．362 93.下列陈述中正确的是( )

A．二叉树是度为2的有序树 B．二叉树中结点只有一个孩子时无左右之分

C．二叉树中必有度为2的结点 D．二叉树中最多只有两棵子树，并且有左右之分 94.n个顶点的有向完全图中含有向边的数目最多为( )

A．n-1 B．n C．n(n-1)/2 D．n(n-1)

95.设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均探查次数不超过1.5，则散列存储空间应能够至少容纳（ ）个表项。（设搜索成功的平均搜索长度为Snl=(1+1/(1-a))/2,其中a 为装填因子）

A．400 B．526 C．624 D．676 96.在有向图中每个顶点的度等于该顶点的（ ）

A．入度 B．出度 C．入度与出度之和 D．入度与出度之差 97.一个二叉树按顺序方式存储在一维数组中，如图则结点E在二叉树的第（ ）层。

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A B C D E F G H I J A．1 B．2 C．3 D．4 98．设某线性链表的头结点指针为L, L->data表示该链表的结点个数，L->next指向该链表的第一个结点，p指向新建立的结点，其类型与L相同。在建立该链表的过程中，若希望L->next始终指向新输入的结点，可采用如下的C语言语句实现：（ ）

A. p->next=L->next, L->next=p，L->data++; B. p->next=NULL, L->next=p, L->data++; C. L->data++, L->next=p->next, p->next=L; D.以上都不是。

99.以数组Q[0..m-1]存放循环队列中的元素，变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数，队列第一个元素的实际位置是（ ）

A．rear - qulen B．rear - qulen + m

C．m - qulen D．1 +（rear + m - qulen）% m

100.设结点x和结点y是二叉树T中的任意两个结点，若在先根序列中x在y之前，而在后根序列中x在y之后，则x和y的关系是（ ）

A．x是y的左兄弟 B．x是y的右兄弟 C．x是y的祖先 D．x是y的后代 101.对线性表进行二分查找时，要求线性表必须( )。

A．以顺序方式存储 B．以链接方式存储

C．以顺序方式存储，且结点按关键字有序排序 D．以链接方式存储，且结点按关键字有序排序

二、判断题(若正确在( )内打√，否则打×。)

( ) 1．对链表执行插入和删除操作时，不必移动结点。 ( ) 2．双链表中只有一个结点的后继指针为空。

( ) 3．数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。 ( ) 4．线性表的逻辑顺序与物理顺序总是一致的。 ( ) 5．线性表的顺序存储表示优于链式存储表示。 ( ) 6．栈是实现函数调用的必不可少的数据结构。

( ) 7．线性表的长度是线性表所占用的存储空间的大小。

( ) 8．在带头结点的单链表中插入元素结点不会改变头指针的值。 ( ) 9．对链队列执行出队操作不会改变尾指针的值。

( )10．树(或森林)转化为对应的二叉树后，两者的分支数相等。

( )11．由给定的n个权值所构造的哈夫曼树可能不唯一，其结点个数也可能不确定。 ( )12．图中一个顶点i的出度等于其邻接矩阵中第i列的非0元素个数。 ( )13．二叉树是树的特殊情形。

本文来源：https://www.bwwdw.com/article/sqif.html