第1页 / 共126页
第2页 / 共126页
第3页 / 共126页
第4页 / 共126页
第5页 / 共126页
第6页 / 共126页
第7页 / 共126页
第8页 / 共126页
江南大学数据结构题库答案.pdf
江南大学本科生数据结构题库答案 江大英才 QQ707697898
第一课 绪论
一、选择题
1．算法的计算量的大小称为计算的（ ）。
A．效率 B．复杂性 C．现实性 D．难度
参考答案：B
2．算法的时间复杂度取决于（ ）。
A．问题的规模 B．待处理数据的初态 C．A 和 B
参考答案：C
3．计算机算法指的是（ ）。
A．计算方法 B．排序方法 C．解决问题的步骤序列 D．调度方法
参考答案：C
4．计算机算法必须具备（ ）这三个特性。
A．可执行性、可移植性、可扩充性 B．可执行性、确定性、有穷性
C．确定性、有穷性、稳定性 D．易读性、稳定性、安全性
参考答案：B
5．下面关于算法说法错误的是（ ）。
A．算法最终必须由计算机程序实现
B．为解决某问题的算法同为该问题编写的程序含义是相同的
C．算法的可行性是指指令不能有二义性
D．以上几个都是错误的
参考答案：D
6．从逻辑上可以把数据结构分为（ ）两大类。
A．动态结构、静态结构 B．顺序结构、链式结构
C．线性结构、非线性结构 D．初等结构、构造型结构
参考答案：C
二、应用题
1．数据元素之间的关系在计算机中有几种表示方法？各有什么特点？
参考答案：
数据元素间关系在计算机中有四种表示方法。
（1）顺序存储方式。数据元素顺序存放，每个存储结点只含一个元素。存储位置反映数据元素间的逻
辑关系。存储密度大，但有些操作（如插入、删除）效率较差。
（2）链式存储方式。每个存储结点除包含数据元素信息外还包含一组（至少一个）指针。指针反映数
据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操作（如插入、删除等），但存储空间开
销大（用于指针），另外不能折半查找等。
（3）索引存储方式。除数据元素存储在一段地址连续的内存空间外，尚需建立一个索引表，索引表中
索引指示存储结点的存储位置（下标）或存储区间端点（下标），兼有静态和动态特性。
（4）散列存储方式。通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并
将散列函数的值解释成关键字所在元素的存储地址，这种存储方式称为散列存储。其特点是存取速度快，
只能按关键字随机存取，不能顺序存取，也不能折半存取。
本资料由江南大学研究生 QQ707697898 搜集和整理，其他均属倒卖资料
江南大学本科生数据结构题库答案 江大英才 QQ707697898
2．评价一个好的算法，可以从哪几方面来考虑的？
参考答案：
评价好的算法有四个方面。一是算法的正确性；二是算法的易读性；三是算法的健壮性；四是算法的
时空效率。
3．对于一个数据结构，一般包括哪三个方面的讨论？
参考答案：逻辑结构、存储结构、操作（运算）。
4．当你为解决某一问题而选择数据结构时，应从哪些方面考虑？
参考答案：
通常考虑算法所需要的存储空间量和算法所需要的时间量。后者又涉及到四方面：程序运行时所需输
入的数据总量，对源程序进行编译所需时间，计算机执行每条指令所需时间和程序中指令重复执行的次数。
5．在编制管理通讯录的程序时，什么样的数据结构合适?为什么?
参考答案：
应从两方面进行讨论：如通讯录较少变动（如城市私人电话号码），主要用于查询，以顺序存储较方
便，既能顺序查找也可随机查找；若通讯录经常有增删操作，用链式存储结构较为合适，将每个人的情况
作为一个元素（即一个结点存放一个人），设姓名作关键字，链表安排成有序表，这样可提高查询速度。
6．试举一例，说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，其运算效率不同。
参考答案：
线性表中的插入、删除操作，在顺序存储方式下平均移动近一半的元素，时间复杂度为 O（n）；而在
链式存储方式下，插入和删除时间复杂度都是 O（1）。
7．有实现同一功能的两个算法 A1 和 A2，其中 A1 的时间复杂度为 Tl=O(2n)，A2 的时间复杂度为 T2=O(n2)，
仅就时间复杂度而言，请具体分析这两个算法哪一个好。
参考答案：
对算法 A1 和 A2 的时间复杂度 T1 和 T2 取对数，得 nlog2 和 2logn。显然，算法 A2 好于 A1。
8．分析下面程序段中循环语句的执行次数。
i=0;s=0;n=100;
do{
i=i+1;
s=s+10*i;
}while((i
江南大学本科生数据结构题库答案 江大英才 QQ707697898
{
for(j=n;j>i-1; j--)
for(k=1;k
江南大学本科生数据结构题库答案 江大英才 QQ707697898
语句频度=1+2+…+n=
)1
。
( nn
2
⑵i=0;
j=1;
while (i+j<=n){
x++;
if (i>j) j++;
else i++;
}
参考答案：
i 与 j 初始和为 1，其后每循环一次，i 和 j 中有且仅有一个值增 1，即 i 与 j 的和增 1。由于循环条件
为 i+j<=n，因此循环共执行 n 次。
语句频度＝ｎ。
⑶for (i=1;i<=n;i++)
for (j=1;j<=i;j++)
for (k=1;k<=n;k++)
x++;
参考答案：
语句频度=
)1
nn
(2
2
。
n 。
⑷x=0;y=n; //n 是不小于 1 的常数
while (y>=(x+1)*(x+1)){
x++;
}
参考答案：
语句频度=
⑸设ｎ为正整数，试确定如下程序段中 if 语句的频度。
x=91;
y=100;
while(y>0){
if (x>100){x-=10;y--;}
else x++;
}
参考答案：
语句频度=1100
本资料由江南大学研究生 QQ707697898 搜集和整理，其他均属倒卖资料
江南大学本科生数据结构题库答案 江大英才 QQ707697898
第二课 线性表
一 选择题
1．下列属顺序存储结构优点的是（ ）。
A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示
参考答案：A
2．下列关于线性表的叙述中，错误的是（ ）。
A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
参考答案：B
3．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）
存储方式最节省时间。
A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表
参考答案：A
4．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存
储方式最节省运算时间。
A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表
参考答案：D
5．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ ）存储
方式最节省运算时间。
A．单链表 B．双链表 C．带尾指针的单循环链表 D．带头结点的双循环链表
参考答案：D
6．静态链表中指针表示的是（ ）。
A．下一元素的地址 B．内存储器的地址
C．下一元素在数组中的位置 D．左链或右链指向的元素的地址
参考答案：C
7．链表不具有的特点是（ ）。
A．插入、删除不需要移动元素 B．可随机访问任一元素
C．不必事先估计存储空间 D．所需空间与线性长度成正比
参考答案：B
8．双向链表中有两个指针域，llink 和 rlink 分别指向前趋及后继，设 p 指向链表中的一个结点，现要求删
去 p 所指结点，则正确的删除是（ ）（链中结点数大于 2，p 不是第一个结点）。
A．p->llink->rlink=p->llink; p->llink->rlink=p->rlink; free(p);
B．free (p); p->llink->rlink=p->llink; p->llink->rlink=p->rlink;
C．p->llink->rlink=p->llink; free (p); p->llink->rlink=p->rlink;
D．以上 A，B，C 都不对。
参考答案：D
本资料由江南大学研究生 QQ707697898 搜集和整理，其他均属倒卖资料
江南大学本科生数据结构题库答案 江大英才 QQ707697898
9．下列说法错误的是（ ）。
⑴静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第 i 个元素的时间与 i 无关。
⑵静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。
⑶静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。
A．⑴和⑵ B．⑴ C．⑴、⑵和⑶ D．⑵
参考答案：B
10．若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复杂度为（ ）
(1<=i<=n+1)。
A．O(0) B．O(1) C．O(n) D．O(n2)
参考答案：C
11．对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）。
A．O(n) O(n) B．O(n) O(1) C．O(1) O(n) D．O(1) O(1)
参考答案：C
12．线性表（a1，a2，…，an）以链接方式存储时，访问第 i 位置元素的时间复杂性为（ ）。
A．O(i) B．O(1) C．O(n) D．O(i-1)
参考答案：C
13．在一个以 h 为头的单循环链中，p 指针指向链尾的条件是（ ）。
A．p->next=h B．p->next=NULL C．p->next->next=h D．p->data=-1
参考答案：A
14．双向链表中有两个指针域，llink 和 rlink，分别指回前驱及后继，设 p 指向链表中的一个结点，q 指向
一待插入结点，现要求在 p 前插入 q，则正确的插入为（ ）。
A．p->llink=q; q->rlink=p; p->llink->rlink=q; q->llink=p->llink;
B．q->llink=p->llink; p->llink->rlink=q; q->rlink=p; p->llink=q->rlink;
C．q->rlink=p; p->rlink=q; p->llink->rlink=q; q->rlink=p;
D．p->llink->rlink=q; q->rlink=p; q->llink=p->llink; p->llink=q;
参考答案：D
15．对于一个头指针为 head 的带头结点的单链表，判定该表为空表的条件是（ ）。
A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL
参考答案：B
二、应用题
1．有线性表(a1，a2，…，an)，采用单链表存储，头指针为 H，每个结点中存放线性表中一个元素，现查
找某个元素值等于 X 的结点。分别写出下面三种情况的查找语句，要求时间尽量少。⑴线性表中元素无序。
⑵线性表中元素按递增有序。⑶线性表中元素按递减有序。
参考答案：
设单链表带头结点，工作指针 p 初始化为 p=H->next;
⑴
while(p!=null && p->data!=X) p=p->next;
if(p= =null) return(null);∥查找失败
本资料由江南大学研究生 QQ707697898 搜集和整理，其他均属倒卖资料
江南大学本科生数据结构题库答案 江大英才 QQ707697898
else return(p);∥查找成功
⑵
while(p!=null && p->datanext;
if(p==null || p->data>X) return(null);∥查找失败
else return(p);
⑶
while(p!=null && p->data>X) p=p->next;
if(p==null || p->datanext=p->prior-> next;
p-> prior =p-> next -> prior;
free(p);
参考答案：
前两个语句改为：
p-> prior ->next= p-> next;
p-> next -> prior = p-> prior;
⑵下面的算法描述片段用于在双链表中指针变量 p 所指结点后插入一个新结点：
q=(dlinklist *)malloc(sizeof(dlinklist));
q-> prior =p;
p-> next =q;
q-> next =p-> next;
q = p-> next -> prior;
参考答案：
后三个语句序列应改为：
q-> next =p-> next;
p-> next -> prior =q;
p-> next =q;
3．一线性表存储在带头结点的双向循环链表中，L 为头指针。如下算法：
void unknown (Dlinklist *L)
{ …
p=L->next; q=p->next; r=q->next；
while (q!=L)
{ while (p!=L) && (p->data>q->data) p=p->prior；
q->prior->next=r;
① ______;
q->next=p->next;
q->prior=p;
② ______;
③ ______;
q=r;p=q->prior;
④ ______;
本资料由江南大学研究生 QQ707697898 搜集和整理，其他均属倒卖资料
江南大学本科生数据结构题库答案 江大英才 QQ707697898
}
}
⑴说明该算法的功能。
参考答案：
本算法功能是将双向循环链表结点的数据域按值自小到大排序，成为非递减（可能包括数据域值相等
的结点）有序双向循环链表。
⑵在空缺处填写相应的语句。
参考答案：
①r->prior=q->prior;∥将 q 结点摘下，以便插入到适当位置。
②p->next->prior=q;∥⑵⑶将 q 结点插入
③p->next=q;
④r=r->next;或 r=q->next;∥后移指针，再将新结点插入到适当位置。
4．设单链表 L 带头结点且非空，指针变量 p 指向 L 中的一个结点，且该结点既不是 L 中的第一个结点，
也不是 L 中的最后一个结点，指针变量 s 指向一个待插入 L 的新结点。试选择合适的语句序列，完成下列
操作。
⑴在 p 所指结点之前插入 s 所指结点；
⑵在 L 中最后一个结点之后插入 s 所指结点；
⑶删除 p 所指结点的直接后继；
⑷删除 L 中第一个结点。
参考答案：
⑴q=L;
while(q->next!=p)q=q->next; //q 指向 p 的直接前驱
s->next=p;
q->next=s;
或者
s->next=p->next; p->next=s;
datatype x;
x=p->data;
p->data=s->data;
s->data=x;
⑵q=L;
while(q->next)q=q->next;
s->next=NULL;
q->next=s;
⑶q=p->next; //q 指向待删结点
p->next=q->next;
free(q);
⑷q=L->next;
L->next=q->next;
free(q);
三、算法设计题
1．顺序结构线性表 LA 与 LB 的结点关键字为整数。LA 与 LB 的元素按非递减有序，线性表空间足够大。
本资料由江南大学研究生 QQ707697898 搜集和整理，其他均属倒卖资料
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
最新资料
2022-2023学年河北省唐山市高三上学期期末数学试题及答案.doc
2022-2023学年河北省张家口市高三上学期期末数学试题及答案.doc
2022-2023学年河北省衡水市高三上学期期末语文试题及答案.doc
2022-2023学年河北省保定市高三上学期期末数学试题及答案.doc
2022-2023学年河北省张家口市高三上学期期末语文试题及答案.doc
2022-2023学年河北省石家庄市高三上学期期末语文试题及答案.doc
2020-2021年四川省凉山州西昌市高一物理上学期期中试卷及答案.doc
2020-2021年四川省遂宁市安居区高一英语上学期期中试卷及答案.doc
2020-2021年四川省西昌市高一英语上学期期中试卷及答案.doc
2021-2022年四川省广安市岳池县高一地理上学期期中试卷及答案.doc
2021-2022年四川省成都市郫都区高一物理上学期期中试卷及答案.doc
2021-2022年四川省广安市岳池县高一物理上学期期中试卷及答案.doc