发布时间 : 星期一 文章数据结构习题及答案更新完毕开始阅读
108.假定一组记录为（46，79，56，38，40，84），在冒泡排序过程中进行第一趟排序后的结果为＿＿。
109.假定一组记录为（46，79，56，64，38，40，84，43），在冒泡排序过程中进行第一趟排序时，元素97将最终下沉到其后第＿＿位置。
110.＿＿排序方法使键值达的记录逐渐下沉，使键值小的记录逐渐上浮。
111.假定一组记录为（46，79，56，38，40，80）对其进行快速排序的过程中，共需要＿＿趟。
112.假定一组记录为（46，79，56，25，76，38，40，80）对其进行快速排序的第一次划分后，右区间内元素个数为＿＿。
113.假定一组记录为（46，79，56，38，40，80），对其进行快速排序的第一次划分后的结果为＿＿。
114.在所有排序方法中，＿＿排序方法采用的是折半查找法的思想。
115.在简单选择排序中，记录比较次数的时间复杂度为＿＿，记录移动次数的时间复杂度为＿＿。
116.若对一组记录（46，79，56，38，40，80，35，50，74）进行简单选择排序，用k表示最小值元素的下标，进行第一趟是可得初值为1，则在第一趟选择最小值的过程中，k的值被修改＿＿次。
117.在时间复杂度为O（n2）的所有排序方法中，＿＿排序方法使不稳定的。 118.假定一个堆为（38，40，56，79，46，84），则利用堆排序方法进行第一趟交换和对根结点筛运算后得到的结果为＿＿。
119.在所有排序方法中，＿＿方法使数据的组织采用的是完全二叉树的结构。 120.＿＿排序方法能够每次从无序表中查找出一个最小值。
三、名词解释
1.数据 2.数据元素 3.数据对象 4.数据结构 5.逻辑结构 6.时间复杂度 7.空间复杂度 8.栈 9.队列 10.压缩存储 11.树形结构 12.结点的度 13.树的度 14.树的深度 15.有序树 16.遍历 17.哈夫曼树 18.邻接关系 19.路径 20.连通图
21.强连通图 22.完全无向图 23.完全有向图 24.主关键字
四、简答题
1.简述线性结构，树形结构，网状结构的不同。 2.简述算法复杂度的评价方法。
3.设有两个算法在同一台机器上运行，其执行时间分别为100n2和2n,要使前者快于后者，n至少为多大？
4.在顺序表中插入和删除一个结点需平均移动多少个结点，具体移动的次数取决于哪些因素？
5.简述定义：线性表、单链表、线性表的存储方式、循环链表、双向链表。
6.在单链表，双向链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将p从相应的链表中删去？若可以，其时间复杂度分别为多少？
7.有哪些链表可仅有一个尾指针来唯一确定，即从尾指针出发能访问到链表上任何一个结点？
8.何时选用顺序表，何时选用链表作为线性表的存储结构？
9.简述栈与队列的不同之处。
10.设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序压入其中，请回答下述问题： 若入、出栈次序为Push(1),Pop(),Push(2),Push(3), Pop(),Pop(),Push(4),Pop(),则出栈的数字序列如何？
能否得到出栈序列1423和1432，并说明为什么不能得到或者如何得到。
请分析1，2，3，4的各种排列中，哪些序列是可以通过相应的入,出栈操作得到的。 11.举例说明栈的“上溢”和“下溢”现象。
12.循环队列的优点是什么？如何判别它的空和满？
13.假定用一维数组a[7]顺序存储一个循环队列，队首和队尾指针分别用front和rear表示，当前队列中有5个元素：23，45，67，80，34，其中23为队首元素，front的值为3，请画出对应的存储状态，当连续进行4次出队运算后，再让15，36，48元素依次进队，请再次画出对应的存储状态。
14.空串和空格串有何区别？字符串中空格符有何意义？空串在串的处理中有何作用？ 15.两个字符串相等的充要条件是什么？
16.二叉树和树之间有何区别？一棵度为2的树与二叉树有何区别？
17.在一棵二叉树如图1.11所示。写出对此树进行先序，中序，后序遍历时得到的结点序列。 18.已知一棵二叉树的中序遍历序列为CDBAEGF,先序遍历序列为ABCDEFG,试问能不能唯一确定一棵二叉树？若能，画出该二叉树。若给定先序遍历序列和后序遍历序列，能否唯一确定？
19.将图1.12所示的树转换成二叉树。
20.一棵度为2的有序树与一棵二叉树有何区别？
21.试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 22.高度为h的完全二叉树至少有多少个结点？至多有多少个结点？
23.试采用顺序存储方法和链式存储方法分别画出如图1.13所示各二叉树的存储结构。 24.假定用于通信的电文由8个字母组成，分别是A，B，C，D，E，F，G，和H，各字母在电文中出现的概率为：5%，25%，4%，7%，9%，12%，30%，8%，试为8个字母设计哈夫曼编码。
25.根据如图1.14所示的带权有向图G，试回答下面问题：
（1）给出从结点V1出发按深度优先搜索遍历G所得的结点序列，并给出按广度优先搜索遍历G所得的结点序列。
（2）给出从结点V1到结点V8的最短路径。 26.对于如图1.15所示的有向图，请给出
（1）对应的邻接矩阵，并给出A，B，C三个顶点的出度与入度。 （2）邻接表表示和逆邻接表表示。 （3）强连通分量。
27.假设图的顶点是A，B，C，D，?请根据下述邻接矩阵画出相应的有向图和无向图。 （1）0 1 1 1 （2） 0 1 1 0 0 1 0 1 1 0 0 0 1 0 1 1 0 1 1 0 0 0 1 1 1 1 0 0 1 0 1 0
28.对n个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判别下列有关问题： （1）图中有多少条边？
（2）任意两个顶点i和j是否有边相连？ （3）任意一个顶点的度是多少？
29.试述顺序查找法，折半查找法和分块查找法对查找表中元素的要求。
30.若有一个长度为n的表，其查找该表中每个元素的概率相同，采用顺序查找、折半查找和分块查找3种查找方法进行查找时的其平均查找长度各为多少？
31.设有一组关键字（17，13，14，153，29，35）需插入到表长为12的散列表中，请回答下列问题：
（1）设计一个适合该散列表的哈希函数。
（2）用设计的哈希函数将上述关键字插入到散列表中，画出其结构，并指出用线性探测再散列法解决冲突时构造散列表的装填因子为多少？ 32.选择排序算法是否稳定？为什么？
33.给出一组关键字（19，01，26，92，87，11，43，87，21），进行冒泡排序，列出每一遍排序后关键字的排列次序，并统计每遍排序进行的关键字比较次数。 34.直接插入排序算法是否稳定？为什么？
35.堆排序为什么是不稳定的排序？试举例说明。
五、应用题
1.指出下列每个算法的功能并求出其时间复杂性。 （1）int sum1（int n） { int p=1,s=0;
for(int i=1；i<=n;i++) { p*=i; s+=p； }
return s; }
(2) void mtable（int n）
{for（int i=1；i<=n;i++） for（int j=i；j<=n;j++） printf（“i*j=%d ”，i*j）； printf（“\\n”）; }
(3)void cmatrix(int a[M][N],int d) /*M和N为全局整型常量*/ {
for（int i=0；i 2. void AA(sqlist &L)/*L为一个顺序表*/ {initiate_sqlist(L);/*初始化顺序表L*/ end_insert(L,30);/*把三十个元素插入到表尾*/ begin_insert（L，50）/*把五十个元素插入到表头*/ int a[4]={5,8,12,15}; int i; for(i=0;i<=4;i++) end_insert(L,a[i]);/*依次把每个元素插入到表尾*/ for(i=0;i<=4;i++) begin_insert(L,a[i]);/*依次把每个元素插入到表头*/ } 该算法被调用执行后，得到的顺序表L为：＿＿。 3. viod AC（lklist &HL）/*HL为一个单链表*/ {initiate_lklist（HL）；/*初始化单链表HL*/ insert_lklist(HL,30,1);/*向单链表第一个位置插入元素30*/ insert_lklist(HL,50,2);/*向单链表第二个位置插入元素50*/ int a[5]={15，8，9，26，12}； for（inti=0；i<5;i++）begin_insert(HL,a[i]); /*向HL的表头依次插入数组a中的前五个元素值*/ int x=delete_lklist（HL，3）； /*此函数删除HL中的第三个结点并返回该结点的值*/ end_lklist（HL，x）；/*向HL的表尾插入x*/ } 该算法被调用执行后，得到的HL单链表所对应的线性表为：＿＿＿＿。 4.分别编写在顺序表和带头结点的单链表上统计出值为x的元素个数的算法，统计结果由函数值返回。 5.分别编写在顺序表和带头结点的单链表上删除其值等于x的所有元素。 6.分别编写在顺序表和单链表上删除具有重复值的多余结点，使每个结点的值均不同。如将线性表（2，8，9，2，5，5，6，8，7，2）变为（2，8，9，5，7）。 7.有6个元素A，B，C，D，E，F依次入栈，允许任何时候出栈，能否得到下列的各个出栈序列，若能，给出出栈操作的过程，若不能，简述其理由。 （1）CDBEFA（2）ABEDFC（3）DCEABF（4）BAEFCD 8.设计一个递归算法，计算出返回1至n之间的所有整数平方和。 9.斐波那契（Fibonacci）数列的定义为：它的第一项和第二项均为1，以后各项为前两项之和。若斐波那契数列中第n项用Fib(n)表示，则计算公式为： 试编写出计算Fib(n)的递归算法和非递归算法。 10.假定在一个链式队列中只设置队尾指针，不设置队首指针，并且让队尾结点的指针域指向队首结点（称此为循环队列），试分别写出在循环队列上进行插入和删除操作的算法。 11.设以二叉链表为二叉树的存储结构，结点的结构如下： 其中data为整数，试设计一个算法void change(bitreptrr),若结点左孩子data的值大于右孩子的data域的值，则交换其左右子树。 12.设计一个算法，统计出二叉树中等于给定值x的结点个数，该统计值由变量k带回（k的初值为0）。 Void countl（bitreptrr，datatype x,int &k） 13.设计一个算法，从一棵二叉树查找出所有结点的最大值并返回。 Datatype maximum(bitreptrr) 14.假设用于通信的电文有8个字母组成，字母在电文中出现的频率分别为：7，19，2，6，32，3，21，10。试为这8个字母设计哈夫曼编码。 15.已知一个无向图的邻接矩阵如图1.16所示，试写出从顶点V0出发分别进行深度优先和