算法与数据结构中国大学mooc完整答案-买球的app软件下载

当前位置:正规买球app首页 » » 正文

7698 人参与  2022-11-04 23:47:04    点这评论
第一周 数据结构概述(时长:24分42秒)

第1讲 什么是数据结构(时长:8分01秒)随堂测验

1、什么是数据结构?
    a、一个计算过程,从一个初始状态和初始输入开始,停止于一个终态。
    b、计算机中存储、组织数据的方式。
    c、程序设计
    d、基本数据类型

第2讲 数据结构与抽象数据类型(时长:7分34秒)随堂测验

1、基本的逻辑结构有哪些?
    a、线性结构、树形结构、图形结构;
    b、顺序结构、索引结构、链式结构;
    c、抽象数据类型、运算集合。
    d、散列结构

第3讲 算法与算法复杂度分析(时长:9分07秒)随堂测验

1、关于算法复杂度说法正确的是( )
    a、算法复杂度指时间复杂度
    b、算法复杂度指空间复杂度
    c、算法复杂度包含时间复杂度、空间复杂度
    d、算法复杂度通常与数据规模无关

单元测试

1、计算机算法指的是()
    a、计算机程序
    b、解决问题的有限运算序列
    c、排序方法
    d、检索方法

2、下面程序段的算法复杂度是() min=a[0]; for(i=1;ia[i]) min=a[i] 其中 n为正整数。
    a、
    b、
    c、
    d、

3、在数据结构中,数据的( )的结构是与计算机无关的。
    a、物理
    b、存储
    c、逻辑
    d、逻辑和存储

4、数据的最小单位是( )。
    a、数据项
    b、数据元素
    c、结点
    d、记录

5、数据结构是指( )的集合以及它们之间的关系。
    a、数据
    b、数据的逻辑结构
    c、算法
    d、数据元素

6、数据的逻辑结构可以分为() 。
    a、内部结构和外部结构
    b、链式结构和顺序结构
    c、动态结构和静态结构
    d、线性结构和非线性结构

7、数据结构在计算机内存中的表示是指( )。
    a、数据元素之间的关系
    b、顺序结构
    c、数据的存储结构
    d、数据的逻辑结构

8、算法分析的主要任务之一是分析( )。
    a、算法的执行时间和问题规模之间的关系
    b、算法的正确性
    c、算法的可读性
    d、算法的功能是否符合用户需求

9、若某算法的时间复杂度为o(n^2),则表明该算法的( )。
    a、执行时间与n^2成正比
    b、问题规模是n^2
    c、问题规模与n^2成正比
    d、执行时间等于n^2

10、下列函数中时间复杂度是o(n)的是()。
    a、
    b、t(n)=500n
    c、
    d、t(n)=2n^2

11、下面代码段的时间复杂度为()。 { int i=1; while (i<=n) i=i*2; }
    a、o(1)
    b、o(n)
    c、
    d、

