数据结构试题汇总

您所在位置：数据结构网络教学平台>>> 试卷汇粹>>数据结构试题汇总

一、选择题

第一二章

1．数据结构是一门研究计算机中____对象及其关系的学科。 （1）数值运算 （2）非数值运算 （3）集合 （4）非集合

2．数据结构的定义为(K，R)，其中K是____的集合。 （1）算法 （2）数据元素 （3）数据操作 （4）逻辑结构 3．算法分析的目的是____。 （1） 找出数据结构的合理性 （2） 研究算法中输入和输出的关系 （3） 分析算法的效率以求改进

（4） 分析算法的易懂性和文档性

4．在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行___。 （1）s->link=p;p->next=s;

（2）s->link=p->link;p->link=s; （3）s->link=p->link;p=s;

（4）p->link=s;s->link=p;

5．在循环链表中first为指向链表表头的指针，current为链表当前指针，在循环链表中检测current是否达到链表表尾的语句是____。

（1）current->link=NULL (2)first->link=current

（3）first=current (4)current->link=first

6．从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较____个结点。 （1）n （2）n/2

（3）（n-1）/2 （4）(n+1)/2

7．在一个具有n个结点的有序单链表中，插入一个新结点并仍然有序的时间复杂度为____。 （1）O(1) （2）O(n)

（3）O(n2) （4）O(nlog2n)

8、（ ）是具有相同特性数据元素的集合，是数据的子集。 A 数据符号 B 数据对象 C 数据 D 数据结构

9 与数据元素本身的形式、内容、相对位置、个数无关的是数据的 ( )。 A. 存储结构 B. 逻辑结构 C. 算法 D. 操作 10 用链表表示线性表的优点是 ( )。

A. 便于随机存取 B. 花费的存储空间比顺序表少

C. 便于插入与删除 D. 数据元素的物理顺序与逻辑顺序相同 11、数据结构是研究数据的（ C ）及它们之间的相互联系。 A、理想结构，物理结构 b、理想结构，逻辑结构 C、物理结构，逻辑结构 d、抽象结构，逻辑结构

12、线性表是（ A ）。

a、一个有限系列，可以为空 b、一个有限系列，不能为空 c、一个无限系列，可以为空 d、一个无限系列，不能为空 13、组成数据的基本单位是 （ C ） 。

a、数据项 b、数据类型 c、数据元素 d、数据变量 14、线性表的链接实现有利于（ A ）运算。 A、插入 b、读表元 c、查找 d、定位 15 线性表采用链式存储时，其地址（ d ）

A 必须是连续的 B 部分地址是连续的 C 一定是不连续的 D 连续与否均可以

16、设单链表中指针p指着结点a，若要删除a之后的结点（若存在），则需要修改指针的操作为（ A ）。 A、p->next=p->next->next b、p=p->next C、 p= p->next->next d、p->next=p

17向一个有127个元素原顺序表中插入一个新元素并保存原来顺序不变，平均要移动（ ）个元素。 A、8 B、63.5 C、63 D、7

18．若将两个各有 n个元素的有序表归并成一个有序表，则最少比较次数是（ ）。 A n B 2*n-1 C 2n D n-1

第三章

1．输入序列为（A,B,C,D）不可能的输出有（ ）。

A (A,B,C,D) B (D,C,B,A) C (A,C,D,B) D (C,A,B,D) 2 链式栈与顺序栈相比，一个比较明显的优点是 ( )。

A. 插入操作更加方便 B. 通常不会出现栈满的情况 C. 不会出现栈空的情况 D. 删除操作更加方便 3 在一个顺序存储的循环队列中，队头指针指向队头元素的 ( )。 A. 前一个位置 B. 后一个位置

C. 队头元素位置 D. 队尾元素的前一位置

4、若一个栈的输入序列是1，2，3……n，则输出序列的第一个元素是n，则第i个输出元素是（ ）。

A n-i B i C n-i+1 D n-i-1

5．栈的数组表示中，top为栈顶指针，栈空的条件是____。 （1） top=0 （2）top=maxSize （2） top=maxSize（4）top=-1

6．在数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是____。 （1） front=maxSize （2）(rear+1)%maxSize=front （2） rear=maxSize （4）rear=front 7．栈和队列的共同特点是____。

（1） 都是先进后出 （2）都是先进先出

（2） 只允许在端点处插入和删除 （4）没有共同点

