复习题数据结构(1)

单项选择题

1.数据的（B）包括集合、线性、树和图4种基本类型 A．存储结构 移动（ B）个元素。 A．n-i

B．n-i+1

C．n-i-1

D．i

3下面程序的时间复杂度为（ C ）。 For(i=0;i

B. O(n2)

C. O(n*m)

D.O(n+m)

4长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法时间复杂度为（ C）。 A．O(0)

B．O(1)

C．O(n)

D．O(n2)

5.数据结构就是研究（ D ）。 A．数据的逻辑结构

B．数据的存储结构

C．数据的逻辑结构和存储结构

B．逻辑结构

C．基本运算

D．算法描述

2.对一个长度为n的顺序表，在第i个元素（1≤i≤n+1）之前插入一个新元素时需向右

D．数据的逻辑结构、存储结构及其数据在运算上的实现 6下面关于算法的说法，错误的是（D ）。 A．算法最终必须由计算机程序实现

B．为解决某问题的算法和为该问题编写的程序含义是相同的 C．算法的可行性是指指令不能有二义性 D．以上三种说法都错误

7线性表L=（a1，a2 ，……an，）下列说法正确的是（D ）。 A．每个元素都有一个直接前驱和一个直接后继 B．线性表中至少要有一个元素

C．表中所有元素的排列顺序必须是由小到大或由大到小

D．除第一个和最后一个元素外，其余每个元素都有且仅有一个直接前驱和一个直接后继

8．下面关于线性表叙述错误的是（ B ）。 A．线性表采用顺序存储，必须占用一段地址连续的单元 B．线性表采用顺序存储，便于进行插入和删除操作 C．线性表采用链式存储，不必占用一段地址连续的单元 D．线性表采用链式存储，便于进行插入和删除操作 9用链表表示线性表的优点是（C） A．便于随机存取

B．存储空间比顺序存储方式少

C．便于插入和删除

D．数据元素的存储顺序与逻辑顺序相同

10若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋元素，则采用（ D ）存储方式最节省时间。

A．单链表 B．双链表

C．单向循环 D．顺序表

11.若队列采用顺序存储结构，元素的排列顺序（B） A．与元素值的大小有关

B．由元素进入队列的先后顺序决定 D．与作为顺序存储结构的数组大小有关

C. ACB

D.

C．与队头指针和队尾指针的取值有关 A. ABC BAC

13假定一个顺序循环队列存储于长度为n的一维数组中，其队头和队尾指针分别用front和rear表示，则判断队满的条件是（A） A．（rear+1）%n==front C．rear==（front-1）%n 是（D）。

A．（front+1）%n==rear C．front==0

B．front==rear+1 D．front==rear

C．31 C．n(n-1)

D．63 D．n(n+1)

B．front+1==rear D．rear==（front+1）%n

B. CAB

12.三个元素按照A,B,C的顺序入栈，下列哪一个是不合法的出栈序列？（B ）

14假定一个顺序循环队列的队头和队尾指针分别用front和rear表示，则判队空的条件

15.深度为5（假设空树的深度为0）的二叉树至多有（C ）结点。 A．64 A．n(n+1)/2 （ D）。 A．A B G D C E F

B．A B D G C F E

C．B D G C E FA

D．A B D G C E F

B．对栈不作任何判别 D．判别栈元素的类型

B．32

16一个具有n个顶点的无向完全图的边数为（ B ）

B．n(n-1)/2

17后序遍历序列为G D B E F C A,中序遍历序列为D G B A E C F，则前序遍历序列为

18 如果以链表作为栈的存储结构，则出栈操作时（ C ） A．必须判别栈是否满 C．必须判别栈是否空 A．必须连续 C．必须连续 A．存储结构 A．2

19线性表采用链式存储时，其地址（D ）。

B．部分地址必须连续 D．连续与否均可 B．逻辑结构

B．3

C．基本运算

C．4

D．算法描述

D．A~C项都不对

20数据的（ B ）包括集合、线性、树和图4种基本类型。 21一棵完全二叉树上有15个结点，其深度是不超过（C）的最大整数。

22若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用（ D ）存储方式最节省运算时间。 A．单链表 的顺序表

23.二叉树中第5层上的结点个数最多为__C__ A.8

B.15

B．双链表 C．带头结点的双循环链表 D．容量足够大

C.16 D.32

B．32 D．63

24.深度为5的二叉树至多有（ C ）结点。 A．64 C．31

25.将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子的编号为___A ___。 A.98 C.50 A.（A,(B,C)） C.((A),B,C)

填空题

1.对于给定的n个元素，可以构造出的逻辑结构有（ 树性结构 ）（ 图性结构 ）、、（线性结构 ）、（集合 ）4种。

2数据元素在计算机中的（ 存储 ）方式称为存储结构。

3线性结构中的元素之间存在（ 一对一 ）关系，树形结构中元素之间存在（ 一对多 ）关系，图形结构中的元素之间存在（ 多对多 ）关系。

4设单链表的结点结构为（data，*next），已知指针p指向单链表中X结点，指针q指向y的新结点，若将结点y插入到结点x之后，则需要执行以下两条语句（ q->next=p->next ）， （ p->next=q ）。

5数据的（ 逻辑 ）结构与数据元素本身的内容和形式无关。

6一个算法的好坏取决于该算法的（ 时间复杂度 ）和（ 空间复杂度 ）。 7数据结构中评价算法的两个重要指标是（ 时间复杂度 ）、空间复杂度。 8一个循环队列存储于下标由0开始且长度为m的一维数组中，假定队头和队尾指针分别为front和rear，则判断队空的条件为（ front==rear）。则判断队满的条件为（（rear+1）%n==front）。

9 队列的插入操作是在队列的（ 队尾 ）进行，删除操作是在队列的（ 队头 ）进行。 10堆栈的逻辑特点是（ 先进后出 ），队列的逻辑特点是（ 先进先出 ）。 11堆栈的逻辑特点是（ 后进先出 ），队列的逻辑特点是（ 先进先出 ）。二者的共同点是只允许在它们的（ 端点 ）处插入和删除数据元素。

12堆栈操作设输入元素的顺序为1,2,3,4,5，要在栈的输出端得到43521，则应进行栈的基本运算表示应为：Push（S,1），Push(S,2)，Push(S,3)，Push(S,4)，Pop(S)，（ pop(S） ），（ Push(S,5) ），Pop(S)，Pop(S)，Pop(S)。 13设有一个链队，结点结构为data|next，front为队头指针，rear为队尾指针，当执行入队操作时需执行下列语句：malloc(p)；p->data=x; p->next=NULL；（rear->next=p ）；（rear=p）；

B.99 D.48

B.（A,B,C）

26．已知广义表的表头为A，表尾为(B,C)，则此广义表为____B____

D.(( A,B,C))

13、一棵二叉树有67个结点,这些结点的度要么是0，要么是2。这棵二叉树中度数为2的结点有 33 个。

14、一个哈夫曼(Huffman)树有19个结点，则其叶结点的个数是 10 。 15、一棵深度为6的满二叉树有 31 个分支结点和 32 个叶子。 16、设二叉树结点的先序序列为ABDECFGH，中序序列为DEBAFCHG,则二叉树的后序序列是 EDBFHGCA 。

17. 克鲁斯卡尔算法的时间复杂度为（ O（eloge ） ），适合求（ 边稀疏的网 ）的最小生成树。

18.空串是（由零个字符组成的串），其长度等于（ 0 ）。

19.空格串是（由一个或多个空格组成的串），其长度等于（ 串中空格字符的个数 ）。 20.两个字符串相等的充分必要条件是（串的长度相等，并且各个对应位置的字符都相等）。

21写出模式串p=“abaabcac”的next函数值序列为（01122312） 22、设有一稀疏图G，则G采用 （邻接表）存储结构较省空间。

23、已知广义表A=((a,b,c),(d,e,f)),则运算head(head (tail（A）)))=__d_ ________. 24．一棵深度为6的满二叉树有 31 个分支结点和 32 个叶子。 25．在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较 3 次。

应用题

1．什么是线性结构？线性结构的特点是什么？ 列举？ 2.什么是树形结构？树形结构的特点是什么？ 3.什么是图结构？

4.已知二叉树的前序ABCDEFGHIJ和中序CDBFEAIHGJ，试构造出相应的二叉树。 5.已知一棵二叉树的后序遍历序列为EICBGAHDF，中序遍历序列为ECIFBAGDH，请画出这棵二叉树，

7. 对于一个有10000个结点的二叉树，树叶最多有多少个？最少有多少个？ 8写出某个有向图的顶点V和弧E的邻接矩阵。 9已知某二叉树，写出前序遍历、中序遍历和后序遍历

10根据普里姆算法思想，画出构造该无向带权图最小生成树的过程。（5分） 11的有向带权图，根据狄克斯特拉算法思想，画出生成从顶点A到其余各项顶点最短路径的过程。

12已知序列{34，17，6，29，33，11，80，37}请用冒泡排序的方法从大到小进行排序，并给出详细过程。

13已知序列{34，17，6，29，33，11，80，37}请用直接选择排序的方法从大到小进行排序，并给出详细过程。

14、已知一棵二叉树的中序序列和后序序列分别为： DBGEACHF和DGEBHFCA，则该二叉树的前序序列是什么？试画出这棵二叉树。

15、给定权值集合{15,03,14,02,06,09,16,17}，构造相应的哈夫曼树，并计算它的带权路径长度。

16．设一数组A[5][6]，A[0][0]的地址为1100，且每个元素占2个存储单元，则这个二维数组的存储量为多少？A[4][5]的地址为多少？如按行优先顺序存储A[2][3]的地址为多少？

17.用序列（46，88，45，39，70，58，101，10，66，34）建立一个排序二叉树，画出该树，并求在等概率情况下查找成功的平均查找长度 18.按下列要求，写出相应结果

设关键字的输入次序为45，24，53，45，12，24，90。画出生成的二叉排序树（5分)。 19试画出具有3个结点的二叉树所有不同形态（5分）。 A A A / / \\ \\ B 、 B C 、 B / \\

C C

写算法

1.请写出顺序存储的线性表中，在第i个位置插入和删除数据元素x的实现算法。（请在关键部分给出注释。）

2.请写出链式存储的线性表中，在第i个位置插入和删除数据元素x的实现算法。（请在关键部分给出注释。）

3. 请写出链式堆栈操作中，入栈和 出栈的实现算法。（请在关键部分给出注释。）

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