数据结构2008(信管A)

《数据结构2008(信管A)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、广东工业大学考试试卷(A)课程名称:数据结构（C语言）试卷满分100分考试时间:2008年6月25日(第18周星期3)题号一二三四五六七八九十总分评卷得分评卷签名复核得分复核签名一、选择题(每项选择2分，共36分)1、下面程序段的时间复杂度为（）。i=1;while(i

2、i≤n+1)A．O(0)B．O(1)C.O(n)D．O(n2)4、对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（）。A、顺序表B、带头指针的单循环链表C、带尾指针的单循环链表D、单链表学院：专业：学号：姓名：装订线广东工业大学试卷用纸，共6页，第6页5、数组A中，每个数据元素的长度为4个字节，行下标从3到8，列下标从2到10，存放该数组至少需要的字节数是（）。A、54B、108C、216D、2706、若一棵完全二叉树中某结点无左孩子，则该结点一定是（）。A、度为1的结点B、度为2的结点C、分支结点D、叶子结点7、某二叉树只有度为0和度为2的结点，如果该二叉树只有19个结点，则

3、叶子结点数为（）。A、9B、10C、11D、128已知二叉树的前序序列为DABCEFG，中序序列为BACDFGE则该二叉树的后序序列为（①），层次序列为（②）。①、②：A、BCAGFEDB、DAEBCFGC、ABCDEFGD、BCAEFGD9、将一棵树转换成二叉树，树的前根序列与其对应的二叉树的（①）相同。树的后根序列与其对应的二叉树的（②）相同。①、②：A、前序序列B、中序序列C、后序序列D、层序序列10、具有8个顶点的无向图最多可以有（）条边。A、8B、28C、56D、7211、下面关于图的操作的说法不正确的是（）。A、寻找关键路径是关于带权有向图的操作。B、拓扑排序是关于有向图的操作。C

4、、连通图的生成树不一定是唯一的。D、带权连通图的最小生成树是唯一的。12、下面的各种图中，哪个图的邻接矩阵是一定对称的（）。A、AOE网B、AOV网C、无向图D、有向图13、对线性表用折半查找时要求线性表必须是（）。A、顺序表B、单链表C、顺序存储的有序表D、散列表广东工业大学试卷用纸，共6页，第6页14、若一组记录的排序码序列为{60，40，10，90，80，20}，利用快速排序方法，以60为基准，升序排列，得到第一趟快速排序的结果为（）。A、10，40，20，60，90，80B、20，40，10，60，80，90C、40，10，20，60，90，80D、20，10，40，60，80，901

5、5、下列几种排序方法中要求辅助存储空间最大的是（）。A、堆排序B、直接选择排序C、归并排序D、快速排序二、算法测试（共34分）先按要求填空完成程序，再回答有关问题。1、（12分）在头指针为h的带表头结点的单链表中，把结点b插入到结点a之前，若不存在结点a就把结点b插入到表尾。单链表结点结构为：typedefstructnode{intdata;structnode*link;}LNode;voidinsertb(LNode*h，inta,intb){LNode*p,*q,*s;s=_（LNode*）malloc(sizeOf(LNode));（2分）s->data=b;p=h->link;q=

6、h;while(p->data!=a&&p->link!=NULL){q=p;p=_p->link________;(2分)}if(p->data==a){q->link=s;_s->link=p;___________;(2分)}else{__p->link=s;________;(2分)s->link=NULL;}}（1）（2分）什么是表头结点？用来指向链表的第一个节点的空节点。（2）（2分）分析该算法的时间复杂度为多少？O(n)广东工业大学试卷用纸，共6页，第6页2、（12分）以下函数实现二分法查找。intbinarysearch(Elemr[],intn,intk){intlow,hi

7、gh,mid;low=1;high=n;while(____mid==0______)(2分){mid=(low+high)/2;if(k==r[mid].key)return(____mid___);(2分)elseif(k