第四章

6．设有串t=’I am a good student ’，那么Substr(t,6,6)=（ ）。 A student B a good s C good D a good

第五章

1设有一个对称矩阵A，采用压缩存储方式，以行序为主序存储a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则 a85地址为（ b ）。

A 23 B 33 C 18 D 40

2已知广义表 LS=(A,(B,C,D),E)运用head和tail函数，取出LS中原子b的运算（ c ）。

A Gethead(Gethead(LS)) B Gettail(Gethead(LS)) C Gethead(Gethead(Gettail(LS))) D Gethead(Gettail(LS))

3．设有一个矩阵A8×6，采用压缩存储方式，以行序为主序存储，a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则 a56地址为（ ）。

A 23 B 30 C 31 D 45

4．一个数组第一个元素的存储地址是100，每个数组元素的长度为2，则第5个元素的地址是____。 （1）110 （2）108 （3）100 （4）120

5 若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个 ( )。 A. 上三角矩阵 B. 稀疏矩阵 C. 对角矩阵 D. 对称矩阵

6设有一个二维数A[m][n],假设A[0][0]存放位置在644(10),A[2][2]存放位置在676(10),每个元素占一个空间，则A[4][5]在（ ）位置，(10)表明用10进数表示。

A、692(10) B、626(10) C、709(10) D、724(10)

7、一个n*n对成矩阵，如果以行或列为主序存入内存，则其容量为（ ）。 A n*n B n*n/2 C n*（n+1）/2 D （n+1）*（n+1）/2 8、已知A=(a,b), B=(A,A),那么GetHead(GetHead(GetTail(B)))=( )。

A (a) B A C a D (A) 第六章

1、若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为(a) A CDBGFEA B CDBFGEA C CDBAGFE D BCDAGFE 2、二叉树第i(i>=1)层上至多有（ C ）结点。

A、２i b、２i c、２i－１ d、２i－１

3、如果结点a有三个兄弟，而且b为a的双亲，则b的度为（ D ）。 A、３ b、 ４ c、５ d、２

4、具有2000个结点的二叉树，其高度至少为（ C ）。

A、９ b、１０ c、１１ d、１２

5、中序遍历一棵二叉排序树所得到的结点序列是键值的（ C ）序列。 A、递增或递减 b、递减 c、递增 d、无序

6．在一棵具有5层的满二叉树中结点总数为 ( )。 A. 31 B. 32 C. 33 D. 16

7含5个结点（元素值均不相同）的二叉搜索树有（ ）种。 A、54 B、42 C、36 D、65

8一个二叉树按顺序方式存储在一个维数组中，如图 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B C D E F G H I J 则结点E在二叉树的第（ ）层。 A、1 B、2 C、3 D、4

9下列存储形式中，( ) 不是树的存储形式。

A. 双亲表示法 B. 左子女右兄弟表示法 C. 广义表表示法 D. 顺序表示法

第七章

2．具有 n 个顶点的有向完全图有（ ）条弧。 A n B n*(n-1) C n*(n+1) D n*n 3 n 个顶点的连通图至少有（ ）条边。 A、n-1 B 、n C、n+1 D、0 第九章

1排序趟数与序列的原始状态(原始排列)有关的排序方法是（ d ）排序方法。 A 插入 B 选择 C 冒泡 D 快速

2．设有100个数据元素，采用折半搜索时，最大比较次数为 ( )。

A. 6 B. 7 C. 8 D. 10

3 对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是 ( )。

A. 直接选择排序 B. 直接插入排序 C. 快速排序 D. 起泡排序

4 对5个不同的数据元素进行直接插入排序，最多需要进行 ( ) 次比较。 A. 8 B. 10 C. 15 D. 25

5一个有序顺表有255个对象，采用顺序搜索法查表，搜索长度为（ ）。 A、128 B、127 C、126 D、255

6在分析析半搜索的性能时时常加入失败结点，即外结点，从而形成扩充的二叉树。若设失败结点?所在层次为,那么搜索失败到达失败点时所做的数据比较次数是（ ）。

A、Li+1 B、Li+2 C、Li-1 D、Li

7设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均探查次数不超过1.5，则散列存储空间应能够至少容纳（ ）个表项。（设搜索成功的平均搜索长度为Snl=(n+1/(1-a))/2,其中a 为装填因子） A、400 B、526 C、624 D、676

