实用数据结构基础参考答案.pdf

《实用数据结构基础参考答案.pdf》由会员分享，可在线阅读，更多相关《实用数据结构基础参考答案.pdf（70页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、单元练习 1 一判断题（下列各题，正确的请在前面的括号内打；错误的打）（）（1）数据的逻辑结构与数据元素本身的内容和形式无关。（）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（）（3）数据元素是数据的最小单位。（）（4）数据的逻辑结构和数据的存储结构是相同的。（）（5）程序和算法原则上没有区别，所以在讨论数据结构时可以通用。（）（6）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。（）（7）数据的存储结构是数据的逻辑结构的存储映像。（）（8）数据的物理结构是指数据在计算机内实际的存储形式。（）（9）数据的逻辑结构是依赖于计算机的。（）（10）算法是对

2、解题方法和步骤的描述。二填空题（1）数据有逻辑结构和 存储结构 两种结构。（2）数据逻辑结构除了集合以外，还包括：线性结构、树形结构和 图形结构 。（3）数据结构按逻辑结构可分为两大类，它们是线性结构和 非线性结构 。（4）树形结构 和 图形结构 合称为非线性结构。（5）在树形结构中，除了树根结点以外，其余每个结点只有 1 个前趋结点。（6）在图形结构中，每个结点的前趋结点数和后续结点数可以 任意多个 。（7）数据的存储结构又叫 物理结构 。（8）数据的存储结构形式包括：顺序存储、链式存储、索引存储和 散列存储 。（9）线性结构中的元素之间存在 一对一 的关系。（10）树形结构结构中的元素之间

3、存在 一对多 的关系，（11）图形结构的元素之间存在 多对多 的关系。（12）数据结构主要研究数据的逻辑结构、存储结构和 算法（或运算）三个方面的内容。（13）数据结构被定义为(D，R)，其中 D 是数据的有限集合，R 是 D 上的 关系 的有限集合。（14）算法是一个 有穷指令 的集合。（15）算法效率的度量可以分为事先估算法和 事后统计法 。（16）一个算法的时间复杂性是算法 输入规模 的函数。（17）算法的空间复杂度是指该算法所耗费的 存储空间 ，它是该算法求解问题规模 n的函数。（18）若一个算法中的语句频度之和为 T（n）=6n+3nlog2n，则算法的时间复杂度为 O（nlog2n

4、）。（19）若一个算法中的语句频度之和为 T（n）=3n+nlog2n+n2，则算法的时间复杂度为 O（n2）。（20）数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 ，以及它们之间的关系和运算的学科。三选择题（1）数据结构通常是研究数据的（A ）及它们之间的相互联系。A.存储结构和逻辑结构 B.存储和抽象 C.联系和抽象 D.联系与逻辑（2）在逻辑上可以把数据结构分成：（C ）。A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构（3）数据在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为（C ）。A.存储结构 B

5、.逻辑结构 C.顺序存储结构 D.链式存储结构（4）非线性结构中的每个结点（D ）。A.无直接前趋结点 B.无直接后继结点 C.只有一个直接前趋结点和一个直接后继结点 D.可能有多个直接前趋结点和多个直接后继结点（5）链式存储的存储结构所占存储空间（A ）。A 分两部分，一部分存放结点的值，另一部分存放表示结点间关系的指针 B 只有一部分，存放结点的值 C 只有一部分，存储表示结点间关系的指针 D 分两部分，一部分存放结点的值，另一部分存放结点所占单元素（6）算法的计算量大小称为算法的（C ）。A.现实性 B.难度 C.时间复杂性 D.效率（7）数据的基本单位是（B ）。A.数据结构 B.数据

6、元素 C.数据项 D.文件（8）每个结点只含有一个数据元素，所有存储结点相继存放在一个连续的存储区里，这种存储结构称为（A ）结构。A.顺序存储 B.链式存储 C.索引存储 D.散列存储（9）每一个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是（B ）存储方式。A.顺序 B.链式 C.索引 D.散列（10）以下任何两个结点之间都没有逻辑关系的是（D ）。A.图形结构 B.线性结构 C.树形结构 D.集合（11）在数据结构中，与所使用的计算机无关的是（C ）。A.物理结构 B.存储结构 C.逻辑结构 D.逻辑和存储结构（12）下列四种基本逻辑结构中，数据元素之间关系最弱的是（A ）。

