数据结构复习题.docx

数据结构复习题.docx

《数据结构复习题.docx》由会员分享，可在线阅读，更多相关《数据结构复习题.docx（16页珍藏版）》请在冰点文库上搜索。

数据结构复习题

考试时间：

2014年1月10日（星期五）14时30分～16时30分

考试教室安排：

B413 

考试方式：

闭卷笔试

考试成绩＝卷面（60％）＋平时作业（40％）

考试题型（参考）：

1、选择（20分）

2、填空（20分）

3、综合应用（60分）

4、算法设计（30分）

题型

1单选题（10题，2分/题，20分）

2填空题（5题，4分/题，20分）

3应用题（6题，10分/题，60分）

4附加题（2题，15分/题，30分）

（写C函数）

题型

1单选题（10题，2分/题，20分）

如：

存取数据采用先进先出原则的是（）。

A、线性表B、字符串C、栈D、队列

2填空题（5题，4分/题，20分）

如：

循环队列，head,tail分别指向队头，队尾，最大长度n，判队满的条件为。

3应用题（6题，10分/题，60分）

如：

假设对一段电文“abcdcbcacab”进行Huffman编码。

画出对应的Huffman树，并写出每个字符的Huffman编码。

4附加题（2题，15分/题，30分）（写C函数）

如：

哈希表用拉链法解决冲突，结构如下：

#defineLEN32

structnode{intdata;structnode*next;};

structnode*HashTab[LEN];

①写哈希函数inthash（intkey）。

（5分）

②写函数structnode*srch（intkey），查找key。

若找到，返回其结点指针；否则将其插入表中再返回其结点指针。

（10分）

一、线性结构

（包括：

表、栈、队、串、数组、广义表）

1.假设有二维数组A7×9，每个元素用相邻的6个字节存储，存储器按字节编址。

已知A的起始存储位置（基地址）为1000，末尾元素A[6][8]的第一个字节地址为多少？

若按列存储时，元素A[4][7]的第一个字节地址为多少？

答：

①末尾元素A[6][8]的第一个字节地址＝1000＋（7行×9列—1）×6B＝1000＋62×6=1372

②按列存储时，元素A[4][7]的第一个字节地址＝1000＋（7列×7行＋4）×6B＝1000＋53×6=1318

2.在KMP算法中，已知模式串为LIUYULIUWENYU，请写出模式串的next[j]函数值，并分析next[j]函数值的大小与KMP算法的比较次数多少（或时间）有何关系，简单解释你的理由。

答：

next[j]函数值=0111112341111

next[j]函数值越大，比较次数越多；

反之，函数值越小，则比较次数越少，时间越快。

2、非线性结构

（包括：

二叉树、树、图）

1.已知一棵二叉树的前序序列和中序序列分别为：

ABDGCEFH和DGBAECHF，则该二叉树的后序序列是什么？

答：

既可先画树而得后序序列，也可直接推出后序序列，结果为：

GDBEHFCA

总结二叉树的常见题有：

1.先序/中序/后序遍历的递归算法

2.如何判定一棵二叉树是二叉排序树?

2.假设字符a,b,c,d,e,f的使用频度分别是0.07,0.09,0.16,0.18,0.23,0.27，写出a,b,c,d,e,f的Huffman编码并计算其平均码长WPL。

（10分）

3.设A～H8个字符出现的概率为:

w={0.10,0.16,0.01,0.02,0.29,0.10,0.07,0.25},设计最优二进制码并计算平均码长。

（10分）

答：

最优二进制码构造同上，WPL=2.59

解：

（1）根据给定的n个权值构成n颗二叉树的集合F

（2）在F中选取两颗根结点的权值最小的数作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值较小者

（3）在F中删除这两棵树，同时将新得到的二叉树加入F中

（4）重复

（2）和（3），直到F只含一棵树为止

图

1.某无向图G的邻接表如下图所示。

要求：

①请画出该图G的逻辑结构图；

②根据邻接表写出其深度优先遍历序列和广度优先遍历序列（设访问起点为v3）；

③根据遍历结果，画出图G的深度优先和广度优先生成树。

2.下图为某无向图的邻接表，按教材算法分别写出深度优先搜索和广度优先搜索的结果，并画出逻辑结构图。

