《数据结构》习题2

1、3个结点可构成棵不同形态的树。

2、利用直接选择排序算法对n个记录进行排序，最坏的情况下，记录交换的次数为。

3、一个图的_______表示法是唯一的，而______表示法是不唯一的。

4、一棵深度为h的满二叉树上的结点总数为，一棵深度为h的完全二叉树上的结点总数的最小值为，最大值为。

5、在一棵完全二叉树中有n个结点，对这些结点按层序编号，若一个结点编号为69，则其双亲编号为，有左孩子的条件是，其左孩子编号为。

6、二维数组M的成员是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要________个字节；M的第8列和第5行共占___________个字节；若M按行优先方式存储，元素M[8][5]的起始地址与当M按列优先方式存储时的________元素的起始地址一致。

7、设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是________。

8、在线性表的顺序存储中，元素之间的逻辑关系是通过决定的；在线性表的链式存储中，元素之间的逻辑关系是通过_________决定的。

9、n个顶点的连通图的生成树有n-1条边。

10、通常数组只有______给定一组有定义的下标，存取相应的数据__和___给定一组有定义的下标，修改相应数据元素的值_____两种运算，因此常采用__顺序_______来存储数组。

11、3个节点可以构成 5 棵不同形态的二叉树。

12、对于一棵具有n个结点的二叉树，当它为一棵完全二叉树时具有最小高度，即为∟log2n」+1，当它为一棵单支树时具有最大高度，即为n 。

13、在一棵有n个结点的完全二叉树中，对这些结点按层序编号，若一个结点编号为59，则其双亲编号为，若一个结点编号为23，则其有右孩子的条件是。

14、数组M中每个元素的长度是3个字节，行下标i从1到8，列下标j从1到10，从首地址EA开始连续存放在存储器中。

第二章习题与解答一判断题1．线性表的逻辑顺序与存储顺序总是一致的。

2．顺序存储的线性表可以按序号随机存取。

3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。

4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。

5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。

6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。

7．线性表的链式存储结构优于顺序存储结构。

8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。

9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。

10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。

二单选题 (请从下列A，B，C，D选项中选择一项)1．线性表是( ) 。

(A) 一个有限序列，可以为空；(B) 一个有限序列，不能为空；(C) 一个无限序列，可以为空；(D) 一个无序序列，不能为空。

2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。

插入一个元素时平均要移动表中的（）个元素。

(A) n/2 (B) n+1/2 (C) n -1/2 (D) n3．线性表采用链式存储时，其地址( ) 。

(A) 必须是连续的；(B) 部分地址必须是连续的；(C) 一定是不连续的；(D) 连续与否均可以。

4．用链表表示线性表的优点是（）。

(A)便于随机存取(B)花费的存储空间较顺序存储少(C)便于插入和删除(D)数据元素的物理顺序与逻辑顺序相同5．某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( )存储方式最节省运算时间。

(A)单链表(B)双链表(C)单循环链表(D)带头结点的双循环链表6．循环链表的主要优点是( )。

(A)不在需要头指针了(B)已知某个结点的位置后，能够容易找到他的直接前趋(C)在进行插入、删除运算时，能更好的保证链表不断开(D)从表中的任意结点出发都能扫描到整个链表7．下面关于线性表的叙述错误的是( )。

第二章线性表一、选择题1.一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是( )（A）110 （B）108（C）100 （D）120参考答案：B2. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。

（A）64（B）63 （C）63.5 （D）7参考答案：C3.线性表采用链式存储结构时，其地址（）。

(A) 必须是连续的 (B) 部分地址必须是连续的(C) 一定是不连续的 (D) 连续与否均可以参考答案：D4. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（）（A）s->next=p;p->next=s; （B） s->next=p->next;p->next=s;（C）s->next=p->next;p=s; （D）p->next=s;s->next=p;参考答案：B5.在一个单链表中，若删除p所指结点的后续结点，则执行（）（A）p->next=p->next->next; （B）p=p->next; p->next=p->next->next;（C）p->next=p->next; （D）p =p->next->next;参考答案：A6.下列有关线性表的叙述中，正确的是（）（A）线性表中的元素之间隔是线性关系（B）线性表中至少有一个元素（C）线性表中任何一个元素有且仅有一个直接前趋（D）线性表中任何一个元素有且仅有一个直接后继参考答案：A7.线性表是具有n个（）的有限序列（n≠0)（A）表元素（B）字符（C）数据元素（D）数据项参考答案：C二、判断题1.线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。

（）2.如果没有提供指针类型的语言，就无法构造链式结构。

（）3.线性结构的特点是只有一个结点没有前驱，只有一个结点没有后继，其余的结点只有一个前驱和后继。

