第一章 引论

第1讲 数据结构的基本概念-1(总时长15分18秒)随堂测验

1、数据的逻辑结构有几种?
    A、4
    B、3
    C、2
    D、1

2、数据的存储结构包括?
    A、线性结构和非线性结构
    B、静态结构和非静态结构
    C、顺序结构和非顺序结构
    D、动态结构和非动态结构

第2讲 数据结构的基本概念-2(总时长11分12秒)随堂测验

1、数据的逻辑结构包括?
    A、线性结构和非线性结构
    B、顺序结构和非顺序结构
    C、静态结构和非静态结构
    D、动态结构和非动态结构

第3讲 数据结构的基本概念-3(总时长10分29秒)随堂测验

1、数据结构包括数据的逻辑结构、存储结构以及相关运算。

第4讲 数据的逻辑结构和存储结构(总时长11分19秒)随堂测验

1、数据的逻辑结构和机器无关。

第5讲 算法及其时间复杂度(总时长14分59秒)随堂测验

1、时间复杂度和频度是一样的。

第6讲 时间复杂度及应用(总时长10分44秒)随堂测验

1、一个算法包含的循环嵌套的层数越多,该算法的时间复杂度越高。

在线练习1

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、某算法的时间复杂度是O(n2),表明该算法的( )。
    A、执行时间与n2成正比
    B、问题规模是n2
    C、执行时间等于n2
    D、问题规模与n2成正比

7、衡量算法效率优劣的不包括( )。
    A、正确性和可读性
    B、健壮性/鲁棒性
    C、高效率与低存储
    D、现实性

8、算法指( )。
    A、计算方法
    B、排序方法
    C、解决问题的步骤序列
    D、调度方法

9、下面的程序段时间复杂度为( )。 for(i=1;i<n;i++) for(j=1;j<n;j++) x=x+1;
    A、O(2n)
    B、O(n)
    C、O(n2)
    D、O(log2n)

10、算法效率分析的两个主要方面是( )。
    A、空间复杂度和时间复杂度
    B、正确性和简明性
    C、可读性和文档性
    D、数据复杂性和程序复杂性

11、有如下递归函数fact(n),分析其时间复杂度为( )。 int fact(int n) { if(n<=1) return 1; else return(n*fact(n-1)); }
    A、O(n)
    B、O(1)
    C、O(n2)
    D、O(logn)

12、下面程序段的时间复杂度为( )。 for(i=0;i<n;i++) for(j=0;j<m;j++) A[i][j]=0;
    A、O(n*m)
    B、O(n2)
    C、O(m2)
    D、O(1)

13、下面程序段的时间复杂度为( )。 void sum(int n) //n为正整数 { int p=1,sum=0,i; for(i=1;i<=n;i++) { p*=i; sum+=p; } }
    A、O()
    B、O(n)
    C、O(1)
    D、O(n2)

14、顺序存储方式的优点是存储密度大,且插入、删除运算效率高。

15、算法可以用不同的语言描述,如果用C 语言或PASCAL语言等高级语言来描述,则算法实际上就是程序了。

16、链式存储的优点是可以随机存储。

17、在相同的数据规模n下,复杂度为O(n)的算法在时间上总是优于复杂度为O()的算法。

18、数据的逻辑结构分为线性结构、树型结构、图状结构和集合。

19、数据的存储结构表示的是数据元素之间的逻辑关系。

第一章单元作业1

1、设计求解下列问题的算法,并分析其最坏情况的时间复杂度及其量级。 (1)在数组A[1..n]中查找值为K的元素,若找到则输出其位置i(1<=i<=n),否则输出0作为标志。 (2)找出数组A[1..n]中元素的最大值和次最大值(本小题以数组元素的比较为标准操作)。

2、如下程序段: x=1; for (i=1; i<=n; i++) for (j=1; j<=n; j++) for (k=1; k<=n; k++) x++; 其时间复杂度为 。

3、如下程序段: void func(int n) { int i=0, s=0; while ( s<n ) { i++; s=s+i; } } 其时间复杂度为 。

第二章 线性表

第1讲 线性表的概念及顺序存储(总时长17分44秒)随堂测验

1、顺序表是指按照顺序方式进行存储的线性表。

第2讲 单链表的概念及其基本操作(总时长12分27秒)随堂测验

1、单链表的插入、删除效率优于顺序表。

第3讲 建立单链表(总时长13分45秒)随堂测验

1、单链表的头插建立算法也称为反向建立单链表。

第4讲 循环链表(总时长14分45秒)随堂测验

1、带尾指针的循环链表比带头指针的循环链表更便于运算。

第5讲 双向链表(总时长16分01秒)随堂测验

1、在双向链表中查找某一结点的前驱或者后继,都非常方便。

在线练习2

1、下述哪一条是顺序存储结构的优点( )。
    A、随机存取
    B、插入运算方便
    C、删除运算方便
    D、可方便地用于各种逻辑结构的存储表示

2、下面关于线性表叙述中错误的是( )。
    A、线性表采用顺序存储,必须占用一片连续的存储单元。
    B、线性表采用顺序存储,便于进行插入和删除操作。
    C、线性表采用链式存储,不必占用一片连续的存储单元。
    D、线性表采用链式存储,便于插入和删除操作。

3、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用( )存储方式最节省时间。
    A、顺序表
    B、双链表
    C、带头结点的双循环链表
    D、单循环链表

4、设某顺序表中第一个元素的存储地址是Base,下限值为1,每个结点占m个单元,则第i个结点的存储地址为( )。
    A、Base+(i+1)×m
    B、Base+i×m
    C、Base+(i-1)×m
    D、Base-i×m

