数据结构数组和广义表自测题(附答案)
更新时间:2023-10-31 11:29:01 阅读量: 综合文库 文档下载
第4~5章 串和数组
一、填空题
1. 不包含任何字符(长度为0)的串 称为空串; 由一个或多个空格(仅由空格符)组成的串 称为空白串。
2. 设S=“A;/document/Mary.doc”,则strlen(s)= 20 , “/”的字符定位的位置为 3 。
4. 子串的定位运算称为串的模式匹配; 被匹配的主串 称为目标串, 子串 称为模式。
5. 设目标T=”abccdcdccbaa”,模式P=“cdcc”,则第 6 次匹配成功。
6. 若n为主串长,m为子串长,则串的古典(朴素)匹配算法最坏的情况下需要比较字符的总次数为 (n-m+1)*m 。
7. 假设有二维数组A68,每个元素用相邻的6个字节存储,存储器按字节编址。已知A的起始存储位置(基
×
地址)为1000,则数组A的体积(存储量)为 288 B ;末尾元素A57的第一个字节地址为 1282 ;若按行存储时,元素A14的第一个字节地址为 (8+4)×6+1000=1072 ;若按列存储时,元素A47的第一个字节地址为 (6×7+4)×6+1000)=1276 。 (注:数组是从0行0列还是从1行1列计算起呢?由末单元为A57可知,是从0行0列开始!)
8.设数组a[1?60, 1?70]的基地址为2048,每个元素占2个存储单元,若以列序为主序顺序存储,则元素a[32,58]的存储地址为 8950 。 答:不考虑0行0列,利用列优先公式: LOC(aij)=LOC(ac1,
c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L 得:LOC(a32,58)=2048+[(58-1)*(60-1+1)+32-1]]*2=8950
9. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素,它包含有三个数据项,分别表示该元素 的 行下标 、 列下标 和 元素值 。
10.求下列广义表操作的结果:
(1) GetHead【((a,b),(c,d))】=== (a, b) ; //头元素不必加括号
(2) GetHead【GetTail【((a,b),(c,d))】】=== (c,d) ;
(3) GetHead【GetTail【GetHead【((a,b),(c,d))】】】=== b ;
1
(4) GetTail【GetHead【GetTail【((a,b),(c,d))】】】=== (d) ; 二、单选题
( B )1.串是一种特殊的线性表,其特殊性体现在:
A.可以顺序存储 B.数据元素是一个字符
C.可以链式存储 D.数据元素可以是多个字符
( B )2.设有两个串p和q,求q在p中首次出现的位置的运算称作:
A.连接 B.模式匹配 C.求子串 D.求串长
( D )3.设串s1=’ABCDEFG’,s2=’PQRST’,函数con(x,y)返回x和y串的连接串,subs(s, i, j)返回串s的从序号i开始的j个字符组成的子串,len(s)返回串s的长度,则con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))的结果串是: A.BCDEF B.BCDEFG C.BCPQRST D.BCDEFEF
解:con(x,y)返回x和y串的连接串,即 con(x,y)=‘ABCDEFGPQRST’; subs(s, i, j)返回串s的从序号i开始的j个字符组成的子串,则 subs(s1, 2, len(s2))=subs(s1, 2, 5)=’ BCDEF’; subs(s1, len(s2), 2)=subs(s1, 5, 2)=’ EF’; 所以con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))=con(’ BCDEF’, ’ EF’)之连接,即BCDEFEF
( A )4.假设有60行70列的二维数组a[1?60, 1?70]以列序为主序顺序存储,其基地址为10000,每个元素占2个存储单元,那么第32行第58列的元素a[32,58]的存储地址为 。(无第0行第0列元素)
A.16902 B.16904 C.14454 D.答案A, B, C均不对
答:此题与填空题第8小题相似。(57列×60行+31行)×2字节+10000=16902
( B )5. 设矩阵A是一个对称矩阵,为了节省存储,将其下三角部分(如下图所示)按行序存放在一维数组B[ 1, n(n-1)/2 ]中,对下三角部分中任一元素ai,j(i≤j), 在一维数组B中下标k的值是: A.i(i-1)/2+j-1 B.i(i-1)/2+j C.i(i+1)/2+j-1 D.i(i+1)/2+j
2
?a1,1?a2,1?A??????an,1a2,2an,2??????an,n??6. 有一个二维数组A,行下标的范围是0到8,列下标的范围是1到5,每个数组元素用相邻的4个字节
存储。存储器按字节编址。假设存储数组元素A[0,1]的第一个字节的地址是0。存储数组A的最后一个元素的第一个字节的地址是 A 。若按行存储,则A[3,5]和A[5,3]的第一个字节的地址分别是 B 和 C 。若按列存储,则A[7,1]和A[2,4]的第一个字节的地址分别是 D 和 E 。供选择的答案:
A~E:①28 ② 44 ③ 76 ④ 92 ⑤ 108 ⑥ 116 ⑦ 132 ⑧ 176 ⑨ 184 ⑩ 188 答案:A= B= C= D= E=
答案:ABCDE=8, 3, 5, 1, 6
7. 有一个二维数组A,行下标的范围是1到6,列下标的范围是0到7,每个数组元素用相邻的6个字节存储,存储器按字节编址。那么,这个数组的体积是 A 个字节。假设存储数组元素A[1,0]的第一个字节的地址是0,则存储数组A的最后一个元素的第一个字节的地址是 B 。若按行存储,则A[2,4]的第一个字节的地址是 C 。若按列存储,则A[5,7]的第一个字节的地址是 D 。供选择的答案 A~D:①12 ②66 ③72 ④96 ⑤114 ⑥120 ⑦156 ⑧234 ⑨276 ⑩282 (11)283 (12)288 答案:A= B= C= D= E=
答案:ABCD=12, 10, 3, 9
三、简答题
1. 已知二维数组Am,m采用按行优先顺序存放,每个元素占K个存储单元,并且第一个元素的存储地址为Loc(a11),请写出求Loc(aij)的计算公式。如果采用列优先顺序存放呢?
答:公式教材已给出,此处虽是方阵,但行列公式仍不相同; 按行存储的元素地址公式是: Loc(aij)= Loc(a11) +[ (i-1)*m+(j-1按列存储的元素地址公式是: Loc(aij)= Loc(a11) +[ (j-1)*m+(i-1) ] * K 2. 递归算法比非递归算法花费更多的时间,对吗?为什么?
答:不一定。时间复杂度与样本个数n有关,是指最深层的执行操作, 在最深层的语句执行上是没有区别的,循环的次数也没有太大差异。仅仅是确定循环是否继续的方式不同,递归用栈隐含循环次数,非递归用循环变量来显示循环次数而已。
四、 计算题
1. 设s=’I AM A STUDENT’, t=’GOOD’, q=’WORKER’,
求Replace(s,’STUDENT’,q) 和Concat(SubString(s,6,2), Concat(t,SubString(s,7,8)))。
3
2. 用三元组表表示下列稀疏矩阵:
?00000000?00000000??03000800?00000000(1)??00060000??00000000?00000005??20000000???00000?2?????000090????000000?? (2)?? ?005000????000000?????000030??????3. 下列各三元组表分别表示一个稀疏矩阵,试写出它们的稀疏矩阵。
?6?1??2?(1)3??4??5?6?46??455??22???111??112??249??13 (2)?? ?328??44??356??36???437??116??五、算法设计题
1. 编写一个实现串的置换操作Replace(&S, T, V)的算法。
2. 试设计一个算法,将数组An 中的元素A[0]至A[n-1]循环右移k位,并要求只用一个元素大小的附加
存储,元素移动或交换次数为O(n)
4
正在阅读:
数据结构数组和广义表自测题(附答案)10-31
餐饮管理(第三版)知识总结06-27
小学生秋季运动会演讲稿04-30
设计概论试题12-07
计算机三级嵌入式系统操作题(到详细解答)04-06
详解香港居民身份与永居(护照)03-17
焊接职业危害与防护措施11-07
运算器电路(P1口)04-28
高中语文语法教学要点剖析-最新教育资料06-29
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 自测题
- 数据结构
- 数组
- 广义
- 答案
- 机电传动控制课后习题答案1
- 《老王》中学语文教学技能考试复习大纲
- 东北财经《投资项目评估》全部随堂练习及答案
- 施工技术单项多项选择题答案
- 2016年杭州中考锦绣科学一模试卷
- 财政学学习大纲
- Nanodrop分光光度计20002000C中文操作使用说明 - 图文
- 绿植花卉购销合同-模版
- 《现代城市生态与环境学》2016期末考试答案
- 青银高速夏津服务区场地施工组织设计
- 口才艺术与社交礼仪尔雅通识课考试答案
- 完善军民融合的工作机制
- 模拟联合国大会中英对照发言稿,非常实用
- PCM通信系统设计
- 《风险管理》教案
- 20世纪日本中国史研究的步履
- 西大湖湿地围栏工程实施方案
- Lotus Notes Domino面试试题及答案
- 《商法》作业练习题
- 转染细胞的稳定筛选方法和实验步骤