3、查找和排序

查找算法包括：

顺序、折半、二叉排序树、散列

排序算法包括：

插入、交换、选择、基数

1.假设一有序表中有23个元素，现进行折半查找，则平均查找长度是多少？

提示：

现在n=23比较小，应当用穷举法罗列：

全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋8×5）＝89ASL＝89/23=3.87

2.已知一组关键字为（10，24，32，17，31，30，46，47，40，63，49），设哈希函数H（key）＝keyMOD7。

请解答：

（1）    写出用链地址法处理冲突构造所得的哈希表；

（2）    若查找关键字17，需要依次与哪些关键字进行比较？

（3）    若查找关键字60，需要依次与哪些关键字比较？

（4）  假定每个关键字的查找概率相等，求查找成功时的平均查找长度。

（10分）

答：

ASL≈1.82

3.已知一组关键字为（10，24，32，17，31，30，46，47，40，63，49），设哈希函数H（key）＝keyMOD13。

请写出用线性探测法处理冲突构造所得的哈希表。

（10分）

4.欲将无序序列（23,78,12,35,69,95,11,09,35*,48,99,26）中的关键码按升序重新排列，请写出快速排序第一趟排序的结果序列。

另外请画出堆排序（小根堆）的初始堆。

提示1：

快速排序注意要按振荡式逼近算法来实现；

第一趟排序的结果为：

09，11，12，[23]，69，95,35,78,35*,48,99,26

提示2：

堆排序要从排无序堆开始，从最后一个非终端结点开始，自下而上调整,而且要排成小根堆。

初始堆序列为：

09，23，11，35，48，26，12，78，35*,69,99,95

5.采用一个辅助空间的堆排序算法对关键字序列{46，37，65，96，75，11，25，48}排序，如果排序结果为逆序，请给出初始堆。

答：

最终逆序则意味着要建小根堆：

1137254875654696

6.快速排序在什么情况下最快？

什么样情况下最慢？

在最慢的情况下请提出一种提高效率的解决办法。

答：

快速排序在无序状态下最快，在基本有序（或逆序）下最慢。

提高效率的解决办法为，选中间位置的元素a下标mid为中枢

7.设有1000个无序的元素，需排出前10个最大（小）的元素，你认为采用哪种排序方法最快？

为什么？

答：

堆排序

第2章线性表

线性表具有两种存储方式，即顺序方式和链接方式。

现有一个具有五个元素的线性表L={23，17，47，05，31}，

若它以链接方式存储在下列100～119号地址空间中，每个结点由数据（占2个字节）和指针（占2个字节）组成，如下图所示。

其中指针X，Y，Z的值分别为多少？

该线性表的首结点起始地址为多少？

末结点的起始地址为多少？

1、填空题

1、向一个长度为n的顺序表中的第i个元素（0≤i≤n-1）之前插入一个元素时，需向后移动_______个元素。

2、在单链表中，要删除某一指定的结点，必须找到该结点的_______结点。

3、访问单链表中的结点，必须沿着_____一次进行。

4、在一个单链表中p所指结点之后插入一个s所指结点时，应执行_________和________的操作。

二、选择题

1、链表不具备的特点是。

①可随机访问任一节点②插入删除不须要移动元素

③不必事先估计存储空间④所需空间与其长度成正比

2、带头结点的单链表head为空的判定条件是。

①head==NULL②head->next==NULL

③head->next==head④head!

=NULL

3、如果最常用的操作是取第i个结点及其前驱，则采用存储方式最节省时间。

①单链表②双链表③单循环链表④顺序表

第3章栈与队列

和栈类似，队列中亦有上溢和下溢现象。

此外，顺序队列中还存在“假上溢”现象。

因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。

因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。

该现象称为假上溢。

为充分利用向量空间。

克服上述假上溢现象的方法是将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为循环队列（CircularQueue）。

①空队列的特征？

约定：

front=rear

②队列会满吗？

极易装满！

因为数组通常有长度限制，而其前端空间无法释放。

问：

什么叫“假溢出”？

如何解决？

答：

在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。

解决假溢出的途径———采用循环队列

在循环队列中又出现了一个新问题：

如何判定队满和队空？

由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。

因此，我们无法通过front=rear来判断队列“空”还是“满”。