7、A.集合 B.线性结构 C.树形结构 D.图形结构（13）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（A ）。A.逻辑结构 B.存储结构 C.逻辑实现 D.存储实现（14）每一个存储结点只含有一个数据元素，存储结点存放在连续的存储空间，另外有一组指明结点存储位置的表，该存储方式是（C ）存储方式。A.顺序 B.链式 C.索引 D.散列（15）算法能正确的实现预定功能的特性称为算法的（A ）。A.正确性 B.易读性 C.健壮性 D.高效性（16）算法在发生非法操作时可以作出处理的特性称为算法的（C ）。A.正确性 B.易读性 C.健壮性 D.高效性（17）下列时间复杂度中最坏的是（

8、D ）。A.O（1）B.O（n）C.O（log2n）D.O（n2）（18）下列算法的时间复杂度是（D ）。for (i=0;in;i+)for (j=0;in;j+)cij=i+j;A.O（1）B.O（n）C.O（log2n）D.O（n2）（19）算法分析的两个主要方面是（A ）。A.空间复杂性和时间复杂性 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性（20）计算机算法必须具备输入、输出和（C ）。A.计算方法 B.排序方法 C.解决问题的有限运算步骤 D.程序设计方法 四分析下面各程序段的时间复杂度（1）for(i=0;in;i+)for(j=0;jm;j+)Aij 解

9、：O(n*m)（2）s=0;for(i=0;in;i+)for(j=0;jn;j+)s+=Bij;sum=s;解：O(n2)（3）T=A；A=B；B=T；解：O(1)（4）s1(int n)int p=1,s=0;for(i=1;i=n;i+)p*=i;s+=p;return(s);O(n)（5）s2(int n)x=0;y=0;for(k=1;k=n;k+)x+;for(i=1;i=n;i+)for(j=1;j=n;j+)y+;解：O(n2)五 根据二元组关系，画出对应逻辑图形的草图，指出它们属于何种数据结构。（1）A=（D，R），其中：D=a，b，c，d，e，R=解：a b c d e 属

10、于集合 （2）B=（D,R），其中：D=a,b,c,d,e,f，R=r R=,（尖括号表示结点之间关系是有向的）解：属于线性结构。（3）F=（D,R），其中：D=50,25,64,57,82,36,75,55，R=r R=,解：属于树结构 （4）C=（D,R），其中：D=1,2,3,4,5,6，R=r R=(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)（园括号表示结点之间关系是有向的）解：属于图结构 1 2 6 3 4 5 25 50 75 57 36 82 64 55 b a e d f c（5）E=（D,R），其中：D=a,b,c,d,e,f

11、,g,h，R=r R=,解：属于树结构。c b d f e a h g 单元练习 2 一判断题（下列各题，正确的请在前面的括号内打；错误的打）（）（1）线性表的链式存储结构优于顺序存储。（）（2）链表的每个结点都恰好包含一个指针域。（）（3）在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。（）（4）顺序存储方式的优点是存储密度大，插入、删除效率高。（）（5）线性链表的删除算法简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。（）（6）顺序表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（）（7）线性表链式存储的特点是可以用一组任

12、意的存储单元存储表中的数据元素。（）（8）线性表采用顺序存储，必须占用一片连续的存储单元。（）（9）顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。（）（10）插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。二填空题（1）顺序表中逻辑上相邻的元素在物理位置上 必须 相连。（2）线性表中结点的集合是有限的，结点间的关系是 一对一 关系。（3）顺序表相对于链表的优点是：节省存储 和随机存取。（4）链表相对于顺序表的优点是：插入、删除 方便。（5）采用 顺序 存储结构的线性表叫顺序表。（6）顺序表中访问任意一个结点的时间复杂度均为 O(1)。（7）链表相对于顺序

13、表的优点是插入、删除方便；缺点是存储密度 小 。（8）在双链表中要删除已知结点*P，其时间复杂度为 O(1)。（9）在单链表中要在已知结点*P 之前插入一个新结点，需找到*P 的直接前趋结点的地址，其查找的时间复杂度为 O(n)。（10）单链表中需知道 头指针 才能遍历整个链表。（11）性表中第一个结点没有直接前趋，称为 开始 结点。（12）在一个长度为 n 的顺序表中删除第 i 个元素，要移动 n-i 个元素。（13）在一个长度为 n 的顺序表中，如果要在第 i 个元素前插入一个元素，要后移 n-i+1 个元素。（14）在无头结点的单链表中，第一个结点的地址存放在头指针中，而其它结点的存储地

