 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
数据结构与算法（C语言版） 严蔚敏 吴伟民编著
下载积分：0
内容提示：数据结构与算法（C语言版） 严蔚敏 吴伟民编著
文档格式：PPT|
浏览次数：7|
上传日期： 15:42:49|
文档星级：
全文阅读已结束，此文档免费下载
下载此文档
该用户还上传了这些文档
数据结构与算法（C语言版） 严蔚敏 吴伟民编著
关注微信公众号君，已阅读到文档的结尾了呢~~
广告剩余8秒
文档加载中
数据结构原理与分析,数据结构原理与分析,数据结构和微机原理,数据结构原理,数据结构与算法分析,数据结构与算法分析 c,数据结构与算法分析80,数据结构和算法分析,redis数据结构分析,数据结构成绩分析问题
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
数据结构原理与分析
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer--144.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
数据结构课程设计-矩阵的加、减、乘法运算的实现
下载积分：1500
内容提示：数据结构课程设计-矩阵的加、减、乘法运算的实现
文档格式：DOC|
浏览次数：290|
上传日期： 01:41:29|
文档星级：
全文阅读已结束，如果下载本文需要使用
 1500 积分
下载此文档
该用户还上传了这些文档
数据结构课程设计-矩阵的加、减、乘法运算的实现
关注微信公众号当前位置： >>
数据结构例题与答案
1 章 绪论 一、选择题 1. 算法的计算量的大小称为计算的( )。 【北京邮 电大学 2000 二、3 (20/8 分)】 a．效率 b. 复杂性 c. 现实性 d. 难度 2. 算 法 的时 间 复 杂度 取决 于 ( )【 中 科院 计 算 所 1998 二、1 (2 分)】 a． 问题的规模 b. 待处理数据的初态 c. a 和 b 3.计算机算法指的是(1)，它必须具备(2) 这三个 特性。 (1) a．计算方法 b. 排序方法 c. 解决问题的步骤序列 d. 调度方法 (2) a．可执行性、可移植性、可扩充性 b. 可执行性、确定性、有穷性 c. 确定性、有穷性、稳定性 d. 易读性、稳定性、安全性 【南京理工大学 1999 一、1(2 分) 【武汉交通科 技大学 1996 一、1( 4 分)】 4．一个算法应该是( )。 【中山大学 1998 二、 1(2 分)】 a．程序 b．问题求解步骤的描述 c．要满足五个基本特性 d．a 和 c. 5. 下面关于算法说法错误的是( )【南京理工大 学 2000 一、1(1.5 分)】 a．算法最终必须由计算机程序实现 b.为解决某问题的算法同为该问题编写的程序含 义是相同的 c.算法的可行性是指指令不能有二义性 d. 以上几个都是错误的6. 下 面 说 法 错 误 的 是 ( ) 【 南 京 理 工 大 学 2000 一、2 (1.5 分)】 (1)算法原地工作的含义是指不需要任何额外的 辅助空间 (2)在相同的规模 n 下， 复杂度 o(n)的算法在时间 上总是优于复杂度 o(2n)的算法 (3)所谓时间复杂度是指最坏情况下， 估算算法执 行时间的一个上界 (4)同一个算法，实现语言的级别越高，执行效率 就越低 a．(1) b.(1),(2) c.(1),(4) d.(3) 7． 从逻辑上可以把数据结构分为( )两大类。 武 【 汉交通科技大学 1996 一 、4(2 分)】 a．动态结构、静态结构 b．顺序结构、链式结构 c．线性结构、非线性结构 d．初等结构、构造型结构 8． 以下与数据的存储结构无关的术语是( )。 北 【 方交通大学 2000 二、1(2 分)】 a．循环队列 b. 链表 c. 哈希表 d. 栈 9． 以下数据结构中， 哪一个是线性结构( )？ 【北 方交通大学 2001 一、1(2 分)】 a．广义表 b. 二叉树 c. 稀疏矩阵 d. 串 10．以下那一个术语与数据的存储结构无关？ ( )【北方交通大学 2001 一、2(2 分)】 a． 栈 b. 哈希表 c. 线索树 d. 双向链表 11．在下面的程序段中，对 x 的赋值语句的频度 为( )【北京工商大学 2001 一、10(3 分)】 for i:=1 to n dofor j:=1 to n do x:=x+1; a．o(2n) b． o(n) c． o(n2) d． o(log2n) 12．程序段 for i:=n-1 downto 1 do for j:=1 to i do if a[j]&a[j+1] then a[j]与 a[j+1]对换； 其中 n 为正整数， 则最后一行的语句频度在最坏 情况下是( ) a. o(n) b. o(nlogn) c. o(n3) d. o(n2) 【南京 理工大学 1998 一、1(2 分)】 二、判断题 1. 数据元素是数据的最小单位。( ) 【北京邮电大学 1998 一、1(2 分)】 【青岛大 学 2000 一、1 (1 分)】 【上海交通大学 1998 一、1】 【山东师范大 学 2001 一、1 (2 分)】 2. 记录是数据处理的最小单位。 ( ) 【上海海运 学院 1998 一、5(1 分)】 3. 数据的逻辑结构是指数据的各数据项之间的 逻辑关系； ) 北京邮电大学 2002 一、 分)】 ( 【 1(1 4．算法的优劣与算法描述语言无关，但与所用 计算机有关。( ) 【大连海事大学 2001 一、10(1 分)】 5．健壮的算法不会因非法的输入数据而出现莫 名其妙的状态。( ) 【大连海事大学 2001 一、11(1 分)】 6．算法可以用不同的语言描述，如果用 c 语言 或 pascal 语言等高级语言来描述，则算法实际上就是程序了。( )【西安交通大学 1996 二、7(3 分)】 7．程序一定是算法。( )【燕山大学 1998 二、 2(2 分)并改错】 8．数据的物理结构是指数据在计算机内的实际 存储形式。 ) 山东师范大学 2001 一、 分)】 ( 【 2(2 9. 数据结构的抽象操作的定义与具体实现有关。 ( )【华南理工大学 2002 一、1(1 分)】 10. 在顺序存储结构中，有时也存储数据结构中 元素之间的关系。( ) 【华南理工大学 2002 一、2 (1 分)】 11. 顺序存储方式的优点是存储密度大，且插入、 删除运算效率高。( ) 【上海海运学院 1999 一、1(1 分)】 12. 数据结构的基本操作的设置的最重要的准则 是，实现应用程序与存储结构的独立。( ) 【华南理工大学 2002 一、5(1 分)】 13. 数据的逻辑结构说明数据元素之间的顺序关 系,它依赖于计算机的储存结构. ( ) 【上海海运学院 1998 一、1(1 分)】 三、填空 1．数据的物理结构包括 的表示和 的表 示。 【燕山大学 1998 一、1(2 分)】 2. 对于给定的 n 个元素,可以构造出的逻辑结构 有 (1) ， (2) ， (3) ，__(4)_四种。 【中科院计算所 1999 二、1(4 分)】 3．数据的逻辑结构是指 。 【北京邮电大 学 2001 二、1(2 分)】 4． 一个数据结构在计算机中 称为存储结构。【华中理工大学 2000 一、1(1 分)】 5．抽象数据类型的定义仅取决于它的一组 __(1)_，而与_(2)_无关，即不论其内部结构如何 变化， 只要它的_(3)_不变， 都不影响其外部使用。 【山东大学 2001 三、3(2 分)】 6．数据结构中评价算法的两个重要指标 是 【北京理工大学 2001 七、1(2 分)】 7. 数据结构是研讨数据的_(1)_和_(2)_，以及它 们之间的相互关系，并对与这种结构定义相应的 _(3)_，设计出相应的(4)_。 【西安电子科技大 学 1998 二、2(3 分)】 8． 一个算法具有 5 个特性: (1) 、 (2) 、 (3) ，有 零个或多个输入、有一个或多个输出。 【华中理工大学 2000 一、2(5 分)】 【燕山大 学 1998 一、2(5 分)】 9．已知如下程序段 for i:= n downto 1 do {语句 1} begin x:=x+1； {语句 2} for j:=n downto i do {语句 3} y:=y+1; {语句 4} end； 语句 1 执行的频度为 (1) ；语句 2 执行的频度 为 (2) ；语句 3 执行的频度为 (3) ；语句 4 执行 的频度为 (4) 。 北方交通大学 1999 二、 分)】 【 4(5 10．在下面的程序段中，对ｘ的赋值语句的频度 为______(表示为 n 的函数) for i：＝１ to n do for j：＝１ to i dofor k：＝1 to j do ｘ：＝ｘ＋delta； 【北京工业大学 1999 一、6(2 分)】 11.下面程序段中带下划线的语句的执行次数的 数量级是： 【合肥工业大学 1999 三、1(2 分)】 i ： =1 ； while i&N DO I ： =I*2;   12. 下面程序段中带下划线的语句的执行次数的 数量级是( )。 【合肥工业大学 2000 三、 分)】 1(2 i:=1; while i&N BEGIN  FOR& NBSP;J:=1 TO N DO&N BSP;X:=X+1;I:=I*2  END ；   13. 下面程序段中带有下划线的语句的执行次数 的数量级是( ) 【合肥工业大学 2001 三、1(2 分)】 i：=n*n while i&&1 do i:=i div 2; 14. 计算机执行下面的语句时，语句 s 的执行次 数为 _______ 。 【南京理工大学 2000 二、1(1.5 分)】 for(i=l；i&N-L；I++)  for(j=n;j&=i;j--) 15. 下面程序段的时间复杂度为________。 (n&1) sum=1； for (i=0;sum&N;I++) SUM+=1;&NBS P;   【 南 京 理 工 大 学  2001 二、1(2 分)】 16．设 m.n 均为自然数，m 可表示为一些不超过 n 的自然数之和，f(m,n)为这种表示方式的数目。 例 f(5,3)=5， 5 种表示方式： 有 3+2， 3+1+1， 2+2+1， 2+1+1+1，1+1+1+1+1。 ①以下是该函数的程序段，请将未完成的部分填 入，使之完整 int f(m,n) int m,n; { if(m==1) return (1) ; if(n==1){ return (2) ;} if(m&N)   {return f(m,m);} if (m==n) {return 1+ (3) ;} return f(m.n-1)+f(m-n, (4) ); } ② 执 行 程 序 ， f(6,4)= 。 中科院软件 【 所 1997 二、1 (9 分)】 17. 在有 n 个选手参加的单循环赛中，总共将进 行______场比赛。 【合肥工业大学 1999 三、8(2 分)】 四、应用题 1. 数据结构是一门研究什么内容的学科？ 【燕山 大学 1999 二、1 (4 分)】 2. 数据元素之间的关系在计算机中有几种表示 方法？各有什么特点？【燕山大学 1999 二、2(4 分)】3. 数据类型和抽象数据类型是如何定义的。 二者 有何相同和不同之处， 抽象数据类型的主要特点 是 什么？使 用抽象 数据类 型的主要 好处是 什 么？【北京邮电大学 1994 一(8 分)】 4. 回答问题(每题 2 分) 【山东工业大学 1997 一 (8 分)】 (1)在数据结构课程中，数据的逻辑结构，数据的 存 储结构及 数据的 运算之 间存在着 怎样的 关 系？ (2)若逻辑结构相同但存储结构不同， 则为不同的 数据结构。这样的说法对吗？举例说明之。 (3)在给定的逻辑结构及其存储表示上可以定义 不同的运算集合，从而得到不同的数据结构。这 样说法对吗？举例说明之。 (4)评价各种不同数据结构的标准是什么？ 5．评价一个好的算法，您是从哪几方面来考虑 的？ 【大连海事大学 1996 二、3 (2 分)】 【中山大 学 1998 三、1 (5 分)】 6．解释和比较以下各组概念【华南师范大 学 2000 一(10 分)】 (1)抽象数据类型及数据类型 (2)数据结构、逻辑 结构、存储结构 (3)抽象数据类型【哈尔滨工业大学 2000 一、1(3 分)】 (4)算法的时间复杂性 【河海大学 1998 一、2(3 分)】 (5)算法【吉林工业大学 1999 一、1(2 分)】 (6)频度【吉林工业大学 1999 一、2(2 分)】7. 根据数据元素之间的逻辑关系， 一般有哪几类 基本的数据结构？ 【北京科技大学 1998 一、1】 【同济大学 1998】 8．对于一个数据结构，一般包括哪三个方面的 讨论？【北京科技大学 1999 一、1(2 分)】 9. 当你为解决某一问题而选择数据结构时， 应从 哪些方面考虑？ 【西安电子北京科技大学 2000】 10. 若将数据结构定义为一个二元组(d， r),说明符 号 d，r 应分别表示什么？ 【北京科技大学 2001 一、1(2 分)】 11．数据结构与数据类型有什么区别？【哈尔滨 工业大学 2001 三、1(3 分)】 12． 数据的存储结构由哪四种基本的存储方法实 现？【山东科技大学 2001 一、1(4 分)】 13．若有 100 个学生，每个学生有学号，姓名， 平均成绩，采用什么样的数据结构最方便，写出 这些结构？ 【山东师范大学 1996 二、2(2 分)】 14. 运算是数据结构的一个重要方面。试举一例， 说明两个数据结构的逻辑结构和存储方式完全 相同，只是对于运算的定义不同。因而两个结构 具有显著不同的特性，是两个不同的结构。 【北京大学 1998 一、1(5 分)】 15. 在编制管理通讯录的程序时, 什么样的数据 结构合适? 为什么?【 长沙铁道学院 1998 四、 3(6 分)】 16. 试举一例，说明对相同的逻辑结构,同一种运 算在不同的存储方式下实现， 其运算效率不同。 【北京理工大学 2000 三、1(4.5 分)】17. 有实现同一功能的两个算法 a1 和 a2，其中 a1 的时间复杂度为 tl=o(2n)，a2 的时间复杂度为 t2=o(n2)，仅就时间复杂度而言，请具体分析这 两个算法哪一个好。 【北京航空航天大学 2000 二 (10 分)】 18．设计一数据结构，用来表示某一银行储户的 基本信息：账号、 姓名、 开户年月日、 储蓄类型、 存入累加数、利息、帐面总数。 浙江大 【 学 1994 一 、3(5 分)】 19. 写出下面算法中带标号语句的频度。 type ar=array[1..n] procedure perm ( a: k, n: integer); var x: i: begin (1)if k=n then begin (2)for i:=1 to n do (3)write (a[i]); end else begin (4) for i:=k to n do (5)a[i]:=a[i]+i*i; (6) perm (a, k+1, n); 设 k 的初值等于 1。 【北京邮电大学 1997 二(10 分)】 20. 分析下面程序段中循环语句的执行次数。i:=0;s:=0;n:=100; repeat i:=i+1; s:=s+10*i; until not((i&N) AND (S&N));&NB SP; 【北京邮电大学 1998 四、1(5 分)】 25．有下列运行时间函数： (1)t1 (n)=1000; (2)t2(n)=n2+1000n; (3)t3(n)=3 n3+100n2+n+1; 分别写出相应的大 o 表示的运算时间。 【吉林工业大学 1999 二(12 分)】 26. 试给出下面两个算法的运算时间。 (1) for i←1 to n do x ← x+1 end (2) for i← 1 to n do for j←1 to n do x← x+1 end end 【中科院自动化研究所 1995 二、2 (6 分)】 27. 斐波那契数列 fn 定义如下 f0=0， fl=1， fn=fn-1+fn-2, n=2,3... 请就此斐波那契数列，回答下列问题。 (1) (7 分) 在递归计算 fn 的时候，需要对较小 的 fn-1，fn-2，?, fl, f0 精确计算多少次? (2) (5 分) 如果用大 o 表示法， 试给出递归计算 fn 时递归函数的时间复杂度录多少?【清华大学 2000 二(12 分)】 28．将下列函数，按它们在 n→∝时的无穷大阶 数，从小到大排序。 n, n-n3+7n5, nlogn, 2n/2, n3, logn, n1/2+logn, (3 /2)n, ,n!, n2+logn 【中科院计算所 1995 】 第 2 章 线性表 一 选择题 1．下述哪一条是顺序存储结构的优点？( )【北 方交通大学 2001 一、4(2 分)】 a．存储密度大 b．插入运算方便 c．删除运算 方便 d． 可方便地用于各种逻辑结构的存储表示 2． 下面关于线性表的叙述中， 错误的是哪一个？ ( )【北方交通大学 2001 一、14(2 分)】 a．线性表采用顺序存储，必须占用一片连续的 存储单元。 b．线性表采用顺序存储，便于进行插入和删除 操作。 c．线性表采用链接存储，不必占用一片连续的 存储单元。 d．线性表采用链接存储，便于插入和删除操作。 3． 线性表是具有 n 个( )的有限序列(n&0)。 【清 华大学 1998 一、4(2 分)】 a．表元素 b．字符 c．数据元素 d．数据 项 e．信息项 4．若某线性表最常用的操作是存取任一指定序 号的元素和在最后进行插入和删除运算，则利用 ( )存储方式最节省时间。 哈尔滨工业大 【 学 2001 二、1(2 分)】a．顺序表 表元编号 1 2 3 4 5 6b．双链表 c．带头结点的双循 货号 数量 表元间联 系 618 40 5 205 2 1 103 15 4 501 20 2 781 17 6 910 24 3环链表 d．单循环链表 5．某线性表中最常用的操作是在最后一个元素 之后插入一个元素和删除第一个元素，则采用 ( )存储方式最节省运算时间。 南开大 【 学 2000 一、3】 a． 单链表 b． 仅有头指针的单循环链表 c． 双 链表 d．仅有尾指针的单循环链表 表元间联 系 1 618 40 2 表元编号 货号 数量 表元间联 2 205 2 3 系4 3 103 15 618 40 41 501 20 55 2 205 2 5 781 17 61 3 103 15 6 910 24 04 4 501 20 0 6．设一个链表最常用的操作是在末尾插入结点 5 781 17 和删除尾结点，则选用( )最节省时间。 6 a. 单链表 b.单循环链表 c. 带尾指针的单循环 6 910 24 3 表元编号 货号 数量链表 d.带头结点的双循环链表 【合肥工业大学 2000 一、1(2 分)】 7．若某表最常用的操作是在最后一个结点之后 插入一个结点或删除最后一个结点。则采用( ) 存储方式最节省运算时间。 北京理工大 【 学 2000 一、1(2 分)】 a． 单链表 b． 双链表 c． 单循环链表 d． 带 头结点的双循环链表 8. 静态链表中指针表示的是( ). 【北京理工大 学 2001 六、2(2 分)】 a． 内存地址 b．数组下标 c．下一元素地 址 d．左、右孩子地址 9. 链表不具有的特点是( ) 【福州大学 1998 一、 8 (2 分)】 a．插入、删除不需要移动元素 b．可随机访问 任一元素 c．不必事先估计存储空间 d．所需空间与线性 长度成正比 10. 下面的叙述不正确的是( )【南京理工大 学 1996 一、10(2 分)】a． 线性表在链式存储时， 查找第 i 个元素的时间 同 i 的值成正比 b. 线性表在链式存储时，查找第 i 个元素的时 间同 i 的值无关 c. 线性表在顺序存储时，查找第 i 个元素的时间 同 i 的值成正比 d. 线性表在顺序存储时，查找第 i 个元素的时间 同 i 的值无关 11. 线性表的表元存储方式有((1))和链接两种。 试 指出下列各表中使用的是何种存储方式：表 1 是 ((2))存储方式； 2 是((3))存储方式； 3 是((4)) 表 表 存储方式；表 4 是((5))存储方式。表左的 s 指向 起 始 表 元。 表元编号货号数量表元间联系表元编号货号数量表元间联系表2表元编号货号数量表元间联系表3表元编号货号数量表元间联系 表元编号 货号 数量 表元间 联 系 1 2 5 2 1 0 4 6 0 3 6 1 3 51 2 3 4 5 6618 205 103 501 781 91040 2 15 20 17 24表4供选择的答案：a.连续 b.单向链接 c.双向链接 d.不连接 e.循 环链接 f.树状 g.网状 h.随机 i.顺序 j.顺序循环 【上海海运学院 1995 二、1(5 分)】 16．非空的循环单链表 head 的尾结点 p↑满足 ( )。 【武汉大学 2000 二、10】 a ． p ↑ .link=head b ． p ↑.link=nil c．p=nil d．p= head 17．循环链表 h 的尾结点 p 的特点是( )。 【中山 大学 1998 二、2(2 分)】 a ． p^.next:=h b ． p^.next:= h^.next c ．p:=h d．p:=h^.next 18．在一个以 h 为头的单循环链中，p 指针指向 链尾的条件是()【南京理工大学 1998 一、15(2 分)】 a. p ＾ .next=h b. p ＾ .next=nil c. p ＾ .next. ＾ next=h d. p＾.data=-1 19．完成在双循环链表结点 p 之后插入 s 的操作 是( )； 【北方交通大学 1999 一、4(3 分)】 a． p^.next:= s^.priou:=p; p^.next^.priou:= s^. next:=p^. b． p^.next^.priou:=s; p^.next:=s; s^.priou:=p; s^.n ext:=p^. c． s^.priou:=p; s^.next:=p^. p^.next:=s; p^.ne xt^.priou:= d ． s^.priou:=p; s^.next:=p^. p^.next^.priou:= p^.next:=s; 20． 在双向循环链表中,在 p 指针所指向的结点前 插入一个指针 q 所指向的新结点,其修改指针的操作是( )。 【北京邮电大学 1998 二、2(2 分)】 注:双向链表的结点结构为(llink,data,rlink)。供选 择的答案： a． p↑.llink：=q； q↑.rlink：=p； p↑.llink ↑.rlink：=q； q↑.llink：=q； b． p↑.llink： p↑.llink↑.rlink： ； =q； =q q↑.rlink： = p； q↑.llink:=p↑.llink； c．q↑.rlink： =p；q↑.llink： =p↑.llink；p↑.llink ↑.rlink：=q; p↑.llink：=q; d． q↑.llink:=p↑.llink；q↑.rlink:=p； p↑.llink： =q；p↑.llink：=q；(编者按：原题如此) 21． 在非空双向循环链表中 q 所指的结点前插入 一个由 p 所指的链结点的过程依次为: rlink(p) ← llink(p) ← llink(q); llink(q) ← ( ) a．rlink(q) ← p b．rlink(llink(q)) ← p c．rlink(lli nk(p)) ← p d．rlink(rlink(p)) ← p 【北京航空航天大学 2000 一、1(2 分)】 22． 双向链表中有两个指针域，llink 和 rlink， 分别指回前驱及后继， p 指向链表中的一个结 设 点，q 指向一待插入结点，现要求在 p 前插入 q， 则正确的插入为( )【南京理工大学 1996 一、1(2 分)】 a. p ＾ .llink:=q; q ＾ .rlink:=p; p ＾ .llink ＾.rlink:=q; q^.llink:=p^. b. q ＾ .llink:=p^. p ＾ .llink^.rlink:=q; q ＾.rlink:=p; p^.llink:=q^. c. q^.rlink:=p; p^.rlink:=q; p^.llink^.rlink:=q; q^. rlink:=p;d. p^.llink^.rlink:=q; q^.rlink:=p; q^.llink:=p^. p^.llink:=q; 23．在双向链表指针 p 的结点前插入一个指针 q 的结点操作是( )。 【青岛大学 2000 五、2(2 分)】 a. p-&llink=q;q-&rlink=p;p-&llink-&rlink=q;q-&llin k=q； b. p-&llink=q;p-&llink-&rlink=q;q-&rlink=p;q-&llin k=p-& c. q-&rlink=p;q-&llink=p-&p-&llink-&rlink=q; p-&llink=q; d. q-&llink=p-&q-&rlink=q;p-&llink=q;p-&llin k=q; 24．在单链表指针为 p 的结点之后插入指针为 s 的结点，正确的操作是：( )。 a．p-&next=s;s-&next=p-& b． s-&next=p-&p-&next=s; c．p-&next=s;p-&next=s-& d． p-&next=s-&p-&next=s; 【青岛大学 2001 五、3(2 分)】 25．对于一个头指针为 head 的带头结点的单链 表，判定该表为空表的条件是( ) a．head==null b．head→next==null c．head→ next==head d．head!=null 【北京工商大学 2001 一、5(3 分)】 26. 在双向链表存储结构中，删除 p 所指的结点 时须修改指针( )。 a． (p^.llink)^.rlink:=p^.rlink (p^.rlink)^.llink:=p ^. b． p^.llink:=(p^.llink)^.llink (p^.llink)^.rlink:=p;c ． (p^.rlink)^.llink:=p p^.rlink:=(p^.rlink)^. rlink d ． p^.rlink:=(p^.llink)^.llink p^.llink:=(p^.rlink )^. 【西安电子科技大学 1998 一、1(2 分)】 27. 双向链表中有两个指针域，llink 和 rlink 分别 指向前趋及后继，设 p 指向链表中的一个结点， 现要求删去 p 所指结点， 则正确的删除是( )(链 中结点数大于 2，p 不是第一个结点) a ． p^.llink^.rlink:=p^. p^.llink^.rlink:=p^. dispose(p); b ． dispose(p); p^.llink^.rlink:=p^. p^.llink^, rlink:=p^. c ． p^.llink^.rlink:=p^. dispose(p); p^.llink^. rlink:=p^. d． 以上 a， c 都不对。 b， 【南京理工大学 1997 一、 1(2 分)】 二、判断 1. 链表中的头结点仅起到标识的作用。( )【南 京航空航天大学 1997 一、1(1 分)】 2. 顺序存储结构的主要缺点是不利于插入或删 除操作。( )【南京航空航天大学 1997 一、2(1 分)】 3．线性表采用链表存储时，结点和结点内部的 存储空间可以是不连续的。( ) 【北京邮电大学 1998 一、2(2 分)】 4．顺序存储方式插入和删除时效率太低，因此 它不如链式存储方式好。( ) 【北京邮电大学 2002 一、2(1 分)】5. 对任何数据结构链式存储结构一定优于顺序 存储结构。( )【南京航空航天大学 1997 一、3(1 分)】 6．顺序存储方式只能用于存储线性结构。( ) 【中科院软件所 1999 六、1-2(2 分)】 【上海海运 学院 1997 一、1(1 分)】 7．集合与线性表的区别在于是否按关键字排序。 ( )【大连海事大学 2001 一、5 ( 1 分)】 8. 所谓静态链表就是一直不发生变化的链表。 ( )【合肥工业大学 2000 二、1(1 分)】 9. 线性表的特点是每个元素都有一个前驱和一 个后继。( )【合肥工业大学 2001 二、1(1 分)】 10. 取线性表的第 i 个元素的时间同 i 的大小有 关. ( )【南京理工大学 1997 二、9(2 分)】 11. 循 环 链 表 不 是 线 性 表 . ( ) 【 南 京 理 工 大 学 1998 二、1(2 分)】 12. 线性表只能用顺序存储结构实现。( )【青岛 大学 2001 四、2(1 分)】 13. 线性表就是顺序存储的表。( )【青岛大 学 2002 一、1(1 分)】 14．为了很方便的插入和删除数据，可以使用双 向链表存放数据。( ) 【上海海运学院 1995 一、1(1 分)】 【上海海运 学院 1997 一、2(1 分)】 15. 顺序存储方式的优点是存储密度大， 且插入、 删除运算效率高。( ) 【上海海运学院 1996 一、1(1 分)】 【上海 海运学院 1999 一、1(1 分)】 16. 链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中 效率高。 ( ) 【上海海运学院 1998 一、2(1 分)】 三、填空 1．当线性表的元素总数基本稳定，且很少进行 插入和删除操作， 但要求以最快的速度存取线性 表中的元素时，应采用_______存储结构。 【北方 交通大学 2001 二、4】 2．线性表 l=(a1,a2,?,an)用数组表示，假定删除 表中任一元素的概率相同，则删除一个元素平均 需要移动元素的个数是________。 【北方交通大 学 2001 二、9】 3．设单链表的结点结构为(data,next)，next 为指 针域，已知指针 px 指向单链表中 data 为 x 的结 点， 指针 py 指向 data 为 y 的新结点 , 若将结点 y 插入结点 x 之后，则需要执行以下语 句:_______； ______;【华中理工大学 2000 一、 4(2 分)】 4．在一个长度为 n 的顺序表中第 i 个元素 (1&=i&=n) 之 前 插 入 一 个元 素 时 ， 需 向 后 移动 ________个元素。 【北京工商大学 2001 二、4(4 分)】 5．在单链表中设置头结点的作用是________。 【哈尔滨工业大学 2000 二、1(1 分)】 6．对于一个具有 n 个结点的单链表，在已知的 结 点 *p 后 插 入 一 个 新 结 点 的 时 间 复 杂 度 为 ________,在给定值为 x 的结点后插入一个新结 点的时间复杂度为________。 【哈尔滨工业大 学 2001 一、1(2 分)】 7．根据线性表的链式存储结构中每一个结点包含 的 指 针 个 数 ， 将 线 性 链 表 分 成 ________ 和 _______；而又根据指针的连接方式，链表又可 分成________和________。 【西安电子科技大学 1998 二、4(3 分)】 8． 在双向循环链表中,向 p 所指的结点之后插入 指针 f 所指的结点， 其操作是_______、 _______、 _______、________。 【中国矿业大学 2000 一、 1(3 分)】 9. 在双向链表结构中， 若要求在 p 指针所指的结 点之前插入指针为 s 所指的结点，则需执行下列 语句： s^ .next:=p； s^ .prior:= ________；p^ .prior:=s； ________:=s； 【福州大学 1998 二、7 (2 分)】 10． 链接存储的特点是利用________来表示数据 元素之间的逻辑关系。 【中山大学 1998 一、1 (1 分)】 11.顺序存储结构是通过________表示元素之间 的关系的;链式存储结构是通过________表示元 素之间的关系的。 【北京理工大学 2001 七、2 (2 分)】 12. 对于双向链表,在两个结点之间插入一个新结 点需修改的指针共 ______个，单链表为_______ 个。 【南京理工大学 2000 二、2 (3 分)】 13. 循环单链表的最大优点是：________。 【福州 大学 1998 二、3 (2 分)】 14. 已知指针 p 指向单链表 l 中的某结点， 则删除 其后继结点的语句是：________【合肥工业大学 1999 三、2 (2 分)】 15. 带头结点的双循环链表 l 中只有一个元素结 点的条件是：________ 【合肥工业大学 1999 三、3 2000 三、2(2 分)】 16. 在单链表 l 中， 指针 p 所指结点有后继结点的 条件是：__ 【合肥工业大学 2001 三、3 (2 分)】 17.带头结点的双循环链表 l 为空表的条件是： ________。 【北京理工大学 2000 二、1 (2 分)】 【青岛 大学 2002 三、1 (2 分)】 18. 在单链表 p 结点之后插入 s 结点的操作是： _______。 【青岛大学 2002 三、2(2 分)】 19. 请在下列算法的横线上填入适当的语句。 【清 华大学 1994 五 (15 分)】 function inclusion(ha,hb:linklisttp): {以 ha 和 hb 为头指针的单链表分别表示有序表 a 和 b， 本算法判别表 a 是否包含在表 b 内， 若是， 则返回“true” ，否则返回“false”} begin pa:=ha^. pb:=hb^. (1) ; while(2) do if pa^.data=pb^.data then(3) else(4) ; (5) 29．已知一双向循还链表，从第二个结点至表尾 递增有序，(设 a1&X&AN)如下图(“第二个结点 至表尾”指 A1..AN  ，因篇幅所 限，编者略去图)。试编写程序，将第一个结点 删除并插入表中适当位置，使整个链表递增有序。 【南京航空航天大学 1998 八(10 分)】 30. 已知长度为 n 的线性表 a 采用顺序存储结构， 请写一时间复杂度为 0(n)、空间复杂度为 0(1)的 算法， 该算法删除线性表中所有值为 item 的数据 元素。(o(1)表示算法的辅助空间为常量)。 【北京航空航天大学 2000 五(10 分)】 31．设民航公司有一个自动预订飞机票的系统， 该系统中有一张用双重链表示的乘客表，表中结 点按乘客姓氏的字母序相链。例如，下面是张某 个时刻的乘客表。 试为该系统写出一个当任一乘 客要订票时修改乘客表的算法。 序号 data llink rlink 1 liu 6 5 2 chan 4 9 3 wang 5 7 4 bao 0 2 5 mai 1 3 6 dong 8 1 7 xi 3 0 8 deng 9 6 9 cuang 2 8 【北方交通大学 2000 六(17 分)】 32．设有一头指针为 l 的带有表头结点的非循环 双向链表，其每个结点中除有 pred(前驱指针)， data(数据)和 next(后继指针)域外，还有一个访问 频度域 freq。在链表被起用前，其值均初始化为 零。每当在链表中进行一次 locate(l,x)运算时， 令元素值为 x 的结点中 freq 域的值增 1，并使此 链表中结点保持按访问频度非增(递减)的顺序排列， 同时最近访问的结点排在频度相同的结点的 最后，以便使频繁访问的结点总是靠近表头。试 编写符合上述要求的 locate(l,x)运算的算法，该 运算为函数过程，返回找到结点的地址，类型为 指针型。 【清华大学 1997 二 (10 分)】 33．给定(已生成)一个带表头结点的单链表，设 head 为头指针，结点的结构为(data,next),data 为 整型元素， next 为指针， 试写出算法:按递增次序 输出单链表中各结点的数据元素， 并释放结点所 占的存储空间。(要求;不允许使用数组作辅助空 间)【华中理工大学 2000 八、2 (13 分)】 34．已知三个带头结点的线性链表 a、b 和 c 中 的结点均依元素值自小至大非递减排列(可能存 在两个以上值相同的结点)， 编写算法对 a 表进行 如下操作：使操作后的链表 a 中仅留下三个表中 均包含的数据元素的结点，且没有值相同的结 点，并释放所有无用结点。限定算法的时间复杂 度为 o(m+n+p)，其中 m、n 和 p 分别为三个表的 长度。 【清华大学 1995 一 (15 分)】 第 3 章 栈和队列 一 选择题 1. 对 于 栈 操 作 数 据 的 原 则 是 ( ) 。 青 岛 大 【 学 2001 五、2(2 分)】 a. 先进先出 b. 后进先出 c. 后进后出 d. 不 分顺序 2. 在作进栈运算时,应先判别栈是否( ① ),在作 退栈运算时应先判别栈是否( ② )。当栈中元素 为 n 个,作进栈运算时发生上溢,则说明该栈的最 大容量为( ③ )。为了增加内存空间的利用率和减少溢出的可能 性,由两个栈共享一片连续的内存空间时,应将两 栈的 ( ④ )分别设在这片内存空间的两端,这样, 当( ⑤ )时，才产生上溢。 ① , ② : a. 空 b. 满 c. 上 溢 d. 下 溢 ③: a. n-1 b. n c. n+1 d. n/2 ④: a. 长度 b. 深度 c. 栈顶 d. 栈底 ⑤: a. 两个栈的栈顶同时到达栈空间的中心点. b. 其中一个栈的栈顶到达栈空间的中心点. c. 两个栈的栈顶在栈空间的某一位置相遇. d. 两个栈均不空,且一个栈的栈顶到达另一 个栈的栈底. 【上海海运学院 1997 二、1(5 分)】 【上海海运学 院 1999 二、1(5 分)】 3. 一个栈的输入序列为 123?n， 若输出序列的第 一个元素是 n，输出第 i(1&=i&=n)个元素是( )。 a. 不确定 b. n-i+1 c. i d. n-i 【中山大学 1999 一、9(1 分)】 4. 若一个栈的输入序列为 1,2,3,?,n， 输出序列的 第一个元素是 i，则第 j 个输出元素是( )。 a. i-j-1 b. i-j c. j-i+1 d. 不确定的 【武汉大学 2000 二、3】 5. 若已知一个栈的入栈序列是 1,2,3,?,n， 其输出 序列为 p1,p2,p3， pn,若 pn 是 n， pi 是( )。 ?， 则 a. i b. n-i c. n-i+1 d. 不确定 【南京理工大学 2001 一、1(1.5 分)】 6. 有六个元素 6，5，4，3，2，1 的顺序进栈， 问下列哪一个不是合法的出栈序列？( )a. 5 4 3 6 1 2 b. 4 5 3 1 2 6 c. 3 4 6 5 2 1 d. 2 34156 【北方交通大学 2001 一、3(2 分)】 7. 设栈的输入序列是 1，2，3，4,则( )不可能是 其出栈序列。 【中科院计算所 2000 一、10(2 分)】 a. 1，2，4，3， b. 2，1，3，4， c. 1，4， 3，2， d. 4，3，1，2， e. 3，2，1，4， 8. 一个栈的输入序列为 1 2 3 4 5，则下列序列中 不可能是栈的输出序列的是( )。 a. 2 3 4 1 5 b. 5 4 1 3 2 c. 2 3 1 4 5 d. 1 5 432 【南开大学 2000 一、 【山东大学 2001 二、 (1 1】 4 分)】 【北京理工大学 2000 一、2(2 分)】 9. 设一个栈的输入序列是 1，2，3，4，5,则下列 序列中，是栈的合法输出序列的是( )。 a. 5 1 2 3 4 b. 4 5 1 3 2 c. 4 3 1 2 5 d. 3 2154 【合肥工业大学 2001 一、1(2 分)】 10. 某堆栈的输入序列为 a, b，c ，d,下面的四个 序列中，不可能是它的输出序列的是( )。 a. a ， c ， b ， d b. b, c ， d ， a c. c, d ， b, a d. d, c，a，b 【北京航空航天大学 2000 一、3(2 分)】 【北京邮 电大学 1999 一、3(2 分)】 11. 设 abcdef 以所给的次序进栈，若在进栈操作 时，允许退栈操作,则下面得不到的序列为( )。 a．fedcba b. bcafed c. dcefba d. cabdef 【南京理工大学 1996 一、9(2 分)】12. 设有三个元素 x，y，z 顺序进栈(进的过程中 允许出栈)，下列得不到的出栈排列是( )。 a．xyz b. yzx c. zxy d. zyx 【南京理工大学 1997 一、5(2 分)】 13. 输入序列为 abc，可以变为 cba 时，经过的栈 操作为( )【中山大学 1999 一、8(1 分)】 a. push,pop,push,pop,push,pop b. push,push,pu sh,pop,pop,pop c. push,push,pop,pop,push,pop d. push,pop,p ush,push,pop,pop 14. 若一个栈以向量 v[1..n]存储，初始栈顶指针 top 为 n+1，则下面 x 进栈的正确操作是( )。 a ． top:=top+1; v [top]:=x b. v [top]:=x; to p:=top+1 c. top:=top-1; v [top]:=x d. v [top]:=x; top: =top-1 【南京理工大学 1998 一、13(2 分)】 19. 表达式 a*(b+c)-d 的后缀表达式是( )。 【南京 理工大学 2001 一、2(1.5 分)】 a． abcd*+- b. abc+*d- c. abc*+d- d. -+*abcd 20. 表达式 3* 2^(4+2*2-6*3)-5 求值过程中当扫 描到 6 时， 对象栈和算符栈为( )， 其中^为乘幂 。 a. 3,2,4,1,1； (*^(+*- b. 3,2,8； (*^- c. 3,2,4,2,2； (*^(- d. 3,2,8；(*^(【青岛大学 2000 五、5(2 分)】 21. 设计一个判别表达式中左，右括号是否配对 出现的算法，采用( )数据结构最佳。 a．线性表的顺序存储结构 b. 队列 c. 线性 表的链式存储结构 d. 栈【西安电子科技大学 1996 一、6(2 分)】 22. 用链接方式存储的队列，在进行删除运算时 ( )。 【北方交通大学 2001 一、12(2 分)】 a. 仅修改头指针 b. 仅修改尾指针 c. 头、尾指 针都要修改 d. 头、尾指针可能都要修改 23. 用不带头结点的单链表存储队列时,其队头指 针指向队头结点,其队尾指针指向队尾结点， 则在 进行删除操作时( )。 【北京理工大学 2001 六、 3(2 分)】 a．仅修改队头指针 b. 仅修改队尾指针 c. 队头、队尾指针都要修改 d. 队头,队尾指针都 可能要修改 24. 递归过程或函数调用时，处理参数及返回地 址，要用一种称为( )的数据结构。 a ． 队 列 b ． 多 维 数 组 c．栈 d. 线性表 【福州大学 1998 一、1(2 分)】 25. 假设以数组 a[m]存放循环队列的元素,其头尾 指针分别为 front 和 rear， 则当前队列中的元素个 数为( )。 【北京工商大学 2001 一、2(3 分)】 a．(rear-front+m)%m b．rear-front+1 c．(fr ont-rear+m)%m d．(rear-front)%m 26. 循环队列 a[0..m-1]存放其元素值，用 front 和 rear 分别表示队头和队尾，则当前队列中的元素 数是( )。 【南京理工大学 2001 一、5(1.5 分)】 a. (rear-front+m)%m b. rear-front+1 c. rear-fr ont-1 d. rear-front 27. 循环队列存储在数组 a[0..m]中，则入队时的 操作为( )。 【中山大学 1999 一、6(1 分)】a. rear=rear+1 b. rear=(rear+1) mod (m-1) c. rear=(rear+1) mod m d. rear=(rear+1)mod( m+1) 28. 若用一个大小为 6 的数组来实现循环队列， 且当前 rear 和 front 的值分别为 0 和 3， 当从队列 中删除一个元素， 再加入两个元素后， 和 front rear 的值分别为多少？( )【浙江大学 1999 四、1(4 分)】 a. 1 和 5 b. 2 和 4 c. 4 和 2 d. 5 和 1 29. 已知输入序列为 abcd 经过输出受限的双向队 列后能得到的输出序列有( )。 a. dacb b. cadb c. dbca d. bdac e. 以 上答案都不对 【西安交通大学 1996 三、3 (3 分)】 30. 若以 1234 作为双端队列的输入序列，则既不 能由输入受限的双端队列得到，也不能由输出受 限的双端队列得到的输出序列是( )。 【西安电子 科技大学 1996 一、5(2 分)】 a. 1234 b. 4132 c. 4231 d. 4213 31. 最大容量为 n 的循环队列，队尾指针是 rear， 队头是 front，则队空的条件是 ( )。 a. (rear+1) mod n=front b. rear=front c．rear+1=front d. (rear-l) mod n=f ront 【南京理工大学 1999 一、16(2 分)】 32. 栈 和 队 列 的 共 同 点 是 ( ) 。 燕 山 大 【 学 2001 一、1(2 分)】 a. 都是先进先出 b. 都是先进后出c. 只允许在端点处插入和删除元素 d. 没有 共同点 33. 栈的特点是( ① ),队列的特点是( ② ),栈和 队列都是( ③ )。若进栈序列为 1,2,3,4 则( ④ ) 不可能是一个出栈序列(不一定全部进栈后再出 栈)； 若进队列的序列为 1,2,3,4 则( ⑤ )是一个出 队列序列。 【北方交通大学 1999 一、1(5 分)】 ①, ②: a. 先进先出 b. 后进先出 c. 进优 于出 d. 出优于进 ③: a.顺序存储的线性结构 b.链式存储的线性 结构 c.限制存取点的线性结构 d.限制存取点的非线 性结构 ④, ⑤: a. 3,2,1,4 b. 3,2,4,1 c. 4,2,3,1 d. 4,3,2,1 f. 1,2,3,4 g. 1,3,2,4 34. 栈和队都是( )【南京理工大学 1997 一、3(2 分)】 a． 顺序存储的线性结构 b. 链式存储的非线性 结构 c. 限制存取点的线性结构 d. 限制存取点的非 线性结构 35. 设栈 s 和队列 q 的初始状态为空，元素 e1， e2，e3，e4,e5 和 e6 依次通过栈 s，一个元素出 栈后即进队列 q，若 6 个元素出队的序列是 e2， e4，e3,e6,e5,e1 则栈 s 的容量至少应该是( )。 a． 6 b. 4 c. 3 d. 2 【南京理工大学 2000 一、6(1.5 分)】 36. 用单链表表示的链式队列的队头在链表的 ( )位置。 【清华大学 1998 一、1(2 分)】a．链头 b．链尾 c．链中 37. 依次读入数据元素序列{a，b，c，d，e，f， g}进栈,每进一个元素， 机器可要求下一个元素进 栈或弹栈，如此进行，则栈空时弹出的元素构成 的序列是以下哪些序列？【哈尔滨工业大 学 2000 七(8 分)】 a．{d ，e，c，f，b，g，a} b. {f，e，g，d，a， c，b} c. {e，f，d，g，b，c，a} d. {c，d，b，e，f， a，g} 二 判断题 1. 消除递归不一定需要使用栈，此说法( ) 【中科院计算所 1998 二、2(2 分)】 【中国科技大 学 1998 二、2(2 分)】 2. 栈是实现过程和函数等子程序所必需的结构。 ( )【合肥工业大学 2000 二、2(1 分)】 3. 两个栈共用静态存储空间， 对头使用也存在空 间溢出问题。( )【青岛大学 2000 四、2(1 分)】 4．两个栈共享一片连续内存空间时，为提高内 存利用率，减少溢出机会，应把两个栈的栈底分 别设在这片内存空间的两端。( )【上海海运学 院 1998 一、4(1 分)】 5. 即使对不含相同元素的同一输入序列进行两 组不同的合法的入栈和出栈组合操作， 所得的输 出序列也一定相同。 【北京邮电大学 1999 二、 ( ) 4(2 分)】 6. 有 n 个数顺序(依次)进栈，出栈序列有 cn 种， cn=[1/(n+1)]*(2n)!/[(n!)*(n!)]。( ) 【北京邮电大学 1998 一、3(2 分)】7. 栈与队列是一种特殊操作的线性表。( )【青 岛大学 2001 四、3 (1 分)】 8. 若输入序列为 1,2,3,4,5,6,则通过一个栈可以输 出序列 3,2,5,6,4,1. ( ) 【上海海运学院 1995 一、2(1 分) 1997 一、3(1 分)】 9. 栈和队列都是限制存取点的线性结构。 【中 ( ) 科院软件所 1999 六、(5)(2 分)】 10．若输入序列为 1，2，3，4，5，6，则通过一 个栈可以输出序列 1，5，4，6，2，3。( ) 【上海海运学院 1999 一、3(1 分)】 11. 任何一个递归过程都可以转换成非递归过 程。( )【上海交通大学 1998 一、3(1 分)】 12. 只有那种使用了局部变量的递归过程在转换 成非递归过程时才必须使用栈。( ) 【上海交通大学 1998 一、4(1 分)】 13. 队列是一种插入与删除操作分别在表的两端 进行的线性表，是一种先进后出型结构。( ) 【上海海运学院 1998 一、3(1 分)】 14. 通常使用队列来处理函数或过程的调用。 ) ( 【南京航空航天大学 1997 一、5(1 分)】 15. 队列逻辑上是一个下端和上端既能增加又能 减少的线性表。( )【上海交通大学 1998 一、2】 16. 循环队列通常用指针来实现队列的头尾相 接。( )【南京航空航天大学 1996 六、1(1 分)】 17. 循环队列也存在空间溢出问题。( )【青岛大 学 2002 一、2 (1 分)】 18. 队列和栈都是运算受限的线性表，只允许在 表的两端进行运算。( )【长沙铁道学院 1997 一、5(1 分)】 19. 栈和队列都是线性表，只是在插入和删除时 受到了一些限制。( )【北京邮电大学 2002 一、 3(1 分)】 20. 栈和队列的存储方式，既可以是顺序方式， 又可以是链式方式。( ) 【上海海运学院 1996 一、2(1 分) 1999 一、2(1 分)】 三 填空题 1．栈是_______的线性表，其运算遵循_______ 的原则。 【北京科技大学 1997 一、3】 2．_______是限定仅在表尾进行插入或删除操作 的线性表。 【燕山大学 1998 一、3 (1 分)】 3. 一个栈的输入序列是：1，2，3 则不可能的栈 输出序列是_______。 【中国人民大学 2001 一、 1(2 分)】 4. 设有一个空栈，栈顶指针为 1000h(十六进制)， 现有输入序列为 1，2，3，4，5，经过 push,push,pop,push,pop,push,push 之后， 输出序列 是_______，而栈顶指针值是_______h。设栈为 顺序栈，每个元素占 4 个字节。 【西安电子科技 大学 1998 二、1(4 分)】 5. 当两个栈共享一存储区时，栈利用一维数组 stack(1,n)表示，两栈顶指针为 top[1]与 top[2]， 则当栈 1 空时， top[1]为_______， 2 空时 ， 栈 top[2] 为_______，栈满时为_______。 【南京理工大学 1997 三、1(3 分)】 6．两个栈共享空间时栈满的条件_______。 【中 山大学 1998 一、3(1 分)】7．在作进栈运算时应先判别栈是否_(1)_;在作退 栈运算时应先判别栈是否_(2)_；当栈中元素为 n 个，作进栈运算时发生上溢，则说明该栈的最大 容量为_(3)_。 为了增加内存空间的利用率和减少溢出的可能 性，由两个栈共享一片连续的空间时，应将两栈 的_(4)_分别设在内存空间的两端，这样只有当 _(5)_时才产生溢出。 【山东工业大学 1994 一、 1(5 分)】 8. 多个栈共存时， 最好用_______作为存储结构。 【南京理工大学 2001 二、7(2 分)】 9．用 s 表示入栈操作，x 表示出栈操作，若元素 入栈的顺序为 1234，为了得到 1342 出栈顺序， 相应的 s 和 x 的操作串为_______。 【西南交通大 学 2000 一、5】 10. 顺序栈用 data[1..n]存储数据， 栈顶指针是 top, 则值为 x 的元素入栈的操作是_______。 【合肥工业大学 2001 三、2 (2 分)】 11． 表达式 23+((12*3-2)/4+34*5/7)+108/9 的后缀 表达式是_______。 【中山大学 1998 一、4(1 分)】 12. 循环队列的引入，目的是为了克服_______。 【 厦 门 大 学 2001 一 、 1 (14/8 分)】 13．用下标 0 开始的 n 元数组实现循环队列时， 为实现下标变量 m 加 1 后在数组有效下标范围内 循环， 可采用的表达式是： =_______(填 pascal m： 语言，c 语言的考生不填)； m= _______(填 c 语 言 ， pascal 语 言 的 考 生 不 填 ) 。 西 南 交 通 大 【 学 2000 一、7】14 ． ________ 又 称 作 先 进 先 出 表 。 重 庆 大 【 学 2000 一、7】 15. 队 列 的 特 点 是 _______ 。 北 京 理 工 大 【 学 2000 二、2(2 分)】 16．队列是限制插入只能在表的一端，而删除在 表的另一端进行的线性表，其特点是_______。 【北方交通大学 2001 二、5】 17. 已知链队列的头尾指针分别是 f 和 r，则将值 x 入队的操作序列是_______。 【合肥工业大学 2000 三、3(2 分)】 18．区分循环队列的满与空，只有两种方法，它 们是______和______。 【北京邮电大学 2001 二、 2(4 分)】 19．设循环队列用数组 a[1..m]表示，队首、队尾 指针分别是 front 和 tail，判定队满的条件为 _______。 【山东工业大学 1995 一、1(1 分)】 20. 设循环队列存放在向量 sq.data[0:m]中，则队 头指针 sq.front 在循环意义下的出队操作可表示 为_______，若用牺牲一个单元的办法来区分队 满和队空(设队尾指针 sq.rear),则队满的条件为 _______。 【长沙铁道学院 1997 二、4 (4 分)】 21． 表达式求值是_______应用的一个典型例子。 【重庆大学 2000 一、10】 22．循环队列用数组 a[0..m-1]存放其元素值，已 知其头尾指针分别是 front 和 rear ，则当前队列 的元素个数是_______。 【厦门大学 2000 六、 1(16%/3 分)】23．设 q[0..n-1]为循环队列，其头、尾指针分别 为 p 和 r， 则队 q 中当前所含元素个数为_______。 【北京科技大学 1997 一、4】 24． 完善下面算法。 【中山大学 1998 四、 分)】 2(6 后缀表达式求值，表达式 13/25+61 的后缀表达 式格式为： 13, 25/61, + func compute(a): 后 缀 表 达 式 存 储 在 数 组 a[1..m]中。 begin setnull(s)；i:=1；ch:= (1)______； while ch&&’@’ do begin case ch of ‘0’..‘9’: x:=0; while ch&&’,’do begin x:=x*10+ord(ch)-ord(‘0’); i:=i+1；ch:= (2)_______; end ‘+’: x:=pop(s)+pop(s); ‘-‘: x:=pop(s);x:=pop(s)-x; ‘*’: x:=pop(s)*pop(s); ‘/’: x:=pop(s);x:=pop(s)/x; endcase push(s,x)；i:=i+1；ch:=a[i]； comput:= (3)_______； 25. 算术表达式求值的流程，其中 optr 为算术符栈，opnd 为操作数栈，precede(oper1，oper2)是 比 较 运 算 符 优 先 级 别 的 函 数 ， operate(opnd1,oper,opnd2)为 两 操 作 数 的 运 算结 果函数。(#表示运算起始和终止符号)【西北工业 大学 1999 六、2 (7 分)】 function exp_reduced: initstack(optr);push(optr&#&) ； initstack(opnd);read(w)； while not((w=’#’) and (gettop(optr)=’#’)) do if not w in op then push(opnd,w); else case precede(gettop(optr),w)of ’&’:[(1)_______; read(w);] ’=’:[(2)_______; read(w);]; ’&’:[theta:=pop(optr);b:=pop(opnd);a:= pop(opnd);(3)_______；] return(gettop(opnd)); 26．根据需要，用适当的语句填入下面算法的 _______中： 问题： 设有 n 件物品， 重量分别为 w1,w2,w3,?,wn 和一个能装载总重量为 t 的背包。能否从 n 件物 品中选择若干件恰好使它们的重量之和等于 t。 若能，则背包问题有解，否则无解。解此问题的 算法如下： function kanp_stack(var stack,w:array[1..n] var top: t:real): {w[1：n] 存放 n 件物品的重量，依次从中取 出物品放入背包中，检查背包重量，若不超过 t，则装入，否则弃之，取下一个物品试之。若有解 则返回函数值 true,否则返回 false} begin top:=0; i:=1; { i 指示待选物品} while (1)_______ and(2)_______do [if (3)______ or (4)_______ and (i then [top := (5)_______ ;stack[top] :=i;{第 i 件物品装入背包} t:=t-w[i]]; if t=0 then return ((6)_______) {背包问题有 解} else [if (i=n ) and (top&0) then [i:=(7)_______;{取出栈顶物品} top:= (8)_______ ； t:= (9)_______ ]; {恢复 t 值} i:=i+1 {准备挑选下一件物品} ]; ); return((10)_______) {背包无解} 【北京邮电大学 1996 四(10 分)】 19. 写出和下列递归过程等价的非递归过程。 procedure test(var sum:integer); var a:integer, begin read(a); if a=0 then sum:=1 else begin test(sum); sum:=sum*a； write(sum)； 【清华大学 1996 二】 20. 试将下列递归过程改写为非递归过程。 void test(int &sum) { int x； scanf(x)； if(x=0) sum=0 else {test(sum); sum+=x;} printf(sum)； } 【北京轻工业学院 2000 三 (15 分)】 21. 已知 ackermann 函数定义如下: (1) 写出 ack(2,1)的计算过程。 (2) 写出计算 ack(m,n)的非递归算法。 【北京航 空航天大学 1999 六 (15 分)】 22． 设计算法以求解从集合{1..n}中选取 k(k&=n) 个元素的所有组合。 例如， 从集合{1..4}中选取 2 个元素的所有组合的输出结果为： 2， 3， 4， 1 1 1 2 3， 2 4，3 4。 【合肥工业大学 2000 五、5(8 分)】 串 一、选择题 1． 下面关于串的的叙述中， 哪一个是不正确的？ ( )【北方交通大学 2001 一、5(2 分)】 a．串是字符的有限序列 b．空串是由空格 构成的串 c．模式匹配是串的一种重要运算 d．串既可以 采用顺序存储，也可以采用链式存储 2 若串 s1= ‘abcdefg’ s2= , ‘9898’,s3= ‘###’ ,s4= ‘012345’,执行 concat(replace(s1,substr(s1,length(s2),length(s3)),s 3),substr(s4,index(s2,‘8’),length(s2)))其 结 果 为 ( ) 【 北 方 交 通 大 学 1999 一 、 5 (25/7 分)】 a．abc###g0123 b．abcd###2345 c．abc###g23 45 d．abc###2345 e． abc###g1234 f． abcd###1234 g． abc###01234 3．设有两个串 p 和 q，其中 q 是 p 的子串，求 q 在 p 中首次出现的位置的算法称为( ) a．求子串 b．联接 c．匹配 d．求串 长 【北京邮电大学 2000 二、 4(20/8 分)】 【西安电子 科技大学 1996 一、1 (2 分)】 4．已知串 s=‘aaab’,其 next 数组值为( )。 【西 安电子科技大学 1996 一、7 (2 分)】 a．0123 b．1123 c．1231 d．1211 5．串 ‘ababaaababaa’ 的 next 数组为( )。 【中 山大学 1999 一、7】 a． b． c．456 d．5 6．字符串‘ababaabab’ 的 nextval 为( ) a．(0,1,0,1,04,1,0,1) b．(0,1,0,1,0,2,1,0,1) c．(0,1,0,1,0,0,0,1,1) d．(0,1,0,1,0,1,0,1,1 ) 【北京邮电大学 1999 一、1(2 分)】 7．模式串 t=‘abcaabbcabcaabdab’ ，该模式串的 next 数组的值为( )，nextval 数组的值为 ( )。 a．0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2 b．0 1 1 1 2 1
c．0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1 d．0 1 1 1 2 2
e．0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1 f．0 1 1 0 2 1
【北京邮电大学 1998 二、3 (2 分)】 8．若串 s=’software’,其子串的数目是( )。 【西 安电子科技大学 2001 应用 一、2(2 分)】 a．8 b．37 c．36 d．9 9．设 s 为一个长度为 n 的字符串，其中的字符 各不相同， s 中的互异的非平凡子串(非空且不 则 同于 s 本身)的个数为( )。 中科院计算 【 所 1997 】 a．2n-1 b．n2 c．(n2/2)+(n/2) d．(n2/2)+(n /2)-1 e. (n2/2)-(n/2)-1 f.其他情况 10．串的长度是指( )【北京工商大学 2001 一、 6 (3 分)】 a．串中所含不同字母的个数 b．串中所含字 符的个数 c．串中所含不同字符的个数 d．串中所含非 空格字符的个数 7 ． 字 符 串 ’ ababaaab ’ 的 nextval 函 数 值 为 ________。 【北京邮电大学 2001 二、4 (2 分)】 8．设 t 和 p 是两个给定的串，在 t 中寻找等于 p 的子串的过程称为__(1)__，又称 p 为__(2)__。 【西安电子科技大学 1998 二、5 (16/6 分)】 9．串是一种特殊的线性表，其特殊性表现在 __(1)__；串的两种最基本的存储方式是__(2)__、 __(3)__ ； 两 个 串 相 等 的 充 分 必 要 条 件 是 __(4)__。 【中国矿业大学 2000 一、3 (4 分)】 10 ． 两 个 字 符 串 相 等 的 充 分 必 要 条 件 是 _______。 【西安电子科技大学 1999 软件 一、 (2 1分)】 11．知 u=‘xyxyxyxxyxy’ ；t=‘xxy’ ； assign(s，u)； assign(v，substr(s，index(s，t)，len(t)+1))； assign(m， ‘ww’) 求 replace(s ， v ， m)= ________ 。 【 东 北 大 学 1997 一、1 (5 分)】 12．实现字符串拷贝的函数 strcpy 为： void strcpy(char *s , char *t) /*copy t to s*/ { while (________) } 【浙江大学 1999 一、5 (3 分)】 13．下列程序判断字符串 s 是否对称，对称则返 回 1，否则返回 0；如 f(&abba&)返回 1，f(&abab&) 返回 0； int f((1)________) {int i=0,j=0; while (s[j])(2)________; for(j--; i&J  && S[I]== S[J]; I++,J--);  return((3)_______) } 【浙江大学 1999 一、6 (3 分)】 14．下列算法实现求采用顺序结构存储的串 s 和 串 t 的一个最长公共子串。 程序(a) procedure maxcomstr(var s,t : var inde x,length : integer); var i,j,k,length1: con: begin index :=0; length :=0; i :=1;while(i&=s.len) do [j:=1; while (j&=t.len) do [ if (s[i]=t[j]) then [ k:=1; length1:=1; con:= while con do if (1)__then [length1:=length1+1;k:=k+1; ] else(2) _; if (length1&length) then [index:=i; length: =length1; ] (3)____; ] else (4)____; ] (5) ___; ] 程序(b) void maxcomstr(orderstring *s,*t; int index, length ) {int i,j,k,length1, index=0;length=0;i=1; while (i&=s.len) {j=1; while(j&=t.len) { if (s[i]= =t[j]) { k=1;length1=1;con=1; while(con) if (1) _ { length1=length1+1;k=k+1; } else(2) __; if (length1&length) { index=i; length=length 1; } (3)____; } else (4) ___; } (5) __ } } 【上海大学 2000 一、2 (10 分)】 15．完善算法：求 kmp 算法中 next 数组。 proc get _next(t:string,var next:array[1..t.len] of int eger); begin j:=1; k:=(1)__; next[1]:=0; while j&T.LEN DO   if k=0 or t.ch[j]=t.ch[k] then begin j:=j+1; k:=k+1; next[j]:=k;end else k:=(2)___; 【中山大学 1998 四、1 (4 分)】 16．下面函数 index 用于求 t 是否为 s 的子串， 若是返回 t 第一次出现在 s 中的序号(从 1 开始 计)，否则返回 0。 例 如 :s= ‘ abcdefcdek ’， t= ‘ cde ’ , 则 indse(s,t)=3, index(s,’aaa’)=0 。已知 t，s 的串 长分别是 mt,ms func index(s,t,ms,mt); i:=1;j:=1; while (i&MS) AND (J&MT) DO  if s[i]=t[j] then [ (1)__; (2)__] else [ (3)___; (4)_ ] if j&mt then return (5)____; else return (6)__ 【南京理工大学 1999 三、2 (6 分)】 17． 阅读下列程序说明和 pascal 程序,把应填入其 中的( )处的字句写在答题纸上。 程序说明： 本程序用于判别输入的字符串是否为如下形式 的字符串: w&m$ 其中,子字符串 m 是子字符串 w 的字符反 向排列,在此假定 w 不含有字符&和字符$,字符& 用作 w 与 m 的分隔符,字符$用作字符串的输入结 束符。 例如,对输入字符串 ab&ba$、11&12$、ab&dd$、 &$,程序将分别输出 ok.(是),no.(不是)。 程序 program accept(input,output); const midch=’&’; endch=’$’; var an: ch: procedure match(var answer: boolean); var ch1,ch2: f: begin read(ch1); if ch1&&endch then if (1)__ then begin match(f); if f then begin read(ch2); answer:=(2)_ end else answer:=false end else (3)___ else (4)___ begin writeln(‘enter string:’); match(an); if an then begin (5)__ if (6)_ then writeln(‘ok.’) els e writeln(‘no.’) end else writeln(‘no.’) end. 【上海海运学院 1998 七 (15 分)】 18． 试利用下列栈和串的基本操作完成下述填空 题。 initstack(s) 置 s 为空栈； push(s,x) 元素 x 入栈; pop(s) 出栈操作; gettop(s) 返回栈顶元素； sempty(s) 判栈空函数； setnull(st) 置串 st 为空串； length(st) 返回串 st 的长度； equal(s1,s2) 判串 s1 和 s2 是否相等的函数； concat(s1,s2) 返回联接 s1 和 s2 之后的串； sub(s,i,1) 返回 s 中第 i 个字符； empty(st) 判串空函数 func invert(pre: var exp:string): {若给定的表达式的前缀式 pre 正确， 本过程求得和它相应的表达式 exp 并返回“true” ，否则 exp 为空串，并返回“false” 。已知原表达式中不包 含括弧，opset 为运算符的集合。} var s: i,n: succ: ch: begin i:=1; n:=length(pre); succ:= (1)__; (2)__; while (i&N)  AND &NBS P;SUCC  DO   begin ch:=sub(pre,i,l); if (3)_ then (4)__ else if (5)__then (6)_ else begin exp:=concat((7)___,(8)____); exp:=concat((9)___,(10)___); (11)__; i:=i+1 if (12)___then begin exp:=concat(exp,sub(pre,n,1)); invert:=true end else begin setnull(exp); invert:= 注意：每个空格只填一个语句。 【清华大 学 1996 八】 四、应用题 1． 名词解释： 【大连海事 1996 一、 (1 分) 】 串 10 【河海大学 1998 二、5(3 分)】2．描述以下概念的区别：空格串与空串。 【大连 海事大学 1996 三、2、(1) (2 分)】 3．两个字符串 s1 和 s2 的长度分别为 m 和 n。 求这两个字符串最大共同子串算法的时间复杂 度为 t(m,n)。估算最优的 t(m,n)，并简要说明理 由。 【北京工业大学 1996 一、5 (6 分)】 4．设主串 s=‘xxyxxxyxxxxyxyx’ ，模式串 t= ‘xxyxy’ 。请问：如何用最少的比较次数找到 t 在 s 中出现的位置？相应的比较次数是多 少？ 【大连海事大学 2001 四 (8 分)】 5．kmp 算法(字符串匹配算法)较 brute(朴素的字 符串匹配)算法有哪些改进? 【大连海事大学 1996 三、1((2 分)】 6．已知模式串 t=‘abcaabbabcab’写出用 kmp 法求得的每个字符对应的 next 和 nextval 函数 值。 【北京邮电大学 1997 三 (10 分)】 7．给出字符串‘abacabaaad’在 kmp 算法中的 next 和 nextval 数组。 【北京邮电大学 2000 三、 1(5 分)】 8．令 t=‘abcabaa’,求其 next 函数值和 nextval 函数值。 【北方交通大学 1994 一 (6 分)】 9．已知字符串‘cddcdececdea’ ，计算每个字符 的 next 和 nextval 函 数 的 值 。 南 京 邮 电 大 【 学 2000 一 2】 10．试利用 kmp 算法和改进算法分别求 p1= ‘abaabaa’ p2= aabbaab’ next 函数和 nextval 和 ‘ 的 函数。 【东南大学 1999 一、6(8 分)】11．已知 kmp 串匹配算法中子串为 babababaa, 写出 next 数组改进后的 next 数组信息值(要求写 出数组下标起点)。 【西南交通大学 2000 二、2】 12． 求模式串 t= ‘abcaabbac’ 的失败函数 next(j) 值。 【西安交通大学 1996 四、4 (5 分)】 13．字符串的模式匹配 kmp 算法中,失败函数 (next) 是 如 何 定 义 的 ? 计 算 模 式 串 p= ‘aabaabaaabc’ 中各字符的失败函数值. 石油大 【 学 1998 一、2 (10 分)】 14．设字符串 s=‘aabaabaabaac’ ，p=‘aabaac’ (1)给出 s 和 p 的 next 值和 nextval 值； (2)若 s 作主串，p 作模式串，试给出利用 bf 算法 和 kmp 算法的匹配过程。 【北方交通大学 1998 二(15 分)】 15．设目标为 t=‘abcaabbabcabaacbacba’,模式 为 p=‘abcabaa’ (1)计算模式 p 的 naxtval 函数值；(5 分) (2)不写出算法,只画出利用 kmp 算法进行模式匹 配时每一趟的匹配过程。(5 分) 【清华大学 1998 八(10 分)】 16． 模式匹配算法是在主串中快速寻找模式的一 种有效的方法，如果设主串的长度为 m，模式的 长度为 n， 则在主串中寻找模式的 kmp 算法的时 间 复 杂 性 是 多 少 ？ 如 果 ， 某 一 模 式 p= ’ abcaacabaca’ ，请给出它的 next 函数值及 next 函 数 的 修 正 值 nextval 之 值 。 上 海 交 通 大 【 学 2000 一 (5 分)】 17．设目标为 s=‘abcaabbcaaabababaabca’ ，模 式为 p=‘babab’ ，(1)手工计算模式 p 的 nextval 数组的值；(5 分) (2)写出利用求得的 nextval 数组，按 kmp 算法对 目标 s 进行模式匹配的过程。 (5 分) 【清华大学 1997 四(10 分)】 18．用无回溯的模式匹配法(kmp 法)及快速的无 回溯的模式匹配法求模式串 t 的 next[j]值，添入 下面表中： j1 2 3 4 5 6 7 ta a b b a a b kmp 法求得的 next[j]值 快速无回溯法求得的 next[j]值 【北京邮电大学 1992 三、1(25/4 分)】 19．在改进了的(无回溯)字符串模式匹配中，要 先求 next 数组的值。 下面是求 nextval 值的算法。 type sar=array[1..m] pty=array[1..m] procedure next2(p:var nextval:sar); {在模式 p 中求 nextval 数组的值} 1 begin 2 j:=1;nextval[1]:=0;k:=0 3 repeat 4 if (k=0) or (p[j]=p[k]) 5 then [ j:=j+1;k:=k+1; 6 if p[j]=p[k] 7 then nextval[j]:=nextval[k] 8 else nextval[j]:=k ] 9 else k:=nextval[k] 10 until j=m11 算 法 中 第 4 行 有 p[j]=p[k], 第 六 行 中 也 有 p[j]=p[k]。两处比较语句相同。请分析说明此两 处比较语句的含义是什么？分析此算法在最坏 情 况下的时 间复杂 度是多 少？【北 京邮电 大 学 1993 二、2(6 分)】 20． 在字符串模式匹配的 kmp 算法中， 求模式的 next 数组值的定义如下： next［j］= 请问： (1)当 j=1 时，为什么要取 next[1]=0？ (2)为什么要取 max{k},k 最大是多少？ (3)其它情况是什么情况， 为什么取 next[j]=1? 【北 京邮电大学 1994 二(8 分)】 21．给出 kmp 算法中失败函数 f 的定义，并说明 利用 f 进行串模式匹配的规则，该算法的技术特 点是什么？ 【 东 南 大 学 1993 一 、 3 (9 分 ) 1997 一 、 2 (8 分) 2001 一、6 (6 分)】 22． 在模试匹配 kmp 算法中所用失败函数 f 的 定义中，为何要求 p1p2??pf(j)为 p1p2??pj 两头匹配的真子串？且为最大真子串？ 【东南大 学 1996 一、3(7 分)】 23．如果两个串含有相等的字符，能否说它们相 等？ 【西安电子科技大学 2000 软件 一、 (5 分)】 3 24． s1,s2 为串， 设 请给出使 s1//s2=s2//s1 成立的 所有可能的条件(//为连接符)。 【长沙铁道学院 1997 三、5 (3 分)】 【国防科技 大学 1999 一 】25．已知：s ＝’(xyz)＋＊’ ＝’(x＋z)＊y’ ，t 。 试利用联结、求子串和置换等基本运算，将 s 转 化为 t 。 【北方交通大学 1996 一、3(5 分)】 【山东科技大 学 2002 一、6 (5 分)】 第五部分、算法设计 1．设 s、t 为两个字符串，分别放在两个一维数 组中，m、n 分别为其长度，判断 t 是否为 s 的子 串。如果是，输出子串所在位置(第一个字符)， 否则输出 0。(注：用程序实现)【南京航空航天 大学 1997 九(10 分)】 2．输入一个字符串，内有数字和非数字字符， 如：ak123x456 gef4563，将其中连续 的数字作为一个整体，依次存放到一数组ａ中， 例如 123 放入ａ ［０］ 放入ａ ,456 ［１］? ? 。 ， 编程统计其共有多少个整数， 并输出这些数。 【上 海大学 1998 一 (13 分)】 3． 以顺序存储结构表示串，设计算法。求串 s 中出现的第一个最长重复子串及其位置并分析 算法的时间复杂度。 【东南大学 2000 五 (15 分)】 类似本题的另外叙述有： (1)如果字符串的一个子串(其长度大于 1)的各个 字符均相同， 则称之为等值子串。 试设计一算法， 输入字符串 s，以“！ ”作为结束标志。如果串 s 中不存在等值子串，则输出信息“无等值子串” ， 否则求出(输出)一个长度最大的等值子串。 例如：若 s=“abc123abc123!” ，则输出“无等值 子串” ；若 s=“abceebccadddddaaadd!” ，则输出 “ddddd” 。【华中科技大学 2001】 10．编写程序，统计在输入字符串中各个不同字 符出现的频度并将结果存入文件(字符串中的合 法字符为 a-z 这 26 个字母和 0-9 这 10 个数字)。 【西北大学 2000 四 (10 分)】 11．写一个递归算法来实现字符串逆序存储，要 求不另设串存储空间。 【西南交通大学 2000 三、 2】 12． 已知三个字符串分别为 s=’ ab?abcaabcbca? a’ ，s’=’caab’, s’ ’=’bcb’ 。利用所学字符 串基本运算的函数得到结果串为： s’ ’=’ ’ caabcbca?aca?a’ 要求写出得到上结果串 s’’ ， ’ 所用的函数及执行算法。 【东北大学 1998 一、 1 (10 分)】 13．s=“s1s2?sn”是一个长为 n 的字符串，存 放在一个数组中，编程序将 s 改造之后输出： (1)将 s 的所有第偶数个字符按照其原来的下标 从大到小的次序放在 s 的后半部分； (2)将 s 的所有第奇数个字符按照其原来的下标 从小到大的次序放在 s 的前半部分； 例如： s=‘abcdefghijkl’ 则改造后的 s 为‘acegikljhfdb’ 【中科院计算 。 所 1995】 第 5 章 数组和广义表 一、选择题 1.设有一个 10 阶的对称矩阵 a，采用压缩存储方 式，以行序为主存储，a11 为第一元素，其存储 地址为 1，每个元素占一个地址空间，则 a85 的地址为( )。 【燕山大学 2001 一、2 (2 分)】 a. 13 b. 33 c. 18 d. 40 2. 有一个二维数组 a[1:6， 每个数组元素用相 0:7] 邻的 6 个字节存储，存储器按字节编址，那么这 个数组的体积是(①)个字节。假设存储数组元素 a[1，0]的第一个字节的地址是 0，则存储数组 a 的最后一个元素的第一个字节的地址是(②)。若 按行存储， a[2， 则 4]的第一个字节的地址是(③)。 若按列存储，则 a[5，7]的第一个字节的地址是 (④)。就一般情况而言，当(⑤)时，按行存储的 a[i，j]地址与按列存储的 a[j，i]地址相等。供选 择的答案： 【上海海运学院 1998 二、2 (5 分)】 ① ④：a． 12 b. 66 c. 72 d. 96 e. 114 f. 120 g. 156 h. 234 i. 276 j. 282 k. 283 l. 288 ⑤： a．行与列的上界相同 b. 行与列的 下界相同 c. 行与列的上、下界都相同 d. 行的元素个数 与列的元素个数相同 3. 设有数组 a[i,j]， 数组的每个元素长度为 3 字节， i 的值为 1 到 8 ，j 的值为 1 到 10，数组从内存 首地址 ba 开始顺序存放，当用以列为主存放时， 元素 a[5，8]的存储首地址为( )。 a. ba+141 b. ba+180 c. ba+222 d. ba+225 【南京理工大学 1997 一、8 (2 分)】 4. 假 设 以 行 序 为 主 序 存 储 二 维 数 组 a=array[1..100，1..100]，设每个数据元素占 2 个 存储单元，基地址为 10，则 loc[5，5]=( )。 【福州大学 1998 一、10 (2 分)】 a. 808 b. 818 c. 1010 d. 1 020 5. 数组 a[0..5,0..6]的每个元素占五个字节，将其 按列优先次序存储在起始地址为 1000 的内存单 元中，则元素 a[5，5]的地址是( )。 【南京理工 大学 2001 一、13 (1.5 分)】 a. 1175 b. 1180 c. 1205 d. 1210 6. 有一个二维数组 a[0:8,1:5],每个数组元素用相 邻的 4 个字节存储，存储器按字节编址，假设存 储数组元素 a[0,1]的第一个字节的地址是 0，存 储数组 a 的最后一个元素的第一个字节的地址是 ( ① )。若按行存储，则 a[3,5]和 a[5,3]的第一个 字节的地址是( ② ) 和( ③ )。若按列存储，则 a[7,1]和 a[2,4]的第一个字节的地址是( ④ )和 ( ⑤ )。 【上海海运学院 1996 二、1 (5 分)】 ① ⑤ :a.28 b.44 c.76 d.92 e.108 f.116 g.132 h.176 i.184 j.188 7. 将一个 a[1..100，1..100]的三对角矩阵，按行 优 先 存 入 一 维 数 组 b[1 E 298] 中 ， a 中 元 素 a6665(即该元素下标 i=66，j=65)，在 b 数组中的 位置 k 为( )。供选择的答案： a. 198 b. 195 c. 197 【北京邮电大 学 1998 二、5 (2 分)】 8. 二维数组 a 的元素都是 6 个字符组成的串，行 下标 i 的范围从 0 到 8，列下标 j 的范圈从 1 到 10。 从供选择的答案中选出应填入下列关于数组 存储叙述中( )内的正确答案。(1)存放 a 至少需要( )个字节； (2)a 的第 8 列和第 5 行共占( )个字节； (3)若 a 按行存放，元素 a[8，5]的起始地址与 a 按列存放时的元素( )的起始地址一致。 供选择的答案： (1)a. 90 b. 180 c. 240 d. 270 e. 540 (2)a. 108 b. 114 c. 54 d. 60 e. 150(3)a. a[8,5] b. a[3,10] c. a[5,8] d. a[0,9] 【山东工业大学 2000 三、1 (4 分)】 【山东大 学 1998 三、1 (4 分)】 9. 二维数组 a 的每个元素是由 6 个字符组成的 串，其行下标 i=0,1,?,8,列下标 j=1,2,?,10。若 a 按行先存储，元素 a[8,5]的起始地址与当 a 按列 先存储时的元素( )的起始地址相同。设每个字 符占一个字节。 【西安电子科技大学 1998 一、 2 (2 分)】 a. a[8,5] b. a[3,10] c. a[5,8] d. a[0,9] 10. 若对 n 阶对称矩阵 a 以行序为主序方式将其 下三角形的元素(包括主对角线上所有元素)依次 存放于一维数组 b［1..(n(n+1))/2］中，则在 b 中 确定 aij(i&j)的位置 k 的关系为( )。 a. i*(i-1)/2+j b. j*(j-1)/2+i c. i*(i+1)/2+j d. j*(j +1)/2+i 【北京航空航天大学 2000 一、2 (2 分)】 11. 设 a 是 n*n 的对称矩阵，将 a 的对角线及对 角线上方的元素以列为主的次序存放在一维数 组 b[1..n(n+1)/2]中，对上述任一元素 aij(1≤i，j≤n，且 i≤j)在 b 中的位置为( )。 a. i(i-l)/2+j b. j(j-l)/2+i c. j(j-l)/2+i-1 d. i(i-l )/2+j-1 【南京理工大学 1999 一、9(2 分)】 12. a[n， n]是对称矩阵， 将下面三角(包括对角线) 以行序存储到一维数组 t[n(n+1)/2]中，则对任一 上三角元素 a[i][j]对应 t[k]的下标 k 是( )。 【青 岛大学 2002 二、6 (2 分)】 a. i(i-1)/2+j b. j(j-1)/2+i c. i(j-i)/2+1 d. j(i-1)/ 2+1 13. 设二维数组 a[1.. m，1.. n](即 m 行 n 列)按行 存储在数组 b[1.. m*n]中，则二维数组元素 a[i， j]在一维数组 b 中的下标为( )。 【南京理工大 学 1998 一、2 (2 分)】 a.(i-1)*n+j b.(i-1)*n+j-1 c. i*(j-1) d. j*m +i-1 14. 有一个 100*90 的稀疏矩阵，非 0 元素有 10 个，设每个整型数占 2 字节，则用三元组表示该 矩阵时，所需的字节数是( )。 【南京理工大 学 1999 二、8 (2 分)】 a. 60 b. 66 c. 18000 d. 33 15. 数组 a[0..4,-1..-3,5..7]中含有元素的个数( )。 【中山大学 1998 二、5(2 分)】 a. 55 b. 45 c. 36 d. 16 16. 用数组 r 存储静态链表，结点的 next 域指向 后继，工作指针 j 指向链中结点，使 j 沿链移动 的操作为( )。 【南京理工大学 2001 一、16(1.5 分)】a. j=r[j].next b. j=j+1 c. j=j-&next d. j= r[j]-& next 17. 对稀疏矩阵进行压缩存储目的是( )。 【北京 工商大学 2001 一、1 (3 分)】 a． 便于进行矩阵运算 b． 便于输入和输出 c． 节 省存储空间 d．降低运算的时间复杂度 18. 已知广义表 l=((x,y,z)，a，(u，t，w))，从 l 表中取出原子项 t 的运算是( )。 a. head(tail(tail(l))) b. tail(head(head(tail(l))) ) c. head(tail(head(tail(l)))) d. head(tail(head(tail(t ail(l))))) 【北京邮电大学 1998 二、4(2 分)】 19. 已知广义表 ls＝((a,b,c),(d,e,f)),运用 head 和 tail 函数取出 ls 中原子 e 的运算是( )。 a. head(tail(ls)) b. tail(head(ls)) c. head(tail(head(tail(ls))) d. head(tail(tail(hea d(ls)))) 【西安电子科技大学 2001 应用一、3(2 分)】 20. 广义表 a=(a,b,(c,d),(e,(f,g))),则下面式子的值 为( )。 【北京邮电大学 1999 一、2(2 分)】 head(tail(head(tail(tail(a))))) a. (g) b. (d) c. c d. d 21. 已知广义表: a=(a,b), b=(a,a), c=(a,(b,a),b), 求 下列运算的结果: tail(head(tail(c))) =( )。 【长沙铁道学院 1998 三、 4 (2 分)】 a.(a) b. a c. a d. (b) e. b f. (a)22. 广义表运算式 tail(((a,b),(c,d)))的操作结果是 ( )。 【西安电子科技大学 1998 一、4(2 分)】 a. (c,d) b. c,d c. ((c,d)) d. d 23. 广义表 l=(a，(b，c))，进行 tail(l)操作后的结 果为( )。 【中山大学 1999 一、10】 a. c b. b，c c.(b，c) d.((b，c)) 24. 广义表((a,b,c,d))的表头是( )，表尾是( )。 【青岛大学 2002 二、7 (2 分)】 a. a b.() c.(a,b,c,d) d.(b,c,d) 25. 广 义 表 (a,(b,c),d,e)的表 头 为 ( )。 中山 大 【 学 1998 二、6(2 分)】 a. a b. a,(b,c) c. (a,(b,c)) d. (a) 26. 设广义表 l=((a,b,c))，则 l 的长度和深度分别 为( )。 【武汉大学 2000 二、9】 a. 1 和 1 b. 1 和 3 c. 1 和 2 d. 2 和3 27. 下面说法不正确的是( )。 【南京理工大 学 2001 一、3 (1.5 分)】 a. 广义表的表头总是一个广义表 b. 广义表 的表尾总是一个广义表 c. 广义表难以用顺序存储结构 d. 广义表可 以是一个多层次的结构 二、判断题 1. 数组不适合作为任何二叉树的存储结构。( ) 【南京航空航天大学 1995 五、2 (1 分)】 2. 从逻辑结构上看，n 维数组的每个元素均属于 n 个向量。( ) 【 东 南 大 学 2001 一 、 2 (1 分 ) 】 中 山 大 【 学 1994 一、2 (2 分)】3. 稀疏矩阵压缩存储后，必会失去随机存取功 能。( )【中科院软件所 1997 一、1 (1 分)】 4. 数组是同类型值的集合。( )【上海海运学 院 1996 一、3(1 分)1999 一、4(1 分)】 5. 数组可看成线性结构的一种推广，因此与线性 表一样，可以对它进行插入，删除等操作。( ) 【上海交通大学 1998 一、5】 6. 一个稀疏矩阵 am*n 采用三元组形式表示， 若 把三元组中有关行下标与列下标的值互换， 并把 m 和 n 的值互换， 则就完成了 am*n 的转置运算。 ( ) 【西安交通大学 1996 二、8 (3 分)】 7. 二维以上的数组其实是一种特殊的广义表。 ( ) 【北京邮电大学 2002 一、5 (1 分)】 8. 广义表的取表尾运算，其结果通常是个表，但 有时也可是个单元素值。( ) 【南京航空航天大学 1996 六、2 (1 分)】 9. 若一个广义表的表头为空表，则此广义表亦为 空表。( ) 【中科院软件所 1997 一、8(1 分)】 【长沙铁道 学院 1998 一、8 (1 分)】 10. 广义表中的元素或者是一个不可分割的原 子，或者是一个非空的广义表。( ) 【合肥工业大学 2000 二、3 (1 分)】 11. 所谓取广义表的表尾就是返回广义表中最后 一个元素。 ) 合肥工业大学 2001 二、 (1 分)】 ( 【 3 12. 广义表的同级元素(直属于同一个表中的各 元素)具有线性关系。( ) 【华南理工大学 2002 一、9(1 分)】 13. 对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。( ) 【华南理工大学 2002 一、10(1 分)】 14. 一 个 广 义 表 可 以 为 其 它 广 义 表 所 共 享 。 ( ) 【山东大学 2001 一、2(1 分)】 三、 填空题 1. 数组的存储结构采用_______存储方式。 【中山 大学 1998 一、6(1 分)】 2. 设二维数组 a[-20..30,-30..20], 每个元素占有 4 个存储单元, 存储起始地址为 200.如按行优先 顺序存储,则元素 a[25,18]的存储地址为__(1)_； 如按列优先顺序存储,则元素 a[-18,-25]的存储地 址为__(2)_。 【北方交通大学 1999 二、3(4 分)】 3. 设数组 a[1..50,1..80]的基地址为 2000，每个元 素占 2 个存储单元，若以行序为主序顺序存储， 则元素 a[45,68]的存储地址为_(1)_;若以列序为 主序顺序存储，则元素 a[45,68]的存储地址为 _(2)_。 【华中理工大学 2000 一、5(2 分)】 4. 将整型数组 a[1..8，1..8]按行优先次序存储在 起始地址为 1000 的连续的内存单元中，则元素 a[7 ， 3] 的 地 址 是 ： _______ 。 合 肥 工 业 大 【 学 1999 三、4(2 分)】 5. 二维数组 a[4][5][6](下标从 0 开始计，a 有 4*5*6 个元素)， 每个元素的长度是 2， a[2][3][4] 则 的地址是____。 a[0][0][0]的地址是 1000,数据 (设 以行为主方式存储) 【南京理工大学 2000 二、11(1.5 分)】 6. 设有二维数组 a[0..9,0..19],其每个元素占两个 字节，第一个元素的存储地址为 100，若按列优先 顺 序 存 储 ， 则 元 素 a[6,6] 存 储 地 址 为 _______。 【北京工商大学 2001 二、5 (4 分)】 7. 已知数组 a[0..9,0..9]的每个元素占 5 个存储单 元，将其按行优先次序存储在起始地址为 1000 的连续的内存单元中，则元素 a[6，8]的地址为 _______。 【合肥工业大学 2001 三、4(2 分)】 8. 已知二维数组 a[1..10，0..9]中每个元素占 4 个 单元，在按行优先方式将其存储到起始地址为 1000 的连续存储区域时，a[5，9]的地址是： _______。 【厦门大学 2002 六、5 (4 分)】 9. 用一维数组 b 与列优先存放带状矩阵 a 中的非 零元素 a[i,j] (1≤i≤n,i-2≤j≤i+2),b 中的第 8 个 元素是 a 中的第_(1)_行，第_(2)_列的元素。 【北 京邮电大学 2001 二、3(4 分)】 10. 设数组 a[0..8,1..10],数组中任一元素 a[i,j]均占 内存 48 个二进制位，从首地址 2000 开始连续存 放在主内存里，主内存字长为 16 位，那么 (l) 存放该数组至少需要的单元数是_______; (2) 存放数组的第 8 列的所有元素至少需要的 单元数是_______; (3) 数组按列存储时，元素 a[5,8]的起始地址是 _______。 【中国矿业大学 2000 一、4(4 分)】 11．设 n 行 n 列的下三角矩阵 a 已压缩到一维数 组 b[1..n*(n+1)/2]中， 若按行为主序存储， a[i,j] 则 对应 的 b 中存储位置为_______。 【武汉 大 学 2000 一、1】 12. n 阶对称矩阵 a 满足 a[i][j]=a[j][i],i,j=1..n,， 用 一维数组 t 存储时，t 的长度为__(1)______，当 i=j，a[i][j]=t[(2)],i&j,a[i][j]=t[(3)],i&j,a[i][j]=t[(4)]。【青岛大学 2001 六、1(3 分)】 13．己知三对角矩阵 a【1..9,1..9】的每个元素占 2 个单元，现将其三条对角线上的元素逐行存储 在起始地址为 1000 的连续的内存单元中，则元 素 a[7,8] 的 地 址 为 ______ 。 合 肥 工 业 大 【 学 2000 三、4(2 分)】 14. 设有一个 10 阶对称矩阵 a 采用压缩存储方式 (以行为主序存储：a11=1)，则 a85 的地址为 _______。 【西安电子科技大学 1999 软件 一、3 (2 分)】 15. 所 谓 稀 疏 矩 阵 指 的 是 _______ 。 厦 门 大 【 学 2001 一、2 (14%/5 分)】 16. 对矩阵压缩是为了_______。 【北京理工大 学 2000 二、3(2 分)】 17. 上 三 角 矩 阵 压 缩 的 下 标 对 应 关 系 为 ： _______。 【福州大学 1998 二、6 (2 分)】 【南京大 学 1999】 18. 假设一个 15 阶的上三角矩阵 a 按行优先顺序 压缩存储在一维数组 b 中，则非零元素 a9,9 在 b 中的存储位置 k=_______。(注：矩阵元素下标从 1 开始)【北京工商大学 2001 二、1 (4 分)】 19．设下三角矩阵 a= 如果按行序为主序将下三角元素 ai j (i,j)存储在 一个一维数组 b[ 1..n(n+1)/2]中， 对任一个三角矩 阵元素 aij ,它在数组 b 中的下标为_______。 【北 方交通大学 2001 二、3】 20. 当广义表中的每个元素都是原子时，广义表 便成了_______。 【长沙铁道学院 1998 二、8 (2 分)】21. 广 义 表 的 表 尾 是 指 除 第 一 个 元 素 之 外 ， _______。 【中山大学 1998 一、7 (1 分)】 22. 广义表简称表，是由零个或多个原子或子表 组成的有限序列，原子与表的差别仅在 于 (1)____。 为了区分原子和表， 一般用 (2)____ 表示表，用 (3)_____表示原子。一个表的长度 是指 (4)__，而表的深度是指__(5)__【山东工业 大学 2000 一、 分)】 3(3 【山东大学 1998 一、 (3 2 分)】 23. 广义表的_______ 定义为广义表中括弧的重 数。 【重庆大学 2000 一、5】 24．设广义表 l=((),()), 则 head(l)是(1)___；tail(l) 是(2)____；l 的长度是(3)___；深度是 (4)__。 【中科院计算所 1998 一、2(4 分)】 【中国科技大 学 1998 一、2(4 分)】 25. 已知广义表 a=(9,7,( 8,10,(99)),12)，试用求表 头和表尾的操作 head( )和 tail( )将原子元素 99 从 a 中取出来。 【西安交通大学 1996 四、5 (5 分)】 26. 广义表的深度是_______。 【北京轻工业学 院 2000 一、1(2 分)】 27. 广义表(a,(a,b),d,e,((i,j),k))的长度是(1)_，深度 是(2)_。 【山东大学 2001 三、9 (2 分)】 【西安电子科技大学 2001 软件 一、 (2 分)】 5 【哈 尔滨工业大学 2001 一、2 (2 分)】 28. 已知广义表 ls=(a，(b，c，d)，e),运用 head 和 tail 函数取出 ls 中原子 b 的运算是_______。 【燕山大学 2001 二、2 (3 分)】 29. 广义表 a=(((a，b)，(c，d，e)))，取出 a 中的 原子 e 的操作是: _______。【合肥工业大学 1999 三、5(2 分)】 30. 设某广义表 h=(a，(a,b,c)) ，运用 head 函数和 tail 函数求出广义表 h 中某元素 b 的运算式 _______。 【北京科技大学 1997 一、5】 31. 广 义 表 a((( ),(a,(b),c))) ， head(tail(head(tail(head(a))))等于 。 【合肥工业大学 2000 三、5(2 分)】 32. 广义表运算式 head(tail(((a,b,c),(x,y,z))))的结 果是_______。 【西安电子科技大学 1999 软件 一、9(2 分)】 33. 已 知 广 义 表 a=(((a ， b) ， (c) ， (d ， e))) ， head(tail(tail(head(a))))的结果是_______。 【合肥工业大学 2001 三、5 (2 分)】 34. 利用广义表的 gethead 和 gettail 操作， 从广义 表 l=((apple，pear)，(banana，orange))中分离出 原子 banana 的函数表达式是_______。【山东大 学 2001 三、6 (2 分)】 35. 已知 a 数组元素共 5 个，依次为 12，10，5， 3，1；b 数组元素共 4 个，依次为 4,6,8,15，则执 行如下所示的过程语句 sort 后得到 c 数组各元素 依次为 15,12,10,8,6,5,4,3,1；数组 a,b,c 的长度分 别为 l=5,m=4,n=9 请在程序中方框内填入正确的 成分，完成上述要求。 var i, j, k, x: d: array[1..m] begin for i:=1 to m do d[i]:=(1) ;i:=1; j:=1; k:=1; while (i&=l) and (j&=m) do begin if a[i]&d[j] then begin(2) ; (3) _end else begin (4)__; (5) __ c[k]:=x; (6) while(7) _do begin c[k]:=a[i]; k:=k+1; i:=i+1； while(8) _do begin c[k]:=d[j]; k:=k+1; j:=j+1； end. {sort} 【上海交通大学 1998 七 (12 分)】 36. 下列程序段 search(a,n,k)在数组 a 的前 n(n&=1) 个元素中找出第 k(1&=k&=n)小的值。 这里假设数 组 a 中各元素的值都不相同。 #define maxn 100 int a[maxn],n,k; int search_c(int a[], int n, int k) {int low, high, i, j, m, k--,;low=0 ;high=n-1; do {i= j= t=a[low]; do{while (i&j && t&a[j]) j--; if (i&j) a[i++]=a[j]; while (i&j && t&=a[i]) i++ if (i&j) a[j--]=a[i]; } while (i&j); a[i]=t; if (1) ; if (i&k) low= (2) ; else high= (3) ;}while(4) _; return(a[k]); } 【上海大学 1999 一、1(8 分)】 37. 完善下列程序，每小题在 pascal 语言(a)和 c 语言(b)中任选一题。 下面是一个将广义表逆置的 过程。例如原来广义表为((a,b),c,(d,e))，经逆置 后为：((e,d),c,(b,a))。 (a)算法的 pascal 语言过程描述(编者略)：(b)算法 的 c 语言过程描述： typedef struct glistnode { struct glistnode * union{ struct{struct glistnode *hp,*} } }*glist, glist reverse(p) {glist q,h,t,s; if(p==null) q= else {if(1) { q=(glist)malloc(sizeof(gnode)); q-&tag=0 ; q-&val.data