数据结构习题

1、绪论习题(一)1. 数据在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为（ ）。 A. 存储结构 B. 逻辑结构 C. 顺序存储结构 D. 链式存储结构2. 每一个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是（ ）存储方式。A. 顺序 B. 链式 C. 索引 D. 散列3. 以下任何两个结点之间都没有逻辑关系的是（ ）。A. 图形结构 B. 线性结构 C. 树形结构 D. 集合4. 算法在发生非法操作时可以作出处理的特性称为算法的（ ）。A. 正确性 B. 易读性 C. 健壮性 D. 高效性 绪论练习（二）1.数据逻辑结构除了集合以外，还包括：线性结构、树形结构

2、和 图形结构 。2.树形结构结构中的元素之间存在 一对多 的关系。3.数据结构被定义为(D，R)，其中D是数据的有限集合，R是D上的 关系 的有限集合。5.若一个算法中的语句频度之和为T（n）=6n+3nlog2n，则算法的时间复杂度为 O(nlog2n) 。线性表习题（一）2.已知一个顺序存储的线性表，设每个结点占m个存储单元，若第一个结点的地址为B，则第i个结点的地址为（ ）。A B+(i-1)*m BB+i*m C B-i*m D B+(i+1)*m3.两个指针P和Q，分别指向单链表的两个元素，P所指元素是Q所指元素前驱的条件是（ ）。AP-next=Q-next BP-next= Q

3、CQ-next= P DP= Q5.等概率情况下，在有n个结点的顺序表上做插入结点运算，需平均移动结点的数目为（ ）。An B(n-1)/2 C n/2 D(n+1)/26.在（ ）的运算中，使用顺序表比链表好。A插入 B根据序号查找 C 删除 D根据元素查找线性表习题（二）1.链表相对于顺序表的优点是： 插入、删除 方便。2.顺序表中访问任意一个结点的时间复杂度均为 O(1) 。3.在单链表中要在已知结点*P之前插入一个新结点，需找到*P的直接前趋结点的地址，其查找的时间复杂度为 O(n) 。4.单链表中需知道 头指针 才能遍历整个链表。5.在一个长度为n的顺序表中删除第i个元素，要移动 n

4、-i 个元素。6.在一个长度为n的顺序表中，如果要在第i个元素前插入一个元素，要后移 n-i+1 个元素。7.双链表中，设p是指向其中待删除的结点，则需要执行的操作为： p-prior-next=p-next 。 栈和队列习题（一）1.在有n个元素的栈中，进栈操作的时间复杂度为 O(1) 。2.在栈结构中，允许插入、删除的一端称为 栈顶 。3.若进栈的次序是A、B、C、D、E，执行三次出栈操作以后，栈顶元素为 B 。4.解决顺序队列“假溢出”的方法是采用 循环队列 。5.设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有 front=11，rear=19，则循环队列中

5、还有 8 个元素。6.设循环队列的头指针front指向队首元素，尾指针rear指向队尾元素后的一个空闲元素，队列的最大空间为MAXLEN，则队满标志为： front=(rear+1)%MAXLEN 。栈和队列练习（二）1.设有编号为1，2，3，4的四辆列车，顺序进入一个栈结构的站台，下列不可能的出站顺序为( )A1234 B1243 C1324 D14232.从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行下列 ( )命令。 Ax=top;top=top-next; Btop=top-next;x=top-data; Cx=top-data; Dx=top-data;

6、top=top-next;3.在一个栈顶指针为HS的链栈中，将一个S指针所指的结点入栈，应执行下列( )命令。 AHS-next=S; BS-next=HS-next;HS-next=S; CS-next=HS-next;HS=S; DS-next=HS;HS=HS-next;4. 设有一个顺序栈S，元素A,B,C,D,E,F,依次进栈，如果六个元素出栈的顺序是B，D，C，F，E，A，则栈的容量至少应是( )。 A3 B4 C5 D 6栈和队列练习（二）5.若进队的序列为：A，B，C，D，则出队的序列是（ ）。AB，C，D，ABA，C，B，D CA，B，C，DDC，B，D，A6.四个元素按：A

7、，B，C，D顺序连续进队Q，执行一次OutQueue(Q)操作后，队头元素是（ ）。A A B B C C D D8.设链栈中结点的结构：data为数据域，next为指针域，且top是栈顶指针。若想在链栈的栈顶插入一个由指针s所指的结点，则应执行下列（ ）操作。 As-next=top-next；top-next=s； Btop-next=s； Cs-next=top；top=top-next； Ds-next=top；top=s；树习题（一）1.不相交的树的聚集称之为 森林 。 2.深度为k的完全二叉树至少有 2k-1 个结点。至多有 2k-1 个结点。3.在一棵二叉树中，度为零的结点的个数

