郑航院2020年上学期数据结构试卷1答案

一、单选题（题数：30，共60.0分）1算法分析的两个主要方面是()。（2.0分）A、[url=]空间复杂度和时间复杂度[/url]B、[url=]正确性和简单性[/url]C、[url=]可读性和文档性[/url]D、[url=]数据复杂性和程序复杂性[/url]正确答案：A我的答案：A答案解析：2具有线性结构的数据结构是()。（2.0分）A、[url=]图[/url]B、[url=]树[/url]C、[url=]二叉树[/url]D、[url=]栈[/url]正确答案：D我的答案：D答案解析：3下面程序段的时间复杂度是()。

for(i=0;i<m;i++)

for(j=0;j<n;j++)

a[j]=i*j;（2.0分）A、[url=]O(m2)[/url]B、[url=]O(n2)[/url]C、[url=]O(m*n)[/url]D、[url=]O(m+n)[/url]正确答案：C我的答案：B答案解析：4抽象数据类型的三个组成部分分别为()。（2.0分）A、[url=]数据对象、数据关系和基本操作[/url]B、[url=]数据元素、逻辑结构和存储结构[/url]C、[url=]数据项、数据元素和数据类型[/url]D、[url=]数据元素、数据结构和数据类型[/url]正确答案：A我的答案：A答案解析：5线性表是n个()的有限序列。（2.0分）A、[url=]表元素[/url]B、[url=]字符[/url]C、[url=]数据元素[/url]D、[url=]数据项[/url]正确答案：C我的答案：C答案解析：6一个顺序表的第一个元素的存储地址是90,每个元素的长度为2,则第6个元素的存储地址是()。（2.0分）A、[url=]98[/url]B、[url=]100[/url]C、[url=]102[/url]D、[url=]106[/url]正确答案：C我的答案：B答案解析：7向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动()个元素。（2.0分）A、[url=]8[/url]B、[url=]63.5[/url]C、[url=]63[/url]D、[url=]7[/url]正确答案：C我的答案：B答案解析：8在一个长度为n的顺序表中删除第i个元素,需要向前移动()个元素。（2.0分）A、[url=]n-i[/url]B、[url=]n-i+1[/url]C、[url=]n-i-1[/url]D、[url=]i+1[/url]正确答案：C我的答案：A答案解析：9在线性表的下列存储结构中,读取元素花费的时间最少的是()。（2.0分）A、[url=]单链表[/url]B、[url=]双链表[/url]C、[url=]循环链表[/url]D、[url=]顺序表[/url]正确答案：D我的答案：D答案解析：10栈的插入和删除操作在()。（2.0分）A、[url=]栈底[/url]B、[url=]栈顶[/url]C、[url=]任意位置[/url]D、[url=]指定位置[/url]正确答案：B我的答案：B答案解析：11栈中元素的进出原则是()。（2.0分）A、[url=]先进先出[/url]B、[url=]后进先出[/url]C、[url=]栈空则进[/url]D、[url=]栈满则出[/url]正确答案：B我的答案：B答案解析：12正常情况下,删除非空的顺序存储结构的堆栈的栈顶元素,栈顶指针top的变化是()。（2.0分）A、[url=]top不变[/url]B、[url=]top=0[/url]C、[url=]top=top+1[/url]D、[url=]top=top-1[/url]正确答案：D我的答案：D答案解析：13队列的插入操作是在()。（2.0分）A、[url=]队尾[/url]B、[url=]队头[/url]C、[url=]队列任意位置[/url]D、[url=]队头元素后[/url]正确答案：A我的答案：A答案解析：14队列的删除操作是在()。（2.0分）A、[url=]队尾[/url]B、[url=]队头[/url]C、[url=]队列任意位置[/url]D、[url=]队头元素后[/url]正确答案：D我的答案：B答案解析：15设有两个串S1和S2,求串S2在S1中首次出现位置的运算称作()。（2.0分）A、[url=]连接[/url]B、[url=]求子串[/url]C、[url=]模式匹配[/url]D、[url=]判断子串[/url]正确答案：C我的答案：C答案解析：16广义表((a),a)的表尾是()。（2.0分）A、[url=]a[/url]B、[url=](a)[/url]C、[url=]()[/url]D、[url=]((a))[/url]正确答案：B我的答案：B答案解析：17广义表G=(a,(b,c,d,(e,f)),g)的长度是()。（2.0分）A、[url=]3[/url]B、[url=]4[/url]C、[url=]7[/url]D、[url=]8[/url]正确答案：A我的答案：A答案解析：18常对数组进行两种基本操作是()。（2.0分）A、[url=]建立和删除[/url]B、[url=]索引和修改[/url]C、[url=]查找和修改[/url]D、[url=]查找与索引[/url]正确答案：C我的答案：C答案解析：19对一些特殊矩阵采用压缩存储的目的主要是为了()。（2.0分）A、[url=]表达变得简单[/url]B、[url=]对矩阵元素的存取变得简单[/url]C、[url=]去掉矩阵中的多余元素[/url]D、[url=]减少不必要的存储空间的开销[/url]正确答案：D我的答案：D答案解析：20稀疏矩阵一般的压缩存储方法有两种,即()。（2.0分）A、[url=]空间复杂度和时间复杂度[/url]B、[url=]正确性和简单性[/url]C、[url=]可读性和文档性[/url]D、[url=]数据复杂性和程序复杂性[/url]正确答案：A我的答案：B答案解析：21树最适合用来表示()。（2.0分）A、[url=]有序数据元素[/url]B、[url=]无序数据元素[/url]C、[url=]元素之间具有分支层次关系的数据[/url]D、[url=]元素之间无联系的数据[/url]正确答案：C我的答案：C答案解析：22把一棵树转换为二叉树后,这棵二叉树的形态是()。（2.0分）A、[url=]唯一的[/url]B、[url=]有多种[/url]C、[url=]有多种,但根结点都没有左孩子[/url]D、[url=]有多种,但根结点都没有右孩子[/url]正确答案：A我的答案：A答案解析：23关键路径是事件结点网络中()。（2.0分）A、[url=]从源点到汇点的最长路径[/url]B、[url=]从源点到汇点的最短路径[/url]C、[url=]最长的回路[/url]D、[url=]求关键路径[/url]正确答案：A我的答案：A答案解析：24无向图的邻接矩阵是一个()。（2.0分）A、[url=]上三角矩阵[/url]B、[url=]下三角矩阵[/url]C、[url=]零矩阵[/url]D、[url=]对称矩阵[/url]正确答案：D我的答案：D答案解析：25一个具有n个顶点的有向图最多有()条边。（2.0分）A、[url=]n×(n-1)[/url]B、[url=]n×(n-1)/2[/url]C、[url=]n×(n+1)/2[/url]D、[url=]n2[/url]正确答案：B我的答案：A答案解析：26在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的()倍。（2.0分）A、[url=]1/2[/url]B、[url=]1[/url]C、[url=]2[/url]D、[url=]4[/url]正确答案：B我的答案：B答案解析：27已知一个有序表为(11,22,33,44,55,66,77,88,99),则折半查找55需要比较()次。。（2.0分）A、[url=]1[/url]B、[url=]2[/url]C、[url=]3[/url]D、[url=]4[/url]正确答案：A我的答案：A答案解析：28在散列查找中,平均查找长度主要与()有关。。（2.0分）A、[url=]散列表长度[/url]B、[url=]散列元素个数[/url]C、[url=]装填因子[/url]D、[url=]处理冲突方法[/url]正确答案：C我的答案：C答案解析：29在各种查找方法中,平均查找次数与结点个数n无关的查找方法是()。（2.0分）A、[url=]顺序查找[/url]B、[url=]折半查找[/url]C、[url=]哈希查找[/url]D、[url=]分块查找[/url]正确答案：C我的答案：C答案解析：30

