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

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

有些题目顺序不一致，下载后按键盘ctrl+F进行搜索《数据结构》东北大学客观题试卷1.单选题：给出一组关键字{51，40，13，5，27，26}，对其进行第一趟直接插入排序的结果是（）。

选项：

A、40，51，13，5，27，26

B、5，40，13，27，26，51

C、5，51，40，13，27，26

D、5，40，13，51，27，26

答案：【40，51，13，5，27，26】2.单选题：设low和high分别是在有序表中折半查找的指针，如果查找的关键字key小于low和high的中间值mid所指的关键字，则正确缩小查找区间的是（）。

选项：

A、high=mid

B、high=mid-1

C、low=mid+1

D、low=mid

答案：【high=mid-1】3.单选题：设森林F中具有3棵树，结点个数分别为n1、n2、n3，当把森林F转化为一棵二叉树B之后，B的右子树中结点个数是（）。

选项：

A、n2

B、n3

C、n2+n3

D、无法确定的

答案：【n2+n3】4.单选题：一棵二叉树上具有n、m两个结点，在中序遍历时n在m前的条件是（）。

选项：

A、n在m右方

B、n在m左方

C、n是m祖先

D、n是m子孙

答案：【n在m左方】5.单选题：一棵完全二叉树的第4层（设根为第1层）具有6个叶子结点，则该完全二叉树的结点数最多是（）。

选项：

A、13

B、15

C、19

D、31

答案：【19】6.单选题：下列关于队列的操作，正确的是（）。

选项：

A、取出最近进入队列的若干元素

B、取出队头元素

C、在队列中查找指定的元素

D、在队列任意元素之间插入新元素

答案：【取出队头元素】7.单选题：在链队列中，队头设在（）。

选项：

A、链头

B、链中

C、链尾

D、以上位置都可以

答案：【链头】8.单选题：树和森林都具有（）遍历方法。

选项：

A、后序（根）

B、中序（根）

C、先序（根）

D、以上全部

答案：【先序（根）】9.单选题：如果元素2，3，4，5，6依次进栈，两个元素退栈后，则栈顶元素是（）。

选项：

A、2

B、3

C、4

D、5

答案：【4】10.单选题：设有一个有向图G=(V,E)，其中V={A,B,C,D}，E={<A,C>，<A,D>，<B,A>，<B,C>，<C,D>}，则该图的拓扑排序序列是（）。

选项：

A、BCDA

B、BCAD

C、BADC

D、BACD

答案：【BACD】11.单选题：在二路归并排序过程中，n个关键字需要执行（）趟二路归并。

选项：

A、O(n)

B、O(logn)

C、O(nlogn)

D、O(n^2)

答案：【O(logn)】[vk-content]12.单选题：给定一个整数集合{2,6,14,3,11,10,9}，构建相应的哈夫曼树，则该树的加权路径长度为（）。

选项：

A、55

B、104

C、110

D、145

答案：【145】13.单选题：给出一组元素的关键码是21，37，47，40，12，哈希表长为10，哈希函数采用(k)=k%7，冲突解决策略为线性探测再散列，则关键码12保存位置为（）。

选项：

A、4

B、5

C、6

D、7

答案：【7】14.单选题：克鲁斯卡尔（Kruskal）算法求解最小生成树问题，主要适用于（）图。

选项：

A、稀疏

B、稠密

C、非连通

D、无权

答案：【稀疏】15.单选题：图的深度优先搜索类似树的（）遍历。

选项：

A、先根

B、中根

C、后根

D、层次

答案：【先根】16.单选题：在一个具有n个顶点的有向图中，如果所有顶点的入度之和为k，则所有顶点的出度之和为（）。

选项：

A、k-1

B、k

C、k+1

D、2k

答案：【k】17.单选题：具有n个顶点和e条边的无向图，如果采用邻接矩阵存储，则矩阵中非零元的个数是（）。

选项：

A、e/2

B、e

C、2e

D、n+e

答案：【2e】18.单选题：假设一个栈的输入序列是1、2、3、4，则不可能得到的输出序列是（）。

选项：

A、4、1、2、3

B、1、2、3、4

C、4、3、2、1

D、2、4、3、1

答案：【4、1、2、3】19.单选题：带头结点的单链表head为空的判定条件是（）。

选项：

A、head->next->next==NULL

B、head->next==NULL

C、head->next=NULL

D、head==NULL

答案：【head->next==NULL】20.单选题：线性表采用单链表存储，它不具有的特点是（）。

选项：

A、插入和删除元素不需要移动元素

B、不必事先预估和申请存储空间

C、可以随机访问任一元素

