数据结构练习题(1)

《数据结构练习题(1)》由会员分享，可在线阅读，更多相关《数据结构练习题(1)（8页珍藏版）》请在金锄头文库上搜索。

1、数据结构练习题说明：除题中另有说明外，本书均采用下面的存储结构及操作二叉链表的 C 语言存储描述如下 单向链表的存储typedef struct BiTNode typedef struct LNodechar data； /元素信息 ElemType data；struct BiTNode *lchild，rchild ； struct LNode *next；BiTNode，*BiTree； LNode，*LinkList ；邻接表的 C 语言存储描述如下 基本操作如下typedef struct Arc InitStack(S)int adj； /顶点序号 StackEmpty(S)st

2、ruct Arc *next； Push(S，e)ArcNode，*ARC ； /表结点 Pop(S，e)typedef struct Vnode /头结点 InitQueue（Q ）char data； /元素信息 QueueEmpty（Q）ARC *first； Enqueue（Q ，x）GraphN； /N 为顶点的实际个数 DelQueue（Q，x）一、判断正误 1、线性表采用链式存储，则链表中结点总数一定等于元素总数。2、栈是一种后进先出的线性表，因此，元素的进栈序列和出栈序列不可能相同。3、无论采用何种存储结构，队列的入队、出队次序一定相同。4、由三个不同关键字构造的二叉排序树的基

3、本形态共有五种。5、若非空二叉树的先序、中序遍历序列相同，则必为仅有一个根的二叉树。6、二叉链表存储的二叉树中结点总数为 n，则空指针域总数必为 n+1。7、n(0)个权值作为叶子构造的哈夫曼树中结点总数为 2n-1。8、森林的后序遍历与它对应的二叉树的中序遍历相同。 9、折半查找的平均查找效率高于顺序查找，因此，查找某一元素时，折半查找所需与关键字的比较次数一定少于顺序查找。10、二叉排序树的中序遍历序列按关键字递增有序。11、有向图的邻接表的第 i 个链表中表结点总数为该顶点的度。 12、顺序表，链表，二叉链表，邻接表，散列表均为存储结构。13、选取散列函数时，冲突越少越好。14、冒泡，直

4、接插入，归并，基数排序均为稳定排序。15、快速排序最坏的时间复杂度为 O（N*logN ） 。16、不稳定排序后，相同关键字元素的相对位置一定发生改变。17、直接插入排序适用于元素个数较少或初始序列基本有序情况。18、对称矩阵压缩存储后不具备随机存取的特点。19、在考虑存储结构的前提下，有向图的拓扑排序序列一定唯一。20、折半查找要求元素必须按关键字有序，且只能采用顺序存储结构。二、填空题数据的基本单位是_，数据结构常见的逻辑结构有_，存储结构有_。数据结构的逻辑结构可视为一个二元组 Data_Structure=（ D，S ） ，其中 D 是_，S 是_。数据结构的抽象数据类型 ADT 是指

5、一个数学模型及定义在该模型上的一组操作。它可用三元组（D，S ，P）表示，其中 D 是数据对象，S 是_，P 是_设计一个好的算法应达到的目标是正确性、_、_和高效率低存储量。算法时间效率、空间效率的度量分别称为_、_。5、顺序表、链表分别通过_、_体现元素的前驱、后继的逻辑关系。6、在表长为 n 的顺序表中插入、删除元素时，在等概率条件下平均移动元素的次数分别为_、_，具体移动的元素个数与_有关。7、已知 L 为头指针的带头结点的单循环链表（指针域为 next） ，a若 R 为尾指针，则满足的条件为_，b若该表为空表，则满足的条件是_。8、已知五个元素 ABCDE 的进栈次序为 ABCDE，

6、a若 C 为第一个出栈元素，则下一个出栈的元素可能是_；b能否得到出栈序列 CDBEA_、CEDAB_？9、若三个元素 ABC 的进栈次序为 ABC，则借助栈一共可以得到_中出栈序列？10、已知顺序存储的循环队列中，f，r 分别为队头、队尾指针， MAX 为队列中存储单元的最大个数。若当队列中仅有一个空闲单元时视为队满，则队空、队满条件分别为_、_；一般情况下，队列中元素个数可表示为_ 。11、广义表 A=(a，(b)，c)，(d)，(e，f ，g)的表长为_，深度为_，利用取表头、表尾运算表示原子 e 的表达式为_。12、广义表中元素既可以是单原子，也可以是_，广义表的两个基本操作是_和_。

7、13、10 个结点二叉树至多有_个叶子，最低高度为_。14、83 个结点的完全二叉树高度为_，其中叶子个数为_，一度结点个数为_。15、n(n0)个结点的完全二叉树叶子个数为 _，一度结点个数为 _。16、高度为 5 的 BST 树结点总数至多，至少为_，_ 。17、n 个叶子的哈夫曼树最高高度为_，结点总数为_。18、从本质上而言，森林的孩子兄弟链表与它转换所对应的二叉树的_存储结构一致。19、n 个顶点的无向、有向完全图的边数分别是_、_，n 个顶点的强连通图至少有_条边。20、无向网的最小生成树的构造算法是_和_；n 个顶点的无向网构造的最小生成树中边的条数为_。21、构造散列表要解决的

