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

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 条评论
登录 后参与评论

相关文章

来自专栏小白客

每天学习一点儿算法--二分查找

算法是什么? 算法就是完成一组特定任务的方法。 比如将大象放进冰箱需要三步: 打开冰箱 将大象放进冰箱 关闭冰箱 这就是一种算法。 如果用计算机语言来叙述...

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

P2264 情书

题目背景 一封好的情书需要撰写人全身心的投入。lin_toto同学看上了可爱的卡速米想对她表白,但却不知道自己写的情书是否能感动她,现在他带着情书请你来帮助他。...

3179
来自专栏从零开始学自动化测试

python笔记1-用python解决小学生数学题

前几天有人在群里给小编出了个数学题: 假设你有无限数量的邮票,面值分别为6角,7角,8角,请问你最大的不可支付邮资是多少元? 小编掰着手指头和脚趾头算了下,答案...

2819
来自专栏编程

Python之路-day6

所谓高阶函数,简单点说就是将一个函数作为另一个函数的传入参数,这样我们就称这个组合函数为高阶函数。 举个例子: map()函数能接收两个参数,一个为函数,一个为...

1738
来自专栏desperate633

[编程题] 彩色瓷砖分析代码

牛牛喜欢彩色的东西,尤其是彩色的瓷砖。牛牛的房间内铺有L块正方形瓷砖。每块砖的颜色有四种可能:红、绿、蓝、黄。给定一个字符串S, 如果S的第i个字符是'R', ...

833
来自专栏磐创AI技术团队的专栏

快速学习 Python 的全套 14 张思维导图(附高清版下载)

基础知识图一包括了基本规则、Python语言特点、计算机语言、如何运行Python、变量赋值五个方面,辅助你快速掌握Python编程的基底知识。

773
来自专栏代码世界

题型分析

1、 简单让A、B的值交换 a,b = 1,2 print(a,b) a = 1 b = 2 a,b = b,a print(a,b) a,b=[1,2],[5...

32910
来自专栏禹都一只猫博客

Python科学计算:在Numpy的边缘试探(入门学习)

1928
来自专栏Crossin的编程教室

【每周一坑】神奇的九宫格

五一小长假大家应该玩的挺开心吧,还沉浸在假日的愉悦中么?请大家收收心,准备准备月底的端午节。 看看本周的题目吧,本周的题目由读者 @疯琴 提供,我们做了小小的改...

2677
来自专栏云霄雨霁

离散数学中求合取范式&析取范式

890

扫码关注云+社区