《(完整版)2018年韩山师范学院本科插班生考试试题《数据结构》A试卷.pdf》由会员分享，可在线阅读，更多相关《(完整版)2018年韩山师范学院本科插班生考试试题《数据结构》A试卷.pdf（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、（A 卷）第1 页 共 8 页韩山师范学院 2018年本科插班生考试试卷计算机科学与技术专业数据结构试卷（ A 卷）题号一二三四五六总分评卷人得分一、单项选择题（每题2 分，共 30 分）1. 数据的最小单位是（B ）。A. 数据元素B.数据项C.数据类型D. 数据变量2. 一个栈的输入序列为A B C，则下列序列中不可能是栈的输出序列的是( C)。A. B C A B.C B A C. C A BD. A B C 3 程序段 s=i=0； do i=i+1 ；s=s+i； while(inext；p-next=q-next；free(q)；B. q=p-next；p-data=q-data
2、；free(q)；C. q=p-next；p-data=q-data ；p-next=q-next；free(q)；D. q=p-next；q-data=p-data ；p-next=q-next；free(q)；7设有一个二维数组Amn，假设 A00 存放位置在 644(10)，A22存放位置在 676(10)， 每个元素占一个空间， 问 A33(10)存放在什么位置？脚注(10)表示用 10 进制表示（B ）。得分评卷人精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 8 页 - - - -
3、 - - - - - - （A 卷）第2 页 共 8 页A. 696 B. 692C.688 D. 678 /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)/28设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以 20 为基准记录的一趟快速排序
4、结束后的结果为( 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设某棵二叉树中有2000 个结点，则该二叉树的最小高度为（C ）。A.9 B. 10 C.11D. 12 10数组的逻辑结构不同于下列（A）的逻辑结构。A. 树B. 栈C. 队列D. 线性表11根据二叉树的定义可知二叉树共有（B）种不同的形态。A.4 B. 5C. 6 D. 7 12设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（A）
5、。A.head=0B. head-next=0 C. head-next=head D.head!=0 / 注意：不论是带头结点的链表还是不带头结点的链表，头指针head都指向链表中的第一个结点。如果该链表有头结点，则头指针head 指向头结点，如果没有头结点，则头指针head 指向链表的第一个节点。1 带头结点的单链表中头指针head 指向头结点，头结点的值域不含任何信息， 从头结点的后继结点开始存储信息。 头指针 head始终不等于 NULL ，head-next 等于 NULL的时候链表为空。2 不带头结点的单链表中的头指针head 直接指向开始结点，当head 等于 NULL的时候链表
6、为空。头结点的存在，使得空链表与非空链表的处理变得一直，也方便了对链表的开始结点插入或删除操作。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 8 页 - - - - - - - - - - （A 卷）第3 页 共 8 页13设用邻接矩阵 A 表示有向图 G 的存储结构，则有向图G 中顶点 i 的入度为（B ）。A.第 i 行非 0 元素的个数之和B. 第 i 列非 0 元素的个数之和C.第 i 行 0 元素的个数之和D. 第 i 列 0 元素的个数之和14设无向图G 中有 n 个顶点，则该无
7、向图的最小生成树上有（C ）条边。A. 2n 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_； 若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有_个空指针域。3. 设指针 p 指向单链表中结点A，指针 s 指向被插入的结点X，
8、则在结点 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/ 深度优先是从某个顶点出发，访问完后，寻找一个未访问的邻接顶点继得分评卷人精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 3 页，共 8 页 - - - - - - - - - - （A 卷）
9、第4 页 共 8 页续深度优先，如果此路不同就往回退，所以看邻接表，首先访问V1，完了后顺链寻找没有访问的邻接顶点，自然链表中的第一个结点就是v3，接着转到 v3 再来深度优先，访问v3 后，在其链表中第一个邻接顶点是v4 接着访问 v4，下面走不通，回到v3，继续顺链往后，自然是v5，v5 的邻接顶点中 v2 还没有访问所以序列为 v1, v3, v4, v5, v2 再看广度优先，从某个顶点完成后，需要一口气将其邻接未访问的所有顶点都访问，后面类推于是过程是先 v1，再顺链将 v3，v2 依次访问完， 然后再依次访问 v3 和v2 的各个未访问邻接顶点， v3 链表中顺链可以访问v4，v5
10、，所以最后访问序列为 v1, v3, v2, v4, v55. 解决散列表冲突的两种方法是_开放定址法 _和_链地址法 _。三、判断题（对的划，错的划。每小题1 分，共 10 分）（）1调用一次深度优先遍历可以访问到图中的所有顶点。（）2. 设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。/因为不知道左右孩子。所以如果已知中序，只需要一个前序或者后序就可以确定二叉树了（）3快速排序是排序算法中平均性能最好的一种排序。（ ）4不论是入队列操作还是入栈操作，在顺序存储结构上都需得分评卷人精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳
11、 - - - - - - - - - -第 4 页，共 8 页 - - - - - - - - - - （A 卷）第5 页 共 8 页要考虑“溢出”情况。（ ）5线性表中的所有元素都有一个前驱元素和后继元素。（ ）6.分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。/分块查找 : 即又称索引顺序查找, 这是顺序查找的一种改进的方法. 在此查找法中, 除表本身以外 , 尚需建立一个 索引表, 其包含两项内容 : 关键字项( 其值为该字表中最大的关键字) 和指针项 ( 指示该字表的第一个记录在表中的位置). 所谓分块指的是第二个子表中
12、所有的关键字都比第一个表中的关键字大, 同理, 第三个字表都大于第二个字表中的所有的关键字. 通常, 分块查找的过程需要分两步 : 先确定待查记录所在的块 ( 字表), 然后在块中顺序查找 . （ ）7向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。（ ）8不论线性表采用顺序存储结构还是链式存储结构，删除值为X 的结点的时间复杂度均为O(n)。（ ）9子串“ ABC”在主串“ AABCABCD ”中的位置为 2。（ ）10用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。四、程序填空题（每个空2 分，共 10 分）1.下面程序段的功能是实现冒泡
13、排序算法，请在下划线处填上正确的语句。void bubble(int rn) for(i=1;i=n-1; i+) 得分评卷人精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 5 页，共 8 页 - - - - - - - - - - （A 卷）第6 页 共 8 页for(exchange=0,j=0; jrj+1)temp=rj+1;_;rj=temp;exchange=1; if (exchange=0) return； 2. 如下为二分查找的非递归算法，试将其填写完整。Int Binsch(ElemT
14、ype A ,int n,KeyType 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 得分评卷人精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳
15、- - - - - - - - - -第 6 页，共 8 页 - - - - - - - - - - （A 卷）第7 页 共 8 页2. （10 分）一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设散列表为HT0.12，散列函数为 H（key）= key % 13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 7 页，共 8 页 - - - - - - - - - - （A 卷）第8 页 共 8 页六、 算法设计题（ 10分）1. 设计两个有序单链表的合并排序算法。得分评卷人精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 8 页，共 8 页 - - - - - - - - - -