(完整word版)中国石油大学数据结构试题及答案
- 格式：doc
- 大小：118.01 KB
- 文档页数：19
文档推荐
-
【免费下载】中国海洋大学成人高考页数:7
-
中国海洋大学954计算机基础综合考研真题页数:2
-
中国海洋大学数据结构试卷页数:2
下载文档原格式
合集下载
中国石油大学大数据结构精彩试题及问题详解
数据结构试题一、单选题1、在数据结构的讨论中把数据结构从逻辑上分为（）A 内部结构与外部结构B 静态结构与动态结构C 线性结构与非线性结构D 紧凑结构与非紧凑结构。
2、采用线性链表表示一个向量时，要求占用的存储空间地址（）A 必须是连续的B 部分地址必须是连续的C 一定是不连续的D 可连续可不连续3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（）。
A nB n/2C (n-1)/2D (n+1)/24、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（）。
A s→link = p→link;p→link = s;B p→link = s; s→link = q;C p→link = s→link;s→link = p;D q→link = s;s→link = p;5、如果想在4092个数据中只需要选择其中最小的5个，采用（）方法最好。
A 起泡排序B 堆排序C 锦标赛排序D 快速排序6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（）。
A 求子串B 模式匹配C 串替换D 串连接7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。
所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（）。
A 80B 100C 240D 2708、将一个递归算法改为对应的非递归算法时，通常需要使用（）。
A 栈B 队列C 循环队列D 优先队列9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（）。
10、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（）。
A ( front - rear + 1) % mB ( rear - front + 1) % mC ( front - rear + m) % mD ( rear - front + m) % m11、一个数组元素a[i]与（）的表示等价。
中国石油大学期末考试复习题 070109数据结构-18
《数据结构》综合复习资料一、填空题1、数据结构是（）。
2、数据结构的四种基本形式为集合、（）、（）和（）。
3、线性结构的基本特征是:若至少含有一个结点，则除起始结点没有直接前驱外，其他结点有且仅有一个直接（）；除终端结点没有直接（）外，其它结点有且仅有一个直接（）。
4、堆栈的特点是（），队列的特点是（），字符串中的数据元素为（）。
5、字符串s1=“I am a student！”(单词与单词之间一个空格),s2=“student”,则字符串s1的长度为（），串s2是串s1的一个（）串，串s2在s1中的位置为（）。
6、KMP算法的特点：效率较（）；（）回溯，对主串仅需要从头到尾扫描（）遍，可以边读入边匹配。
7、广义表（（a），（（b），c），（（（d））））的长度为（），表头为（），表尾为（）。
8、ADT称为抽象数据类型，它是指（）。
9、求下列程序的时间复杂度，并用大O表示方法表示（）。
for( i=1 ; i<=n ; + + i)for( j=1 ; j<=i; + + j ){ ++x;a[i][j] = x;}10、以下运算实现在链栈上的退栈操作，请在_____处用适当句子予以填充。
int Pop(LstackTp *ls,DataType *x){ LstackTp *p;if(ls!=NULL){ p=ls;*x= ;ls= ;;return(1)；}else return(0);}11、用堆栈求中缀表达式a+b*c/d+e*f的后缀表达式，求出的后缀表达式为（）。
12、C语言中存储数组是采用以（）为主序存储的，在C语言中定义二维数组float a[8][10],每个数据元素占4个字节，则数组共占用（）字节的内存。
若第一个数据元素的存储地址为8000，则a[5][8]的存储地址为（）。
13、含零个字符的串称为（）串，用 表示。
其他串称为（）串。
任何串中所含字符的个数称为该串的（）。
数据结构试卷试题及答案
数据结构试卷试题及答案一、选择题（每题5分，共40分）1. 数据结构是研究数据元素的（）A. 存储结构B. 处理方法C. 逻辑结构D. 所有以上内容答案：D2. 在数据结构中，通常采用（）方式来表示数据元素之间的逻辑关系。
A. 顺序存储结构B. 链式存储结构C. 索引存储结构D. 散列存储结构答案：B3. 下面哪一个不是栈的基本操作？（）A. 入栈B. 出栈C. 判断栈空D. 获取栈顶元素答案：D4. 下面哪一个不是队列的基本操作？（）A. 入队B. 出队C. 判断队列空D. 获取队头元素答案：D5. 下面哪一个不是线性表的特点？（）A. 有且只有一个根节点B. 每个节点最多有一个前驱和一个后继C. 数据元素类型相同D. 数据元素类型可以不同答案：D6. 在下列哪种情况中，使用链式存储结构比顺序存储结构更合适？（）A. 数据元素经常插入和删除B. 数据元素大小不固定C. 数据元素个数不确定D. 所有以上情况答案：D7. 下面哪一个不是树的遍历方式？（）A. 前序遍历B. 中序遍历C. 后序遍历D. 翻转遍历答案：D8. 在下列哪种情况中，使用散列存储结构比其他存储结构更合适？（）A. 数据元素个数较少B. 数据元素查找频繁C. 数据元素插入和删除频繁D. 数据元素大小不固定答案：B二、填空题（每题5分，共30分）9. 栈是一种特殊的线性表，它的插入和删除操作都限定在表的一端进行，这一端称为______。
答案：栈顶10. 队列是一种特殊的线性表，它的插入操作在表的一端进行，这一端称为______，而删除操作在另一端进行，这一端称为______。
答案：队尾、队头11. 二叉树中的节点包括______和______。
答案：根节点、子节点12. 在图的存储结构中，邻接矩阵表示法用______个一维数组来表示图中各个顶点之间的关系。
答案：两个13. 散列存储结构中，关键码到存储地址的映射方法称为______。
国开02272《数据结构》形成性考核(1-4)试题及解答
国开02272《数据结构》形成性考核(1-4)试题及解答1. 选择题问题 1.1:在数据结构中，以下哪种结构是最基本的数据结构？- A. 栈- B. 队列- C. 树- D. 图解答 1.1:正确答案是 A. 栈。
栈是一种后进先出（LIFO）的数据结构，它是通过在一端进行插入和删除操作来实现的。
问题 1.2:在二叉树中，一个节点的最大孩子数目是？- A. 1- B. 2- C. 3- D. 无穷大解答 1.2:正确答案是 B. 2。
在二叉树中，每个节点最多有两个子节点，即左子节点和右子节点。
2. 填空题问题 2.1:在线性表中，如果一个元素在表中的位置是 i，那么它之前有 i - 1 个元素。
_____解答 2.1:正确答案是 "正确"。
在线性表中，如果一个元素在表中的位置是 i，那么它之前有 i - 1 个元素，因为它是从位置 1 开始计数的。
问题2.2:在_____结构中，删除操作的平均时间复杂度是O(n)。
_____解答 2.2:正确答案是 "链表" 和 "O(n)"。
在链表结构中，删除操作的平均时间复杂度是 O(n)，因为需要找到要删除的元素的前一个元素来进行删除操作。
3. 简答题问题 3.1:请解释什么是深度优先搜索（DFS）算法，并给出一个应用场景。
解答 3.1:深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。
它从根节点开始，沿着树的深度遍历树的节点，尽可能深地搜索树的分支。
当节点v的所有边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。
它适用于解决迷宫问题、求解最大子矩阵问题等。
问题 3.2:请解释什么是堆，并给出两种类型的堆。
解答 3.2:堆是一种特殊的完全二叉树，用于实现优先队列。
堆分为两种类型：最大堆和最小堆。
- 最大堆：在一个最大堆中，每个节点的值都大于或等于其子节点的值。
最大堆的根节点具有最大值。
中国石油大学数据结构试题及答案
该数组至少需要的存储字数是（）。
A80B100C240D270
8、将一个递归算法改为对应的非递归算法时，通常需要使用（）。
A栈B队列C循环队列D优先队列
9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（）。
10、在循环队列中用数组A[0..m-1]存放队列元素，其队头和队尾指针分别为
front和rear，则当前队列中的元素个数是（）。
树中的结点数为（85）个。
15、若对一棵二叉树从0开始进行结点编号，并按此编号把它顺序存储到一维数
组中，即编号为0的结点存储到a[0]中，其余类推，则a[i]元素的左子女结点
为（2*i+1），右子女结点为（2*i+2），双亲结点（i>=1）为（「(i-1)/2
Cp->link=s->link;s->link=p;Dp->link=s; s->link=q;
20、设单链表中结点结构为(data,link).若想摘除结点*p的直接后继，则应执
行下列哪一个操作（）
Ap->link=p->link->link;
Bp=p->link; p->link=p->link->link;
（）。
AnBn/2C(n-1)/2D(n+1)/2
4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点
s，则执行（）。
As→link=p→link;p→link=s;
Bp→link=s;s→link=q;
Cp→link=s→link;s→link=p;
Dq→link=s;s→link=p;
Cx=top; top=top->link;Dx=top->data;
A80B100C240D270
8、将一个递归算法改为对应的非递归算法时，通常需要使用（）。
A栈B队列C循环队列D优先队列
9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（）。
10、在循环队列中用数组A[0..m-1]存放队列元素，其队头和队尾指针分别为
front和rear，则当前队列中的元素个数是（）。
树中的结点数为（85）个。
15、若对一棵二叉树从0开始进行结点编号，并按此编号把它顺序存储到一维数
组中，即编号为0的结点存储到a[0]中，其余类推，则a[i]元素的左子女结点
为（2*i+1），右子女结点为（2*i+2），双亲结点（i>=1）为（「(i-1)/2
Cp->link=s->link;s->link=p;Dp->link=s; s->link=q;
20、设单链表中结点结构为(data,link).若想摘除结点*p的直接后继，则应执
行下列哪一个操作（）
Ap->link=p->link->link;
Bp=p->link; p->link=p->link->link;
（）。
AnBn/2C(n-1)/2D(n+1)/2
4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点
s，则执行（）。
As→link=p→link;p→link=s;
Bp→link=s;s→link=q;
Cp→link=s→link;s→link=p;
Dq→link=s;s→link=p;
Cx=top; top=top->link;Dx=top->data;
中石油(华东)《数据结构》2019年秋学期在线作业(三)答案
C.图的深度遍历是一个递归过程
D.图的深度遍历不适用于有向图
答案:D
3.题目和答案如下图所示：
{图}
A.D
B.C
C.B
D.A
答案:A
4.设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有（）个结点。
A.26
B.25
C.13
D.12
答案:B
5.下列哪一个关键码序列不符合堆的定义？（）。
A.(12，22，42，62，68，79，82，84，87，100，102)
A.除留余数法是所有哈希函数中最好的
B.在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可
C.哈希函数构造的越复杂越好，因为这样随机性好，冲突小
D.不存在特别好与坏的哈希函数，要视情况而定
答案:D
11.在二叉树的先序遍历，中序遍历和后序遍历算法中，所有叶子结点的先后顺序（）。
A.k(k-1)/2
B.k-1
C.k
D.1+k(k-1)/2
答案:A
14.设有一个无向图G=（V，E）和G’=（V’，E’）如果G’为G的生成树，则下面不正确的说法是（）。
A.G’为G的连通分量
B.G’为G的极小连通子图且V’=V
C.G’为G的子图
D.G’为G的一个无环子图
答案:A
15.在具有n个结点的二叉树（二叉链表表示）中，值为空的链域数为（）。
B.(102，87，42，79，82，62，68，100，84，12，22)
C.(102，87，100，79，82，62，84，42，22，12，68)
D.(102，100，87，84，82，79，68，62，42，22，12)
答案:B
D.图的深度遍历不适用于有向图
答案:D
3.题目和答案如下图所示：
{图}
A.D
B.C
C.B
D.A
答案:A
4.设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有（）个结点。
A.26
B.25
C.13
D.12
答案:B
5.下列哪一个关键码序列不符合堆的定义？（）。
A.(12，22，42，62，68，79，82，84，87，100，102)
A.除留余数法是所有哈希函数中最好的
B.在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可
C.哈希函数构造的越复杂越好，因为这样随机性好，冲突小
D.不存在特别好与坏的哈希函数，要视情况而定
答案:D
11.在二叉树的先序遍历，中序遍历和后序遍历算法中，所有叶子结点的先后顺序（）。
A.k(k-1)/2
B.k-1
C.k
D.1+k(k-1)/2
答案:A
14.设有一个无向图G=（V，E）和G’=（V’，E’）如果G’为G的生成树，则下面不正确的说法是（）。
A.G’为G的连通分量
B.G’为G的极小连通子图且V’=V
C.G’为G的子图
D.G’为G的一个无环子图
答案:A
15.在具有n个结点的二叉树（二叉链表表示）中，值为空的链域数为（）。
B.(102，87，42，79，82，62，68，100，84，12，22)
C.(102，87，100，79，82，62，84，42，22，12，68)
D.(102，100，87，84，82，79，68，62，42，22，12)
答案:B
2020年中国石油大学北京网络学院 数据结构-第三次在线作业 参考答案
中国石油大学北京网络学院
数据结构-第三次在线作业
参考答案
1.（2.5分） 下面结构中最适于表示稀疏无向图的是（ ）
A、邻接矩阵
B、逆邻接表
C、邻接多重表
D、十字链表
我的答案：C 此题得分：2.5分
2.（2.5分） 下列哪一种图的邻接矩阵是对称矩阵？（ ）
A、有向图
B、无向图
C、AOV网
D、AOE网
我的答案：B 此题得分：2.5分
C、求最短路径
D、求关键路径
我的答案：B 此题得分：2.5分
5.（2.5分） 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )
A、O(n)
B、O(n+e)
C、O(n2）)
D、O(n3）)
我的答案：B 此题得分：2.5分
6.（2.5分） 求解最短路径的Floyd算法的时间复杂度为( )。
B、任何一个关键活动提前完成，那么整个工程将会提前完成
C、所有的关键活动提前完成，那么整个工程将会提前完成
D、某些关键活动提前完成，那么整个工程将会提前完成
我的答案：B 此题得分：2.5分
12.（2.5分） 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( )
A、（N+1）/2
C、数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
D、数据分成若干块，每块（除最后一块外）中数据个数需相同
我的答案：B 此题得分：2.5分
16.（2.5分） 既希望较快的查找又便于线性表动态变化的查找方法是 ( )
A、顺序查找
B、折半查找
C、索引顺序查找
D、哈希法查找
我的答案：C 此题得分：2.5分
数据结构-第三次在线作业
参考答案
1.（2.5分） 下面结构中最适于表示稀疏无向图的是（ ）
A、邻接矩阵
B、逆邻接表
C、邻接多重表
D、十字链表
我的答案：C 此题得分：2.5分
2.（2.5分） 下列哪一种图的邻接矩阵是对称矩阵？（ ）
A、有向图
B、无向图
C、AOV网
D、AOE网
我的答案：B 此题得分：2.5分
C、求最短路径
D、求关键路径
我的答案：B 此题得分：2.5分
5.（2.5分） 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )
A、O(n)
B、O(n+e)
C、O(n2）)
D、O(n3）)
我的答案：B 此题得分：2.5分
6.（2.5分） 求解最短路径的Floyd算法的时间复杂度为( )。
B、任何一个关键活动提前完成，那么整个工程将会提前完成
C、所有的关键活动提前完成，那么整个工程将会提前完成
D、某些关键活动提前完成，那么整个工程将会提前完成
我的答案：B 此题得分：2.5分
12.（2.5分） 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( )
A、（N+1）/2
C、数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
D、数据分成若干块，每块（除最后一块外）中数据个数需相同
我的答案：B 此题得分：2.5分
16.（2.5分） 既希望较快的查找又便于线性表动态变化的查找方法是 ( )
A、顺序查找
B、折半查找
C、索引顺序查找
D、哈希法查找
我的答案：C 此题得分：2.5分
中石油(华东)《数据结构》2019年秋学期在线作业(二)答案
D.base+[(i-1)*m+(j-1)]*w
答案:C
20.链表不具有的特点是（）。
A.插入、删除不需要移动元素
B.所需空间与线性长度成正比
C.可随机访问任一元素
D.不必事先估计存储空间
答案:C
《数据结构》2019年秋学期在线作业（二）
试卷总分:100得分:100
一、单选题(共20道试题,共100分)
1.用堆栈求算术表达式a+b*(c-d)-e/f的后缀表达式为（）。
A.abcdef-*+/-
B.abcd-*+ef/-
C.abc-d*ef/+-
D.a+b*(c-d)-e/f
答案:D
2.以下判断不正确的是（）。
A.顺序存储的线性表可随机存取。
B.顺序存储方式的优点是存储密度大，插入、删除操效率高。
C.在线性表的链式存储结构中，逻辑上相邻的数据元素在物理位置上不一定相邻。
D.同一线性表中的数据元素应具有相同的特性。
答案:B
3.在顺序存储（空间大小为m）的循环队列q中，下列判满正确的是（）。
A.q.rear % m = 0 ;
A.SA+225
B.SA+222
C.SA+180
D.SA+141
答案:B
19.设A是一个m*n阶矩阵，A按列序存储在一组连续的存储单元中，每个元素占用w个存储单元，若A[1,1]的存储地址为base，则A[i,j]的存储地址为（）。
A.base+（j*m+i）*w
B.base+（j*m+i）*w
C.base+[(j-1)*m+(i-1)]*w
答案:C
20.链表不具有的特点是（）。
A.插入、删除不需要移动元素
B.所需空间与线性长度成正比
C.可随机访问任一元素
D.不必事先估计存储空间
答案:C
《数据结构》2019年秋学期在线作业（二）
试卷总分:100得分:100
一、单选题(共20道试题,共100分)
1.用堆栈求算术表达式a+b*(c-d)-e/f的后缀表达式为（）。
A.abcdef-*+/-
B.abcd-*+ef/-
C.abc-d*ef/+-
D.a+b*(c-d)-e/f
答案:D
2.以下判断不正确的是（）。
A.顺序存储的线性表可随机存取。
B.顺序存储方式的优点是存储密度大，插入、删除操效率高。
C.在线性表的链式存储结构中，逻辑上相邻的数据元素在物理位置上不一定相邻。
D.同一线性表中的数据元素应具有相同的特性。
答案:B
3.在顺序存储（空间大小为m）的循环队列q中，下列判满正确的是（）。
A.q.rear % m = 0 ;
A.SA+225
B.SA+222
C.SA+180
D.SA+141
答案:B
19.设A是一个m*n阶矩阵，A按列序存储在一组连续的存储单元中，每个元素占用w个存储单元，若A[1,1]的存储地址为base，则A[i,j]的存储地址为（）。
A.base+（j*m+i）*w
B.base+（j*m+i）*w
C.base+[(j-1)*m+(i-1)]*w
中国石油大学（北京）《858数据结构》历年考研真题汇编
目 录2000年中国石油大学（北京）数据结构考研真题2001年中国石油大学（北京）数据结构考研真题2002年中国石油大学（北京）数据结构考研真题2003年中国石油大学（北京）数据结构考研真题2004年中国石油大学（北京）数据结构考研真题2000年中国石油大学（北京）数据结构考研真题石油大学（北京）二000年研究生入学试题糙明数据结构共2页适用专业：计算机应用-、求解下^问题(7X6分〉1、判别以下序列是否为堆(小顶堆或大顶堆).如果不是,则把它调整为堆(要求记录交换次数最少).⑴<100,86,48,73,35,39,42,57,/66,21)<2)《05,56.20,23.40.38,29,61,35,76.28,100)(3)(103,97,56,38,66,23,42,12,30,52,06,的)2、宿线性浪进行二分法粉索的先决编中是什么？简述二分法检索的基本汶程及草平均检索长度，3、按照四则运算加、减、m,除和慕运算（t）优先关系的惯例，即出对下列算术衰达式求值时操作数栈和运算待栈的变化过程：A-BXC/D+E tF4、己知下列各始为广义表的存赭结构图，其结点的结构为,Uj数据结构的主要区别是什么，（2）分配算法的主要区别是什么？⑶回收算法的主要区别是什么？6、画出与下列己知序列时应的森林F：森林的先序次序访问序列为：ABCDEFGHIJKL森林的中序次序访问序列为：CBEFDGAJIKLH7、画出上面有向图的十字链袤.I''>■**，-*二、写算法（2X12分）1、从循环双向链表中新除第i<i^l）个结点，试写出其算法.2、已知一棵以链表存储的二叉材，如欲姚结点起，由上而下，逐孱打印各结瘁的数据，同一是结点宜左而右打印，试写出其算法.（要求所用变量必须注解）】*l,t土|>”.1三，分析与推导L一棵深度为H的满k义村有如下性质：第H层上•钓结点都是叶于结点,其余各层上每个嬉点都有! k棵非空亍树.如果按层次倾序从1开殖对全部结点编号，网（12分）（D各层的结点数目是多少？•⑵编号为p的结点的父结点（若存在〉的编号是多少？⑶编号为P的绪点的第i个儿子结点（若存在）的编号是多少？⑴漏号为p的结点宥兄弟的条件是什么？其兄弟的编号是什么？2、.画出下图所示的无向图的邻接多重表，使得其中母个无向边绡点宇曾一个顶点号小于第二个顶点号，旦每个顶点的各邻接边的链接顾序为它所邻接的顶点序号或'到大莉前序.列出深度优先和广度优先搜索遍历该图所得顶*律列和边序列.（12分）3、什么姑平衡二又树|?平衡二叉树有什么优点，用在什么堕方？试推导含12个结点的平衡二叉树%"的最大深陌,芥皿出一棵这样的平衡二又树.no分｝2001年中国石油大学（北京）数据结构考研真题石油大学（北京）2001年研究生入学试题考试科目：数据结构共2页适用专业：计算机应用求解下列间题'（8X6分）1.画出广义表（a.（（）,b）,（（（e））））的存储结构图.2.若二棵树中有度为1至m的结点数分别为m,任，…，n.（&衷示及数为m的结点个数）*谄推导也该树中有多少个叶结点n“的公式.3.请给出下而稀疏炬阵的漆——列表示法（即十字镂表法）存储结构.勺200。
石油大学在线作业 数据结构1、2、3
×第一次在线作业单选题 (共40道题)展开收起1.（2.5分）程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF A[j]> A[j+1] THEN A[j]与A[j+1]对换；其中 n为正整数，则最后一行的语句频度在最坏情况下是（）•A、O（n）•B、O(nlogn)•C、O(n3)•D、O(n2)我的答案：D此题得分：2.5分2.（2.5分）若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1< =i< =n+1)。
•A、O(0)•B、O(1)•C、O(n)•D、O(n2)我的答案：C此题得分：2.5分3.（2.5分）算法的计算量的大小称为计算的•A、效率•B、复杂性•C、现实性•D、难度我的答案：B此题得分：2.5分4.（2.5分）算法的时间复杂度取决于•A、问题的规模•B、待处理数据的初态•C、A和B我的答案：C此题得分：2.5分5.（2.5分）下面关于算法说法错误的是•A、算法最终必须由计算机程序实现•B、为解决某问题的算法同为该问题编写的程序含义是相同的•C、算法的可行性是指指令不能有二义性•D、以上几个都是错误的我的答案：D此题得分：2.5分6.（2.5分）下面说法错误的是•A、算法原地工作的含义是指不需要任何额外的辅助空间•B、在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法•C、所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界•D、同一个算法，实现语言的级别越高，执行效率就不定我的答案：A此题得分：2.5分7.（2.5分）从逻辑上可以把数据结构分为（）两大类•A、动态结构、静态结构•B、顺序结构、链式结构•C、线性结构、非线性结构•D、初等结构、构造型结构我的答案：C此题得分：2.5分8.（2.5分）以下数据结构中，哪一个是线性结构（）•A、广义表•B、二叉树•C、稀疏矩阵•D、串我的答案：D此题得分：2.5分9.（2.5分）以下那一个术语与数据的存储结构无关？•A、栈•B、哈希表•C、线索树•D、双向链表我的答案：A此题得分：2.5分10.（2.5分）在下面的程序段中，对x的赋值语句的频度为（） FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1;•A、O(2n)•B、O(n)•C、O(n2)•D、O(log2n)我的答案：C此题得分：2.5分11.（2.5分）以下数据结构中，（）是非线性数据结构•A、树•B、字符串•C、队•D、栈我的答案：A此题得分：2.5分12.（2.5分）下列数据中，（）是非线性数据结构•A、栈•B、队列•C、完全二叉树•D、堆我的答案：C此题得分：2.5分13.（2.5分）下面关于线性表的叙述中，错误的是哪一个？（）•A、线性表采用顺序存储，必须占用一片连续的存储单元。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
数据结构试题一、单选题1、在数据结构的讨论中把数据结构从逻辑上分为（）A 内部结构与外部结构B 静态结构与动态结构C 线性结构与非线性结构D 紧凑结构与非紧凑结构。
2、采用线性链表表示一个向量时，要求占用的存储空间地址（）A 必须是连续的B 部分地址必须是连续的C 一定是不连续的D 可连续可不连续3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（）。
A nB n/2C (n-1)/2D (n+1)/24、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（）。
A s→link = p→link;p→link = s;B p→link = s; s→link = q;C p→link = s→link;s→link = p;D q→link = s;s→link = p;5、如果想在4092个数据中只需要选择其中最小的5个，采用（）方法最好。
A 起泡排序B 堆排序C 锦标赛排序D 快速排序6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（）。
A 求子串B 模式匹配C 串替换D 串连接7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。
所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（）。
A 80B 100C 240D 2708、将一个递归算法改为对应的非递归算法时，通常需要使用（）。
A 栈B 队列C 循环队列D 优先队列9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（）。
10、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（）。
A ( front - rear + 1) % mB ( rear - front + 1) % mC ( front - rear + m) % mD ( rear - front + m) % m11、一个数组元素a[i]与（）的表示等价。
A *（a+i）B a+iC *a+iD &a+i12、若需要利用形参直接访问实参，则应把形参变量说明为（）参数。
A 指针B 引用C 值D 变量13、下面程序段的时间复杂度为（）for (int i=0;i<m;i++)for (int j=0;j<n;j++)a[i][j]=i*j;A O(m2)B O(n2)C O(m*n)D O(m+n)14、下面程序段的时间复杂度为（）int f(unsigned int n) {if(n= =0 || n= =1) return 1;else return n*f(n-1);}A O(1)B O(n)C O(n2)D O(n!)15、线性表若是采用链式存储结构时，要求内存中可用存储单元的地址( )。
A 必须是连续的B 部分地址必须是连续的C 一定是不连续的D 连续或不连续都可以16、数据结构的定义为(D，S)，其中D是( )的集合。
A 算法 B数据元素 C 数据操作 D 逻辑结构17、算法分析的目的是( )。
A找出数据结构的合理性B研究算法中输入和输出的关系C分析算法的效率以求改进D分析算法的易懂性和文档性18、在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行( )。
A s->link=p;p->link=s;B s->link=p->link;p->link=s;C s->link=p->link;p=s;D p->link=s;s->link=p;19、设单链表中结点结构为(data,link).已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作（）A s->link=p->link; p->link=s; B q->link=s; s->link=pC p->link=s->link; s->link=p;D p->link=s; s->link=q;20、设单链表中结点结构为(data,link).若想摘除结点*p的直接后继，则应执行下列哪一个操作（）A p->link=p->link->link;B p=p->link; p->link=p->link->link;C p->link=p->link;D p=p->link->link;21、设单循环链表中结点的结构为（data,link）,且rear是指向非空的带表头结点的单循环链表的尾结点的指针。
若想删除链表第一个结点，则应执行下列哪一个操作（ D ）A s=rear; rear=rear->link; delete s;B rear=rear->link; delete rear;C rear=rear->link->link; delete rear;D s=rear->link->link; rear->link->link=s->link; delete s;s为第一个结点硫22、设单循环链表中结点的结构为（data,link）,且first为指向链表表头的指针，current为链表当前指针，在循环链表中检测current是否达到链表表尾的语句是( D )。
A current->link =nullB first->link=currentC first=currentD current->link=first23、一个栈的入栈序列为a，b，c，则出栈序列不可能的是( C )。
A c,b,aB b,a,cC c,a,bD a,c,b24、栈的数组表示中，top为栈顶指针，栈空的条件是( A )。
A top=0B top=maxSizeC top=maxSizeD top=-125、栈和队列的共同特点是( C )。
A 都是先进后出B 都是先进先出C只允许在端点处插入和删除 D 没有共同点26、假定一个顺序存储的循环队列的队头和队尾指针分别为f和r ,则判断队空的条件为( D ).A f+1= =rB r+1= =fC f= =0D f= =r27、当利用大小为n 的数组顺序存储一个队列时，该队列的最大长度为（ B ）A n-2B n-1C nD n+128、当利用大小为n 的数组顺序存储一个栈时，假定用top= =n 表示栈空，则向这个栈插入一个元素时，首先应执行（）语句修改top指针。
A top++;B top--;C top=0;D top;29、设链式栈中结点的结构为（data, link）,且top是指向栈顶的指针。
若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行下列（ A ）操作。
A x=top->data; top=top->link;B top=top->link; x=top->data;C x=top; top=top->link;D x=top->data;30、设循环队列的结构是：const int Maxsize=100;typedef int Data Type;typedef struct {Data Type data[Maxsize];Int front, rear;} Queue;若有一个Queue类型的队列Q，试问判断队列满的条件应是下列哪一个语句（ D ）A Q.front= = Q.rear;B Q.front - Q.rear= = Maxsize;C Q.front + Q.rear= = Maxsize;D Q.front= = (Q.rear+1)% Maxsize;31、设有一个递归算法如下：int fact (int n ){ if (n<=0) return 1;else return n*fact(n-1);}下面正确的叙述是（ B ）A 计算fact(n) 需要执行n次递归B fact(7)=5040C 此递归算法最多只能计算到fact(8)D 以上结论都不对32、设有一个递归算法如下int x (int n) {if (n<=3) return 1;else return x(n-2)+x(n-4)+1;}试问计算 x(x(8))时需要计算（ D ）次x函数。
A 8 次B 9 次C 16 次D 18次33、设有广义表D(a,b,D),其长度为（ B ），深度为（ A ）A ∞B 3C 2D 534、广义表A(a),则表尾为（ C ）A aB (( ) )C 空表D （a）35、下列广义表是线性表的有（ C ）A E（a,(b,c)）B E(a,E)C E (a,b) DE(a,L( ) )36、递归表、再入表、纯表、线性表之间的关系为（ C ）A 再入表>递归表>纯表>线性表B 递归表>线性表>再入表>纯表C 递归表>再入表>纯表>线性表 D递归表>再入表>线性表>纯表37、某二叉树的前序和后序序列正好相反，则该二叉树一定是（ B ）的二叉树。
A 空或只有一个结点B 高度等于其结点数C 任一结点无左孩子D 任一结点无右孩子38、对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点为n2.,则( A )A n0= n2+1 B n2= n+1 C n0=2n2+1 D n2=2n+139、由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（B ）A 24B 73C 48D 5340、已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为da1,则第I 个结点的地址为（ A ）。
A da1+(I-1)*mB da1+I*mC da1-I*mD da1+(I+1)*m41、34 具有35个结点的完全二叉树的深度为( A )A 5B 6C 7D 842、对线性表进行折半搜索时，要求线性表必须（ C ）A 以链接方式存储且结点按关键码有序排列B 以数组方式存储C 以数组方式存储且结点按关键码有序排列 D以链接方式存储43、顺序搜索算法适合于存储结构为（ B ）的线性表。
A 散列存储B 顺序存储或链接存储C 压缩存储D 索引存储44、采用折半搜索算法搜索长度为n的有序表时，元素的平均搜索长度为（ C ）A O（n2）B O（n log2n） C O（log2n） D O（n）45、对于一个具有n个顶点和e条边的无向图，进行拓扑排序时，总的时间为( A )A nB n+1C n-1D n+e46、判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（C ）。