9、采用折半查找方法进行查找，数据文件应为（ ），且限于（ ）。 A 有序表 顺序存储结构 B 有序表 链式存储结构 C 随机表 顺序存储结构 D 随机表 链式存储结构

10、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其存放在已排序序列的合适位置，该排序方法称为（ ）排序法。

A 插入 B 选择 C 希尔 D 二路并归

11、就平均查找速度而言，下列几种查找速度从慢至快的关系是（ ） A 顺序 折半 哈西 分块 B 顺序 分块 折半 哈西 C 分块 折半 哈西 顺序 D 顺序 哈西 分块 折半

12．将递归算法转换成对应的非递归算法时，通常需要使用____。 （1）栈 （2）队列 （3）链表 （4）数组

13、在下列算法中，（ ）算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。 A 堆排序 B 冒泡排序 C 插入排序 D 快速排序

二、填空题

第一二章

1、算法是指令的有限序列，其中每一条指令表示一个或多个操作，此外，一个算法还具有五个重要特性，它们分别是 有穷性 、 确定性 、 可行性 、有零或多个输入和有一或多个输出。 2、循环链表的主要优点是 从任何一个结点出发可以遍历所有结点 。 3．为度量一个搜索算法的性能，需要在_____________和空间复杂度方面进行权衡。 4． 算法优劣的五个标准是正确性、可使用性、____、____、____。 5． 下面程序段的时间复杂度是_____。 For(i=0;i

For(j=0;j

6． 用顺序存储方式实现的线形表，称为________。 7． 单链表是______的链接存储表示。

8． 在一个单链表中删除p所指结点的下一个结点时，应执行以下操作： q=p->link;

p->link=______ Delete q

9． 将适当的语句添入单链表搜索函数find中。

templateListNode*List::find(Type value){ current=frist->link while(current!=NULL)

if(current->data=value)break else current=current->link;

return _______ }

10．算法是指令的有限序列，其中每一条指令表示一个或多个操作，此外，一个算法还具有五个重要特性，它们分别是 、 、可行性、有零或多个输入和有一或多个输出。

11．为度量一个搜索算法的性能，需要在时间复杂度和空间复杂度方面进行权衡。

12数据结构是一门研究非数值计算的程序设计问题中计算机的 以及它们之间__________的等等的学科。

第三四章

1设有串t=’I am a student ’，s=’good’，那么Concat(t,s)= ’I am a student good’，Substr(t,8,7)= ‘student’ 。

2在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区应该是一个 队列 结构，其主要特点是 先进先出 。

3对于一个以顺序实现的循环队列Q[0…m-1]，队头、队尾指针分别为f、r，其判空的条件是 r=f ，判满的条件是 (r+1)%m=f 。

4． 设有两个串p和q，求p在q中首次出现的位置的运算称为_________。 5． 栈、队列逻辑上都是________结构。

6． 在具有n个单元的循环队列中，队满时共有_______个元素。

第五章

1． 创建动态数组，可用________声明数组。

2． 广义表((a),a)的表头是_______，表尾是_______。

3． 广义表((a)，((b)，c)，(((d)))的长度是______，深度为_______。

4．设有一个矩阵A8×6，采用压缩存储方式，以行序为主序存储，a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则 a56地址为__________。

第六章

1具有n个叶子的二叉树，每个叶子的权值为wi(1≤i≤n)其中带权路径最小的二叉树被称为 霍夫曼树 。 2若已知一棵二叉树的深度为k(k≥1)，则这棵树至多有 2k-1 个结点，这棵树的第i (1≤i≤k)层上至多有 2i-1 个结点，若这是一棵具有n结点的完全二叉树，则k与n的关系为 k=┗log2n┛+1 。

3．具有64个结点的完全二叉树的深度为7。

4．若已知一棵二叉树的先序序列为 – + a * b – c d / e f，中序序列为a + b * c – d – e / f，则其后序序列为___________。 5已知一棵完全二叉树存放于一个一维数组T[n]中，T[n]中存放的是各结点的值。下面算法的功能是：从T[0]开始顺序读出各结点的值，建立该二叉树的二叉链表表示。

此算法有5处缺失，请根据算法的功能补充之。 (10分)

template istream& operator >> ( istream& in, BinaryTree& t ) { int n;

cout << \in >> n; Type *A = new Type[n+1];

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构试题汇总在线全文阅读。