解决此问题的方法至少有三种：

其一是另设一个布尔变量以区别队列的空和满；

其二是少用一个元素的空间，约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：

rear所指的单元始终为空）；

其三是使用一个计数器记录队列中元素的总数（实际上是队列长度）

2、顺序循环队列的队空和队满判断问题

新问题：

在循环队列中，空队特征是front=rear；队满时也会有front=rear；判决条件将出现二义性！

解决方案有三：

①使用一个计数器记录队列中元素个数（即队列长度）；

　　判队满：

count>0&&rear==front

判队空：

count==0

②加设标志位，出队时置０,入队时置１,则可识别当前front=rear属于何种情况

　　判队满：

tag==1&&rear==front

判队空：

tag==0&&rear==front

③少用一个存储单元

　　判队满：

front=＝（rear+1）%MaxQueueSize

判队空：

rear==front

1、单项选择题

1、栈的特点是B，队列的特点是A。

（A）先进先出（B）先进后出

2、栈和队列的共同特点是C。

（A）都是先进后出（B）都是先进先出

（C）只允许在端点处插入和删除元素（D）没有共同点

3、一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是C。

（A）edcba（B）decba（C）dceab（D）abcde

4、若已知一个栈的进栈序列是p1，p2，p3，…，pn。

其输出序列为1，2，3，…，n，若p3=1，则p1为C。

（A）可能是2（B）一定是2（C）不可能是2（D）不可能是3

5、设有一个空栈，栈顶指针为1000H（十六进制，下同），现有输入序列为1、2、3、4、5，经过PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH后，输出序列是3，栈顶指针是8。

①5、4、3、2、1②2、1③2、3

④3、4⑤1002H⑥1004H

⑦1005H⑧1003H

6、一个队列的入对序列是若1，2，3，4，则队列的输出序列是B。

（A）4，3，2，1（B）1，2，3，4

（C）1，4，3，2（D）3，2，4，1

7、若用一个大小为6的一维数组来实现循环队列，且当前rear和front的值分别为0和3。

当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是B。

（A）1和5（B）2和4（C）4和2（D）5和1

第4章串

一、选择题

1、空串与空白串是相同的，这种说法B。

（A）正确（B）不正确

2、串是一种特殊的线性表，其特殊性体现在D。

（A）可以顺序存储（B）数据元素是一个字符

（C）可以链接存储（D）数据元素可以是多个字符

3、D是C语言中”abcd321ABCD”的子串。

（A）abcd（B）321AB（C）”abcABC”（D）”21AB”

二、填空题

1、两个串相等的充分必要条件是。

两个串的长度相等且对应位置的字符相同

2、空串是零个字符的串，其长度等于零。

3、空白串是由一个或多个空格字符组成的串其长度等于其包含的空格个数。

4、模式串t=‘abaabcac”的next函数值序列为-10011201，nextval函数值序列为-1，0，-1，1，0，2，-1，1。

第5章数组与广义表

广义表L=（a，（b,c）），进行GetTail（L）操作后的结果为（）

A、cB、b,c

C、（b,c）D、（（b,c））√

第6章树

1、单项选择题

1、由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法B。

（A）正确（B）错误

2、某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是D。

（A）空或只有一个结点（B）完全二叉树

（C）二叉排序树（D）高度等于其节点数

3、深度为5的二叉树至多有C个结点。

（A）16（B）32（C）31（D）10

4、根据使用频率为5个字符设计的哈夫曼编码不可能是D

（A）111，110，10，01，00

（B）000，001，010，011，1

（C）100，11，10，1，0

（D）001，000，01，11，10

二、填空题

1、树和二叉树的主要差别是（1.树中结点的最大度数没有限制，而二叉树结点的最大度数为2；）（2.树的结点无左、右之分，而二叉树的结点有左、右之分。

）

2、深度为k的完全二叉树至少有___（2的K-1次方）_个结点，至多有（2的k次方）-1个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是（2的k-2次方）+1_________。

3、一棵二叉树的第i（i³1）层最多有（2的i-1次方）个结点；一棵有n（n>0）个结点的满二叉树共有（2的logn次方）个叶子结点和（2的logn次方）-1个非叶子结点。

