问题 单项选择题

对长度为n的线性表排序,在最坏情况下,比较次数不是n(n-1)/2的排序方法是

A.快速排序

B.冒泡排序

C.直接插入排序

D.堆排序

答案

参考答案:D

解析: 主要考察各种排序方法的掌握情况。直接插入排序:每次将一个待排序的数据元素,插入到前面已经排好序的数列中的适当位置,使数列依然有序;直到待排序数据元素全部插入完为止。冒泡排序:两两比较待排序数据元素的大小,发现两个数据元素的次序相反时即进行交换,直到没有反序的数据元素为止。快速排序:在当前无序区R[1.. H]中任取一个数据元素作为比较的“基准”,用此基准将当前无序区划分为左右两个较小的无序区:R[1.. I-1]和R[I+1.. H],且左边的无序子区中数据元素均小于等于基准元素,右边的无序子区中数据元素均大于等于基准元素,而基准则位于最终排序的位置上,即R[1.. I-1]≤X. Key≤R[I+1.. H](1≤I≤H),当R[I.. I-1)和R[I+1.. H]均非空时,分别对它们进行上述的划分过程,直至所有无序子区中的数据元素均已排序为止。堆排序:堆排序是一树形选择排序,在排序过程中,将R[1.. N]看成是一颗完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。

阅读理解与欣赏

阅读下面的文字

中国古代的“驻京办事处”——进奏院

李 永

  进奏院是唐后期地方藩镇设置在当时京城长安的驻京办事机构,最早出现于唐代宗大历十二年(777年)。进奏院之前,早在战国秦汉时代,其实就已经有了“驻京办事处”的影子——邸。但邸仅仅是地方官员进京时的起居之地,还没有固定的驻京代表来主持这些邸的日常工作,尚不具备联系中央与地方的职能,因此它还只能算作是“驻京办事处”的雏形。进奏院和邸的不同之处在于,其设置之初就有地方指派的进奏官主持日常工作。进奏官常驻京城,作为藩镇的代表同朝廷进行沟通、交流,处理地方与中央之间的各种事务。驻京机构——进奏院,驻京代表——进奏官,两者的结合以及进奏院在信息的上传下达过程中发挥的中介作用,使其具备了现代地方政府驻京办事处的基本性质。唐代进奏院集中分布在长安东市周边的几个坊内,其中尤以最为繁华的崇仁坊和平康坊为多。而且现今学者的研究成果表明,随着大明宫和兴庆宫的修建,以东市为中心,朱雀街东形成了贵族和官僚集中居住区。这就使以东市为中心的一片区域,成为唐后期长安城各种信息,尤其是政治信息的集散地。所以,进奏院选址于此,不仅便于进奏官的日常生活,而且便于他们搜集情报,结交权贵,开展日常工作。

  进奏院不仅可以为来京的地方官员提供住宿之处等各种方便,而且由于唐后期中央式微,地方藩镇势力崛起,进奏官在京城也会狐假虎威,代表地方政府同中央斡旋,通过各种渠道争取自己的最大利益。尤其是势力较强的藩镇,其进奏官会更加有恃无恐。《资治通鉴》卷二四四载:文宗太和七年(833年),朝廷加卢龙节度使杨志诚为检校吏部尚书,杨志诚的进奏官徐迪便用略带威胁的口吻向朝廷抗议:“军中不识朝廷之制,唯知尚书改仆射为迁,不知工部改吏部为美,敕使往,恐不得出。”这是卢龙镇的进奏官公然地和朝廷谈条件、邀利益。在当时藩镇势力强大的背景下,进奏官“作为藩帅的心腹,主要还是作为藩镇对付朝廷的工具”而存在,唐王朝对进奏官进行有效管理是有一定难度的。当然,若遇地方发动叛乱或拒命不遵,唐王朝也会拿这些地方政府代表——进奏官开刀,并加强对其进奏院的监管。文宗太和元年,横海节度副使李同捷擅据沧、景,拒命不遵,朝廷便下诏:“(其)进奏官皇测等七人,并锢身分配羊、阆等州。”进奏院除了作为地方政府同中央博弈的工具存在而外,更重要的是作为两者之间信息交流、往复的渠道而存在。安史之乱后,在唐前期中央与地方交流过程中发挥过重要作用的朝集制度废止,当时社会迫切需要一个沟通上下的新渠道。进奏院就是在这样的背景下出现在历史舞台上的。当时的进奏官通过进奏院状报向藩镇长官传达其在京城搜集到的各种信息。这些信息内容广泛,包括官员任免、朝廷及他镇的政治军事动向等等,其中还包括一些通过非常规手段刺探而来的信息情报。因为进奏院向地方传达信息的速度较快,所以朝廷也会通过进奏院向藩镇长官下达相关文书、传达政令。地方奏章、上贡、进奉等也以进奏院为中转站上传中央。中央与地方之间以进奏院为媒介,形成一个信息往来的通道,发挥了联系上下、沟通中央与地方的重要作用。

                                   (选自2010年5月11日《光明日报》,有删节)

小题1:下列关于“进奏院”的解说,不正确的一项是

A.进奏院是地方藩镇设在京城的办事机构,基本职能是代表地方藩镇与朝廷进行沟通,同时也相机与中央政府斡旋,为藩镇谋取利益。

B.唐代后期的长安,随着大明宫和兴庆宫的修建,东市成为政治信息的集散地,进奏

院也应运而生。

C.唐朝地方潘镇设驻京代表来主持进奏院的日常工作,进奏院多分布在京城繁华地

带,他们代表地方,搜集情报,结交权贵,开展日常工作。

D.进奏院是联结地方与朝廷的渠道和中介,唐代前期中央与地方之间交流的朝集制度废止是其产生的一个重要原因。

小题2:下列对进奏院与朝廷的关系及其原因的表述,正确的一项是

A.进奏院设置以后,安排专门的进奏官来主持进奏院的工作,进奏官代表朝廷与藩镇进行沟通、交流并处理两者间的各种事物。

B.两者属于上下级关系,可是地方敢于同中央叫板,除了中央式微的原因外,也有一些不便启齿的原因。

C.地方藩镇势力崛起,势力强大的藩镇威胁朝廷,甚至拒命不尊,朝廷拿进奏官开刀,“锢身分配”,两者成为对等的政治实体。

D.两者间沟通交流,频繁来往;地方给中央上贡,中央也施予地方恩惠。“礼尚往来”的规则在主导着双方的来往。小题3:下列说法不符合文意的一项是

A.战国秦汉时代出现的“邸”,还没有固定的地方驻京代表主持工作,仅仅是地方官员进京时的起居之地,“邸”是进奏院的雏形。

B.进奏院大多分布在东市的崇仁坊和平康坊,主要因为此处是贵族和官僚的集中居住地,能够搜集到各种有效信息,便于开展工作。

C.进奏官张扬跋扈,有恃无恐,通过各种渠道,为地方藩镇谋取利益;其最根本的原因是地方藩镇势力强大。

D.中央与地方之间的很多来往,如官员任免、中央的军事动向、地方奏章、上贡、进奉等等,都可以通过进奏院来完成。

单项选择题