2019秋《数据结构》作业

2014秋《数据结构》作业。

单选题。第1题下列编码中属前缀码的是( )a、b、c、d、

第2题下列各式中，按增长率由小至大的顺序正确排列的是()。a．n1/2，n!，2n，n3/2b．n3/2，2n，nlogn，2100c．2n，logn，nlogn，n3/2d．2100，logn, 2n, nna、ab、bc、cd、d

第3题设p指向单链表中的一个结点，s指向待插入的结点，则下述程序段的功能是( )s->next=p->next;p->next=s;t=p->data;p->data=s->data;s->data=t;

a、结点*p与结点*s的数据域互换b、在p所指结点的元素之前插入元素c、在p所指结点的元素之后插入元素d、在结点*p之前插入结点*s第4题设s=”abc”;t=”xyz”，则strcmp(s,t)的值为( )a、正数b、负数c、零d、不确定第5题以下广义表关系正确的是( )a、线性表《再入表《纯表《递归表b、线性表《纯表《递归表《再入表c、纯表《线性表《再入表《递归表d、线性表《纯表《再入表《递归表第6题假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行( )次探侧。a、k-1b、kc、k+1d、k(k+1)/2第7题n个记录直接选择排序时所需的记录最多交换次数是( )a、n-1b、nc、n(n-1)/2d、n(n+1)/2第8题线索二叉树中某结点为叶子的条件是( )a、p-> lchild!=null ||p-> rchild!

=nullb、p-> ltag==0 ||p-> rtag==0

c、p-> lchild!=null & p-> rchild!=nulld、p-> ltag==1 & p-> rtag==1

第9题设有向图n个顶点和e条边，进行拓扑排序时，总的计算时间为( )a)o(nlog2n)b)o(en)c)o(elog2n)d)o(n+e)a、ab、bc、cd、d

第10题在下列排序方法中，空间复杂性为o(log2n)的方法为( )a、直接选择排序b、归并排序c、堆排序d、快速排序第11题设计一个判断表达式中左右括号是否配对出现的算法，采用( )数据结构最好。a、顺序表b、链表c、队列d、栈第12题以下叙述错误的是()。a、数据可分为数值型和非数值型。

b、数据类型可分为原子类型和结构类型c、运算可分为加工型和引用型。

d、数据结构可分为逻辑结构和非逻辑结构第13题导致队列下溢的操作是( )a、队满时执行出队b、队满时执行入队c、队空时执行出队d、队空时执行入队。

第14题若要在o(1)的时间内将两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向( )a、各自的头结点b、各自的尾结点c、各自的第一个元素结点d、一个表的头结点，另一个表的尾结点第15题算法分析的目的是( )a、找出数据结构的合理性b、研究算法中的输入/输出关系c、分析算法的效率以求改进d、分析算法的易读性。

第16题若要在单链表中的结点*p之后插入一个结点*s，则应执行的语句是( )a、s-> next=p-> next; p-> next=s;b、p-> next=s; s-> next=p-> next;c、p-> next=s-> next; s-> next=p;d、s-> next=p; p-> next=s-> next;

第17题在散列查找中，平均查找长度主要与( )有关。a、散列表长度b、散列元素的个数c、装填因子d、处理冲突方法第18题对n个元素进行冒泡排序，最好情况下的只需进行( )对相邻元素之间的比较。a、nb、n-1c、n+1d、n/2第19题给定整数集合，与之对应的哈夫曼树是( )

a、ab、bc、cd、d第20题连通网的最小生成树是其所有生成树中()。a、顶点集最小的生成树b、边集最小的生成树c、顶点权值之和最小的生成树d、边的权值之和最小的生成树。

第21题如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是( )a、有向完全图b、连通图c、强连通图d、有向无环图第22题( )存储方式适用于折半查找。a、键值有序的单链表b、键值有序的顺序表c、键值有序的双链表d、键值无序的顺序表第23题单链表中增加头结点的目的是为了( )a、使单链表至少有一个结点b、标识表结点中首结点的位置c、方便运算的实现d、说明单链表是线性表的链式存储第24题若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用( )存储方式最节省运算时间( )

a、单链表b、顺序表c、双链表d、单循环链表第25题要解决散列引起的冲突问题，常采用的方法有( )a、数字分析法、平方取中法b、数字分析法、线性探测法c、二次探测法、平方取中法d、二次探测法、链地址法第26题串s=″data structure″中长度为3的子串的数目是( )a、9b、11c、12d、14第27题若下图表示某广义表，则它是一种( )

a、线性表b、纯表c、再入表d、递归表。

判断题。第28题线索二叉链表就是用结点的空指针域来存放某种遍历的前趋和后继线索，所以线索二叉链表中就没有空指针了。（×

第29题用线性探测法解决突出时，同义词在散列表中是相邻的。（×第30题计算机的速度越快，算法的时间复杂性就越低。（×第31题链表中逻辑上相邻的元素在物理位置上不一定相邻。

（√第32题以中序方式遍历一个堆，则得到一个有序序列。（√

第33题若链队列的头指针为f，尾指针为r，则队列中元素个数为r-f。（×第34题稀疏矩阵压缩存储后会丧失随机存取特性。（√

第35题有向图的邻接表和逆邻接表中的结点数肯定是相同的。（√第36题缩短关键路径上活动的工期一定能够缩短整个工程的工期。（×第37题循环队列中入队和出队的节点位置可出现在数组的任一端，已不满足“一端进另一端出”的要求，故实际上已不是队列了。

（×第38题顾名思义，快速排序法是在所有情况下，速度最快的排序方法。（×第39题若二叉树中没有度为1的结点，则为满二叉树。（×第40题消除递归不一定需要使用栈。（√

第41题开散列表和闭散列表的装填因子都可大于、等于或小于1。（×第42题若算法的复杂性与数据集的状态无关，则最好、最坏和平均复杂性是相同的。（√

第43题顺序表不需存放指针，链表要存放指针，故链表的存储空间要求总是比顺序表大。（×

第44题线性表、树、图等都可以用广义表表示。（√第45题基数排序不需进行关键字间的比较，故执行时间比基于比较的排序方法要快。（×

第46题设串的长度为n，则其子串个数为n(n+1)/2。（×

第47题关键路径是指起点到终点的最短路径，它决定了整个工期的长短。（×第48题由普通树转换来的二叉树，其根结点一定没有右子树。（√第49题计算机的内、外存越大，算法的空间复杂性就越低。

（×第50题在拓扑序列中，若两点vi和vj相邻，则从vi到vj有路径。（×

2019秋《数据结构》作业

数据结构2019级数据结构大作业

北语17秋《数据结构》作业

北语16秋《数据结构》作业

其他用户还读了