【MOOC】《数据结构》(东北大学)中国大学慕课答案

【MOOC】《数据结构》(东北大学)中国大学慕课答案

有些题目顺序不一致，下载后按键盘ctrl+F进行搜索第一章绪论单元测试一1.单选题：具有相同性质的数据元素的集合称为____________，它是数据的一个子集。

选项：

A、记录

B、数据对象

C、数组

D、数据结构

答案：【数据对象】2.单选题：利用数据元素在计算机存储器的相对位置来表示数据元素之间的逻辑关系，称之为___________存储结构。

选项：

A、物理

B、逻辑

C、顺序

D、链式

答案：【顺序】3.多选题：算法具有5个重要特性，除输入和输出外还包括:_________，_________，_________。

选项：

A、有穷性

B、确定性

C、可读性

D、可行性

答案：【有穷性;确定性;可行性】4.多选题：算法的设计要求包括达到以下目标：正确性、_________、_________和效率与低存储量需求。

选项：

A、反编译性

B、可读性

C、健壮性

D、操作性

答案：【可读性;健壮性】5.单选题：数据的物理结构是指数据结构在计算机中的表示，也称为映像。

选项：

A、正确

B、错误

答案：【正确】6.单选题：非线性结构指的是图和网。

选项：

A、正确

B、错误

答案：【错误】7.数据的基本单位是__________。

答案：【数据元素】8.计算机中具有两种不同的存储结构：顺序存储结构和___________存储结构。

答案：【链式】9.数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的___________和操作的学科。

答案：【关系】单元作业一1.分析下面代码段中各行的执行次数，用大O表示算法的时间复杂度。说明：方次可用符号^表示，如100的3次方表示为100^3。y=0;for(i=1;i<=n;i++)for(j=1;j<=n;j++)y++;

算法时间复杂度为O(n^2)，正确得10分，否则得0分。参考：y=0;//1次for(i=1;i<=n;i++)//n+1次for(j=1;j<=n;j++)//n(n+1)次y++;//n^2全部代码的执行次数：1+(n+1)+n(n+1)+n^2=2n^2+2n+2因此，时间复杂度T(n)=O(n^2)第二章线性表单元测验二1.单选题：在一个线性表含有10个数据元素，如果在第i个位置前插入新的数据元素，那么i的取值错误的是_________。

选项：

A、1

B、10

C、11

D、12

答案：【12】2.单选题：如果在n个结点的单链表中删除已知结点s，那么需要_________。

选项：

A、找到s的直接后继结点

B、找到s的直接前驱结点

C、移动s后的所有结点

D、释放s后的所有结点

答案：【找到s的直接前驱结点】3.单选题：判定带头结点的单链表head为空的条件是_________。

选项：

A、head->next==NULL

B、head==NULL

C、head->next==head

D、head!=NULL

答案：【head->next==NULL】4.单选题：在线性结构中，所有的结点仅有一个前驱结点和一个后继结点。

选项：

A、正确

B、错误

答案：【错误】5.单选题：线性表的顺序存储结构是一种随机存取结构，即访问任一数据元素的时间相同。

选项：

A、正确

B、错误

答案：【正确】6.在链表的操作中，生成和释放结点的标准函数是malloc和_______。

答案：【free】7.线性表采用链式存储时，每个结点包含两个域，存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为_______域。

答案：【指针】8.在长度为n的顺序存储的线性表中，查找一个数据元素的时间复杂度为O(__)。

答案：【n】9.一个长度为1000的线性表，采用顺序存储，如果删除第900个元素，需要向前移动_______个元素。

答案：【100】10.一个长度为1000的线性表，采用顺序存储，如果在第900个元素之前插入一个元素，需要向后移动_______个元素。

答案：【101】单元作业二1.设指针p指向单链表中的某个结点，将要删除该结点的直接后继结点，而直接后继结点有可能不存在。所有语句如下，需要重新排列才能完成上述功能。1.q=p->next;2.free(q);3.if(p->next==NULL)returnERROR;4.returnOK;5.p->next=q->next;正确的语句顺序应为_________。A.15243B.31524C.31254D.35124