12、下面代码段的时间复杂度为()。 { int i=0, s=0; while (i    a、o(1)
    b、o(n)
    c、
    d、

13、以下说法正确的是()。
    a、数据结构是带结构的各数据项的集合
    b、一些表面上很不相同的数据可以有相同的逻辑结构
    c、数据元素是数据的最小单位
    d、数据项是数据的基本单位

14、通常要求同一逻辑结构中的所有数据元素具有相同的特性,这说明()。
    a、每个数据元素所包含的数据项的个数要相等
    b、每个数据元素都一样
    c、数据元素具有同一特点
    d、不仅数据元素所包含的数据项的个数要相同,而且对应的数据项的类型要一致

15、在决定选取何种存储结构时,一般不考虑()。
    a、所用编程语言实现这种结构是否方便
    b、结点个数的多少
    c、各结点的具体值如何
    d、对数据有哪些运算

16、下面的算法是判断n是否为素数,其算法时间复杂度为( )。 void prime(int n) { /* 判断n是否是素数 */ for (i=2; isqrt(n)) printf("%d is a prime number", n); else printf("%d is not a prime number", n); }
    a、
    b、
    c、
    d、

17、下面算法的时间复杂度为( )。 x=100; y=100; while(y>0) if(x>100) {x=x-10; y--;} else x ;
    a、
    b、
    c、
    d、

18、如下程序段: for(i=1;i<=n-1;i ) for(j=i 1;j<=n;j ) x=x 1; 其中语句x=x 1执行的语句频度为( )。
    a、n*n
    b、n*(n-1)
    c、n*(n-1)/2
    d、n*(n 1)/2

19、评价一个算法性能好坏的重要标准是( )。
    a、算法是否易于理解
    b、算法是否易于调试
    c、算法的时间复杂度
    d、算法的正确性

20、算法的时间复杂度取决于( )。
    a、问题的规模
    b、待处理数据的初态
    c、实现算法所使用的的语言
    d、数据采用的存储结构

21、数据结构包括数据的()、数据的()和数据的()这三个方面的内容。
    a、逻辑结构
    b、存储结构
    c、运算
    d、输入输出

22、常见的逻辑结构有集合 ,(),(),()四种。
    a、顺序表
    b、线性结构
    c、树形结构
    d、图形结构

23、计算机中算法指的是解决某一问题的有限运算序列,它必须具备0或多个输入、1或多个输出、( )、()、()。
    a、确定性
    b、有穷性
    c、可移植性
    d、可行性

24、一个抽象数据类型包括()。
    a、一组基本操作
    b、数据
    c、数据对象
    d、数据对象中各元素间的关系

25、数据的物理结构是指数据的各数据项之间的逻辑关系。

26、数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构。

27、某算法的时间复杂度是o(n^3),表明该算法的执行时间与n^3成正比。

28、顺序存储的优点是逻辑上相邻的元素,物理上也是相邻的,因此可以实现随机存储。

29、数据元素是数据的基本单位

30、在存储数据时,通常不仅要存储各数据元素的值,而且还要存储数据元素之间的关系。

31、健壮的算法不会因为非法输入而出现莫名的执行结果。

32、算法的可行性是指每一条指令具有明确含义。

33、算法的优劣与算法描述的语言无关。

34、程序一定是算法。

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

36、任何数据结构都具备3个基本运算:插入、删除、和查找。

37、数据的逻辑结构与数据元素在计算机中如何存储有关。

38、如果数据元素值发生改变,则数据的逻辑结构也随之改变。

39、数据的逻辑结构时指数据的各数据项之间的逻辑关系。

编程作业

1、本题要求实现一个函数,求给定的n个整数的和。

2、本题要求实现一个函数,计算n个整数中所有偶数的和,并实现一个判断奇偶性的函数。

3、该题为编程题,计算个人所得税

4、本题要求实现一个根据学生成绩设置其等级,并完成统计不及格人数的函数。

第二周 线性表(上)(时长:74分54秒)

第1讲 线性表及其顺序存储(时长:34分46秒)随堂测验

1、对于顺序存储的长度为n的线性表,下标从0开始,则删除第i个位置的元素需要移动____个元素。其中(0≤i<n)。
    a、n-i
    b、n-i-1
    c、i
    d、i 1

2、若长度为 n 的线性表采用顺序存储结构存储,在第 i 个位置上插入一个新元素的时间复杂度为( )。
    a、o(n^2)
    b、
    c、o(n)
    d、o(1)

3、假设在顺序表{a1,a2,……,an}中,每一个数据元素所占的存储单元的数目为4,且第1个数据元素的存储地址为100,则第8个数据元素的存储地址是()。
    a、106
    b、107
    c、124
    d、128

4、同一个线性表中数据元素的类型可以不相同。

第2讲 单链表(时长:40分09秒)随堂测验

1、在一个不带头结点的单链表中,若要删除 p 所指结点的后继结点q,则执行( )。
    a、p->next=q->next;free(q);
    b、p=p->next; p->next=q->next;free(q);
    c、p->next=p->next;free(q);
    d、p =p->next->next;free(q);

2、线性表若采用链式存储结构时,要求内存中可用存储单元的地址()
    a、必须是连续的
    b、一定不是连续的
    c、连续不连续均可
    d、以上说法都不对

3、若用指针head指向不带头结点的单链表的表头,则该单链表为空的判定条件是()。
    a、head->next==head
    b、head!=null
    c、head->next==null
    d、head==null

4、在一个不带头结点的单链表中,若 p 所指结点不是最后结点,在 p 之后插入 s 所指结点,则执行()。
    a、s->next=p;p->next=s;
    b、s->next=p->next;p=s;
    c、s->next=p->next;p->next=s;
    d、p->next=s;s->next=p->next;

单元测试

1、线性表是( )
    a、一个有限序列,不可以为空
    b、一个有限序列,可以为空
    c、一个无限序列,可以为空
    d、一个无限序列,不可以为空

2、对于长度为n的顺序表(下标范围0..n-1),在第i个位置插入一个元素需要移动( )个元素。其中,0≤i≤n。
    a、n-i
    b、n-i-1
    c、n-i 1
    d、i

3、若数组a可存放100个元素,每个元素占4个字节,从首地址1000开始按顺序连续存放,那么,元素a[16]的起始地址为( )。
    a、1128
    b、1064
    c、1032
    d、1016

4、对于顺序存储的长度为n的线性表,删除第i个位置的元素需要移动( )个元素。其中,0≤i<n。
    a、i
    b、n-i 1
    c、n-i-1
    d、n-i

5、对于线性表,下列说法正确的是()。
    a、表中元素必须是有序的
    b、每个元素有且仅有一个直接前驱和一个直接后继
    c、除第一个元素与最后一个元素,其他每个元素有且仅有一个直接前驱和一个直接后继
    d、线性表不允许为空

6、线性表采用顺序存储结构,下列说法不正确的是( )。
    a、插入、删除操作不必移动元素
    b、需要事先估计所需存储空间,可能出现顺序表满的情况
    c、内容空间地址必须是连续的
    d、可以进行随机存取

7、线性表的顺序存储最适合于实现 ( )运算。
    a、将x插入第i个位置
    b、查找值为x
    c、删除第i个位置元素
    d、取第i个位置元素

8、在长度为n的顺序表中,查找值为x的数据元素的时间复杂度为()
    a、o(1)
    b、o(n)
    c、o(n^2)
    d、

9、在长度为n的顺序表中,查找第i个位置的数据元素的时间复杂度为()
    a、o(1)
    b、o(n)
    c、o(n^2)
    d、

10、对顺序存储的长度为n的线性表,假设在任何位置上进行删除操作是等概率的。则删除一个元素时平均要移动表中的( )个元素。
    a、n
    b、(n 1)/2
    c、n/2
    d、(n-1)/2

11、对顺序存储的长度为n的线性表,假设在任何位置上进行插入操作是等概率的。则插入一个元素时平均要移动表中的( )个元素。
    a、n
    b、n/2
    c、(n 1)/2
    d、(n-1)/2

12、在长度为n的顺序表的运算中,算法的时间复杂度是o(1)的操作是( )。
    a、在第i个位置上插入一个新元素(0≤i≤n)
    b、求第i个位置的元素的直接前驱(1≤i    c、删除第i个位置上的元素(0≤i    d、以上都不对

13、下面关于线性表的叙述错误的是 ()。
    a、线性表采用链式存储便于插入和删除操作的实现
    b、线性表采用顺序存储必须占用一片连续的存储空间
    c、线性表采用链式存储不必占用一片连续的存储空间
    d、线性表采用顺序存储便于插入和删除操作的实现

14、在单链表中,要删除某一指定的结(节)点,必须找到该结点的 ()结点。
    a、头结点
    b、尾结点
    c、前驱
    d、后继

15、求一个单链表长度的算法的时间复杂度为()。
    a、
    b、
    c、
    d、

16、已知一个长度为n的单链表中所有结点是递增有序的,以下叙述中正确的是 ()。
    a、删除最大值结点使之有序的算法的时间复杂度为 o(1)
    b、都不对
    c、找最小值结点的算法的时间复杂度为 o(1)
    d、插入一个结点使之有序的算法的时间复杂度为o(1)

17、将长度为m的单链表(a)链接在长度为n的单链表(b)之后的算法时间复杂度为()。
    a、o(n)
    b、o(m n)
    c、o(m)
    d、o(1)

18、将长度为m的顺序表(a)链接在长度为n的顺序表(b)之后的算法时间复杂度为()。
    a、o(m)
    b、o(n)
    c、o(m n)
    d、o(1)

19、在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是 ()。
    a、
    b、
    c、
    d、

20、在单链表中查找指定值的结点的时间复杂度是()。
    a、
    b、
    c、
    d、

21、对于一个具有n个元素的线性表,建立其单链表的时间复杂度为 ( )。
    a、
    b、
    c、
    d、

22、对于一个具有n个结点的单链表,在已知的结点*p后插入一个新结点的时间复杂度为( )。
    a、
    b、
    c、
    d、

23、对于一个具有n个结点的单链表,在给定值为x的结点后插入一个新结点的时间复杂度为()。
    a、
    b、
    c、
    d、

24、下面的叙述中正确的是()。
    a、线性表在链式存储时,查找第i个元素的时间与i的数值无关。
    b、线性表在顺序存储时,查找第i个元素的时间与i的数值无关。
    c、线性表在链式存储时,插入第i个元素的时间与i的数值成正比。
    d、线性表在顺序存储时,查找第i个元素的时间与i的数值成正比。

25、线性表采用顺序存储结构进行存储,取第i个位置元素的时间与i值的大小有关。

26、具有100个元素的顺序表(下标从0开始),删除第50个位置的元素,需要移动51个元素。

27、线性表的特点是除了第一个元素以及最后一个元素外,其他元素有且仅有一个直接前驱和一个直接后继。

28、线性表中的所有数据元素的数据类型必须相同。

29、顺序表的插入、删除总是伴随着大量数据的移动。

30、顺序存储方式的优点是存储密度大,数据存储在连续的内存空间中,但是插入、删除运算效率低。

31、插入和删除操作是线性表的基本操作。这两种操作在数组中也经常使用。

32、顺序表中所有元素的排列顺序必须从小到大或从大到小。

33、顺序表结构适宜进行随机访问,而链表适宜进行插入、删除。

34、在单链表中,可以从头结点开始查找任何一个结点。

35、在单链表中,可以从任一结点开始查找到任何其他结点。

36、线性表的顺序存储结构优于链式存储结构。

编程作业

1、本题要求实现一个函数,将给定单向链表逆置,即表头置为表尾,表尾置为表头。

2、本题要求实现顺序表的操作集。

3、编写算法函数void reverse(list l),实现顺序表的就地倒置。

4、已知顺序表l1,l2中数据由小到大有序,请用尽可能快的方法将l1与l2中的数据合并到l3中,使数据在l3中按升序排列。

第三周 线性表(下)(时长:105分58秒)

第3讲 带头结点的单链表(时长:40分16秒)随堂测验

1、采用头插法创建带头结点的单链表,则创建一个长度为n的链表,其时间复杂度为()。
    a、o(n)
    b、o(1)
    c、o(n^2)
    d、

2、在一个带头结点的单链表中,若 head 所指结点是头结点,若要删除第一个实际元素结点,则执行()。
    a、p=head->next;head->next=p->next;free(p);
    b、p=head;free(p);head=head->next;
    c、head=head->next;p=head;free(p);
    d、p=head;head=head->next;free(p);

3、若带头结点的单链表的表头指针为head,则该单链表为空的判定条件是()。
    a、head==null
    b、head->next=null
    c、head!=null
    d、head->next=head

4、在一个带头结点的单链表head中,若要将 s 所指结点插入在第一个结点之前,则执行()。
    a、head->next=s;s->next=head;
    b、s->next=head->next;head=s;
    c、s->next=head;head->next=s;
    d、s->next=head->next;head->next=s;

第4讲 循环链表(时长:34分01秒)随堂测验

1、在一个非空的循环单链表中,若要删除p所指结点的后继结点,则执行( )。
    a、q=p->next;p->next=q->next->next; free(q);
    b、q=p->next;p->next=q->next; free(q);
    c、q=p->next;p=q->next->next; free(q);
    d、q=p->next; free(q);p->next=q->next->next;

2、对于一个非空的循环单链表,若头指针为head,假设指针myrear指向表中的最后一个结点,如果要在非空的循环单链表的最前面插入一个新结点p,则执行( )。
    a、p->next=head;myrear->next=p;head=p;
    b、head->next=p;myrear->next=p;head=p;
    c、myrear->next=p;head=p;head->next=p;
    d、myrear->next=p;head=p;p->next=head;

3、对于一个循环单链表,若头指针为head,表中的某个结点p是最后一个结点的特征是( )。
    a、p->next==null
    b、head==null
    c、head->next=p
    d、p->next==head

第5讲 双链表和静态链表(时长:31分41秒)随堂测验

1、在双链表中,任意一个结点中有( )个指针。
    a、1
    b、2
    c、0
    d、3

2、相对于顺序表而言,静态链表的优点是:在执行插入和删除操作时,只需修改下标,不需要移动表中的元素。

3、在一个非空的双链表中,若p所指的结点有前驱和后继,则执行p->next->prior=p=p->prior->next。

单元测试

1、关于线性表的链式存储,以下说法正确的是( )
    a、可方便地进行随机存取
    b、存储密度大
    c、插入、删除运算方便
    d、以上都不对

2、下面关于线性表的叙述中,错误的是哪一个?( )
    a、线性表采用顺序存储,便于进行插入和删除操作
    b、线性表采用顺序存储,必须占用一片连续的存储空间
    c、线性表采用链接存储,便于插入和删除操作
    d、线性表采用链接存储,存储空间连不连续都可以

3、如果线性表最常用的操作是取第i个结点及其前驱,则采用( )存储方式最节省时间。
    a、单向链表
    b、双向链表
    c、顺序表
    d、单向循环链表

4、对于使用带头结点的单链表,若头指针为head,判定该表为空的条件是( )。
    a、head!=null
    b、head->next==head
    c、head==null
    d、head->next==null

5、对于使用不带头结点的单链表,若头指针为head,判定该表为空的条件是( )
    a、head==null
    b、head->next==null
    c、head->next=head
    d、head!=null

6、已知指针p指向在一个单链表中的某个结点,若在该结点之后插入指针s指向的结点,则需执行( )。
    a、s->next=p->next;p->next=s;
    b、p->next=s;s->next=p;
    c、s->next=p->next;s=p;
    d、s->next=p->next;s=p->next;

7、已知指针p指向单链表head中的某个结点,若删除其后继结点,则需执行()。
    a、r=p; p->next=r->next; free(r);
    b、r=p->next; p=r->next; free(r);
    c、r=p->next; p->next=r->next; free(r);
    d、r=p->next; r->next=p->next; free(r);

8、对于一个具有n个结点的单链表,在给定值为x的结点后插入一个新结点的时间复杂度为()
    a、o(1)
    b、o(n)
    c、o(n^2)
    d、

9、在单链表head中,指针p所指结点是线性表中最后一个元素的条件是( )
    a、p==null
    b、p->next==null
    c、p!=null
    d、p->next!=null

10、在循环单链表head中,指针p所指结点是线性表中最后一个元素的条件是( )
    a、p==head
    b、p->next==null
    c、p->next==head
    d、p==null

11、与单链表相比,双链表的优点之一是 ( ) 。
    a、更节约存储空间
    b、能够方便的访问某结点的前驱结点
    c、可以进行随机访问
    d、插入、删除操作更简单

12、取链式表的第i个元素的时间与i值的大小有关。

13、静态链表中指针表示的是下一元素在数组中的下标。

14、对于一个头指针为h的带头结点的循环单链表,判定该表为空表的条件是h->next=null。

15、设p为指向长度为n的循环单链表上某结点的指针,从p开始可以遍历整个单链表。

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

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

编程作业

1、实现单链表的初始化,插入、删除、访问等基本操作。 单链表为带头结点的单链表结构。

2、假设带头结点的单链表l是升序排列的,将值为x的结点插入到链表l中,并保持链表有序性。

3、删除带头结点单链表l中所有值为x的结点。

4、已知两个带头结点的单链表l1和l2中的结点值均已按升序排序,设计一个算法,将l1和l2合并成一个升序的带头结单链表,并用l1记录新的带头结点单链表。

5、编写一个程序,用尽可能快的方法返回带头结点单链表中倒数第k个结点的地址,如果不存在,则返回error。

第四周 栈和队列(时长:79分33秒)

第1讲 栈(时长:29分45秒)随堂测验

1、判定一个顺序栈st为(元素个数最多为maxsize,top初始值为0,指向下一个待入栈的元素的下标)空的条件为( )。
    a、st.top==0
    b、st.top!=maxsize-1
    c、st.top==maxsize-1
    d、st.top!=0

2、表达式a*(b c)-d的后缀表达式是 ( )。
    a、- * a b c d
    b、a b c * d -
    c、a b c * d -
    d、a b c d * -

3、若用一个数组data[0..n-1]存储顺序栈,初始栈顶指针top为0,则要让元素x入栈(假设栈不满),应执行()操作。
    a、data[top]=x;top--;
    b、data[top]=x;top ;
    c、top--; data[top]=x;
    d、top ; data[top]=x;

4、已知一个栈的进栈序列是abc,中间可以出栈,以下出栈序列正确的是()。
    a、cab
    b、abc
    c、bac
    d、acb

5、顺序栈中元素值的大小是有序的

第2讲 队列(时长:49分38秒)随堂测验

1、若用一个不带头结点的单链表表示队列,队头和队尾指针分别为front和rear,则判断队空的条件是( )。
    a、front == rear
    b、front == null
    c、front!==null
    d、rear!==null

2、若用一个不带表头节点的单链表表示队列,若队列非空,则在进行删除操作时,( )。
    a、仅修改头指针
    b、头、尾指针都要修改
    c、仅修改尾指针
    d、头指针一定要修改、尾指针可能要修改

3、循环队列qu(元素个数最多为maxsize ,front队首指针指向队首元素位置,rear队尾指针指向下一个待入队元素的下标,采用浪费一个空间的方式进行存储),元素个数是( )。
    a、(qu.rear-qu.front maxsize)% maxsize
    b、(qu.rear-qu.front)% maxsize
    c、qu.rear-qu.front 1
    d、qu.rear-qu.front

4、栈和队列的共同点是只允许在端点处插入和删除元素。

单元测试

1、若元素a、b、c、d、e依次进栈后,栈顶元素是( )。
    a、e
    b、d
    c、b
    d、c

2、元素a、b、c依次进栈,中间允许出栈,若出栈序列为bca,经过栈的操作是 ( )。
    a、push push push pop pop pop
    b、push push pop push pop pop
    c、push pop push pop push pop
    d、push pop push push pop pop

3、元素a、b、c依次进栈,中间允许出栈,则不可能的出栈序列是 ( )。
    a、cab
    b、bca
    c、bac
    d、abc

4、某算法在数据处理过程中需要存储一些中间数据,并且后存储的数据先处理,则使用()来存储这些数据更合理。
    a、链式表
    b、栈
    c、队列
    d、顺序表

5、表达式5*6-7*8 的后缀表达式是(  )。
    a、56*78*-
    b、5678**-
    c、-**5678
    d、5678*-*

6、表达式3 5 7*8 的后缀表达式是(  )。
    a、35 78*
    b、3578*
    c、 35*78
    d、3578 *

7、若一个栈用数组data[0..n-1]存储,初始栈顶指针top为-1,则以下元素x进入栈的正确操作是( )。
    a、data[top]=x;top ;
    b、data[top]=x;top--;
    c、top--; data[top]=x;
    d、top ; data[top]=x;

8、若一个栈用数组data[0..n-1]存储,初始栈顶指针top为0,则以下元素x进入栈的正确操作是( )。
    a、top ; data[top]=x;
    b、top--; data[top]=x;
    c、data[top]=x;top--;
    d、data[top]=x;top ;

9、判定一个顺序栈st(数组大小为maxsize,初始st.top==0)栈满的条件是( )。
    a、st.top==-1
    b、st.top==0
    c、st.top==maxsize-1
    d、st.top==maxsize

10、链栈与顺序栈相比,链式栈有一个明显的优点,它是()。
    a、判断栈空更方便
    b、一般不会出现栈满的情况
    c、插入操作更方便
    d、删除操作更加方便

11、若不带头结点的链栈其栈顶指针为top,则插入一个s指针所指向的结点时,应进行如下()操作。
    a、s->next=top; top=s;
    b、s->next=top->next; top->next=s;
    c、s->next=top; top->next=s;
    d、top>next = s;

12、若不带头结点的链栈其栈顶指针为top,则删除栈顶元素,应进行如下()操作。
    a、top=top->next; s=top; free(s);
    b、s=top; top=top->next; free(s);
    c、s=top->next; top->next=s->next;free(s);
    d、s=top; top->next=s->next;free(s);

13、顺序循环队列qu的队满条件(front队首指针指向队首元素,rear队尾指针指向队尾元素的后一个位置,采用浪费一个空间的方式进行存储,队列元素最大个数为maxsize)是 ()。
    a、(qu.rear 1)%maxsize==qu.front
    b、(qu.rear 1)%maxsize==qu.front 1
    c、qu.rear==qu.front
    d、(qu.rear 1)%maxsize==(qu.front 1)%maxsize

14、假设用不带头结点的单链表表示队列,front和rear分别指向队头和队尾,则判断队空的条件是 ()。
    a、front == null
    b、front!==null
    c、rear!==null
    d、front == rear

15、为解决计算机主机与打印机之间速度不匹配问题,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中读取数据。该缓冲区最适合采用的逻辑结构是( )。
    a、顺序表
    b、栈
    c、链式表
    d、队列

16、队列操作的原则是( )。
    a、先进先出
    b、后进先出
    c、只能进行插入操作
    d、只能进行删除操作

17、栈和队列的不同点是栈只能在一端进行插入删除操作,而队列在不同端进行插入删除操作。

18、栈和队列均为操作受限的线性表。

19、顺序循环队列解决了空间溢出的问题。

20、顺序循环队列解决了顺序队列的假溢出问题。

21、栈是一种插入与删除操作均在表的一端进行的线性表,具有后进先出的特点。

22、在具有n个元素的非空顺序队列中, 插入或者删除一个元素的操作时间复杂度是o(n)。

第五周 字符串和数组 (上)(时长:73分31秒)

第1讲 字符串的定义以及顺序串的实现(时长:29分34秒)随堂测验

1、假设空串是任何串的子串,则串s=“computer”的子串个数是( )
    a、8
    b、9
    c、36
    d、37

2、两个字符串相等的充分必要条件是()
    a、两个字符串中对应位置上的字符相等
    b、两个字符串的长度相等且对应位置上的字符也相等
    c、两个字符串的长度相等
    d、以上说法都不对

3、下列说法正确的是()
    a、空串就是空白串
    b、串只可以采用顺序存储,不可以采用链式存储
    c、空串是任意字符串的子串
    d、在c标准中,char s[m]最多能表示长度为m的字符串

4、在字符{a, c, g, t}组成的dna序列中,a和t、c和g是互补对。判断一个dna序列中是否存在互补回文串(例如,atcatgat的补串是tagtacta,与原串形成互补回文串)。则dna序列gtacgtac也存在互补回文串。

第2讲 字符串的链式存储实现(时长:32分33秒)随堂测验

1、以下是采用压缩存储的一个链串的节点类型定义: #define nodesize 6 typedef struct node { char data[nodesize]; struct node *next; } linkstrnode; 如果每个字符占1个字节,指针占2个字节,该链串的存储密度为( )。
    a、
    b、
    c、
    d、

2、对于一个链串s,查找第一个字符值为x的算法的时间复杂度为( )
    a、
    b、
    c、
    d、

第3讲 字符串的朴素模式匹配(时长:11分24秒)随堂测验

1、设有两个串s1与s2,求串s2在s1中首次出现位置的运算称作( )
    a、模式匹配
    b、取子串
    c、求串长
    d、串连接

2、在串的简单模式匹配中,当模式串位j与目标串位i比较时,两字符不相等,则i的位移方式是( )。
    a、i不动
    b、i
    c、i=j 1
    d、i=i-j 1

单元测试

1、两个字符串相等的充分必要条件是( )
    a、两个字符串的长度相等且对应位置上的字符也相等
    b、两个字符串中对应位置上的字符相等
    c、两个字符串的长度相等
    d、以上说法都不对

2、设有两个串s和t ,其中t是s的子串,求t在s中首次出现的位置的算法称为( )
    a、串的模式匹配
    b、串连接
    c、取子串
    d、串插入

3、串的长度是指( )。
    a、串中所含字符的个数
    b、串中所含非空格字符的个数
    c、串中所含不同字符的个数
    d、串中所含不同字母的个数

4、以下是采用压缩存储的一个链串的节点类型定义: #define nodesize 8 typedef struct node { char data[nodesize]; struct node *next; } linkstrnode; 如果每个字符占1个字节,指针占2个字节,该链串的存储密度为( )。
    a、1/4
    b、1/3
    c、2/3
    d、4/5

5、若串s=“software”,其子串个数为()
    a、8
    b、9
    c、36
    d、37

6、串是一种特殊的线性表,其特殊性体现在()
    a、可以顺序存储
    b、可以链式存储
    c、数据元素可以是多个字符
    d、数据元素是一个字符

7、int f(char s[])函数判断字符串s 是否是回文,是回文则返回1,否则返回0;如 f("abba")返回1,f("abcba")返回1f("abab")返回0; 对于(1),下列选项正确的是() int f(char s[]) { int i=0,j=0; while(s[j]) j ; for(j--; i < j && s[i] == s[j]; i , j--); return _______(1)_______ ; }
    a、i>j
    b、i= =j
    c、s[i] = = s[j]
    d、i=j

8、下面关于串的叙述中,不正确的是( )。
    a、串是一种特殊的线性表
    b、串中元素只能是字母
    c、空串就是空白串
    d、串的长度必须大于零

9、在字符{a, c, g, t}组成的dna序列中,a和t、c和g是互补对。判断一个dna序列中是否存在互补回文串(例如,atcatgat的补串是tagtacta,与原串形成互补回文串)。则下面dna序列中存在互补回文串的是()
    a、gtacgtac
    b、agctagct
    c、aattaatt
    d、ctgatcag

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

11、串只可以采用顺序存储,不可以采用链式存储。

12、空串是任意字符串的子串。

13、空串就是空白串。

14、空串是不含字符的串,长度为0。

编程作业

1、已知字符串采用带结点的链式存储结构,请完成以下函数的编写 1)linkstring substring(linkstring s,int i,int len),在字符串s中从第i个位置起取长度为len的子串,函数返回子串链表。 2)void delstring(linkstring s, int i,int len) ,在字符串s中删除从第i个位置开始,长度为len的子串。 3)linkstring index(linkstring s, linkstring t),查找子串t在主串s中第一次出现的位置,若匹配不成功,则返回null。

2、已知字符串采用顺序存储结构,请完成以下函数的编写: seqstring* substring(seqstring str, int i, int len);//在字符串str中从第i个位置起取长度为len的子串(i从1开始),函数返回子串指针,若子串超出边界返回null。 int index(seqstring s, seqstring t);//查找子串t在主串s中第一次出现的位置,若匹配成功,返回起始位置。若匹配不成功,则返回-1。 void delstring(seqstring *s, int i, int len);//在字符串s中删除从第i个位置开始(i从1开始),长度为len的子串。

3、加密解密

第六周 字符串和数组(下)(时长:62分06秒)

第4讲 数组及其顺序存储(时长:15分18秒)随堂测验

1、数组通常只有两种运算:( )和( )
    a、读取 修改
    b、插入 删除
    c、读取 插入
    d、插入 修改

2、以行序优先顺序存储数组a[100][120];假定a[0][0]的地址为1000, 每个元素占2个字节,则a[5][3]的地址是()
    a、2204
    b、2206
    c、2004
    d、2006

3、数组的维数和维度一旦确定,数组中元素的个数就确定了,不能增加也不能减少。

第5讲 特殊矩阵的压缩存储(时长:16分07秒)随堂测验

1、对特殊矩阵采用压缩存储的目的主要是()
    a、减少不必要的存储空间
    b、对矩阵元素的存储变得简单
    c、去掉矩阵中的多余元素
    d、对矩阵元素的操作更方便

2、对n*n的对称矩阵进行压缩存储,需要保存的数据元素的个数是()
    a、n^2
    b、n
    c、n*(n 1)/2
    d、n*n/2

3、(2016年考研真题 第4题) 有一个100阶的三对角矩阵m,其元素 按行优先次序压缩存入下标从0开始的一维数组n中。元素 在n中的下标是()
    a、86
    b、87
    c、88
    d、89

第6讲 稀疏矩阵的三元组表示(时长:14分50秒)随堂测验

1、适用于压缩存储稀疏矩阵的两种存储结构是()
    a、三元组表和十字链表
    b、三元组表和邻接矩阵
    c、十字链表和二叉链表
    d、十字链表和邻接矩阵

2、使用三元组来保存稀疏矩阵中的非零元素,三元组包含非零元素的()
    a、个数
    b、行号
    c、列号
    d、元素值

3、使用三元组顺序表作为稀疏矩阵中的物理结构,对元素可以进行随机访问

第7讲 稀疏矩阵的转置(时长:15分51秒)随堂测验

1、以下物理结构中,不能够对数据元素进行随机访问的是( )
    a、三元组顺序表
    b、三对角矩阵的压缩存储
    c、数组的顺序存储
    d、对称矩阵的压缩存储

单元测试

1、设有10×5的数组a,其每个元素占2个字节,按行优先顺序存储,若已知a[3][4]在内存中的地址是1038,则a[6][0]的地址是( )
    a、1060
    b、1030
    c、1098
    d、1068

2、设有10×6的数组a,数组下标从0,0开始,其每个元素占2个字节,按列优先顺序存储,若已知a[3][4]在内存中的地址是1086,则a[4][5]的地址是( )
    a、1296
    b、1140
    c、1108
    d、1054

3、将10×5 的二维数组a按照行优先顺序存储到一维数组b中,则b[35]中存储的二维数组元素是( )。
    a、a[6][0]
    b、a[7][0]
    c、a[7][1]
    d、a[6][1]

4、对特殊矩阵采用压缩存储的目的主要是( )。
    a、对矩阵元素的存储变得简单
    b、表达变得简单
    c、减少不必要的存储空间
    d、去掉矩阵中的多余元素

5、n*n的三对角矩阵,需要保存的数据元素的个数是( )。
    a、3n-2
    b、3n-1
    c、3n
    d、n(n 1)

6、某稀疏矩阵a采用三元组顺序表作为存储结构,对于矩阵元素的赋值运算a[i][j]=x,不可能的操作是( )。
    a、修改某个三元组的元素值
    b、删除一个三元组
    c、插入一个新的三元组
    d、修改某个三元组的行号或列号

7、使用三元组来保存稀疏矩阵中的非零元素,三元组不包括非零元素的( )
    a、行号
    b、列号
    c、元素值
    d、个数

8、以下物理结构中,不能够对数据元素进行随机访问的是( )
    a、三对角矩阵的压缩存储
    b、三元组顺序表
    c、数组的顺序存储
    d、对称矩阵的压缩存储

9、对稀疏矩阵进行压缩存储方法一般有两种,分别为三元组顺序表和十字链表

10、数组是一种定长的线性表,数组的基本操作有存取、修改、检索和排序等,没有插入与删除操作。

11、数组是一种非线性结构,除了插入与删除操作外,数组的基本操作还有存取、修改、检索和排序等操作。

12、使用三元组顺序表或十字链表作为稀疏矩阵中的物理结构,对元素可以进行随机访问。

编程作业

1、实现稀疏矩阵(采用三元组表示法)的基本运算

2、实现稀疏矩阵(采用三元组表示法)的加法运算

第七周 树和二叉树(上)(时长:83分48秒)

第1讲 树的基本概念和存储结构(时长:23分18秒)随堂测验

1、在一棵度为3的树中,度为3结点数为2个,度为2的结点数为1个,度为1的结点数为2个,则度为0的结点数为( )个
    a、4
    b、5
    c、6
    d、7

2、如图所示,d结点的度等于()。
    a、2
    b、3
    c、4
    d、1

3、在树的双亲表示法中,查找孩子的时间复杂度是()
    a、
    b、
    c、
    d、

第2讲 树的遍历算法以及层次遍历的实现(时长:16分05秒)随堂测验

1、如图所示,该树的先序遍历序列是( )
    a、defbca
    b、abfedc
    c、abcdef
    d、abdefc

2、树的层序遍历实现时借助栈实现的。

第3讲 二叉树的定义和性质(时长:22分29秒)随堂测验

1、高度为4的满二叉树结点个数为()。
    a、4
    b、15
    c、16
    d、5

2、二叉树是度为2的有序树。

3、只有度为0和度为2的结点的二叉树就是满二叉树

第4讲 二叉树的存储(时长:14分14秒)随堂测验

1、完全二叉树的存储结构通常采用顺序存储结构。

第5讲 树、森林与二叉树的转换(7分38秒)随堂测验

1、树结构中某结点的第3个孩子,转换成二叉树后,应该是()
    a、该结点的右孩子
    b、该结点的左孩子的右孩子的右孩子
    c、该结点的左孩子
    d、该结点的左孩子的右孩子

2、(2019年 第2题) 若将一棵树t转化为对应的二又树bt,则下列对bt的遍历中,其遍历序列与t的后根遍历序列相同的是 ()
    a、先序遍历
    b、中序遍历
    c、后序遍历
    d、层次遍历

单元测试

1、对于二叉树,下列说法正确的是()
    a、二叉树是非线性数据结构,因此它不能用顺序存储结构存储
    b、二叉树是非线性数据结构,因此只能使用链式存储结构进行存储
    c、二叉树是非线性数据结构,因此它既不能顺序存储结构存储,也不能用链式存储结构存储
    d、二叉树是非线性数据结构,既可以使用顺序存储结构存储,也可以链式存储结构进行存储

2、树的后根遍历序列等同于该树对应的二叉树的()
    a、先序遍历
    b、中序遍历
    c、后序遍历
    d、层次遍历

3、一棵深度为6的满二叉树有( )个分支结点。
    a、31
    b、32
    c、63
    d、64

4、在一棵二叉树中,度为零的结点的个数为n0,度为2的结点的个数为n2,则有n0等于( )
    a、无法确定
    b、n2 1
    c、n2-1
    d、n2

5、若在一棵度为3的树中,有3个度为3的结点,2个度为2的结点,2个度为1的结点,该树中叶子结点的个数为()
    a、9
    b、7
    c、6
    d、16

6、若某棵二叉树的后序遍历序列为abcdefg,则其根结点值是( )
    a、a
    b、g
    c、b
    d、不能确定

7、若某棵二叉树的中序根遍历序列为abcdefg,则其根结点值是( )
    a、a
    b、b
    c、g
    d、不能确定

8、以下关于二叉树的说法中正确的是()
    a、二叉树就是度为2的树
    b、二叉树中每个结点的度都小于等于2
    c、二叉树中每个结点的度都为2
    d、二叉树就是度为2有序树

9、二叉树的先序和中序遍历序列相同,则此二叉树为()
    a、空树或者任一结点最多只有左子树
    b、空树或者任一结点最多只有右子树
    c、只有一个根结点
    d、空树或者根结点无左子树

10、具有1024个结点的非空二叉树的最小深度为( )
    a、9
    b、10
    c、11
    d、12

11、若知道一棵二叉树的先序和中序遍历序列,便可以唯一确定该二叉树。

12、把一棵树转换为二叉树后,这棵二叉树是唯一的,且根结点都没有右孩子。

13、若二叉树用二叉链表作存储结构,则在n个结点的二叉树链表中只有n-1个非空指针域。

14、具有12个结点的完全二叉树,叶子结点个数为6。

15、在二叉树结点的先序序列,中序序列和后序序列中,所有叶子结点的先后顺序是相同的。

16、树型结构最适合用来描述层次结构。

编程作业

1、树的基本运算

2、求树中叶子结点的个数以及树t中结点值为x的结点的层号 int leafnodes(tree t); int level(tree t,datatype x,int h);

第八周 树和二叉树(下)(时长:82分06秒)

第6讲 二叉树的遍历(时长:37分03秒)随堂测验

1、以下函数,能正确实现二叉树后序遍历功能的是()
    a、void postorder(bintree t) { if (t) { postorder(t->lchild); postorder(t->rchild); printf(“%c”,t->data); } }
    b、void postorder(bintree t) { postorder(t->lchild); postorder(t->rchild); printf(“%c”,t->data); }
    c、void postorder(bintree t) { if (t) { postorder(t->lchild); printf(“%c”,t->data); postorder(t->rchild); } }
    d、void postorder(bintree t) { if (t) { printf(“%c”,t->data); postorder(t->lchild); postorder(t->rchild); } }

2、如图所示的二叉树,其前序遍历序列为________(答案不要有空格)

3、如图所示的二叉树,其中序遍历序列为________(答案不要有空格)

4、如图所示的二叉树,其后序遍历序列为________(答案不要有空格)

第8讲 线索二叉树(时长:18分02秒)随堂测验

1、引人线索二叉树的目的的是( )。
    a、加快查找结点的前驱或后继的速度
    b、为了能在二叉树中方便地进行插人与侧除
    c、为了能方便地找到双亲
    d、使二叉树的遍历结果唯一

2、n个结点的线索二叉树上含有的线索数为( )。
    a、n
    b、2n
    c、n 1
    d、n-1

3、若x是二叉中序线索树中一个有左孩子的结点,且x不为根,则x的前驱为( )。
    a、x的双亲
    b、x的右子树中最左的结点
    c、x的左子树中最右的结点
    d、x的左子树中最右叶结点

4、下列线索二叉树中(用虚线表示线索),符合后序线索树定义的是()
    a、
    b、
    c、
    d、

第9讲 哈夫曼树(时长:19分54秒)随堂测验

1、(2019年 第3题)对n个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有115个结点,则n的值()
    a、56
    b、57
    c、58
    d、60

2、设有13个值,用它们构成一棵哈夫曼树,则该哈夫曼树共有结点数是( )
    a、13
    b、14
    c、25
    d、26

3、由分别带权为9、2、5、7的四个叶子结点构成一棵哈夫曼树,该树的带权路径长度为()
    a、23
    b、37
    c、44
    d、46

单元测试

1、设有一棵哈夫曼树的结点总数为41,则该哈夫曼树共有( )个叶子结点。
    a、20
    b、21
    c、22
    d、30

2、判断线索二叉树中p所指的结点无右孩子的条件是()
    a、p->ltag==1
    b、p->ltag==0
    c、p->rchild==null
    d、p->rtag==1

3、树中某结点的第3个孩子,转换成二叉树后,应该是()
    a、该结点的右孩子
    b、该结点的左孩子的右孩子
    c、该结点的左孩子的右孩子的右孩子
    d、该结点的右孩子的右孩子的右孩子

4、引入线索二叉树的目的是()
    a、加快查找结点的前驱或后继的速度
    b、为了能在二叉树中方便的进行插入与删除
    c、为了能方便的找到双亲
    d、使二叉树的遍历结果唯一

5、若结点a是中序线索二叉树中一个有右孩子的结点,则a的后继为( )
    a、a的右子树中最左的结点
    b、a的左子树中最右的结点
    c、a的左子树中最右的叶结点
    d、a的右子树中最右的结点

6、根据使用频率为4个字符设计的哈夫曼编码不可能是()
    a、00,10,01,11
    b、111,110,10,0
    c、11,10,1,0
    d、001,000,01,1

7、n个结点的线索二叉树上含有的线索个数为()
    a、n
    b、n-1
    c、n 1
    d、2n

8、给定权值总数有n个,其哈夫曼树的结点总数是2n-1个。

9、哈夫曼树中除了度为1的节点外,还有度为2的节点和叶子节点。

10、哈夫曼树中不存在度为1的结点。

11、哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。

12、判断线索二叉树中*p结点为叶子结点的条件是p->ltag==1 && p->rtag==1。

13、哈夫曼树的带权路径长度等于其中所有结点的带权路径之和。

14、对应于一组权值构造出的哈夫曼树可能不是唯一的。

编程作业

1、二叉树的基本运算

2、根据遍历序列构建二叉树,分别实现根据前序和中序序列,中序和后序序列构建二叉树。

3、按照先序遍历的顺序输出给定二叉树的叶结点

4、哈夫曼树的建立,请完成select函数的编写 void select(huffnode huffmantree[ ], int k, int *s1, int *s2); //从huffmantree数组的0到up-1中找出father为-1的且权重最小的结点赋给s1,s2,(为了保证答案唯一,请让s1的结点编号小于s2)保证每个结点的权重值小于10000。

5、将一棵给定二叉树中所有结点的左、右子女互换。

第九周 图(上)(时长:64分49秒)

第1讲 图的基本概念(时长:19分43秒)随堂测验

1、n个顶点的无向图至多有()条边。
    a、
    b、
    c、
    d、

2、n个顶点的有向图中,顶点的最大度数等于()。
    a、
    b、
    c、
    d、

3、在有向图中,所有顶点的入度之和等于所有顶点的出度之和。

4、如果顶点v到顶点w之间存在一条路径,则称v和w是邻接的。

第2讲 图的存储(时长:22分13秒)随堂测验

1、关于图的邻接矩阵,下列哪个结论是正确的?
    a、有向图的邻接矩阵总是不对称的
    b、有向图的邻接矩阵可以是对称的,也可以是不对称的
    c、无向图的邻接矩阵总是不对称的
    d、无向图的邻接矩阵可以是不对称的,也可以是对称的

2、对于一个具有n个顶点m条边的无向图,若采用邻接矩阵表示,则该矩阵的大小是:
    a、
    b、
    c、
    d、

3、若一个有向图用邻接矩阵表示,则第i个结点的入度就是()
    a、第i行的元素个数
    b、第i行的非零元素个数
    c、第i列的非零元素个数
    d、第i列的零元素个数

4、下面关于图的存储的叙述中,哪一个是正确的?
    a、用邻接矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关
    b、用邻接矩阵法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关
    c、用邻接表法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关
    d、用邻接表法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关

第3讲 图的遍历(时长:22分53秒)随堂测验

1、下列说法不正确的是:
    a、图的遍历是从给定的源点出发每一个顶点仅被访问一次
    b、遍历的基本算法有两种:深度优先遍历和广度优先遍历
    c、图的深度优先遍历是一个递归过程
    d、图的深度优先遍历不适用于有向图

2、图的深度优先遍历类似于二叉树的()
    a、先序遍历
    b、中序遍历
    c、后序遍历
    d、层次遍历

3、在用邻接表表示有n个结点e条边的图时,深度优先遍历算法的时间复杂度为()
    a、
    b、
    c、
    d、

4、图的广度优先遍历类似于二叉树的层次遍历。

单元测试

1、图的深度优先遍历类似于二叉树的()
    a、先序遍历
    b、中序遍历
    c、层次遍历
    d、后序遍历

2、如果从无向图的任一顶点出发进行一次深度优先遍历即可访问所有顶点,则该图一定是 ( )
    a、完全图
    b、有回路
    c、连通图
    d、有回路的连通图

3、在图的广度优先遍历算法中用到一个队列,每个顶点最多进队( )次
    a、1
    b、2
    c、0
    d、不确定

4、下列属于非线性数据结构的是()
    a、线性表
    b、队列
    c、栈
    d、图

5、关于图的邻接矩阵,下列哪个结论是正确的( )
    a、有向图的邻接矩阵一定是不对称的
    b、有向图的邻接矩阵可以是对称的,也可以是不对称的
    c、无向图的邻接矩阵一定不是对称的。
    d、无向图的邻接矩阵可以是不对称的,也可以是对称的。

6、对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,所有顶点邻接表的边结点总数为()
    a、e/2
    b、e
    c、2e
    d、n e

7、在下列邻接表的叙述中,()是正确的。
    a、有向图的邻接表中,第i个顶点的度为第i个链表中结点数的2倍。
    b、求有向图结点的度,必须遍历整个邻接表。
    c、邻接表的表示是唯一的。
    d、邻接表法只能用于有向图的存储。

8、对于简单无向图而言,一条回路至少含有()条边。
    a、2
    b、3
    c、4
    d、5

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

10、图的深度优先遍历算法可以应用于判断回路问题。

11、稠密图更适合采用邻接矩阵存储。

12、在图的表示法中,表示形式唯一的是邻接矩阵。

13、广度优先遍历类似于二叉树的层次遍历。

14、具有n个顶点的无向连通图,至少有n-1条边。

15、任何连通图的连通分量只有1个。

16、对于网络而言,加权边的权通常满足三角不等式(即:两边之和大于第三边)。

17、无向图g的连通分量是g的极大连通子图。

18、有向图和无向图都具有强连通分量。

19、如果顶点v到顶点w之间存在一条路径,则称v和w是邻接的。

第十周 图(下)(时长:46分50秒)

第4讲 图的最小生成树(时长:34分34秒)随堂测验

1、任何一个带权无向连通图的最小生成树()
    a、不一定存在
    b、是唯一的
    c、一定是不唯一的
    d、一定存在,但是可能是不唯一的

2、如图所示的具有 7 个结点的网 g,采用prim算法,从3号结点开始,给出该网的最小生成树。下列哪个选项给出了正确的树结点收集顺序?
    a、3654102
    b、3165402
    c、3615402
    d、36524102

3、图通过bfs得到的生成树的树高小于或者等于通过dfs得到的生成树的树高。

第5讲 最短路径(时长:12分16秒)随堂测验

1、对于给定的有权无向图g,下列哪个说法是正确的()
    a、g的最小生成树中,任意一对顶点间的路径必是它们在g中的最短路径
    b、设顶点v到w的最短路径为p。若我们将g中每条边的权重都加1,则p一定仍然是v到w的最短路径
    c、单源最短路问题可以用o(∣e∣ ∣v∣)的时间解决
    d、以上都不对

2、使用迪杰斯特拉(dijkstra)算法求下图中从顶点1到其他各顶点的最短路径,依次得到的各最短路径的目标顶点是()
    a、5, 2, 3, 4, 6
    b、5, 2, 3, 6, 4
    c、5, 2, 4, 3, 6
    d、5, 2, 6, 3, 4

3、数据结构中dijkstra算法用来解决最小生成树问题的

单元测试

1、任何一个无向连通网的最小生成树()。
    a、不一定存在
    b、只有1棵
    c、至少有1棵
    d、一定存在多棵

2、用kruskal算法,求下图的最小生成树时,依次得到的树边为()
    a、be1、af2、ed3、ba4、ac6
    b、be1、ed3、ba4、af2、ac6
    c、ab4、be1、ed3、af2、ac6
    d、be1、af2、ba4、ed3、ac6

3、在求最小生成树时,kruskal算法更适合于()。
    a、有向图
    b、无向图
    c、稀疏图
    d、稠密图

4、从b点出发用prim算法,求下图的最小生成树时,依次得到的树边为()。
    a、be1、af2、ed3、ba4、ac6
    b、be1、ed3、ba4、af2、ac6
    c、ab4、be1、ed3、af2、ac6
    d、be1、af2、ba4、ed3、ac6

5、最小生成树指的是()
    a、由连通网所得到的边数最少的生成树
    b、由连通网所得到的顶点数相对较少的生成树
    c、连通网中所有生成树中权值之和为最小的生成树
    d、连通网的极小连通子图

6、设无向图 g=(v, e)和 g' =(v', e' ),如果 g' 是 g 的生成树,则下面的说法中错误的是()
    a、g' 为 g 的子图
    b、g' 为 g 的连通分量
    c、g' 为 g 的极小连通子图且 v = v'
    d、g' 是 g 的一个无环子图

7、图的生成树( ), n 个顶点的生成树有()条边。
    a、不唯一,n-1
    b、不唯一,n
    c、唯一,n-1
    d、不唯一,n

8、在一个带权连通图g中,权值最小的边一定包含在g的( )生成树中。
    a、某个最小
    b、所有最小
    c、广度优先
    d、深度优先

9、航线可以用有向图表示。下列哪一种算法最适合在任何一对城市之间寻找最经济的飞行路线
    a、bfs
    b、dfs
    c、prim
    d、dijkstra

10、迪杰斯特拉算法求最短路径时,是按照路径长度递增的顺序求解的。

11、数据结构中dijkstra算法是用来求解最短路径的。

12、在用kruskal算法求解带权连通图的最小生成树时,选择权值最小的边的原则是该边不能在图中构成回路。

13、图的简单路径是指顶点不重复的路径。

编程作业

1、求无向图(邻接表表示)中某个顶点的度

2、无向图(邻接表表示)的基本运算(bfs和dfs)

3、求无向连通图(邻接表表示)的所有深度优先遍历序列

4、编程题:求解两个动物之间通信最少翻译问题(广度优先遍历算法应用)

5、利用prim算法求解最小生成树

第十一周 检索(时长:77分41秒)

第2讲 基于线性表的检索(时长:22分11秒)随堂测验

1、对于表长为n的查找表,如果采用顺序查找,查找失败时的平均查找长度是( )。
    a、(n 1)/2
    b、n/2
    c、n-1
    d、n

2、折半查找一个长度为56的有序表,若查找不成功,最少需要比较( )次关键字。
    a、5
    b、4
    c、7
    d、6

3、二分查找过程所对应的判定树是一棵二叉排序树。

4、在有序的单链表上也可以进行二分查找。

第3讲 二叉排序树(时长:24分17秒)随堂测验

1、将{ 32, 2, 15, 65, 28, 10 }依次插入初始为空的二叉排序树,则该树的后序遍历结果是()
    a、2, 10, 15, 28, 32, 65
    b、32, 2, 10, 15, 28, 65
    c、10, 28, 15, 2, 65, 32
    d、32, 2, 15, 10, 28, 65

2、对二叉搜索树进行什么遍历可以得到从小到大的排序序列()
    a、前序遍历
    b、后序遍历
    c、中序遍历
    d、层次遍历

3、在二叉排序树中,凡是新插入的结点都是叶子结点。

第4讲 散列检索(时长:22分50秒)随堂测验

1、采用线性探测法解决冲突时所产生的一系列后继散列地址:()
    a、必须大于等于原散列地址
    b、必须小于等于原散列地址
    c、可以大于或小于但不等于原散列地址
    d、对地址在何处没有限制

2、在散列表中,所谓同义词就是:()
    a、两个意义相近的单词
    b、具有相同散列地址的两个元素
    c、被映射到不同散列地址的一个元素
    d、被不同散列函数映射到同一地址的两个元素

3、设数字序列 {1, 16, 29,61,4, 51, 25,12} 在大小为14的散列表中根据散列函数 h(x)=x,并用线性探测法解决冲突后,得到的下标对应为()
    a、1, 3, 4, 9, 5,12,13,0
    b、1, 3, 2, 9, 5,12,13,0
    c、1, 3, 4, 9, 5,12,13,11
    d、1, 3, 4, 9, 5,12,11,13

单元测试

1、采用顺序查找法查找一个长度为n 的线性表,则查找成功(假设查找概率相等)时,平均比较次数为()
    a、n/2
    b、(n-1)/2
    c、(n 1)/2
    d、n

2、对线性表进行二分检索时,线性表必须采用()
    a、链式存储
    b、顺序存储,且结点之间是有序排列的。
    c、链式存储,且结点之间是有序排列的
    d、顺序存储,不要求结点之间可是有序排列的

3、有序数组a[11],下标从0开始,使用二分检索进行查找,则查找到a[7]的查找路径(下标序列)为( )
    a、5,7
    b、5,8,7
    c、5,8,6,7
    d、1,4,7

4、设有一组关键字为{29,40,23,1,92,21,88,14,55,11}的记录,若用拉链地址法构造散列表,散列函数为h(key)=key mod 13,散列地址为1的链中有( )个记录。
    a、3
    b、4
    c、2
    d、5

5、顺序查找n个元素的顺序表,若查找成功,则比较关键字的次数最多为( )次
    a、n
    b、n-1
    c、n/2
    d、(n 1)/2

6、用二分法对有序数组a[16]进行查找,下标从0开始,若待查元素为x,且a[4]    a、7,3,5,4
    b、7,3,5
    c、7,3,4
    d、8,3,5,4

7、二分检索的时间复杂性为()
    a、
    b、
    c、o(n)
    d、o(n^2)

8、分别以下列序列构造二叉排序树,与用其它三个序列所构造的结果不同的是( )
    a、(120,90, 140, 60, 100)
    b、(120,60, 140, 90, 100)
    c、(120,140, 90, 100, 60)
    d、(120,140, 90, 60,100)

9、设散列表长为13,哈希函数是h(key)=key,表中已有数据的关键字为26,5,17,20共4个,现要将关键字为60的结点加到表中,用二次探测再散列法解决冲突,则放入的位置是( )
    a、7
    b、9
    c、8
    d、1

10、设散列表长为13,哈希函数是h(key)=key,表中已有数据的关键字为26,5,17,20共4个,现要将关键字为60的结点加到表中,用线性探测再散列法解决冲突,则放入的位置是( )
    a、7
    b、8
    c、3
    d、2

11、用二分(对半)检索法,查找表的元素的速度一定比用顺序法快。

12、若将100个元素散列到100000个单元的哈希表中,则一定不会产生冲突。

13、顺序查找n个元素的顺序表,当使用监视哨时,若查找失败,则比较关键字的次数为n次。

14、对二叉排序树进行中序遍历,得到的序列一定是有序的。

15、在二叉排序树中插入一个结点,该结点一定在叶子上。

16、在顺序表(10,20,30,40,50,60,70)中,用二分(折半)查找法查找关键码值20,需做的关键码比较次数为_____。

17、对长度为99的顺序表,在等概率情况下,查找成功时的平均查找长度为______。(写整数)

18、哈希表长度为15,哈希函数采用除留余数法,即h(k)=k%p,那么p的取值应该是_________ 。

编程作业

1、二分检索算法的实现

2、顺序检索算法的实现

3、二叉排序树的基本运算,完成如下两个函数 bool insertbst(bstree *pt,elementtype x);//在以*pt为根结点的二叉排序树中,插入一个关键字为x的结点,返回二叉排序树的根结点,若存在关键字为x的结点,不插入并返回false,否则插入该结点,并返回true bstree searchbst(bstree t,elementtype x);//在以t为根结点的二叉排序树中,查找一个关键字为x的结点,若不存在关键字为x的结点,返回null,否则返回该结点的指针。

4、实现散列表的相关运算,完成如下三个函数 void inserthash(hashtable h, elementtype key); //将关键字为key的记录插入到h中,状态默认为legitimate,若关键字为key的记录已经在hash表中,则不作任何处理。不考虑表满的情况,假设表足够大。 int deletehash(hashtable h, elementtype key); //将关键字为key的记录从h中删除,修改单元状态为deleted,并返回1,若关键字为key的记录不存在,返回0 int find( hashtable h, elementtype key ); //函数find 使用的散列函数hash( key, h->tablesize )从散列表h中查到key的位置并返回。 //如果key不存在,则返回error。

第十二周 排序(上)(时长:49分56秒)

第2讲 选择排序(时长:23分13秒)随堂测验

1、下面给出的四种排序算法中,( )是稳定的排序。
    a、插入排序
    b、堆排序
    c、希尔排序
    d、选择排序

2、假定对元素序列(7, 3, 5, 9, 1, 12)进行堆排序,并且采用小根堆,则由初始数据构成的初始堆为( )。
    a、1, 3, 5, 7, 9, 12
    b、1, 3, 5, 9, 7, 12
    c、1, 5, 3, 7, 9, 12
    d、1, 5, 3, 9, 12, 7

3、对一组数据(84,47,25,15,21)排序,数据的排列次序在排序的过程中的变化情况为: (1) 84 47 25 15 21 (2) 15 47 25 84 21 (3) 15 21 25 84 47 (4) 15 21 25 47 84则采用的排序法是()
    a、堆排序
    b、冒泡排序
    c、选择排序
    d、快速排序

第3讲 交换排序(时长:21分22秒)随堂测验

1、下列那种排序算法用了分治法()
    a、快速排序
    b、直接选择排序
    c、堆排序
    d、冒泡排序

2、数据序列{ 3, 1, 4, 11, 9, 16, 7, 28 }只能是下列哪种排序算法的两趟排序结果()
    a、冒泡排序
    b、快速排序
    c、插入排序
    d、堆排序

3、快速排序算法是稳定的。

单元测试

1、使用冒泡排序方法对关键字序列(25,54,47,27,68,20)进行排序,第一趟排序之后的序列是()
    a、(25,47,27,54,20,68)
    b、(25,47,27,20,54,68)
    c、(25,27,47,54,20,68)
    d、(25,47,27,20,68,54)

2、使用直接选择排序方法对关键字序列(25,54,47,27,68,20)进行升序排序,第一趟排序之后的序列是()
    a、(20,25,54,47,27,68)
    b、(20,54,47,27,68,25)
    c、(54,25,47,27,68,20)
    d、(25,47,27,54,20,68)

3、将关键字(68,45,27,54,20,25)按从大到小排列,利用堆排序的方法建立的初始小根堆为( ) 。
    a、(20,45,25,54,68,27)
    b、(20,68,25,54,45,27)
    c、(20,68,27,54,45,25)
    d、(20,54,25,45,68,27)

4、设有500000个待排序的记录,如果只需要选出其中关键字最小的100个记录,则使用下列( )方法最快。
    a、直接选择排序
    b、快速排序
    c、冒泡排序
    d、堆排序

5、冒泡排序算法在()情况下,算法效率最高。
    a、初始有序
    b、初始逆序
    c、初始无序
    d、以上答案都不对

6、排序时扫描待排序记录序列,依次比较相邻的两个元素的大小,逆序时就交换位置,这是( )排序方法的基本思想。
    a、直接选择排序
    b、堆排序
    c、快速排序
    d、冒泡排序

7、以下是不稳定的排序算法的是( )
    a、直接选择排序
    b、冒泡排序
    c、快速排序
    d、堆排序

8、以下关键字序列不符合堆的定义的是()。
    a、(12, 36, 24, 85, 47, 30, 53, 91)
    b、(8, 21, 42, 35, 85, 53)
    c、(85, 53, 42, 21, 8, 35)
    d、(85, 35, 42, 21, 8, 53)

9、假定在待排序的数据表中,存在多个具有相同键值的记录,若经过排序后,这些记录的相对次序仍然保持不变。则该排序算法是稳定的

10、冒泡排序算法的排序趟数与序列的初始状态有关。

11、内排序要求数据一定要以顺序方式存储。

12、直接选择排序算法的时间复杂度和序列的初始状态有关。

13、冒泡排序在最好情况下的时间复杂度是o(n)。

14、快速排序算法平均时间复杂度和最坏时间复杂度均为o(nlogn)。

第十三周 排序(下)(时长:42分11秒)

第4讲 插入排序(时长:20分34秒)随堂测验

1、若数据元素序列{ 11,12,13,7,8,9,23,4,5 }是采用下列排序方法之一得到的第二趟排序后的结果,则该排序算法只能是()
    a、冒泡排序
    b、选择排序
    c、插入排序
    d、shell排序

2、下列排序算法中,哪种算法可能出现:在最后一趟开始之前,所有的元素都不在其最终的位置上?(假设待排序元素个数大于2)
    a、冒泡排序
    b、选择排序
    c、插入排序
    d、快速排序

3、shell排序算法是稳定的。

第5讲 归并排序(时长:11分00秒)随堂测验

1、就排序算法所用的辅助空间而言,堆排序、快速排序、归并排序的关系是()
    a、堆排序 < 归并排序 < 快速排序
    b、堆排序 > 归并排序 > 快速排序
    c、堆排序 < 快速排序 < 归并排序
    d、堆排序 > 快速排序 > 归并排序

2、在内部排序时,若选择了归并排序而没有选择插入排序,则可能的理由是:() 1、归并排序的程序代码更短 2、归并排序占用的空间更少 3、归并排序的运行效率更高
    a、仅 2
    b、仅 3
    c、仅 1、2
    d、仅 1、3

3、若数据元素序列{ 22, 25, 18, 20, 5, 30, 2, 19 }是采用下列排序方法之一得到的第一趟排序后的结果,则该排序算法只能是()
    a、快速排序
    b、归并排序
    c、堆排序
    d、选择排序

第6讲 基数排序(时长:10分37秒)随堂测验

1、若对个只有三位数字的整数进行排序,可以用o(n)复杂度将其排序的算法是()
    a、快速排序
    b、插入排序
    c、希尔排序
    d、基数排序

2、对给定序列{ 110,119,7,911,114,120,122 }采用次位优先(lsd)的基数排序,则两趟收集后的结果为:()
    a、7, 110, 119, 114, 911, 120, 122
    b、7, 110, 119, 114, 911, 122, 120
    c、7, 110, 911, 114, 119, 120, 122
    d、110, 120, 911, 122, 114, 7, 119

单元测试

1、最好和最坏时间复杂度均为o(nlogn)且稳定的排序方法是( )
    a、归并排序
    b、快速排序
    c、堆排序
    d、基数排序

2、用某种排序方法对关键字序列(20,84,41,37,15,29,68,35,25)进行排序时,序列的变化情况如下: 15,29,41,35,20,84,68,37,25 则所采用的排序方法是( )
    a、直接插入排序
    b、希尔排序
    c、基数排序
    d、归并排序

3、时间复杂度为o(n^2),且关键字比较次数与待排序记录的初始排列顺序无关且排序不稳定,则该排序算法是
    a、直接选择排序
    b、直接插入排序
    c、shell排序
    d、基数排序

4、以下四种排序法中,要求辅助空间为o(n)的是()
    a、希尔排序
    b、快速排序
    c、堆排序
    d、二路归并排序

5、适合记录个数很大,但待排序关键字位数很少的排序算法是( )。
    a、基数排序
    b、快速排序
    c、希尔排序
    d、二路归并排序

6、在所有排序方法中,( )排序方法使数据的组织采用的是完全二叉树的结构。
    a、堆排序
    b、快速排序
    c、基数排序
    d、直接选择排序

7、设有100000个待排序的记录,如果只需要选出其中关键字最小的100个记录,则使用下列( )方法最快。
    a、堆排序
    b、二路归并排序
    c、基数排序
    d、直接插入排序

8、以下是不稳定的排序算法的是()
    a、简单选择排序
    b、希尔(shell)排序
    c、直接插入排序
    d、归并排序

9、以下是稳定的排序算法的是()
    a、快速排序
    b、冒泡排序
    c、基数排序
    d、堆排序

10、下面各种排序方法中,最好情况下时间复杂度为o(n)的是( ) 。
    a、直接插入排序
    b、快速排序
    c、二路归并排序
    d、冒泡排序

11、基数排序算法是一个稳定的算法。

12、将10个不同的数据进行排序,至少需要比较9次。

13、直接插入排序算法不能保证每趟排序至少能将一个元素放到其最终的位置上。

编程作业

1、实现简单选择排序算法,void selectsort(int r[],int n);

2、二路归并排序算法递归实现,完成void merge(int r[],int n,int u,int m,int v);//将有序段r[u..m],r[m 1..v]归并到r[u..v]

3、快速排序算法递归实现,完成int partition(int r[],int low,int high); //对r[low]..r[high]进行一趟划分,划分算法采用mooc教学视频中的划分策略。

期中测试

算法与数据结构期中考试

1、某字符型循环队列如图所示,队头指针front指向队头元素的位置,队尾指针rear指向队尾元素的下一个位置,则该队列元素为( )。
    a、6789abc
    b、6789abcd
    c、defg12345
    d、defg123456

2、已知一个栈的进栈序列是1、2、3、…、n,其输出序列是p1、p2、…、pn,若p1=n,则pi的值为( )
    a、i
    b、i 1
    c、不确定
    d、n-i 1

3、一个栈的输入序列为1、2、3、4,则下列序列中不可能是栈的输出序列的是( )。
    a、1、4、3、2
    b、1、4、2、3
    c、1、3、2、4
    d、3、2、4、1

4、在长度为n(n≥1)的双链表head中,假设在0..n个位置插入的概率是相等的,则插入一个新结点的时间复杂度为( )。
    a、o(1)
    b、o(n)
    c、
    d、

5、对于一个顺序串s,查找第i个字符的算法的时间复杂度为( )
    a、o(1)
    b、
    c、o(n)
    d、

6、设二维数组a[10][20],每个数组元素占用2个存储单元,若按行优先顺序存放数组元素,若a[0][0]的存储地址为100,则a[3][2]的存储地址是( )
    a、224
    b、162
    c、146
    d、123

7、稀疏矩阵是指( )。
    a、零元素较多且分布无规律的矩阵
    b、总的元素个数较少
    c、零元素较多但是分布有规律的矩阵
    d、以上说法都不对

8、在数据结构中,数据的逻辑结构是指( )
    a、数据元素之间的物理关系
    b、数据元素之间的逻辑关系
    c、数据元素
    d、以上说法都不对

9、在单链表中,要删除某一指定结点,必须先找到该结点的()。
    a、该结点的直接前驱
    b、该结点自身位置
    c、该结点的直接后继
    d、该结点的直接后继的后继

10、若想在单链表中删除指针p所指的结点( p所指的结点既不是第一个也不是最后一个结点)的直接后继,不考虑free语句,则应执行以下( )操作。
    a、p->next=p->next->next;
    b、p->next=p->next;
    c、p=p->next;p->next=p->next->next;
    d、p=p->next->next;

11、不带头结点的单链表head为空的判定条件为( )
    a、head->next==null
    b、head!=null
    c、head==null
    d、head->next=head

12、采用头插法创建不带头结点单链表h,h指向头结点,如果接下来要插入的是s指向的结点,操作语句应为()。
    a、s->next=h->next;h->next=s;
    b、h->next=s; s->next=h->next;
    c、h=s; s->next=h->next;
    d、s->next= h; h=s;

13、设循环队列中数组的下标范围是0—maxsize-1,其头尾指针分别为front和rear,头指针front总是指向队头元素,尾指针rear总是指向队尾元素的下一个位置,则队满的条件为( )。
    a、(rear 1)%maxsize==front
    b、rear==front
    c、rear 1==front
    d、(rear-1)%maxsize==front

14、设循环队列中数组的下标范围是0—maxsize-1,其头尾指针分别为front和rear,头指针front总是指向队头元素,尾指针rear总是指向队尾元素的下一个位置,则其元素的个数为( )
    a、rear-front
    b、rear-front 1
    c、(rear-front)%maxsize 1
    d、(rear-front maxsize) %maxsize

15、在顺序栈中,若栈顶指针top指向栈顶元素的下一个存储单元,且顺序栈的最大容量是maxsize。则顺序栈的判满的条件是( )。
    a、top==0
    b、top==-1
    c、top==maxsize
    d、top==maxsize-1

16、栈的插入和删除操作在( )进行。
    a、栈顶
    b、栈底
    c、任意位置
    d、以上说法都不对

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

18、以下存储结构中,最不适合用来存储链队的链表是()。
    a、只带队头指针的非循环双链表
    b、只带队头指针的循环双链表
    c、只带队尾指针的循环双链表
    d、只带队尾指针的循环单链表

19、循环队列存储在数组a[0..maxsize-1]中,其头尾指针分别为front和rear,头指针front总是指向队头元素,尾指针rear总是指向队尾元素的下一个位置,则元素x入队时的操作为( )。
    a、a[rear]=x;rear=rear 1;
    b、a[rear]=x;rear=(rear 1)%maxsize;
    c、a[rear]=x;rear=(rear 1)%(maxsize 1);
    d、rear=(rear 1)%maxsize; a[rear]=x;

20、若栈采用顺序存储方式存储,现两栈共享空间a[n]:top1代表第1个栈的栈顶指针,top2代表第2个栈的栈顶指针,分别指向实际栈顶位置,栈1的底在a[0],栈2的底在a[n-1],则栈满的条件是( )
    a、|top2-top1|==1
    b、top1 top2==n
    c、top1==top2
    d、top1 1==top2

21、适用于压缩存储稀疏矩阵的两种存储结构是()
    a、三元组表和十字链表
    b、三元组表和邻接矩阵
    c、十字链表和二叉链表
    d、邻接矩阵和十字链表

22、采用多项式的非零项链式存储表示法,如果两个多项式的非零项分别为n1和n2个,最高项指数分别为m1和m2,则实现两个多项式相加的时间复杂度是()
    a、o(n1 n2)
    b、o(m1 m2)
    c、o(n1×n2)
    d、o(m1×m2)

23、算法分析的目的是( )。
    a、研究算法中输入和输出的关系
    b、分析算法的易读性和可行性
    c、分析算法的效率以求改进
    d、找出数据结构的合理性

24、算法的空间复杂度是指( )。
    a、算法本身所占用的存储空间的大小
    b、算法中输入数据所占用的存储空间的大小
    c、算法中所占用的所有存储空间的大小
    d、算法中需要的辅助变量所占用存储空间的大小

25、若某算法的空间复杂度为o(1),则( )。
    a、该算法执行不需要任何空间
    b、该算法执行所需辅助空间大小与问题规模n无关
    c、该算法执行所需总空间大小与问题规模n无关
    d、该算法执行不需要任何辅助空间

26、在一个含有n个元素的顺序表中查找值为x元素,对应算法的时间复杂度为( )。
    a、o(1)
    b、o(n)
    c、
    d、

27、在一个长度为n的顺序表中插入第i个元素时所需要的执行时间( )。
    a、只与该元素的插入位置有关
    b、以上都不对
    c、只与顺序表的长度有关
    d、与该元素的插入位置及顺序表的长度都有关

28、线性表的链式存储结构和顺序存储结构相比,其优点是( )。
    a、查找第i个元素的操作算法实现更简单
    b、便于插入和删除元素
    c、节省存储空间
    d、便于随机存取

29、在以下存储方式中,如果线性表最常用的操作是取第i个元素及其前驱元素,则采用( )最节省时间。
    a、双链表
    b、单链表
    c、顺序表
    d、循环单链表

30、表达式a*(b c)-d的后缀表达式是( )
    a、a b c * d -
    b、a b c d * -
    c、a b c * d -
    d、- * a b c d

31、设一个堆栈的入栈顺序是1、2、3、4、5。若第一个出栈的元素是4,则最后一个出栈的元素一定是()
    a、1
    b、3
    c、5
    d、1或者5

32、假设有5个整数以1、2、3、4、5的顺序被压入堆栈,且出栈顺序为3、5、4、2、1,那么为了获得这样的输出,堆栈大小至少为()
    a、2
    b、3
    c、4
    d、5

33、若将一棵树 t 转化为对应的二叉树 bt,则下列对 bt 的遍历中,其遍历序列与 t 的后根遍历序列相同的是()
    a、先序遍历
    b、中序遍历
    c、后序遍历
    d、按层遍历

34、已知一棵二叉树的树形如下图所示,其后序序列为{ e, a, c, b, d, g, f }。树中与结点a同层的结点是()
    a、c
    b、d
    c、f
    d、g

35、设 t 是非空二叉树,若 t 的先序遍历和后序遍历序列相同,则 t 的形态可能是()
    a、只有一个根结点
    b、没有度为 1 的结点
    c、结点个数大于1,且所有非叶子结点只有左孩子
    d、结点个数大于1,且所有非叶子只有右孩子

36、按照二叉树的定义,具有3个结点的二叉树有()种。
    a、2
    b、3
    c、4
    d、5

37、如果a和b都是二叉树的叶结点,那么下面判断中哪个是对的?()
    a、存在一种二叉树结构,其前序遍历结果是…a…b…,而中序遍历结果是…b…a…
    b、存在一种二叉树结构,其中序遍历结果是…a…b…,而后序遍历结果是…b…a…
    c、存在一种二叉树结构,其前序遍历结果是…a…b…,而后序遍历结果是…b…a…
    d、以上三种都是错的

38、设有一个10阶的对称矩阵a,采用压缩存储方式,以行序为主进行存储,a11为第一个元素,其存储地址为100,每个元素占2个地址空间,则a85的地址为( )
    a、164
    b、144
    c、124
    d、132

39、如图所示,该二叉树的先序遍历结果是( )
    a、a,b,c,d,h,e,i,f,g
    b、a,b,d,h,i,e,c,f,g
    c、h,d,i,b,e,a,f,c,g
    d、h,i,d,b,e,f,g,a,c

40、如图所示,该二叉树的中序遍历结果是( )
    a、a,b,c,d,h,e,i,f,g
    b、a,b,d,h,i,e,c,f,g
    c、h,d,i,b,e,a,f,c,g
    d、h,i,d,b,e,f,g,a,c

41、如图所示,该二叉树的后序遍历结果是( )
    a、a,b,c,d,h,e,i,f,g
    b、a,b,d,h,i,e,c,f,g
    c、h,d,i,b,e,a,f,c,g
    d、h,i,d,e,b,f,g,c,a

42、如图所示,该二叉树的层次遍历结果是( )
    a、a,b,c,d,e,f,g,h,i
    b、a,b,d,h,i,e,c,f,g
    c、h,d,i,b,e,a,f,c,g
    d、h,i,d,b,e,f,g,a,c

43、在完全二叉树中,若一个结点度为1,则它没有( )。
    a、左子树
    b、右子树
    c、左子树和右子树
    d、右子树和兄弟结点

44、设一棵非空完全二叉树 t 的所有叶结点均位于同一层,且每个非叶结点都有 2 个子结点。若 t 有 k 个叶结点,则 t 的结点总数是()
    a、2k
    b、2k-1
    c、
    d、

45、下面的程序段违反了算法的()原则。 void sum() { int n=2; while (n%2==0) n =2; printf(“%d”,n); }
    a、有穷性
    b、确定性
    c、可行性
    d、健壮性

46、在数据结构中,从逻辑上可以把数据结构分成()。
    a、动态结构和静态结构
    b、紧凑结构和非紧凑结构
    c、线性结构和非线性结构
    d、内部结构和外部结构

47、已知last指向单向简单链表的尾结点,将s所指结点加在表尾,正确的操作是()。
    a、s->next=s,last=s,last->next=null;
    b、last->next=s,s->next=null,last=s;
    c、s->next=last, last->next=null,last=s;
    d、s->next=null, last->next=s, s=last;

48、n个结点的线索二叉树上含有的线索数为( )
    a、n
    b、n-1
    c、n 1
    d、2n

49、引入线索二叉树的目的的是( )。
    a、加快查找结点的前驱或后继的速度
    b、为了能在二叉树中方便地进行插人与删除
    c、为了能方便地找到双亲
    d、使二叉树的遍历结果唯一

50、下列线索二叉树中(用虚线表示线索),符合后序线索树定义的是()
    a、
    b、
    c、
    d、

51、下列关于栈的叙述中,错误的是()
    a、采用非递归方式重写递归程序时必须使用栈
    b、函数调用时,系统要用栈保存必要的信息
    c、只要确定了入栈次序,即可确定出栈次序
    d、栈是一种受限的线性表,允许在其两端进行操作

52、以下数据结构中,属于线性结构的有()。
    a、栈
    b、树
    c、串
    d、数组

53、在下述结论中,正确的是()
    a、只有2个结点的树的度为1
    b、二叉树的度为2
    c、二叉树的左右子树可任意交换
    d、二叉树的度小于等于2

54、设 t 是非空二叉树,若 t 的先序遍历和中序遍历序列相同,则 t 的形态可能是( )
    a、只有一个根结点
    b、没有度为 1 的结点
    c、结点个数大于1,且所有非叶子结点只有左孩子
    d、结点个数大于1,且所有非叶子结点只有右孩子

55、下列关于数据的逻辑结构的叙述中,不正确的有()。
    a、数据的逻辑结构是数据元素间关系的描述
    b、数据的逻辑结构反映了数据在计算机中的存储方式
    c、数据的逻辑结构分为顺序结构和链式结构
    d、数据的逻辑结构分为静态结构和动态结构

56、以下说法错误的是()
    a、任何一棵二叉树中至少有一个结点的度为2
    b、任何一棵二叉树中每个结点的度都小于等于2
    c、任何一棵二叉树的度肯定等于2
    d、任何一棵二叉树的度都小于等于2

57、以下与数据的存储结构无关的术语是()
    a、串
    b、链式表
    c、循环队列
    d、栈

58、二叉树的先序遍历和中序遍历如下: 先序遍历:abcde;中序遍历: bcaed 。以下结论正确的是()。
    a、a是根结点
    b、b和d结点在同一层
    c、d是a的左孩子
    d、d是e的双亲结点

59、顺序表的优点是()
    a、存储密度大
    b、插入、删除运算效率高
    c、可以随机存取
    d、不需要预留空间

60、在数据结构中,若逻辑结构相同,则对应的存储结构也必相同。

61、栈和队列属于非线性结构。

62、顺序存储方法仅适合存储线性结构的数据。

63、链式存储结构通过链指针表示数据元素之间的关系。

64、与链表相比,顺序表的优点是:存储密度大,并且插入删除元素更快。

65、如果知道一个二叉树的前序遍历和中序遍历结果,可以唯一确定一棵树。

66、一棵有n个结点的完全二叉树,其叶结点个数是确定的。

67、若一个栈的进栈序列为{1, 2, 3, 4, 5},则不可能得到{3, 4, 1, 2, 5}这样的出栈序列。

68、将一棵完全二叉树存于数组中(根结点的下标为1)。则下标为23和24的两个结点是兄弟。

69、在用数组表示的循环队列中,front值一定小于等于rear值。

70、某二叉树的后序和中序遍历序列正好一样,则该二叉树中的任何结点一定都无右孩子。

71、某二叉树中,若叶子结点个数为50,则度为2的结点个数一定等于49。

72、若用链表来表示一个线性表,则表中元素的地址一定是连续的。

73、算法可以没有输入,但是必须有输出。

74、对于一个有n个结点、k条边的森林,不能确定它共有几棵树。

75、对于顺序存储的长度为n的线性表,访问结点和插入结点的时间复杂度分别对应为o(1)和o(n)。

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

77、完全二叉树中,若某个结点没有左孩子,则它必是叶子结点。

78、完全二叉树中,度为1的结点最多只有一个,且一定是该结点的左孩子。

79、将一棵树转成二叉树,根结点没有左子树。

80、在具有头结点的链式存储结构中,头指针指向链表中的第一个元素结点。

81、链表是线性表的一种存储形式,它与顺序表的存储有所不同,它对存储地址的要求是地址连续或不连续均可。

82、对于双向链表,在两个结点之间插入一个新结点需修改的指针共4个。

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

期末测试

期末考试

1、下列线索二叉树中(用虚线表示线索),符合中序线索树定义的是()
    a、
    b、
    c、
    d、

2、在决定选取何种存储结构时,一般不考虑()。
    a、结点个数的多少
    b、各结点的值如何
    c、所用编程语言实现这种结构是否方便
    d、对数据有哪些运算

3、在存储数据时,通常不仅要存储各数据元素的值,而且还要存储()。
    a、数据元素之间的关系
    b、数据的处理方法
    c、数据元素的类型
    d、数据的存储方法

4、通常要求同一逻辑结构中的所有数据元素具有相同的特性,这意味着()。
    a、不仅数据元素所包含的数据项的个数要相同,而且对应的数据项的类型要一致
    b、数据元素所包含的数据项的个数要相等
    c、数据元素具有同一特点
    d、每个数据元素值必须相同

5、下面代码段的时间复杂度为()。 { int i=0, s=0; while (i    a、
    b、
    c、
    d、

6、对于长度为n的顺序表(下标范围0..n-1),在第i个位置插入一个元素,平均移动( )个元素。其中,0≤i≤n
    a、n
    b、n/2
    c、(n 1)/2
    d、(n-1)/2

7、对于长度为n的顺序表(下标范围0..n-1),在第i个位置删除一个元素,平均移动( )个元素。其中,0≤i≤n-1
    a、n
    b、n/2
    c、(n 1)/2
    d、(n-1)/2

8、在长度为n的顺序表中,查找第i个位置的数据元素的时间复杂度为()
    a、o(1)
    b、o(n)
    c、
    d、

9、对于顺序存储的长度为n的线性表,插入、删除一个元素的平均时间复杂度分别是()
    a、o(1) o(1)
    b、o(n) o(1)
    c、o(n) o(n)
    d、o(1)o(n)

10、已知head是指向带头结点单链表的首指针,则删除线性表第一个实际结点(首结点)的操作是()
    a、p=head,head=p->next;free(p);
    b、p=head->next;free(p);head=head->next;
    c、p=head->next,head->next=p->next;free(p);
    d、free(head->next);head=head->next;

11、若某线性表最常用的操作是取第i个结点及其前驱,则采用以下哪种存储方式最节省时间( )。
    a、顺序表
    b、循环单链表
    c、双链表
    d、静态链表

12、对于使用带头结点的循环单链表,若头指针为head,判定该表为空的条件是( )。
    a、head->next==null
    b、head!=null
    c、head->next==head
    d、head==null

13、对于使用带头结点的单链表,若头指针为head,判定该表为非空的条件是( )。
    a、head->next==null
    b、head!=null
    c、head->next!=null
    d、head==null

14、已知指针p指向单链表head中的某个结点,且该结点有后继结点,若要删除其后继结点,则需执行()。
    a、q=p->next; p->next=q->next; free(q);
    b、q=p; p->next=q->next; free(q);
    c、q=p->next; p=q->next; free(q);
    d、q=p->next; q->next=p->next; free(q);

15、已知指针p指向在一个单链表中的某个结点,若在该结点之后插入指针s指向的结点,则需执行( )。
    a、s->next=p->next;p->next=s;
    b、p->next=s;s->next=p;
    c、s->next=p->next;s=p;
    d、s->next=p->next;s=p->next;

16、元素a、b、c、d依次进栈,中间允许出栈,则不可能的出栈序列是 ( )。
    a、abcd
    b、adbc
    c、abdc
    d、acdb

17、为解决计算机主机与打印机之间速度不匹配问题,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中读取数据。该缓冲区最适合采用的逻辑结构是()
    a、队列
    b、栈
    c、树
    d、图

18、设栈s和队列q的初始状态都为空,元素a,b,c,d,e,f依次通过栈s,一个元素出栈后即进入队列q,若6个元素出队的序列是bdcfea,则栈的容量至少应该是()
    a、2
    b、3
    c、4
    d、5

19、数组a[m](m等于6)存储一个循环队列,front和rear分别是首尾指针。已知front和rear的当前值分别等于1和4,此时a[3]存放的是队尾元素。当从队列中删除两个元素,再插入两个元素后,front和rear的值分别等于()。
    a、4和1
    b、3和6
    c、3和0
    d、3和1

20、表达式5 (6-7)*8 的后缀表达式是(  )
    a、567-8*
    b、567- 8*
    c、67-8*5
    d、567-8 *

21、若一个栈用数组data[0..n-1]存储,初始栈顶指针top为n-1,则以下元素x进入栈的正确操作是( )。
    a、top ; data[top]=x;
    b、data[top]=x;top ;
    c、data[top]=x;top--;
    d、top--; data[top]=x;

22、顺序循环队列qu的队满条件(front队首指针指向队首元素,rear队尾指针指向队尾元素的后一个位置,采用浪费一个空间的方式进行存储,队列元素最大个数为maxsize)是 ()。
    a、(qu.rear 1)%maxsize==qu.front
    b、(qu.rear 1)%maxsize==qu.front 1
    c、qu.rear==qu.front
    d、(qu.rear 1)%maxsize==(qu.front 1)%maxsize

23、若以单链表存储一个栈,且该栈顶指针为top,则使指针s所指结点进栈的操作是()。
    a、s->next=top->next; top->next=s;
    b、top->next=s;
    c、s->next=top;top=s->next;
    d、s->next=top;top=s;

24、循环队列存储在数组a[0..maxsize-1]中,其头尾指针分别为front和rear,头指针front总是指向队头元素,尾指针rear总是指向队尾元素的下一个位置,则元素x入队时的操作为( )
    a、a[rear]=x;rear=(rear 1)%maxsize;
    b、a[rear]=x;rear=rear 1;
    c、a[rear]=x;rear=(rear 1)%(maxsize 1);
    d、rear=(rear 1)%maxsize; a[rear]=x;

25、设有10×5的数组a,其每个元素占2个字节,按行优先顺序存储,若已知a[3][4]在内存中的地址是1038,则a[5][0]的地址是( )
    a、1025
    b、1050
    c、1085
    d、1048

26、将10×5 的二维数组a按照行优先顺序存储到一维数组b中,则b[21]中存储的二维数组元素是( )。
    a、a[4][1]
    b、a[2][1]
    c、a[4][0]
    d、a[4][2]

27、n*n的三对角矩阵,需要保存的数据元素的个数是( )。
    a、3n
    b、n*(n-1)/2
    c、3n-1
    d、3n-2

28、以下物理结构中,不能够对数据元素进行随机访问的是( )
    a、三元组顺序表
    b、三对角矩阵的压缩存储
    c、数组的顺序存储
    d、对称矩阵的压缩存储

29、若一个度为3树中,度数为1,2,3的结点数分别是2,1,3。叶子数必为()个。
    a、5
    b、4
    c、6
    d、8

30、高度为h(h>1)的完全二叉树至少有()结点。
    a、
    b、
    c、
    d、

31、若已知某二叉树的先序序列为abcde,中序序列为badce,则其后序序列为()
    a、无法确定
    b、bdeca
    c、bedca
    d、ebdca

32、已知二叉排序树的后序序列是12,21,19,67,45,23,那么,它的先序序列是()
    a、23,19,21,12,67,45
    b、23,19,12,21,45,67
    c、21,12,19,23,45,67
    d、23,45,12,67,19,21

33、若二叉排序树中序序列是从小到大的序列,下列说法正确的是()
    a、二叉排序树中,每个结点的关键字都大于等于其左子树中所有结点关键字,都小于其右子树中所有结点关键字
    b、二叉排序树中,每个结点的关键字都小于等于其左子树中所有结点关键字,都大于其右子树中所有结点关键字
    c、二叉排序树中,每个结点的关键字都小于等于其左右孩子关键字
    d、二叉排序树中,每个结点的关键字大于等于其左孩子关键字,都小于其右孩子关键字

34、连通图的极小连通子图称为该图的()。
    a、最小生成树
    b、生成树
    c、回路
    d、最小回路

35、如果从无向图的任一顶点出发进行一次深度优先搜索可访问所有顶点,则该图一定是()
    a、连通图
    b、完全图
    c、有回路的图
    d、一棵树

36、设有两个无向图g=(v,e),g1=(v1,e1),如果g1是g的生成树,则下列说法不正确的是()。
    a、g1是g的无环子图
    b、g1是g的子图
    c、g1是g的连通分量
    d、g1是g的极小连通子图,且v1=v

37、具有6个顶点的无向图至少应有()条边才能确保是一个连通图。
    a、5
    b、6
    c、7
    d、8

38、如果无向图g必须进行两次广度优先搜索才能访问其所有顶点,则下列说法中不正确的是()
    a、g肯定不是完全图
    b、g中一定有回路
    c、g一定不是连通图
    d、g有2个连通分量

39、对如下所示的无向带权图,利用prim(普里姆)算法构造其最小生成树(假定从v0开始),依次得到的树边为()
    a、v0v3 、 v0v2、 v3v1 、 v2v5 、 v5v4
    b、v0v3 、 v3v1 、 v0v2、 v2v5 、 v5v4
    c、v0v3 、 v0v2、 v3v1 、 v5v4 、 v2v5
    d、v0v3 、 v0v2、 v5v4 、 v3v1 、v2v5

40、对于hash函数,h(key)=key,被称为同义词的关键字是( )。
    a、35和41
    b、23和39
    c、15和44
    d、25和51

41、数据结构是一门研究非数值计算的程序设计问题中,数据元素的①  、数据信息在计算机中的②     以及一组相关的运算等的课程。( )
    a、① 逻辑结构 ② 存储结构
    b、① 操作对象  ② 存储结构
    c、① 逻辑结构 ② 关系 
    d、① 逻辑结构 ② 算法

42、在一个无向图中,所有顶点的度数之和等于所有边数的( )倍。
    a、1/2
    b、1
    c、2
    d、4

43、对如下所示的无向带权图,利用prim(普里姆)算法构造其最小生成树(假定从a开始),依次得到的树边为()。
    a、ac 1、 ce 4、 ed 2、cb 5、 bf 3
    b、ac 1、 ed 2、 bf 3、 ce 4、cb 5
    c、ac 1、 ed 2、 bf 3、 ce 4、cb 5
    d、ac 1、 ed 2、 bf 3、cb 5、ce 4

44、n个记录采用冒泡排序,最好情况下,所需关键字的比较次数是( )。
    a、n-1
    b、n*(n-1)
    c、n
    d、nlogn

45、排序时扫描待排序记录序列,顺次比较相邻的两个元素的大小,逆序时就交换位置,这是( )排序方法的基本思想。
    a、冒泡排序
    b、直接插入排序
    c、堆排序
    d、快速排序

46、设有500000个待排序的记录关键字,如果需要用最快的方法选出其中最小的10个记录关键字,则用下列( )方法可以达到此目的。
    a、快速排序
    b、基数排序
    c、堆排序
    d、归并排序

47、用某种排序方法对关键字序列(25,84,21,47,15,27,68,35,20)进行排序时,序列的变化情况如下: 20,15,21,25,47,27,68,35,84 15,20,21,25,35,27,47,68,84 15,20,21,25,27,35,47,68,84 则所采用的排序方法是( )。
    a、冒泡排序
    b、直接插入排序
    c、简单选择排序
    d、快速排序

48、设一组初始记录关键字序列为(45,80,55,30,42,95),则以第一个关键字45为基准而得到的一趟快速排序结果是( )。
    a、30,42,45,55,80,95
    b、30,42,45,55,80,95
    c、42,30,45,55,80,95
    d、42,30,45,95,55,80

49、将关键字(46,79,56,33,40,90)按从小到大排列,则利用堆排序的方法建立的初始堆为( ) 。
    a、79,46,56,33,40,90
    b、90,79,56,46,40,38
    c、90,79,56,33,40,46
    d、90,56,79,40,46,33

50、快速排序在下列( )情况下最易发挥其长处。
    a、被排序的数据元素中的最大值和最小值相差悬殊
    b、被排序的数据元素已基本有序
    c、被排序的数据元素中含有多个相同的关键字
    d、被排序的数据元素完全无序

51、下面( )关键字序列符合堆的定义。
    a、{96, 83, 27, 38, 11, 40}
    b、{12, 34, 6, 54, 23, 46}
    c、{12, 36, 24, 85, 47, 30, 53, 91}
    d、{98, 86, 100, 45, 67, 34, 20}

52、以下是不稳定的排序算法是( )。
    a、冒泡排序
    b、归并排序
    c、直接插入排序
    d、堆排序

53、最好和最坏时间复杂度均为o(nlogn)且稳定的排序方法是( )。
    a、归并排序
    b、基数排序
    c、堆排序
    d、快速排序

54、以下是稳定的排序算法的是( )。
    a、快速排序
    b、希尔排序
    c、冒泡排序
    d、简单选择排序

55、( )其时间复杂度为o(n*n),关键字比较次数与待排序记录的初始排列顺序无关且排序不稳定,则该排序算法是
    a、直接插入排序
    b、简单选择排序
    c、冒泡排序
    d、快速排序

56、希尔排序法、快速排序法、堆排序法和二路归并排序法四种排序法中,要求辅助空间最多的是 ()
    a、希尔排序法
    b、快速排序法
    c、堆排序法
    d、二路归并排序法

57、排序算法的稳定性是指( )。
    a、经过排序后,能使原来关键字值相同的数据保持原有顺序中的绝对位置不变
    b、排序算法的性能和被排序的数据数量关系不大
    c、经过排序后,能使原来关键字值相同的数据保持原有顺序中的相对位置不变
    d、排序算法的性能和被排序的数据数量关系密切

58、假设两个有序表长度分别为n和m,将其归并成一个有序表最少需要( )次关键字之间的比较。
    a、n
    b、min{n,m}
    c、m
    d、max{n,m}

59、假设两个有序表长度分别为n和m,将其归并成一个有序表最多需要( )次关键字之间的比较。
    a、min{n,m}
    b、m n
    c、max{n,m}
    d、n m-1

60、对关键字序列(30,26,18,16,5,66),进行2遍( )排序后得到序列(5,16,18,26,30,66)。
    a、选择
    b、插入
    c、归并
    d、冒泡

61、在下列排序算法中,( )排序算法可能出现如下情况:在最后一趟排序之前,所有元素均不在其最终的位置上。
    a、插入排序
    b、冒泡排序
    c、选择排序
    d、堆

62、设哈希表为t[0..16],哈希函数h(key)=key,采用线性探测开放地址法处理冲突,且t中已有关键字为11、28、47和18这4个数据元素,现插入关键字为24的数据元素,其实际存储的地址是( )。
    a、3
    b、6
    c、9
    d、12

63、对于查找表(13,27,38,49,50 ,65,76,97)采用顺序查找,在等概率情况下查找成功的平均查找长度是( )。
    a、4.5
    b、4
    c、8
    d、9

64、在关键字序列(10,20,30,40,50)中采用折半查找20,依次与( )关键字进行了比较。
    a、30,10,20
    b、30,20
    c、20
    d、40,20

65、对于长度为11的有序表,按折半查找,在等概率情况下查找成功时,其平均查找长度是( )。
    a、1
    b、2
    c、3
    d、4

66、对于长度为11的有序表,按折半查找,在查找失败时,待查找值域表中关键字比较的次数是( )。
    a、2次或3次
    b、3次或4次
    c、4次或5次
    d、1次或2次

67、对于长度为n的关键字序列创建一颗二叉排序树,该树可能的最大高度是( )。
    a、logn
    b、n
    c、n-1
    d、n/2

68、对于关键字序列(30,25,40,35,45),按序列次序创建一颗二叉排序树,则下列说法错误的是()
    a、35是树根
    b、45是40的右孩子
    c、25和40是兄弟
    d、30是25的双亲

69、一组关键字序列为(27,17,9,19,16,43,53,8,63),用哈希函数h(key)=key mod 8和链地址法处理冲突,查找关键字43,与散列表中关键字进行了( )次比较。
    a、3
    b、4
    c、5
    d、6

70、设哈希表下标为0~15,哈希函数为h(key)=key mod 13,其中key为关键字,mod为取余数运算,处理冲突方法为线性探查法,对于关键字序列为(22,18,38,39,48,35,9,64,29),建立哈希表后,关键字9的在哈希表的位置是( )。
    a、9
    b、11
    c、13
    d、15

71、将关键字(68,45,27,54,20,25)按从小到大排列,利用堆排序的方法建立的初始大根堆为( )
    a、68,45,27,54,20,25
    b、68,54,27,45,20,25
    c、68,54,45,27,20,25
    d、68,54,45,27,25,20

72、将关键字(54,27,45,68,20,25)按从小到大排列,采用冒泡排序算法,则第一趟冒泡之后的状态为( )
    a、45,27,54,20,25,68
    b、27,45,54,20,25,68
    c、54,27,45,20,25,68
    d、54,27,45,25,20,68

73、将关键字(45,68,27,54,20,25)按从小到大排列,利用快速排序,以45为枢轴,进行第一次划分之后状态为( )
    a、25, 20, 27, 45, 54, 68
    b、20, 25, 27, 45, 54, 68
    c、20, 68, 27, 45, 54, 25
    d、25, 20, 27, 45, 68, 54

74、对关键字序列(149,138,165,197,176,113,127),采用基数排序的第一趟之后所得结果为( )
    a、(113,127,138,149,165,176,197)
    b、(149,138,165,197,176,113,127)
    c、(113,165,176,127,197,138,149)
    d、(113,165,176,197,127,138,149)

75、假设一组待排序的关键字序列为(24,62,36,19),要求从小到大进行排序,( )是二路归并排序的过程。
    a、(24,62,36,19) (24,36,62,19) (19,24,36,62)
    b、(24,19,36,62) (24,19,36,62) (19,24,36,62)
    c、(24,62,19,36) (19,24,36,62)
    d、(62,24,36,19) (19,24,36,62)

76、在第一趟排序之后,不能确保将数据表中某一个元素放在其最终位置上的排序算法是( )
    a、冒泡排序
    b、快速排序
    c、归并排序
    d、选择排序

77、设哈希表下标为0~15,哈希函数为h(key)=key mod 13,其中key为关键字,mod为取余数运算,处理冲突方法为线性探查法,对于关键字序列为(22,18,38,39,48,35,9,64,29),建立哈希表后,关键字9的在哈希表的位置是( )。
    a、9
    b、11
    c、13
    d、15

78、假设哈希函数h(k)=k mod 29,那么( )为7的同义词。
    a、16
    b、26
    c、36
    d、46

79、若根据查找表建立长度为m的哈希表,假定对一个元素第一次计算的哈希地址为d,若该位置产生冲突,采用线性探测法处理冲突,则下一次的哈希地址为( )。
    a、d 1
    b、d
    c、(d 1) % m
    d、(d 1) / m

80、以下说法不正确的是()
    a、数据项是数据的基本单位
    b、数据元素是数据的最小单位
    c、一些表面上很不相同的数据可以有相同的逻辑结构
    d、逻辑结构相同的数据存储结构一定相同

81、关于线性表的链式存储,以下说法不正确的是( )
    a、插入、删除运算方便
    b、可方便地进行随机存取
    c、存储密度大
    d、不需要预留空间,地址连续不连续都可以

82、设进栈序列是1,2,3,…,n,输出序列为p1,p2,p3,…,pn。若p1=3,则p2为()。
    a、可能是2
    b、一定是2
    c、不可能是1
    d、可能是1

83、设进栈序列是1,2,3,…,n,输出序列为p1,p2,p3,…,pn。若p3=1,则p1()
    a、可能是3
    b、可能是2
    c、必定是3
    d、一定不是3

84、某稀疏矩阵a采用三元组顺序表作为存储结构,对于矩阵元素的赋值运算a[i][j]=x,可能的操作是()
    a、修改某个三元组的行号或列号
    b、修改某个三元组的元素值
    c、删除一个三元组
    d、插入一个新的三元组

85、函数功能: 在带头结点单链表中删除一个值为x的结点,函数返回值为头指针。请选择正确的选项 链式表定义如下: typedef int datatype; typedef struct link_node{ datatype info; struct link_node *next; }node; 函数实现如下: node *dele(node *head,datatype x) { node *pre= (1) ,*q; q=head->next; while( (2) ) { pre=q; q=q->next; } if(q) { pre->next=q->next; //删除q free(p); } return head; }
    a、(1) head
    b、(1) null
    c、(2) q && q->info!=x
    d、(2) q->info!=x && q

86、假设二叉树采用链式方式存储,t为其根结点,请选择正确的选项将函数int depth(bintree t) 补充完整,该函数功能为求树t的高度。 二叉链表定义如下: typedef struct node{ datatype data; struct node *lchild,*rchild; }bintnode typedef bintnode *bintree; 函数定义如下: int depth(bintree t) { int height,lefttreeheight,righttreeheight; if (t==null) ( 1 ) ; else { (2) ; righttreeheight =depth(t->rchild); if ( (3) ) height=lefttreeheight 1; else height= righttreeheight 1; } return height; }
    a、(1) return 0;
    b、(1) return 1;
    c、(3) lefttreeheight >= righttreeheight
    d、(3) lefttreeheight <= righttreeheight
    e、(2) lefttreeheight =depth(t->lchild)
    f、(2) depth(t->lchild)

87、函数void preorder(bintree t)实现了二叉树的非递归先序遍历,该算法借助栈进行实现,请选择合适的选项填入相应的空缺处,使算法完整。 用c语言描述二叉树结点的结构如下: typedef char datatype; /*结点属性值的类型*/ typedef struct node{ /*二叉树结点的类型*/ datatype data; struct node *lchild, *rchild; } bintnode; typedef bintnode *bintree; void preorder (bintree t) { bintree st[100]; //顺序栈 int top=-1; while ( t || top!=-1) /*当前处理的子树不为空或栈不为空则循环*/ { if(t) { printf("%c ",t->data); ___(1)_______ //入栈 ___(2)_______ //继续往左子树遍历 } else { ___(3)_______ //取栈顶元,并出栈 t=t->rchild; //继续往右子树遍历 } } }
    a、(1) top ;st[top]=t;
    b、(1) st[top]=t;top ;
    c、(2) t=t->lchild;
    d、(2) t->lchild=t->lchild->lchild;
    e、(3)t=st[top];top--;
    f、(3)top--;t=st[top];

88、函数slnklist delx(linklist head, datatype x),该算法实现删除带头结点单链表head中第一个值为x 的结点,请选择合适的选项填入空缺处,使算法完整。 用c语言描述单链表结点的结构如下: typedef int datatype; typedef struct link_node{ datatype info; struct link_node *next; }node; typedef node *linklist; del函数定义如下: linklist delx(linklist head,datatype x) { linklist pre,p; //pre指向待删除结点的前驱 pre=head; (1) ; while (p &&p->info!=x) //找到第一个info为x的结点 { (2) ; } if (p) { (3) ; } return head; }
    a、(1) p=head->next;
    b、(1) p=head;
    c、(2) pre=p; p=p->next;
    d、(2) p=p->next;pre=p;
    e、(3)pre->next=p->next;free(p);
    f、(3)p=p->next;pre->next=p;free(p);

89、二分查找的递归实现,请选择正确的选项将函数补充完整。顺序表定义如下: typedef int datatype; /*假设数据类型为整型*/ typedef struct { datatype data[100]; /*此处假设数据元素只包含一个整型的关键字域*/ int len; /*线性表长度*/ } slist; /*预定义的顺序表类型*/ 函数定义如下: int binsearch(slist l,datatype key,int low,int high) { int mid,k; if ( (1) ) return -1; /*检索不成功的出口条件*/ else { mid=(low high)/2; /*二分*/ if ( (2) ) return mid; /*检索成功返回*/ if (l.data[mid]>key) return (3) ;/*递归地在前半部分检索*/ else return binsearch(l,key,mid 1,high); /*递归地在后半部分检索*/ } }
    a、(1) low>high
    b、(1) low>=high
    c、(2) l.data[mid]==key
    d、(2) data[mid]==key
    e、(3) binsearch(l,key,low,mid-1)
    f、(3) binsearch(l,key,low,mid)

90、以下排序算法中,关键字的比较次数与元素初始序列无关的是( )。
    a、简单选择排序
    b、直接插入排序
    c、冒泡排序
    d、堆排序

91、计算机算法就是计算机程序。

92、顺序存储方式的优点是存储密度大,数据存储在连续的内存空间中,但是插入、删除运算效率低。

93、链表是线性表的一种存储形式,它与顺序表的存储有所不同,它对存储地址的要求是地址必须连续。

94、取链式表的第i个元素的时间与i值的大小无关。

95、静态链表中指针表示的是下一元素在数组中的下标。

96、栈和队列的不同点是栈只能在一端进行插入删除操作,而队列在不同端进行插入删除操作。

97、顺序循环队列解决了顺序队列的假溢出问题。

98、对特殊矩阵采用压缩存储的目的主要是去掉矩阵中的多余元素。

99、使用三元组来保存稀疏矩阵中的非零元素,三元组包括非零元素的行号,列号以及元素值。

100、两个字符串相等的充分必要条件是两个字符串中对应位置上的字符相等。

101、所有的排序算法的比较次数与初始序列无关。

102、对顺序表中的n个记录进行直接插入排序,在初始关键字序列为逆序的情况下,需要关键字比较的次数最少。

103、如果冒泡排序的某趟过程中没有出现数据交换情况,那么说明关键字序列已经有序。

104、如果关键字序列是堆,则关键字序列对应的二叉树是一棵二叉排序树。

105、在用堆排序算法排序时,如果要进行增序排序,则需要采用“大根堆”。

106、排序要求数据一定要以顺序方式存储。

107、因为直接插入排序是稳定的,而shell 排序是调用若干趟直接插入排序,所以也是稳定的。

108、二路归并排序的核心操作是把两个有序序列合并为一个有序序列。

109、如果关键字序列采用单链表存储,那么基数排序过程可以避免大量数据移动。

110、基数排序是一种基于最高位优先(msd)的多关键字排序法。

111、基于“比较”运算的排序算法,其时间复杂度的下界为o(n㏒n)。

112、快速排序方法的每一趟都能将一个元素把它放到最终的位置上。

113、因为堆排序的算法时间复杂度为,冒泡排序的算法复杂度为,所以堆排序一定比冒泡排序的速度快。

114、在hash表中进行查找运算,根据hash函数就能确定要查找的元素位置,不需要进行关键字的比较。

下一篇 >>

相关文章

  • 2022-11-04 23:47
  • 2022-11-04 23:29
  • 2022-11-04 23:04
  • 2022-11-04 22:48
  • 2022-11-04 21:44

备案号: 买球平台网址的版权所有 买球平台网址 copyright © 2012-2022 青果答案 all rights reserved. sitemap