研究数据结构就是研究（

）

（2.0分）A、[url=]数据的逻辑结构

[/url]B、[url=]数据的存储结构

[/url]C、[url=]数据的基本操作

[/url]D、[url=]数据的逻辑结构、存储结构及其基本操作

[/url]正确答案：D我的答案：D

二、填空题（题数：11，共20.0分）1在线性结构中,第一个结点____前驱结点,其余每个结点有且只有____个前驱结点;最后一个结点____后继结点,其余每个结点有且只有1个后续结点

（3.0分）

[url=]正确答案[/url]

第一空：无

第二空：一

第三空：无

我的答案:第一空：没有

第二空：1

第三空：没有

2在树形结构中,结点的上层结点称为____结点。叶子结点没有____结点。

（2.0分）

[url=]正确答案[/url]

第一空：父亲

第二空：孩子

我的答案:第一空：前驱

第二空：后继

3线性表的逻辑结构是____(“线性结构”或者“树结构”、“图结构”),其所含元素的个数称为线性表的____,结点间的关系是____(“一对一”或者“一对多”、“多对多”)的

（3.0分）

[url=]正确答案[/url]

第一空：线性结构

第二空：长度

第三空：一对一

我的答案:第一空：

第二空：

第三空：

4顺序表中逻辑上相邻元素的物理位置____(“必定”还是“不一定”)相邻。单链表中逻辑上相邻的元素的物理位置____相邻

