数据结构复习题

填空

在数据结构中,?从逻辑上能够把数据结构分为
- 线性结构
- 非线性结构
数据结构在计算机内存中的表示是指
- 数据的存储结构
链式存储的特点是利用**指针** 来表示数据元之间的逻辑关系。
对于给定的n个元素，可以构造出的逻辑结构有
- 集合
- 树形结构
- 线性结构
- 图结构
顺序存储结构是通过==结点物理上相邻==表示元素之间的关系的；
- 链式存储结构是通过**结点指针**表示元素之间的关系的。
循环单链表的最大优点是：
- 从任一结点出发都可访问到链表中每一个元素。
堆栈是一种操作受限的线性表，

它只能在线性表的==一端==进行插入和删除操作，
对栈的访问是按照==后进先出==的原则进行的。

栈是==操作受限==的线性表，

其运算遵循的原则：后进先出。
栈可以在线性表的==栈顶==进行操作和删除。
循环队列的引入，
- 目的：克服假溢出时大量的移动数据元素。
对于一个具有n个结点的二叉树，
- 当它为一棵==完全==二叉树时具有最小高度。
哈夫曼树
- 是==带权路径长度最小的二叉树==，又称**最优二叉树**。
完全图
- 是**任意两个顶点之间存在边**；

连通图
- 是任意两个顶点之间都有路径。

一般线性表顺序查找，
- 查找成功的平均查找长度为==（n+1）/2==，
- 查找失败的平均查找长度为n+1。

15.采用分块查找时，

数组的组织方式：数据分成若干块，
每块内数据不必有序，但**块间必须有序，每块内最大的数据**组成索引块。

在线性表的顺序存储中
- 元素之间的逻辑关系是通过： 物理位置相邻 决定的
在线性表的链接存储中，
- 元素之间的逻辑关系是通过：**指针**决定的。
空格串
- 长度为：空格数，
- 空串的长度为 0 。
己知三对角矩阵A[1…9,1…9]的每个元素占2个单元，现将其三条对角线上的元素逐行存储在起始地址为1000的连续的内存单元中，则元素A[7,8]的地址为：
- 1038
设广义表L = ((),())
- head(L)：()；
- tail(L)：( ( ) )；
- L的长度：2；
- 深度：2。
一棵深度为k的二叉树，
- 最多有2k-1个结点。
图，的存储结构常采用____两种
- 邻接矩阵
- 邻接表。

22.指针q值为null，指针p指向单链表L的某个结点

删除其后继节点（要求由指针q指向）的语句是：
- q=p->next，
- p->next=q->next，
- free(q)

选择

n个顶点，e条边的有向图的邻接矩阵中非零元素有（C）个。
- A.n B.2e C.e D.n+e
如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（C）
- A. 栈 B. 队列 C. 树 D. 图
数据结构研究的内容是（D）。
- A．数据的逻辑结构 B．数据的存储结构
- C．建立在相应逻辑结构和存储结构上的算法 D．包括以上三个方面
若下面几个符号串编码集合中，不是前缀编码的是（B）。
- A．{0,10,110,1111} B．{11,10,001,101,0001}
- C．{00,010,0110,1000} D．{b,c,aa,ac,aba,abb,abc}
一棵二叉树，前序遍历序列为：ABCDEFG，它的中序遍历序列可能是（B）
- A．CABDEFG B：ABCDEFG C．DACEFBG D．ADCFEG
设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，

当用以列为主存放时，元素 A[5，8]的存储首地址为：(B)：
- A. BA+141 B. BA+180 C. BA+222 D. BA+225
下面的说法中，只有（A）是正确的
- A.串是一种特殊的线性表 B. 串的长度必须大于零
- C.串中元素只能是字母 D. 空串就是空白串
设有一个栈，元素的进栈次序为A, B, C, D, E,下列是不可能的出栈序列（C）
- A．A, B, C, D, E B．B, C, D, E, A
- C．E, A, B, C, D D．E, D, C, B, A
在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为（C）
- A．top不变 B．top=0 C．top– D．top++
在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行（B）
- A．s->next=p->next; p->next=s
- B．q->next=s; s->next=p
- C．p->next=s->next; s->next=p
- D．p->next=s; s->next=q
设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（ C）。

? (A)O(n) (B) O(nlog2n) ? O(1) (D)O(n2)

设，一棵二叉树的深度为k，则该二叉树中最多有（D）个结点。

(A)2k-1 (B) 2k ? 2k-1 (D)2k-1

设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（D）。

(A)n (B) e ? 2n (D) 2e

在二叉排序树中插入一个结点的时间复杂度为（B）。

(A)O(1) (B) O(n) ? O(log2n) (D) O(n2)

设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（C ）条有向边。

(A)n (B) n-1 ?m (D)m-1

判断

