数据结构试卷及其答案解析

专升本《数据结构》

一、 （共75题,共150分）

1. 数据的逻辑结构是由（）部分组成的。 （2分） A.2 B.3 C.4 D.5

标准答案：A

2. 算法是对某一类问题求解步骤的有限序列，并具有（）个特性。 （2分） A.3 B.4 C.5 D.6

标准答案：C

3. 队列的入队操作是在（）进行的。 （2分） A.队头 B.队尾 C.任意位置 D.指定位置

标准答案：B

4. 队列的出队操作是在（）进行的。 （2分） A.队头 B.队尾 C.任意位置 D.指定位置

标准答案：A

5. 数组通常采用顺序存储的优点是（）。 （2分） A.便于增加存储空间 B.便于依据下标进行随机存取 C.避免数据元素的移动 D.防止下标溢出

标准答案：B

6. 下列给

问题说明

部分题目或答案有问题，现将已经发现的公布如下，同学在作这些模拟题的时候应着重做题方法的理解，遇到问题以教材或课件为准，不确定的地方可找同学商量或问我

（1）试卷1第一套填空题第1题，试卷1第2套选择题第3题关于循环队列队头指针和队尾指针的约定与教材不一致，以教材或课件为准，实际上front指向的是队头元素，rear指向当前尚未被占用的第一个队列空间，队慢或队空的判定条件及入队/出队等操作具体可参考课件或教材

（2）试卷1第一套应用题第5题，不声明邻接点顺序时默认编号最小的邻接点为第一邻接点，该图的深度优先遍历序列为123465,答案错。此外，当给定邻接表时则邻接点顺序按照邻接表中的前后顺序确定，如试卷1第二套填空题第8题

（3）试卷1第五套应用题第4题，两种方法处理冲突的方法下所求ASL值相等都为7/6

（4）试卷1第五套填空题第8题答案给出的是小顶堆需满足的条件，大顶堆满足k i>=k2i && k i>=k2i+1（5）试卷1第一套填空题第9题模式匹配的BF算法以书中答案为准，两者区别在于，教材中存储字符串的数组的0号单元不存放有效字符，而试卷答案认为0号单元也放数组

（6）试卷1第二套填空题第7题给定初始序列建堆未声明建大顶堆还是小顶堆，

选择题（查找排序不考）

1．下面关于线性表的叙述错误的是（ D ）。

