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

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

    6569 人参与  2022-11-04 23:45:46    点这评论
    第一章 引论

    第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(n^2),表明该算法的( )。
        a、执行时间与n^2成正比
        b、问题规模是n^2
        c、执行时间等于n^2
        d、问题规模与n^2成正比

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

    8、算法指( )。
        a、计算方法
        b、排序方法
        c、解决问题的步骤序列
        d、调度方法

    9、下面的程序段时间复杂度为( )。 for(i=1;i    a、o(2n)
        b、o(n)
        c、o(n^2)
        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(n^2)
        d、o(logn)

    12、下面程序段的时间复杂度为( )。 for(i=0;i    a、o(n*m)
        b、o(n^2)
        c、o(m^2)
        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(n^2)

    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
    第二章 线性表

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

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

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

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

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

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

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

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

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

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

    单元作业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    a、o(2n)
        b、o(n)
        c、o(n^2)
        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讲 串的基本操作(总时长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'相等。

    单元作业4

    1、在顺序串中,参数ch,ch1和ch2均是字符型,编写下列算法。 (1)将串r中所有其值为ch1的字符换成ch2的字符。 (2)将串r中删除其值等于ch的所有字符。 (3)从串r1中第index个字符起求出首次与串r2相同的子串的起始位置。

    2、编写算法,实现顺序串的基本操作strreplace(s,t,v)。

    第五章 多维数组和广义表

    第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、稀疏矩阵中非零元素的个数远小于矩阵中元素的总数。

    单元作业5

    1、鞍点是指矩阵中的某元素a[i][j]是第i行中值最小的元素,同时又是第j列中值最大的元素。试设计一个算法求矩阵a中的所有鞍点。

    2、设计一个算法,实现将一维数组a(下标从1开始)中的元素循环右移k位,要求只用一个元素大小的辅助空间,并给出算法的时间复杂度。

    第六章 树

    第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算法需要对图中每条边至少检查一次。

    在线练习7

    1、一个具有n个顶点的无向图最多有( )边。
        a、n(n-1)/2
        b、n(n-1)
        c、n
        d、2n

    2、一个具有n个顶点的有向图中,要连通全部顶点至少需要( )条弧。
        a、n
        b、n-1
        c、n 1
        d、2n

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

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

    5、对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则占用的存储空间为( )。
        a、n 2e
        b、n
        c、2e
        d、n e

    6、如果含有n个顶点的图形成一个环,则它有( )棵生成树。
        a、n
        b、n-1
        c、n 1
        d、不确定

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

    8、判断一个有向图是否存在回路,可以用( )。
        a、深度优先遍历算法
        b、求关键路径的方法
        c、dijkstra方法
        d、广度优先遍历算法

    9、设图g有n个顶点和e条边,采用邻接表存储,则拓扑排序算法的时间复杂度为( )。
        a、o(n e)
        b、o(n)
        c、o(e)
        d、o(n*e)

    10、下面不正确的说法是( )。
        a、任何一个关键活动提前完成,将使整个工程提前完成
        b、关键活动不按期完成就会影响整个工程的完成时间
        c、所有关键活动都提前完成,则整个工程提前完成
        d、某些关键活动若提前完成,将使整个工程提前完成

    11、关键路径是事件结点网络中( )。
        a、从源点到汇点的最长路径
        b、最长回路
        c、从源点到汇点的最短路径
        d、最短回路

    12、图g是一个非连通无向图,共有28条边,则该图至少有( )个顶点。
        a、9
        b、8
        c、10
        d、11

    13、已知一个图的邻接矩阵表示,删除所有从第i个顶点出发的弧方法是( )。
        a、将矩阵第i行上的元素全部置0
        b、将矩阵第i列上的元素全部置0
        c、将矩阵第i行删除,后序行上移
        d、将矩阵第i列删除,后序列左移

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

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

    16、在图的表示法中,表示形式唯一的是( )。
        a、邻接矩阵表示法
        b、邻接表表示法
        c、逆邻接表表示法
        d、邻接表和逆邻接表表示法

    17、连通分量是( )的极大连通子图。
        a、无向图
        b、树
        c、图
        d、有向图

    18、最小生成树的构造可使用( )算法。
        a、prim算法
        b、卡尔算法
        c、哈夫曼算法
        d、迪杰斯特拉算法

    19、在一个具有n个顶点e条边的图中,所有顶点的度数之和等于( )。
        a、2n
        b、n
        c、e
        d、2e

    20、下面关于图的存储结构的叙述中正确的是( )。
        a、用邻接矩阵存储图,占用空间大小只与图中顶点数有关,而与边数无关
        b、用邻接矩阵存储图,占用空间大小只与图中边数有关,而与顶点数无关
        c、用邻接表存储图,占用空间大小只与图中顶点数有关,而与边数无关
        d、邻接表存储图,占用空间大小只与图中边数有关,而与顶点数无关

    21、有8个结点的有向完全图有( )条边。
        a、56
        b、14
        c、28
        d、112

    22、下图中,度为3的结点是( )。
        a、v2
        b、v1
        c、v3
        d、v4

    23、下图是( )。
        a、连通图
        b、强连通图
        c、生成树
        d、无环图

    24、如下图所示,从顶点a出发,按深度优先进行遍历,则可能得到的一种顶点序列为( )。
        a、a,e,d,f,c,b
        b、a,b,e,c,d,f
        c、a,c,f,e,b,d
        d、a,e,b,c,f,d

    25、如下图所示,从顶点a出发,按广度优先进行遍历,则可能得到的一种顶点序列为( )。
        a、a,b,e,c,d,f
        b、a,c,f,e,b,d
        c、a,e,b,c,f,d
        d、a,e,d,f,c,b

    26、图可以没有边,但不能没有顶点。

    27、关键路径上的活动都是关键活动,它们是否按时完成会影响工期。

    28、求稀疏图的最小生成树,用克鲁斯卡尔算法来求解较好。

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

    30、任何一个有向图都一定存在拓扑序列。

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

    32、若一个无向图以顶点v1为起点进行深度优先遍历,所得的遍历序列唯一,则可以唯一确定该图。

    33、若从一个无向图中任一顶点出发,进行一次深度优先遍历,就可以访问图中所有的顶点,则该图一定是连通的。

    34、存储无向图的邻接矩阵是对称的,因此只要存储邻接矩阵的上三角(或下三角)部分就可以了。

    35、有向图不能进行广度优先遍历。

    单元作业7

    1、已知图以邻接矩阵作为存储结构,编写算法判断两个指定顶点之间是否存在路径。

    2、对于题图所示的有向网, (1)给出该图对应的邻接矩阵、邻接表和逆邻接表; (2)判断该图是否为强连通图,并给出其强连通分量; (3)给出每个顶点的度、入度和出度; (4)给出从顶点v1开始的深度优先搜索遍历序列和广度优先搜索遍历序列。

    3、如题图所示的有向网,利用dijkstra算法求顶点v0到其他各顶点之间的最短路径以及最短路径长度。

    第八章 查找

    第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、处理冲突实际就是为了产生冲突的地址寻找下一个散列地址。

    在线练习8

    1、在关键字随机分布的情况下,用二叉排序树的方法进行查找,其查找长度与( )数量级相当。
        a、折半查找
        b、顺序查找
        c、分块查找
        d、哈希查找

    2、关于折半查找,以下说法正确的是( )。
        a、待查找表必须有序,且只能以顺序方式存储
        b、待查找表必须有序,可以顺序方式存储,也可以链表方式存储
        c、待查找表必须有序且表中数据必须是整型
        d、待查找表必须有序,而且必须从小到大排列

    3、具有12个关键字的有序表,折半查找的平均查找长度( )。
        a、37/12
        b、25
        c、25/12
        d、10/12

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

    5、折半查找适合于存储结构为( )的线性表。
        a、顺序
        b、散列存储
        c、压缩存储
        d、索引存储

    6、如果要求用线性表既能较快地查找,又能适应动态变化的要求,则可采用( )查找方法。
        a、分块查找
        b、顺序查找
        c、折半查找
        d、基于属性

    7、以下适合用分块查的数据集是( )。
        a、数据分成若干块,块内数据不必有序,但块间必须有序
        b、数据分成若干块,每块(除最后一块外)中数据个数需相同
        c、数据分成若干块,块内数据必须有序,块间不必有序
        d、数据分成大小相等的若干块,块内数据有序

    8、已知一如下10个记录的表,其关键字序列为(2,15,19,25,30,34,44,55,58,80),用折半查找法查找关键字为55的记录,比较次数是( )。
        a、2次
        b、1次
        c、3次
        d、4次

    9、关于哈希查找,以下说法不正确的是( )。
        a、哈希查找的asl一定可以达到0
        b、装填因子越小,越容易产生冲突
        c、哈希查找有两个关键问题:哈希函数的选择和处理冲突的方法
        d、链地址法和线性探测再散列都是解决冲突的方法

    10、由同一关键字集合构造的各棵二叉排序树( )。
        a、形态和平均查找长度都不一定相同
        b、形态和平均查找长度都相同
        c、形态相同,但平均查找长度不一定相同
        d、形态不一定相同,但平均查找长度相同

    11、如果按关键码值递增的顺序依次将99个关键码值插入到二叉排序树中,则对这样的二叉排序树检索时,在等概率情况下查找成功时的平均查找长度asl为( )。
        a、50
        b、48
        c、45
        d、47

    12、对二叉排序树进行( )遍历,可以得到各结点键值的非递减序列。
        a、中序
        b、层次
        c、后序
        d、先序

    13、在有n个元素的顺序表中顺序查找,则等概率情况下查找成功的平均查找长度为( )。
        a、(n 1)/2
        b、n/2
        c、n 1
        d、n(n 1)/2

    14、对线性表进行折半查找时,要求线性表( )。
        a、关键字有序并按顺序方式存储
        b、有序
        c、顺序存储
        d、没有正确答案

    15、顺序查找法适合于存储结构为( )的线性表。
        a、顺序存储或链接存储
        b、散列存储
        c、压缩存储
        d、索引存储

    16、一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值为82的结点时,( )次比较后查找成功。
        a、4
        b、2
        c、3
        d、5

    17、下列( )不是利用比较进行查找的方法。
        a、散列查找
        b、平衡二叉树
        c、有序表的查找
        d、二叉排序树的查找

    18、设哈希表长m=14,哈希函数h(key)=key%11。表中已有4个结点: addr(15)=4 addr(38)=5 addr(61)=6 addr(84)=7 其余地址为空。如用二次探测再散列处理冲突,关键字为49的结点的地址是( )。
        a、9
        b、8
        c、3
        d、5

    19、冲突指的是( )。
        a、不同关键字记录对应相同的存储地址
        b、两个元素具有相同序号
        c、两个元素的键值不同
        d、两个元素的键值相同

    20、对包含n个元素的散列表进行查找,其平均查找长度( )。
        a、不直接依赖于n
        b、o(n^2)
        c、o(log2n)
        d、o(n)

    21、衡量查找算法效率的主要标准是( )。
        a、平均查找长度
        b、元素个数
        c、所需的存储量
        d、算法难易程度

    22、在查找过程中,不做增加、删除或修改的查找称为( )。
        a、静态查找
        b、内查找
        c、动态查找
        d、外查找

    23、hash表的平均查找长度与处理冲突的方法无关。

    24、不同关键字序列,构造的二叉排序树的平均查找长度都相同。

    25、有n个元素存放在一维数组a[1...n]中,在进行顺序查找时,这n个数的不同排列,其平均查找长度不同。

    26、在二叉树排序树中插入一个新结点,总是插入到叶结点下面。

    27、同样的数据集合,二叉排序树的查找性能与关键字的输入序列有关系。

    28、二分查找法要求待查表的关键字值必须有序。

    29、哈希表是一种将关键字转换为存储地址的存储方法。

    30、在二叉排序树上删除一个结点时,不必移动其它结点,只要将该结点的父结点的相应的指针域置空即可。

    31、在有序的顺序表和有序的链表上,均可以采用二分查找来提高查找速度。

    单元作业8

    1、已知一个有7个数据元素的有序顺序表,其关键字为{3,18,25,37,69,87,99}。给出用折半查找方法查找关键字值18的查找过程。

    2、已知关键字序列为{53,17,19,61,98,75,79,63,46,40},给出利用这些关键字构造的二叉排序树。

    3、已知一组关键字序列为{5,88,12,56,71,28,33,43,93,17},哈希表长为13,哈希函数为h(key)=key,请用线性探测再散列、二次线性探测再散列以及链地址法解决冲突构造这组关键字的哈希表,并计算查找成功时的平均查找长度。

    第九章 排序

    第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、基数排序常用来进行多关键字的排序。

    在线练习9

    1、有一组数据(15,9,7,8,20,-1,7,4),用堆排序的筛选方法建立的初始小根堆为( )。
        a、-1,4,7,8,20,15,7,9
        b、-1,4,8,9,20,7,15,7
        c、-1,7,15,7,4,8,20,9
        d、没有正确答案

    2、一组记录的关键字为(46,79,56,38,40,84),则利用快速排序的方法,以第一个记录为基准得到的一次划分结果为( )。
        a、(40, 38, 46, 56, 79, 84)
        b、(38, 40, 46, 56, 79, 84)
        c、(40, 38, 46, 79, 56, 84)
        d、(40, 38, 46, 84, 56, 79)

    3、对下列整数序列(179,208,93,306,55,859,984,9,271,33)使用基数排序,一趟分配收集之后的结果是( )。
        a、{271,93,33,984,55,306,208,179,859,9}
        b、{93,55,9,33,179,208,271,306,859,984}
        c、{208,306,9,33,55,859,179,271,984,93}
        d、{9,33,55,93,179,208,271,306,859,984}

    4、对序列{15,9,7,8,20,-1,4}进行排序,进行一趟后数据的排列变为{9,15,7,8,20,-1,4},则采用的排序方法是( )。
        a、直接插入排序
        b、选择排序
        c、堆排序
        d、希尔排序

    5、评价排序算法好坏的标准主要是( )。
        a、执行时间和所需的辅助空间
        b、执行时间
        c、辅助空间
        d、算法本身的复杂度

    6、对n个不同的待排对象进行冒泡(递增)排序,在下列( )情况比较的次数最多。
        a、从大到小排列好的
        b、从小到大排列好的
        c、元素无序
        d、元素基本有序

    7、如果只想得到1000个元素组成的序列中第5个最小元素之前的序列,用( )方法最快。
        a、堆排序
        b、冒泡排序
        c、快速排序
        d、shell排序

    8、用直接插入排序方法对下面四个序列进行排序(由小到大),元素比较次数最少的是( )。
        a、21,32,46,40,80,69,90,94
        b、94,32,40,90,80,46,21,69
        c、32,40,21,46,69,94,90,80
        d、90,69,80,46,21,32,94,40

    9、在文件“局部有序”或文件长度较小的情况下,最佳内部排序的方法是( )。
        a、直接插入排序
        b、冒泡排序
        c、简单选择排序
        d、快速排序

    10、在下列排序算法中,( )算法的效率与待排数据的原始状态无关。
        a、基数排序
        b、冒泡排序
        c、插入排序
        d、快速排序

    11、有些排序算法在每趟排序过程中,都会有一个元素被放置在其最终的位置上,下列算法不会出现此情况的是( )。
        a、希尔排序
        b、堆排序
        c、冒泡排序
        d、快速排序

    12、简单选择排序和堆排序性能都受初始序列顺序的影响。

    13、快速排序算法在每一趟排序中都能找到一个元素放在其最终位置上。

    14、堆排序所需的时间与待排序的记录个数无关。

    15、采用希尔方法排序时,若关键字的排列杂乱无序,则效率最高。

    下一篇 >>

    相关文章

    • 2022-11-04 23:47
    • 2022-11-04 23:32
    • 2022-11-04 22:49
    • 2022-11-04 22:30
    • 2022-11-04 21:49

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