5、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用( )存储方式最节省运算时间。
    A、单链表
    B、仅有头指针的单循环链表
    C、双链表
    D、仅有尾指针的单循环链表

6、设一个链表最常用的操作是在末尾插入结点和删除尾结点,则选用( )最节省时间。
    A、单链表
    B、带尾指针的单循环链表
    C、单循环链表
    D、带头结点的双循环链表

7、链表不具有的特点是( )。
    A、插入、删除不需要移动元素
    B、可随机访问任意元素
    C、不必事先估计存储空间
    D、所需空间与线性长度成正比

8、线性表若采用链式存储结构时,要求内存中可用存储单元的地址( )。
    A、必须是连续的
    B、部分地址必须是连续的
    C、一定是不连续的
    D、连续或不连续都可以

9、静态链表中指针表示的是( )。
    A、内存地址
    B、数组下标
    C、下一元素在数组中的下标
    D、左、右孩子地址

10、若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算法的时间复杂度为 ()。
    A、O(0)
    B、O(1)
    C、O(n)
    D、O()

11、对于顺序表,访问结点和删除结点的时间复杂度分别为( )。
    A、O(n) O(n)
    B、O(n) O(1)
    C、O(1) O(n)
    D、O(1) O(1)

12、在单链表指针为p的结点之后插入指针为s的结点,正确的操作是( )。
    A、p->next=s;s->next=p->next;
    B、s->next=p->next;p->next=s;
    C、p->next=s;p->next=s->next;
    D、p->next=s->next;p->next=s;

13、对于一个带头结点的单链表,其头指针为head,判定该表为空表的条件是( )。
    A、head==NULL
    B、head→next==head
    C、head→next==NULL
    D、head!=NULL

14、将两个各有n个元素的有序表合并成一个有序表,其最少的比较次数是( )。
    A、n
    B、2n-1
    C、2n
    D、n-1

15、在双向链表中,在p所指向的结点前插入一个q所指向的结点,相应的操作语句是( )。 注:双向链表的结点结构为(prior,data,next)。
    A、p->prior=q;q->next=p;p->prior->next=q;q->prior=q;
    B、p->prior=q;p->prior->next=q;q->next=p;q->prior=p->prior;
    C、q->next=p;q->prior=p->prior;p->prior->next=q;p->prior=q;
    D、q->prior=p->prior;q->next=q;p->prior=q;p->prior=q;

16、线性表( a1,a2,…,an)以链式方式存储时,访问第i个元素的时间复杂度为( )
    A、O(i)
    B、O(1)
    C、O(n)
    D、O(i-1)

17、头指针为H的循环单链表中尾结点P的特点是( )。
    A、P->next=H
    B、P->next= H->next
    C、P=H
    D、P=H->next

18、两个指针P和Q,分别指向单链表的两个结点,P是Q的前驱结点的条件是( )。
    A、P->next==Q->next
    B、P->next==Q
    C、Q->next==P
    D、P==Q

19、在单链表中,增加头结点的目的是( )。
    A、使单链表至少有一个结点
    B、标志表中首结点的位置
    C、链表判空、插入第一个结点以及删除第一个结点等运算方便
    D、说明该单链表是线性表的链式存储结构

20、下面关于线性表的叙述中,错误的是( )。
    A、顺序表必须占一片地址连续的存储单元
    B、顺序表可以随机存取任一元素
    C、链表不必占用一片地址连续的存储单元
    D、链表可以随机存取任一元素

21、设p为指向长度为n的单循环链表上某结点的指针,则找到p的直接前驱( )。
    A、找不到
    B、时间复杂度为O(1)
    C、时间复杂度为O(n)
    D、次数约为n

22、以下关于线性表的论述,不正确的是( )。
    A、线性表中的元素可以是数字、字符、记录等不同类型。
    B、顺序表中包含的元素个数是有限的。
    C、线性表中的每个结点都有且仅有一个直接前趋和一个直接后继。
    D、存在这样的线性表,即表中没有任何结点。

23、在( )的运算中,使用顺序表比链表好。
    A、插入
    B、根据序号查找
    C、删除
    D、根据元素查找

24、静态链表与动态链表在元素的插入、删除上类似,不需做元素的移动。

25、线性表的特点是每个元素都有一个前驱和一个后继。

26、若长度为n的线性表采用顺序存储结构,找到其中第i个元素的时间复杂度为O(n)。

27、已知带头结点的双向循环链表L,判断其为空表的条件是L->next==L && L->prior==L。

28、顺序表的插入、删除运算更方便。

29、链表的性能优于顺序表。

30、顺序表适宜于顺序存取,而链表适宜于随机存取。

31、顺序表的每个结点只能是一个简单类型,而链表的每个结点可以是一个复杂类型。

32、插入和删除操作是数据结构中最基本的两种操作,所以这两种操作在数组中也经常使用。

33、线性表的链式存储结构中,逻辑上相邻的两个元素在物理位置上不一定相邻。

单元作业2

1、设有一线性表e=(e1 , e2 , … , en-1 , en),其逆线性表定义为e'=( en , en-1 , … , e2 , e1),请设计一个算法,将线性表逆置,要求逆线性表仍占用原线性表的空间,并且用顺序表和单链表两种方法来表示,写出不同的处理函数。

2、设指针la和lb分别指向两个无头结点单链表中的首元结点,试设计从表la中删除自第i个元素起共len个元素,并将它们插入到表lb的第j个元素之后的算法。

第三章 栈和队列

第1讲 栈的概念及其基本操作(总时长13分06秒)随堂测验