答案为B得10分，否则0分。2.设存在一个带头结点的单循环链表L，每个结点包含三个域，它们分别是prior、data和next。其中data为数据域，prior是指针域，其值为空指针；next是指针域，指向直接后继结点。下面的代码将此单链表转化为双向循环链表。#defineOK1#defineERROR0typedefintElemType;typedefintStatus;typedefstructLNode{structLNode*prior;ElemTypedata;structLNode*next;}DuLNode,*DuLinkList;StatusCreateDuList_prior(DuLinkList&L){//Makethepriorpointtotheprecursornode.DuLinkListp,q;1;do{q=p->next;2;p=q;}while(p!=L);returnOK;}请填写空格1和2处的代码，实现上述功能。

参考答案：1.p=L2.q->prior=p评分标准：每个空格5分，代码正确得分，错误不得分。第三章栈与队列单元测试三1.单选题：设循环队列采用一维数组A[0..20]存储，队头指针front=15，元素个数size=5，在插入两个新元素后，队尾的位置是______。

选项：

A、0

B、1

C、2

D、22

答案：【1】2.单选题：某链栈的栈顶指针为top，若向该栈中插入一个p所指结点，则执行______。

选项：

A、p->next=top;top=top->next;

B、top->next=p;

C、p->next=top->next;top->next=p;

D、p->next=top;top=p;

答案：【p->next=top;top=p;】3.多选题：一个队列的入列序列是a、b、c、d、e，则队列的输出序列不可能是______。

选项：

A、a、b、c、d、e

B、a、c、b、d、e

C、a、b、d、c、e

D、e、d、c、b、a

答案：【a、c、b、d、e;a、b、d、c、e;e、d、c、b、a】4.多选题：一个栈的入栈序列是a、b、c、d、e，则栈的可能输出的序列是______。

选项：

A、a、b、c、d、e

B、d、c、e、a、b

C、d、e、c、b、a

D、e、d、c、b、a

答案：【a、b、c、d、e;d、e、c、b、a;e、d、c、b、a】5.单选题：循环队列解决了一般顺序存储队列中出现的“假上溢”问题。

选项：

A、正确

B、错误

答案：【正确】6.单选题：采用顺序存储结构的栈称为链栈。

选项：

A、正确

B、错误