8、为n0，度为2的结点的个数为 n2，则有 n0=n2+1 。4.一棵有n（n0）个结点的满二叉树共有 (n+1)/2 个叶子和 (n-1)/2 个非终端结点。5.高度为k且有2k-1个结点的二叉树称为 满 二叉树。树习题（一） 7. 如图所示，二叉树的中序遍历是 BLEACWXD ：BCDELAXW树习题（二）1.某二叉树先序遍历的结点序列是abdgcefh，中序遍历的结点序列是dgbaechf，则其后序遍历的结点序列是 。 A、bdgcefha B、gdbecfha C、bdgaechf D、gdbehfca2.某二叉树后序遍历结果为dabec,中序遍历结果为debac,那么二叉树的先序遍历

9、序列是 。A. acbed B. decab C.deabc D.cedba3.高度为6的满二叉树，总共有的结点数是 。 A、15 B、63 C、20 D、25 4.具有10个叶结点的二叉树中有 个度为2的结点。 A、8 B、9 C、10 D、11树习题（三）假设用于通讯的电文仅有六个符号（a1,a2,a3,a4,a5,a6)，符号在电文中出现的概率分别为0.13,0.18,0.16,0.07,0.32,0.14.试为这六个字母设计哈夫曼编码，写出构造哈夫曼树过程和编码过程。图习题（一）1.设无向图的顶点个数为n，则该图最多有（）条边。A.n-1 B.n(n-1)/2 C.n(n+1)/2 D

10、.n22.一个n个顶点的连通无向图，其边的个数至少为（）。A.n-1 B.n C.n+1 D.2n3.有8个结点的有向完全图有（）条边。A.14 B. 28 C.56 D.112 4.已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（） A. 0 1 3 2 B.0 2 3 1 C.0 3 2 1 D. 0 1 2 3图习题（一）5. 已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是（）A.0 3 2 1 B.0 1 2 3 C. 0 1 3 2 D. 0 3 1 26. 图的深度优先遍历类似于二叉树的（）。A.先序遍历 B.中序遍历 C.后

11、序遍历 D.层次遍历 图习题（二）1. 在有向图中，以顶点v为终点的边的数目成为v的_入度_.3. 有n个顶点的强连通有向图G至少有_n_条弧。4. 有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的_出度_.5. 图的存储结构表示有_邻接矩阵_,_邻接表_,十字链表、邻接多重表等多种存储结构。图习题（三） 1. 已知如图所示的有向图，请给出该图的： （1）每个顶点的入/出度；（2）邻接矩阵；（3）邻接表（4）逆邻接表图习题（三） 2.已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。图习题（三） 1.已知已个 AOV 网如

12、图所示，写出所有拓扑序列。图习题（三） 1.如图所示是一个无向网图，请分别按Prim算法和Kruskal算法求最小生成树。查找习题（一）1已知一个有序表为（12，18，24，35，47，50，62，83，90，115，134），当折半查找值为 90 的元 素时，经过（ ）次比较后查找成功。A 2 B 3C 4D 52已知 10 个元素（54，28，16，73，62，95，60，26，43），按照依次插入的方法生成一棵二叉排序树，查找值为 62 的结点所需比较次数为（ ）。A 2B 3C 4D 53已知数据元素为（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二

13、叉排序树，则该树的深度为（ ）。A 4B 5C 6D 74按（ ）遍历二叉排序树得到的序列是一个有序序列。A 前序 B 中序 C 后序 D 层次5在散列函数 H(k)= k mod m 中，一般来讲，m 应取（ ）。A 奇数 B 偶数 C 素数 D 充分大的数查找习题（三）1.已知关键码序列为（Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec），散列表的地址空间为 016，设散列函数为 H(x)= ，其中 i 为关键码中第一个字母在字母表中的序号，采用线性探测法和链地址法处理冲突，试分别构造散列表，并求等概率情况下查找成功的平均查找长度。排序习题（一）2.一组记录的关键码为46, 79, 56, 38, 40, 84，则利用快速排序的方法，以第一个记录为基准得到的一 次划分结果为（ ）。A 40, 38, 46, 56, 79, 84 B 40, 38, 46, 79, 56, 84C 40,