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

人生有几件绝对不能失去的东西:自制的力量，冷静的头脑，希望和信心1韩山师范学院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）。23A.O(n)B.O(nlog2n)C.O(n)D.O(n/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.696B.692C.688D.678//c,对的.676+(676-644)/2A[2][2]与A[0][0]相差两排零2个元素部分文档来自网络收集，如有侵权，请联系作者删除1人生有几件绝对不能失去的东西:自制的力量，冷静的头脑，希望和信心2A[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的时候链表为空。头结点的存在，使得空链表与非空链表的处理变得一直，也方便了对链表的开始结点插入或删除操作。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）部分文档来自网络收集，如有侵权，请联系作者删除2人生有几件绝对不能失去的东西:自制的力量，冷静的头脑，希望和信心3A.24B.48C.53D