2024秋最新国家开放大学国开电大机考期末数据结构（本）试卷机考期末试卷参考试题

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

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

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

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

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

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

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

一 、单选题

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

A. top++

B. top--

C. top=0

D. ！top

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

2. 空串与空格串（ ）。

A. 相同

B. 不相同

C. 可能相同

D. 无法确定

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

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

A. a

B. (( ))

C. ( )

D. (a)

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

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

A. 必须判断栈是否满

B. 判断栈元素类型

C. 必须判断栈是否空

D. 对栈不作任何判断

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

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

A. n

B. e

C. 2n

D. 2e

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

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

A. 一对一

B. 一对多

C. 多对一

D. 多对多

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

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

A. acbed

B. decab

C. deabc

D. cedba

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

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

A. “BEIJING”

B. “BEI”

C. “BEFANG”

D. “BEFI”

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

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

A. 线性表至少要求一个元素

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

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

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

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

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

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

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

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

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

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

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

A. 1

B. 0

C. 2

D. -1

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

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

A. 都是线性表

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

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

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

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

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

A. O(n2)

B. O(nlog2n)

C. O(n)

D. O(log2n)

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

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

A. top==0

B. top!=0

C. top==n-1

D. top=-1

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

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

A. head = p;

B. p=head;

C. C. p->next = NULL;

D. p->next=head;

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

二 、判断题

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

A. √

B. ×

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

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

A. √

B. ×

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

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

A. √

B. ×

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

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

A. √

B. ×

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

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

A. √

B. ×

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

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

A. √

B. ×

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

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

A. √

B. ×

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

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

A. √

B. ×

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

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

A. √

B. ×

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

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

A. √

B. ×

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

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

A. √

B. ×

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

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

A. √

B. ×

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

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

A. √

B. ×

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

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

A. √

B. ×

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

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

A. √

B. ×

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

三 、综合题

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); }

A. quicksort(a,start,i-1);

B. quicksort(a,start,i+1);

C. quicksort(a,start,j-1);

D. 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+!; } }

A. dep1>dep2

B. dep1<dep2

C. BT->left==NULL

D. 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; }

A. return 0;

B. return -1;

C. return 1;

D. return i;

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

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

A. 3.5

B. 3

C. 19/6

D. 14/6

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

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

A. p->next=q

B. p->next=s

C. q->next=s

D. q->next=p

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

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