一种新颖稳定的RFID反碰撞算法模型(计算机)
１引言
未来物联网（ｉｎｔｅｒｎｅｔｏｆｔｈｉｎｇｓ）所采用的无线射频识别（ＲＦＩＤ）技术中：阅读器信号作用范围内可能存在多个标签，如果同一时刻有两个或以上的标签向阅读器返回信息，将产生冲突，称为标签冲突。解决标签冲突的反碰撞算法分为两大类：一种是随机方式，阅读器要求区域内标签采用随机应答的方式来处理。例如：ＡＬＯＨＡ算法［８－１２］、时隙ＡＬＯＨＡ算法［１］，信道的最佳利用率分别为１８．４％、３６．８％，但随着标签数量的扩大，性能将急剧恶化［３］。另一种是确定性方式，阅读器将冲突区域内标签不断划分为更小的子集来初步解决。譬如：树形搜索算法［４－７］，其算法效率在理想情况下为４７．８％～５０％左右，但其前提条件是要求区域内标签在短时间内数量处于不变的状况下进行。如果阅读器在识别标签的过程中，又有新的标签动态进入将扰乱其算法执行过程，性能得不到保证。
本算法的思想来源于计算机网络ＩＥＥＥ８０２．３标准中的二进制指数后退算法［２］。该二进制指数后退算法已广泛用于ＣＳ－ＭＡ／ＣＤ局域网，但若直接用于解决ＲＦＩＤ标签冲突问题将形成后到反而先处理的局面，有失公平性；同时，在标签连绵不断涌入阅读器问询区的情况下，最先到达的标签被识别的概率极低以致于不能被识别。而采用双向指数索引的方式一方面可以动态有效地识别区域内标签，同时另一方面可以保持识别的公平性。
２算法原理
２．１算法约定
为更好地描述以及定量分析该算法，提出以下几点约定。２．１．１时隙
从阅读器发送问询命令开始，到标签应答返回信息的情况下，所消耗的这一段时间间隔称为一个时隙。由定义可知，一个时隙包括两部分：问询命令发送阶段和标签应答阶段。２．１．２阅读器问询命令
阅读器发送命令到区域内标签，区域内处于活动状态的标
一种新颖稳定的RFID反碰撞算法模型
余松森１，２，袁斌１，詹宜巨２
ＹＵＳｏｎｇ－ｓｅｎ１，２，ＹＵＡＮＢｉｎ１，ＺＨＡＮＹｉ－ｊｕ２
１．南昌大学计算机系，南昌３３００２９
２．中山大学工学院，广州５１０２７５
１．ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒ，ＮａｎｃｈａｎｇＵｎｉｖｅｒｓｉｔｙ，Ｎａｎｃｈａｎｇ３３００２９，Ｃｈｉｎａ
２．ＳｃｈｏｏｌｏｆＴｅｃｈｎｏｌｏｇｙ，ＳＵＮＹＡＴ－ＳＥＮＵｎｉｖｅｒｓｉｔｙ，Ｇｕａｎｇｚｈｏｕ５１０２７５，Ｃｈｉｎａ
Ｅ－ｍａｉｌ：ｙｓｓ８１０９＠１６３．ｃｏｍ
ＹＵＳｏｎｇ－ｓｅｎ，ＹＵＡＮＢｉｎ，ＺＨＡＮＹｉ－ｊｕ．ＮｅｗｌｙｓｔｅａｄｙＲＦＩＤａｎｔｉ－ｃｏｌｌｉｓｉｏｎａｌｇｏｒｉｔｈｍ．ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ，２００７，４３（１）：９０－９３．
Ａｂｓｔｒａｃｔ：ＴｈｅｅｆｆｉｃｉｅｎｃｙｏｆｓｔｏｃｈａｓｔｉｃＡＬＯＨＡｔｏｓｏｌｖｅｔａｇｓｃｏｌｌｉｓｉｏｎｉｓｖｅｒｙｌｏｗ，ａｎｄｄｅｔｅｒｍｉｎｉｓｔｉｃｔｒｅｅｓｅａｒｃｈｉｎｇａｌｇｏｒｉｔｈｍｈａｓｔｈｅｌｉｍｉｔａｔｉｏｎｔｈａｔｔｈｅｎｕｍｂｅｒｏｆｔｈｅｔａｇｓｉｎｔｈｅａｒｅａｄｏｅｓｎ’ｔｃｈａｎｇｅ．Ｔｈｉｓａｌｇｏｒｉｔｈｍｇｅｔｓｏｖｅｒｔｈｉｓｄｉｓａｄｖａｎｔａｇｅ，Ａｃｃｏｒｄｉｎｇｔｏｔｈｅｒｅａｄｅｒ’ｓｉｄｅｎｔｉｆｙｉｎｇｒｅｓｕｌｔｅａｃｈｔｉｍｅ，ｔｈｅｔａｇｓｃａｎｍｏｄｉｆｙｔｈｅｉｒｒｅｓｐｏｎｓｉｖｅｐｒｏｂａｂｉｌｉｔｙｉｎｔｈｅｉｎｃｒｅｍｅｎｔａｌｏｒｄｅｇｒｅｓｓｉｖｅｍｏｄｅ．Ｆｉｎａｌｌｙ，ｉｔｓｉｄｅｎｔｉｆｙｉｎｇｅｆｆｉｃｉｅｎｃｙｃａｎｓｔｅａｄｉｌｙａｔｔａｉｎ０．３２２ｉｎｔｈｅｄｙｎａｍｉｃｃｏｎｄｉｔｉｏｎａｎｄａｌｏｔｏｆｔａｇｓｓｉｍｕｌｔａｎｅｏｕｓｌｙａｐｐｅａｒｉｎｇ．ＴｈｉｓａｒｔｉｃｌｅｄｅｓｃｒｉｂｅｓｉｔｂｙＭａｒｋｏｖｃｈａｉｎ．Ｔｈｉｓａｒｔｉｃｌｅａｌｓｏａｎａｌｙｓｅｓｗｈａｔｖａｌｕｅｋｓｈｏｕｌｄｂｅｉｎｔｈｅｃａｓｅｔｈａｔｔｈｅｉｄｅｎｔｉｆｙｉｎｇｅｆｆｉｃｉｅｎｃｙｏｆｔｈｉｓａｌｇｏｒｉｔｈｍｉｎｉｔｉａｌｌｙｒｅａｃｈｅｓｔｈｅｂｅｓｔａｎｄｈｏｗｍｕｃｈｔｈｅｃｈａｎｇｉｎｇｒａｎｇｅｏｆｔｈｅｉｎｃｒｅａｓｅｏｒｄｅｃｒｅａｓｅｓｈｏｕｌｄｂｅｉｎｔｈｅｄｙｎａｍｉｃｓｉｔｕａｔｉｏｎｔｏｍａｋｅｔｈｉｓａｌｇｏｒｉｔｈｍｍｏｒｅａｐｐｒｏｐｒｉａｔｅａｎｄｅｆｆｉｃｉｅｎｔ．
Ｋｅｙｗｏｒｄｓ：ｅｘｐｏｎｅｎｔｉａｌｉｎｄｅｘ，ＲＦＩＤ，ａｎｔｉ－ｃｏｌｌｉｓｉｏｎａｌｇｏｒｉｔｈｍ，Ｍａｒｋｏｖｃｈａｉｎ
摘要：解决ＲＦＩＤ多标签冲突的随机ＡＬＯＨＡ方法效率较低，确定性树型方法要求区域内标签数量不变。该算法克服了这些局限，根据阅读器每次识别的结果，标签以递增或递减方式修改其应答概率。最终，该算法识别效率在动态以及标签数量庞大的情况下也可以稳定地达到０．３２２。论文用马尔可夫链理论对该算法模型进行了描述。重点针对标签以线性方式进入时，在识别效率能初步达到最优的情况下，标签可以取得的极小状态级别数ｋ以及标签应答概率动态变化时，变化的幅度如何才能更加合理进行了分析。关键词：指数索引；ＲＦＩＤ；反碰撞算法；马尔可夫链
文章编号１００２－８３３１（２００７）０１－００９０－０４文献标识码：Ａ中图分类号：ＴＰ３０１．６
基金项目：广东省科技攻关项目（２００５Ｂ１０１０１００６）；江西省科技厅项目赣科发计字［２２４］号资助；江西省教育厅项目赣教计字［３０］号资助；广州市重点科技攻关项目（２００５Ｚｚ－Ｄ０３０３１）；中山大学校基金项目（２００５－３９０００－１１３２０１７）。
作者简介：余松森，男，博士，副教授，主要从事物联网、电子识别、控制网络及应用研究；詹宜巨，教授，博导。
签将以某一概率应答。根据上一时隙阅读器对标签的识别状态，问询命令分为三种类型：
Ｒｅｑ＿ｓｕｃ：上一时隙阅读器成功识别一个标签的情况下，本时隙阅读器将发送的问询命令；
Ｒｅｑ＿ｆａｌ：上一时隙多标签冲突导致阅读器未能成功识别标签的情况下，本时隙阅读器将发送的问询命令；
Ｒｅｑ＿ｉｄｌ：上一时隙阅读器信道空闲的情况下，本时隙阅读器将发送的问询命令。
２．１．３屏蔽命令，Ｓｈｉｅｌｄ（ＥＰＣ）
阅读器发送该命令屏蔽掉区域内指定ＥＰＣ参数的标签，使其保持“静默”，不再对阅读器的问询命令应答。
阅读器在成功识别某一ＥＰＣ代码的标签之后，为避免此标签再次重复读取，可用此命令屏蔽掉它。
２．１．４标签状态分为两种：活动状态和屏蔽状态
活动状态指标签处在阅读器的问询区域但未曾被屏蔽命令所屏蔽的情形。标签处在该状态时，每一次检测到阅读器的问询命令它将以某一概率应答。
屏蔽状态指标签被阅读器用屏蔽命令屏蔽后所处的状态。标签处在该状态意味着：它已被成功识别过，所以不再对阅读器的问询命令进行应答。
２．１．５标签的应答概率
标签的应答概率ｐ采用可变值，其取值范围是一些离散值。本文约定：
ｐ∈［ｑ，ｑ
２，
ｑ
４
，
ｑ
８
，
ｑ
１６
，
ｑ
３２
，
ｑ
６４
，
ｑ
１２８
，
ｑ
２５６
，…，
ｑ
２ｋ－１
，…］
概率值为一系列２的离散有限次指数幂。
标签刚进入阅读器问询区时，将以某一初始概率ｐ（取值可为集合中间某一值）应答。以后根据阅读器每次发送的问询命令格式动态调整应答概率，调整原理为：
当阅读器发送Ｒｅｑ＿ｉｄｌ命令时，标签应答概率乘２；
当阅读器发送Ｒｅｑ＿ｓｕｃ命令时，标签应答概率不变；
当阅读器发送Ｒｅｑ＿ｆａｌ命令时，标签应答概率除２。
所以，标签的应答概率表现为以倍增或倍减方式双向动态变化，直到标签被成功识别，阅读器用屏蔽命令屏蔽掉它为止。
当然，实际应用时：应答概率倍乘时若大于ｑ则取极值ｑ；
倍除时若小于
１
１０２４
则取极小值
１
１０２４
。
２．２算法描述
本算法的运行原理分为两个方面：首先，阅读器在每一时隙发送问询命令要求区域内标签应答，在应答期根据标签的应答情况决定下一时隙应该发送的问询命令格式；同时，若成功识别出一个标签，再发一个屏蔽命令屏蔽掉该标签。其次，针对标签来说：它在每个时隙监测阅读器问询命令，根据命令格式调整应答概率，并以此概率在应答期应答。
随着标签的连续不断进入阅读器问询区，采用本算法的ＲＦＩＤ识别过程如图１所示。
３算法的数学分析
由算法模型可以看出，随着时间的推移标签所处的状态是随机的，从这个时隙到下一个时隙的状态将按照一定的概率进行转移，并且下一个时隙的状态只取决于这个时隙的状态和转移概率，与以前各个时隙的状态无关，所以本算法模型是一个典型的马尔可夫链模型。
另外，标签最终的目的是被阅读器识别，并且一旦被识别后将保持“静默”状态不再变化，所以本马尔可夫链是一个吸收链。
将时间离散化为ｍ（ｍ＝０，１，２，…）个时隙，对每一个ｍ，标签的状态用随机变量ＴＲｍ表示，设ＴＲｍ可以取ｋ个离散值ＴＲｍ＝１，２，…，ｋ，且记ａｉ（ｍ）＝Ｑ（ＴＲｍ＝ｉ），即状态概率；从ＴＲｍ＝ｉ到ＴＲｍ＋１＝ｊ的概率记ｑｉｊ＝Ｑ（ＴＲｍ＋１＝ｊ｜ＴＲｍ＝ｉ），即转移概率。
另外，标签数ｎｌ指系统中标签状态变量ＴＲｍ取值为ｌ的标签数量；应答概率ｐｌ指标签状态变量ＴＲｍ取值为ｌ时具有的应答概率。
很显然，随着时间的推移ＲＦＩＤ识别标签过程的一般情况为：在系统的每一种状态ＴＲｍ＝ｌ具有ｎｌ个标签，处在该状态的每一个标签在时隙的应答阶段将以概率ｐｌ应答，所以有下面的结论：
信道空闲的概率：
ｐｉｄｌｅ＝
ｋ－１
ｉ＝１
"（１－ｐｉ）ｎｉ（１）信道成功识别一个标签的概率：
ｐｓｕｃ＝
ｋ－１
ｌ＝１
#（ｎｌ?ｐｌ?（１－ｐｌ）ｎｌ－１?ｋ－１
ｉ＝１，ｉ≠ｌ
"（１－ｐｉ）ｎｉ）（２）信道碰撞的概率：
ｐｃｏｌｌ＝１－ｐｉｄｌｅ－ｐｓｕｃ（３）另外，在信道成功识别一个标签的情况下，该标签来自状态ＴＲｍ＝ｌ的条件概率为：
ｐ
（ＴＲ
ｍ
＝ｌ／ｓｕｃｃ）
＝
ｎｌ?ｐｌ?（１－ｐｌ）ｎｌ－１?
ｋ－１
ｉ＝１，ｉ≠ｌ
"（１－ｐｉ）ｎｉ
ｋ－１
ｌ＝１
#（ｎｌ?ｐｌ?（１－ｐｌ）ｎｌ－１?ｋ－１
ｉ＝１，ｉ≠ｌ
"（１－ｐｉ）ｎｉ）
１≤ｌ≤ｋ（４）
所以，状态ＴＲｍ＝ｌ的ｎｌ个标签在下一时隙还处于状态ｌ（ＴＲｍ＋１＝ｌ）的概率为：
ｕｌ＝
（ｎｌ－１）?ｐｓｕｃ?ｐ（ＴＲｍ
＝ｌ／ｓｕｃｃ）＋ｎｌ?ｐｓｕｃ
?（１－ｐ（ＴＲｍ
＝ｌ／ｓｕｃｃ））ｎｌ
１≤ｌ＜ｋ且ｎｌ≠００
１≤ｌ＜ｋ且ｎｌ＝#%%%$%%%&
０
（５）
状态ＴＲｍ＝ｌ的ｎｌ个标签在下一时隙处于状态ｋ（ＴＲｍ＋１＝ｋ）的概率为：
ｖｌ＝１?ｐｓｕｃ?ｐ（ＴＲｍ
＝ｌ／ｓｕｃｃ）
ｎｌ
１≤ｌ＜ｋ且ｎｌ≠００
１≤ｌ＜ｋ且ｎｌ＝#
%%%’%%%&
０
（６）
根据双向二进制指数索引的算法原理以及标签应答概率的调整规则可得：
ｑｉｊ＝ｐｉｄｌｅｉ＝ｊ＋１且１≤ｊ＜ｋ－１ｕｉ
ｉ＝ｊ且２≤ｊ＜ｋ－１ｐｃｏｌｌｉ＝ｊ－１且２≤ｊ＜#%%%’%%%&
ｋ（７－１）
另外有：
ｑｉｊ＝
ｕ１＋ｐｉｄｌｅｉ＝１且ｊ＝１ｖｉｊ＝ｋ且１≤ｉ≤ｋ－１０｜ｉ－ｊ｜≥２且ｉ，ｊ∈［１，ｋ－１］０ｉ＝ｋ且１≤ｊ≤ｋ－１ｕｋ－１＋ｐｃｏｌｌｉ＝ｋ－１且ｊ＝ｋ－１
１
ｉ＝ｋ且ｊ＝#%%%%%%%%’%%%%%%%%&
ｋ
（７－２）
因此算法的状态转移矩阵为：
Ｑ＝ｑ１１，ｑ１２，ｑ１３，…，ｑ１ｋｑ２１，ｑ２２，ｑ２３，…，ｑ２ｋ
ｑ３１，ｑ３２，ｑ３３，…，ｑ３ｋ…
…
ｑｋ１，ｑｋ２，ｑｋ３，…，ｑｋｋ
*+++++++++++++,
-............./
＝
ｕ１＋ｐｉｄｌｅ，ｐｃｏｌｌ，０，…，０，ｖ１ｐｉｄｌｅ，ｕ２，ｐｃｏｌｌ，…，０，ｖ２
０，ｐｉｄｌｅ，ｕ３
…
…ｐｉｄｌｅ，ｕｋ－１＋ｐｃｏｌｌ，ｖｋ－１
０，０，…，
０，０，*+++++++++++++++++,
-................./
１
（８）
则算法模型的状态概率基本方程为：
ａｉ（ｍ＋１）＝ｋ
ｊ＝１
0ａｊ（ｍ）ｑｊｉ，ｉ＝１，２，…，ｋ
（９）
若引入状态概率向量（行向量）：
ａ（ｍ）＝（ａ１（ｍ），ａ２（ｍ），…，ａｋ（ｍ））
则基本方程（９）可以表为：
ａ（ｍ＋１）＝ａ（ｍ）?Ｑ（１０）
所以，在ＲＦＩＤ识别的过程中，一方面只要给定初始状态就可以用式（８）～式（１０）计算任意时隙ｍ的状态；另一方面已知初始状态也可以求出系统最终为了全部达到吸收状态所需要的时隙数，从而得知其识别效率。
４算法的算例仿真分析
该算法模型与一般的马尔可夫链模型不同的地方在于：由
于不同时隙处在不同状态的标签数ｎｌ将动态变化，导致转移矩阵的值在不同的时隙具有不同的值，所以对其的效率分析难于从数学的角度直接导出。为此采用实验的方法，利用计算机仿真模拟来进行分析。
４．１该算法与时隙ＡＬＯＨＡ算法的效率比较
时隙ＡＬＯＨＡ算法中标签在每一时隙以一固定概率ｐ应
答，本次实验中ｐ＝０．１２５；双向算法中ｋ＝１１，ｐ１，ｐ２，…，ｐ１１依次为
１２，１４，１８，１１６，１３２，１６４，１１２８，１２５６
，…，１
２１１，标签的初始
应答概率取ｐ３＝０．１２５。在标签数不断变化的情况可以得到两者
的识别效率如图２所示。
虽然，ＡＬＯＨＡ算法中标签能够以动态的方式随机进入阅
读器的问询区，但图２表明其最高效率０．３２７仍低于双向算法的０．４２。随着标签数的增大，其性能将急剧下降；而双向算法效率却保持在０．３２２附近，显示出极强的稳定性。该性能对未来物联网中大批量物品的快速识别具有极其重要的意义。
４．２
标签应答概率级别数ｋ值分析
算法模型中标签应答概率级别数ｋ与算法识别效率有一
定的关系。在此，欲利用实验方法研究在算法识别效率能初步达到最优的情况下，ｋ取何极小值。其意义在于标签的状态级别数ｋ越小，系统的复杂程度就越低，产品的成本也越低。
标签以线性函数的形式动态进入：
ｎ＝ｖ?ｔ，ｔ为离散时隙
速度ｖ为每时隙０．４个标签，标签总数为２０，ｐ１＝０．５，标签
的初始应答概率为ｐ３，标签状态级别数ｋ依次为３～１３，所得结果如图３所示。从图可知：识别效率与标签应答概率级别数ｋ并不是简单的线性关系，而是在ｋ＝４时取极大值０．３４６，ｋ＝８时取极小值０．３１１。这是由于概率级别适度的调整有利于算法识别性能的提高，过度的调整将导致空闲时隙的增多，反而使算
法性能局部下降。但是波动的幅度不超过１０％，这也从另一个角度验证了本算法的稳定性。
为此，在本实验情况下，取ｋ＝４能使算法识别效率初步达到最优。
４．３
标签相邻应答概率级别之间递增／递减幅度
分析
前面的算法模型中标签相邻应答概率级别之间为２倍的
关系，在此进一步研究标签相邻应答概率级别之间递增递减的幅度ｘ如何才能更加合理有效化。实验结果如图４所示，ｘ＝２时算法性能只有０．３２６２，ｘ＝１．５时反而性能最优为０．３４４８。
（ａ）ａｌｕｍｇｒｎｓ原图（ｂ）加入０．０１５高斯噪声（ｃ）本文算法滤波
（ｄ）维纳滤波（３×３）（ｅ）中值滤波（５×５十字窗）（ｆ）均值滤波（５×５）
图５
对图４的Ｓｏｂｅｌ算子边缘检测结果
由式（７）得到的联接权模拟了高斯噪声的分布特点，其中联接权矩阵半径ｒ＝４，!＝２。其它ＰＣＮＮ参数为："＝０．０３５，#ｌ＝０．５，!$＝
１０，ＶＬ＝１，ＶＲ＝１５０，Ｖ$＝２００００；类均值算法阈值参数：$ｍａｘ＝４０，ｋ＝０．００２４。
５结论
ＰＣＮＮ以相似集群为特征产生同步脉冲发放的行为实际
上是对输入信息的重新组织，是对网络输入的一个非线性变换，正是通过这种变换特性，为实现图像的滤波提供了重要的支柱。
实验结果表明，文中的算法不仅能够去除高方差的高斯噪声，而且能够突出图像的边缘，特别是处理低频图像时，优势更
为明显。与传统的滤波方法相比，本方法在滤除噪声的同时，能较好地保护图像的边缘信息。已有的滤波方法大都是基于窗口函数的，且对噪声像素和非噪声像素不加区别地都进行滤波，显然，其滤波的结果不仅易于受到窗口大小的影响而且易于产生图像的畸变。本文方法是基于图像本身的自然区域进行滤波
的，而且仅仅针对噪声像素进行滤波，从而克服了窗口效应，有效地解决了图像滤波与图像畸变间的矛盾。（收稿日期：２００６年４月）
参考文献：
［１］ＥｃｋｈｏｒｎＲ，ＲｅｉｔｂｏｅｃｋＨＪ，ＡｒｎｄｔＭ，ｅｔａｌ．Ａｎｅｕｒａｌｎｅｔｗｏｒｋｆｏｒｆｕ－
ｔｕｒｅｌｉｎｋｉｎｇｖｉａｓｙｎｃｈｒｏｎｏｕｓａｃｔｉｖｉｔｙ：ｒｅｓｕｌｔｓｆｒｏｍｃａｔｖｉｓｕａｌｃｏｒｔｅｘａｎｄｆｒｏｍｓｉｍｕｌａｔｉｏｎｓ［Ｃ］／／ＣｏｔｔｅｒｉｌｌＲＭＪ．ＭｏｄｅｌｓｏｆＢｒａｉｎＦｕｎｃｔｉｏｎ．Ｃａｍｂｒｉｄｇｅ，ＵＫ：ＣａｍｂｒｉｄｇｅＵｉｎｖＰｒｅｓｓ，１９８９：２５５－２７２．
［２］ＬｉｎＨＭ，ＷｉｌｌｓｏｎＡＮ．Ｍｅｄｉａｎｆｉｌｔｅｒｓｗｉｔｈａｄａｐｔｉｖｅｌｅｎｇｔｈ［Ｊ］．ＩＥＥＥ
ＴｒａｎｓａｃｔｉｏｎｓｏｎＣｉｒｃｕｉｔｓａｎｄＳｙｓｔｅｍｓ，１９８８，３５（６）：６７５－６９０．［３］ＢｒｏｗｎｒｉｇｇＤＲＫ．Ｔｈｅｗｅｉｇｈｔｅｄｍｅｄｉａｎｆｉｌｔｅｒ［Ｊ］．ＣｏｍｍｕｎＡｓｓＣｏｍ－
ｐｕｔ，１９８４，２７（８）：８０７－８１８．
［４］ＰｌｔａｓＬ，ＶｅｎｅｒｓａｎｏｐｏｕｌｏｓＡＮ．Ｎｏｎｌｉｎｅａｒｄｉｇｉｔａｌｆｉｌｔｅｒ：Ｐｒｉｎｃｉｐｌｅａｎｄ
Ａｐｐｌｉｃｔｉｏｎｓ［Ｍ］．Ｄｃｅｉｍｃｈｔ：Ｋｌｕｗｅｒ，１９９０．
［５］ＨａｒｄｉｅＲＣ，ＢａｒｎｅｒＫＥ．Ｒａｎｋｃｏｎｄｉｔｉｏｎｅｄｒａｎｋｓｅｌｅｃｔｉｏｎｆｉｌｔｅｒｓ
ｆｏｒｓｉｇｎａｌｒｅｓｔｏｒａｔｉｏｎ［Ｊ］．ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎＩｍａｇｅＰｒｏｃｅｓｓｉｎｇ，１９９４，３（２）：１９２－２０６．
［６］李树涛，王耀南．图像椒盐噪声的非线性自适应滤波［Ｊ］．中国图象图
形学报，２０００，５（Ａ１２）：９９９－１００１．
（上接６７页）５结论
从上面的研究分析可以看出本算法模型的特点是：（１）在理想静态情况下，该算法效率略低于ＲＦＩＤ树形搜
索反碰撞算法，但高于动态时隙ＡＬＯＨＡ算法。
（２）在动态情况下，该算法效率不仅高于动态时隙ＡＬＯＨＡ算法，而且远远优于树形搜索反碰撞算法。
（３）该算法性能极其稳定。标签数量急剧增大时，识别效率稳定在某一值附近。
（４）在公平性方面，不会造成８０２．３协议中二进制指数后退算法那种后到先处理的不利局面。适当选择标签的初始应答概率，有利于形成先到先服务的局面，也优于ＡＬＯＨＡ算法中采用一律平等的服务概率。（收稿日期：２００６年５月）
参考文献
［１］ＶｏｇｔＨ．ＭｕｌｔｉｐｌｅｏｂｊｅｃｔｉｄｅｎｔｉｆｉｃａｔｉｏｎｗｉｔｈｐａｓｓｉｖｅＲＦＩＤｔａｇｓ［Ｃ］／／Ｐｅｒｖａｓｉｖｅ２００２，Ｚｕｒｉｃｈ，Ｓｗｉｔｚｅｒｌａｎｄ，２００２－０８：９８－１１３．
［２］ＰａｎｔａｚｉＡ，ＡｎｔｏｎａｋｏｐｏｕｌｏｓＴ．Ｅｑｕｉｌｉｂｒｉｕｍｐｏｉｎｔａｎａｌｙｓｉｓｏｆｔｈｅｂｉｎａｒｙ
ｅｘｐｏｎｅｎｔｉａｌｂａｃｋｏｆｆａｌｇｏｒｉｔｈｍ［Ｊ］．ＣｏｍｐｕｔｅｒＣｏｍｍｕｎｉｃａｔｉｏｎｓ，２００１，２４：１７５９－１７６８．
［３］ＫａｌｉｎｏｗｓｋｉＲ，ＬａｔｔｅｕｘＭ，ＳｉｍｐｗｔＤ．Ａｎａｄａｐｔｉｖｅａｎｔｉｃｏｌｌｉｓｉｏｎｐｒｏ－
ｔｏｃｏｌｆｏｒｓｍａｒｔｌａｂｅｌｓ［ＥＢ／ＯＬ］．ｈｔｔｐ：／／ｗｗｗ．ｌｉｆｌ．ｆｒ／～ｓｉｍｐｌｏｔ／ｒｅｃｈｅｒｃｈ／ａｒ－ｔｉｃｌｅｓ，２００１．
［４］ＪａｎｓｓｅｎＡＪＥＭ，ｄｅＪｏｎｇＭＪＭ．Ａｎａｌｙｓｉｓｏｆｃｏｎｔｅｎｔｉｏｎｔｒｅｅ－ａｌ－ｇｏｒｉｔｈｍｓ［Ｊ］．ＩＥＥＥＴｒａｎｓｉｎｆｏｒｍＴｈｅｏｒｙ，１９９５，３１：１１９－１２３．［５］ＬａｗＣ，ＬｅｅＫ，ＳｉｕＫＹ．Ｅｆｆｉｃｉｅｎｔｍｅｍｏｒｙｌｅｓｓｐｒｏｔｏｃｏｌｆｏｒｔａｇｉｄｅｎ－
ｔｉｆｉｃａｔｉｏｎ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ４ｔｈＩｎｔｅｒｎａｔｉｏｎａｌＷｏｒｋｓｈｏｐｏｎＤｉｓｃｒｅｔｅＡｌｇｏｒｉｔｈｍｓａｎｄＭｅｔｈｏｄｓｆｏｒＭｏｂｉｌｅＣｏｍｐｕｔｉｎｇａｎｄ
Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，ＡＣＭ，２０００－０８：７５－８４．
［６］ＤｏｎＨｕｓｈＲ，ＷｏｏｄＣ．ＡｎａｌｙｓｉｓｏｆｔｒｅｅａｌｇｏｒｉｔｈｍｓｆｏｒＲＦＩＤａｒｂｉ
ｔｒａｔｉｏｎ［Ｃ］／／ＩＥＥＥＩｎｔｅｒｎａｔｉｏｎａｌＳｙｍｐｏｓｉｕｍｏｎＩｎｆｏｒｍａｔｉｏｎＴｈｅｏｒｙ．ＩＥＥＥ，１９９８．
［７］余松森，詹宜巨．基于后退式索引的二进制树形搜索反碰撞算法及
其实现［Ｊ］．计算机工程与应用，２００４，４０（１６）：２６－２８．
［８］ＭａｒｓａｎＭＡ，ＢｒｕｓｃａｇｉｎＭ．ＭｕｌｔｉｃｈａｎｎｅｌＡＬＯＨＡｎｅｔｗｏｒｋｓｗｉｔｈｒｅ－ｄｕｃｅｄｃｏｎｎｅｃｔｉｏｎｓ［Ｃ］／／ＩＥＥＥＩＮＦＯＣＯＭ’８７，ＳａｎＦｒａｎｃｉｓｃｏ，ＣＡ，１９８７－０４：２６８－２７５．
［９］ＨｅｍａｎｄｅｚＰ，ＳａｎｄｏｖａｌＪＤ．Ｍａｔｈｅｍａｔｉｃａｌｍｏｄｅｌｆｏｒａｍｕｌｔｉｒｅａｄａｎ－ｔｉｃｏｌｌｉｓｉｏｎｐｒｏｔｏｃｏｌ［Ｊ］．Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，ＣｏｍｐｕｔｅｒｓａｎｄＳｉｇｎａｌＰｒｏｃｅｓｓ－ｉｎｇ，２００１：４－３８．
［１０］蒋纯波．射频识别系统手持式读写设备的设计及在邮政速递业务
中应用系统的研究［Ｄ］．２００１．
［１１］沈宇超．一种用于多目标实时识别的防碰撞算法＊———
射频识别系统的关键技术［Ｊ］．北京邮电大学学报，２００２（３）：１０－１４．
［１２］吴春华，陈军．动态ＡＬＯＨＡ法在解决ＲＦＩＤ反碰撞问题中的应用［Ｊ］．
电子器件，２００３（２）．
数据结构与算法习题及答案
第1章绪论 习题 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 4．存储结构由哪两种基本的存储方法实现 5．选择题 （1）在数据结构中，从逻辑上可以把数据结构分成（）。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 （2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。 A．存储结构B．存储实现 C．逻辑结构D．运算实现 （3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。 A．数据具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 （4）以下说法正确的是（）。 A．数据元素是数据的最小单位 B．数据项是数据的基本单位 C．数据结构是带有结构的各数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 （5）以下与数据的存储结构无关的术语是（）。 A．顺序队列B.链表C.有序表D.链栈 （6）以下数据结构中，（）是非线性数据结构 A．树B．字符串C．队D．栈 6．试分析下面各程序段的时间复杂度。 （1）x=90;y=100; while(y>0) if(x>100) {x=x-10;y--;} elsex++; （2）for(i=0;i 2.1 用二分法求方程013=--x x 在[1, 2]的近似根，要求误差不超过3102 1-?至少要二分多少？ 解：给定误差限ε＝0.5×10－3，使用二分法时，误差限为 )(211*a b x x k k -≤-+ 只要取k 满足ε<-+)(2 11 a b k 即可，亦即 96678.912lg 10lg 35.0lg 12lg lg )lg(=-+-=---≥εa b k 只要取n ＝10. 2.3 证明方程1 -x –sin x ＝0 在区间[0, 1]内有一个根，使用二分法求误差不超过 0.5×10-4的根要二分多少次？ 证明 令f (x )＝1－x －sin x ， ∵ f (0)=1>0，f (1)=－sin1<0 ∴ f (x )=1－x －sin x =0在[0，1]有根.又 f '(x )=-1－c os x<0 (x ∈[0.1]),故f (x ) 在[0，1]单调减少，所以f (x ) 在区间 [0，1]内有唯一实根. 给定误差限ε＝0.5×10－4，使用二分法时，误差限为 )(211*a b x x k k -≤-+ 只要取k 满足ε<-+)(211 a b k 即可，亦即 7287.1312 lg 10lg 45.0lg 12lg lg )lg(=-+-=---≥εa b k 只要取n ＝14. 2.4 方程0123=--x x 在x =1.5附近有根，把方程写成四种不同的等价形式，并建立相应的迭代公式： （1）211x x +=，迭代公式2111k k x x +=+ （2）231x x +=，迭代公式3211k k x x +=+ （3）112-=x x ，迭代公式111-=+k k x x （4）13-=x x ，迭代公式131-=+k k x x 试分析每种迭代公式的收敛性，并选取一种收敛迭代公式求出具有四位有效数字的近似根。 解：（1）令211)(x x f + =，则3 2)(x x f -='，由于 159.05.112)(33<≈≤='x x f ，因而迭代收敛。 （2）令321)(x x f +=，则322)1(3 2)(-+='x x x f ，由于 计算机基础作业 第一章计算机与信息社会 习题1 一、思考题： 1．计算机的发展经历了哪几个阶段？各阶段的主要特征是什么？ 答：计算机经历了电子管、晶体管、中小规模集成电路和大、超大规模集成电路等4个阶段。 电子管计算机的特征是：采用电子管作为计算机的逻辑元件，内存储器采用水银延迟线，外存储器采用磁鼓、纸带、卡片等，运算速度只有每秒几千次到几万次基本运算，内存容量只有几千个字节，使用二进制表示的机器语言或汇编语言编写程序。 晶体管计算机的特征是：用晶体管代替了电子管，大量采用磁芯作为内存储器，采用磁盘、磁带等作为外存储器。 采用了中小规模集成电路的计算机的特征是：用集成电路代替了分立元件。集成电路是把多个电子元器件集中在几平方毫米的基片上形成的逻辑电路。 采用了大、超大规模集成电路的计算机的特征是：以大规模、超大规模集成电路来构成计算机的主要功能部件，主存储器采用集成度很高的半导体存储器，目前计算机的最高速度可以达到每秒几十万亿次浮点运算。 4．计算机主要用于哪些领域？ 答：计算机主要应用在科学和工程计算、信息和数据处理、过程控制、计算机辅助系统及人工智能等领域。 7．信息技术都包含那些？ 答：信息技术主要包括信息基础技术、信息系统技术、信息应用技术三个层次。 二、选择题 1.最早的计算机是用来进行（A)的。 A ）科学计算B）系统仿真C）自动控制D)信息处理 2.构成第二代计算机的主要电子元件是（B) A ）电子管B）晶体管C）中.小规模集成电路D)超大规模集成电路 3.以下哪个不是计算机的特点（D) A ）计算机的运行速度快B）计算机的准确度高C）计算机的存储容量巨大D)计算机的体积很小 4办公自动化属于计算机哪项应用（A) A ）数据处理B）科学计算C）辅助设计D)人工智能 5.以下关于信息的特征不正确的是（B) A ）共享性B）不可存储C）可处理性D)可传递 算法设计与分析试卷 一、填空题（20分，每空2分） 1、算法的性质包括输入、输出、＿＿＿、有限性。 2、动态规划算法的基本思想就将待求问题＿＿＿＿＿、先求 解子问题，然后从这些子问题的解得到原问题的解。 3、设计动态规划算法的4个步骤： （1）找出＿＿＿＿，并刻画其结构特征。 （2）＿＿＿＿＿＿＿。 （3）＿＿＿＿＿＿＿。 （4）根据计算最优值得到的信息，＿＿＿＿＿＿＿。 4、流水作业调度问题的johnson算法： （1）令N1=＿＿＿,N2={i|ai>=bj}; （2）将N1中作业依ai的＿＿＿。 5、对于流水作业高度问题，必存在一个最优调度π，使得作业π（i）和π（i+1）满足Johnson不等式＿＿＿＿＿。 6、最优二叉搜索树即是＿＿＿的二叉搜索树。 二、综合题（50分） 1、当（a1,a2,a3,a4,a5,a6）=(-2,11,-4,13,-5,-2)时，最大子段和为∑ak(2<=k<=4)＿＿＿＿（5分） 2、由流水作业调度问题的最优子结构性质可知，T（N，0）=＿＿＿＿＿＿（5分） 3、最大子段和问题的简单算法(10分) int maxsum(int n,int *a,int & bestj) { intsum=0; for (int i=1;i<=n;i++) for (int j=i;j<=n;j++) int thissum=0; for(int k=i;k<=j;k++)＿＿＿＿＿; if(thissum>sum){ sum=thissum; ＿＿＿＿＿＿； bestj=j;} } return sum; } 4、设计最优二叉搜索树问题的动态规划算法 OptimalBinarysearchTree? (15分) Void OptimalBinarysearchTree(int a,int n,int * * m, int * * w) { for(int i=0;i<=n;i++) {w[i+1][i]=a[i]; m[i+1][i]=＿＿＿＿;} for(int r=0;r 算法实现题3-7 数字三角形问题 问题描述： 给定一个由n行数字组成的数字三角形，如图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。编程任务： 对于给定的由n行数字组成的数字三角形，编程计算从三角形的顶至底的路径经过的数字和的最大值。数据输入： 有文件input.txt提供输入数据。文件的第1行是数字三角形的行数n，1<=n<=100。接下来的n行是数字三角形各行的数字。所有数字在0-99之间。结果输出： 程序运行结束时，将计算结果输出到文件output.txt中。文件第1行中的数是计算出的最大值。 输入文件示例输出文件示 例 input.txt output.txt 5 30 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 源程序： #include "stdio.h" voidmain() { intn,triangle[100][100],i,j;//triangle数组用来存储金字塔数值,n表示行数 FILE *in,*out;//定义in，out两个文件指针变量 in=fopen("input.txt","r"); fscanf(in,"%d",&n);//将行数n读入到变量n中 for(i=0;i 第一章 1. 计算机的发展经历了那几个阶段？各阶段的主要特征是什么？ a）四个阶段： 电子管计算机阶段；晶体管电路电子计算机阶段；集成电路计算机阶段；大规模集成电路电子计算机阶段。 b ）主要特征： 电子管计算机阶段：采用电子管作为计算机的逻辑元件；数据表示主要是定点数；用机器语言或汇编语言编写程序。 晶体管电路电子计算机阶段：采用晶体管作为计算机的逻辑元件，内存大都使用铁金氧磁性材料制成的磁芯存储器。集成电路计算机阶段：逻辑元件采用小规模集成电路和中规模集成电路。 大规模集成电路电子计算机阶段：逻辑元件采用大规模集成电路和超大规模集成电路。 2. 按综合性能指标分类，计算机一般分为哪几类？请列出各计算机的代表机型。 高性能计算机（曙光），微型机（台式机算机），工作站（DN-100 ）,服务器（Web服务器）。 3. 信息与数据的区别是什么？ 信息：对各种事物的变化和特征的反映，又是事物之间相互作用和联系表征。数据：是信息的载体。 4. 什么是信息技术？ 一般是指一系列与计算机等相关的技术。 5. 为什么说微电子技术是整个信息技术的基础？ 晶体管是集成电路技术发展的基础，而微电子技术就是建立在以集成电路为核心的各种半导体器件基础上的高新电子技术。 6. 信息处理技术具体包括哪些内容？3C含义是什么？ a ）对获取的信息进行识别、转换、加工，使信息安全地存储、传送，并能方便的检索、再生、利用，或便于人们从中提炼知识、发现规律的工作手段。b）信息技术、计算机技术和控制技术的总称 7. 试述当代计算机的主要应用。 应用于科学计算、数据处理、电子商务、过程控制、计算机辅助设计、计算机辅助制造、计 算机集成制造系统、多媒体技术和人工智能等。 4.2在下列情况下求解递归关系式T(n)=g(n) 2T(n/2)f(n)n足够小 否则 当①n=2kg(n)=O (1)和f(n)=O(n)； ②n=2kg(n)=O (1)和f(n)=O (1)。 解: T(n)=T(2k)=2 T(2k-1)+f(2k)=2(2 T(2k-2)+f(2k-1)) +f(2k) =22T(2k-2)+21f(2k-1)+ f(2k) =…… =2kT (1)+2k-1f (2)+2k-2f (22)+…+20f(2k)kk-1k-220k=2g(n)+ 2f (2)+2f (2)+ (2) (2)①当g(n)=O (1)和f(n)=O(n)时， 不妨设g(n)=a，f(n)=bn，a，b为正常数。则 T(n)=T(2k)= 2ka+ 2k-1*2b+2k-2*22b+…+20*2kb =2ka+kb2k =an+bnlog 2n=O(nlog 2n) ②当g(n)=O (1)和f(n)=O (1)时， 不妨设g(n)=c，f(n)=d，c，d为正常数。则 T(n)=T(2k)=c2k+ 2k-1d+2k-2d+…+20d=c2k+d(2k-1) =(c+d)n-d=O(n) 4.3根据教材中所给出的二分检索策略，写一个二分检索的递归过程。 Procedure BINSRCH(A, low, high, x, j) integer mid if low≤high then mid← (low high)/2 if x=A(mid) then j←mid; endif if x>A(mid) then BINSRCH(A, mid+1, high, x, j); endif x 《数据结构与算法》课后习题 答案 2.3 课后习题解答 2．3.2 判断题 1.线性表的逻辑顺序与存储顺序总是一致的。（×） 2．顺序存储的线性表可以按序号随机存取。（√） 3.顺序表的插入和删除操作不需要付出很大的时间代价,因为每次操作平均只有近一半的元素需要移动。（×） 4.线性表中的元素可以是各种各样的,但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。（√）...文档交流仅供参考... 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（×) ６.在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（√) 7.线性表的链式存储结构优于顺序存储结构。（×) 8．在线性表的顺序存储结构中,插入和删除时移动元素的个数与该元素的位置有关。（√） 9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（√） 10．在单链表中，要取得某个元素,只要知道该元素的指针即可，因此,单链表是随机存取的存储结构。(×)１１.静态链表既有顺序存储的优点，又有动态链表的优点。所以它存取表中第i个元素的时间与ｉ无关。(×） 12.线性表的特点是每个元素都有一个前驱和一个后继。（×) 2．3．3 算法设计题 1．设线性表存放在向量A[arｒｓize]的前eleｎum个分量中，且递增有序。试写一算法,将x 插入到线性表的适当位置上,以保持线性表的有序性，并且分析算法的时间复杂度。...文档交流仅供参考... 【提示】直接用题目中所给定的数据结构（顺序存储的思想是用物理上的相邻表示逻辑上的相邻,不一定将向量和表示线性表长度的变量封装成一个结构体),因为是顺序存储，分配的存储空间是固定大小的,所以首先确定是否还有存储空间，若有，则根据原线性表中元素的有序性,来确定插入元素的插入位置,后面的元素为它让出位置,（也可以从高下标端开始一边比较,一边移位)然后插入ｘ，最后修改表示表长的变量。...文档交流仅供参考... int iｎsert （datａtypｅＡ[］，iｎt *eｌｅnｕm，dataｔypｅ x)???/*设eｌenum为表的最大下标＊/...文档交流仅供参考... 习题二 1. 证明方程043 =-+x x 在区间[1，2]内有一个根。如果用二分法求它具有5位有效数字的根，需要 二分多少次。 证明: （1） 不妨令 4)(3-+=x x x f ，求得： 02)1(<-=f 06)2(>=f 又因为4)(3-+=x x x f 在区间[1，2]内是连续的，所以在区间[1，2]内有至少一个根。 又因为 13)(2'+=x x f 在区间[1，2]内013)(2'>+=x x f ，所以4)(3-+=x x x f 单调。 得证，043 =-+x x 在区间[1，2]内仅有一个根。 （2）具有5位有效数字的根，说明根可以表示成 5 4321.a a a a a ，所以绝对误差限应该是 5a 位上的 一半，即： 4105.0-?=ε。由公式： ε≤-+1 2 k a b 可得到, 14=k 迭代次数为151=+k 次。 ---------------------------------------------------------------------------------------------------------------------- 2. 用二分法求方程 0)2 (sin )(2=-=x x x f 在区间[1.5，2]内的近似根（精确到10-3）。 解：043499.05625.099749.0)25.1(5.1sin )5.1(2 >=-=-=f 009070.0190930.0)22(2sin )2(2 <-=-=-=f 所以0)2 (sin )(2 =-=x x x f 在区间[1.5，2]内有根，又 x cos )('-=x x f 在区间[1.5，2]内 0x cos )('<-=x x f 所以 0)2 (sin )(2=-=x x x f 在区间[1.5，2]内有根，且唯一。符合二分条件，可以用二分法，二分的 次数为： 第一章 1．计算机的发展经历了哪几个阶段？各阶段的主要特点是什么？ 答：电子计算机的发展已经历了四个明显的阶段（也称为四代）.正向第五代智能化的计算机发展。 前四代计算机的特点是： 第一代为电子管计算机.使用的软件程序主要为机器语言。 第二代机是以晶体管作为主要逻辑元件的计算机.软件程序使用了汇编语言且高级程序设计语言诞生。 第三代机是由中小规模集成电路组成的计算机.软件程序使用状况是：操作系统和结构化程序设计语言诞生使用。 第四代机是由大规模或超大规模集成电路组成的计算机.软件状况为网络操作系统、面向对象程序设计诞生和使用。 2．计算机内为什么采用二进制数表示信息？ 答：电子计算机内部采用二进制数表示信息的主要原因是： （1）二进制数数码少（只有0和1两个）.因此易于实现其数码的表示； （2）二进制数的运算法简单； （3）采用二进制数易于实现逻辑运算。 3．计算机硬件系统由哪几部份组成？各部份的主要功能是什么？ 答：电子计算机硬件由运算器、控制器、存储器、输入设备和输出设备组成。它们通过总线连接成有机整体。 运算器的主要功能是：完成算术运算和逻辑运算； 控制器的功能是：协调指挥计算机各部件工作； 存储器的主要作用是：存储程序和数据.实现记忆的功能。 输入设备的功能是：输入数据并转换为机内信息存储； 输出设备的作用是：将机内信息转换为便于识别、处理和使用的字符、图形输出显示。4．什么是硬件？什么是软件？它们有何关系？ 答：计算机硬件是构成机器的电子、光电、电磁、机械等物理设备。软件即是计算机中使用的各种各样的程序及其说明文档。 硬件与软件的关系是：硬件是软件运行的基础.软件扩充了硬件的功能。 5．什么是指令？什么是程序？计算机的指令由哪两部份组成？ 答：指令是计算机能实现的基本操作.指令均为二进制数形式。程序是若干指令或命令的集合。指令由操作码和地址码（操作数）组成.操作码告诉计算机执行什么操作（指明指令的功能）.地址码告诉计算机到哪个存储单元地址中读取参与操作的数据。 6．计算机程序设计语言如何分类？什么程序语言是计算机能直接识别和执行的？ 答：计算机程序设计语言可分为低级语言和高级语言两大类。低级语言包括：机器语言和汇编语言.它们都是面向计算机硬件的程序设计语言。高级语言有：面向过程的结构化的程序设计语言（Basic、Pascal、C……）和面向对象的程序设计语言（Visual Basic、Visual FoxPro、Visual C……）。 7．高级程序设计语言的两种执行方式是哪两种？ 答：解释方式——边解释边执行.速度慢但方便程序调试。 编译方式——程序源代码全部编译后再执行.执行速度快.但不易查错。通常是先源代码程序调试成功后再编译使用。 第3章栈和队列 一、基础知识题 3.1有五个数依次进栈：1，2，3，4，5。在各种出栈的序列中，以3，4先出 的序列有哪几个。（３在４之前出栈）。 【解答】34215 ，34251， 34521 3.2铁路进行列车调度时，常把站台设计成栈式结构，若进站的六辆列车顺序 为：1，2，3，4，5，6，那么是否能够得到435612， 325641， 154623和135426的出站序列，如果不能，说明为什么不能；如果能，说明如何得到(即写出"进栈"或"出栈"的序列)。 【解答】输入序列为123456，不能得出435612和154623。不能得到435612的理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能让栈底元素1在栈顶元素2之前出栈。不能得到154623的理由类似，当栈中元素只剩23，且3在栈顶，2不可能先于3出栈。 得到325641的过程如下：1 2 3顺序入栈，32出栈，得到部分输出序列32；然后45入栈，5出栈，部分输出序列变为325；接着6入栈并退栈，部分输出序列变为3256；最后41退栈，得最终结果325641。 得到135426的过程如下：1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出栈，部分输出序列变为13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果135426。 3.3若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别 为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？ 【解答】2和 4 3.4设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通 过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e3，e5，e4，e6，e2，e1，则栈S的容量至少应该是多少？ 【解答】 4 3.5循环队列的优点是什么，如何判断“空”和“满”。 【解答】循环队列解决了常规用0--m-1的数组表示队列时出现的“假溢出”（即队列未满但不能入队）。在循环队列中我们仍用队头指针等于队尾指针表示队空，而用牺牲一个单元的办法表示队满，即当队尾指针加1（求模）等于队头指针时，表示队列满。也有通过设标记以及用一个队头或队尾指针加上队中元素个数来区分队列的“空”和“满”的。 3.6设长度为n的链队列用单循环链表表示，若只设头指针，则入队和出队的 时间如何？若只设尾指针呢？ 【解答】若只设头指针，则入队的时间为O(n），出队的时间为O(1)。若只设尾指针，则入队和出队的时间均为O(1)。 3.7指出下面程序段的功能是什么？ (1)void demo1(SeqStack S) {int i，arr[64]，n=0; while(!StackEmpty(S)) arr[n++]=Pop(S); 计算机基础练习题 1.微机硬件系统中最核心的部件是____ 。 A、内存储器 B、输入输出设备 C、CPU D、硬盘 2.根据计算机使用的电信号来分类，电子计算机分为数字计算机和模拟计算机，其中，数 字计算机是以____为处理对象。 A、字符数字量 B、物理量 C、数字量 D、数字、字符和物理量 3.用MIPS来衡量的计算机性能指标是____ 。 A、传输速率 B、存储容量 C、字长 D、运算速度 4.交互式操作系统允许用户频繁地与计算机对话，下列不属于交互式操作系统的是____。 A、Windows系统 B、DOS系统 C、分时系统 D、批处理系统 5.计算机硬盘正在工作时应特别注意避免____。 A、噪声 B、震动 C、潮湿 D、日光 6.下列四条叙述中，正确的一条是____。 A、字节通常用英文单词“bit”来表示 B、目前广泛使用的Pentium机其字长为5个字节 C、计算机存储器中将8个相邻的二进制位作为一个单位，这种单位称为字节 D、微型计算机的字长并不一定是字节的倍数 7.一条计算机指令中规定其执行功能的部分称为____。 A、源地址码 B、操作码 C、目标地址码 D、数据码 8.在微型计算机中，内存储器，通常采用____。 A、光存储器 B、磁表面存储器 C、半导体存储器 D、磁芯存储器 9.微型计算机键盘上的Tab键是____。 A、退格键 B、控制键 C、交替换档键 D、制表定位键 10.在计算机中，既可作为输入设备又可作为输出设备的是____。 A、显示器 B、磁盘驱动器 C、键盘 D、图形扫描仪 11.微型计算机中，ROM的中文名字是____。 A、随机存储器 B、只读存储器 C、高速缓冲存储器 D、可编程只读存储器 12.要存放10个24×24点阵的汉字字模，需要____存储空间。 A、74B B、320B C、720B D、72KB 13.把硬盘上的数据传送到计算机的内存中去，称为____。 A、打印 B、写盘 C、输出 D、读盘 14. 3.5英寸软盘片角上有一带黑滑块的小方口，当小方口被关闭时，其作用是____。 计算机算法设计与分析习 题及答案 Prepared on 24 November 2020 《计算机算法设计与分析》习题及答案 一．选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5．下列算法中通常以自底向上的方式求解最优解的是（B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是（ D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是（A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9．下面不是分支界限法搜索方式的是（D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 10．下列算法中通常以深度优先方式系统搜索问题解的是（D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 11.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为（B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 13．分支限界法解最大团问题时，活结点表的组织形式是（B ）。 A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是（B）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是（A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是（C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略（B ） A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 19. （D）是贪心算法与动态规划算法的共同点。 《数据结构简明教程》练习题及参考答案 练习题1 1. 单项选择题 （1）线性结构中数据元素之间是（）关系。 A.一对多 B.多对多 C.多对一 D.一对一 答：D （2）数据结构中与所使用的计算机无关的是数据的（）结构。 A.存储 B.物理 C.逻辑 D.物理和存储 答：C （3）算法分析的目的是（）。 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 答：C （4）算法分析的两个主要方面是（）。 A.空间复杂性和时间复杂性 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 答：A （5）计算机算法指的是（）。 A.计算方法 B. 排序方法 C.求解问题的有限运算序列 D.调度方法 答：C （6）计算机算法必须具备输入、输出和（）等5个特性。 A.可行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 答：B 2. 填空题 （1）数据结构包括数据的①、数据的②和数据的③这三个方面的内容。 答：①逻辑结构②存储结构③运算 （2）数据结构按逻辑结构可分为两大类，它们分别是①和②。 答：①线性结构②非线性结构 （3）数据结构被形式地定义为（D,R），其中D是①的有限集合，R是D上的②有限集合。 答：①数据元素 ②关系 （4）在线性结构中，第一个结点 ① 前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点 ② 后继结点，其余每个结点有且只有1个后继结点。 答：①没有 ②没有 （5）在树形结构中，树根结点没有 ① 结点，其余每个结点有且只有 ② 个前驱结点；叶子结点没有 ③ 结点，其余每个结点的后继结点数可以是 ④ 。 答：①前驱 ②1 ③后继 ④任意多个 （6）在图形结构中，每个结点的前驱结点数和后继结点数可以是（ ）。 答：任意多个 （7）数据的存储结构主要有四种，它们分别是 ① 、 ② 、 ③ 和 ④ 存储结构。 答：①顺序 ②链式 ③索引 ④哈希 （8）一个算法的效率可分为 ① 效率和 ② 效率。 答：①时间 ②空间 3. 简答题 （1）数据结构和数据类型两个概念之间有区别吗？ 答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素的集合。数据类型不仅定义了一组数据元素，而且还在其上定义了一组操作。 （2）简述线性结构、树形结构和图形结构的不同点。 答：线性结构反映结点间的逻辑关系是一对一的，树形线性结构反映结点间的逻辑关系是一对多的，图在结构反映结点间的逻辑关系是多对多的。 （3）设有采用二元组表示的数据逻辑结构S=(D,R)，其中D={a ,b ,…,i }，R={(a ,b ),(a ,c ),(c ,d ),(c ,f ),(f ,h ),(d ,e ),(f ,g ),(h ,i )}，问相对于关系R ，哪些结点是开始结点，哪些结点是终端结点？ 答：该逻辑结构为树形结构，其中a 结点没有前驱结点，称为根结点，b 、e 、g 、i 结点没有后继结点，是终端结点，也称为叶子结点。 （4）以下各函数是算法中语句的执行频度，n 为问题规模，给出对应的时间复杂度： T 1(n )=n log 2n -1000log 2n T 2(n )=3log 2n -1000log 2n T 3(n )=n 2 -1000log 2n T 4(n )=2n log 2n -1000log 2n 答：T 1(n )=O(n log 2n )，T 2(n )=O( )，T 3(n )=O(n 2 )，T 4(n )=O(n log 2n )。 （5）分析下面程序段中循环语句的执行次数。 int j=0,s=0,n=100; do { j=j+1; s=s+10*j; } while (j 引论试题（11页） 4 试证：对任给初值x 0, 0)a >的牛顿迭代公式 112(),0,1 ,2,......k a k k x x x k +=+= 恒成立下列关系式： 2112(1)(,0,1,2,.... (2)1,2,...... k k k x k x x k x k +-=≥= 证明： （1 ）(2 2 11222k k k k k k k k x a x a x x x x x +-??-+=+= =? ?? （2） 取初值00>x ，显然有0>k x ，对任意0≥k ， a a x a x x a x x k k k k k ≥+??? ? ??-=???? ??+=+2 12121 6 证明： 若k x 有n 位有效数字，则n k x -?≤ -1102 1 8， 而() k k k k k x x x x x 28882182 1-=-???? ??+=-+ n n k k x x 21221102 1 5.22104185 .28--+?=??<-∴>≥ 1k x +∴必有2n 位有效数字。 8 解： 此题的相对误差限通常有两种解法. ①根据本章中所给出的定理： （设x 的近似数* x 可表示为m n a a a x 10......021*?±=，如果* x 具有l 位有效数字，则其相对误差限为 ()11 * *1021 --?≤ -l a x x x ，其中1a 为*x 中第一个非零数） 则7.21=x ，有两位有效数字，相对误差限为 025.0102 21 111=??≤--x x e 71.22=x ，有两位有效数字，相对误差限为 025.0102 21 122=??≤--x x e 3 2.718x =，有两位有效数字，其相对误差限为： 00025.0102 21 333=??≤--x e x ②第二种方法直接根据相对误差限的定义式求解 对于7.21=x ，0183.01<-e x ∴其相对误差限为 00678.07 .20183 .011≈<-x e x 同理对于71.22=x ，有 003063 .071 .20083 .022≈<-x e x 对于718.23=x ，有 00012.0718 .20003 .033≈<-x e x 备注：（1）两种方法均可得出相对误差限，但第一种是对于所有具有n 位有效数字的近似数都成立的正确结论，故他对误差限的估计偏大，但计算略简单些；而第二种方法给出较好的误差限估计，但计算稍复杂。 （2）采用第二种方法时，分子为绝对误差限，不是单纯的对真实值与近似值差值的四舍五入，绝对误差限大于或等于真实值与近似值的差。 11. 解: ......142857.3722≈，.......1415929.3113 255≈ 21021 722-?≤-∴ π，具有3位有效数字 6102 1 113255-?≤-π，具有7位有效数字 第1章 计算机基础知识 一、填空题 1．硬件系统、软件系统 2．(11011101)2=(221)10 =(335)8=(DD)16 3．1101.011 4．11110111.00000 ．011 ．(小数点后第5位到第8位循环) 5．1111 6．221 7．主存、Cache ram,rom 8．RAM 、ROM 9．外存 10．读、写、字节 二、选择题 1-5:CBADC 6-10:AADDD 11-15:ACCAD 三、判断题 1-5:错错对对对 6-10:对错错错错 四、简答题 1．修改题干：简述计算机发展各阶段所采用的逻辑部件及计算机的发展趋势。 答案：第一代计算机：电子管 第二代计算机：晶体管 第三代计算机：中小规模集成电路 第四代计算机：大规模、超大规模集成电路 计算机的研制正向智能化、网络化、巨型化、微型化、多媒体化的方向前进。 2．修改题干：简述计算机内部的信息为什么要采用二进制数编码来表示？ 答案：因为采用二进制易于物理实现，机器可靠性高，运算规则简单。 3．位：代表一个二进制数位，是计算机表示数据的最小单位。 字节：计算机内部以字节为单位存储数据。1B=8b 。 字：CPU 通过数据总线一次存取、加工和传送的数据单位称为字。一个字通常由若干个字节组成。字长：一个字对应的位数。 4．1）运算速度 2）主频 3）字长 4）内存容量 5）外设扩展能力 6）软件配置情况 5．原码：数X 补码：X 原码：01010010 反码：01010010 补码：01010010 原码：11111111 反码：10000000 补码：10000001 原码：11010001==表示时不应该有小数点 反码：10101110 补码：10101111 原码：10000001 反码：11111110 补码：11111111 原码：00000000（或10000000） 反码：00000000（或11111111） 补码：00000000 1.绪论 1．将下列复杂度由小到大重新排序： A．2n B．n! C．n5D．10 000 E．n*log2 (n) 【答】10 000< n*log2(n)< n5< 2n < n! 2．将下列复杂度由小到大重新排序： A．n*log2(n) B．n + n2 + n3C．24D．n0.5 【答】24< n0.5< n*log2 (n) < n + n2 + n3 3．用大“O”表示法描述下列复杂度： A．5n5/2 + n2/5 B．6*log2(n) + 9n C．3n4+ n* log2(n) D．5n2 + n3/2 【答】A：O (n5/2) B：O (n) C：O (n4) D：O (n2) 4．按照增长率从低到高的顺序排列以下表达式：4n2 , log3n, 3n , 20n , 2000 , log2n , n2/3。又n！应排在第几位？ 【答】按照增长率从低到高依次为：2000, log3n, log2n , n2/3 , 20n , 4n2 , 3n。 n！的增长率比它们中的每一个都要大，应排在最后一位。 5. 计算下列程序片断的时间代价： int i=1; while(i<=n) { printf(“i=%d\n”,i); i=i+1; } 【答】循环控制变量i从1增加到n，循环体执行n次，第一句i的初始化执行次数为1，第二句执行n次，循环体中第一句printf执行n次，第二句i从1循环到n，共执行n次。所以该程序段总的时间代价为： T(n) = 1 + n + 2n = 3n+ 1 = O(n) 6. 计算下列程序片断的时间代价： int i=1; while(i<=n) { int j=1; while(j<=n) { int k=1; 第一章 填空： 计算机的发展趋势：巨型化微型化网络化智能化多媒体化 阶段：电子管计算机晶体计算机集成电路计算机大规模计算机 用途：巨型机大型机小型机工作站微型机 特点：快速运算计算精度高存储功能强逻辑判断能力自动运行程序硬件设备：CPU 总线系统内存储器外存储器输入输出设备 编码：国标码内码外码汉字字形码 选择： 1-6 C D B D A C 判断： XXVXX（X错V对） 第二章 填空： 快捷键：WIN+D 按住：shift 按住:ctrl Ctrl+Z 左右上下综合 书写顺序取大优先兼顾直观能连不交，能交不连 选择: 1-6 A D B B D B 判断： VVXXV 第三章 填空： 菜单元工具栏工作区状态栏 直看正文的宽度设定左右的界限直行缩进位置制表符位置 左对齐右对齐两端对齐 横排竖排 亮度对比度灰度 选择： 1-5 A B B D C 判断： XVVV 第四章 填空： 输入数据编辑数据设置数据格式排序数据筛选数据 25665536 列宽标准列宽 单元格格式 等于参数 图表对象 选择： 1-6 A B A C C A 判断： XVVXVV 第五章 填空： 远程中断联机计算机网络计算机网络互联 服务器模式对等模式 环形网星型网总线网混合型 TCP/IP协议IPX/SPX协议NetBEUI协议AppleTalk协议 A类B类C类 选择： CADCD 判断： XXVV 第六章 选择：D B A C A A 第八章 填空： 多媒体硬件软件 多媒体立机多媒体输入设备多媒体存储设备多媒体输出设备功能键操控控动设备信息采集信息回收 熵编码信息源码 选择： B B A 判断： VXV 算法与数据结构习题答案.txt机会就像秃子头上一根毛，你抓住就抓住了，抓不住就没了。我和你说了10分钟的话，但却没有和你产生任何争论。那么，我们之间一定有个人变得虚伪无比！过错是短暂的遗憾，错过是永远的遗憾。相遇是缘，相知是份，相爱是约定，相守才是真爱。3.3 在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素? 答： 在等概率情况下，顺序表中插入一个结点需平均移动n/2个结点。删除一个结点需平均移动(n-1)/2个结点。具体的移动次数取决于顺序表的长度n以及需插入或删除的位置i。i 越接近n则所需移动的结点数越少。 3.12 已知由单链表表示的线性表中，含有三类字符的数据元素(如：字母字符、数字字符和其它字符)，试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。 解： 要解决这样的问题，只要新建三个头结点，然后在原来的单链表中依次查询，找到一类字符结点时，就摘下此结点链接到相应头结点指明的新链表中就是了。 算法如下： //设已建立三个带头结点的空循环链表A,B,C且A、B、C分别是尾指针. void DivideList( LinkList L, LinkList A, LinkList B, LinkList C) { ListNode *p=L->next, *q; while ( p ) { if ( p->data>='a' &&p->data<='z'|| p->data>='A' &&p->data<='Z') { q=p->next; p=p->next;//指向下一结点 q->next=A->next;//将字母结点链到A表中 A->next=q;A=q; } else if( p->data>='0' && p->data<='9') { // 分出数字结点 q=p->next; p=p->next;//指向下一结点 q->next=B->next;//将数字结点链到B表中 B->next=q;B=q; } else { //分出其他字符结点 q=p->next; p=p->next;//指向下一结点 q->next=C->next;//将其他结点链到C表中 C->next=q;C=q; } } }//结束计算方法——第二章——课后习题答案刘师少
大学计算机基础教程课后习题答案大一
计算机算法试题含答案1
算法设计与分析课后部分习题答案
《大学计算机基础》第五版第1-4章课后习题答案
《计算机算法基础》第三版,课后习题答案
《数据结构与算法》课后习题答案(课件)
计算方法课后题答案之习题二
计算机基础课后问答题答案
算法和数据结构C语言版课后习题集答案解析(机械工业出版社)第34章习题集参考答案解析
计算机基础练习题附答案
计算机算法设计与分析习题及答案
数据结构课程 课后习题答案
数值计算方法习题答案(绪论,习题1,习题2)
大学计算机基础课后习题答案
最新算法与数据结构C语言习题参考答案1-5章讲解学习
计算机应用基础课后习题答案(第三版)
算法与数据结构习题答案
- 计算机算法设计与分析(第三版)课后习题答案详解
- 算法题计算机算法设计与分析期末试题4套(含答案)
- 计算机算法设计与分析课后题答案(第三版)王晓东
- 计算机算法课后题答案
- 计算机算法试题含答案1
- 计算机算法设计与分析》习题及答案
- 最新计算机软件技术基础(第三版)习题答案
- 计算机算法试题含答案
- 《计算机算法基础》第三版_课后习题答案
- 计算机算法分析设计 复习题
- 计算机算法设计与分析习题及答案
- 计算机算法设计与分析第四版课后答案
- 计算机算法设计与分析课后题答案(第三版)王晓东
- 计算机算法设计分析试题及答案
- 计算机算法试题(含答案)
- 计算机算法基础第三版_课后习题答案
- 《计算机算法基础》课后答案
- 计算机算法试题(含答案)
- 计算机算法设计与分析习题及答案
- 计算机算法试题含答案