搜索
（A卷）第1页共8页韩山师范学院2018年本科插班生考试试卷计算机科学与技术专业数据结构试卷（A卷）题号一二三四五六总分评卷人得分一、单项选择题（每题2分，共30分）1.数据的最小单位是（B）。A.数据元素B.数据项C.数据类型D.数据变量2.一个栈的输入序列为ABC，则下列序列中不可能是栈的输出序列的是(C)。A.BCAB.CBAC.CABD.ABC3．程序段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-FB.F-RC.(F-R+M)％MD.(R-F+M)％M6．设指针变量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卷）第2页共8页A.696B.692C.688D.678//c,对的.676+(676-644)/2A[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-644A[3][3]与A[2][2]地址差是(676-644)/2所以A[3][3]的地址是676+(676-644)/28．设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为(D)。A.15，10，14，18，20，36，40，21B.10，15，14，18，20，40，36，21C.10，15，14，20，18，40，36，2lD.10，15，14，18，20，36，40，219．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（C）。A.9B.10C.11D.1210．数组的逻辑结构不同于下列（A）的逻辑结构。A.树B.栈C.队列D.线性表11．根据二叉树的定义可知二叉树共有（B）种不同的形态。A.4B.5C.6D.712．设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（A）。A.head==0B.head-next==0C.head-next==headD.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元素的个数之和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二、填空题（每空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//深度优先是从某个顶点出发，访问完后，寻找一个未访问的邻接顶点继得分评卷人（A卷）第4页共8页续深度优先，如果此路不同就往回退，所以看邻接表，首先访问V1，完了后顺链寻找没有访问的邻接顶点，自然链表中的第一个结点就是v3，接着转到v3再来深度优先，访问v3后，在其链表中第一个邻接顶点是v4接着访问v4，下面走不通，回到v3，继续顺链往后，自然是v5，v5的邻接顶点中v2还没有访问所以序列为v1,v3,v4,v5,v2再看广度优先，从某个顶点完成后，需要一口气将其邻接未访问的所有顶点都访问，后面类推于是过程是先v1，再顺链将v3，v2依次访问完，然后再依次访问v3和v2的各个未访问邻接顶点，v3链表中顺链可以访问v4，v5，所以最后访问序列为v1,v3,v2,v4,v55.解决散列表冲突的两种方法是___开放定址法____和__链地址法__。三、判断题（对的划√，错的划×。每小题1分，共10分）（×）1．调用一次深度优先遍历可以访问到图中的所有顶点。（×）2.设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。//因为不知道左右孩子。所以如果已知中序，只需要一个前序或者后序就可以确定二叉树了（√）3．快速排序是排序算法中平均性能最好的一种排序。（√）4．不论是入队列操作还是入栈操作，在顺序存储结构上都需得分评卷人（A卷）第5页共8页要考虑“溢出”情况。（×）5．线性表中的所有元素都有一个前驱元素和后继元素。（√）6.分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。//分块查找:即又称索引顺序查找,这是顺序查找的一种改进的方法.在此查找法中,除表本身以外,尚需建立一个索引表,其包含两项内容:关键字项(其值为该字表中最大的关键字)和指针项(指示该字表的第一个记录在表中的位置).所谓分块指的是第二个子表中所有的关键字都比第一个表中的关键字大,同理,第三个字表都大于第二个字表中的所有的关键字..通常,分块查找的过程需要分两步:先确定待查记录所在的块(字表),然后在块中顺序查找.（×）7．向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。（√）8．不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。（×）9．子串“ABC”在主串“AABCABCD”中的位置为2。（×）10．用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。四、程序填空题（每个空2分，共10分）1.下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。voidbubble(intr[n]){for(i=1;i=n-1;i++){得分评卷人（A卷）第6页共8页for(exchange=0,j=0;j_____________;j++)if(r[j]r[j+1]){temp=r[j+1];______________;r[j]=temp;exchange=1;}if(exchange==0)return；}}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}五、分析简答题（共20分）1．（10分）求AOE网的关键路径。关键路径：v0,v1,v4,v3,v6得分评卷人（A卷）第7页共8页2.（10分）一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设散列表为HT[0..12]，散列函数为H（key）=key%13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。（A卷）第8页共8页六、算法设计题（10分）1.设计两个有序单链表的合并排序算法。得分评卷人