14、址存放在前趋 结点的指针域中。（15）当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快速度存取线性表中的元素时，应采用 顺序 存储结构。（16）在线性表的链式存储中，元素之间的逻辑关系是通过 指针 决定的。（17）在双向链表中，每个结点都有两个指针域，它们一个指向其 前趋 结点，另一个指向其 后继结点。（18）对一个需要经常进行插入和删除操作的线性表，采用 链式 存储结构为宜。（19）双 链 表 中，设 p 是 指 向 其 中 待 删 除 的 结 点，则 需 要 执 行 的 操 作 为：p-prior-next=p-next 。（20）在如图所示的链表中，若在指针P所在的结点

15、之后插入数据域值为a和b的两个结点，则可用下列两个语句：S-next-next=P-next;和P-next=S;来实现该操作。a b 三选择题（1）在具有 n 个结点的单链表中，实现（A ）的操作，其算法的时间复杂度都是 O（n）。A遍历链表或求链表的第 i 个结点 B 在地址为 P 的结点之后插入一个结点 C删除开始结点 D删除地址为 P 的结点的后继结点（2）设 a、b、c 为三个结点，p、10、20 分别代表它们的地址，则如下的存储结构称为（B ）。A 循环链表 B 单链表 C双向循环链表 D 双向链表（3）单链表的存储密度（C ）。A 大于 1 B 等于 1 C小于 1 D 不能确定

16、（4）已知一个顺序存储的线性表，设每个结点占 m 个存储单元，若第一个结点的地址为 B，则第 i 个结点的地址为（A ）。A B+(i-1)*m BB+i*m C B-i*m D B+(i+1)*m（5）在有 n 个结点的顺序表上做插入、删除结点运算的时间复杂度为（B ）。AO（1）BO（n）CO（n2）DO（log2n）（6）设 Llink、Rlink 分别为循环双链表结点的左指针和右指针，则指针 P 所指的元素是双循环链表 L 的尾元素的条件是（D ）。a 10 c b 20 P P S AP=L BP-Llink=L CP=NULL DP-Rlink=L （7）两个指针 P 和 Q，分别

17、指向单链表的两个元素，P 所指元素是 Q 所指元素前驱的条件是（B ）。AP-next=Q-next BP-next=Q CQ-next=P DP=Q（8）用链表存储的线性表，其优点是（C ）。A 便于随机存取 B 花费的存储空间比顺序表少 C 便于插入和删除 D 数据元素的物理顺序与逻辑顺序相同（9）在单链表中，增加头结点的目的是（C ）。A 使单链表至少有一个结点 B 标志表中首结点的位置 C 方便运算的实现 D 说明该单链表是线性表的链式存储结构（10）下面关于线性表的叙述中，错误的是（D ）关系。A顺序表必须占一片地址连续的存储单元 B顺序表可以随机存取任一元素 C链表不必占用一片地址

18、连续的存储单元 D链表可以随机存取任一元素 （11）L 是线性表，已知 LengthList（L）的值是 5，经 DelList（L，2）运算后，LengthList（L）的值是（C ）。A2 B3 C4 D5 （12）单链表的示意图如下：L A B C D 指向链表 Q 结点的前趋的指针是（B ）。AL BP CQ DR （13）设 p 为指向单循环链表上某结点的指针，则*p 的直接前驱（C ）。A找不到 B查找时间复杂度为 O（1）C查找时间复杂度为 O（n）D查找结点的次数约为 n（14）等概率情况下，在有 n 个结点的顺序表上做插入结点运算，需平均移动结点的数目为（C ）。An B(n

19、-1)/2 C n/2 D(n+1)/2 （15）在下列链表中不能从当前结点出发访问到其余各结点的是（C ）。A双向链表 B单循环链表 C单链表 D双向循环链表 P Q R（16）在顺序表中，只要知道（D ），就可以求出任一结点的存储地址。A基地址 B结点大小 C 向量大小 D基地址和结点大小 （17）在双链表中做插入运算的时间复杂度为（A ）。AO（1）BO（n）CO（n2）DO（log2n）（18）链表不具备的特点是（A ）。A随机访问 B不必事先估计存储空间 C插入删除时不需移动元素 D所需空间与线性表成正比（19）以下关于线性表的论述，不正确的为（C ）。A线性表中的元素可以是数字、字

