2022年数据结构b .pdf

1 / 9 南 京 林 业 大 学 试 卷课程数据结构(A 卷20042005学年第一学期注意：请将正确答案写在答题纸上，答在试卷上不给分。1 2 3 4 5 6 7 8 9 10 XXXXXX二选择题： (20分 1 2 3 4 5 6 7 8 9 10 C A C D C C B A B A 一是非题：每小题 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 ）题号一二三四五六总分得分名姓号学号班精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 9 页2 / 9 10连通分量是无向图中的极小连通子图。F ）二选择题 归并成一个有序表，仍保持其递增顺序，则最少的比较次数是_。An1 Bn2 Cn1+n2-1 Dmin (n1,n2 5具有线性结构的数据结构是_。A. 树结构 B.图结构 C.广义表 D.文件结构6按照二叉树的定义，具有3个结点的二叉树有_ 种。 A3 B4 C5 D6 7下面哪一个方法可以判断出一个有向图中是否有环 Cn(n-1/2 D 2n 10不满足平衡查找树概念的是_。ABST树 B.AVL树 C.折半查找判定树 D.B+树三填空题：本大题共10 小题，每小题2 分，共 20 分）1计算机执行下面语句时，语句S的频度 执行次数）为_。for(i=1。 i for(j=n。 j=i 。 j- S。2从任何一个结点开始都能成功查找其它结点的单链表是表。3设 n 行 n 列的上三角矩阵A 已压缩存储到一维数组B0.n(n+1/2-1精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 9 页3 / 9 中，且按行为主序存储，则aiji,j=0,1,2,n-1 ）对应的B中的存储位置为。4n个顶点的有向强连通图用邻接矩阵表示时，该矩阵至少有个非零元素。5若一个二叉树含有n个结点，则它的二叉链表中必有个空的链域。6若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总的结点数是 _。7Dijkstra最 短 路 径 算 法 从 源 点 到 其 余 各 顶 点 的 最 短 路 径 长 度 按_次序产生。8设有 100个元素，用折半查找方法查找时，若查找成功，则最多的比较次数是 _，最少的比较次数是_。9若m 阶 B- 树中有n 个关键字，则叶子结点即查找不成功的结点数为_。10对 n 个不同的元素进行冒泡排序从小到大排序），在最坏情况下记录的移动次数为 _，关键字的比较次数为_。四解答题 =K MOD P，哈希表地址空间为012，对给定的关键字序列19，14， 23，01，68，21，84，38）分别以链地址法和线性探测散列法解决冲突构造哈希表，给出所构造的过程，计算查找概率相等情况下查找成功的平均查找长度。2已知关键字序列为20，10，40，45， 55，58，68），依照次顺序建立一棵3阶 B-树，给出建立的过程及结果树。若删除了40和 58，结果又如何？五算法阅读题 lb=(LinkTypemalloc(sizeof(NodeType。r=lb 。 p=la-next。while(_(1_&p-next_(2_ q=p-next。_(3_。r-next=q。 r=q 。 _(4_。 _(5_。 /disab 2设有算法如下： #define NULL 0 typedef struct node 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 9 页4 / 9 KeyType key 。struct node *lchild, *rchild。BSN, *BST 。void unknown (BST *bs, KeyType key BST s。 if (*bs= NULL s=(BSTmalloc(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 的功能。 后， root指向的二叉树。六算法设计题10分）：1. 一元稀疏多项式以单链表结构按降幂排列，结点有三个域，系数域coef ，指数域exp和指针域next ，链表的头指针为ha，头结点的exp 域为 -1。设计一算法实现对一元多项式求一阶导数。5分）单链表的存储结构为：typedef struct Node 45 27 52 19 68 root 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 9 页5 / 9 int coef，exp 。 struct Node * next。Node,* LinkList。2二叉树采用链式存储结构，设计一个计算一棵给定二叉树深度的递归算法。20042005学年第一学期一是非题： 1 2 3 4 5 6 7 8 9 10 三填空题： (20分 1.2. 3.4. 5. 6. 7. 8. 题号一二三四五六总分得分名姓号学精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 9 页6 / 9 9. 10. 以下题目请写清楚题号南 京 林 业 大 学 答 案课程数据结构(A 卷20042005学年第一学期二是非题： 1 2 3 4 5 6 7 8 9 10 C A C D C C B A B A 三填空题： (n-2/22. 循环链 /2+j4. n 5. 2n-(n-1 (或 n+16. 69 7. 路径长度递增 8. 7，1 9. n+110.(n-1 ， n(n-1/2 题号一二三四五六总分得分名姓号学精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 9 页7 / 9 四解答题 =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 0123 4 56789101112 14 01 68 19 84 21 23 38 121 121 11 ASL 成功 =1/8链地址法0 1 2 3 4 5 6 7 8 9 10 11 12 ASL 成功 =1/81+2+1+1+2+1+1+1 ）=1.25 2 20 20 45 45 10 40 45 10 40 55 58 20 58 10 40 55 68 删除了 40和58后，结果如下： 45 58 45 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 9 页8 / 9 45 27 52 19 68 root 10 20 55 68 10 20 55 58 五算法阅读题 p!=NULL (2 !=NULL (3 p-next=q-next (4 p=q-next (5 r-next 2 (1 实现在二叉排序树上的插入操作：若二叉排序树上不存在，则插入；若二叉排序树上已存在，不插入，仅给出提示信息“The node exists in the binary tree!” (2 48 六算法设计题 LinkList q, pa。q=ha 。 pa=ha-next。while(pa if(pa-exp=0 q-next=pa-next 。free(pa。 pa=q。 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 9 页9 / 9 else pa-coef=pa-coef*pa-exp 。pa-exp= pa-exp-1 。 q=pa。 pa= pa-next 。 2. typedef struct node ElemType data。struct node *lchild, *rchild。BiNode, *BiTree。int f(BiTree T int y。 if(T=NULL y=0。else y1=f(T-lchild。y2=f(T-rchild。if(y1y2 y=y1+1。else y=y2+1。 return y。 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 9 页