贵州大学2010-2011学年第二学期数据结构试卷

贵州大学2010-2011学年第二学期考试试卷 A数据结构与算法设计注意事项：1. 请考生按要求在试卷装订线内填写姓名、学号和年级专业。2. 请仔细阅读各种题目的回答要求，在规定的位置填写答案。3. 不要在试卷上乱写乱画，不要在装订线内填写无关的内容。4. 满分100分，考试时间为120分钟。题 号一二三四五总 分统分人得 分得 分评分人一、填空题（共20分,每小题2分）1、数据的存储结构可以分为_结构、 结构、索引结构和散列结构。2、一个广义表中的元素分为 元素和 元素。3、在线性表的单链接存储结构中，每个结点包含有两个域，一个叫 域，另一个叫 域。4、向一个栈顶指针为HS的链栈中插入一个新结点*p时，应执行 和 操作。5、后缀表达式“5 6 * 4 3 + ”的值为 。6、对于一棵含有40个结点的理想平衡二叉树，它的高度为 。7、若对一棵二叉树从0开始进行结点编号，并按此编号把它顺序存储到一维数组a中，即编号为0的结点存储到a0中，其余类推，则ai元素的左孩子元素为 ，右孩子元素为 ，双亲元素（i0）为a(i-1)/2。8、在任何一棵哈夫曼树中，单分支结点的个数为 。9、图中的一条路径的长度为k，该路径所含的顶点数为 。10、在循环单链表中，最后一个结点的指针域指向 结点。得 分评分人二、选择题（共20分,每小题2分）1、一个数组元素ai与（ ）的表示等价。 A、*(a+i) B、a+i C、*a+i D、&a+i2、在一个长度为n的顺序存储的线性表中，删除第i个元素(1in)时，需要从依次移（ ）个元素。A、ni B、ni+1 C、ni1 D、i3、在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行 ( )。A、HL=p; p-next=HL; B、p-next=HL; HL=p; C、p-next=HL; p=HL; D、p-next=HL-next; HL-next=p;4、一个链栈的栈顶指针用top表示，当进行退栈时所进行的指针操作为（ ）。A、top-next=top; B、top=top-data;C、top=top-next; D、top-next=top-next-next;5、从一个顺序队列删除元素时，首先需要（ ）。A、队首指针循环加1 B、队首指针循环减1C、取出队首指针所指位置上的元素 D、取出队尾指针所指位置上的元素6、树中所有结点的数等于所有结点度数加（ ）。 A、2 B、1 C、-1 D、07、若根据数组长度为m的散列表，采用线性探测法处理冲突，假定对一个元素第一次计算的散列地址为d，则下一次的散列地址为( )。A、d B、d1 C、(d1)/m D、(d1)%m8、若一个图的边集为,，则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为（ ）。A、1,2,5,4,3 B、1,2,3,4,5 C、1,2,5,3,4 D、1,4,3,2,59、在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的（ ）。 A、出边数 B、入边数 C、度数 D、度数减110、若对n个元素进行直接插入排序，在进行第i趟(1in-1)排序时，为寻找插入位置最多需进行（ ）次元素比较。A、i+1 B、i-1 C、i D、1得 分评分人三、程序阅读题（共15分,每小题3分）1、 以下程序段的时间复杂度为 。int i=0,s=0;while(+i=n)int p=1;for(int j=1;j=i;j+) p*=j;s=s+p;2、 下面函数的功能是从单链表中查找出所有元素的最大值，该值由函数返回。请将程序补充完整。typedef int ElemType;struct LNodeElemType data;LNode* next; ElemType MaxValue(LNode* HL)if(HL=NULL)cerrLinked list is empty!data;LNode *p=HL-next;while( )if(maxdata) max=p-data; return max;3、 说出下列算法的含义。data为结点值域，left为指向左孩子的指针域，right为指向右孩子的指针域。typedef int ElemType;struct BTreeNodeElemType data;BTreeNode* left;BTreeNode* right;void fun(BTreeNode* BT)if(BT!=NULL)BTreeNode *pt=BT-left; BT-left=BT-right; BT-right=pt; fun(BT-left); fun(BT-right); 4、 下面函数的功能是采用递归的方法求1n之间的所有整数平方的和。请将程序补充完整。int SquareSum(int n) if(n= =0) return 0; else 5、 说出下列算法的含义。typedef int ElemType;struct ListElemType *list;int size;int MaxSize;void fun(List& L,ElemType s,ElemType t)int i=0;while(i=s) & (L.listi=t)for(int j=i+1;js2，函数返回大于0的数，如果s1s2，函数返回小于0的数，如果s1=s