20、符、记录等不同类型 B线性顺序表中包含的元素个数不是任意的 C线性表中的每个结点都有且仅有一个直接前趋和一个直接后继 D存在这样的线性表，即表中没有任何结点 （20）在（B ）的运算中，使用顺序表比链表好。A插入 B根据序号查找 C 删除 D根据元素查找 四分析下述算法的功能（1）（2）ListNode*Demo1(LinkList L,ListNode*p)/L 是有头结点的单链表 ListNode*q=L-next;While(q&q-next!=p)q=q-next;if(q)void Demo2(ListNode*p,ListNode*q)/p,*q 是链表中的两个结点 DataTyp

21、e temp;temp=p-data;p-data=q-data;解：（1）返回结点*p 的直接前趋结点地址。（2）交换结点*p 和结点*q（p 和 q 的值不变）。五 程序填空 （1）已知线性表中的元素是无序的，并以带表头结点的单链表作存储。试写一算法，删除表中所有大于 min，小于 max 的元素，试完成下列程序填空。Void delete(lklist head;datatype min,max)q=head-next;while(p!=NULL)if (p-datadata=max )q=p;p=p-next ;else q-next=p-next ;delete(p);p=q-nex

22、t ;（2）在带头结点 head 的单链表的结点 a 之后插入新元素 x，试完成下列程序填空。struct node elemtype data;node*next;void lkinsert(node*head,elemtype x)node*s,*p;s=new node ;s-data=x ;p=head-next;while(p!=NULL)&(p-data!=a)_p=p-next ;if(p=NULL)coutnext=p-next_;_ p-next=s _;六算法设计题（1）写一个对单循环链表进行遍历（打印每个结点的值）的算法，已知链表中任意结点的地址为 P。解：void Sh

23、ow(ListNode*P)ListNode*t=P;do printf(%c,t-data);t=t-rear;while(t!=P);（2）对给定的带头结点的单链表 L，编写一个删除 L 中值为 x 的结点的直接前趋结点的算法。解：void delete(ListNode*L)ListNode*p=L,*q;if(L-next-data=X)printf(“值为 x 的结点是第一个结点，没有直接前趋结点可以删除”);return;For(p-next-data!=X;q=p;p=p-next);MAXLEN-1中，进栈操作时要执行的语句有：S-top +。（或=S-top+1）（9）链栈L

24、S，指向栈顶元素的指针是 LS-next 。（10）从一个栈删除元素时，首先取出 栈顶元素 ，然后再移动栈顶指针。（11）由于链栈的操作只在链表的头部进行，所以没有必要设置 头 结点。（12）已知顺序栈 S，在对 S 进行进栈操作之前首先要判断 栈是否满 。（13）已知顺序栈 S，在对 S 进行出栈操作之前首先要判断 栈是否空 。（14）若内存空间充足，链 栈可以不定义栈满运算。（15）链栈LS是空的条件是 LS-next=NULL 。（16）链栈LS的栈顶元素是链表的 首 元素。（17）同一栈的各元素的类型 相同 。（18）若进栈的次序是 A、B、C、D、E，执行三次出栈操作以后，栈顶元素为

25、 B 。（19）A+B/C-D*E 的后缀表达式是：ABC/+DE*-。（20）四个元素按A、B、C、D顺序进S栈，执行两次Pop（S，x）运算后，x的值是 C 。三选择题（1）插入和删除只能在一端进行的线性表，称为(C )。A队列 B循环队列 C栈 D循环栈 （2）设有编号为1，2，3，4的四辆列车，顺序进入一个栈结构的站台，下列不可能的出站顺序为(D )A1234 B1243 C1324 D1423（3）如果以链表作为栈的存储结构，则出栈操作时（B ）A必须判别栈是否满 B必须判别栈是否空 C必须判别栈元素类型 D队栈可不做任何判别（4）元素A,B,C,D依次进栈以后，栈顶元素是（D ）A