D、存储所需空间与线性表的长度成正比

答案：【可以随机访问任一元素】21.单选题：已知二叉树的先序遍历序列是ABCDE，中序遍历序列是CBDAE，则后序遍历序列是（）。

选项：

A、CDEBA

B、EDCBA

C、CDBEA

D、BCDEA

答案：【CDBEA】22.单选题：在长度为n的线性表的表尾插入一个新元素，其时间复杂度为（）。

选项：

A、O(1)

B、O(n)

C、O(n^2)[注：n^2表示n的2次方]

D、O(logn)

答案：【O(1)】23.单选题：输出一个二维数组a[m][n]中各元素的时间复杂度为（）。

选项：

A、O(m)

B、O(n)

C、O(mn)

D、O(m+n)

答案：【O(mn)】24.单选题：在一个单链表中，若删除s所指结点的直接后继结点，则执行()。

选项：

A、p=s->next;s->next=p->next;free(p);

B、p=s->next;free(p);s->next=s->next->next;

C、s->next=s->next->next;free(s);

D、s->next=s->next->next;p=s->next;free(p);

答案：【p=s->next;s->next=p->next;free(p);】25.单选题：在一个单链表中，已知p所指结点是q所指结点的前驱结点，若在p和q之间插入t结点，则执行()。

选项：

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

B、t->next=p->next;p->next=t;

C、p->next=t->next;t->next=q;

D、t->next=q;p->next=t->next;

答案：【t->next=p->next;p->next=t;】26.多选题：以下数据结构中，属于线性结构的是（）。

选项：

A、字符串

B、图

C、树

D、栈

答案：【字符串;栈】27.多选题：对关键字集合{50,25,85,35,10,55,5}进行起泡排序，前两趟发泡排序的结果分别是（）。

选项：

A、25,50,35,10,55,5,85

B、25,50,35,10,5,55,85

C、25,35,10,50,5,55,85

D、5,25,85,35,10,55,50

答案：【25,50,35,10,55,5,85;25,35,10,50,5,55,85】28.多选题：下面排序方法中，时间复杂度为O(nlogn)的是（）。

选项：

A、简单排序

B、基数排序

C、快速排序

D、堆排序

答案：【快速排序;堆排序】29.多选题：基于“关键字间的比较和移动”的排序方法有（）。

选项：

A、插入排序

B、快速排序

C、归并排序

D、基数排序

答案：【插入排序;快速排序;归并排序】30.多选题：树的存储结构包括（）。

选项：

A、双亲表示法

B、孩子表示法

C、孩子-兄弟表示法

D、邻接矩阵法

答案：【双亲表示法;孩子表示法;孩子-兄弟表示法】31.多选题：按照先左子树、后右子树的次序，二叉树的遍历方法分为（）。

选项：

A、先序遍历

B、中序遍历

C、后序遍历

D、广度优先搜索

答案：【先序遍历;中序遍历;后序遍历】32.单选题：广义表的数据元素可以是单个元素，也可以是广义表。

选项：

A、正确

B、错误

答案：【正确】33.单选题：串采用定长顺序存储，串的实际长度不可以直接获得，需要遍历整个串获得。

选项：

A、正确

B、错误

答案：【错误】34.单选题：一维数组也是一种线性结构。

选项：

A、正确

B、错误

答案：【正确】35.单选题：希尔排序的增量序列可以不同，但是最后的增量都是1。

选项：

A、正确

B、错误

答案：【正确】36.单选题：如果1,2,…,n依次进入队列，出队的序列存在多种可能。

选项：

A、正确

B、错误

答案：【错误】37.单选题：线性表中各元素可以任意排列，可以按照需要随意存取。

选项：

A、正确

B、错误

答案：【正确】38.两个关键字相等的记录，排序后它们的先后位置可能发生变化，这类排序称为的排序方法。（限填汉字）

答案：【不稳定】39.一个顺序存储的线性表存有100个数据元素，则插入一个新元素的可能位置有个。（限填数值）

答案：【101】40.一个顺序存储的线性表中含有100个数据元素，若要删除第60个元素，则需要向前移动元素次。（限填数值）

答案：【40】41.带权值的图称为。（限填一个汉字）

答案：【网】42.已知一组记录{540，380，960，230，150，720，620，450，830}保存在数组A[1..9]中，按照升序排序，当第一趟选择排序后，540将被保存在数组A中下标为的位置。（限填数值）

答案：【5】43.循环队列的空间为100，队头指针front的值为80，队尾指针rear的值为20，则队列中数据元素的个数为个。（限填数值）

答案：【40】44.设一个具有100行100