（A卷）第1页共8页
韩山师范学院2017年本科插班生考试试卷
计算机科学与技术专业
题号得分一二三四
数据结构试卷（A卷）
五六总分评卷人
得分
评卷人
一、单项选择题（每题2分，共30分）
1对线性表，在下列哪种情况下应当采用链表表示？A经常需要随机地存取元素2C表中元素需要占据一片连续的存储空间。

B经常需要进行插入和删除操作D表中元素的个数不变
一个栈的输入序列为123，则下列序列中不可能是栈的输出序列的是
A23B321C312D1233．程序段si0；doii1；ssi；whilei
；的时间复杂度为（AO
BO
log2
CO
2）。B只能是子表D可以是子表或原子）。DO
324．一个非空广义表的表头（A不可能是子表C只能是原子
）。
5．设数组datam作为循环队列SQ的存储空间，fro
t为队头指针，rear为队尾指针，则执行出队操作后其头指针fro
t值为（Afro
tfro
t1Bfro
tfro
t1m1
Cfro
tfro
t1mDfro
tfro
t1m6．在一个单链表中若q所指结点是p所指结点的前驱结点若在q与p之间插入一个s所指的结点则执行As→li
kp→li
kCq→li
ksp→li
kss→li
kp。Bp→li
kss→li
kqs→li
kpDp→li
ks→li
k
1
f（A卷）第2页共8页
7．设有一个二维数组Am
，假设A00存放位置在64410，A22存放位置在67610，每个元素占一个空间，问A3310存放在什么位置？脚注10表示用10进制表示（A696B692）。C688D678
8．用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则所采用的排序方法是（）。D快速排序D数据变量D线性表）种不同的形态。D7A选择排序B希尔排序C归并排序9．组成数据的基本单位是（）。A数据项A树A4是（）。Bhead
ext0Chead
extheadDhead0B数据类型B栈B5C数据元素C队列C610．数组的逻辑结构不同于下列（
）的逻辑结构。
11．根据二叉树的定义可知二叉树共有（
12．设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件Ahead0为（）。B第i列非0元素的个数之和D第i列0元素的个数之和C
1D

13．设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度A第i行非0元素的个数之和C第i行0元素的个数之和A2
路径长度为（A24B2
1）B48C53D71
14．设无向图G中有
个顶点，则该无向图的最r