2018年韩山师范学院本科插班生考试试题《数据结构》A试卷

（A卷）第 1 页 共 8 页

韩山师范学院2018年本科插班生考试试卷

计算机科学与技术 专业 数据结构 试卷（A卷）

题号 得分

一 二 三 四 五 六 总分 评卷人 得分 评卷人 一、单项选择题（每题2分，共30分）

1. 数据的最小单位是（ B ）。 A. 数据元素 B.数据项 是( C )。

A. B C A B.C B A C. C A B D. A B C 3．程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的时间复杂度为（ A ）。 A. O(n)

B. O(nlog2n)

C.O(n2)

D.O(n3/2)

4．一个非空广义表的表头（ D ）。

A.不可能是子表 B.只能是子表 C.只能是原子 D.可以是子表或原子

5．设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ D ）。

A. R-F B.F-R C. (F-R+M)％M D. (R-F+M)％M

6．设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（ C ）。 A. q=p->next；p->next=q->next；free(q)； B. q=p->next；p->data=q->data；free(q)；

C. q=p->next；p->data=q->data；p->next=q->next；free(q)； D. q=p->next；q->data=p->data；p->next=q->next；free(q)；

7．设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示（ B ）。

C.数据类型 D. 数据变量

2. 一个栈的输入序列为A B C，则下列序列中不可能是栈的输出序列的

（A卷）第 2 页 共 8 页

A. 696 B. 692 C.688 D. 678

//c,对的.676+(676-644)/2

A[2][2]与A[0][0] 相差两排零2个元素 A[3][3]与A[2][2] 相差一排零1个元素 因为元素的地址是连续的

所以A[2][2]与A[0][0] 的地址差是A[3][3]与A[2][2]地址差的2倍 A[2][2]与A[0][0] 的地址差是676-644 A[3][3]与A[2][2]地址差是(676-644)/2 所以A[3][3]的地址是676+(676-644)/2

8．设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为( D )。 A. 15，10，14，18，20，36，40，21 B.10，15，14，18，20，40，36，21 C. 10，15，14，20，18，40，36，2l

D. 10，15，14，18，20，36，40，21

9．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（ C ）。

A.9 A. 树 A.4

B. 10 C.11

B. 栈 B. 5

D. 12 C. 队列 C. 6

D. 线性表 D. 7

10．数组的逻辑结构不同于下列（ A ）的逻辑结构。

11．根据二叉树的定义可知二叉树共有（ B ）种不同的形态。 12．设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（ A ）。

A.head==0 B. head->next==0 C. head->next==head //

D.head!=0

注意：不论是带头结点的链表还是不带头结点的链表，头指针head都指向链表中的第一个结点。如果该链表有头结点，则头指针head指向头结点，如果没有头结点，则头指针head指向链表的第一个节点。

1 带头结点的单链表中头指针head指向头结点，头结点的值域不含任何信息，从头结点的后继结点开始存储信息。头指针head始终不等于NULL，head->next等于NULL的时候链表为空。

2 不带头结点的单链表中的头指针head直接指向开始结点，当head等于NULL的时候链表为空。

头结点的存在，使得空链表与非空链表的处理变得一直，也方便了对链表的开始结点插入或删除操作。

（A卷）第 3 页 共 8 页

13．设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的

入度为（ B ）。 A.第i行非0元素的个数之和 C.第i行0元素的个数之和 条边。 A. 2n

B. 2n-1

C. n-1

D. n

15.由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ D ）

A. 24 B. 48 C. 53 D. 71

B. 第i列非0元素的个数之和 D. 第i列0元素的个数之和

14．设无向图G中有n个顶点，则该无向图的最小生成树上有（C ）

得分 评卷人 二、填空题（每空2分，共20分）

1．数据的物理结构主要包括_顺序储存结构_和___链式存储结构_两种情况。

2.设某棵二叉树中度数为0的结点数为N0，度数为1的结点数为N1，则该二叉树中度数为2的结点数为___N0-1______；若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有_______个空指针域。

3. 设指针p指向单链表中结点A，指针s指向被插入的结点X，则在结点A的前面插入结点X时的操作序列为：

1) s->next=__p->next____；2) p->next=s；3) t=p->data； 4) p->data=____s_______；5) s->data=t； 4. 已知一有向图的邻接表存储结构如下：从顶点1出发，DFS遍历的输

出序列是 13452 ，BFS遍历的输出序列是 13245

// 深度优先是从某个顶点出发，访问完后，寻找一个未访问的邻接顶点继