数据结构期末试卷

《数据结构期末试卷》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、华南农业大学期末考试试卷（　A　卷）2003学年第2学期　考试科目：　数据结构　　评卷人：　　　　　学生姓名：　　　　　学号：　　　　　专业年级：　　　　　成绩：　　一、单选题（每题1.5分，共15分）1．研究数据结构就是研究（）A．数据的逻辑结构B．数据的存储结构C．数据的逻辑结构和存储结构D．数据的逻辑结构、存储结构及其数据在运算上的实现2．链表不具有的特点是（）。A.可随机访问任一个元素B.插入删除不需要移动元素C.不必事先估计存储空间D.所需空间与线性表的长度成正比3．设一个栈的输入序列是A、B、C、D，下列出栈序列中不正确的是（）A．ABCDB.DCBAC.ACDBD.DABC

2、4．一棵深度为7（根的层次号为0）的完全二叉树有（）个叶子结点。A.256B.255C.128D.1275．二维数组A[4][5]采用行序为主序方式存储，每个数据元素占4个存储单元，且A[2][2]的存储地址是1000，则A[3][3]的地址是（）A．1005B.1006C.1024D.1026.6．若循环队列用数组A[0,m-1]存放元素，其头尾指针分别为front和rear，则当前队列的长度是（）。A.(rear-front+m)%mB.rear-front+1C.rear-front-1D.(rear-front)%m7．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到

3、右依次对结点进行编号，根结点编号为0，则编号位39的结点的左孩子的编号为（）。A．78B.79C.80D.818．利用逐点插入法建立序列（50，72，85，75，20，45，35，30，26）对应的二叉排序树以后，查找元素45要进行（）元素的比较。A．3次B.4次C.7次D.9次9．已知数据表A中每个元素距其最终位置不远，则采用（）排序算法最节省时间A．冒泡排序B.简单选择排序C.直接插入排序D.快速排序10．一个有n个顶点的有向图最多有()条边。A．nB.n(n-1)C.n(n-1)/2D.2n二、判断题（每题1.5分，共15分）1．线性表的每一个结点都有一个前驱和一个后继。2．一维数

4、组实质是线性表的一种。3．顺序存储结构只能用来存放线性结构；链式存储结构只能用来存放非线性结构。4．任意一棵树均可转换成二叉树，再进行存储。5．在查找中，装填因子越大，再填记录时发生的冲突越小。6．简单选择排序是稳定排序。7．三种简单排序方法：简单选择排序、直接插入排序、冒泡排序在所有的排序算法中效率最低，所以不能使用。8．Dijkstra算法是按路径长度递增的次序产生一点到其余各顶点最短路径的算法。41．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。2．拓扑排序是指结点的值是有序排列。一、完成算法设计（每空3,共30分）1．单链表的删除typedefstructNode{D

5、ataTypeinfo;structNode*link;}*PNode,*LinkList;intdelete_link(LinkListllist,DataTypex)/*在llist带有头结点的单链表中删除第一个值为x的结点*/{PNodep,q;⑴;/*找值为x的结点的前驱结点的存储位置*/while(p->link!=NULL&&p->link->info!=x)⑵;if(p->link==NULL)/*没找到值为x的结点*/{printf(”Notexist!”);return(0);}else{q=p->link;/*找到值为x的结点*/⑶;/*删除该结点*/⑷;retu

6、rn(1);}}2．进队列 #defineMAXNUM100structSeqQueue{DataTypea[Maxnum];intf,r;};typedefstructSeqQueue*PSeqQueue;voidenQueue_seq(PSeqQueuepaqu,DataTypex)/*在队列中插入一元素x*/{if(⑸)printf("Fullqueue.");else{paqu->q[paqu->r]=x;⑹;4}}1．直接插入排序typedefstruct{KeyTypekey;/*排序码字段*/DataTypeinfo;/*记录的其他字段*/}RecordNode;typ

7、edefstruct{RecordNoderecord[MAXNUM];intn;/*n为文件中的记录个数n<=MAXNUM*/}SortObject;voidinsertSort(SortObject*pvector)/*按递增序进行直接插入排序*/{inti,j;RecordNodetemp;for(i=1;i<⑺;i++)/*依次插入记录R1,R2…Rn-1*/{temp=pvector->record[i];⑻;while(