8、两个问题是_；若将关键字序列的散列地址定位在 100 至 110之间，则散列函数可表示为 H（key）=_。22、从理论上讲，散列查找的算法效率为_，但实际应用时，常常因为_使查找速度有所降低。23、若关键字序列为正序，则直接插入、冒泡、简单选择、归并、快速、堆排序中排序效率最高的是_和_，此时时间复杂度为_。24、希尔排序每趟的排序方法是_，平均时间复杂度为_；快速排序的平均时间复杂度为_，最坏时间复杂度为_。25、排序时所需与关键字的比较次数仅与元素个数有关而与关键字的初始序列无关的排序方法是_，若关键字个数为 n 个，则第一趟的比较次数为_。26、写出三种不稳定的排序方法的名称_、_和_

9、。27、n 个元素进行起泡排序时，最好情况下只需进行_次比较和_次交换，最坏情况需进行_次比较和_次交换。三、综合题1、已知线性链表中结点的数据域、指针域依次为 data、next，写出在表中删除*p 结点的语句（设该结点存在后继）及*p 结点前插入*s 结点语句。2、简述顺序表、链表的各自特点。3、简述链式存储中头结点、头指针；结点、元素的区别。4、n 阶矩阵 Aij（1i，jn）或 Aij（0i，j n-1）的上三角(不含对角线)为常数 C，下三角无规律，设计压缩存储方案。5、画出广义表 A=(a，(b)，c)，(d)，(e，f)的链式存储结构。6、画出由三个结点构造的二叉树的基本形态。7

10、、已知一棵度为 5 的树中 1 度，2 度， ，5 度结点的个数依次为 1，2， ，5，则叶子个数为多少？8、证明任意一棵二叉树中叶子数等于两度结点数加 1。9、已知字符， ，G 的权值依次为(5 ，7，8，10， 9，20，30)，设计各个字符的Huffman 编码，画出 Huffman 树的存储结构，并计算 WPL 值。10、已知二叉树的先序，中序遍历序列分别为 EFHBDGAC，FHDBEAGC，画出二叉树的逻辑结构，顺序存储结构和中序线索二叉树的逻辑结构图示。11、已知某二叉树由八个字符 A-H 组成，先序，中序，后序遍历序列分别为_AC_E_GH；C_DB_GHF；_DA_FEB，画

11、出二叉树的逻辑结构和后序线索二叉树的存储结构。提示：每个空白处至少缺少一个字符。12、已知森林的逻辑结构如图 1 所示，画出它的孩子兄弟链表存储结构及其转换的二叉树的逻辑结构。13、已知无向网如图 2 所示，画出根据 PRIM 算法构造的最小生成树步骤图示。14、画出图 3 所示无向图的邻接表，以它为基础写出深度、广度优先遍历序列及画出深度、广度优先生成树（从结点 A 开始） 。15、画出图 4 所示有向图的邻接矩阵，邻接表，并以该邻接表为基础，写出它的深度、广度优先遍历序列、拓扑排序序列（其中拓扑排序要求标示出入度为 0 的顶点进栈、出栈的先后次序） 。16、分别画出关键字序列(34，23，

12、56，32，27，30，58，89，56) 构造的 BST 树、AVL 树的逻辑结构，并分别计算等概率成功查找条件下的 ASL 值；设 a1、a2、a3 是不同的关键字且 a1next；q=p ；n=0；while (q)n+；q=q-next；n1=_；for(i=1；idata)；_；if(_) p=p-next；while(p)POP(S，x)；if（p-data!=x）break；p=p-next；if(_)return(1)；else return(0)； 2、 删除 L 单链表中最大元素结点的算法。void delmax(LinkList &L)LinkList p，q，r；int

13、 m；r=L；p=L-next；if (p)m=p-data； _；p=p-next；while(p)if (_)_；m=p-data；_；p=p-next；q=r-next；_free(q)； 3、将二叉树 bt 的各个结点左右子树互换算法， ADDQ(Q，bt)，DELQ(Q)，EMPTY(Q)分别代表入队、出队、判队空函数（10 分）void EXCHANGE(BiTree &bt)Tree p，q；if (bt)ADDQ(Q，bt)；while(!EMPTY(Q)p=DELQ(Q)；if(p-lchild)_；if(p-rchild)_；q=_；p-rchild=_；_=q； 4、将带头结点的单链表中所有的奇数放在链表的前面，偶数放在后面。void change(LinkList &L)LinkList p，q；p=L-next；if(p)while(_ )if (_)q=p-next；p-next=q-next ； _；L-next=q；else_；4、 设算术表达式右字符串 exp 表示，可以包含三种括号：“（） ”， “ ”， “ ”它们可以任意次序嵌套使用，实现算法填空，判定表达式中括号是否匹配int f(char exp)int legal=1； SqStack s；InitStack(&s)；for (int I=0；legal&e