长沙理工大学数据结构期末考试试卷

1、 4/4长沙理工大学数据结构期末考试试卷 长沙理工大学计算机与通信工程学院 2013-2014学年二学期数据结构期末考试试卷(C卷) 班级:_学号:_姓名:_得分:_ 题目部分，(卷面共有32题,100分,各大题标有题量和总分) 一、应用题(2小题,共16分) 1分析下列程序段的时间复杂度： （1）for (i=1; inext=top; D top=top-next; 5若串S=SOFTWARE，其子串的数目最多是：（）。 A35 B36 C37 D38 6对于完全二叉树中的任一结点，若其右分支下的子孙的最大层次为h，则其左分支下的子孙的最大层次为（）。 A h B h+1 C h或h+1

2、D 任意 7下列命题正确的是（）。 A 一个图的邻接矩阵表示是唯一的，邻接表表示也唯一 B 一个图的邻接矩阵表示是唯一的，邻接表表示不唯一 C 一个图的邻接矩阵表示不唯一的，邻接表表示是唯一 D 一个图的邻接矩阵表示不唯一的，邻接表表示也不唯一 8设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选择（）。 A 99 B 97 C 91 D 93 9堆的形状是一棵（）。 A二叉排序树 B满二叉树 C完全二叉树 D 判定树 10设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是（）。 A F，H，C，D

3、，P，A，M，Q，R，S，Y，X B P，A，C，S，Q，D，F，X，R，H，M，Y C A，D，C，R，F，Q，M，S，Y，P，H，X D H，C，Q，P，A，M，S，R，D，F，X，Y 四、算法设计题(4小题,共32分) 1设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。 2设有两个集合A和集合B，要求设计生成集合C=AB的算法，其中集合A、B和C 用链式存储结构表示。 3对给定的带头结点的单链表L，编写一个删除L中值为X的结点的直接前趋结点的算法。4设计一个在链式存储结构上统计二叉树中结点个数的算

4、法。 五、填空题(11小题,共22分) 1已知顺序栈S，在对S进行进栈操作之前首先要判断（），在对S进行出栈操作之前首先要判断（）。 2设循环队列存放在向量sq.data0:M中，若用牺牲一个单元的办法来区分队满和队空（设队尾指针sq.rear）,则队满的条件为_。 3广义表(a), (b),c),(d)的表头是（），表尾是（）。 4在有n个叶子的哈夫曼树中，叶子结点总数为（），分支结点总数为（）。 5一棵二叉树的第i（i1）层最多有（）个结点；一棵有n（n0）个结点的满二叉树共有（）个叶子结点和（）个非终端结点。 6希尔排序法属于（） 7对n个待排序记录序列进行快速排序，所需要的最好时间复杂

5、度是（），最坏时间复杂度是（）。 8假设线性表的长度为n，则在最坏情况下，冒泡排序需要的比较次数为（） 9对于键值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从键值为（）的结点开始。 10图形结构的元素之间存在（）的关系。 11数据的存储结构是指（） 长沙理工大学计算机与通信工程学院 2013-2014学年二学期数据结构期末考试试卷(C卷)答案部分，(卷面共有32题,100.0分,各大题标有题量和总分) 一、应用题(2小题,共22分) 1O(log2n) （2）O(n2) 2【解答】构造的哈夫曼树如图所示。 树的带权路径长度为： WPL=24+34+5

6、3+73+83+92+112 =120 二、判断正误(5小题,共22分) 1错 2对 3错 4对 5对 三、单项选择题(10小题,共22分) 1栈 2A 3A 4D 5C 6C 7B 8B 9C 10D 四、算法设计题(4小题,共22分) 1typedef char datatype; typedef struct node datatype data; struct node *next;lklist; void split(lklist *head,lklist * ha=0,hb=0,hc=0; for(p=head;p!=0;p=head) head=p-next; p-next=0;

7、 if (p-data=A ha=p; else if (p-data=0 hb=p; else p-next=hc; hc=p; 2typedef struct node int data; struct node *next; lklist; void intersection(lklist *ha,lklist *hb,lklist * For(p=ha,hc=0;p!=0;p=p-next) for(q=hb;q!=0;q=q-next) if (q-data=p-data) break; if(q!=0) t=(lklist *)malloc(sizeof(lklist); t-da

8、ta=p-data; t-next=hc; hc=t; 3解： void delete(ListNode *L) ListNode *p=L,*q; if (L-next-data=X) printf (“值为x的结点是第一个结点，没有直接前趋结点可以删除”); return; for (;p-next-data!=X; q=p; p=p-next); / 删除指针p所指向的结点q-next=p-next; delete p; 4void countnode(bitree *bt,int countnode(bt-lchild,count); countnode(bt-rchild,count); 五、填空题(11小题,共22分) 1栈是否满栈是否空 2(sq.rear+1