第一章 概论
一、填空题
1.计算机专业人员必须完成的两项基本任务是：_数据表示__和__数据处理__。
2.数据在计算机存储器中的存在形式称为_机内表示_。
3.概括地说，数据结构课程的主要内容包括: 数据的_逻辑结构__、定义在_逻辑结构上的基本运算__、数据的_存储结构和运算__的实现。此外，该课程还要考虑各种结构和实现
方法的_评价和选择_。
4.由一种_逻辑性_结构和一组_基本运算_构成的整体是实际问题的一种数学模型，这种数学模型的建立、选择和实现是数据结构的核心问题。
5.存储结构是逻辑结构的_存储_实现。
6.数据表示任务是逐步完成的，即数据表示形式的变化过程是_机外表示_->_逻辑结构_->_存储结构__。
7.数据处理任务也是逐步完成的，即转化过程是_处理要求_->_基本运算和运算_->_算法。
8.从数据结构的观点看，通常所说的\"数据\"应分成三个不同的层次，即_数据_、_数据元素_和_数据项_。
1
9.根据需要，数据元素又被称为_元素_、_结点_、_顶点_或_记录_。
10.在有些场合下，数据项又称为_字段_或_域_，它是数据的不可分割的最小标识单位。
11.从某种意义上说，数据、数据元素和数据项实际反映了数据组织的三个层次，数据
可由若干个_数据元素_构成，数据元素可由若干个_数据项_构成。
12.根据数据元素之间关系的不同特性，通常有_集合_、_线性结构_、_树形结构__、_图状结构_四类基本逻辑结构，它们反映了四类基本的数据组织形式。
13.根据操作的效果，可将运算分成以下两种基本类型：
①__加工_型运算，其操作改变了原逻辑结构的“值”，如结点个数、某些结点的内容等；
②__引用_型运算，其操作不改变原逻辑结构，只从中提取某些信息作为运算的结果。
14.将以某种逻辑结构S为操作对象的运算称为“_定义在S上的运算_”，简称“_ S上运算_”。
15.一般地，可能存在同一逻辑结构S上的两个运算A和B，A的实现需要或可以利用B，而B的实现不需要利用A。在这种情况下，称A可以“_归纳_”为B。
16.存储实现的基本目标是建立数据的_机内表示_。
17.一般地，一个存储结构包括_存储结点__、_数据元素之间关联方式的表示_、_附加设
2
施_三个主要部分。
18.通常，存储结点之间可以有_顺序存储方式_、_链式存储方式_、_索引存储方式_、_
散列存储方式_四种关联方式，称为四种基本存储方式。
19.可用任何一种存储方式所规定的存储结点之间的关联方式来间接表达给定逻辑
结构S中数据元素之间的逻辑关系。由此得到的存储结构，称为_给定逻辑结构S的存储实现__或_存储映象_。
20.一个运算的实现是指一个完成该运算功能的_程序_。运算实现的核心是处
理步骤的规定，即_算法设计_。
21.任何算法都必须用某种语言加以描述。根据描述算法的语言的不同，可将算法分
为：__运行终止的程序可执行部分_、_伪语言算法_、_非形式算法_三类。
22.数据结构课程着重评论算法的_时空性能_，又称为“_算法分析 _”。
23.通常从_正确性能_、_易读性_、_健壮性_、_高效性_等几方面评价算法的(包括程序)的质量。
24.一个算法的时空性能是指该算法的_时间性能_和_空间性能_，前者是算法包含的_计算量，后者是算法需要的_存储量_。
3
25.通常采用下述办法来估算求解某类问题的各个算法在给定输入下的计算量：
① 根据该类问题的特点合理地选择一种或几种操作作为“_标准操作_”；
② 确定每个算法在给定输入下共执行了多少次_标准操作_，并将此次数规定为该算法在给定输入下的_计算量__。
26.通常，一个算法在不同输入下的计算量是不同的。则可用以下两种方式来确定一个算法的计算量：
① 以算法在所有输入下的计算量的最大值作为算法的计算量，这种计算量称为算法的____最坏情况时间复杂性_或_最坏情况时间复杂度_。
② 以算法在所有输入下的计算量的加权平均值作为算法的计算量，这种计算量称为算法的_平均时间复杂性_或_平均时间复杂度__。
27.最坏情况时间复杂性和平均时间复杂性统称为_时间复杂性_或_时间复杂度___。
28.在一般情况下，一个算法的时间复杂性是_算法输入规模_的函数。
29.一个算法的输入规模或问题的规模是指_作为该算法输入的数据所含数据元素的数目，或与此数目有关的其他参数__。
30.常见时间复杂性的量级有：常数阶O(_1__)、对数阶O(_log2n __)、线性阶O (_n _)、平方阶O(_n2_)、和指数阶O(_2n_)。通常认为，具有指数阶量级的算法是_实际不可计算_，而量级低于平方阶的算法是_高效_的。
4
31.数据结构的基本任务是数据结构的_设计_和_实现__。
32.数据结构的课程的主要内容可以概括为：_数据结构的定义_、_数据结构的实现、_数据结构的评价_和_选择_。
33._ 数据的逻辑结构_与数据元素本身的内容和形式无关。
34.从逻辑关系上讲，数据结构主要分为两大类，它们是_线性结构_和__非线性结构_。
35.程序段“for(i=l;i<=n;i++){k++;for(j=1;j<=n;j++)l+=k;}”的时间复杂度T(n)= O（n2）。
36.程序段“i=1;while(i<=n)i=i*2;”的时间复杂度T(n)= o(log2n) _。
二、单项选择题
1.以下说法错误的是 2
①用数字式计算机解决问题的实质是对数据的加工处理
②程序设计的实质是数据处理
③数据的逻辑结构是数据的组织形式，基本运算规定了数据的基本操作方式
④运算实现是完成运算功能的算法，或这些算法的设计
5
⑤数据处理方式总是与数据某种相应的表示形式相联系，反之亦然
2.根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的
数据组织形式。以下解释错误的是 ( 1 )
①集合中任何两个结点之间都有逻辑关系但组织形式松散
②线性结构中结点按逻辑关系依次排列形成一条\"锁链\"
③树形结构具有分支、层次特性，其形态有点像自然界中的树
④图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接
3.关于逻辑结构，以下说法错误的是 ( 2 ①逻辑结构与数据元素本身的形成、内容无关
②逻辑结构与数据元素的相对位置有关
③逻辑结构与所含结点个数无关
④一些表面上很不相同的数据可以有相同的逻辑结构
⑤逻辑结构是数据组织的某种\"本质性\"的东西
6
)
4.根据操作的效果，可将运算分成加工型运算、引用型运算两种基本类型。对于表格 处理中的五种功能以下解释错误的是 ( 3 )
①查找引用型运算，功能是找出满足某种条件的结点在s(线形结构)中的位置
②读取引用型运算 功能是读出s(线形结构)中某指定位置结点的内容
③插入引用型运算，功能是在s(线形结构)的某指定位置上增加一个新结点
④删除加工型运算，功能是撤消s(线形结构)某指定位置上的结点
⑤更新加工型运算，功能是修改s(线形结构)中某指定结点的内容
5.一般地，一个存储结构包括以下三个主要部分。以下说法错误的是 ( 1 )
①存储结点每个存储结点可以存放一个或一个以上的数据元素
②数据元素之间关联方式的表示 也就是逻辑结构的机内表示
③附加设施，如为便于运算实现而设置的“哑结点”等等
6.一般地，一个存储结构包括以下三个主要部分。以下说法错误的是
①每个存储结点只能存放一个数据元素 ( 2 )
7
②数据元素之间的关联方式可由存储结点之间的关联方式直接表达
③一种存储结构可以在两个级别上讨论。其一是机器级，其二是语言级
④语言级描述可经编译自动转换成机器级 因此也可以看成是一种机内表示
7.通常从正确性、易读性、健壮性、高效性等四个方面评价算法(包括程序)的质
量。以下解释错误的是 ( 4 )
①正确性 算法应能正确地实现预定的功能(即处理要求)
②易读性 算法应易于阅读和理解 以便于调试 修改和扩充
③健壮性 当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要的运行结果
④高效性 即达到所需要的时间性能
8.对于数据结构课程的主要内容，以下解释正确的是 ( 3 )
①数据结构的定义，包括逻辑结构、存储结构和基本运算集
②数据结构的实现，包括存储实现、运算实现和基本运算集
③数据结构的评价和选择，包括逻辑结构的选择、基本运算集的选择和存储
8
选择
9，与数据元素本身的形式、内容、相对位置、个数无关的是数据的 ( 3 )
①存储结构 ②存储实现 ③逻辑结构 ④运算实现
10顺序存储结构 ( 3 )
①仅适合于静态查找表的存储
②仅适合于动态查找表的存储
③既适合静态又适合动态查找表的存储
④既不适合静态又不适合动态查找表的存储
11.算法的时间复杂度，都要以通过算法中执行频度最高的语句的执行次数来确定这种
观点 ( 2 )
①正确 ②错误
12以下说法正确的是 ( 2 )
①所谓数据的逻辑结构指的是数据元素之间的逻辑关系。
9
②逻辑结构与数据元素本身的内容和形式无关
③顺序文件只适合于存放在磁带上，索引文件只能存放在磁盘上
④基于某种逻辑结构之上的运算，其实现是惟一的
13以下说法正确的是 ( 4 )
①数据元素是数据的最小单位
②数据项是数据的基本单位
③数据结构是带有结构的各数据项的集合
④数据结构是带有结构的数据元素的集合
14以下说法错误的是 ( 4 )
①所谓数据的逻辑结构指的是数据元素之间的逻辑关系的整体
②数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要而建立的
③数据结构、数据元素、数据项在计算机中的映象分别称为存储结构、结点、数据域
④数据项是数据的基本单位
10
15通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 ( 2 )
①数据元素具有同一特点
②不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致
③每个数据元素都一样
④数据元素所包含的数据项的个数要相等
第二章 线性表习题
一、单项选择题
1. 线性表是__A______。
A．一个有限序列，可以为空 B．一个有限序列，不可以为空
C．一个无限序列，可以为空 D．一个无限序列，不可以为空
2. 在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动 A 个元素。
A．n-i B．n-i+l C．n-i-1 D．i
3. 线性表采用链式存储时，其地址___D_____。
11
A．必须是连续的 B．一定是不连续的
C．部分地址必须是连续的 D．连续与否均可以
4. 从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较___C_____个元素结点。
A．n/2 B．n C．（n+1）/2 D．（n-1）/2
5. 在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是_D___。
A． p->next=s; s->prior=p;
p->next->prior=s; s->next=p->next;
B． s->prior=p; s->next=p->next;
p->next=s; p->next->prior=s;
C． p->next=s; p->next->prior=s;
s->prior=p; s->next=p->next;
D． s->prior=p; s->next=p->next;
p->next->prior=s; p->next=s;
12
6. 设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为___A_____。
A．p->next=p->next->next; B．p=p->next; C．p=p->next->next; D．p->next=p;
7. 在一个长度为n的顺序表中向第i个元素(0< i 8. 在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行B A．s->next=p->next; p->next=s B．q->next=s; s->next=p C．p->next=s->next; s->next=p D．p->next=s; s->next=q 9. 以下关于线性表的说法不正确的是__C____。 A．线性表中的数据元素可以是数字、字符、记录等不同类型。 B．线性表中包含的数据元素个数不是任意的。 C．线性表中的每个结点都有且只有一个直接前趋和直接后继。 13 D．存在这样的线性表：表中各结点都没有直接前趋和直接后继。 10. 线性表的顺序存储结构是一种__A_____的存储结构。 A．随机存取 B．顺序存取 C．索引存取 D．散列存取 11. 在顺序表中，只要知道___D____，就可在相同时间内求出任一结点的存储地址。 A．基地址 B．结点大小 C．向量大小 D．基地址和结点大小 12. 在等概率情况下，顺序表的插入操作要移动__B____结点。 A．全部 B．一半 C．三分之一 D．四分之一 13. 在___C___运算中，使用顺序表比链表好。 A．插入 B．删除 C．根据序号查找 D．根据元素值查找 14. 在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是__B_____。 A．O(1) B．O(n) C．O(n2) D．O(log2n) 15. 设有一个栈，元素的进栈次序为A, B, C, D, E,下列是不可能的出栈序列____C______。 A．A, B, C, D, E B．B, C, D, E, A C．E, A, B, C, D D．E, D, C, B, 14 A 16. 在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为__C____。 A．top不变 B．top=0 C．top-- D．top++ 17. 向一个栈顶指针为hs的链栈中插入一个s结点时，应执行__B____。 A．hs->next=s; B．s->next=hs; hs=s; C．s->next=hs->next;hs->next=s; D．s->next=hs; hs=hs->next; 18. 在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为___D_____。 A．rear％n= = front B．（front+l）％n= = rear C．rear％n -1= = front D．(rear+l)％n= = front 19. 在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为___C_____。 A．rear％n= = front B．front+l= rear C．rear= = front D．(rear+l)％n= front 15 20. 在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为___A_____。 A．front=front->next B．rear=rear->next C．rear=front->next D．front=rear->next 二、填空题 1. 线性表是一种典型的___线性______结构。 2. 在一个长度为n的顺序表的第i个元素之前插入一个元素，需要后移n-i+1个元素。 3. 顺序表中逻辑上相邻的元素的物理位置相邻。 4. 要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需__前移_____一个位置，移动过程是从__前_____向___后____依次移动每一个元素。 5. 在线性表的顺序存储中，元素之间的逻辑关系是通过__物理存储位置_____决定的；在线性表的链接存储中，元素之间的逻辑关系是通过_链域的指针值______决定的。 6. 在双向链表中，每个结点含有两个指针域，一个指向__前趋_____结点，另一个指向__后继_____结点。 7. 当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用___顺序____存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用__链接_____存储结构 16 为宜。 8. 顺序表中逻辑上相邻的元素，物理位置__一定__相邻，单链表中逻辑上相邻的元素，物理位置_不一定___相邻。 9. 线性表、栈和队列都是__线性_____结构，可以在线性表的__任何____位置插入和删除元素；对于栈只能在___栈顶____位置插入和删除元素；对于队列只能在__队尾_____位置插入元素和在___队头____位置删除元素。 10. 根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为___单链表__和__双链表__；而根据指针的联接方式，链表又可分为__非循环链表__和__循环链表__。 11. 在单链表中设置头结点的作用是___使空表和非空表统一；算法处理一致_____。 12. 对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为__O(1)____，在给定值为x的结点后插入一个新结点的时间复杂度为__O(n)__。 13. 对于一个栈作进栈运算时，应先判别栈是否为__栈满_____，作退栈运算时，应先判别栈是否为__栈空__，当栈中元素为m时，作进栈运算时发生上溢，则说明栈的可用最大容量为__m_____。为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的__栈底_分别设在这片内存空间的两端，这样只有当__两个栈的栈顶在栈空间的某一位置相遇_____时才产生上溢。 14. 设有一空栈，现有输入序列1，2，3，4，5，经过push, push, pop, push, pop, push, push后，输出序列是__2、3__。 17 15. 无论对于顺序存储还是链式存储的栈和队列来说，进行插入或删除运算的时间复杂度均相同为___O(1)_______。 -------------------------------------------------------------------------------- 习题三 栈和队列 一 单项选择题 1. 在作进栈运算时,应先判别栈是否(① ),在作退栈运算时应先判别栈是否(② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③ )。 （B A B） ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 2．若已知一个栈的进栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，...，pn，若p1＝3，则p2为( A )。 A 可能是2 B 一定是2 C 可能是1 D 一定是1 3. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ C ） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 18 4.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6 , s5,s1,则栈的容量至少应该是 （ B ） A.2 B. 3 C. 5 D.6 5. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（ B ）。 A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 6. 执行完下列语句段后，i值为：（ B ） int f(int x) { return ((x>0) ? x* f(x-1):2);} int i ; i =f(f(1)); A．2 B. 4 C. 8 D. 无限递归 7. 表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（ D ），其中^为乘幂 。 19 A. 3,2,4,1,1；(*^(+*- B. 3,2,8；(*^- C. 3,2,4,2,2；(*^(- D. 3,2,8；(*^(- 8. 用链接方式存储的队列，在进行删除运算时（ D ）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 9. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（ C ）的数据结构。 A．队列 B．多维数组 C．栈 D. 线性表 10．设C语言数组Data[m+1]作为循环队列SQ的存储空间， front为队头指针，rear 为 队 尾 指 针 ， 则 执 行 出 队 操 作 的 语 句 为 （ D ） A.front=front+1 B. front=（front+1）% m C.rear=(rear+1)%(m+1) D. front=(front+1)%(m+1) 11.循环队列的队满条件为 ( C ) A. (sq.rear+1) % maxsize ==(sq.front+1) % maxsize; 20 B. (sq.front+1) % maxsize ==sq.rear C. (sq.rear+1) % maxsize ==sq.front D.sq.rear ==sq.front 12. 栈和队列的共同点是（ C ）。 A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点 二、填空题 1．栈是__操作受限（或限定仅在表尾进行插入和删除操作）_____的线性表，其运算遵循__后进先出_____的原则。 2. 一个栈的输入序列是：1，2，3则不可能的栈输出序列是_3 1 2__。 3．用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为__S×SS×S××_____。 4. 循环队列的引入，目的是为了克服__假溢出时大量移动数据元素_____。 5．队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是__先进先出_____。 21 6. 已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是_s=(LinkedList)malloc(sizeof(LNode))； s->data=x;s->next=r->next；r->next=s；r=s；______。 7．表达式求值是__栈_____应用的一个典型例子。 8．循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear ，则当前队列的元素个数是__（rear-front+m）% m_____。 9. 以下运算实现在链栈上的初始化，请在________________处用请适当句子予以填充。 Void InitStacl(LstackTp *ls){ ___ls=NULL_____________;} 10.` 以下运算实现在链栈上的进栈，请在处用请适当句子予以填充。 Void Push（LStackTp *ls,DataType x） { LstackTp *p;p=malloc(sizeof(LstackTp)); ____p->data=x____________; p->next=ls; ____ ls=p____________; } 22 11．以下运算实现在链栈上的退栈，请在________________处用请适当句子予以填充。 Int Pop(LstackTp *ls,DataType *x) {LstackTp *p; if(ls!=NULL) { p=ls; *x=____p->data____________; ls=ls->next; ___free(p)_____________; return(1)； }else return(0); } 12. 以下运算实现在链队上的入队列，请在________________处用适当句子予以填充。 Void EnQueue(QueptrTp *lq,DataType x) 23 { LqueueTp *p; p=(LqueueTp *)malloc(sizeof(LqueueTp)); ___p->data_____________=x; p->next=NULL; (lq->rear)->next=______p__________; ____ lq->rear=p____________; } ------------------------------------------------------------------------------- 习题四 串 一、单项选择题 1．下面关于串的的叙述中，哪一个是不正确的？（ B ） A．串是字符的有限序列 B．空串是由空格构成的串 C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 24 2．串是一种特殊的线性表，其特殊性体现在（ B ）。 A．可以顺序存储 B．数据元素是一个字符 C．可以链接存储 D．数据元素可以是多个字符 3．串的长度是指（ B ） A．串中所含不同字母的个数 B．串中所含字符的个数 C．串中所含不同字符的个数 D．串中所含非空格字符的个数 4．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ C ） A．求子串 B．联接 C．匹配 D．求串长 5．若串S=“software”,其子串的个数是（ C ）。 A．8 B．37 C．36 D．9 二、填空题 1．含零个字符的串称为__空____串。任何串中所含__字符____的个数称为该串的长度。 2．空格串是指__ 由空格字符（ASCII值32）所组成的字符串 __，其长度等于 25 __ 空格个数 __。 3．当且仅当两个串的__长度____相等并且各个对应位置上的字符都__相等____时，这两个串相等。一个串中任意个连续字符组成的序列称为该串的__子____串，该串称为它所有子串的___主___串。 4．INDEX（‘DATASTRUCTURE’， ‘STR’）=___5_____。 5．模式串P=‘abaabcac’的next函数值序列为__01122312__。 6．下列程序判断字符串s 是否对称，对称则返回1，否则返回0；如 f(\"abba\")返回1，f(\"abab\")返回0； int f((1)__char s[ ] ______) {int i=0,j=0; while (s[j])(2)___ j++ _____; for(j--; i } 7．下列算法实现求采用顺序结构存储的串s和串t的一个最长公共子串。 26 void maxcomstr(orderstring *s,*t; int index, length) {int i,j,k,length1,con; 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)i+k<=s.len && j+k<=t.len && s[i+k]==t[j+k] { length1=length1+1;k=k+1; } else (2) con=0 __; if (length1>length) { index=i; length=length1; } (3)__ j+=k __; 27 } else (4) j++ ___; } (5) i++ __ } } -------------------------------------------------------------------------------- 习题五 数组和广义表 一、单项选择题 1．常对数组进行的两种基本操作是（ C ） A.建立与删除 B. 索引与修改 C. 查找与修改 D. 查找与索引 2．对于C语言的二维数组DataType A[m][n],每个数据元素占K个存储单元，二维数组中任意元素a[i,j] 的存储位置可由( C )式确定. A.Loc[i,j]=A[m,n]+[(n+1)*i+j]*k B.Loc[i,j]=loc[0,0]+[(m+n)*i+j]*k 28 C.Loc[i,j]=loc[0,0]+[(n+1)*i+j]*k D.Loc[i,j]=[(n+1)*i+j]*k 3．稀疏矩阵的压缩存储方法是只存储 ( A ) A.非零元素 B. 三元祖（i,j, aij） C. aij D. i,j 4. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( A )。 A. 1175 B. 1180 C. 1205 D. 1210 5. A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（ B ）。 A. i（i-1）/2+j B. j（j-1）/2+i C. i（j-i）/2+1 D. j（i-1）/2+1 6. 用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j 沿链移动的操作为( A )。 A. j=r[j].next B. j=j+1 C. j=j->next D. j=r[j]-> next 7. 对稀疏矩阵进行压缩存储目的是（ C ）。 A．便于进行矩阵运算 B．便于输入和输出 29 C．节省存储空间 D．降低运算的时间复杂度 8. 已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是( C )。 A. head(tail(LS)) B. tail(head(LS)) C. head(tail(head(tail(LS))) D. head(tail(tail(head(LS)))) 9. 广义表（（a,b,c,d））的表头是（ ），表尾是（ C ）。 A. a B.（） C.（a,b,c,d） D.（b,c,d） 10. 设广义表L=（（a,b,c）），则L的长度和深度分别为（ C ）。 A. 1和1 B. 1和3 C. 1和2 D. 2和3 11. 下面说法不正确的是( A )。 A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表 C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构 二、填空题 1．通常采用_____顺序______存储结构来存放数组 。对二维数组可有两种存储方法：一 30 种是以_____列序______为主序的存储方式，另一种是以____行序_______为主序的存储方式。 2. 用一维数组B与列优先存放带状矩阵A中的非零元素A[i,j] (1≤i≤n,i-2≤j≤i+2),B中的第8个元素是A 中的第_ 第1 _行，第_ 第3 _列的元素。 3．设n行n列的下三角矩阵A已压缩到一维数组B[1..n*（n+1）/2]中，若按行为主序存储，则A[i,j]对应的B中存储位置为__i(i-1)/2+j (1<=i,j<=n)_____。 4. 所谓稀疏矩阵指的是_ 非零元很少(t< 6．设广义表L=((),()), 则head(L)是 （） ；tail(L)是（ （）） ；L的长度是 2 ；深度是 2 __。 7．基于三元组的稀疏矩阵转置的处理方法有两种，以下运算按照矩阵A的列序来进行转置，请在___________处用适当的句子用以填充。 Trans_Sparmat(SpMatrixTp a,SpMatrixTp *b) { (*b).mu=a.nu;(*b).nu=a.mu;(*b).tu=a.tu; 31 if(a.tu) { q=1; for(col=1; __col<=a.nu_________;col++) for(p=1;p<=a.tu;p++) if(____a.data[p].j_______==col) {(*b).data[q].i=a.data[p].j; (*b).data[q].j=a.data[p].i; (*b).data[q].v=a.data[p].v; ____q++_______; } } 8. 完善下列程序。下面是一个将广义表逆置的过程。例如原来广义表为（（a,b）,c,（d,e）），经逆置后为：（（e,d）,c,（b,a））。 typedef struct glistnode 32 {int tag; struct glistnode *next; union{char data; struct{struct glistnode *hp,*tp;}ptr; }val; }*glist,gnode; glist reverse(p) glist p; {glist q,h,t,s; if(p==NULL) q=NULL; else {if(1) (p->tag==0) //处理原子 { q=(glist)malloc(sizeof(gnode)); q->tag=0; q->val.data=p->val.data; } 33 else {(2) h=reverse(p->val.ptr.hp) //处理表头 if (3) (p->val.ptr.tp) //产生表尾的逆置广义表 {t=reverse(p->val.ptr.tp); s=t; while(s->val.ptr.tp!=NULL) s=s->val.ptr.tp; s->val.ptr.tp=(glist)malloc(sizeof(gnode)); s=s->val.ptr.tp;s->tag=1;s->val.ptr.tp=NULL; s->val.ptr.hp=h; (4) s->val.ptr.tp=t; //连接 __ } else {q=(glist)malloc(sizeof(gnode));q->tag=1; q->val.ptr.tp=NULL; (5) q->val.ptr.hp=h//头结点指向广义表 ; } } } return(q); } 34 因篇幅问题不能全部显示，请点此查看更多更全内容