2022年韩山师范学院本科插班生考试试题《数据结构》试卷 .docx

《2022年韩山师范学院本科插班生考试试题《数据结构》试卷 .docx》由会员分享，可在线阅读，更多相关《2022年韩山师范学院本科插班生考试试题《数据结构》试卷 .docx（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品_精品资料_（A 卷）第 1 页 共 8 页韩山师范学院 2022 年本科插班生考试试卷题号运算机科学与技术专业数据结构试卷（ A 卷）一二三四五六总分评卷人得分得分评卷人一、单项选择题（每题2 分,共 30 分）B ）.1. 数据的最小单位是（A. 数据元素B.数据项C.数据类型D. 数据变量可编辑资料 - - - 欢迎下载精品_精品资料_2. 一个栈的输入序列为是 C.可编辑资料 - - - 欢迎下载精品_精品资料_A B C ,就以下序列中不行能是栈的输出序列的可编辑资料 - - - 欢迎下载精品_精品资料_A. B C A B.C B A C. C A BD. A B C 3程序段

2、 s=i=0.do i=i+1 . s=s+i.whileinext.p-next=q-next.freeq.B. q=p-next.p-data=q-data.freeq.C. q=p-next.p-data=q-data.p-next=q-next.freeq.D. q=p-next.q-data=p-data.p-next=q-next.freeq.可编辑资料 - - - 欢迎下载精品_精品资料_7设有一个二维数组可编辑资料 - - - 欢迎下载精品_精品资料_Am n,假设 A00 存放位置在 64410,A22可编辑资料 - - - 欢迎下载精品_精品资料_存放位置在 67610,每

3、个元素占一个空间, 问 A33 10存放在什么位置？脚注 10表示用 10 进制表示（B ）.可编辑资料 - - - 欢迎下载精品_精品资料_A. 696 （A 卷）第2 页 共 8 页D. 678 B. 692C.688 /c, 对的 .676+676-644/2 A22 与 A00 相差两排零2 个元素A33 与 A22 相差一排零1 个元素由于元素的的址是连续的所以 A22 与 A00 的的址差是 A33 与 A22 的址差的 2 倍A22 与 A00 的的址差是 676-644 A33 与 A22 的址差是 676-644/2 所以 A33 的的址是 676+676-644/2可编辑资

4、料 - - - 欢迎下载精品_精品资料_8设一组初始关键字记录关键字为可编辑资料 - - - 欢迎下载精品_精品资料_20,15,14,18,21,36,40,10,可编辑资料 - - - 欢迎下载精品_精品资料_就以 20 为基准记录的一趟快速排序终止后的结果为 D .A. 15,10,14,18,20,36,40,21 B.10,15,14,18,20,40,36,21 C. 10,15,14,20,18,40,36,2l D. 10,15,14,18,20,36,40,21 9设某棵二叉树中有 2022 个结点,就该二叉树的最小高度为（C ）.A.9 B. 10 C.11 D. 12 1

5、0数组的规律结构不同于以下（A）的规律结构.A. 树 B. 栈 C. 队列 D. 线性表11依据二叉树的定义可知二叉树共有（B）种不同的形状.A.4 B. 5 C. 6 D. 7 可编辑资料 - - - 欢迎下载精品_精品资料_12设一条单链表的头指针变量为条件是（A）.可编辑资料 - - - 欢迎下载精品_精品资料_head且该链表没有头结点,就其判空可编辑资料 - - - 欢迎下载精品_精品资料_A.head=0B. head-next=0 C. head-next=head D.head.=0 / 留意：不论是带头结点的链表仍是不带头结点的链表,头指针 head 都指 向链表中的第一个结

