拨开荷叶行,寻梦已然成。仙女莲花里,翩翩白鹭情。 网站地图
IMG-LOGO
主页 文章列表 资料结构复习题

资料结构复习题

by 白鹭 - 2022-01-23 2264 0 0

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

文章目录

  • 资料结构 复习题
    • 填空
    • 选择
    • 判断
    • 简答
      • 存盘结构
      • 森林
      • 阿克曼(Ackerman)函式
      • 排序
        • 直接选择排序:
        • 冒泡排序:

资料结构 复习题

填空

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

    • 线性结构

    • 非线性结构

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

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

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

    • 集合

    • 树形结构

    • 线性结构

    • 图结构

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

    • 链式存盘结构是通过**结点指标**表示元素之间的关系的,
  6. 回圈单链表的最大优点是:

    • 从任一结点出发都可访问到链表中每一个元素,
  7. 堆栈是一种操作受限的线性表,

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

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

  1. 堆栈是==操作受限==的线性表,

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

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

  3. 回圈队列的引入

    • 目的:克服假溢位时大量的移动资料元素
  4. 对于一个具有n个结点的二叉树

    • 当它为一棵==完全==二叉树时具有最小高度,
  5. 哈夫曼树

    • 是==带权路径长度最小的二叉树==,又称**最优二叉树**,
  6. 完全图

    • 是**任意两个顶点之间存在边**;
  • 连通图
    • 任意两个顶点之间都有路径
  1. 一般线性表顺序查找

    • 查找成功的平均查找长度为==(n+1)/2==,

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

15.采用分块查找时,

  • 阵列的组织方式:资料分成若干块,
  • 每块内资料不必有序,但**块间必须有序,每块内最大的资料**组成索引块,
  1. 线性表的顺序存盘

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

    线性表的链接存盘中,

    • 元素之间的逻辑关系是通过:**指标**决定的,
  2. 空格串

    • 长度为: 空格数
    • 空串的长度为 0
  3. 己知三对角矩阵A[1…9,1…9]的每个元素占2个单元,现将其三条对角线上的元素逐行存盘在起始地址为1000的连续的存储器单元中,则元素A[7,8]的地址为:

    • 1038
  4. 广义表L = ((),())

    • head(L)()
    • tail(L)( ( ) )
    • L的长度:2
    • 深度:2
  5. 一棵深度为k的二叉树

    • 最多有2k-1个结点,
  6. ,的存盘结构常采用____两种

    • 邻接矩阵
    • 邻接表

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)

  1. 设,一棵二叉树的深度为k,则该二叉树中最多有(D)个结点,

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

  1. 设某无向图中有n个顶点e条边,则该无向图中所有顶点的入度之和为(D),

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

  1. 二叉排序树中插入一个结点的时间复杂度为(B),

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

  1. 设某有向图的邻接表中有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)

森林

下图所示的森林:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(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)]

  1. 求树(a)的先根序列和后根序列;

    • ABCDEF
    • BDEFCA
  2. 求森林先序序列和中序序列

    • ABCDEFGHIJK
    • BDEFCAIJKHG
  3. 将此森林转换为相应的二叉树;

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(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)]

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

直接选择排序:

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

参考

初始值 {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

标签:

0 评论

发表评论

您的电子邮件地址不会被公开。 必填的字段已做标记 *