一．判断题（下列各题，正确的请在前面的括号内打√；错误的打×）第1章（√）（1）数据的逻辑结构与数据元素本身的内容和形式无关。

（√）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。

（×）（3）数据元素是数据的最小单位。

（×）（4）数据项是数据的基本单位。

（×）（5）数据的逻辑结构和数据的存储结构是相同的。

（√）（6）数据的逻辑结构是各数据元素之间的逻辑关系，是用户按使用需要而建立的。

（√）（7）数据的物理结构是指数据在计算机内实际的存储形式。

（√）（8）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。

（√）（9）数据的存储结构是数据的逻辑结构的存储映像。

（√）（10）算法是对解题方法和步骤的描述。

第2章（×）（1）链表的物理存储结构具有同链表一样的顺序。

（×）（2）链表的每个结点都恰好包含一个指针域。

（√）（3）线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。

（×）（4）链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。

（×）（5）顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。

（√）（6）数组元素的存储位置是下标的线性函数。

（√）（7）在单链表中，元素的存储位置用指针联系，所以可以从头结点开始查找任何一个元素。

（×）（8）顺序存储线性表的插入和删除操作不需要付出很大的代价，因为平均每次移动仅一半的元素。

（×）（9）顺序存储方式的优点是存储密度大，插入、删除效率高。

（×）（10）在单链表中，要取得某个元素，只要知道该元素的指针即可，因此单链表是随机存取的存储结构。

第3章（√）（1）大多数排序算法都有比较关键字大小和改变指向记录的指针或移动记录本身两种基本操作。

第二章习题1. 描述以下三个概念的区别：头指针，头结点，首元素结点。

2. 填空：（1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。

（2）在顺序表中，逻辑上相邻的元素，其物理位置相邻。

在单链表中，逻辑上相邻的元素，其物理位置相邻。

（3）在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存储位置由指示，除首元素结点外，其它任一元素结点的存储位置由指示。

3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。

按要求从下列语句中选择合适的语句序列。

a. 在P结点后插入S结点的语句序列是：。

b. 在P结点前插入S结点的语句序列是：。

c. 在表首插入S结点的语句序列是：。

d. 在表尾插入S结点的语句序列是：。

供选择的语句有：（1）P->next=S;（2）P->next= P->next->next;（3）P->next= S->next;（4）S->next= P->next;（5）S->next= L;（6）S->next= NULL;（7）Q= P;（8）while(P->next!=Q) P=P->next;（9）while(P->next!=NULL) P=P->next;（10）P= Q;（11）P= L;（12）L= S;（13）L= P;4. 设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。

试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。

5. 写一算法，从顺序表中删除自第i个元素开始的k个元素。

6. 已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。

试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。

第六章图1、填空题一个有 n 个结点的无向图中,所有顶点的度数之和等于所有边数之和的 _2__倍。

