专插本《数据结构》样卷

（A卷）第1页共5页1韩山师范学院2009年专升本插班生考试试卷计算机科学与技术专业数据结构样卷题号一二三四五六七八九十总分评卷人得分一、单项选择题（每题2分，共40分）。题号12345678910答案题号11121314151617181920答案1.关于线性表的描述，错误的是（）。A.线性表是线性结构B.线性表就是单链表C.线性表的顺序存储结构，必须占用一片连续的存储单元D.线性表的链式存储结构，不必占用连续的存储单元2.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储()。A.数据的处理方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法3.与单链表相比，双链表的优点之一是()。A.插入、删除操作更简单B.可以进行随机访问C.可以省略表头指针或表尾指针D.顺序访问相邻结点更灵活4.对ｎ个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为()。A.n+1B.nC.n-1D.n(n-1)/25．如果结点A有3个兄弟，而且B为A的双亲，则B是度为（）A．3B．4C．5D．16．在具有N个单元的顺序存储循环队列中，假定front和rear分别为队头（A卷）第2页共5页2指针和队尾指针，则判断队满的条件为（）。A．front==rearB．(rear+1)%MAXSIZE==frontC．front-rear==1D．rear%MAXSIZE==front7.某二叉树的前序遍历序列为ABDGCEFH，中序遍历序列为DGBAECHF，则后序遍历序列为（）。A.BDGCEFHAB.GDBECFHAC.BDGAECHFD.GDBEHFCA8．设无向图的顶点个数为n，则该图最多有（）条边。A.n-1B.n(n-1)/2C．n(n+1)/2D.09.在一个长度为N的线性表中顺序查找值为x的元素时，在等概率的情况下查找成功时的平均查找长度为（）。A.NB.N/2C.(N+1)/2D.(N-1)/210．深度为5的二叉树至多有()个结点。A.16B.32C.31D.1011.堆的形状是一棵()。A.二叉排序树B.满二叉树C.完全二叉树D.平衡二叉树12．下列关于数据结构的叙述中，正确的是()。A.数组是同类型值的集合B.树是一种线性结构C.递归算法的程序结构比迭代算法的程序结构更为精炼D.用一维数组存储二叉树，总是以先序遍历的顺序存储各结点13.在具有n(n1)个结点的完全二叉树中，结点i(2*in)的左孩子结点是（）。A.2*iB.2*i+1C.不存在D.2*i-114.在有n个结点的二叉树中，值为非空的链域的个数为()。A.n-1B.2*n-1C.n+1D.2*n+115.若对一个已排好序的序列进行排序，在下列四种方法中，哪种比较好（）。A.冒泡法B.直接选择法C.直接插入法D.归并法16.设单链表中指针p指向结点A，若A的后继结点存在，则删除该后继结（A卷）第3页共5页3点需要修改指针的操作为（）。A．p-next=p-next-nextB．p=p-nextC．p=p-next-nextD．p-next=p17.队列操作的原则是()。A.先进先出B.后进先出C.只能进行插入D.只能进行删除18.对树进行层次遍历时，通常是采用()作为辅助来实现算法的。A．栈B.队列C.树D.图19.()是顺序存储方式的优点。A.存储密度大B.插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构的存储表示20.数组A[5][6]的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[5,5]的地址为()。A.1140B.1145C.1120D.1125二、判断题（每题1分，共10分）。以下各种说法，你认为对的在前面括号打√，错误的打×。()1．队列只能采用链式存储方式。()2.二叉树的度一定是2。()3.线性结构也是一种树结构。()4.有向图用邻接表表示后，顶点i的入度等于该顶点对应的单链表的元素个数。()5．满二叉树一定有偶数个结点。()6．直接插入排序的关键码比较次数与初始排列有关。()7．顺序存储方式只能用于存储线性结构。()8.给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。()9．在对链队列作出队操作时，不会改变front指针的值。()10.堆排序是不稳定排序。三、填空题（每空2分，共18分）。1．中缀算式（3+4）*2/（8-5）所对应的后缀算式为________。（A卷）第4页共5页42.某算法的时间复杂度为(5*n2+1000*n*log2n+4*n-8)/(10*n)，其数量级表示为______________。3.用1000个结点构造的二叉树，最少___________层，最多__________层。4.假定一个线性表为(12,23,74,55,63,40,82,36)，若按Key%3条件进行划分，使得同一余数的元素成为一个子表，则得到的三个子表分别为____________________、___________________和_____________________。5.假定一棵二叉树广义表表示为a(b(c),d(e,f))，其中序遍历序列为____________________，层次遍历序列为_____________________。四、程序填空题（每个语句2分，共12分）1．下面是向以BST为树根指针的二叉搜索树上插入值为item的结点的递归算法。请将缺失语句填上。voidInsert(BTreeNode*&BST,constElemType&item){if(BST==NULL){BTreeNode*p=newBTreeNode;p-data=item;_______________________;BST=p;}elseif(itemBST-data)___________________;else________________________;}2．下面是向单链表的末尾添加一个元素的算法。请将缺失的语句填上。VoidInsertRear(LNode*&HL,constElemType&item){LNode*newptr;newptr=newLNode;if(newptr==NULL){cerrMemoryallocationfailare!endl;（A卷）第5页共5页5exit(1);}newptr-data=item;_________________if(HL==NULL)HL=newptr;else{____________________;while()p=p-next;p-next=newptr;}}五、算法设计题（20分）1．编写算法函数，把顺序表List原地置逆。(10分)顺序表的数据结构如下：typedefstruct{intdata[100];intlast;//最后元素的下标}SeqList;函数原形为：voidfnReverse(SeqList&List);2.二叉树采用左右孩子指针存储结构：StructTreeNode{Intdata;//数据域StructTreeNode*left,*right;//指向其左右孩子结点};请编写一个递归函数，要在一棵树T中，找出值是x的结点的兄弟结点。(10分)函数原形如下：StructTreeNode*fnGetBrother(StructTreeNode*T,intx);