26、A BB CC DD（5）顺序栈存储空间的实现使用（B ）存储栈元素。A链表 B数组 C循环链表 D变量（6）在C或C+语言中，一个顺序栈一旦被声明，其占用空间的大小（A ）。A已固定 B不固定 C可以改变 D动态变化（7）带头结点的链栈LS的示意图如下，栈顶元素是（A ）LS H A B C D AA BB CC DD（8）链栈与顺序栈相比，有一个比较明显的优点是（B ）。A插入操作更加方便 B通常不会出现栈满的情况。C不会出现栈空的情况 D删除操作根加方便（9）从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行下列(D )命令。Ax=top;top=top-next

27、;Btop=top-next;x=top-data;Cx=top-data;Dx=top-data;top=top-next;（10）在一个栈顶指针为HS的链栈中，将一个S指针所指的结点入栈，应执行下列(B )命令。AHS-next=S;BS-next=HS-next;HS-next=S;CS-next=HS-next;HS=S;DS-next=HS;HS=HS-next;（11）四个元素按A、B、C、D顺序进S栈，执行两次Pop（S，x）运算后，栈顶元素的值是（B ）。AA BB CC DD（12）元素A,B,C,D依次进栈以后，栈底元素是（A ）。AA BB CC DD（13）经过下列栈的

28、运算后，再执行ReadTop(s)的值是（A ）。InitStack(s)（初始化栈）;Push(s,a);Push(s,b);Pop(s)Aa Bb C1 D0（14）经过下列栈的运算后，x的值是（B ）。InitStack(s)（初始化栈）;Push(s,a);Push(s,b);ReadTop(s);Pop(s,x);Aa Bb C1 D0（15）经过下列栈的运算后，x的值是（B ）。InitStack(s)（初始化栈）;Push(s,a);Pop(s,x);Push(s,b);Pop(s,x);Aa Bb C1 D0（16）经过下列栈的运算后，SEmpty(s)的值是（C ）。Init

29、Stack(s)（初始化栈）;Push(s,a);Push(s,b);Pop(s,x);Pop(s,x);Aa Bb C1 D0（17）向顺序栈中压入元素时，（B ）。A 先存入元素，后移动栈顶指针 B先移动栈顶指针，后存入元素 C谁先谁后无关紧要 D同时进行（18）初始化一个空间大小为5的顺序栈S后，S-top的值是（B ）。A0 B-1 C不再改变 D动态变化（19）一个栈的入栈次序ABCDE，则栈的不可能的输出序列是(C )。AEDCBA BDECBA CDCEAB DABCDE（20）设有一个顺序栈S，元素A,B,C,D,E,F,依次进栈，如果六个元素出栈的顺序是B，D，C，F，E，A

30、，则栈的容量至少应是(A )。A3 B4 C5 D 6 四应用题（1）设有一个栈，元素进栈的次序为：A，B，C，D，E，用I表示进栈操作，O表示出栈操作，写出下列出栈的操作序列。C，B，A，D，E A，C，B，E，D 解：IIIOOOIOIO IOIIOOIIOO （2）求后缀表达式 ABC/D 解：A B C D/-A+B*C+D/E 解：0 A B C*+D E/+A*(B+C)*D-E 解：A B C+*D*E-(A+B)*C-E/(F+G/H)-D 解：A B+C*E F G H/+/-D-8/(5+2)-6 解：8 5 2+/6-六算法设计题（1）设用一维数组stackn表示一个堆栈

31、，若堆栈中每个元素需占用M个数组单元（M1）。试写出其入栈操作的算法。试写出其出栈操作的算法。解：10 B0.9 C1.9 D1.10（9）若进队的序列为：A，B，C，D，则出队的序列是（C ）。AB，C，D，A BA，C，B，D CA，B，C，D DC，B，D，A（10）四个元素按：A，B，C，D顺序连续进队Q，则队尾元素是（D ）。A A B B C C D D（11）四个元素按：A，B，C，D顺序连续进队Q，执行一次OutQueue(Q)操作后，队头元素是（B ）。A A B B C C D D（12）四个元素按：A，B，C，D顺序连续进队Q，执行四次OutQueue(Q)操作后，再执行

