数据结构期末试卷.doc

华南农业大学期末考试试卷（A卷）2003学年第2学期考试科目：数据结构评卷人：学生姓名：学号：专业年级：成绩： 一、 单选题（每题1.5分，共 15 分）1 研究数据结构就是研究（ ）A 数据的逻辑结构B 数据的存储结构C 数据的逻辑结构和存储结构D 数据的逻辑结构、存储结构及其数据在运算上的实现2 链表不具有的特点是（ ）。A. 可随机访问任一个元素 B. 插入删除不需要移动元素C. 不必事先估计存储空间 D. 所需空间与线性表的长度成正比3 设一个栈的输入序列是A、B、C、D，下列出栈序列中不正确的是（ ）AABCD B. DCBA C. ACDB D. DABC4 一棵深度为7（根的层次号为0）的完全二叉树有（ ）个叶子结点。A. 256 B. 255 C. 128 D. 1275 二维数组A45采用行序为主序方式存储，每个数据元素占4个存 储单元，且A22的存储地址是1000，则A33的地址是（ ）A1005 B. 1006 C. 1024 D. 1026.6 若循环队列用数组A0,m-1存放元素，其头尾指针分别为front 和rear，则当前队列的长度是（ ）。A. (rear-front+m)%m B. rear-front+1C. rear-front-1 D. (rear-front)%m 7将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为0，则编号位39的结点的左孩子的编号为（ ）。A78 B. 79 C. 80 D. 818利用逐点插入法建立序列（50，72，85，75，20，45，35，30，26）对应的二叉排序树以后，查找元素45要进行（ ）元素的比较。A3次 B. 4次 C. 7次 D. 9次9已知数据表A中每个元素距其最终位置不远，则采用（ ）排序算法最节省时间A冒泡排序 B. 简单选择排序 C. 直接插入排序 D. 快速排序10一个有n个顶点的有向图最多有 ( )条边。An B. n(n-1) C. n(n-1)/2 D. 2n二、 判断题（每题1.5分，共15分）1 线性表的每一个结点都有一个前驱和一个后继。2 一维数组实质是线性表的一种。3 顺序存储结构只能用来存放线性结构；链式存储结构只能用来存放非线性结构。4 任意一棵树均可转换成二叉树，再进行存储。5 在查找中，装填因子越大，再填记录时发生的冲突越小。6 简单选择排序是稳定排序。7 三种简单排序方法：简单选择排序、直接插入排序、冒泡排序在所有的排序算法中效率最低，所以不能使用。8 Dijkstra算法是按路径长度递增的次序产生一点到其余各顶点最短路径的算法。9 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。10 拓扑排序是指结点的值是有序排列。三、 完成算法设计（每空3,共30分）1 单链表的删除typedef struct Node DataType info; struct Node *link; *PNode,*LinkList;int delete_link( LinkList llist, DataType x )/* 在llist带有头结点的单链表中删除第一个值为x的结点 */ PNode p, q; ; /*找值为x的结点的前驱结点的存储位置 */ while( p-link != NULL & p-link-info != x ) ; if( p-link = NULL ) /* 没找到值为x的结点 */ printf(”Not exist!n ”); return(0); else q = p-link; /* 找到值为x的结点 */ ; /* 删除该结点 */ ; return(1); 2 进队列#define MAXNUM 100struct SeqQueue DataType aMaxnum; int f,r;typedef struct SeqQueue *PSeqQueue;void enQueue_seq( PSeqQueue paqu, DataType x )/* 在队列中插入一元素x */ if( ) printf( Full queue.n ); else paqu-qpaqu-r = x; ; 3 直接插入排序typedef struct KeyType key; /*排序码字段*/ DataType info; /*记录的其他字段*/ RecordNode;typedef struct RecordNode recordMAXNUM; int n; /* n为文件中的记录个数 n=MAXNUM*/ SortObject;void insertSort(SortObject * pvector)/* 按递增序进行直接插入排序 */int i, j;RecordNode temp; for( i = 1; i recordi; ; while ( )/* 由后向前找插入位置 */ pvector-recordj+1 = pvector-recordj;/* 将排序码大于ki的记录后移 */ j-; if( ) pvector-recordj+1 = temp; 四、 构造题（共40分）1 假设一颗二叉树的前序遍历序列为 ABDFCE ，中序遍历序列DFBACE。要求：（1）画出该树(3分) （2）写出该树的后序遍历序列(2分)。2 用给出的一组字符A，B，C，D，E的权值是3，4，5，6，8，按权值左小右大建立一棵哈夫曼树(4分)，并给出每个字符的哈夫曼编码(1分)。3 对长度为8的有序表，给出折半查找的判定树(4分)，给出等概率情况下的平均查找长度(2分)。4 已知关键字序列为：75,33,52,41,12,88,66,27,哈希表长为10，哈希函数H(key)=key % 7，解决冲突用线性探测法（1）构造哈希表（4分）（2）给出找每个关键字的比较次数及哈希表等概率条件下AVL值（3分）5 一组记录的关键字为（46，79，56，38，40，84），利用快速排序的方法，以第一个记录为基准，画出一次划分的过程（6分）。6 已知无向图如下：DBCAEFH102522121618142428从A开始，给出一棵广度优先生成树（5分） 7 按Kruskal算法生成上图的最小代价生成树（6分）5 华南农业大学期末考试答题纸（A卷）2003学年第2学期考试科目：数据结构评卷人：孙爱东 学生姓名：学号：专业年级：成绩： 题号一二三 四总分1234567小计得分一、 单选题（每题1.5分，共 15 分）题号 12345678910答案二、 判断题（每题1.5分，共15分，正确、错误）题号 12345678910答案三、 完成算法设计（每空3,共30分） 四、构造题（共40分）华南农业大学期末考试参考答案（A卷）2003学年第2学期考试科目：数据结构评卷人：学生姓名：学号：专业年级：成绩： 一、 单选题（每题1.5分，共 15 分）题号 12345678910答案DADCCABACB二、 判断题（每题1.5分，共15分，正确、错误）题号 12345678910答案三、 完成算法设计（每空3分,共30分） p = llist p = p-link p-link = p-link-link 或 p-link=q-link free( q ) (paqu-r + 1) % MAXNUM = paqu-f paqu-r = (paqu-r + 1) % MAXNUM i n j = i-1 (temp.key recordj.key)&(j=0) j!=(i-1) 四、构造题（共40分）ABDFCE1. (1) 满分3分，上到下，每1结点0.5分(2) FDBECA 满分2分，如果上面的图遍历正确得1分EBADC26A11541586372. (1) (2) A: 100 B:101 C:00 D:01 E:11 满分1分，遵守左0右1可得1分 未按左小右大建树3分 满分4分，4次组合，每对1个1分3. (1)（4分）31075624 (2) AVL=(1+2*2+4*3+1*4)/8=21/8=2.62 （2分）4. 计算函数值key7533524112886627Key%755365436(1)哈希表（4分，每对1个0.5分）index0123456789key2752887533411266(2)比较次数（3分） key7533524112886627Cmp12124175AVL=(1+2+1+2+4+1+7+5)/8=23/8初始序列: 46 79 56 38 40 84(1) 40 79 56 38 46