(完整word版)2015年韩山师范学院本科插班生《数据结构》试卷

（A卷）第 1 页 共 6 页

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

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

一、 单项选择题（每题2分，共30分） 1. 栈和队列的共同特点是( )。

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

A. 队列 B. 栈 C. 线性表 D. 二叉树

4. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644，A[2][2]存放

位置在676，每个元素占一个空间，问A[3][3]存放在什么位置？ A．688 B．678 C．692 D．696 5. 树最适合用来表示( )。

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

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

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

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

则下列属于该有向图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. 用一维数组存储二叉树，总是以先序遍历的顺序存储各结点

（A卷）第 2 页 共 6 页

9. 对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选

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

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 C. p=p->next->next

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

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

历该二叉树得到序列为（ ）。 A. BCDA

二、填空题（每空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

对应的后缀算式为_______________________________。

B. BADC

C. CDAB

D. CBDA

（A卷）第 3 页 共 6 页

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

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

static int j=1; if (w>0){

printf(“%d:”,j++);

for ( i=1; i<=w; i++ ) printf( “%d，”, w ); printf( “\\n” );

f( w ?1 ); }

}

调用语句f(3)的结果是______________________________。

6. 已知一有向图的邻接表存储结构如下：从顶点1出发，DFS遍历的输出序列是______________，BFS遍历的输出序列是________________。

得分 评卷人 三、判断题（对的划√，错的划×。每小题1分，共10

分）

（ ）1．调用一次深度优先遍历可以访问到图中的所有顶点。 （ ）2．哈夫曼树上只有树叶或者双支结点。

（ ）3．冒泡排序在初始关键字序列为递减有序的情况下执行的交换次数

最多。

（ ）4．满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。