华南农业大学期末考试试卷（ A 卷）.doc

华南农业大学期末考试试卷（　A　卷） 2003学年第2学期　考试科目：　数据结构　　评卷人：　　　　　 学生姓名：　　　　　学号：　　　　　专业年级：　　　　　成绩：　　 单选题（每题1.5分，共 15 分） 研究数据结构就是研究（ ） 数据的逻辑结构 数据的存储结构 数据的逻辑结构和存储结构 数据的逻辑结构、存储结构及其数据在运算上的实现 链表不具有的特点是（ ）。 可随机访问任一个元素 B. 插入删除不需要移动元素 C. 不必事先估计存储空间 D. 所需空间与线性表的长度成正比 设一个栈的输入序列是A、B、C、D，下列出栈序列中不正确的是（ ） A．ABCD B. DCBA C. ACDB D. DABC 一棵深度为7（根的层次号为0）的完全二叉树有（ ）个叶子结点。 A. 256 B. 255 C. 128 D. 127 二维数组A[4][5]采用行序为主序方式存储，每个数据元素占4个存 储单元，且A[2][2]的存储地址是1000，则A[3][3]的地址是（ ） A．1005 B. 1006 C. 1024 D. 1026. 若循环队列用数组A[0,m-1]存放元素，其头尾指针分别为front 和rear，则当前队列的长度是（ ）。 A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. (rear-front)%m 7．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为0，则编号位39的结点的左孩子的编号为（ ）。 A．78 B. 79 C. 80 D. 81 8．利用逐点插入法建立序列（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．n B. n(n-1) C. n(n-1)/2 D. 2n 判断题（每题1.5分，共15分） 线性表的每一个结点都有一个前驱和一个后继。 一维数组实质是线性表的一种。 顺序存储结构只能用来存放线性结构；链式存储结构只能用来存放非线性结构。 任意一棵树均可转换成二叉树，再进行存储。 在查找中，装填因子越大，再填记录时发生的冲突越小。 简单选择排序是稳定排序。 三种简单排序方法：简单选择排序、直接插入排序、冒泡排序在所有的排序算法中效率最低，所以不能使用。 Dijkstra算法是按路径长度递增的次序产生一点到其余各顶点最短路径的算法。 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。 拓扑排序是指结点的值是有序排列。 完成算法设计（每空3,共30分） 单链表的删除 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); } } 进队列? #define MAXNUM 100 struct SeqQueue { DataType a[Maxnum];