1、栈的特点是先进先出。

第2讲 栈的概念及其基本操作—双端栈(总时长12分10秒)随堂测验

1、双端栈有效地共享了存储空间。

第3讲 栈的应用—递归及汉诺塔问题(总时长16分27秒)随堂测验

1、汉诺塔问题可以使用递归算法来完成。

第4讲 栈的应用—迷宫实验(总时长07分40秒)随堂测验

1、迷宫问题的非递归实现借助的是栈这种结构。

第5讲 队列的概念及基本操作(总时长16分31秒)随堂测验

1、队列的特点是先进后出。

第6讲 队列的概念及应用—链队列(总时长11分10秒)随堂测验

1、采用链式结构存储的队列称之为链队列。

第7讲 表达式的求值问题(总时长15分01秒)随堂测验

1、在表达式求值问题中,我们使用运算符栈和运算数栈协同工作完成整个表达式的求解过程。

单元测试1

1、栈和队列的共同点是( )。
    A、都是先进先出
    B、都是先进后出
    C、只允许在端点处插入和删除元素
    D、没有共同点

2、栈和队都是( )。
    A、顺序存储的线性结构
    B、链式存储的非线性结构
    C、限制存取点的线性结构
    D、限制存取点的非线性结构

3、依照六个元素6,5,4,3,2,1 的顺序进栈,下列哪一个出栈序列不可能( )。
    A、543612
    B、453216
    C、346521
    D、234156

4、设栈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

5、设计一个判别表达式中括号是否匹配出现的算法,采用( )的数据结构最佳。
    A、顺序表
    B、队列
    C、单链表
    D、栈

6、表达式a*(b+c)-d的后缀表达式是( )。
    A、bc+a*d-
    B、abc+*d-
    C、ab*c+d-
    D、dabc+*-

7、函数递归调用时,处理参数及返回地址需要用一种( )的数据结构。
    A、队列
    B、多维数组
    C、栈
    D、线性表

8、若用一个大小为6的数组来实现循环队列,且当前rear和front的值分别为3和1,当从队列中删除一个元素再加入两个元素后,rear和front的值为( )。
    A、0和5
    B、2和4
    C、5和2
    D、5和1

9、最大容量为n的循环队列,队尾指针为rear,队头指针为front,则队空的条件是( )。
    A、(rear+1)%n==front
    B、rear==front
    C、rear+1==front
    D、(rear-l)%n==front

10、假设以数组A[m]存放循环队列的元素,其头、尾指针分别为front和rear,front指示实际的队头元素,rear指向实际队尾元素的下一个元素位置,则当前队列中的元素个数为( )。
    A、(rear-front+m)%m
    B、rear-front+1
    C、(front-rear+m)%m
    D、(rear-front+1)%m

11、用带头结点的表长大于1的单链表表示队列时,其队头指针指向队头结点,其队尾指针指向队尾结点,则在进行删除操作时( )。
    A、仅修改队头指针
    B、仅修改队尾指针
    C、队头、队尾指针都要修改
    D、队头,队尾指针都可能要修改

12、下列说法正确的是( )。 (1)只有使用了局部变量的递归函数在转换成非递归函数时才必须使用栈。 (2)队列是插入与删除操作在表的两端进行的线性表,具有先进后出的特点。 (3)队列是一端进行删除另外一端进行插入的线性表。 (4)循环队列也存在空间溢出问题。
    A、(1)(2)(4)
    B、(1)(2)(3)
    C、(3)(4)
    D、(1)(2)

13、以下程序的输出结果为( )。 int f( int x) { return (x>0)?x*f(x-1):2; } void main() { int i ; i=f(f(1)); printf("%d",i); }
    A、2
    B、4
    C、8
    D、无限递归

14、若一个栈以数组V[0..n-1]存储,初始栈顶指针top为n,则下面关于元素x进栈的正确操作是( )。
    A、top=top+1; V[top]=x;
    B、V[top]=x; top=top+1;
    C、top=top-1; V[top]=x;
    D、V[top]=x; top=top-1;

15、一个递归算法必须包括( )。
    A、递归体
    B、递归条件和递归体
    C、迭代部分
    D、终止条件和迭代部分

16、输入序列为ABC,想要得到CBA的输出结果,可以经过的栈操作为( )。
    A、push,pop,push,pop,push,pop
    B、push,push,push,pop,pop,pop
    C、push,push,pop,pop,push,pop
    D、push,pop,push,push,pop,pop

17、一个栈的输入序列为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 4 3 2

18、一个栈的输入序列为1,2,3,…,n,若输出序列的第一个元素是i,则输出第j(1<=j<=i)个元素是( )。
    A、i-j-1
    B、i-j+1
    C、j-i+1
    D、不确定的

19、在双向链表(结点包括:data,prior,next)中,删除指针p所指向的结点时须修改指针( )。
    A、p->prior->next=p->next;p->next->prior=p->prior;
    B、p->prior=p->prior->prior;p->prior->next=p;
    C、p->next->prior=p;p->next=p->next->next;
    D、p->next=p->prior->prior;p->prior=p->next->next;

20、以下说法错误的是 ( )。
    A、对循环链表来说,从表中任意结点出发都能通过前后操作而扫描到整个循环链表。
    B、对单链表来说,只有从头结点开始才能扫描表中全部结点。
    C、双向链表的特点是找结点的前趋和后继都很容易。
    D、对双向链表来说,结点*P的存储位置既存放在其前驱结点的后继指针域中,也存放在它的后继结点的前趋指针域中。

