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

（A 卷）第1 页 共 6 页2015年韩山师范学院本科插班生考试试卷计算机科学与技术专业数据结构试卷（ A卷）一、单项选择题（每题2 分，共 30 分）1. 栈和队列的共同特点是 ( )。A. 只允许在端点处插入和删除元素 B. 都是先进后出C. 都是先进先出 D. 没有共同点2. 用链接方式存储的队列，在进行插入运算时( )。 A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D. 头、尾指针可能都要修改3. 以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树4. 设有一个二维数组Amn ，假设 A00存放位置在 644，A22存放位置在 676，每个元素占一个空间，问A33存放在什么位置？ A688 B678 C692 D696 5. 树最适合用来表示 ( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据6. 二叉树的第 k 层的结点数最多为 ( )。 A2k-1 B.2K+1 C.2K-1 D. 2k-1 7. 设有向无环图 G中的有向边集合 E=，则下列属于该有向图G的一种拓扑排序序列的是（）。A. 1,2,3,4 B. 2,3,4,1 C. 1,4,2,3 D. 1,2,4,3 8. 下列关于数据结构的叙述中，正确的是（）。 A. 数组是同类型值的集合 B. 树是一种线性结构 C. 一般情况下递归算法的程序结构更为精炼、效率更高 D. 用一维数组存储二叉树，总是以先序遍历的顺序存储各结点名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 6 页 - - - - - - - - - （A 卷）第2 页 共 6 页9. 对于线性表（ 7，34，55，25，64，46，20，10）进行散列存储时，若选用 H（K）=K % 9 作为散列函数，则散列地址为1 的元素有（）个。 A 1 B2 C3 D4 10. 设有 6 个结点的无向图，该图至少应有 ( )条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8 11. 在带有头结点的单链表HL中，要向表头插入一个由指针p 指向的结点，则执行 ( )。A. p-next=HL-next; HL-next=p; B. p-next=HL; HL=p; C. p-next=HL; p=HL; D. HL=p; p-next=HL; 12. 线性表采用链式存储时，结点的存储地址（）。 A 必须是不连续的 B连续与否均可 C 必须是连续的 D和头结点的存储地址相连续13. 任何一个无向连通图的最小生成树（）。A. 只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在14. 设指针变量 p 指向单链表结点A，则删除结点 A 的后继结点 B需要的操作为（）。A. p-next=p-next-next B. p=p-next C. p=p-next-next D. p-next=p 15. 设某棵二叉树的中序遍历序列为ABCD ，前序遍历序列为 CABD ，则后序遍历该二叉树得到序列为（）。A. BCDA B. BADC C. CDAB D. CBDA 二、填空题（每空2 分，共 20 分）1. 一个算法的时间复杂度为 (n3+n2log2n+14n)/n2， 其数量级表示为 _。2. 假定一棵树的广义表表示为A（C ，D （E，F，G ） ，H（I ，J） ） ，则该树的深度为 _ ，树的度为 _ 。3. 后缀算式 9 2 3 +- 10 2 / -的值为 _ 。中缀算式（ 3+4X）-2Y/3对应的后缀算式为 _ 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 6 页 - - - - - - - - - （A 卷）第3 页 共 6 页4. 若用链表存储一棵二叉树时， 每个结点除数据域外， 还有指向左孩子和右孩子的两个指针。在这种存储结构中，n 个结点的二叉树共有 _个指针域，其中有 _ 个指针是空指针。5. 有如下递归函数：void f( int w ) int i; static int j=1; if (w0) printf(“%d:”,j+); for ( i=1; itop=M-1) printf(“overflow ”);else _; _; 2下面算法是求二叉树双支个数的算法。请完成填空。struct TreeNode int data; struct TreeNode *left, *right; ; int fnGetLeaf( TreeNode *T ) if(_) return 0; if( T-left!=NULL & T-right!=NULL) return (_); 得分评卷人名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 6 页 - - - - - - - - - （A 卷）第5 页 共 6 页 else return(_); 五、分析简答题（10 分）1（4 分）试写出如图所示的二叉树分别按中序、后序遍历时得到的结点序列。2. （6 分）用序列（ 46，68，45，139，70，58，101，10，88，94）建立一个二叉排序树，画出该树，并求在等概率情况下查找成功的平均查找长度。得分评卷人名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - （A 卷）第6 页 共 6 页六、算法设计题（ 20 分）1、（8 分）删除顺序表前i 个元素。已知顺序表的数据结构如下：#define MaxSize 100 typedef struct int dataMaxSize; int last; SeqList; 使用如下函数原型：bool fnDelete( SeqList *L, int i ); / 成功删除则返回 true ，否则返回 false 2、 (12 分) 假设二叉树采用左右孩子指针存储结构，即其结点数据类型描述为：struct TreeNode int data;/数据域 struct TreeNode *left, *right;/指向其左右孩子结点; 试编写一个函数，要在一棵树Tree 中，找出最大值。函数原型如下：bool fnGetMax( struct TreeNode *Tree, int *max ); / 找到最大值则返回true ，否则返回 false; 得分评卷人名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -