完整版数据结构含课程设计随堂练习春华南理工大学网络教育答案docWord格式.docx
《完整版数据结构含课程设计随堂练习春华南理工大学网络教育答案docWord格式.docx》由会员分享，可在线阅读，更多相关《完整版数据结构含课程设计随堂练习春华南理工大学网络教育答案docWord格式.docx（65页珍藏版）》请在冰点文库上搜索。
A.算法最终必须由计算机程序实现
B.算法等同于程序
C算法的可行性是指指令不能有二义性D.以上都是错误的
A.B.
C.D.（已提交）
D
8.（单选题）算法的时间复杂度与（
A问题规模B.计算机硬件性能
C编译程序质量D.程序设计语言
）有关.
9.（单选题）算法的主要任务之一是分析（）
A算法是否具有较好的可读姓,
B算法中是否存在语法错误,
C算法的功能是否符合设计要求
D.算法的执行时间和问题规模之间的关系
10.（单选题）A问题规模是C.执行时间与
某算法的时间复杂度为
B执行时间等于
成正比D.问题规模与
O（），表明该算法的（
成正比
）
A.B.C.
D.（已提交）
C
第二章线性表
1.（单选题）线性表是具有
A.关系B字符
C数据元素D.数据项
n个（
）的有限序列
.
2.（单选题）以下关于线性表的叙述中正确的是（）
A.每个元素都有一个前趋元素和一个后继元素B线性表中至少有一个元素
C.线性表中元素的排列次序必须是由小到大或由大到小
D.除第一个和最后一个元素外，每个元素都有一个且仅有一个前趋元素和后
继元素
3.（单选题）以下关于线性表和有序表的叙述中正确的是（）。
A.线性表中的元素不能重复出现
B.有序表属于线性表的存储结构
C.线性表和有序表都属于逻辑结构
D.有序表可以采用顺序表存储，但线性表不能采用顺序表存储
4.（单选题）以下关于顺序表的叙述中正确的是（）。
A.顺序表的优点是存储密度大且插入、删除运算的效率高
B.顺序表属于静态结构
C.顺序表中的所有元素可以连续存放，也可以不连续存放
D.在有n个元素的顺序表中查找逻辑序号为i的元素的算法时间复杂度为
O（n）
5.（单选题）将两个各有n个元素的递增有序顺序表归并成一个有序顺序表，
其最少的比较次数是（）。
A.nB.2n-1C.2nD.n-1
6.（单选题）线性表的链表存储结构和顺序存储结构相比，优点是（）。
A.所有的操作算法实现简单B.便于随机存取
C.便于插入和删除元素D.节省存储空间
7.（单选题）当线性表采用链表存储时，其存放元素的单元地址（）。
A.必须是连续的B.一定是不连续的
C.部分地址必须是连续的D.连续与否均可以
8.（单选题）对于单链表存储结构，以下说法错误的是（）
A.一个结点的数据域用于存放线性表的一个数据元素
B.一个结点的指针域用于指向下一个数据元素的结点
C.单链表必须带有头结点
D.单链表中的所有结点可以连续存放，也可以不连续存放
9.（单选题）链表不具备的特点是（）
A.可以随机访问任一结点B.插入、删除不需要移动元素
C.不必事先估计存储空间D.所需空间与其长度成正比
10.（单选题）以下关于链表的叙述中，不正确的是（）。
A.结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构
B.逻辑上相邻的元素物理上不必相邻
C.可以通过计算直接确定第i个结点的存储地址
D.插入、删除运算操作方便，不必移动结点
11.（单选题）要求线性表的存储空间大小固定，且插入和删除操作不需要移
动元素，采用的存储结构是（）。
A.单链表B.静态链表C.双链表D.顺序表
12.（单选题）不带头结点的单链表head为空的判定条件是（）
A.head==NULLB.head->
next==NULL
C.head->
next==headD.head!
=NULL
13.（单选题）某线性表最常用的操作是在最后一个结点之后插入一个结点或
删除第一个结点，故采用（）存储方式最节省运算时间。
A.单链表B.仅有头结点的单循环链表
C.双链表D.仅有尾指针的单循环链表
14.（单选题）如果含有
点及其前趋结点，则采用（
A.单链表B.双链表
n个元素的某表最常用的操作是取第
）存储方式最节省时间。
C.单循环链表D.顺序表
i（2
≤i≤n）个结
15.（单选题）在一个长度为n（n>
1）的带头结点的单链表head上，另设有尾
指针r（指向尾结点），执行（）操作与链表的长度有关。
A.删除单链表中的第一个元素
B.删除单链表中的尾结点
C.在单链表的第一个元素前插入一个新结点
D.在单链表的最后一个元素后插入一个新结点
16.（单选题）将长度为n的单链表链接到长度为m的单链表之后的算法的时
间复杂度是（）
A.O
（1）B.O（n）C.O（m）D.O（m+n）
17.（单选题）已知一个长度为n的单链表中的所有结点是有序（递增）的，以
下叙述中正确的是（）。
A.插入一个结点使之有序的算法的时间复杂度为O
（1）
B.删除最大值结点使之有序的算法的时间复杂度为O
（1）
C.找最小值结点的算法的时间复杂度为O
（1）
D.以上都不对
18.（单选题）在一个双链表中，删除p结点（非尾结点）的操作是（
A.p->
prior->
next=p->
next;
p->
next->
prior=p->
prior;
B.p->
prior=p;
）。
C.p->
D.p->
19.（单选题）非空循环单链表head的尾结点
next==NULLB.р==NULL
next==headD.p==head
p满足（
20.（单选题）
在长度为
n的（
）上删除第一个元素，其算法的时间复杂度
为O（n）。
A.只有表头指针的不带表头结点的循环单链表
B.只有表尾指针的不带表头结点的循环单链表
C.只有表尾指针的带表头结点的循环单链表
D.只有表头指针的带表头结点的循环单链表
第三章栈、队列
1.（单选题）若元素a、b、c、d、e、f依次进栈，允许进栈、出栈操作交替
进行，但不允许连续3次出栈，则不可能得到的出栈序列是（）。
A.dcebfa
B.cbdaef
C.bcaefd
D.afedcb
2.（单选题）一个栈的进栈序列是a、b、c、d、e，则不可能的栈的输出序列是（）。
A.edcbaB.decbaC.dceabD.abcde
解析：
3.（）已知一个的序列是1,2,3,⋯,n，其出序列的第一个
元素是i（1≤i≤n），第j（1≤j≤n）个出元素是（
A.iB.n-iC.j-i+1D.不确定
答：
D
4.（）已知一个的序列是1,2,3,...,n
p2,...,pn，若p1=n，pi的（）。
A.iB.n-iC.n-i+1D.不确定
，其出序列是
p1,
5.（）有5个元素，其序列是a、b、c、d、e，其出序列是
c、e、d、b、a，的容量至少是（）。
A.1B.2C.3D.4
6.（）表达式（a+a*b）*a+c*b/a的后表达式是（
A.aab*+a*cb*a/+B.aa*b+a*cb*a/+
C.aab*a*cb*+a/+D.aab*+acb*a/+*
7.（）若一个用数
以下元素x的正确操作是（
data[1..n]）。
存，初始指
top
n+1,
A.top++;
data[top]=x;
B.data[top]=x;
top++;
C.top--;
D.data[top]=x;
top--;
8.（单选题）若一个栈用数组data[1..n]存储，初始栈顶指针top为n，则以
下元素x进栈的正确操作是（）。
A.top++;
data[top]=x;
B.data[top]=x;
top++;
D.data[top]=x;
top―
9.（单选题）若一个栈用数组data[1..n]存储，初始栈顶指针top为0，则以
data[top]=xB.data[top]=x;
10.（单选题）若一个栈用数组data1..n存储，初始栈顶指针top为1，则以
datatop=x;
B.datatop=x;
C.top;
D.datatop=x;
11.（单选题）栈和队列的共同点是（）
A.都是先进后出B.都是后进先出
C.只允许在端点处插入和删除元素D.没有共同点
12.（单选题）栈和队列的不同点是（）
A.都是线性表
B.都不是线性表
C.栈只能在一端进行插入、删除操作，而队列在不同端进行插人、删除操作
D.没有不同点
13.（单选题）设循环队列中数组的下标是0~N-1，其队头、队尾指针分别为f和r（f指向队首元素的前一位置，r指向队尾元素），则其元素个数为
（）。
A.r-fB.r-f-1C.（r-f）%N+1
D.（r-f+N）%N
14.（单选题）设循环队列的存储空间为a[0..20]，且当前队头指针和队尾指
针的值分别为8和3，则该队列中元素的个数为（
A.5В.6C.16D.17
15.（单选题）若用一个大小为6的数组来实现循环队列，且当前rear
和
front的值分别为0和3，当从队列中删除一个元素再加人两个元素后，
和front的值分别为（）。
A.1和5B.2和4C.4和2D.5和1
rear
B
第四章串
1.（单选题）串是一种特殊的线性表，其特殊性体现在（
A.可以顺序存储B.数据元素是单个字符
C.可以链接存储D.数据元素可以是多个字符
2.（单选题）A.abcd
以下（
В.321
）是"
abcd321ABCD"
串的子串
АB.C."
abcABC”D."
21AB"
3.（单选题）对于一个链串s，查找第一个元素值为x的算法的时间复杂度为
（）
A.О
（1）B.O（n）
C.O（）D.以上都不对
4.（单选题）对于一个链串s，查找第i个元素的算法的时间复杂度为（）A.O
（1）B.О（n）
5.（单选题）设有两个串p和q，求q在p中首次出现的位置的运算称作（）
A.连接B.模式匹配
C.求子串D.求串长
第五章多维数组、广义表
1.（单选题）设C++二维数组a[6][10]，每个数组元素占用4个存储单元，若
按行优先顺序存放数组元素，
址是（）
a[0][0]的存储地址为860，则
a[3][5]的存储地
A.1000
B.860
C.1140
D.1200
2.（单选题）设C++二维数组a[6][10]，每个数组元素占用4个存储单元，若
地址是（）
a[3][5]
的存储地址为1000，则a[0][0]的存储
A.872
C.868
D.864
3.（单选题）对稀疏矩阵进行压缩存储的目的是（
A.便于进行矩阵运算B.便于输入和输出
C.节省存储空间D.降低运算的时间复杂度
4.（单选题）一个稀疏矩阵经过压缩后，和直接采用二维数组存储相比会失去（）特性。
A.顺序存储B.随机存取C.输入/输出D.以上都不对
5.（单选题）当m行n列的稀疏矩阵采用十字链表表示时，其中单链表的个数为（）
A.m+1B.n+1C.m+n+1D.MAX（m,n）+1
6.（单选题）在将递归算法转换成非递归算法时，通常要借助的数据结构是（）
A.线性表B.栈C．队列D.树
7.（单选题）
А.а
广义表（（a,b）,c,d）
B.bC.（a,b）
的表头是（
D.（c，d）
）.
8.（单选题）
广义表（（a,b）,c,d）B.bC.dD.（c
的表尾是（
，d）
9.（单选题）
广义表（a,b,c,d）
D.（b,c,d）
10.（单选题）广义表（a,b,c,d）的表尾是（
А.аB.bC.dD.（b,c,d）
第六章树、二叉树
1.（单选题）
深度为
5的二叉树至少有（
）个结点
A.5
В.6
C.7
D.31
2.（单选题）
二叉树第i层上最多有（
A.2i
B.2i-1
C.2i-1-1
D.2i-1
3.（单选题）
一个具有1025个结点的二叉树的高h为（
A.11
B.10
C.11~1025D.12-1024
升级会员 