1、已知二叉树的先序、中序和后序序列分别如下，其中有一些看不清的字母用*表示，请构造出一棵符合条件的二叉树并画出该二叉树。

先序序列是：

*BC**FG

中序序列是：

CB*EAG*

后序序列是：

*EDB*FA

2、将右图所示的树转化为二叉树，并写出先序遍历，中序遍历和后序遍历的结果。

课后习题:

1、假设对一段电文“abcdcbcacab”进行Huffman编码。

画出对应的Huffman树，并写出每个字符的Huffman编码。

2、假设字符a,b,c,d,e,f的使用频度分别是0.2,0.4,0.02,0.1,0.15,0.13,构造Huffman树，写出各字符的Huffman编码。

3、树用孩子兄弟链接法存储，结点结构为

structNode{chardata，structNode*child，*brother；}

写C函数voidPreOrder（structNode*root），先根遍历树。

root是指向树根的指针。

第7章图作业

一、单项选择题

1、一个n个顶点的无向图最多有C条边。

（A）n（B）n（n-1）（C）n（n-1）/2（D）2n

2、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的B倍。

（A）1/2（B）1（C）2（D）4

3、关键路径是事件结点网络中A。

（A）从源点到汇点的最长路径（B）最长的回路

4、下面不正确的说法是B。

A、关键活动不按期完成就会影响整个工程的完成时间

B、任何一个关键活动提前完成，将使整个工程提前完成

C、所有关键活动都提前，则整个工程提前完成

D、某些关键活动若提前完成，将使整个工程提前完成。

二、填空题

1、一个图的邻接矩阵表示法表示法是惟一的，而邻接表表示法是不惟一的。

2、在有n个顶点的有向图中，每个顶点的度最大可达2（n-1）。

1、设有向图G如下图所示，试给出：

（1）该图的邻接矩阵；

（2）该图的邻接表；

（3）从V1出发的“深度优先”遍历序列；

（4）从V1出发的“广度优先”遍历序列。

2、对下图的AOE网，求出：

（1）每个事件的最早发生时间和最迟发生时间；

（2）每个活动的最早开始时间和最迟开始时间；

（3）画出关键活动组成的图。

对哪些活动提速，可使整个工期提前。

课后习题:

1、有向网N={V,E}，V={0,1,2,3,4}，E={<0,1,5>，<0,3,7>，<0,4,15>，<1,2,5>，<2,4,1>，<3,2,2>}，E中每个元组的第三个元素表示权。

（1）、画出该网。

（2）、写出该网的邻接矩阵。

（3）、求关键路径，写出计算过程。

（4）用迪杰斯特拉（Dijkstra）算法求最短路径，写出顶点0到其它各顶点的最短路径长度、路径及产生过程。

2、

（1）、自定义无向图的邻接表存储结构Graph。

（2）、基于上述图结果，写函数voidKruskal（Graphg），用克鲁斯卡尔算法求最小生成树，并输出树的生长过程。

期末考试题型：

1、算法编程题（35分）

2、算法编程题（35分）

3、算法编程题（30分）

共100分

4、附加题：

算法编程题（30分）

期末考试是上机机考：

题型跟我们平时的实验题型描述，输入、输出一致。

分为必做题共3题和附加题1题。

题目难度2题较易，1题相对适中。

附加题较难。

题目内容都是13个实验及所做的练习题中的相关内容！

题型：

1、问题描述2、算法描述3、输入描述

4、输入样本5、输出描述6、输出样本

1、问题描述

给出初始数据

采用冒泡排序（或简单选择排序或直接插入排序，将数据从小到大排成有序序列

2、算法

通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序

3、输入

每个样本分1行：

第一行：

第一个数字m表示样本数目，其后跟m个样本

4、输入样本

81221123456

5、输出

每一趟快速排序的结果（为一行，包括原始序列）

6、输出样本

1221123456

6512341221 

1234561221

本学期必做的13个实验

1顺序表实验（易）

2单链表实验（易）

3堆栈应用括号匹配实验

4串应用KMP算法实验

5Huffman编码的设计与应用实验（难）

6图的深度优先搜索实验（较难）

7最短路径实验（较难）

8顺序查找实验（易）

9折半查找实验（易）

10二叉排序树实验（难）

11哈希查找实验（难）

12快速排序实验（易）

13希尔排序实验（易）