20230506数据结构（本）试卷-06

20230506数据结构（本）试卷-06

20230506数据结构（本）试卷-06

关注公众号【飞鸟搜题】，回复【试题】获取试卷答案

文档说明:本人针对该科精心汇总了历年题库及答案，形成一个完整的题库，并且每年都在更新。该题库对考生的复习、作业和考试起着非常重要的作用，会给您节省大量的时间。做考题时，利用本文档中的查找工具，把考题中的关键字输到查找工具的查找内容框内，就可迅速查找到该题答案。本文库还有期末考核试题、其他网核及教学考一体化、一网一平台复习试题与答案，敬请查看。

课程题目试题是随机的，请按题目关键词查找（或按Ctrl+F输入题目中的关键词，尽量不要输入整个题目，不要复制空格，连续的几个字就行）

本文由【飞鸟搜题】微信公众号提供，禁止复制盗取，违者必究

本文由【飞鸟搜题】微信公众号提供，禁止复制盗取，违者必究

本文由【飞鸟搜题】微信公众号提供，禁止复制盗取，违者必究

一 、单选题

1. 当利用大小为N的数组顺序存储一个栈时，假定用top==-1表示栈空，则入栈应该执行（）语句修改top指针。

top++

top--

top=0

！top

答案：A- 关注公众号【飞鸟搜题】查看答案

2. 空串与空格串（ ）。

相同

不相同

可能相同

无法确定

答案：B- 关注公众号【飞鸟搜题】查看答案

3. 设有一个广义表A (a)，其表尾为（ ）。

a

(( ))

( )

(a)

答案：C- 关注公众号【飞鸟搜题】查看答案

4. 如果以链表作为栈的存储结构，则退栈操作时（ ）。

必须判断栈是否满

判断栈元素类型

必须判断栈是否空

对栈不作任何判断

答案：C- 关注公众号【飞鸟搜题】查看答案

5. 对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（ ）。

n

e

2n

2e

答案：关注公众号【飞鸟搜题】查看答案

6. 线性结构中数据元素之间的关系是（ ）

一对一

一对多

多对一

多对多

答案：关注公众号【飞鸟搜题】查看答案

7. 已知某二叉树的后续遍历序列是dabec，中序遍历是debac，则它的先序遍历序列是（ ）。

acbed

decab

deabc

cedba

答案：关注公众号【飞鸟搜题】查看答案

8. 如果进行串的比较，下列哪个串最大？（ ）

“BEIJING”

“BEI”

“BEFANG”

“BEFI”

答案：关注公众号【飞鸟搜题】查看答案

9. 有关线性表的正确说法是（ ）。

线性表至少要求一个元素

每个元素都有一个直接前驱和一个直接后继

表中的元素必须按由小到大或由大到下排序

除了一个和最后一个元素外，其余元素都有一个且仅有一个直接前驱和一个直接后继

答案：关注公众号【飞鸟搜题】查看答案

10. 就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是（ ）。

堆排序> 快速排序> 归并排序

堆排序< 快速排序< 归并排序

堆排序< 归并排序< 快速排序

堆排序> 归并排序> 快速排序

答案：关注公众号【飞鸟搜题】查看答案

11. 树中所有结点的度等于所有结点数加（ ）。

1

0

2

-1

答案：关注公众号【飞鸟搜题】查看答案

12. 关于栈和队列的说法中，错误的是（）。

都是线性表

基本运算中都不包含排序运算

只能在端点插入和删除操作

栈是先进先出，队列是后进先出

答案：关注公众号【飞鸟搜题】查看答案

13. 采用折半查找方法查找长度为n的线性表时，其算法的时间复杂度为（ ）。

O(n2)

O(nlog2n)

O(n)

O(log2n)

答案：关注公众号【飞鸟搜题】查看答案

14. 判断向上增长型的顺序栈空的条件是（）。

top==0

top!=0

top==n-1

top=-1

答案：关注公众号【飞鸟搜题】查看答案

15. 设头指针为head的非空的单向链表，指针p指向尾结点,则通过以下操作（ )可使其成为单向循环链表。

head = p;

p=head;

C. p->next = NULL;

p->next=head;

答案：关注公众号【飞鸟搜题】查看答案

二 、判断题

1. 采用分块查找时，数据的组织方式为把数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引表。

√

×

答案：关注公众号【飞鸟搜题】查看答案

2. 二叉树的遍历就是按照一定次序访问树中所有结点，并且每个结点的值仅被访问一次的过程。

√

×

答案：关注公众号【飞鸟搜题】查看答案

3. 线性表用顺序方式存储可以随机访问。

