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

（A卷）第1页共8页1韩山师范学院2017年本科插班生考试试卷计算机科学与技术专业数据结构试卷（A卷）题号一二三四五六总分评卷人得分一、单项选择题（每题2分，共30分）1.对线性表，在下列哪种情况下应当采用链表表示？(B)A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变2.一个栈的输入序列为123，则下列序列中不可能是栈的输出序列的是(C)。A.23B.321C.312D.1233．程序段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．设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（D）。A.front=front+1B.front=(front+1)%(m-1)C.front=(front-1)%mD.front=(front+1)%m6．在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行(C)。A.s→link=p→link;p→link=s;B.p→link=s;s→link=q;C.q→link=s;s→link=p;D.p→link=s→link;s→link=p;得分评卷人（A卷）第2页共8页27．设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示（B）。A.696B.692C.688D.6788．用某种排序方法对关键字序列（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）。A.选择排序B.希尔排序C.归并排序D.快速排序9．组成数据的基本单位是（C）。A.数据项B.数据类型C.数据元素D.数据变量10．数组的逻辑结构不同于下列（A）的逻辑结构。A.树B.栈C.队列D.线性表11．根据二叉树的定义可知二叉树共有（B）种不同的形态。A.4B.5C.6D.712．设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（A）。A.head==0B.head-next==0C.head-next==headD.head!=013．设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（B）。A.第i行非0元素的个数之和B.第i列非0元素的个数之和C.第i行0元素的个数之和D.第i列0元素的个数之和14．设无向图G中有n个顶点，则该无向图的最小生成树上有（C）条边。A.2nB.2n-1C.n-1D.n15.由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（D）A.24B.48C.53D.71（A卷）第3页共8页3二、填空题（每空2分，共20分）1．数据的物理结构主要包括___顺序储存结构__和___链式存储结构_两种情况。2.设某棵二叉树中度数为0的结点数为N0，度数为1的结点数为N1，则该二叉树中度数为2的结点数为_________；若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有_______个空指针域。3.设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中_n-i+1__个数据元素；删除第i个位置上的数据元素需要移动表中_n-i__个元素。4.设某无向图G的邻接表为，则从顶点V1开始的深度优先遍历序列为___V1V3V2V4________；广度优先遍历序列为_V1V3V2V4____。5.设有一组初始关键字序列为(24，35，12，27，18，26)，则第3趟直接插入排序结束后的结果的是______(12,24,27,35,18,26)__________；设有一组初始关键字序列为(24，35，12，27，18，26)，则第3趟简单选择排序结束后的结果的是__(12,18,24,27,35,26)_______。三、判断题（对的划√，错的划×。每小题1分，共10分）得分评卷人得分评卷人（A卷）第4页共8页4（×）1．线性表中的所有元素都有一个前驱元素和后继元素。（√）2.不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（√）3．对连通图进行深度优先遍历可以访问到该图中的所有顶点。（×）4．由树转化成二叉树，该二叉树的右子树不一定为空。（√）5．如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（×）6.．有向图的邻接表和逆邻接表中表结点的个数不一定相等。//首先要明确建立“逆邻接表”的作用是为了方便计算入度.有向图每条弧对应唯一的弧头和弧尾.“逆邻接表”只是把“邻接表”中弧头和弧尾的次序换了,并不是一种新表,它和“邻接表”的唯一区别就是弧尾的nextarc指针指向弧头而已.所以节点数是相等的.（参考数据结构教材164页）（√）7．不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。（×）8．关键路径是AOE网中源点到汇点的最短路径。（√）9．图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问过。（×）10．用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。四、程序填空题（每个空2分，共10分）1.下面程序段的功能是实现一趟快速排序，请在下划线处填上正确的语句。structrecord{intkey;datatypeothers;};得分评卷人（A卷）第5页共8页5voidquickpass(structrecordr[],ints,intt,int&i){intj=t;structrecordx=r[s];i=s;while(ij){while(ij&&r[j].keyx.key)j=j-1;if(ij){r[i]=r[j];i=i+1;}while(____________________)i=i+1;if(ij){r[j]=r[i];j=j-1;}}_________________;}2.如下为二分查找的非递归算法，试将其填写完整。IntBinsch(ElemTypeA[],intn,KeyTypeK){intlow=0;inthigh=n-1;while(low=high){intmid=_______________________________；if(K==A[mid].key)returnmid;//查找成功，返回元素的下标elseif(K[mid].key)_________________________;//在左子表上继续查找else__________________;//在右子表上继续查找}return-1;//查找失败，返回-1}五、分析简答题（第一题8分，其余各题6分，共20分）1．（8分）已知一个图的顶点集V和边集E分别为：V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};得分评卷人（A卷）第6页共8页6用克鲁斯卡尔算法(Kruskal)得到最小生成树，试写出在最小生成树中依次得到的各条边。(1,2)3--(4,6)4,--,(1,3)5,--(1,4)8,--(2,5)10--(4,7)20,2.（6分）设某棵二叉树的中序遍历序列为DBEAC，前序遍历序列为ABDEC，试写出这棵二叉树的后序遍历结果并画出这颗二叉树。DEBCA（A卷）第7页共8页73.（6分）一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设散列表为HT[0..12]，散列函数为H（key）=key%13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。（A卷）第8页共8页8六、算法设计题（10分）设有一线性表（a1,a2,…,an-1）用单链表存储，写算法实现将其就地逆置的操作。（“就地”是指辅助空间应为O（1））得分评卷人