下载地址：https://wwm.lanzouw.com/ixFNoy9hdyh
密码:5vyi

资料结构 复习题

填空

1. 在资料结构中,?从逻辑上能够把资料结构分为

   • 线性结构

   • 非线性结构

2. 资料结构在计算机存储器中的表示是指

   • 资料的存盘结构

3. 链式存盘的特点是利用**指标** 来表示资料元之间的逻辑关系，

4. 对于给定的n个元素，可以构造出的逻辑结构有

   • 集合

   • 树形结构

   • 线性结构

   • 图结构

5. 顺序存盘结构是通过==结点物理上相邻==表示元素之间的关系的；

   • 链式存盘结构是通过**结点指标**表示元素之间的关系的，

6. 回圈单链表的最大优点是：

   • 从任一结点出发都可访问到链表中每一个元素，

7. 堆栈是一种操作受限的线性表，

• 它只能在线性表的==一端==进行插入和洗掉操作，

• 对堆栈的访问是按照==后进先出==的原则进行的，

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

   其运算遵循的原则：后进先出，

9. 堆栈可以在线性表的==堆栈顶==进行操作和洗掉，

10. 回圈队列的引入，

    • 目的：克服假溢位时大量的移动资料元素，

11. 对于一个具有n个结点的二叉树，

    • 当它为一棵==完全==二叉树时具有最小高度，

12. 哈夫曼树

    • 是==带权路径长度最小的二叉树==，又称**最优二叉树**，

13. 完全图

    • 是**任意两个顶点之间存在边**；

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

14. 一般线性表顺序查找，

    • 查找成功的平均查找长度为==（n+1）/2==，

    • 查找失败的平均查找长度为n+1，

15.采用分块查找时，

• 阵列的组织方式：资料分成若干块，
• 每块内资料不必有序，但**块间必须有序，每块内最大的资料**组成索引块，

16. 在线性表的顺序存盘中

    • 元素之间的逻辑关系是通过： 物理位置相邻 决定的

    在线性表的链接存盘中，

    • 元素之间的逻辑关系是通过：**指标**决定的，

17. 空格串

    • 长度为： 空格数，
    • 空串的长度为 0 ，

18. 己知三对角矩阵A[1…9,1…9]的每个元素占2个单元，现将其三条对角线上的元素逐行存盘在起始地址为1000的连续的存储器单元中，则元素A[7,8]的地址为：

    • 1038

19. 设广义表L = ((),())

    • head(L)：()；
    • tail(L)：( ( ) )；
    • L的长度：2；
    • 深度：2，

20. 一棵深度为k的二叉树，

    • 最多有2k-1个结点，

21. 图，的存盘结构常采用____两种

    • 邻接矩阵
    • 邻接表，

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

• 洗掉其后继节点（要求由指标q指向）的陈述句是 ：

  • q=p->next，

  • p->next=q->next，

  • free(q)

选择

1. n个顶点，e条边的有向图的邻接矩阵中非零元素有 （C）个，

   • A.n B.2e C.e D.n+e

2. 如果在资料结构中每个资料元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（C）

   • A. 堆栈 B. 队列 C. 树 D. 图

3. 资料结构研究的内容是（D），

   • A．资料的逻辑结构 B．资料的存盘结构

   • C．建立在相应逻辑结构和存盘结构上的算法 D．包括以上三个方面

4. 若下面几个符号串编码集合中，不是前缀编码的是（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}

5. 一棵二叉树，前序遍历序列为：ABCDEFG，它的中序遍历序列可能是（B）

   • A．CABDEFG B：ABCDEFG C．DACEFBG D．ADCFEG

6. 设有阵列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

7. 下面的说法中，只有（A）是正确的

   • A.串是一种特殊的线性表 B. 串的长度必须大于零

   • C.串中元素只能是字母 D. 空串就是空白串

8. 设有一个堆栈，元素的进堆栈次序为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

9. 在一个具有n个单元的顺序堆栈中，假定以地址低端（即0单元）作为堆栈底，以top作为堆栈顶指标，当做出堆栈处理时，top变化为（C）

   • A．top不变 B．top=0 C．top– D．top++

10. 在一个单链表中，已知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

11. 设一维阵列中有n个阵列元素，则读取第i个阵列元素的平均时间复杂度为（ C），

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

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

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

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

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

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

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

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

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

判断

1. 无向连通图，所有顶点的度之和为偶数， [√]

2. 无向连通图边数一定大于顶点个数减1， [×]

3. 无向连通图至少有一个顶点的度为1， [×]

4. 用邻接表法存盘图，占用的存盘空间数只与图中结点个数有关，而与边数无关， [×]

5. 用邻接矩阵法存盘图，占用的存盘空间数只与图中结点个数有关，而与边数无关， [√]

6. 在一个有向图中，所有顶点的入度与出度之和等于所有边之和的2倍， [√]

7. 算法分析的两个主要方面是时间复杂度和空间复杂度的分析， [√]

8. 通过对堆堆栈S操作：Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)，输出的序列为：123， [×]

9. 在用阵列表示的回圈队列中，front值一定小于等于rear值， [×]

10. 若一个堆栈的输入序列为{1, 2, 3, 4, 5}，则不可能得到{3, 4, 1, 2, 5}这样的出堆栈序列， [√]

11. 已知一棵二叉树的先序遍历结果是ABC,　则CAB不可能是中序遍历结果， [√]

12. 一棵有124个结点的完全二叉树，其叶结点个数是确定的， [√]

13. 若用链表来表示一个线性表，则表中元素的地址一定是连续的， [×]

14. 任何二叉搜索树中同一层的结点从左到右是有序的（从小到大）， [√]

15. 某二叉树的前序和中序遍历序列正好一样，则该二叉树中的任何结点一定都无左孩子， [√]

简答

存盘结构

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

1. 如果该线性结构是队列，写出其出队顺序；

   • ABCDE

   • 队列：先进先出

2. 如果该线性结构是堆栈，那么，输出序列可能是dceab幺？为什么？

   • 不可能
   • 因为：
     • d是第一个出堆栈字符，说明ab已分别压入堆栈内；并且压入堆栈的顺序为abcde；
     • 由以上得出：ab出堆栈的顺序只能是b、a，而不是ab，所以出堆栈序列dceab是不肯能的

3. 如果该线性结构是堆栈，且输出序列是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)

森林

下图所示的森林：

1. 求树（a）的先根序列和后根序列；

   • ABCDEF
   • BDEFCA

2. 求森林先序序列和中序序列

   • ABCDEFGHIJK
   • BDEFCAIJKHG

3. 将此森林转换为相应的二叉树；

阿克曼（Ackerman）函式

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

1. 写出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));
        }
    }
}

c

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);
	}
}

2. 写出计算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）请列出冒泡排序（升序）的程序

直接选择排序：

找最小的数，放到第一位~

参考

初始值 {64，5，7，98，6，24}

5，【64，7，98，6，24】

5，6，【7，98，64，24】

5，6，7，【98，64，24】

5，6，7，24【64，98】

5，6，7，24，64，【98】

冒泡排序：

两个相邻数直接比较，

参考

初识值：{64，5，7，98，6，24}

第一趟排序：5

【5，64】，7，98，6，24

5，【7，64】，98，6，24

5，7，[64，98]，6，24

5，7，64，【6，98】，24

5，7，64，6，【24，98】

第二趟排序：4

【 5，7】，64，6，24，98

5，【7，64】，6，24，98

5，7，【6，64】，24，98

5，7，6，【24，64】，98

第三趟排序：3

【5，7】，6，24，64，98

5，【6，7】，24，64，98

5，6，【7，24】，64，98