200-2005-1数据结构 b.doc

南 京 林 业 大 学 试 卷课程 数据结构(A卷) 20042005学年第一学期题号一二三四五六总分得分名姓号学号班 注意：请将正确答案写在答题纸上，答在试卷上不给分。12345678910XXXXXX二选择题：(20分)12345678910CACDCCBABA一是非题：（每小题2分，共20分）1数据项是数据的基本单位。（ ）2线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。（ ）3在线性表的顺序存储结构中，逻辑上相邻的两个元素但在物理位置上并不一定相邻。（ ）4顺序存储方式只能用于存储线性结构。（ ）5若入队序列为1，2，3，4，则4，3， 2，1是一个出队序列。（ ）6设有两个串p和q，其中q是p的子串，把q在p中首次出现的位置作为子串q在p中的位置的算法称为匹配。（ ）7使用三元组顺序表表示稀疏矩阵的元素，有时并不能节省存储空间。（T ）8先根遍历树和先序遍历与该树对应的二叉树，其结果不同。（F ）9哈夫曼树是带权路径长度最短的树，路经上权值较大的结点离根较近。（T ）10连通分量是无向图中的极小连通子图。（F ）二选择题（本大题共10小题，每小题2分，共20分）1 数据结构是研究数据的_以及它们之间的相互关系。A.抽象结构和理想结构 B.物理结构和理想结构 C. 物理结构和逻辑结构 D.物理结构和抽象结构2 线性表是_。A. 一个有限序列，可以为空 B. 一个有限序列，不能为空 C. 一个无限序列，可以为空 D. 一个无限序列，不能为空3 若已知一个栈的入栈序列是1,2,3,n,其输出序列为s1,s2,s3,sn,若s1=n, 则si为_。Ai Bn=i Cn-i+1 D以上都不对4 将两个各有n1和n2个元素的有序表(递增)归并成一个有序表，仍保持其递增顺序，则最少的比较次数是_。An1 Bn2 Cn1+n2-1 Dmin (n1,n2)5 具有线性结构的数据结构是_。A. 树结构 B.图结构 C.广义表 D.文件结构6 按照二叉树的定义，具有3个结点的二叉树有_ 种。A3 B4 C5 D6 7 下面哪一个方法可以判断出一个有向图中是否有环（回路）_。A广度优先遍历 B拓扑排序C求最短路径 D求关键路径8 设森林对应的二叉树为，有个结点，的根为，的右子树结点个数为，森林中第一棵树的结点个数是_。Am-n Bm-n+1 Cn+1 D条件不足，无法确定9 一个具有n个顶点的有向图最多有_B_ 条弧。An Bn(n-1) Cn(n-1)/2 D2n 10 不满足平衡查找树概念的是_。ABST树 B.AVL树 C.折半查找判定树 D.B+树三填空题：（本大题共10小题，每小题2分，共20分）1 计算机执行下面语句时，语句S的频度（执行次数）为_。 for(i=1;i=i;j-) S;2 从任何一个结点开始都能成功查找其它结点的单链表是 表。3 设n行n列的上三角矩阵A已压缩存储到一维数组B0.n(n+1)/2-1中，且按行为主序存储，则aij（i,j=0,1,2,n-1）对应的B中的存储位置为 。4 n个顶点的有向强连通图用邻接矩阵表示时，该矩阵至少有 个非零元素。5 若一个二叉树含有n个结点，则它的二叉链表中必有 个空的链域。 6 若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总的结点数是 _。7 Dijkstra最短路径算法从源点到其余各顶点的最短路径长度按_次序产生。8 设有100个元素，用折半查找方法查找时，若查找成功，则最多的比较次数是_，最少的比较次数是_。9 若m阶B-树中有n个关键字，则叶子结点即查找不成功的结点数为_。10 对n个不同的元素进行冒泡排序（从小到大排序），在最坏情况下记录的移动次数为_，关键字的比较次数为_。四解答题（15分）：1 设哈希函数H(K)=K MOD P，哈希表地址空间为012，对给定的关键字序列（19，14，23，01，68，21，84，38）分别以链地址法和线性探测散列法解决冲突构造哈希表，给出所构造的过程，计算查找概率相等情况下查找成功的平均查找长度。2已知关键字序列为（20，10，40，45，55，58，68），依照次顺序建立一棵3阶B-树，给出建立的过程及结果树。若删除了40和58，结果又如何？五算法阅读题（15分）：1. 下面的算法将一个带头结点的单链表la分解为两个链表la，lb，使得la表中含有原表中的奇数项的结点，而lb表中含有偶数项的节点，且保持结点原有的相对顺序，请补充完整。void disab(ListedList &la,ListedList &lb) lb=(LinkType)malloc(sizeof(NodeType); r=lb;p=la-next; while(_(1)_&p-next_(2)_) q=p-next; _(3)_; r-next=q;r=q; _(4)_; _(5)_;/disab2设有算法如下： #define NULL 0typedef struct node KeyType key;struct node *lchild, *rchild;BSN, *BST;void unknown (BST *bs, KeyType key) BST s; if (*bs= NULL) s=(BST)malloc(sizeof(BSN); s-key=key; s-lchild=NULL; s-rchild=NULL; *bs=s;else if ( key= = (*bs)-key) printf (“The node exists in the binary tree!”); else if (key key) unknown (&(*bs)-lchild),key); else unknown (&(*bs)-rchild),key);函数unknown实现了对二叉排序树的一种运算；（1）试说明unknown的功能。（2） 若root是BST型变量，且root指向如下二叉树的根结点，试画出执行完unknown (root,48) 后，root指向的二叉树。4527521968root六算法设计题（10分）：1.一元稀疏多项式以单链表结构按降幂排列，结点有三个域，系数域coef，指数域exp和指针域next，链表的头指针为ha，头结点的exp域为-1。设计一算法实现对一元多项式求一阶导数。（5分）单链表的存储结构为：typedef struct Node int coef，exp; struct Node * next;Node,* LinkList;2二叉树采用链式存储结构，设计一个计算一棵给定二叉树深度的递归算法。（5分）二叉树的存储结构为：typedef struct node ElemType data;struct node *lchild, *rchild;BiNode, *BiTree; 南 京 林 业 大 学 答 题 纸课程 数据结构(A卷) 20042005学年第一学期题号一二三四五六总分得分名姓号学号班 一 是非题：（20分）12345678910二选择题：(20分)12345678910三填空题：(20分)1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 以下题目请写清楚题号南 京 林 业 大 学 答 案课程 数据结构(A卷) 20042005学年第一学期名姓号学号班题号一二三四五六总分得分 二 是非题：（20分）12345678910XXXXXX二选择题：(20分)12345678910CACDCCBABA三填空题：（20分）1. 3+4+5+n=(3+n)(n-2)/2 2. 循环链（表）3. i(i+1)/2+j 4. n 5. 2n-(n-1) (或 n+1) 6. 697. 路径长度递增 8. 7，19. n+1 10. (n-1) ， n(n-1)/2四解答题（15分）:1.H(19)=19 MOD 13=6 H(14)=14 MOD 13=1 H(23)=23 MOD 13=10 H(01)=01 MOD 13=1 H(68)=68 MOD 13=3 H(21)=21 MOD 13=8 H(84)=84 MOD 13=6 H(38)=38 MOD 13=12(1) 线性探测散列法0 0 1 2 3 4 5 6 7 8 9 10 11 1214016819842123381 2 1 1 2 1 1 1ASL成功=1/8（1+2+1+1+2+1+1+1）=1.25(2) 链地址法0123456789101112ASL成功=1/8（1+2+1+1+2+1+1+1）=1.252 20 20 45 45 10 40 45 10 40 55 58 20 58 10 40 55 68删除了40和58后，结果如下： 45 58 45 10 20 55 68 10 20 55 58五算法阅读题（15分）：1(1) p!=NULL (2) !=NULL (3) p-next=q-next(4) p=q-next (5) r-next2(1) 实现在二叉排序树上的插入操作：若二叉排序树上不存在，则插入；若二叉排序树上已存在，不插入，仅给出提示信息“The node exists in the binary tree!”45275219 68root (2) 48 六算法设计题（10分）：1. typedef struct Node int coef，exp; struct Node * next;Node,* LinkList;derivative(LinkList ha) LinkList q, pa;q=ha; pa=ha-next; while( pa ) if(pa-exp=0) q-next=pa-next ; free(pa); pa=q; else pa-coef=pa-coef*pa-exp; pa-exp= pa-exp-