数据结构 数组和广义表以及树的基本概念

2-1

设有一个10阶的对称矩阵A,采用压缩存储方式,以行序为主存储,a11为第一元素,其存储地址为1,每个元素占一个地址空间,则a85的地址为 (2分)

  1. 13
  2. 33
  3. 18
  4. 40

 / 

a85 - a11   =  a  ( 7 row , 4 col)

7 row : 1 + 2 +3+4+5+6+7 = (1+7)*7/2 = 28 

4 col  :  4 

地址 = 首地址 + (28+4)*sizeof(a) = 1 + 32 = 33

已知aij 求解 auv

&auv = &aij + [(1+2+3+.....(u-i))+(v-j)]*sizeof(a);

这是对于压缩矩阵的运算来说

普通的计算是这样的

m 代表行数目, n 代表列数

已知aij的地址,求解auv

a(u-i)(v-j)

&auv = &aij + [(u-i)*n+(v-j)]*sizeof(a);

/

2-2

设有数组A[i,j],数组的每个元素长度为3字节,i的值为1 到8 ,j的值为1 到10,数组从内存首地址BA开始顺序存放,当用以列为主存放时,元素A[5,8]的存储首地址为()。 (2分)

  1. BA+141
  2. BA+180
  3. BA+222
  4. BA+225

2-3

将一个A[1..100,1..100]的三对角矩阵,按行优先存入一维数组B[1‥298]中,A中元素A6665(即该元素下标i=66,j=65),在B数组中的位置K为()。 (2分)

  1. 198
  2. 195
  3. 197
  4. 199

/

形如

的n×n矩阵A称为三对角矩阵,其中第(i,j)个元素在j>i+1和j<i-1时为零

/

2-4

若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1..(n(n+1))/2]中,则在B中确定aij(i<j)的位置k的关系为()。 (2分)

  1. i*(i-1)/2+j
  2. j*(j-1)/2+i
  3. i*(i+1)/2+j
  4. j*(j+1)/2+i

/

n阶对称矩阵中的元素满足下述条件:aij=aji,(1<=i,j<=n)。对称矩阵中的每一对数据元素可以共用一个存储空间,因此可以将n2个元素压缩存储到n(n+1)/2个元的空间中,即可以一维数组保存。 假设用一维数组B[n(n+1)/2]作为对称矩阵A的存储结构,则B[k]和矩阵元素aij的下标i、j的对应关系为: 当i>-j时,k=i(i-1)/2+i; 当i<j时,k=j(j-1)/2+i;

/

2-5

已知广义表L=((x,y,z),a,(u,t,w)),从L表中取出原子项t的运算是()。 (2分)

  1. head(tail(tail(L)))
  2. tail(head(head(tail(L))))
  3. head(tail(head(tail(L))))
  4. head(tail(head(tail(tail(L)))))

广义表的基本概念和运算

 题目理解:

1:利用广义表的head和tail操作写出函数表达式,把以下各题中的单元素banana从广义表中分离出来:


         (1) L1(apple, pear, banana, orange)


         (2) L2((apple, pear), (banana, orange))


         (3) L3(((apple), (pear), (bananA), (orange)))


         (4) L4((((apple))), ((pear)), (bananA), orange)


         (5) L5((((apple), pear), bananA), orange)


         (6) L6(apple, (pear, (bananA), orange))


  【答案】


         (1) Head (Tail (Tail (L1) ) )


         (2) Head (Head (Tail (L2) ) )


         (3) Head (Head (Tail (Tail (Head (L3) ) ) ) )


         (4) Head (Head (Tail (Tail (L4) ) ) )


         (5) Head (Tail (Head(L5) ) )


         (6) Head (Head (Tail (Head (Tail (L6) ) ) ) )       

code

2-6

广义表A=(a,b,(c,d),(e,(f,g))),则式子Head(Tail(Head(Tail(Tail(A)))))的值为()。 (2分)

(g)

(d)

c

d

2-7

设广义表L=((a,b,c)),则L的长度和深度分别为( ) (2分)

1和1

1和3

1和2

2和3

 广义表长度是第一层括号里逗号的数目 + 1

 深度是每个元素的括号匹配数+1

 ()一层 (())两层 ((()))三层 ( ( ) ( ) ( (  ) )  )三层,取最深的一层作为深度

2-8

树最适合于用来表示 (1分)

有序数据元素

无序数据元素

元素之间无联系的数据

元素之间具有分支层次关系的数据

2-9

设树T的度为4,其中度为1、2、3、4的结点个数分别为4、2、1、1。则T中有多少个叶子结点? (3分)

4

6

8

10

n0:度为0的结点数,n1:度为1的结点 n2:度为2的结点数。 N是总结点。

在二叉树中:

n0=n2+1;

N=n0+n1+n2

树中结点数 = 总分叉数 +1

分叉数 = 度   .*   对应个数 = 1*4+2*2+3*1+4*1=15

节点数 = 15+1 = 16

叶节点度数为 0

叶节点数目 x = 16 - (4+2+1+1) = 8

2-12

已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为()。 (3分)

CBEFDA

FEDCBA

CBEDFA

不定

二叉树遍历

2-13

已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是( )。 (3分)

acbed

decab

deabc

cedba

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

1002. 三角形 (

题目描述 输入三角形三边长a,b,c(保证能构成三角形),输出三角形面积。 输入 一行三个用一个空格隔开的实数a,b,c,表示三角形的三条边长。 输出 输出三角...

2816
来自专栏IT可乐

深入理解计算机系统(2.6)------整数的运算

  前面两篇博客我们详细讲解了计算机中整数的表示,包括有符号和无符号(补码编码)的详细介绍。那么这篇博客我们将对它们的运算有个详细的了解。   在讲解之前首先看...

1966
来自专栏Jack-Cui

141. Linked List Cycle(Linked List-Easy)

Description:Given a linked list, determine if it has a cycle in it. Follow up: ...

1790
来自专栏desperate633

LintCode 链表划分题目代码

样例 给定链表 1->4->3->2->5->2->null,并且 x=3 返回** 1->2->2->4->3->5->null**

502
来自专栏desperate633

LintCode 最小调整代价题目分析代码

给一个整数数组,调整每个数的大小,使得相邻的两个数的差小于一个给定的整数target,调整每个数的代价为调整前后的差的绝对值,求调整代价之和最小是多少。

651
来自专栏程序员互动联盟

【编程基础】C语言产生随机数需要了解的几个函数

C语言产生随机数是一个常见的编程功能任务,当然这个也不难,调用两三个函数就出来了,但是你知道这些函数具体是起到怎样的作用,并且是它们是如何产生随机数的吗? 几...

2677
来自专栏算法与数据结构

动态规划--Kin

2794
来自专栏漫漫深度学习路

tensorflow学习笔记(三十):tf.gradients 与 tf.stop_gradient() 与 高阶导数

gradient tensorflow中有一个计算梯度的函数tf.gradients(ys, xs),要注意的是,xs中的x必须要与ys相关,不相关的话,会报错...

5959
来自专栏AIUAI

Pytorch - Cross Entropy Loss

7036
来自专栏null的专栏

简单易学的机器学习算法——Gibbs采样

一、Gibbs采样概述 前面介绍的Metropolis-Hastings采样为从指定分布中进行采样提供了一个统一的框架,但是采样的效率依赖于指定的分布的选择,若...

3509

扫码关注云+社区