数据结构习题
一、名词解释
1. 数据、数据元素、数据项、数据结构、数据的逻辑结构、数据物理结构、顺序存储、链式存储、算法、时间复杂度、空间复杂度。
2. 线性表、顺序表、单链表、双向链表、循环链表、双向循环链表、三个概念的区别：头指针、头结点、首元结点(第1个元素结点)。
3. 栈（顺序栈、链栈）、队列（顺序队、链队）、循环队列、递归、稀疏矩阵、三元组。
4. 树、叶子结点、结点的度、树的度、树的高(深)度、二叉树、遍历、满二叉树、完全二叉树、哈夫曼树、WPL、哈夫曼编码。
5. 图（有向、无向）、网、边、弧、度、入度、出度、完全图（有向、无向）、（强）连通图（分量）、（最小）生成树、邻接矩阵、邻接表、DFS、BFS。
6. 查表、关键字、静态查、动态查、ASL、顺序查、折半查、分块查、二叉排序树。
7、排序、内（外）排序、稳定性、插入（直接、希尔），交换（起泡、快速），选择（直接、堆），2路归并。
一、填空题
1.数据结构是研究数据的_逻辑结构__和___物理结构__，并在这种结构上定义相关的运算，设计实
现这些运算的算法，分析算法的效率。算法的效率包括时间和空间两个方面，分别称为___时间复杂度____和__空间复杂度___。
2.数据的基本单位是__数据元素__ ，数据的最小单位是__数据项_  。
3.算法是对特定问题求解___步骤___的一种描述，是指令的有限序列。
4.一个算法的时间复杂度为(3n3+2n—7)，其数量级表示为O（n3）_。
5.一个算法具有5个特性：确定性、可行性、有穷性、输入和输出。
6.算法性能的分析和度量，可以从算法的时间复杂度和空间复杂度来评价算法的优劣。
7.数据的逻辑结构包括集合结构、线性结构、树形结构和图型结构四种类型。
8.数据结构在计算机中的表示称为数据的物理结构，它可以采用__顺序存储___或__链式存储_
两种存储方法。
9.线性表有两种存储结构，分别为顺序存储和链式存储。
10.链式存储的特点是利用指针来表示数据元素之间的逻辑关系。
11.若频繁地对线性表进行插入和删除操作，该线性表宜采用_链式存储__存储结构。
12.线性表中的数据元素之间具有一对一的线性关系，除第一个和最后一个元素外，其他数据
元素有且只有一个直接后继和直接前趋。
13.在一个单链表中p所指结点之后插入一个s所指结点时，应执行s->next=__p->next______和
p->next=__s______的操作。
14.在一个单链表中删除p的后继结点q时，应执行以下操作p->next=  q->next。
15.对带头结点head的单链表，则判断其为空的条件为head->next=NULL。
16.对带头结点head的循环单链表尾结点(由p所指向)判非空的条件为p->next=head。
17.在栈结构中，允许插入的一端称为栈顶；在队列结构中，允许插入的一端称为队尾。
18.队列中元素的入队和出队应遵循__先进先出  ____原则，数据元素1，2，3，4，5按照次序入队
后，第一个出队的是__1  ____。
19.在循环队列中，存储空间为0～n-1。设队头指针front指向队头元素前一个空闲元素，队尾指
针指向队尾元素，那么其队空标志为rear=front，队满标志为(rear+1)% n=front。
20.设顺序表有19个元素，第一个元素的地址为200，且每个元素占3个字节，则第14个元素的存
储地址为239。
21.在一个长度为n的顺序表中删除第i个元素（1≤i≤n），需向前移动n-i个元素。
22.在一个长度为n的顺序表中第i个元素前（1≤i≤n），插入一个元素，需向后移动n-i+1
个元素。
23.在顺序存储的线性表中插入或删除一个元素平均约移动表中__50%_（或一半）_的元素。
24.在顺序表中访问任意一结点的时间复杂度均为 O(1) ，因此，顺序表也称为随机存取的数据
结构。
25.在n个结点的单链表中要删除已知结点*p，需到它的前驱结点的地址，其时间复杂度为O（n）。
26.一个广义表为(a,(a,b),d,e,((i,j),k))，则该广义表的长度为__5___，深度为__3___。
27.已知广义表A=((a,b,c),(d,e,f))，则运算tail (head (tail(A)))=(e,f)__。
28.已知广义表Ls=(a,(b,c,d),e)，运用head和tail函数取出Ls中的原子b的运算是
_head(head(tail(LS)))___。
29.广义表((a,b),c,d)的表头是(a,b)表尾是(c,d)。
30.广义表(a,b,c,d)的表头是a 表尾是(b,c,d)___。
31.两个串相等的充分必要条件是:__串长相等___ 且 __对应的字符相等_。
32.不含任何字符的串称为空串其长度为0 。
33.对于稀疏矩阵的压缩存储，通常用一个三元组表示非零元素的信息，其中包括非零元素所在的
行、列以及它的值。
34.若二叉树中有20个叶子结点，则该二叉树有19 个度为2的结点。
35.若二叉树中度为2的结点有15个，则该二叉树有__16________个叶子结点。
36.深度为h且有__2^h-1____个结点的二叉树称为满二叉树。
37.深度为k的二叉树最多有_2^k-1个结点，最少有k个结点，第i 层上最多有
_2^(i-1)____个结点。
38.深度为5的满二叉树共有31个结点，其中有__16_____个叶子节点。
39.若深度为6的完全二叉树的第6层有3个叶结点，则该二叉树一共有34个结点。
40.深度为15的满二叉树上，第11层有 _2^(11-1)=1024个结点。
41.一棵具有100个结点的完全二叉树，它的深度为7，其中度为1的结点有1个。
42.某二叉树的后根遍历序列为abd，中根遍历序列为adb，则它的先根遍历序列为dab。
43.哈夫曼树是指对于一组带有确定权值的叶子结点构造的具有最小带权路径长度
的二叉树。
44.具有m个叶子结点的哈夫曼树共有2m-1个结点。
45.已知一棵哈夫曼树含有60个叶子结点，则该树中共有 59个非叶子结点。
46.在一个具有n个顶点无向完全图中，含有n(n-1)/2边；在一个具有n个顶点有向完全
图中，含有n(n-1)边。一个具有4个顶点的无向完全图有6条边。
47.具有n个顶点的连通图至少需有n-1条边。
48.一个连通图的生成树是该图的极小连通子图。若这个连通图有n个顶点，则它的生成树
有n-1条边。
49.在有向图的邻接矩阵中，第i行中非零元素的个数正好是第i个顶点的出度；第i列中非零
元素的个数正好是第i个顶点的入度。
50.在一个图中，所有顶点的度数之和等于所有边数的2倍。
51.在无向图G的邻接矩阵A中，若A［i］［j］等于1，则A［j］［i］等于1。
52.对二叉排序树进行中序遍历，可以得到按关键字从小到大排列的结点序列。
53.一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当折半查值为82的
结点时，经过  4 次比较后查成功。
54.在线性表中采用折半查法查一个数据元素，线性表中元素应该按值有序，并且采用___顺序
存储__存储方法。
55.在简单选择排序、堆排序、快速排列、归并排序四种排序方法中，排序方法稳定的是__归并排序。
56.冒泡排序是一种稳定的排序方法，对n个元素的序列进行冒泡排序时，最多需进行n-1趟。该
排序方法的时间复杂度为O(n2)。
57.给定序列{100，86，48，73，35，39，42，57，66，21}，按堆的定义，则它一定大根堆。
58.数据结构是指数据及其相互之间的_一种或多种关系____。当结点之间存在M对N（M：N）的联
系时，称这种结构为____图状结构_____。
59.队列的插入操作是在队列的__队尾___进行，删除操作是在队列的__队头__进行。
60.每次从无序表中顺序取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做__直接
插入_排序；每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做__简单选择(或直接选择)____排序。
61.二叉树的前序遍历序列为A，B，C，E，F，D，G，H，中序遍历序列为A，E，C，F，B，G，，H，
其后序遍历序列为__ E,F,C,G,H,D,B,A____。
62.对于一棵具有n个结点的二叉树，若一个结点的编号为i(0＜i＜n-1），则它的左孩子结点的编
号为2i，右孩子结点的编号为 2i+1，双亲结点的编号为 i/2 。
63.在一个具有6个顶点的无向完全图中，包含有15 条边，在一个具有6个顶点的有向完全
图中，包含有30条弧。
64.快速排序在平均情况下的时间复杂度为__O(nlog2n)__，在最坏情况下的时间复杂度为__
O(n2)__。
65.从一棵二叉排序树中查一个元素时，若元素的值等于根结点的值，则表明__查成功_____，
若元素的值小于根结点的值，则继续向__左子树______查，若元素的大于根结点的值，则继续向__右子树______查。
66.在循环单链表中，最后一个结点的指针域指向___首___结点。
67.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为_9_个，树
的深度为__3___，树的度为__3__。
68.通常从四个方面评价算法的质量：_正确性_、_可读性_、__健壮性__和__效率与低存储量
需求_。
69.假设一棵完全二叉树含1000个结点，则其中度为2的结点数为___499___。
70.一个算法的时间复杂度为(3n3+2n—7)／(5n)，其数量级表示为O(n2)。
数据结构与算法分析答案
71.在快速排序、堆排序和归并排序中，最坏时间复杂度为O(n2)的排序算法有_快速排序_____。
72.数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的关系有
限集合。
73.在归并排序中，进行每趟归并的时间复杂度为____O(n)_____，整个排序过程的时间复杂度为
___O(nlog2n)_______，空间复杂度为___ O(n)_____。
74.若一棵二叉树有10个叶结点，则该二叉树中度为2的结的点个数为__9___。
75.对用邻接矩阵表示的具有n个定点和e条边的图进行任一种遍历时，其时间复杂度为 O(n2)，
对用邻接表表示的图进行任一种遍历时，其时间复杂度为___ O(n+e) __。
76.从有序表（12，18，30，43，56，78，82，95）中依次二分查43和56元素时，其查长度分
别为__1____和___3___。
77.对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为_2n_个，其中_ n-1__个用
于指向孩子， n+1__个指针是空闲的。
78.从逻辑结构看，线性表是典型的___线性结构__，树是典型的___非线性结构___。
79.设二叉树中结点的两个指针域分别为lchild和rchild，则判断指针变量p所指向的结点为叶子
结点的条件是____p->lchild==NULL && p->rchild==NULL。
80.栈是一种__先进后出___表。队列又称为___先进先出___表。
81.若对序列(49，38，65，97，76，13，27，50)采用直接选择排序法排序，则第三趟结束后序列的
状态是__(13,27,38),97,76,49,65,50_。
82.利用关键码分别为10，20，30，40的四个结点，能构造出__14__种不同的二叉排序树.
83.设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序方法对
其进行（按递增排序），__冒泡排序___最省时间， __快速排序___最费时间。
84.空串的长度是__0_；空格串的长度是__空格的个数_。串中所含字符个数称为该串的____长度_.
85.在n个结点的单链表中，在P指向的结点之后插入一个结点的时间复杂度为__ O(n)_。
86.设SQ为循环队列，存储在数组d[m]中，则SQ出队操作对其队头指针front的修改是__front=
（front+1）% m____。
87.树的度是指__树内各结点的度____的最大值。
88.已知链栈的结点结构为栈顶指针为top，则实现将指针p所指结点插入栈顶的语句依次为__
__p->next=top___和_top=p__。
89.堆排序的空间复杂度___ O(1)__。
90.深度为n(n>0)的二叉树最多有_____2^n-1___个结点。
91.设关键字序列为(K l，K2，…，K n)，则用筛选法建初始堆必须从第_n/2____个元素开始进行筛选。
92.图有_邻接矩阵___  、____邻接表__等存储结构，遍历图有 _深度优先搜索____ 、 ___广度优
先搜索__等方法。
93.在一个有向图的邻接表中，一个顶点的链表中结点的个数等于这个顶点的__出度__ ，在逆邻接
表中，一个顶点的链表中结点的个数等于这个顶点的___入度__ 。
94.对于有10个元素的有序表采用二分查，需要比较3次方可到其对应的键值，则该元素在有
序表中的位置可能是_1，3，6，9___。
95.折半查有序表（4，6，12，20，28，38，50，70，88，100），若查表中元素20，它将依次
与表中元素______________比较大小。
96.在对一组记录关键字（54，38，96，23，15，72，60，45，83）进行冒泡排序时，整个冒泡排序
过程中需进行_8__趟才能完成。
97.对关键字序列(52，80，63，44，48，91)进行一趟快速排序之后得到的结果为__48，44，52，63，
80，91__。
98.在堆排序和快速排序中，若初始记录接近正序或反序，则选用_堆排序___；若初始记录基本无序，
则最好选用__快速排序___。
99.在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录
60插入到有序表时，为寻插入位置至少需比较 __3________次。
100. 设一组记录关键字序列为(80，70，33，65，24，56，48)，则用筛选法建成的初始堆为_（80，70，56，65，24，33，48）或_(24，65，33，80，70，56，48)。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。