21、对于一个具有n个结点的单链表,在已知的结点*p后插入一个新结点的时间复杂度和在给定值为x的结点后插入一个新结点的时间复杂度分别为( )。
    A、O(n),O(n)
    B、O(1),O(n)
    C、O(1),O(1)
    D、O(n),O(1)

22、循环队列存储在数组A[0..m-1]中,则入队时rear应该变化为( )。
    A、rear++;
    B、rear=(rear+1) mod (m+1);
    C、rear=(rear+1) mod m;
    D、rear=(rear+1) mod (m-1);

23、当利用大小为n的数组顺序存储一个栈时,假定用top=n表示栈空,则每次向这个栈插入一个元素时,首先应执行( )语句修改top指针。
    A、top++;
    B、top--;
    C、top=0;
    D、top=n;

24、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用( )存储方式最节省时间。
    A、顺序表
    B、双链表
    C、带头结点的双循环链表
    D、单循环链表

25、链表不具有的特点是( )。
    A、插入、删除不需要移动元素
    B、可随机访问任意元素
    C、不必事先估计存储空间
    D、所需空间与线性长度成正比

26、设某顺序表中第一个元素的地址是Base,下标从1开始,每个结点占m个单元,则第i个结点的地址为( )。
    A、Base+(i+1)×m
    B、Base+i×m
    C、Base+(i-1)×m
    D、Base-i×m

27、在下面的程序段中,对x的赋值语句的频度为( )。 for(i=1;i<n;i++) for(j=1;j<n;j++) x=x+1;
    A、O(2n)
    B、O(n)
    C、O(n2)
    D、O(log2n)

28、数据结构在计算机内存中的表示是指( )。
    A、数据的存储结构
    B、数据结构
    C、数据的逻辑结构
    D、数据元素之间的关系

29、消除递归不一定需要使用栈,此说法( )。

30、两个栈共享一片连续内存空间时,为提高内存利用率,减少溢出,应把两个栈的栈底分别设在这片内存空间的两端。( )

31、顺序栈因为是顺序存储,所以可以随机存取栈中任意元素。( )

32、任何一个递归过程都可以转换成非递归过程。( )

33、两顺序栈共享空间,也存在空间溢出问题。( )

34、栈和队列都是线性表,只是在插入和删除时受到了一些限制。( )

35、栈和队列的存储方式,既可以是顺序方式,也可以是链式方式。( )

36、线性表的链式存储结构中,逻辑上相邻的两个元素在物理位置上并不一定相邻。

37、顺序表适宜于顺序存取,而链表适宜于随机存取。

38、顺序存储方式的优点是存储密度大,且插入、删除运算效率高。

单元作业3

1、回文序列是指正读反读均相同的字符序列,如“abba”和“abdba”均是回文,但“good”不是回文。试写一个算法判定给定的字符串是否为回文序列。

2、假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点,试编写相应的初始化、入队以及出队算法。

第五章 多维数组和广义表

第1讲 数组的定义与顺序存储(总时长12分25秒)随堂测验

1、n维数组可以看成是由“n-1维数组”的数组元素构成的一维数组。

第2讲 矩阵的压缩存储(总时长11分03秒)随堂测验

1、为了节省存储空间,我们经常对特殊矩阵和稀疏矩阵进行压缩存储。

第3讲 三元组矩阵的快速转置(总时长12分18秒)随堂测验

1、采用三元组顺序表存储的稀疏矩阵,利用快速转置算法,时间复杂度可以达到线性阶。

实验内容随堂测验

1、任何一个非空的广义表其表尾一定还是一个广义表。

在线练习5

1、设有一个10阶的对称矩阵A,采用下三角的压缩存储方式,以行序为主序,a[1][1]为第一元素,其存储地址为1,每个元素占一个地址空间,则a[8][5]的地址为( )。
    A、13
    B、33
    C、18
    D、40

2、设有数组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

3、假设以行序为主序存储二维数组A=array[1..100,1..100],设每个数组元素占2个存储单元,基地址为10,则arry[5][5]的地址为( )。
    A、808
    B、818
    C、1010
    D、1020

4、二维数组A的每个元素都是6个字符组成的串,行下标i的范围从0到8,列下标j的范围从1到10,则存放A至少需要( )个字节。
    A、90
    B、180
    C、240
    D、540

5、二维数组A的元素都是6个字符组成的串,行下标i的范围从0到8,列下标j的范围从1到10,则A的第8列和第5行共占( )个字节。
    A、108
    B、114
    C、54
    D、150

6、二维数组A的每个元素都是6个字符组成的串,行下标i的范围从0到8,列下标j的范围从1到10,则如果A按行存放元素A[8][5]的起始地址与A按列存放时元素( )的起始地址一致。
    A、A[8][5]
    B、A[3][10]
    C、A[5][8]
    D、A[0][9]