6、点.假如该链表有头结点,就头指针 head 指向头结可编辑资料 - - - 欢迎下载精品_精品资料_点,假如没有头结点,就头指针 1 带头结点的单链表中头指针可编辑资料 - - - 欢迎下载精品_精品资料_head 指向链表的第一个节点.head 指向头结点, 头结点的值域不含任何可编辑资料 - - - 欢迎下载精品_精品资料_信息,从头结点的后继结点开头储备信息. 头指针 head 始终不等于 NULL,head-next 等于 NULL的时候链表为空.2 不带头结点的单链表中的头指针head 直接指向开头结点,当head 等于 NULL的时候链表为空.头结点的存在,使得空链表与非空链表的处

7、理变得始终,也便利了对链表的开头结点插入或删除操作.可编辑资料 - - - 欢迎下载精品_精品资料_（A 卷）第 3 页 共 8 页13设用邻接矩阵 A 表示有向图 G 的储备结构,就有向图 G 中顶点 i 的入度为（B ）.可编辑资料 - - - 欢迎下载精品_精品资料_A.第 i 行非 0 元素的个数之和 C.第 i 行 0 元素的个数之和可编辑资料 - - - 欢迎下载精品_精品资料_B. 第 i 列非 0 元素的个数之和 D. 第 i 列 0 元素的个数之和可编辑资料 - - - 欢迎下载精品_精品资料_14设无向图G 中有 n 个顶点,就该无向图的最小生成树上有（C ）条边.A. 2

8、n B. 2n-1 C. n-1D. n 15.由权值分别为 11,8,6,2,5 的叶子结点生成一棵哈夫曼树,它的带权路径长度为（D）A. 24 B. 48 C. 53 D. 71 得分 评卷人 二、填空题（每空 2 分,共 20 分）1数据的物理结构主要包括 _次序储存结构 _和_链式储备结构 _两种情况.2.设某棵二叉树中度数为 0 的结点数为 N0,度数为 1 的结点数为 N1,就该二叉树中度数为 2 的结点数为 _N0-1_.如接受二叉链表作为该可编辑资料 - - - 欢迎下载精品_精品资料_二叉树的储备结构,就该二叉树中共有可编辑资料 - - - 欢迎下载精品_精品资料_个空指针域

9、.可编辑资料 - - - 欢迎下载精品_精品资料_3. 设指针 p 指向单链表中结点 A,指针 s 指向被插入的结点 X,就在结点 A 的前面插入结点 X 时的操作序列为：1 s-next=_p-next_.2 p-next=s.3 t=p-data.4 p-data=_s_.5 s-data=t.4. 已知一有向图的邻接表储备结构如下：从顶点 1 动身, DFS 遍历的输出序列是 13452 ,BFS 遍历的输出序列是 13245/ 深度优先是从某个顶点动身,拜望完后,查找一个未拜望的邻接顶点继可编辑资料 - - - 欢迎下载精品_精品资料_（A 卷）第 4 页 共 8 页续深度优先,假如此

10、路不同就往回退,所以看邻接表,第一拜望 V1 ,完了后顺链查找没有拜望的邻接顶点,自然链表中的第一个结点就是 v3 ,可编辑资料 - - - 欢迎下载精品_精品资料_接着转到 v3 再来深度优先,拜望 v4 可编辑资料 - - - 欢迎下载精品_精品资料_v3 后,在其链表中第一个邻接顶点是可编辑资料 - - - 欢迎下载精品_精品资料_接着拜望 v4,下面走不通,回到v3 ,连续顺链往后,自然是v5 ,v5 的邻接顶点中 v2 仍没有拜望所以序列为 v1, v3, v4, v5, v2 再看广度优先,从某个顶点完成后,需要一口气将其邻接未拜望的全部顶点都拜望,后面类推于是过程是先 v1 ,再

11、顺链将 v3,v2 依次拜望完, 然后再依次拜望 v3 和v2 的各个未拜望邻接顶点, v3 链表中顺链可以拜望 v4 ,v5 ,所以最终拜望序列为 v1, v3, v2, v4, v5可编辑资料 - - - 欢迎下载精品_精品资料_5. 解决散列表冲突的两种方法是可编辑资料 - - - 欢迎下载精品_精品资料_开放定址法 _和_链的址法 _.可编辑资料 - - - 欢迎下载精品_精品资料_得分评卷人三、判定题（对的划,错的划 .每道题1 分,共 10 分）（）1调用一次深度优先遍历可以拜望到图中的全部顶点.（）2. 设一棵二叉树的先序序列和后序序列,就能够唯独确定出该二叉树的形状./由于不知