√

×

答案：关注公众号【飞鸟搜题】查看答案

4. 递归的算法简单、易懂、容易编写，而且执行效率也高。

√

×

答案：关注公众号【飞鸟搜题】查看答案

5. 设有一个单向循环链表，结点的指针域为next，头指针为head，指针p指向表中某结点，若逻辑表达式p->next==head;的结果为真，则p所指结点为尾结点。

√

×

答案：关注公众号【飞鸟搜题】查看答案

6. 对于一棵深度为h，度为3的树最多有（3h-1）/2个结点。

√

×

答案：关注公众号【飞鸟搜题】查看答案

7. 字符串属于线性的数据结构

√

×

答案：关注公众号【飞鸟搜题】查看答案

8. 数据项是数据的最小单位。

√

×

答案：关注公众号【飞鸟搜题】查看答案

9. AOV网是一个带权的有向图。

√

×

答案：关注公众号【飞鸟搜题】查看答案

10. 在归并排序中，在第3趟归并中，是把长度为4的有序表归并为长度为8的有序表。

√

×

答案：关注公众号【飞鸟搜题】查看答案

11. 在一个顺序存储的循环队列中, 队头指针指向队头元素的后一个位置。

√

×

答案：关注公众号【飞鸟搜题】查看答案

12. 使用三元组表示稀疏矩阵中的非零元素能节省存储空间。

√

×

答案：关注公众号【飞鸟搜题】查看答案

13. 在一个查找表中，能够唯一地确定一个记录的关键字称为主关键字。

√

×

答案：关注公众号【飞鸟搜题】查看答案

14. 深度为k的完全二叉树至少有2k-1个结点。

√

×

答案：关注公众号【飞鸟搜题】查看答案

15. 一个有向图的邻接表和逆邻接表中的节点个数一定相等。

√

×

答案：关注公众号【飞鸟搜题】查看答案

三 、综合题

1. 以下程序是快速排序的算法，完成程序中空格部分。 设待排序的记录序列存放在a[start],…a[end]中，按记录的关键字进行快速排序，先进行一次划分，再分别进行递归调用。 void quicksort(NODE a[],int start,int end) { int i,j; NODE mid; if (start>=end ) return; i=start; j=end; mid=a[i]; while (i<j) { while(i<j && a[j].key>mid.key) j--; if(i<j) { a[i]=a[j]; i++; } while(i<j && a[i].key<=mid.key) i++; if(i<j) { a[j]=a[i]; j--; } } a[i]=mid; ____________________ quicksort(a,i+1,end); }

quicksort(a,start,i-1);

quicksort(a,start,i+1);

quicksort(a,start,j-1);

quicksort(a,start,j+1);

答案：关注公众号【飞鸟搜题】查看答案

2. 以下为求二叉树深度的算法，完成程序中空格部分。 int BTreeDepth(BTreeNode* BT) { if (BT==NULL) return 0; else { int dep1=BTreeDepth(BT->left); /* 计算左子树的深度 */ int dep2=BTreeDepth(BT->right); /* 计算右子树的深度 */ if (________) return dep1+1; else return dep2+!; } }

dep1>dep2

dep1<dep2

BT->left==NULL

BT->right==NULL

答案：关注公众号【飞鸟搜题】查看答案

3. 在下面空格处填写一条语句，以使下面的串比较算法完整。 int strcmp(char *s1,char *s2) { int i; for(i=0;s1[i]!='\0'&& s2[i]!='\0';i++) if(s1[i]>s2[i]) return 1; else if(s1[i]<s2[i]) return -1; if(s1[i]=='\0'&& s2[i]=='\0') _________ else if(s1[i]!='\0') return 1; else return -1; }

return 0;

return -1;

return 1;

return i;

答案：关注公众号【飞鸟搜题】查看答案

4. 设查找表为(16,15,20,53,64,7)，用冒泡法对该表进行排序，在排序后的有序表的基础上进行折半查找，在等概率条件下,成功查找的平均查找长度为（ ）。

3.5

3

19/6

14/6

答案：关注公众号【飞鸟搜题】查看答案

5. 设有一个头指针为head的不带头结点单向链表中（结点类型为NODE），p为指向该链表中某个结点的指针。以下程序段为插入一个指针为s的结点，使它成为p结点的直接前驱，请把合适选项填写到空行处。 NODE *q; q=head; while(q->next!=p) q=q->next; s->next=p; ________;

p->next=q

p->next=s

q->next=s

q->next=p

答案：关注公众号【飞鸟搜题】查看答案

关注公众号【飞鸟搜题】，回复【试题】获取试卷答案