7、若对n阶对称矩阵A,下标从1开始,以行序为主序方式将其下三角形的元素依次存放于一维数组B[1..(n(n+1))/2]中,则在B中确定a[i][j](1≤i,j≤n,且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

8、若对n阶对称矩阵A,下标从1开始,以列序为主序方式将其上三角形的元素依次存放于一维数组B[1..(n(n+1))/2]中,则在B中确定a[i][j](1≤i,j≤n,且i≤j)的位置k的计算公式为( )。
    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

9、设二维数组A[1.. m,1.. n](即m行n列)按行存储在数组B[1.. m*n]中,则二维数组中元素A[i][j]在一维数组B中的下标为( )。
    A、(i-1)n+j
    B、(i-1)n+j-1
    C、i(j-1)
    D、jm+i-1

10、有一个100*90的稀疏矩阵,非零元素(int型)有10个,假设int型占2个字节,则用三元组顺序表表示该矩阵时所需的字节数是( )。
    A、60
    B、66
    C、18000
    D、33

11、对稀疏矩阵进行压缩存储的目的是( )。
    A、便于进行矩阵运算
    B、便于输入和输出
    C、节省存储空间
    D、降低运算的时间复杂度

12、已知广义表L=((x,y,z),a,(u,t,w)),从L表中取出原子项t的运算是( )。
    A、head(tail(tail(L)))
    B、head(tail(head(tail(L))))
    C、tail(head(head(tail(L))))
    D、head(tail(head(tail(tail(L)))))

13、广义表A=(a,b,(c,d),(e,(f,g))),则Head(Tail(Head(Tail(Tail(A)))))的值为( )。
    A、(g)
    B、(d)
    C、c
    D、d

14、设广义表L=((a,b,c)),则L的长度和深度分别为( )。
    A、1和1
    B、1和3
    C、1和2
    D、2和3

15、下面说法不正确的是( )。
    A、广义表的表头总是一个广义表
    B、一个非空广义表的表尾总是一个广义表
    C、广义表难以用顺序存储结构进行存储
    D、广义表可以是一个多层次的结构

16、广义表运算式Tail(((a,b),(c,d)))的操作结果是( )。
    A、(c,d)
    B、c,d
    C、((c,d))
    D、d

17、广义表(a,(b,c),d,e)的表头为( )。
    A、a
    B、a,(b,c)
    C、(a,(b,c))
    D、(a)

18、广义表((a,b,c,d))的表尾是( )。
    A、a
    B、()
    C、(a,b,c,d)
    D、(b,c,d)

19、数组A[0..4,-3..-1,5..7]中含有元素的个数( )。
    A、55
    B、45
    C、36
    D、16

20、数组A[0..5,0..6]的每个元素占5个字节,将其按列序为主序存储在起始地址为1000的内存单元中,则元素A[5][5]的地址是( )。
    A、1175
    B、1180
    C、1205
    D、1210

21、将一个A[1..100,1..100]的三对角矩阵,按行优先存入一维数组B[1‥298]中,元素A[66][65]在B数组中的位置K为( )。
    A、198
    B、195
    C、197
    D、196

22、已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B), 求tail(head(tail(C))) =( )。
    A、(a)
    B、(b)
    C、b
    D、((a,b))

23、在稀疏矩阵的三元组顺序表中,每个三元组表示( )。
    A、矩阵中非零元素的数据值
    B、矩阵中数据元素的行号和列号
    C、矩阵中数据元素的行号、列号和数据值
    D、矩阵中非零元素的行号、列号和数据值

24、对矩阵进行压缩存储后,( )矩阵会失去随机存取的优点。
    A、对称矩阵
    B、三角矩阵
    C、三对角矩阵
    D、稀疏矩阵

25、经常对数组进行的两种基本操作是____。
    A、建立与删除
    B、索引和修改
    C、查找和修改
    D、查找与索引

26、假设整型数组A[1..8,-2..6,0..6],按行优先存储,第一个元素的首地址是78,每个数组元素占用4个存储单元,那么元素A[4][2][3]的存储首地址为____。
    A、955
    B、958
    C、950
    D、900

27、tail(head(((a,b,c,d,e))))=__________。
    A、a
    B、b c
    C、Φ
    D、(b,c,d,e)

28、从逻辑结构上看,n维数组的每个元素均属于n个向量。

29、多维数组可以看作是一种特殊的线性表。

30、数组可看成线性结构的一种推广,因此与线性表一样,可以对它进行插入,删除等操作。

31、一个稀疏矩阵Am*n采用三元组顺序表形式表示,若把三元组中有关行下标与列下标的值互换,并把m和n的值互换,则就完成了Am*n的转置运算。

32、广义表B = (a, B) = (a, (a, (a, ××× , ) ) ) 的长度为无穷大。

33、一个广义表可以为其它广义表所共享。

34、一个广义表的表尾一定还是个广义表。

35、稀疏矩阵中非零元素的个数远小于矩阵中元素的总数。

第四章 串

第1讲 串的基本操作(总时长09分34秒)随堂测验

1、串是一种特殊的线性表。

第2讲 串的简单模式匹配(总时长13分18秒)随堂测验

1、串的简单模式匹配算法的时间复杂度达到平方阶。

第4讲 模式串的next值计算思想(总时长07分52秒)随堂测验

1、KMP算法最终只需要讨论模式串本身就可以。

第5讲 模式串的next值计算实现(总时长08分19秒)随堂测验

1、模式串ababc对应的next值为01123。

在线练习4

1、下面关于串的叙述不正确的是( )。
    A、串是字符的有限序列
    B、模式匹配是串的一种重要运算
    C、空串是由空格构成的串
    D、串可以采用顺序存储,也可以采用链式存储

2、串是一种特殊的线性表,其特殊性体现在( )。
    A、顺序存储
    B、数据元素是字符
    C、链式存储
    D、逻辑结构是线性结构

3、若串S= 'software',其前缀真子串的数目是( )。
    A、10
    B、9
    C、8
    D、7

4、串的长度是指( )。
    A、串中所含不同字母的个数
    B、串中所含字符的个数
    C、串中所含不同字符的个数
    D、串中所含非空格字符的个数

5、两个串相等的充要条件是( )。
    A、两个字符串中对应位置上的字符相等
    B、两个字符串存储形式相同
    C、两个字符串的长度相等
    D、两个字符串的长度相等且对应位置上的字符也相等