无向连通图，所有顶点的度之和为偶数。 [√]
无向连通图边数一定大于顶点个数减1。 [×]
无向连通图至少有一个顶点的度为1。 [×]
用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。 [×]
用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。 [√]
在一个有向图中，所有顶点的入度与出度之和等于所有边之和的2倍。 [√]
算法分析的两个主要方面是时间复杂度和空间复杂度的分析。 [√]
通过对堆栈S操作：Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为：123。 [×]
在用数组表示的循环队列中，front值一定小于等于rear值。 [×]
若一个栈的输入序列为{1, 2, 3, 4, 5}，则不可能得到{3, 4, 1, 2, 5}这样的出栈序列。 [√]
已知一棵二叉树的先序遍历结果是ABC,　则CAB不可能是中序遍历结果。 [√]
一棵有124个结点的完全二叉树，其叶结点个数是确定的。 [√]
若用链表来表示一个线性表，则表中元素的地址一定是连续的。 [×]
任何二叉搜索树中同一层的结点从左到右是有序的（从小到大）。 [√]
某二叉树的前序和中序遍历序列正好一样，则该二叉树中的任何结点一定都无左孩子。 [√]

简答

存储结构

有一字符序列abcde依次按照某一线性结构存储，请回答以下问题：

如果该线性结构是队列，写出其出队顺序；
- ABCDE
- 队列：先进先出
如果该线性结构是栈，那么，输出序列可能是dceab么？为什么？
- 不可能
- 因为：
  - d是第一个出栈字符，说明ab已分别压入栈内；并且压入栈的顺序为abcde；
  - 由以上得出：ab出栈的顺序只能是b、a，而不是ab，所以出栈序列dceab是不肯能的
如果该线性结构是栈，且输出序列是adcbe，写出其操作过程

push(x)：表示把x压入栈内；

pop(x)：表示把x弹出栈

栈：先进后出，后进先出。

push(a),pop(a),push(b),push(c),push(d),pop(d),pop(c),pop(b),push(e).pop(e)

森林

下图所示的森林：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4MewFbXh-1641106984599)(%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%20%E5%A4%8D%E4%B9%A0%E9%A2%98.assets/clip_image001.jpg)]

求树（a）的先根序列和后根序列；
- ABCDEF
- BDEFCA
求森林先序序列和中序序列
- ABCDEFGHIJK
- BDEFCAIJKHG
将此森林转换为相应的二叉树；

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-yBKbf253-1641106984599)(%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%20%E5%A4%8D%E4%B9%A0%E9%A2%98.assets/clip_image003.jpg)]

阿克曼（Ackerman）函数

在数学上有一个著名的“阿克曼（Ackerman）函数”，该函数定义如下：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QL8psIUw-1641106984600)(%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%20%E5%A4%8D%E4%B9%A0%E9%A2%98.assets/image-20220102140023331.png)]

写出Ack(m,n)的递归算法；

java

public class Ackerman {

    public static void main(String[] args) {
        System.out.println(" " + ack(3,4) + "");
    }

    public static int ack(int m,int n){
      if (m < 0 || n < 0){
        return -1;
      }else if ( m == 0){
            return n+1;
        }else if (n == 0 && m != 0){
            return ack(m-1,1);
        }else if(n != 0 && m != 0){
            return ack(m-1,ack(m,n-1));
        }
    }
}

int Ack(int m, int n)

{

if(m==0)

  return n+1;

else if (m!=0 && n==0)

 return Ack(m-1, 1);

else

  return Ack(m-1,Ack(m,m-1));

}

//Ackerman递归算法
int akm1(int m,int n){
	int q;
	if(m==0)
		return n+1;
	else if(n==0)
		return akm1(m-1,1);
	else{
		q=akm1(m,n-1);
		return akm1(m-1,q);
	}
}

写出计算Ack(m,n)的非递归算法。

//Ackerman非递归算法
int akm2(int m,int n){
	struct{
		int vm,vn;  //分别保存m和n值
		int vf;     //保存akm(m,n)值
		int tag;  //标识是否求出akm(m,n)值，1:表示未求出，0:表示已求出
	}St[MaxSize];

	int top=-1;  //栈指针
	top++;     //初值进栈
	St[top].vm=m; St[top].vn=n; St[top].tag=1;
	while(top > -1){   //栈不空时循环
		if (St[top].tag==1)   //未计算出栈顶元素的vf值
		{ 
			if (St[top].vm==0)      //(1)式
			{
				St[top].vf=St[top].vn+1;
				St[top].tag=0;
			} 
			else if (St[top].vn==0) //(2)式
			{
				top++;
				St[top].vm=St[top-1].vm-1;
				St[top].vn=1;
				St[top].tag=1;
			}
			else                    //(3)式
			{
				top++;
				St[top].vm=St[top-1].vm;
				St[top].vn=St[top-1].vn-1;
				St[top].tag=1;
			}
		}
		else if (St[top].tag==0)  //已计算出vf值
		{
			if (top>0 && St[top-1].vn==0) //(2)式
			{
				St[top-1].vf=St[top].vf;
				St[top-1].tag=0;
				top--;
			}
			else if (top > 0) //(3)式
			{
				St[top-1].vm=St[top-1].vm-1;
				St[top-1].vn=St[top].vf;
				St[top-1].tag=1;
				top--;
			}
		}
		if(top==0 && St[top].tag==0) //栈中只有一个已求出vf的元素时退出循环
			break;
	}
	return St[top].vf;

}

排序

4.有一组数据{64，5，7，98，6，24}

? （1）请列出直接选择排序（升序）的过程；

? （2）请列出冒泡排序（升序）的过程

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ZV9AntAU-1641106984600)(%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%20%E5%A4%8D%E4%B9%A0%E9%A2%98.assets/clip_image006.jpg)]