答案：【错误】7.单循环链表表示的队列中保存了n个数据元素，若只设头指针，则入队操作的时间复杂度是O(__）。

答案：【n】8.单循环链表表示的队列中保存了n个数据元素，若只设尾指针，则出队操作的时间复杂度是O(___）。

答案：【1】[vk-content]9.在顺序栈中入栈和出栈的时间复杂度都是O(___）。

答案：【1】单元作业三1.设某个循环队列的头指针是front，尾指针是rear，循环队列的空间是M，请为下列1~5的情况选择合适的语句。1.队空的条件：。2.队满的条件：。3.队长的计算：。4.入队时修改指针：。5.出队时修改指针：。可供选择的语句：A.rear=(rear+1)%MB.(rear-front+M)%MC.(rear-front+1)%MD.front==rearE.front=(front+1)%MF.front==(rear+1)%M

参考答案：1.D2.F3.B4.A5.E评分标准：每个空2分，错误不得分。2.顺序栈声明如下，编写一个操作（函数），返回当前允许添加到栈中数据元素的最大个数。typedefintSElemType;typedefstructsqstack{SElemType*base;SElemType*top;intstacksize;}SqStack;

函数返回值为整型，即int或SElemType，得2分；参数为引用型，即形参前有&符号，得2分；num计算正确，即有S.stacksize-(S.top-S.base)算式，得4分；具有返回语句return2分。如果计算与返回为一条语句，正确则得6分。intgetNumOfRemain(SqStack&S){intnum=S.stacksize-(S.top-S.base);returnnum;}第四章串单元测试四1.单选题：设S="tea"，则其非空子串的数目为______。

选项：

A、5

B、6

C、7

D、8

答案：【6】2.单选题：设S="Chinesedreammydream"，T="dream"，则index(S,T,3)的值为______。

选项：

A、0

B、9

C、18

D、9和18

答案：【9】3.单选题：设字符串str1="Datastructures"，其中两个单词之间存在一个空格符，当取子串操SubString(sub1,str1,6,6)执行后，sub1=_______。

选项：

A、"Datas"

B、"Datast"

C、"struct"

D、"tructu"

答案：【"struct"】4.单选题：在串的存储方式中，_______属于链式存储。

选项：

A、定长顺序存储

B、堆分配存储

C、块链存储

D、以上3种全部

答案：【块链存储】5.多选题：下面关于字符串的叙述，不正确的有_________。

选项：

A、字符串是不少于一个字符的序列。

B、字符串是由字母和数字组成的序列。

C、字符串是由零个或多个字符组成的有限序列。

D、字符串是任意个字母组成的序列。

答案：【字符串是不少于一个字符的序列。;字符串是由字母和数字组成的序列。;字符串是任意个字母组成的序列。】6.多选题：以下____________操作属于串类型的最小操作子集。

选项：

A、串赋值StrAssign

B、串定位Index

C、求串长StrLength

D、串复制StrCopy

答案：【串赋值StrAssign;求串长StrLength】7.单选题：串的堆分配存储是一种顺序存储结构。

选项：

A、正确

B、错误

答案：【正确】8.单选题：在空串里面仅包含空格符。

选项：

A、正确

B、错误

答案：【错误】9.设字符串str=""，str的长度为______。

答案：【0/零】单元作业四1.回文是一个顺读和倒读都相同的字符串，如英文单词madam，noon等。设字符串采用堆分配存储，附件中的函数Palindrome用于判断字符串是否为回文。要求：在程序空白处补全代码（标记为1、2）。

参考答案：1.j--或--j2.TRUE评分标准：1、2处正确，各得5分。其他情况不得分。第五章数组与广义表单元测试五1.单选题：对广义表取表尾操作，表尾一定是___________。

选项：

A、原子

B、列表

C、原子或列表

D、十字链表

答案：【列表】2.单选题：广义表GL=(a,(b,c,d),(e,f))的长度为____________。

选项：

A、2

B、3

C、5

D、6

答案：【3】3.多选题：关于一个非空广义表的表尾，以下说法不正确的是____________。

选项：

A、只能是原子

B、只能是子表

C、原子或子表

D、既非原子也非子表

答案：【只能是原子;原子或子表;既非原子也非子表】4.多选题：在计算机中，稀疏矩阵的存储表示和实现包括____________。

选项：

A、三元组顺序表

B、行或列为主序

C、行逻辑链接的顺序表

D、十字链表

答案：【三元组顺序表;行逻辑链接的顺序表;十字链表】5.单选题：非零元素可用三元组（行下标，列下标，元素值）表示，利用它能够恢复一个稀疏矩阵。

选项：

A、正确

B、错误

答案：【错误】6.单选题：若广义表中的每个数据元素都是原子，则广义表就是线性表。

选项：

A、正确

B、错误

答案：【正确】7.单选题：在数组定义后，可以对数组的维数和维界继续更改。

选项：

A、正确

B、错误

答案：【错误】8.已知广义表GL=(a，(b，c，d，e)，f，g)，下列运算head(head(tail(GL)))的结果是__________。

答案：【b】9.一个100*100的对称矩阵，采用压缩存储，所需保存的数据量大小是___________。

答案：【5050】单元作业五1.已知数组a中保存n个整数元素，下面递归算法计算n个元素的平均值。请在程序空白处补全代码。建议在提交作业前验证算法的正确性。

参考答案：returna[0]评分标准：语句正确10分；否则不得分。第六章树和二叉树单元作业六1.假设用于通讯的电文由8个字母C0，C1，C2，C3，C4，C5，C6，C7组成，在电文中各字母出现的频率分别是14，2，1，7，24，18，5，10。请根据构建的哈夫曼树计算其加权路径长度(WPL)，则WPL=。

参考答案：WPL=(1+2)*5+5*4+(7+10+14)*3+(18+24)*2=212评分标准：计算正确，5分；否则得0分。2.已知一棵二叉树的中序遍历序列是CDBEAGF，后序遍历序列是DCEBGFA，请给出该二叉树的先序遍历序列。

根据中序和后序遍历序列重构二叉树，然后再先序遍历二叉树。参考答案：先序遍历序列是ABCDEFG。评分标准：序列完全正确，5分；否则，0分。3.设二叉树采用二叉链表存储，下面递归函数用于计算二叉树的叶子数量。请在空格处完善代码，实现函数功能。typedefstructBiTNode{//结点结构TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;intCalcLeaves(BiTreeT){/*计算叶子结点的数量*/intnum;if(T==NULL)return0;if((T->lchild==NULL)&&(1))return1;num=2;returnnum;}

参考答案：1.T->rchild==NULL2.CalcLeaves(T->lchild)+CalcLeaves(T->rchild)评分标准：第1、2处正确，各得5分。否则不得分。单元测验六1.单选题：设森林F对应的二叉树B有m个结点。B的根为t，若t的右子树有n个结点，则森林F中第一棵树具有_________个结点。

选项：

A、m-n-1

B、m-n

C、m-n+1

D、m-n+2

答案：【m-n】2.单选题：将树转化成二叉树，则对其根结点而言，_________。

选项：

A、右子树可能不空

B、左、右子树都可能存在

C、左子树一定是空的

D、右子树一定是空的

答案：【右子树一定是空的】3.单选题：对一棵二叉树进行先序遍历的结果是A,B,D,C,E,G,H,F，中序遍历的结果是B,D,A,G,E,H,C,F。则对这棵二叉树后序遍历的结果是_______。

选项：

A、D,B,G,H,E,F,C,A

B、G,H,E,F,C,D,B,A

C、G,H,D,E,F,B,C,A

D、D,B,G,H,F,E,C,A

答案：【D,B,G,H,E,F,C,A】4.单选题：满二叉树也是完全二叉树。

选项：

A、正确

B、错误

答案：【正确】5.单选题：树的双亲表示法是树的顺序存储结构。

选项：

A、正确

B、错误

答案：【正确】6.单选题：与二叉树类似，树也可进行中根遍历。

选项：

A、正确

B、错误

答案：【错误】7.假设存在一棵树，其左子树包含50个结点，右子树包含200个结点。采用中序遍历方法，在处理根结点之前处理了___________个结点。

答案：【50】8.使用顺序存储结构存储具有5000个结点的完全二叉树，假设一个结点存储在第2499的位置，那么它的双亲存储的位置是___________。

答案：【1249】9.一棵二叉树有10个叶子结点，其中度为2的结点有___________个。

答案：【9】10.具有20个叶子结点的哈夫曼树总共有_______个结点。

答案：【39】第七章图单元作业七1.对附件中图的顶点进行拓扑排序。

参考答案：拓扑序列：A,E,F,D,B,G,C评分标准：序列正确，5分；序列错误，0分。2.利用普里姆算法或克鲁斯卡尔算法，构造下面附件中无向网的最小生成树，则该最小生成树的权值之和为。

参考答案：15评分标准：正确，4分；错误，0分。3.在广度优先搜索中利用了队列这种数据结构，如果采用栈的结构，将发生什么情况？

参考答案：如果采用栈的结构，将是对图的深度优先搜索。评分标准：回答正确，5分；回答错误，0分。4.(1)选择题：已知图G的邻接矩阵如附件所示，该图是。A.无向图B.有向图C.无向网D.有向网(2)填空题：上述图G中顶点B的入度为。A.1B.2C.3D.4

参考答案：(1)B(2)C评分标准：每个3分，共6分。单元测试七1.单选题：在图的拓扑排序过程中，输出的顶点应该满足________。

选项：

A、入度为1

B、出度为1

C、入度为0

D、出度为0

答案：【入度为0】2.单选题：当以邻接表存储图时，采用________易于实现图的广度优先搜索。

选项：

A、拓扑序列

B、栈

C、队列

D、最小生成树

答案：【队列】3.单选题：某无向连通图具有n个顶点e条边，利用克鲁斯卡尔算法生成最小生成树的时间复杂度是________。

选项：

A、O(elogn)

B、O(eloge)

C、O(nloge)

D、O(ne)

答案：【O(eloge)】4.单选题：某无向连通图具有n个顶点e条边，利用普利姆算法生成最小生成树的时间复杂度是________。

选项：

A、O(nlogn)

B、O(nloge)

C、O(elogn)

D、O(n^2)

答案：【O(n^2)】5.单选题：图的广度优先搜索类似于二叉树的________。

选项：

A、先序遍历

B、中序遍历

C、后序遍历

D、层次遍历

答案：【层次遍历】6.单选题：在图的遍历过程中，如果不标记已经访问过的顶点，当图中存在回路时，将导致无限循环。

选项：

A、正确

B、错误

答案：【正确】7.单选题：逆邻接表也可用于表示无向图。

选项：

A、正确

B、错误

答案：【错误】8.一个具有20个顶点的无向连通图，其生成树有________条边。

答案：【19】9.有向图具有8个顶点和10条弧，采用逆邻接表存储时，则包含8个头结点和___________个表结点。

答案：【10】10.无向图具有10个顶点和25条边，采用邻接表存储时，则包含10个头结点和___________个表结点。

答案：【50】第八章查找单元测试八1.单选题：对长度为n的线性表，采用顺序查找方法查找，每个元素的平均查找长度为_______。

选项：

A、(n-1)/2

B、n/2

C、(n+1)/2

D、n

答案：【(n+1)/2】2.单选题：假设有k个关键码互为同义词，若用线性探测法把这k个关键码值存入散列表中，要进行的探测次数至少为_____。

选项：

A、k-1

B、k

C、k+1

D、k*(k+1)/2

答案：【k*(k+1)/2】3.单选题：设有一组关键字码{24,3,17,49,60,20}将要插入到表长为12的散列表中，设哈希函数H(key)=key%11。当采用线性探测再散列法处理冲突时，关键字为60的记录的地址是_____。

选项：

A、4

B、5

C、6

D、7

答案：【7】4.单选题：对长度为n的线性表，采用折半查找方法查找，每个元素的平均查找长度为_______。

选项：

A、O(logn)

B、O(n)

C、O(nlogn)

D、O(n^2)

答案：【O(logn)】5.多选题：下列关于二叉排序树的说法正确的是_____。

选项：

A、中序遍历二叉排序树可以得到一个关键字的有序序列。

B、若它的右子树不空，则右子树所有结点的值均大于根结点的值。

C、它的左、右子树均为二叉排序树。

D、它的平均查找长度与树的形态有关。

答案：【中序遍历二叉排序树可以得到一个关键字的有序序列。;若它的右子树不空，则右子树所有结点的值均大于根结点的值。;它的左、右子树均为二叉排序树。;它的平均查找长度与树的形态有关。】6.多选题：在哈希表查找中处理冲突时，开放定址法包括_____等方法。

选项：

A、线性探测再散列

B、二次探测再散列

C、再哈希法

D、伪随机数探测再散列

答案：【线性探测再散列;二次探测再散列;伪随机数探测再散列】7.单选题：与顺序表查找类似，哈希表的平均查找长度是表中记录数n的函数。

选项：

A、正确

B、错误

答案：【错误】8.单选题：当二叉排序树蜕变为单支树时，其平均查找长度与顺序查找相同。

选项：

A、正确

B、错误

答案：【正确】9.单选题：哈希表查找的基本思想是按记录的关键字的值决定记录的存储地址。

选项：

A、正确

B、错误

答案：【正确】10.单选题：含有n（n>2）个结点的二叉排序树是唯一的。

选项：

A、正确

B、错误

答案：【错误】11.单选题：如果用low和high分别指向搜索区间的下界和上界，折半查找失败的判定条件是low>high的结果为真值。

选项：

A、正确

B、错误

答案：【正确】12.一个顺序存储的有序表为{7，9，11，30，42，45，52，65，77，89，91}，第一个元素7保存在下标为1的位置，当折半查找89时，________次比较后查找成功。

答案：【3/三】13.折半查找也称为二分查找，它需要满足两个条件分别，即记录是有序的并且采用________存储结构。

答案：【顺序】14.在顺序表中，采用从后向前查找时，通常将待查记录存放在顺序表中下标为________的位置，称之为哨兵。

答案：【0/零】单元作业八1.一组数据元素的关键码是{7，1，14，2，10，18，5，24}，设哈希表的长度为12，采用的哈希函数为H(k)=k%11，用二次探测再散列法解决冲突，请回答如下问题：（1）关键码24对应的数据元素在哈希表中的位置是。（2）哈希表的装填因子为。（3）在等概率下查找成功时的平均查找长度为。

参考答案：(1)6(2)2/3或0.667(3)1.5查找关键码24需要4次，18需要2次，其他的各需1次。因此，平均查找长度为(4+2+1*6)/8=1.5。评分标准：每空4分，共12分。2.判断下面关于二叉排序树的说法是否正确。1.若二叉排序树的左、右子树不空，则左子树所有结点的值均小于右子树所有结点的值。2.二叉排序树和折半查找的平均查找长度都与logn成正比。3.在二叉排序树中插入新结点时需要移动其他结点。4.先序遍历二叉排序树可以得到关键字的有序序列。5.一棵含有n个结点的二叉排序树的平均查找长度与树的形态有关。

参考答案：正确的说法是1、2、5；错误的说法是3、4。对于3中的说法，正确的应该是“不需要移动其他结点”。对于4中的说法，正确的应该是“中序遍历”。评分标准：正确判断每个说法得2分，否则得0分。3.如果在关键字集合{23，15，26，19，8，5，13，47，39}上实现折半查找，需要从小到大排序关键字并顺序存储。设下标为0的位置不保存关键字，如果折半查找关键字26，请给出折半查找的次数及每次查到的关键字。

参考答案：关键字依从小到大保存在下标从1至9的顺序表中。折半查找2次可以查到26。第一次，(1+9)/2=5，查到19；第二次，(6+9)/2=7.5，下取整为7，查到26。评分标准：两次正确，4分；分别查到19和26，每个数2分，共4分。第九章内部排序单元测试九1.单选题：用某种排序方法对关键字集合{26,80,25,46,11,29,63,32,21}进行排序时，元素序列的变化情况如下：(1)26,80,25,46,11,29,63,32,21(2)26,80,25,46,11,29,63,32,21(3)25,26,80,46,11,29,63,32,21(4)25,26,46,80,11,29,63,32,21则所采用的排序方法是_____。

选项：

A、简单选择排序

B、直接插入排序

C、2-路归并排序

D、快速排序

答案：【直接插入排序】2.单选题：用某种排序方法对关键字集合{70,12,83,43,56,33,22,8}进行排序时，元素序列的变化情况如下：(1)70,12,83,43,56,33,22,8(2)8,12,83,43,56,33,22,70(3)8,12,83,43,56,33,22,70(4)8,12,22,43,56,33,83,70则所采用的排序方法是_____。

选项：

A、简单选择排序

B、直接插入排序

C、希尔排序

D、快速排序

答案：【简单选择排序】3.单选题：一组记录的关键字码为{45,78,57,36,41,90}，利用快速排序的方法，以第一个记录为枢轴，则一次划分的结果为_____。

选项：

A、36,41,45,57,78,90

B、41,36,45,57,78,90

C、41,36,45,78,57,90

D、41,36,45,90,57,78

答案：【41,36,45,57,78,90】4.多选题：下列哪些排序方法是不稳定的_____。

选项：

A、冒泡排序

B、希尔排序

C、快速排序

D、堆排序

答案：【希尔排序;快速排序;堆排序】5.多选题：下列哪些排序方法是稳定的_____。

选项：

A、直接插入排序

B、冒泡排序

C、归并排序

D、基数排序

答案：【直接插入排序;冒泡排序;归并排序;基数排序】6.单选题：基数排序是基于关键字比较的排序。

选项：

A、正确

B、错误

答案：【错误】7.单选题：快速排序是不稳定的。

选项：

A、正确

B、错误

答案：【正确】8.单选题：堆排序是一种基于插入的排序方法。

选项：

A、正确

B、错误

答案：【错误】9.单选题：依据排序所需的工作量，先进排序方法的时间复杂度是O(nlogn)。

选项：

A、正确

B、错误

答案：【正确】10.归并排序、堆排序和快速排序的平均时间性能相当，但是________排序方法所需的辅助存储量最多。

答案：【归并】11.在堆排序和快速排序中，如果记录的关键字近似正序或反序，则优先选用________排序。

答案：【堆】12.在最好的情况下，冒泡（发泡）排序只需要交换_________次即可完成排序。（请填数字）

答案：【