6、设有两个串p和q ,其中q是p的子串,求q在p中首次出现的位置的算法称为( )。
    A、求子串
    B、串联接
    C、串的模式匹配
    D、求串长

7、已知串 S=‘aaab',其next函数值为( )。
    A、0123
    B、1123
    C、1231
    D、1211

8、模式串‘ababaaababaa'的next函数值为( )。
    A、012345678999
    B、012121111212
    C、011234223456
    D、0123012322345

9、函数strcmp('stcabuc','stbabuc')的返回值是( )。
    A、-1
    B、2
    C、0
    D、1

10、模式串 t=‘abcaabbcabcaabdab',该模式串的next函数值为( )。
    A、0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2
    B、0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 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 3 1 1 2 3 4 5 6 7 1 2

11、假设空串是任何串的子串,则串S='Computer'的子串个数是( )。
    A、9
    B、36
    C、37
    D、8

12、StrIndex (‘DATASTRUCTURE',1,‘STR')= ( )。
    A、3
    B、7
    C、5
    D、9

13、设正文串长度为n,模式串长度为m,则模式匹配的KMP算法的时间复杂度为( )。
    A、O(m*n)
    B、O(m+n)
    C、O(m)
    D、O(n)

14、StrIndex(‘Index of String’,1,‘Str’)=( ) 。
    A、10
    B、8
    C、6
    D、12

15、SubStr('I like University',8,3)的返回值是( )。
    A、ike
    B、Uni
    C、ver
    D、ers

16、设S="",则LenStr(S)=( )。
    A、0
    B、1
    C、2
    D、3

17、设目标串T="aabaababaabaa",模式P="abab",朴素匹配算法的外层循环进行了( )次。
    A、1
    B、9
    C、4
    D、5

18、S1='good',S2='morning',执行函数SubStr(S2,4,LenStr(S1))后的结果为( )。
    A、'good'
    B、'ning'
    C、'go'
    D、'morn'

19、若串S='SOFT',其子串的数目最多是( ) 。
    A、9
    B、10
    C、11
    D、12

20、以下论述正确的是( )。
    A、空串与空格串是相同的
    B、'tel'是'Telephone'的一个子串
    C、空串是零个字符的串
    D、空串的长度等于1

21、设串S1='I AM',S2=' A STUDENT',则ConcatStr(S1,S2)=( )。
    A、'I AM'
    B、'A STUDENT'
    C、'I AM A STUDENT'
    D、'IAMASTUDENT'

22、设串S1='ABCDEFG',S2='PQRST' ,则ConcatStr(SubStr(S1,2,LenStr(S2)),SubStr(S1,LenStr(S2),2))的结果串为( )。
    A、'BCDEF'
    B、'BCDEFG'
    C、'BCPQRST'
    D、'BCDEFEF'

23、设有三个串S1、S2和S3,则StrReplace(S1,S2,S3)运算称作( )。
    A、串连接
    B、模式匹配
    C、求子串
    D、串替换

24、以下论断正确的是( )。
    A、""是空串," "空格串
    B、"BEIJING"是"BEI JING"的子串
    C、"something"="Something"
    D、"BIT"="BITE"

25、某串的长度小于一个常数,则采用( )存储方式最节省空间。
    A、链式
    B、顺序
    C、堆结构
    D、无法确定

26、串是一种数据对象特殊的线性表。

27、KMP算法的特点是在模式匹配时指示主串的指针不会回溯。

28、设模式串的长度为m, 目标串的长度为n ,当 n ≈ m 且处理只匹配一次的模式时,朴素的匹配(即子串定位函数)算法所花的时间代价可能会更为节省。

29、模式串 P=‘abaabcac'的next函数值序列为01122312

30、串的存储结构有顺序串、堆串和块链串三种。

31、如果一个串中所有的字母均在另一个串中出现,则说明前者是后者的子串。

32、串中任意个字符组成的子序列称为该串的子串。

33、如果两个串含有相同的字符,则说明它们相等。

34、子串的定位运算称为串的模式匹配。

35、串'student'和'Student'相等。

第六章 树

第1讲 二叉树的性质(总时长14分00秒)随堂测验

1、在任何一棵二叉树中,度为0的结点数等于度为2的结点数-1。

第2讲 二叉树的顺序存储(总时长09分21秒)随堂测验

1、完全二叉树采用顺序存储是比较方便的。

第3讲 二叉树的遍历(总时长17分11秒)随堂测验

1、二叉树的按层次遍历算法可以采用递归算法实现。

第6讲 二叉树的恢复建立(总时长12分02秒)随堂测验

1、根据二叉树的前序和后序遍历结果可以恢复出一棵二叉树。

第7讲 二叉树的非递归遍历(总时长13分19秒)随堂测验

1、二叉树的非递归遍历算法借助了栈这种结构。

第8讲 线索二叉树(总时长12分00秒)随堂测验

1、在线索二叉树中,有n+1个线索。

第9讲 线索二叉树的遍历(总时长10分57秒)随堂测验

1、在中序线索树中找结点的直接前驱,实际是找左子树中“最右下端”的结点。

第10讲 树和森林(总时长12分21秒)随堂测验

1、树的双亲表示法采用的是顺序存储结构。

第11讲 树与森林的遍历(总时长11分22秒)随堂测验

1、树的后序遍历结果和对应的二叉树的中序遍历结果相同。

第12讲 哈夫曼树(总时长12分48秒)随堂测验

1、哈夫曼树中叶子结点数为n,那么内部结点数为n+1。

第13讲 哈夫曼编译码(总时长12分48秒)随堂测验

1、哈夫曼编码是前缀编码。

