人生有几件绝对不能失去的东西:自制的力量，冷静的头脑，希望和信心 1
韩山师范学院2018年本科插班生考试试卷
计算机科学与技术 专业 数据结构 试卷（A卷）
题号 得分
一 二 三 四 五 六 总分 评卷人 得分 评卷人 一、单项选择题（每题2分，共30分）
1. 数据的最小单位是（ B ）。 A. 数据元素 B.数据项
C.数据类型 D. 数据变量
2. 一个栈的输入序列为A B C，则下列序列中不可能是栈的输出序列的是( 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 ）。
A. 696 B. 692 C.688 D. 678
//c,对的.676+(676-644)/2
A[2][2]与A[0][0] 相差两排零2个元素
部分文档来自网络收集，如有侵权，请联系作者删除
1
人生有几件绝对不能失去的东西:自制的力量，冷静的头脑，希望和信心 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
D.head!=0
10．数组的逻辑结构不同于下列（ A ）的逻辑结构。
11．根据二叉树的定义可知二叉树共有（ B ）种不同的形态。
12．设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（ A ）。 A.head==0 B. head->next==0 C. head->next==head //
注意：不论是带头结点的链表还是不带头结点的链表，头指针head都指向链表中的第一个结点。如果该链表有头结点，则头指针head指向头结点，如果没有头结点，则头指针head指向链表的第一个节点。
1 带头结点的单链表中头指针head指向头结点，头结点的值域不含任何信息，从头结点的后继结点开始存储信息。头指针head始终不等于NULL，head->next等于NULL的时候链表为空。
2 不带头结点的单链表中的头指针head直接指向开始结点，当head等于NULL的时候链表为空。
头结点的存在，使得空链表与非空链表的处理变得一直，也方便了对链表的开始结点插入或删除操作。
13．设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（ B ）。 A.第i行非0元素的个数之和 C.第i行0元素的个数之和 A. 2n
B. 2n-1
B. 第i列非0元素的个数之和 D. 第i列0元素的个数之和 C. n-1
D. n
14．设无向图G中有n个顶点，则该无向图的最小生成树上有（C ）条边。 15.由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ D ）
部分文档来自网络收集，如有侵权，请联系作者删除
2
人生有几件绝对不能失去的东西:自制的力量，冷静的头脑，希望和信心 3
A. 24 B. 48 C. 53 D. 71
得分 评卷人 二、填空题（每空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
// 深度优先是从某个顶点出发，访问完后，寻找一个未访问的邻接顶点继续深度优先，如果此路不同就往回退，所以看邻接表，首先访问V1，完了后顺链寻找没有访问的邻接顶点，自然链表中的第一个结点就是v3，接着转到v3再来深度优先，访问v3后，在其链表中第一个邻接顶点是v4 接着访问v4，下面走不通，回到v3，继续顺链往后，自然是v5，v5的邻接顶点中v2还没有访问 所以序列为v1, v3, v4, v5, v2 再看广度优先，从某个顶点完成后，需要一口气将其邻接未访问的所有顶点都访问，后面类推 部分文档来自网络收集，如有侵权，请联系作者删除
3
2018年韩山师范学院本科插班生考试试题《数据结构》A试卷
