admin 管理员组文章数量: 1086019
2024年4月22日发(作者：factory下载地址)
《数据结构与算法》复习题
应用简答题。
1．有下列几种用二元组表示的数据结构，画出它们分别对应的逻辑图形表示，
并指出它们分别属于何种结构。
（1）A ＝ ｛D，R｝，其中：D＝｛a，b，c，d，e，f，g，h｝，R ＝｛r｝，
r ＝ ｛
（2）B ＝ ｛D，R｝，其中：D＝｛a，b，c，d，e，f，g，h｝，R ＝｛r｝，
r ＝ ｛
（3）C ＝ ｛D，R｝，其中：D＝｛1，2，3，4，5，6｝，R ＝｛r｝，
r ＝ ｛（1，2），（2，3），（2，4），（3，4），（3，5），（3，6），
（4，5），（4，6）｝
2．简述顺序表和链表存储方式的特点。
答：顺序表的优点是可以随机访问数据元素，缺点是大小固定，不利于增减结
点（增减结点操作需要移动元素）。链表的优点是采用指针方式增减结点，非
常方便（只需改变指针指向，不移动结点）。其缺点是不能进行随机访问，只
能顺序访问。另外，每个结点上增加指针域，造出额外存储空间增大。
3．对链表设置头结点的作用是什么？（至少说出两条好处）
答：其好处有：
（1）对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，
所要做的都是修改前一个结点的指针域，因为任何元素结点都有前驱结点（若
链表没有头结点，则首元素结点没有前驱结点，在其前插入结点和删除该结点
时操作复杂些）。
（2）对带头结点的链表，表头指针是指向头结点的非空指针，因此空表与非空
表的处理是一样的。
4．对于一个栈，给出输入项A，B，C。如果输入项序列由A，B，C组成，试给
出全部可能的输出序列。
5．设有4个元素1、2、3、4依次进栈，而栈的操作可随时进行（进出栈可任
意交错进行，但要保证进栈次序不破坏1、2、3、4的相对次序），请写出所有
不可能的出栈次序和所有可能的出栈次序。
6．现有稀疏矩阵A如图所示，要求画出三元组表示法和十字链表表示法：
150022
01330
0006
0
000
91000
00280
015
00
00
00
00
00
7．设4维数组的4个下标的范围分别为
[-1，0]，[1，2]，[1，3]，[-2，-1]，请分别按行序和列序列出各元素。
8．有一份电文中共使用5个字符：a，b，c，d，e，它们出现的频率依次为4，
7，5，2，9，试画出对应的哈夫曼树（请按左子树根结点的权小于等于右子树
根结点的权的次序构造），并求出每个字符的哈夫曼编码。
9．有如图所示的二叉树，回答如下问题。
（1） 写出该树的中序遍历序列;
d
g
b
e
h
i
a
c
f
（2） 写出该树的先序遍历序列;
（3） 写出该树的后序遍历序列；
（4） 画出该二叉树的中序线索二叉树；
（5） 画出该二叉树的后序线索二叉树；
（6） 画出该二叉树对应的森林；
10．已知一棵树边的集合为
{ ,h> , 11．假设二叉树采用顺序存储结构，如图所示。 （1） 画出二叉树表示； （2） 写出先序遍历、中序遍历和后序遍历的结果； （3） 写出结点值c的双亲结点，其左、右孩子； （4） 画出把此二叉树还原成森林的图。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 e a f 12．已知一棵二叉树的中序序列为cbedahgijf，后序序列为cedbhjigfa，画出 该二叉树的先序线索二叉树。 d g c j h i b 13．某二叉树的先序遍历序列是abdgcefh，中序遍历序列是dgbaechf，给出其 后序遍历序列。 14．将下图所示森林转换成为二叉树，并写出转化后二叉树中序遍历结果。 15．有一份电文中共使用8个字符：a、b、c、d、e、f、o、i，它们的出现 频率依次为10，20，15，32，40，60，26，18。试画出对应的哈夫曼树（请 按左子树根结点的权小于等于右子树根结点的权的次序构造），并求出每个 字符的哈夫曼编码。 16．已知某系统在通信联络中只可能出现A,B,C,D,E,F,G,H八种字符，其频 率为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11试设计哈夫曼编码。 17．对有五个顶点{v1,v2,v3,v4,v5}的图的邻接矩阵如图所示，解答下列问 题： （1）画出逻辑图。 DE F B A C G H I J K L M P Q R N O （2）画出该逻辑结构的邻接表。 （3）基于邻接矩阵写出图的深度、广度优先遍历序列。 18．如图所示，解答如下问题： （1）写出从定点A出发，深度和广度优先遍历方法遍历该图的顶点序列。 （2）根据普里姆算法和克鲁斯卡尔算法，分别求它的最小生成树，要求给出构 造过程。 01003010 0 60020 100 500 A 5 6 B E 3 G 1 1 5 F 4 C 3 2 D 19．给出如图所示的无向图G的邻接矩阵和邻接表两种存储结构。并在给定的 邻接表的基础上，指出从顶点1出发的深度优先遍历和广度优先遍历序列。 1 3 4 2 5 图 一个无向图G 20．使用普里姆算法构造出如图所示的图G的一棵最小生成树。 1 6 1 5 5 5 2 3 4 2 3 6 4 6 56 图 一个无向图G 21．使用克鲁斯卡尔算法构造出如图所示的图G的一棵最小生成树。 1 623 4 725 18 12 2 5 8 1510 7 5 4 3 6 20 图 一个无向图G 22．设有一棵二叉树，它的中序和后序遍历结果如下，请画出该二叉树。 中序：1 4 3 5 6 2 后序：4 6 5 3 2 1 23．设一棵顺序二叉树具有10个结点，请计算其中叶子结点的数目。 24．设如图所示二叉树是由某棵树转化而来，请画出其对应的原树。 1 2 3 4 6 5 7 25．设有如图所示的一棵树，请将其转化为二叉树。 1 2 14 45 8 10 12139 11 67 3 26．下表给出了某工程各工序之间的优先关系和各工序所需时间。解答下列问 题： （1）画出相应的AOE图； （2）给出各事件的最早发生时间和最晚发生时间； （3）找出关键路径，并指明完成该工程所需最短时间； （4）若把AOE网视为AOV网，给出其一个拓扑序列的例子。 工序 A 代号 B C D E F G H I J K L M M 15 10 50 8 时间 15 40 90 15 80 60 15 30 20 40 先驱 － － A,B B 工作 C,D B E G,I E I F,I H,J,K L G 27．某不带权有向图如下所示。给出其邻接矩阵和邻接表表示。 A F B G E DC 28．求如下AOE图的关键路径，要求给出求解过程。 29．有一组数据，内容如下：8，15，38，57，68，88，98，108，129，234， 256 试用二分查找法查找68和222，要求先画出二叉折半检索树，然后写出查找过 程。 30．已知有序表为｛12，18，24，35，47，50，62，83，90，115，134｝，请 画出采用折半查找法对应的判断树。 31．设数据集合d＝｛1，12，5，8，3，10，7，13，9｝，试完成下列各题： （1）依次取d中各数据，构造一棵二叉排序树bt。 （2）如何依据此二叉树bt得到d的一个有序序列。 （3）画出在二叉树bt中删除“12”后的树结构。 32．对给定的数列R＝{7，16，4，8，20，9，6，18，5}，构造一棵二叉排序 树，并且 （1）给出按中序遍历得到的数列R1。 （1）给出按后序遍历得到的数列R2。 33．已知序列{17，18，60，40，7，32，73，65，85}，请给出采用冒泡排序法 对该序列作升序排序时每一趟的结果。 34．已知序列{503，87，512，61，908，170，897，275，653，462}，请给出 采用快速排序法对该序列作升序排序时每一趟的结果。 35．已知序列{503，87，512，61，908，170，897，275，653，462}，请给出 采用堆排序法对该序列作升序排序时每一趟的结果。 36．已知序列{503，87，512，61，908，170，897，275，653，462}，请给出 采用希尔排序法对该序列作升序排序时每一趟的结果。 37．已知序列{17，18，60，40，7，32，73，65，85}，请给出采用直接插入排 序法对该序列作升序排序时每一趟的结果。 38．设散列表的长度m＝13（0，1，2，…，12），散列函数为H（k）＝k mod m，给定的关键字序列为{19，14，23，10，68，20，84，27，55，11}。试画出 用线性探测法解决冲突时所构造的散列表。
版权声明：本文标题：数据结构(C语言) 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://roclinux.cn/p/1713730598a648896.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论