32、QEmpty(Q);后的值是（B ）。A 0 B 1 C 2 D 3（13）队列Q，经过下列运算后，x 的值是（B ）。InitQueue(Q)(初始化队列);InQueue(Q,a);InQueue(Q,b);OutQueue(Q,x);ReadFront(Q,x);Aa Bb C0 D1（14）循环队列SQ队满的条件是(B )。ASQ-rear=SQ-front B(SQ-rear+1)%MAXLEN=SQ-front CSQ-rear=0 DSQ-front=0（15）设链栈中结点的结构：data为数据域，next为指针域，且top是栈顶指针。若想在链栈的栈顶插入一个由指针s所指的结点，

33、则应执行下列（A ）操作。As-next=top-next；top-next=s；Btop-next=s；Cs-next=top；top=top-next；Ds-next=top；top=s；（16）带头结点的链队列LQ示意图如下，链队列的队头元素是（A ）LQ-front H A B C D LQ-rear AA BB CC DD（17）带头结点的链队列LQ示意图如下，指向链队列的队头指针是（C ）LQ-front H A B C D LQ-rear ALQ-front BLQ-rear CLQ-front-next DLQ-rear-next（18）带 头 结 点 的 链 队 列 LQ示

34、意 图 如 下，在 进 行 进 队 运 算 时 指 针 LQ-front（A ）LQ-front H A B C D LQ-rear A始终不改变 B有时改变 C进队时改变 D出队时改变（19）队列Q，经过下列运算后，再执行QEmpty(Q)的值是（C ）。InitQueue(Q)(初始化队列);InQueue(Q,a);InQueue(Q,b);OutQueue(Q,x);ReadQueue(Q,x);Aa Bb C0 D1（20）若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front 和rear的值分别为(B

35、)。A5和1 B4和2 C2和4 D1和5 四 写出程序运行的结果 写出下列程序段的输出结果（队列中的元素类型为 char）。void main()Queue Q;InitQueue(Q);算法设计题（1）设一个循环队列Queue，只有头指针front，不设尾指针，另设一个含有元素个数的记数器cont，试写出相应的入队算法和出队算法。解：MAXLEN-1表示队列时，该队列只有一个头指针front，不设尾指针，而改置一个记数器count用以记录队列中结点的个数。试编写一个能实现：初始化队列、判队空、读队头元素、入队操作和出队操作的算法。解：以顺序存储 B数据元素是一个字符 C.可以链接存储 D数

36、据元素可以是多个字符（2）某串的长度小于一个常数，则采用（B ）存储方式最节省空间。A链式 B顺序 C堆结构 D无法确定（3）以下论述正确的是（C ）。A空串与空格串是相同的 B tel是Teleptone的子串 C空串是零个字符的串 D.空串的长度等于1（4）以下论述正确的是（B ）。A空串与空格串是相同的 B ton是Teleptone的子串 C空格串是有空格的串 D.空串的长度等于1（5）以下论断正确的是(A )。A是空串，空格串 BBEIJING是BEI JING的子串 CsomethingSomethig DBIT=BITE（6）设有两个串S1和S2，则EqualStr(S1,S2)

37、运算称作(D )。A.串连接 B模式匹配 C.求子串 D串比较（7）串的模式匹配是指（D ）。A判断两个串是否相等 C找某字符在主串中第一次出现的位置 B对两个串比较大小 D 找某子串在主串中第一次出现的第一个字符位置（8）若字符串ABCDEFG采用链式存储，假设每个字符占用1个字节，每个指针占用2个字节。则该字符串的存储密度为(D )。A20 B40 C50 D333（9）若字符串ABCDEFG采用链式存储，假设每个指针占用2个字节，若希望存储密度50，则每个结点应存储(A )个字符。A2 B3 C4 D5（10）设串S1=I AM，S2=A SDUDENT,则ConcatStr(S1,S2

38、)=(B )。AI AM BI AM A SDUDENT CIAMASDUDENT D.A SDUDENT（11）设S=，则LenStr（S）=（A ）。A0 B1 C2 D3（12）设目标串T=AABBCCDDE，模式P=ABCDE，则该模式匹配的有效位移为(A )。A0 B1 C2 D3（13）设目标串T=AABBCCDDEEFF，模式P=CCD，则该模式匹配的有效位移为(D )。A2 B3 C4 D.5（14）设目标串T=aabaababaabaa，模式P=abab,朴素匹配算法的外层循环进行了(D )次。A1 B9 C4 D5（15）朴素模式匹配算法在最坏情况下的时间复杂度是(D )。