（2.0分）

[url=]正确答案[/url]

第一空：必定

第二空：不一定

我的答案:

5在具有n个元素的循环队列中,队满时具有____个元素

（1.0分）

[url=]正确答案[/url]

第一空：n-1

我的答案:

6广义表运算式HEAD(TAIL((a,b,c),(x,y,z)))的结果是:____。

（1.0分）

[url=]正确答案[/url]

第一空：(x,y,z)

我的答案:

7哈夫曼树是其树的带权路径长度____的二叉树

（1.0分）

[url=]正确答案[/url]

第一空：最小

我的答案:

8在无向图G的邻接矩阵A中,若A[j]等于1,则A[j]等于____

（1.0分）

[url=]正确答案[/url]

第一空：1

我的答案:

9图有____、____等存储结构,遍历图有____、____等方法

（4.0分）

[url=]正确答案[/url]

第一空：邻接矩阵

第二空：邻接表

第三空：深度优先遍历

第四空：广度优先遍历

我的答案:

10带头结点的单链表head为空的条件是____。

（1.0分）

[url=]正确答案[/url]

第一空：head->next==NULL

我的答案:

11在一个长度为n的向量中删除第i个元素(1≤i≤n)时,需向前移动____个元素

（1.0分）

[url=]正确答案[/url]

第一空：n-i

我的答案:

三、判断题（题数：15，共15.0分）1线性表的每个结点只能是一个简单类型,而链表的每个结点可以是一个复杂类型。()

（1.0分）

正确答案：×我的答案：×答案解析：2在单链表中,要访问某个结点,只要知道该结点的地址即可;因此,单链表是一种随机存取结构。()

（1.0分）

正确答案：×我的答案：×答案解析：3在具有头结点的单链表中,头指针指向链表的第一个数据结点。()

（1.0分）

正确答案：√我的答案：×答案解析：4在表结构中最常用的是线性表,栈和队列不太常用。()

（1.0分）

正确答案：×我的答案：×答案解析：5两个栈共享一片连续内存空间时,为提高内存利用率,减少溢出机会,应把两个栈的栈底分别设在这片内存空间的两端。()

（1.0分）

正确答案：√我的答案：√答案解析：6一个栈的输入序列是12345,则栈的输出序列不可能是12345。()

（1.0分）

正确答案：√我的答案：×答案解析：7广义表是一种多层次的数据结构,其元素可以是单原子也可以是子表。()

（1.0分）

正确答案：√我的答案：√答案解析：8存在这样的二叉树,对它采用任何次序的遍历,结果相同。()

（1.0分）

正确答案：×我的答案：√答案解析：9中序