一个有 n 个结点的强连通图,最多有 _n(n-1_/2__条边,最少有 ___n-1_ 条边。

在一个无向图中,所有顶点的度数之和等于所有边数之和的 __2____倍。

2、判断题1无向图的邻接矩阵一定是对称矩阵。

(√2有向图的邻接矩阵一定是对称矩阵。

(×3图的深度优先搜索路径是唯一的。

(×4图的广度优先搜索路径不是唯一的。

(√5一个图可能存在多棵最小生成树。

(√6无向图的邻接矩阵一定是对称的,有向图的邻接矩阵一定是不对称的。

(√7图的关键路径是指从源点到汇点的最短路径。

(×8用邻接矩阵法存储图,占用的存储空间数量只与图中边数有关,与结点个数无关。

(×9对一个图分别进行深度优先搜索和广度优先搜索,得到的结点序列一定是相同的。

(×10图的关键路径是指从源点到汇点的最长路径。

(√3、选择题1一个无向连通图的生成树是含有该连通图的全部顶点的 __A__。

A 、极小连通子图B 、极小子图C 、极大连通子图D 、极大子图 2具有 e 条边的有向图,它的邻接表中有 _D__个弧结点。

A 、 e-1B 、 2eC 、 2(e-1D 、 e3如果某图的邻接矩阵是对角线元素均为零的上三角矩阵,则此图是 __D__A 、无向图B 、完全图C 、强连通图D 、有向无环图4顶点个数为 n 的有向图最多有 __D_条弧。

A 、 n-1B 、 n(n-1/2C 、 n(n+1/2D 、 n(n-1应用题:1. 请给出图 1的所有最小生成树。

(10分图 1共两棵。

第一棵为:(5分错一条边扣 1分。

第二棵为:(5分错一条边扣 1分。

2. 请给出图 2的所有拓扑排序序列。

(16答案如下:仅有两个第一个:abcdefgh (错一个字符扣 1分第二个:abcdegfh (错一个字符扣 1分3、对于有向无环图(如图 3,写出它的所有不同的拓扑有序序列。

一、填空题1.数据结构包括、和三方面的内容。

2.数据的逻辑结构分为、、、。

3.数据的逻辑结构分为和两大类。

4.数据的存储结构被分为、、、。

5.数据的存储方式有、、和四种基本存储方式。

6.顺序存储和链式存储相比较的存储密度大，的插入删除方便。

7.在线性表的单链接存储结构中，每个结点包含有两个域，一个叫域，另一个叫域。

8.在线性表的单链接存储中，若一个元素所在结点的地址为P，则其后继结点的地址为，若假定P为一个数组a中的下标，则其后继结点的下标为。

9.在顺序存储的向量中，设第一个元素的地址为loc(k1)，每个元素占用的空间为M，则第i个元素ki的地址为loc(ki)=loc(k1)+(i-1)*M 。

10.在循环单链表中，最后一个结点的指针域指向结点。

11.队列的插入操作在进行，删除操作在进行。

12.一棵n个结点的树，其边数为条。

13.设二叉树根结点的层数为0，则第i层上最多有个结点。

14.在一棵二叉树中，第5层上的结点数最多为。

15.深度为 K 的完全二叉树，至少有个结点，至多有个结点。

16.深度为 8 (根的层次号为 1 )的满二叉树有个叶子结点。

17.深度为K的二叉树结点总数最大为。

18.深度为 k (根的层次号为 1 )的满二叉树有个叶子结点。

19.在完全二叉树中，对结点按层次编号，根结点编号为1。

若结点i有右子女，则右子女的编号为，左子女的编号为。

20.按后根次序周游树林，正好等同于按次序周游与之对应的二叉树。

21.按先根次序周游树林，正好等同于按次序周游对应的二叉树。

22.对一棵二叉排序树进行中序遍历时，得到的结点序列是一个。

23.在一个具有n个顶点的无向完全图中，包含有条边。

24.设有m个结点的无向图中，如果其边数为就称为完全图。

25.在图中，与结点相关的边的数目称为该结点的。

26.在有向图的邻接表和逆邻接表表示中，每个顶点邻接表分别链接着该顶点的所有和结点。

27.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为，在表尾插入元素的时间复杂度为。

数据结构第二章习题第2章线性表一、单项选择题1．线性表就是具备n个_________的非常有限序列。

a．表元素b．字符c．数据元素d．数据项2．线性表是_________。

a．一个非常有限序列，可以为空b．一个非常有限序列，不可以为空c．一个无穷序列，可以为空d．一个无穷序列，不可以为空3．线性表使用链表存储时，其地址_________。

a．必须是连续的b．一定是不连续的c．部分地址必须是连续的d．连续与否均可以4．链表不具备的特点是_________。

a．可以随机出访任一结点b．填入删掉不须要移动元素c．不必事先估算存储空间d．所须要空间与其长度成正比5．设立线性表存有n个元素，以下操作方式中，_________在顺序单上同时实现比在链表上同时实现效率更高。

a．输出第i(1≤i≤n)个元素值b．互换第1个元素与第2个元素的值c．顺序输入这n个元素的值d．输出与给定值x相等的元素在线性表中的序号6．设立线性表中存有2n个元素，以下操作方式中，_________在单链单上同时实现Obrero在顺序单上同时实现效率更高。

a．删掉选定的元素b．在最后一个元素的后面插入一个新元素c．顺序输出前k个元素d．互换第i个元素和第2n-i-1个元素的值(i=0,1…,n-1)7．如果最常用的操作是取第i个结点及其前驱，则采用_________存储方式最节省时间。

a．单链表中b．双链表中c．单循环链表d．顺序表8．与单链表相比，双链表的优点之一是_________。

a．填入和删掉操作方式更直观b．可以展开随机出访c．可以省略字段指针或表尾指针d．出访前后相连结点更有效率9．率先垂范结点的单链表中l为觑的认定条件就是_________。

a．l==nullb．l->next==nullc．l->next==ld．l!=null10．在一个具备n个结点的有序单链表填入一个崭新结点并仍然维持有序的时间复杂度就是_________。

第二章线性表2.1描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。

并说明头指针和头结点的作用。

答：头指针是一个指针变量，里面存放的是链表中首结点的地址，并以此来标识一个链表。

如链表H，链表L等，表示链表中第一个结点的地址存放在H、L中。

头结点是附加在第一个元素结点之前的一个结点，头指针指向头结点。

当该链表表示一个非空的线性表时，头结点的指针域指向第一个元素结点，为空表时，该指针域为空。

开始结点指第一个元素结点。

头指针的作用是用来惟一标识一个单链表。

头结点的作用有两个：一是使得对空表和非空表的处理得以统一。

二是使得在链表的第一个位置上的操作和在其他位置上的操作一致，无需特殊处理。

2.2填空题1、在顺序表中插入或删除一个元素，需要平均移动（表中一半）元素，具体移动的元素个数与（表长和该元素在表中的位置）有关。

2、顺序表中逻辑上相邻的元素的物理位置（必定）相邻。

单链表中逻辑上相邻的元素的物理位置（不一定）相邻。

3、在单链表中，除了首元结点外，任一结点的存储位置由（其直接前驱结点的链域的值）指示。

4、在单链表中设置头结点的作用是（插入和删除元素不必进行特殊处理）。

2.3何时选用顺序表、何时选用链表作为线性表的存储结构为宜?答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑：1.基于空间的考虑。

当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。

2.基于时间的考虑。

若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。

并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。

2.10 Status DeleteK(SqList &a,int i,int k)//删除线性表a中第i个元素起的k个元素{if(i<1||k<0||i+k-1>a.length) return INFEASIBLE;for(count=1;i+count-1<=a.length-k;count++) //注意循环结束的条件a.elem[i+count-1]=a.elem[i+count+k-1];a.length-=k;return OK;}//DeleteK2.11设顺序表中的数据元素递增有序，试写一算法，将X插入到顺序表的适当位置上，以保持该表的有序性。

习题2一．选择题1．线性表是具有n个（）的有限序列（n>0)。

A. 表元素B.字符C.数据元素D.数据项2. 线性表的顺序存储结构是一种（）的存储结构。

A．随机存取 B．顺序存取 C．索引存取 D．HASH 存取3. 在一个长度为n的顺序表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需向后移动（）个元素。

A. n-1B. n-i+1C. n-i-1D. i4. 在一个长度为n的顺序表中，设在任何位置上的删除操作都是等概率的，删除一个元素时大约要移动表中的（）个元素。

A. n+1B. n-1C. (n-1)/2D. n5.若线性表采用顺序存储结构，每个元素占用 4 个存储单元，第一个元素的存储地址为 100,则第 12 个元素的存储地址是（）。

A．112 B.144 C.148 D.4126.在一个长度为 n 的顺序表的任一位置插入一个新元素的时间复杂度为（）。

A. O(n)B.O(n/2)C. O(1)D.O(n2)7.在一个单链表中，已知*q结点是*p结点的前驱结点，若在*q和*p之间插入*s结点，则执行（）。

A. s->next=p->next; p->next=s;B. p->next=s->next; s->next=p;C. q->next=s; s->next=p;D. p->next=s; s->next=q;8.设指针p指向单链表中某结点(数据域为m)，指针f指向将要插入的新结点(数据域为x)，当x插在结点m之后时，只要先修改（）后修改p->next=f即可。

A. f->next=p;B. f->next=p->next;C. p->next=f->next;D. f=NULL;9.下面关于线性表的叙述错误的是（）。

A．线性表采用顺序存储必须占用一片连续的存储空间B．线性表采用链式存储不必占用一片连续的存储空间C．线性表采用链式存储便于插入和删除操作的实现D．线性表采用顺序存储便于插入和删除操作的实现10．在具有n个结点的有序单链表中插入一个新结点，并使链表仍然有序的算法的时间复杂度是（）。

第2章线性表一、选择题1.表长为N 的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（E ），删除一个元素需要移动的元素个数为（A ）。

A. (N-1)/2B. NC. N+1D. N-1E. N/2F. (N+1)/2G. (N-2)/22.线性表是具有N 个（C ）的有限序列。

A、表元素B、字符C、数据元素D、数据项E、信息3.“线性表的逻辑顺序和物理顺序总是一致的。

”这个结论是（B ）。

A、正确的B、错误的C、不一定，与具体结构有关。

4.线性表采用链式存储结构时，要求内存中可用存储单元的地址（D ）。

A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、连续或不连续都可以。

5.带头结点的单链表为空的判定条件是（B ）。

A、head==NULLB、head->next==NULLC、head->next==headD、head!=NULL6.不带头结点的单链表head 为空的判定条件是（A ）。

A、head==NULLB、head->next==NULLC、head->next==headD、head!=NULL7.非空的循环单链表head 的尾结点P 满足（ C ）。

A、P->NEXT=NULLB、p=NULLC、p->next==headD、p==head8.在一个具有n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（B ）。

A、O(1)B、O(n)C、O(n2)D、O(nlog2n)9.在一个单链表中，若删除P 所指结点的后继结点，则执行（ A ）。

A、p->next=p->next->nextB、p=p->next;p->next=p->next->nextC、p->next=p->next;D、p=p->next->next;10.在一个单链表中，若在Ｐ所指结点之后插入Ｓ所指结点，则执行（B ）。