2014年韩山师范学院本科插班生考试《数据结构》课程试卷

（A卷）第 1 页 共 8 页

韩山师范学院2014年本科插班生考试试卷

计算机科学与技术专业 数据结构 试卷（A卷）

题号 得分 得分 评卷人 一、 单项选择题（每题2分，共30分）

题号 答案 1 2 12 3 13 4 14 5 15 6 7 8 9 10 一 二 三 四 五 六 总分 评卷人 题号 11 答案 1. 栈和队列的共同特点是( A )。

A. 只允许在端点处插入和删除元素 B. 都是先进后出 C. 都是先进先出 D. 没有共同点 2. 用链接方式存储的队列，在进行插入运算时( D )。 A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D. 头、尾指针可能都要修改 3. 以下数据结构中哪一个是非线性结构？( D )

A. 队列 B. 栈 C. 线性表 D. 二叉树 4. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644，A[2][2]存放

位置在676，每个元素占一个空间，问A[3][3]存放在什么位置？( C ) A．688 B．678 C．692 D．696

//对的.676+(676-644)/2 A[2][2]与A[0][0] 相差两排零2个元素 （A卷）第 2 页 共 8 页

A[3][3]与A[2][2] 相差一排零1个元素 因为元素的地址是连续的 5. 树最适合用来表示( C )。

A.有序数据元素 B.无序数据元素

C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6. 二叉树的第k层的结点数最多为( D )。

A．2k-1 B.2K+1 C.2K-1 D. 2

7. 设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，

则下列属于该有向图G的一种拓扑排序序列的是（ A ）。 A. 1,2,3,4

B. 2,3,4,1

C. 1,4,2,3

D. 1,2,4,3

k-1

//拓扑排序，每个结点的所有前驱结点都排在该结点的前面。

有向无环图中，拓扑排序： 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）进行散列存储时，若选

用H（K）=K % 9作为散列函数，则散列地址为1的元素有（ D ）个。 A．1 B．2 C．3 D．4

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;

（A卷）第 3 页 共 8 页

12. 线性表采用链式存储时，结点的存储地址（ B ）。 A．必须是不连续的 B．连续与否均可

C．必须是连续的 D．和头结点的存储地址相连续

13. 任何一个无向连通图的最小生成树（ B ）。

A. 只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在 14. 设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操

作为（ A ）。 A. p->next=p->next->next C. p=p->next->next

B. p=p->next D. p->next=p

15. 设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍

历该二叉树得到序列为（ B ）。 A. BCDA 得分 评卷人 二、填空题（每空2分，共20分）

1. 一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为__O(n)__。 2. 假定一棵树的广义表表示为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 B. BADC C. CDAB D. CBDA

4. 若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右

孩子的两个指针。在这种存储结构中，n个结点的二叉树共有___2n__个指针域，其中有_______n+1____个指针是空指针。 5. 有如下递归函数： void f( int w ) { int i;