(A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现

(D) 线性表采用顺序存储便于插入和删除操作的实现

2．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ B ）

个空指针域。 (A) 2m-1 (B) 2m (C) 2m+1 3．设顺序循环队列Q[0：M-1]的头

指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素

的当前位置，则该循环队列中的元素个数为（ C ）。

(A) R-F (B) F-R (C) (R-F+M)％M (D) (F-R+M)％M

4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为

（ A ）。 (A) BADC

(B) BCDA

(C) CDAB

(D) CBDA (D) 4m

5．设某完全无向图中有n个顶点，则该完全无向图中有（ A ）条边。 (A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1

6．

选择题（查找排序不考）

1．下面关于线性表的叙述错误的是（ D ）。

(A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现

(D) 线性表采用顺序存储便于插入和删除操作的实现

2．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ B ）

个空指针域。 (A) 2m-1 (B) 2m (C) 2m+1 3．设顺序循环队列Q[0：M-1]的头

指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素

的当前位置，则该循环队列中的元素个数为（ C ）。

(A) R-F (B) F-R (C) (R-F+M)％M (D) (F-R+M)％M

4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为

（ A ）。 (A) BADC

(B) BCDA

(C) CDAB

(D) CBDA (D) 4m

5．设某完全无向图中有n个顶点，则该完全无向图中有（ A ）条边。 (A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1

6．

7、线性表的链式存储比顺序存储最有利于进行（ ）操作。 A）查找 B）表尾插入或删除 C）按值插入或删除 D）表头插入或删除 8、带头结点的单链表H为空的判定条件是（ ）。 A）H==NULL B）H->next==NULL

总分 C）H->next==H D）H!=NULL

9、在一个带头结点的单链表H中，若要向表头插入一个由指针p指向的新结点，则应执行的操作是（ ）

A）H=p;p->next=H; B）p->next=H;H=p;

C）p->next=H;p=H; D）p->next=H->next; H->next=p;

10、设线性表有n个元素，以下算法中，（ ）在顺序表上实现比在链表上实现的效率更高。

A）输出第i（0≤i≤n-1）个元素 B）交换第0个元素与第1个元素的值 C）顺序输出这n个元素的值

D）输出与给定值x相等的元素在线性表中的序号 11．二分查找要求节点（ ）

A）．有序、顺序存储 B）. 有序、链接存储 C）．无序

1．算法分析的目的是( C )。

A.找出数据结构的合理性 B.研究算法中输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2．（ B ）是具有相同特性数据元素的集合，是数据的子集。

A.数据符号 B.数据对象 C.数据 D.数据结构 3．用链表表示线性表的优点是 ( C )。

A.便于随机存取 B.花费的存储空间比顺序表少 C.便于插入与删除 D.数据元素的物理顺序与逻辑顺序相同 4．输入序列为（A,B,C,D）不可能的输出有（ D ）。

A.(A,B,C,D) B. (D,C,B,A) C. (A,C,D,B) D . (C,A,B,D)

5．在数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是( B )。

A. front=maxSize B. (rear+1)%maxSize=front

习题一

一、 选择题 ( 每小题 2 分，共 20 分 )

1．下列程序段的时间复杂度为（ ）。

i=0，s=0； while (s

(A) O(n/2) (B) O(n/3) (C) O(n) (D) O(n2)

2．设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列（ ）存储方式最节省运算时间。

(A) 单向链表 (B) 单向循环链表 (C) 双向链表 (D) 双向循环链表

3．设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（ ）。

(A) s->next=p->next；p->next=-s； (B) q->next=s； s->next=p；

(C) p->next=s->next；s->next=p； (D) p->next=s；s->next=q；

4．设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（ ）。

(A) 5，3，4，6，1，2 (B) 3，2，5，6，4，1

(C) 3，1，2，5，4，6 (D) 1，5，4，6，2，3

5．设有一个10阶的下三角矩阵A（包括对角线），按

一、单项选择题(在每小题的四个备选答案中选出一个正确答案，并将其号码填在题干的括号内。每小题2分，共30分) 1.计算机中算法是指( )。

A.计算方法 B.排序方法 C.解决某一问题的有限运算序列 D.调度方法

2.在一个单链表中，若指针p所指结点不是最后结点，在p之后插入指针s所指结点，则应执行的语句序列为( )。

A. s->next=p；p->next=s; B. s->next=p->next;p->next=s； C. s->next=p->next;p:=s; D. p->next=s;s->next=p;

3. 对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）

A．head==NULL B．head->next==NULL C．head->next==head D．head!=NULL

4.循环队列用数组A［0..m-1］存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是( )。 A.(rear-front+m) MOD

一、单项选择题(在每小题的四个备选答案中选出一个正确答案，并将其号码填在题干的括号内。每小题2分，共30分) 1.计算机中算法是指( )。

A.计算方法 B.排序方法 C.解决某一问题的有限运算序列 D.调度方法

2.在一个单链表中，若指针p所指结点不是最后结点，在p之后插入指针s所指结点，则应执行的语句序列为( )。

A. s->next=p；p->next=s; B. s->next=p->next;p->next=s； C. s->next=p->next;p:=s; D. p->next=s;s->next=p;

3. 对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）

A．head==NULL B．head->next==NULL C．head->next==head D．head!=NULL

4.循环队列用数组A［0..m-1］存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是( )。 A.(rear-front+m) MOD

江西财经大学

学年 第 学期期末考试试卷

试卷代码：03265A卷 课时：96

课程名称：数据结构 适用对象：信息管理与信息系统 一、名词解释（每小题2分，共10分） 1、抽象数据类型 2、排序的稳定性 3、二叉排序树 4、冲突 5、哈希表

二、填空题（每空1分，共14分）

1、通常要表达一种数据结构，要说明 、 、 三方面。 2、带头结点的双向循环链表，空链表的条件是 。

3、已知一棵度为3的树有3个度为1的结点，3个度为2的结点，3个度为3的结点，则该数有 个叶子。

4、有一个长度为21的有序表采用二分查找方法进行查找，共有 个元素查找长度为5。 5、假设一完全二叉树共378个结点，则其中有 个叶子。

6、在内部排序中，需求附加内存容量最大的是 排序。

7、在长度为N的顺序表中的第i（1<=i<=N+1）个元素位置插入一个元素，元素的移动次数为 。

8、循环队列Q中，利用浪费一个空间的办法处理队列，则队空的条件是 ，队满的条件是 。

9、设深度为h的