第14讲 哈夫曼编码算法(总时长09分30秒)随堂测验

1、哈夫曼编码是从叶子到根进行编码的。

单元测试2

1、树最适合用来表示的结构是( )。
    A、元素间的有序结构
    B、元素间具有分支及层次关系的结构
    C、元素间的无序结构
    D、元素间无联系的结构

2、设一棵二叉树的结点个数为18,则它的高度至少为( )。
    A、4
    B、5
    C、6
    D、18

3、任意一棵二叉树的叶子结点在其先序、中序、后序序列中的相对位置( )。
    A、肯定发生变化
    B、有时发生变化
    C、肯定不发生变化
    D、无法确定

4、判断线索二叉树中某结点p有左孩子的条件是( )。
    A、p!=NULL
    B、p->lchild!=NULL
    C、p->LTag==0
    D、p->LTag==1

5、设森林T中有4棵树,其结点个数分别为n1,n2,n3,n4,那么当森林T转换成一棵二叉树后,则根结点的右子树上有( )个结点。
    A、n1-1
    B、n1
    C、n1+n2+n3
    D、n2+n3+n4

6、由权值分别为9、2、5、7、4的5个叶子结点构造一棵哈夫曼树,则该树的带权路径长度为( )。
    A、45
    B、55
    C、60
    D、65

7、设T是一棵哈夫曼树,有8个叶结点,则树T的高度最高可以是( )。
    A、4
    B、6
    C、8
    D、10

8、以下属于前缀编码的是( )。
    A、{0,1101,1110,1100,1111}
    B、{0,1,01,010,110}
    C、{00,01,10,11,101}
    D、{01,00,10,001,110,101}

9、算术表达式a+b*(c+d/e)转为后缀表达式为( )。
    A、ab+cde/*
    B、abcde/+*+
    C、abcde/*++
    D、abcde*/++

10、设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1,则T中的叶子数为( )。
    A、5
    B、6
    C、7
    D、8

11、一棵哈夫曼树共有215个结点,对其进行哈夫曼编码,共能得到( )个不同的码字。
    A、107
    B、108
    C、214
    D、215

12、一棵具有N个结点的二叉树采用二叉链表进行存储,其中空指针域有( )个。
    A、N
    B、N+1
    C、N-1
    D、不确定

13、深度为K的二叉树中结点总数( )。
    A、
    B、
    C、
    D、

14、已知一棵度为3的树有2个度为1的结点,3个度为2的结点,4个度为3的结点,则该树中有( )个叶子结点。
    A、10
    B、12
    C、11
    D、13

15、以数据集{4,5,6,7,10,12,18}为叶结点权值所构造的哈夫曼树,其带权路径长度为( )。
    A、165
    B、155
    C、160
    D、170

16、已知一算术表达式的中缀形式为 A+B*C-D/E,后缀形式为ABC*+DE/-,其前缀形式为( )。
    A、-A+B*C/DE
    B、-A+B*CD/E
    C、-+*ABC/DE
    D、-+A*BC/DE

17、若一个具有n个结点k条边的无向图是一个森林(n>k),则该森林必有( )棵树。
    A、k
    B、n
    C、n-k
    D、n+k

18、一棵二叉树结点的( )可唯一确定一棵二叉树。
    A、前序序列和中序序列
    B、前序序列和后序序列
    C、中序序列
    D、后序序列

19、设a=6,b=4,c=2,d=3,e=2,则后缀表达式abc-/de*+的值为( )。
    A、12
    B、5.5
    C、9
    D、10

20、若二叉树有n个结点,当执行中序遍历的递归程序时,在最坏情况下为处理递归调用所设的栈需要( )个单元。
    A、n-1
    B、n
    C、n/2
    D、n+1

21、具有64个结点的完全二叉树的深度为( )。
    A、5
    B、6
    C、7
    D、8

22、A,B为一棵二叉树上的两个结点,在中序遍历时,A在B前的条件是( )。
    A、A在B右方
    B、A是B祖先
    C、A在B左方
    D、A是B子孙

23、把一棵树转换为二叉树后,这棵二叉树的形态是( )。
    A、唯一的
    B、有多种
    C、有多种,但根结点都没有左孩子
    D、有多种,但根结点都没有右孩子

24、下列陈述正确的是( )。
    A、二叉树是度为2的有序树
    B、二叉树中结点只有一个孩子时无左右之分
    C、二叉树中必有度为2的结点
    D、二叉树中最多只有两棵子树,且有左右子树之分

25、在哈夫曼树中,若编码长度只允许小于等于4,则除了已确定两个字符的编码为0和10外,还可以最多对 个字符进行编码。
    A、3
    B、4
    C、5
    D、6

26、若串S= 'software',其前缀真子串的数目是( )。
    A、10
    B、9
    C、8
    D、7

27、模式串‘ababaaababaa'的next函数值为( )。
    A、012345678999
    B、012121111212
    C、011234223456
    D、0123012322345

28、StrIndex(‘Index of String’,1,‘Str’)=( ) 。
    A、10
    B、9
    C、8
    D、7

29、设串S1='I AM',S2='A STUDENT',则ConcatStr(S1,S2)=( )。
    A、'I AM'
    B、'A STUDENT'
    C、'I AM A STUDENT'
    D、'IAMASTUDENT'

30、设有三个串S1、S2和S3,则StrReplace(S1,S2,S3)运算称作( )。
    A、串连接
    B、模式匹配
    C、求子串
    D、串替换

31、假设以行序为主序存储二维数组A=array[1..100,1..100],设每个数组元素占2个存储单元,基地址为10,则LOC[5,5]=( )。
    A、808
    B、818
    C、1010
    D、1020