39、AO（m）BO（n）C0（m+n）D0（m*n）（16）S=morning，执行求子串函数SubStr(S,2,2)后的结果为(B )。Amo Bor Cin Dng（17）S1=good，S2=morning，执行串连接函数ConcatStr(S1,S2)后的结果为(A )。Agoodmorning Bgood morning CGOODMORNING DGOOD MORNING（18）S1=good，S2=morning，执行函数SubStr(S2,4,LenStr(S1)后的结果为(B )。Agood Bning Cgo Dmorn（19）设串S1=ABCDEFG，S2=PQRST,则

40、ConcatStr(SubStr(S1,2,LenStr(S2),SubStr(S1,LenStr(S2),2)的 结 果 串为(D )。ABCDEF BBCDEFG CBCPQRST D.BCDEFEF（20）若串 S=SOFTWARE，其子串的数目最多是：（C ）。A35 B36 C37 D38 （8+7+6+5+4+3+2+1+1=37）四程序题填空（1）下面程序是把两个串 r1 和 r2 首尾相连的程序，即：r1=r1+r2，试完成程序填空。typedef Struct（1）char vecMAXLEN;20.3的实际地址上2000，元素长度是4，则LOC1,2=2024 。LOC1,

41、2=2000+（1*4+2）*4（6）稀疏矩阵的三元组有 3 列。（7）稀疏矩阵的三元组中第1列存储的是数组中非零元素所在的 行数 。（8）n阶对称矩阵，如果只存储下三角元素，只需要 n（n-1）/2 个存储单元。（9）稀疏矩阵A如下图所示，其非零元素存于8 0 0 0 0 0 0 11 0 0 0 0 0 0 0 6 0 0 0 3 0 0 7 0 A=三元组表中，三元组（4，1，5）按列优先顺序存储在三元组表的第 4 项。（10）稀疏疏矩阵的压缩存储方法通常有三元组表和 十字链表 两种。（11）任何一个非空广义表的表尾必定是 广义表（或子表）。（12）tail(head(a,b),(c,d

42、)=b 。（13）设广义表(a,b,c)，则将c分离出来的运算是 head(tail(tail(head(L)。（14）广义表(a,b),c,d)，表尾是 （c,d）。（15）n阶下三角矩阵，因为对角线的上方是同一个常数，需要 n（n-1）/2+1 个存储单元。（16）稀疏矩阵中有 n 个非零元素，则三元组有 n 行。（17）广义表LS=（a,(b),(c,(d)）的长度是 3 。（18）广义表LS=（a,(b),(c,(d)）的深度是 4 。（19）广义表L=（），L），则L的深度是 。（20）广义表LS=（a,(b),(c,(d)）的表尾是 (b),(c,(d)。三选择题（1）在一个m维数

43、组中，（D ）恰好有m个直接前驱和m个直接界后继。A.开始结点 B总终端结点 C.边界结点 D内部结点（2）对下述矩阵进行压缩存储后，失去随机存取功能是（D ）。A对称矩阵 B三角矩阵 C三对角矩阵 D稀疏矩阵（3）在按行优先顺序存储的三元组表中，下述陈述错误的是（D ）。A 同一行的非零元，是按列号递增次序存储的 B 同一列的非零元，是按行号递增次序存储的 C 三元组表中三元组行号递增的 D 三元组表中三元组列号递增的（4）对稀疏矩阵进行压缩存储是为了（B ）。A降低运算时间 B节约存储空间 C便于矩阵运算 D便于输入和输出（5）若数组A0.m0.n按列优先顺序存储，则aij的地址为（A ）

44、。ALOC(a00)+j*m+i BLOC(a00)+j*n+i CLOC(a00)+(j-1)*n+i-1 DLOC(a00)+(j-1)*m+i-1（6）下列矩阵是一个（B ）A对称矩阵 B三角矩阵 C稀疏矩阵 D带状矩阵（7）在稀疏矩阵的三元组表示法中，每个三元组表示（D ）。A 矩阵中非零元素的值 B 矩阵中数据元素的行号和列号 C 矩阵中数据元素的行号、列号和值 D 矩阵中非零数据元素的行号、列号和值（8）已知二维数组A610，每个数组元素占4个存储单元，若按行优先顺序存放数组元素a35的存储地址是1000，则a00的存储地址是（B ）。A872 B860 C868 D864 100

45、0=B+(3*10+5)*4 B=1000-(3*10+5)*4=1000-140=860（9）广义表是线性表的推广，它们之间的区别在于（A ）。A能否使用子表 B能否使用原子项 C是否能为空 D表的长度（10）下列广义表属于线性表的是（B ）。AE=(a,E)BE=(a,b,c)CE=(a,(b,c)DE=(a,L)；L=()（11）广义表(a,b),c,d)的表尾是(D )。Aa Bd C(a,b)D(c,d)（12）广 义 表 A=(x,(a,b),(x,(a,b),y),则 运 算 head(head(tail(A)为（A ）。Ax B（a，b）C(x,(a,b)DA（13）tail(

46、head(a,b),c,(c,d)的结果是（B ）。Ab B（b）C(a,b)D(d)（14）若广义表满足 head（L）=tail（L），则 L 的形式是（B ）A空表 B若L=(a1,an),则a1=(a2,an)C若L=(a1,an),则a1=a2=an)D(a1),(a1)（15）数组是一个（B ）线性表结构。A非 B推广了的 C加了限制的 D不加限制的（16）数组A0:1,0:1,0:1共有（D ）元素。A4 B5 C6 D8（17）广义表(a,b),c,d)的表头是(C )。Aa Bd C(a,b)D(c,d)（18）广义表A=(a),则表尾为(C )。Aa B()C空表 D(a)

47、（19）以下（C ）是稀疏矩阵的压缩存储方法。A一维数组 B二维数组 C三元组表 D广义表（20）设广义表 D=(a,b,c,D),其深度为（D ）。A2 B3 C4 D 四算法阅读题（1）已知 A是一个下三角矩阵，下述算法的功能是什么 int f1(int A,int n)int i,k,s=0;(n+1)n/2-1存放下三角元素 k=0;s=A0;for(i=0;idatak.v ;return sum;五 编程题（1）试编写求一个三元组表的稀疏矩阵对角线元素之和的算法。#include#define ERROR-99999 typedef struct int row;int col;i

48、nt data;Triple;int MDSum(Triple*a)int i;int sum=0;if(a0.row!=a0.col)return ERROR;for(i=1;itag=0)return(atomnum(head-next)+1);else return(atomnum(head-next)+atomnum(head-);（3）试编写求广义表最大中原子元素个数的算法。int maxele(Gnode*head)int m=0,a;while(head)if(head-tag=1)a=maxele(head-;if(am)m=a;else if(head-m)m=head-;h

49、ead=head-next;return m;单元练习 7 一判断题（下列各题，正确的请在前面的括号内打；错误的打）（）（1）树结构中每个结点最多只有一个直接前驱。（）（2）完全二叉树一定是满二查树。（）（3）在中序线索二叉树中，右线索若不为空，则一定指向其双亲。（）（4）一棵二叉树中序遍历序列的最后一个结点，必定是该二叉树前序遍历的最后一个结点。（）（5）二叉树的前序遍历中，任意一个结点均处于其子女结点的前面。（）（6）由二叉树的前序遍历序列和中序遍历序列，可以推导出后序遍历的序列。（）（7）在完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。（）（8）在哈夫曼编码中，当两个字符出现的

50、频率相同，其编码也相同，对于这种情况应该做特殊处理。（）（9）含多于两棵树的森林转换的二叉树，其根结点一定无右孩子。（）（10）具有 n 个叶子结点的哈夫曼树共有 2n-1 个结点。二填空题（1）在树中，一个结点所拥有的子树数称为该结点的 度 。（2）度为零的结点称为 叶（或叶子，或终端）结点。（3）树中结点的最大层次称为树的 深度（或高度）。（4）对于二叉树来说，第 i 层上至多有 2i-1 个结点。（5）深度为 h 的二叉树至多有 2h-1 个结点。（6）由一棵二叉树的前序序列和 中序 序列可唯一确定这棵二叉树。（7）有 20 个结点的完全二叉树，编号为 10 的结点的父结点的编号是 5