20XX年韩山师范学院本科插班生考试《数据结构》课程试卷38568.pdf

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

1、20 xx 年韩山师范学院本科插班生考试 数据结构课程试卷 韩山师范学院 20 xx 年本科插班生考试试卷 计算机科学与技术专业 数据结构 试卷（A 卷）一、单项选择题（每题 2 分，共 30 分）1.栈和队列的共同特点是(A )。A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时(D )。A.仅修改头指针 B.头、尾指针都要修改 C.仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构？(D )A.队列 B.栈 C.线性表 D.二叉树 4.设有一个二维数组 Amn，假设 A00存放位置在

2、644，A22存放 位置在 676，每个元素占一个空间，问 A33存放在什么位置？(C )A 688 B 678 C 692 D 696/对的.676+(676-644)/2 A22与 A00 相差两排零 2 个元素 A33与 A22 相差一排零 1 个元素 因为元素的地址是连续的 5.树最适合用来表示(C )。A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6.二叉树的第 k 层的结点数最多为(D )。A2k-1 B.2K+1 C.2K-1 D.2k-1 7.设有向无环图 G 中的有向边集合 E=，则下列属于该有向图 G 的一种拓扑排序序列的

3、是（A）。A.1,2,3,4 B.2,3,4,1 C.1,4,2,3 D.1,2,4,3/拓扑排序，每个结点的所有前驱结点都排在该结点的前面。有向无环图中，拓扑排序：1.包含所有顶点 2.若序列有顶点 A 在 B 的前面，则图不存在 B-A 的边。即，若图中存在 B-A，则 B 在 A 的前面故 BCD 不对 8.下列关于数据结构的叙述中，正确的是（A）。A.数组是同类型值的集合 B.树是一种线性结构 C.一般情况下递归算法的程序结构更为精炼、效率更高 D.用一维数组存储二叉树，总是以先序遍历的顺序存储各结点 9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选

4、用 H（K）=K%9 作为散列函数，则散列地址为 1 的元素有（D）个。A1 B2 C3 D4 10.设有 6 个结点的无向图，该图至少应有(A)条边才能确保是一个连通图。A.5 B.6 C.7 D.8 11.在带有头结点的单链表 HL 中，要向表头插入一个由指针 p指向的结点，则执行(A)。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.线性表采用链式存储时，结点的存储地址（B）。A必须是不连续的 B连续与否均可 C必须是连续的 D和头结点的存储地址相连续 13.任何一个无向连通

5、图的最小生成树（B）。A.只有一棵 B.一棵或多棵 C.一定有多棵 D.可能不存在 xx.设指针变量 p 指向单链表结点 A，则删除结点 A 的后继结点B 需要的操 作为（A）。A.p-next=p-next-next B.p=p-next C.p=p-next-next D.p-next=p 15.设某棵二叉树的中序遍历序列为 ABCD，前序遍历序列为CABD，则后序遍 历该二叉树得到序列为（B）。A.BCDA B.BADC C.CDAB D.CBDA 二、填空题（每空 2 分，共 20 分）n+xxn)/n2，其数量级表示为_O(n)_。1.一个算法的时间复杂度为(n3+n2log 2 2

6、.假定一棵树的广义表表示为 A（C，D（E，F，G），H（I，J），则该树 的深度为_3_，树的度为_3_。3.后缀算式 9 2 3+-10 2/-的值为_-1_。中缀算式（3+4X）-2Y/3 对应的后缀算式为_3 4 X*+2 Y*3/-_。/像这样的（9 3 1-3*+10 2/+）后缀表达式怎么样求值呢？遇到符号，就算前面两个数 9 3 1-3*+10 2/+9 2 3*+10 2/+9 6+10 2/+15 10 2/+15 5+20 4.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右 孩子的两个指针。在这种存储结构中，n 个结点的二叉树共有_2n_个指针域，其中有

7、_n+1_个指针是空指针。5.有如下递归函数：void f(int w)int i;static int j=1;if(w0)printf(“%d:”,j+);for(i=1;iprintf(“n”);f(w 1);调用语句 f(3)的结果是_。6.已知一有向图的邻接表存储结构如下：从顶点 1 出发，DFS遍历的输出序列是_（1,3,4,5,2）_，BFS 遍历的输出序列是_（1,3,2,4,5）_。/DFS 是深度优先搜索，则从顶点 1 出发，搜索 3，3 继续搜索 4，4 邻接顶点为空，则返回上一层 3 搜索 5，5 继续搜索 2，故输出：1-3-4-5-2 BFS 是广度优先搜索，则顶点

8、 1 出发，搜索 3、2、4，接着搜索3 的顶点 5，故输出：1-3-2-4-5 深度优先是从某个顶点出发，访问完后，寻找一个未访问的邻接顶点继续深度优先，如果此路不同就往回退，所以看邻接表，首先访问 V1，完了后顺链寻找没有访问的邻接顶点，自然链表中的第一个结点就是 v3，接着转到 v3 再来深度优先，访问 v3 后，在其链表中第一个邻接顶点是 v4 接着访问 v4，下面走不通，回到 v3，继续顺链往后，自然是 v5，v5 的邻接顶点中 v2 还没有访问所以序列为 v1,v3,v4,v5,v2 再看广度优先，从某个顶点完成后，需要一口气将其邻接未访问的所有顶点都访问，后面类推 于是过程是先

9、v1，再顺链将 v3，v2 依次访问完，然后再依次访问 v3 和 v2 的各个未访问邻接顶点，v3 链表中顺链可以访问 v4，v5，所以最后访问序列为 v1,v3,v2,v4,v5 三、判断题（对的划，错的划。每小题 1 分，共 10 分）（）1调用一次深度优先遍历可以访问到图中的所有顶点。（）2哈夫曼树上只有树叶或者双支结点。（）3冒泡排序在初始关键字序列为递减有序的情况下执行的交换次数最多。（）4满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（）5已知一棵二叉树的先序序列和后序序列，则能够唯一确定该二叉树的形状。（）6层次遍历二叉树需要用到堆栈作为辅助结构。/队列（）7一棵树按孩子

10、兄弟法转化成二叉树，该二叉树中一定没有右子树。（）8线性表的顺序存储结构比链式存储结构更好。（一）顺序存储结构和链式存储结构的优缺点比较，以及使用情况。1 优缺点 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。优点：存储密度大（1），易于查找和修改。缺点：插入或删除元素时不方便；存储空间利用率低，预先分配内存可能造成存储空间浪费。链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分 存放表示结点间关系的指针 优点：插入或删除元素时很方便，使用灵活，存储空间利用率高。缺点：存储密度小（1），查找和修改需要遍历整个链表。