32、有一个100*90的稀疏矩阵,非零元素(int型)有10个,假设int型占2个字节,则用三元组顺序表表示该矩阵时所需的字节数是( )。
    A、60
    B、66
    C、18
    D、33

33、广义表(a,(b,c),d,e)的表头为( )。
    A、a
    B、a,(b,c)
    C、(a,(b,c))
    D、(a)

34、数组A[0..4,-1..-3,5..7]中含有元素的个数( )。
    A、55
    B、45
    C、35
    D、25

35、对下述矩阵进行压缩存储后,失去随机存取功能的是( )。
    A、对称矩阵
    B、三角矩阵
    C、三对角矩阵
    D、稀疏矩阵

36、完全二叉树一定存在度为1的结点。

37、一棵树中的叶子数一定等于与其对应的二叉树的叶子数。

38、在叶子数目和权值相同的所有二叉树中,带权路径长度最小的树一定是完全二叉树。

39、给定二叉树先、中和后序遍历序列中的两个,可以唯一确定一棵二叉树。

40、满二叉树一定完全是二叉树。

41、一棵二叉树中,中序遍历序列的最后一个结点,必定是该二叉树前序遍历的最后一个结点。

42、在完全二叉树中,若一个结点没有左孩子,则它必然是叶子结点。

43、具有n个叶子结点的哈夫曼树共有2n-1个结点。

44、串的存储结构有顺序串、堆串和块链串三种。

45、串中任意个字符组成的子序列称为该串的子串。

46、串'student'和'Student'相等。

47、一个广义表的表头一定还是个广义表。

48、稀疏矩阵中非零元素的个数远小于矩阵中元素的总数。

49、数组可看成线性结构的一种推广,因此与线性表一样,可以对它进行插入,删除等操作。

50、多维数组可以看作是一种特殊的线性表。

第七章 图

第1讲 图的基本概念(总时长13分33秒)随堂测验

1、图中任意两个顶点之间有路径相通我们称之为完全图。

第2讲 图的存储(总时长15分27秒)随堂测验

1、图的邻接矩阵是顺序存储方式。

第3讲 图的深度优先遍历(总时长13分05秒随堂测验

1、图的深度优先遍历算法还可以应用于检查回路问题。

第4讲 图的广度优先遍历(总时长07分40秒)随堂测验

1、图的广度优先算法可以使用递归完成。

第5讲 图的最小生成树-Prim算法思想(总时长11分40秒)随堂测验

1、prim算法适合在稠密图中求解最小生成树。

第6讲 图的最小生成树-Prim算法实现(总时长11分21秒)随堂测验

1、prim算法的时间代价主要取决于顶点个数。

第7讲 图的最小生成树-Kruskal算法(总时长09分25秒)随堂测验

1、Kruskal算法适合在稀疏图中求解最小生成树。

第8讲 图的拓扑排序思想(总时长10分38秒)随堂测验

1、拓扑排序可以用于检查图中是否有回路。

第10讲 图的关键路径思想(总时长12分26秒)随堂测验

1、在AOE网中,从源点到汇点的最长路径长度的路径被称为关键路径。

第12讲 图的单源最短路径-Dijkstra思想(总时长10分27秒)随堂测验

1、Dijkstra算法思想属于典型的贪心算法。

第13讲 图的单源最短路径-Dijkstra实现(总时长07分39秒)随堂测验

1、Dijkstra算法需要对图中每条边至少检查一次。

第八章 查找

第1讲 顺序查找(总时长10分21秒)随堂测验

1、对表长为n的线性表进行顺序查找,平均查找长度为(n+1)/2

第2讲 折半查找(总时长12分07秒)随堂测验

1、折半查找只适合关键字有序并且顺序存储的查找表。

第3讲 二叉排序树的基本概念与查找(总时长10分00秒)随堂测验

1、二叉排序树的形态与输入序列的顺序有关。

第4讲 二叉排序树的插入与生成(总时长09分05秒)随堂测验

1、在二叉排序树中,按照中序进行遍历,可以得到一个有序序列。

第6讲 哈希表基本概念(总时长09分41秒)随堂测验

1、哈希查找的理想情况是平均查找长度为0。

第7讲 哈希函数(总时长08分30秒)随堂测验

1、构造哈希函数时尽可能减少地址冲突,但又不可能避免。

第8讲 哈希处理冲突(总时长13分58秒)随堂测验

1、处理冲突实际就是为了产生冲突的地址寻找下一个散列地址。

第九章 排序

第1讲 排序基本概念(总时长04分59秒)随堂测验

1、当待排记录的关键字均不相同时,排序结果是唯一的。

第2讲 直接插入排序(总时长11分08秒)随堂测验

1、插入排序是不稳定的排序算法。

第3讲 希尔排序(总时长10分43秒)随堂测验

1、希尔排序的执行时间很大程度上依赖于增强的选取。

第4讲 冒泡排序(总时长09分31秒)随堂测验

1、冒泡排序是稳定的排序算法。

第5讲 快速排序(总时长13分22秒)随堂测验

1、快速排序的时间复杂度可以达到对数级。

第6讲 选择排序(总时长08分45秒)随堂测验

1、简单选择排序的时间性能是平方阶。

第8讲 堆排序(总时长15分54秒)随堂测验

1、堆排序的时间代价主要花费在建初始堆和调整筛选上。

第9讲 归并排序(总时长08分15秒)随堂测验

1、归并排序的时间性能可以达到对数级。

第10讲 基数排序(总时长11分45秒)随堂测验

1、基数排序常用来进行多关键字的排序。