12、道左右孩子.所以假如已知中序,只需要一个前序或者后序就可以确定二叉树了（）3快速排序是排序算法中平均性能最好的一种排序.（ ）4不论是入队列操作仍是入栈操作,在次序储备结构上都需可编辑资料 - - - 欢迎下载精品_精品资料_（A 卷）第 5 页 共 8 页要考虑“ 溢出” 情形.（ ）5线性表中的全部元素都有一个前驱元素和后继元素.（ ）6.分块查找的基本思想是第一在索引表中进行查找,以便确定给定的关键字可能存在的块号,然后再在相应的块内进行次序查找./ 分块查找 : 即又称索引次序查找, 这是次序查找的一种改进的方法. 在此查找法中 , 除表本身以外 , 尚需建立一个 索引表 , 其包含两

13、项内容 : 关键字项 其值为该字表中最大的关键字 和指针项 指示该字表的第一个记录在表中的位置 . 所谓分块指的是其次个子表中全部的关键字都比第一个表中的关键字大 , 同理, 第三个字表都大于其次个字表中的全部的关键字 . 通常 , 分块查找的过程需要分两步 : 先确定待查记录所在的块 字表, 然后在块中次序查找 . （ ）7向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度.（ ）8不论线性表接受次序储备结构仍是链式储备结构,删除值为X 的结点的时间复杂度均为 On.（ ）9子串“ABC ” 在主串“AABCABCD ” 中的位置为 2.（ ）10用邻接矩阵作为图的储备结构时,就

14、其所占用的储备空间与图中顶点数无关而与图中边数有关.得分 评卷人 四、程序填空题（每个空 2 分,共 10 分）1. 下面程序段的功能是实现冒泡排序算法,请在下划线处填上正确的语句.void bubbleint rn fori=1;i=n-1; i+ 可编辑资料 - - - 欢迎下载精品_精品资料_（A 卷）第 6 页 共 8 页forexchange=0,j=0; jrj+1temp=rj+1;_;rj=temp;exchange=1; if exchange=0 return. 2. 如下为二分查找的非递归算法,试将其填写完整.Int BinschElemType A ,int n,Key

15、Type K int low=0; int high=n-1; while low=high int mid=_.if K=Amid.key return mid; /查找成功,返回元素的下标else if Kmid.key 可编辑资料 - - - 欢迎下载精品_精品资料_; 可编辑资料 - - - 欢迎下载精品_精品资料_/在左子表上连续查找可编辑资料 - - - 欢迎下载精品_精品资料_else _; /在右子表上连续查找 return -1; /查找失败,返回 -1 得分评卷人五、分析简答题（共20 分）1（10 分）求 AOE 网的关键路径.关键路径： v0,v1,v4,v3,v6 可

16、编辑资料 - - - 欢迎下载精品_精品资料_（A 卷）第 7 页 共 8 页可编辑资料 - - - 欢迎下载精品_精品资料_2. （10 分）一个线性表为可编辑资料 - - - 欢迎下载精品_精品资料_B=（12,23,45,57,20,03,78,31,15,可编辑资料 - - - 欢迎下载精品_精品资料_36）,设散列表为 HT0.12 ,散列函数为 H（key）= key % 13 并用线性探查法解决冲突,请画出散列表,并运算等概率情形下查找成功的平均查找长度.可编辑资料 - - - 欢迎下载精品_精品资料_得分评卷人（A 卷）第8 页 共 8 页六、 算法设计题（ 10 分）1. 设计两个有序单链表的合并排序算法.可编辑资料 - - - 欢迎下载