2015年本科插班生考试《数据结构》课程试卷

（A卷）第 1 页 共 8 页

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

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

题号 得分

一 二 三 四 五 六 总分 评卷人 得分 评卷人 一、单项选择题（每题2分，共30分）

1．以下说法正确的是（ ）。

A．数据元素是数据的最小单位。 B．数据项是数据的基本单位。

C．数据结构是带有结构的各数据项的集合。

D．一些表面上很不相同的数据可以有相同的逻辑结构。

2．在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（ ）。

A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）

B．在第i个结点后插入一个新结点（1≤i≤n） C．删除第i个结点（1≤i≤n） D．将n个结点从小到大排序

3．线性表Ｌ在（ ）情况下适用于使用链式结构实现。

A．需经常修改Ｌ中的结点值 B.需要不断对Ｌ进行删除插入 C．Ｌ中含有大量的结点 D.Ｌ中结点结构复杂

4．若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现的情况是（ ）

A．5，4，3，2，1 B．2，1，5，4，3 C．4，3，1，2，5 D．2，3，5，4，1

5．为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据

1

（A卷）第 2 页 共 8 页

缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。 A．队列 B．栈 C．线性表 D．有序表 6．串下面关于串的的叙述中，（ ）是不正确的。

A．串是字符的有限序列 B．空串是由空格构成的串

C．模式匹配是串的一种重要运算

D．串既可以采用顺序存储，也可以采用链式存储

7．把一棵树转换为二叉树后，这棵二叉树的形态是（ ）。

A.唯一的 B.有多种

C.有多种，但根结点都没有左孩子 D.有多种，但根结点都没有右孩子

8．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）。

A．250 B． 500 C．254 D．501 9．下面（ ）算法适合构造一个稠密图G的最小生成树。

A．Prim算法 B．Kruskal算法 C．Floyd算法 D．Dijkstra算法

10．已知图的邻接矩阵如图1. 所示，则从顶点0出发按深度优先遍历的

结果是（ ）

?0?1??1??1?1??0??1111100110000100101100011100001?01??00??10?10??01?10??图1.

A．0 2 4 3 1 5 6 B．0 1 3 6 5 4 2 C．0 1 3 4 2 5 6 D．0 3 6 1 5 4 2

11．已知图的邻接表如图2. 所示，则从顶点0出发按深度优先遍历的结

2

（A卷）第 3 页 共 8 页

果是（ ）。

图2.

A．0 1 3 2 B．0 2 3 1 C．0 3 2 1 D．0 1 2 3 12．下面（ ）方法可以判断出一个有向图是否有环。

A．深度优先遍历 B．拓扑排序 C．求最短路径 D．求关键路径

13．适用于折半查找的表的存储方式及元素排列要求为（ ）。

A．链接方式存储，元素无序 B．链接方式存储，元素有序 C．顺序方式存储，元素无序 D．顺序方式存储，元素有序 14．下面关于哈希查找的说法，正确的是（ ）。

A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小 B．除留余数法是所有哈希函数中最好的 C．不存在特别好与坏的哈希函数，要视情况而定 D．哈希表的平均查找长度有时也和记录总数有关

15．对n个关键字作快速排序，在最坏情况下，算法的时间复杂度是（ ）。

A．O(n) B．O(n2) C．O(nlog2n) D．O(n3) 得分 评卷人 二、填空题（每空2分，共20分）

1．后缀算式4 2 3 * + 10 5 / -的值为__________

2．对于一个具有9个结点的二叉树的最小深度为__________，最大深度为__________。

3．有一矩阵为a[-3:1,2:6]，每个元素占一个存储单元，存储的首地址为100，以行序为主，则元素a(-1,4)的地址为____________。 4．对于二叉排序树的查找，若根结点元素的键值大于被查找元素的键值，则应该在该二叉树的____________上继续查找。

3

（A卷）第 4 页 共 8 页

5. 遍历图的基本方法有深度优先搜索和广度优先搜索。其中，____________是一个递归过程。

6. 在一个具有n个顶点的无向图中，要连通所有顶点则至少需要____________条边。

7. 已知一有序表（13，20，25，37，48，58，61，78，83，90，128），当使用折半查找法查找值48的元素时，经过____________次比较后查找成功。

8. 在快速排序、堆排序、归并排序中，____________排序是稳定的。 9. 设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为____________。 得分 评卷人 三、判断题（对的划√，错的划×。每小题1分，共10分）

（ ）1．在快速排序算法中，取待排序的n个记录中的某个记录（如

第一个记录）的键值为基准，将所有记录分为两组，此记录就排在这两组的中间，这也是此记录的最终位置。

（ ）2．在一个有向图的邻接表中，如果某个顶点的链表为空，则此

顶点的度一定为零。

（ ）3．顺序表在物理存储空间中一定是连续的。

（ ）4．满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。 （ ）5．快速排序是排序算法中平均性能最好的一种排序。 （ ）6．由树转化成二叉树，该二叉树的右子树一定为空。 （ ）7．希尔排序算法的时间复杂度为O(n)

（ ）8．栈是仅限定在一端进行插入和删除的线性表。 （ ）9．线性表的链式存储结构优于顺序存储结构。

（ ）10．线性表的顺序存储结构是通过数据元素的存储地址直接反

映数据元素的逻辑关系。

2

4

（A卷）第 5 页 共 8 页

得分 评卷人 四、程序填空题（每个空2分，共10分）

1. 下面程序段实现数据x进栈，要求在下划线处填上正确的语句。

typedef struct {int s[100]; int top;} sqstack; void push(sqstack &stack,int x) {

if (stack.top==m-1) printf(“overflow”); else {____________________;

_____________________;}

}

2．下面程序段实现向单链表的末尾添加一个元素的算法，要求在下划线处填上正确的语句。

Void InsertRear(LNode*& HL,const ElemType& item) {

LNode* newptr; newptr=new LNode; If (_____________________)

{

cerr<<\exit(1); }

newptr->data=item;

_____________________=NULL;

if (HL==NULL) HL=newptr; else{

LNode* P=HL;

While (P->next!=NULL) ____________________; p->next=newptr; }

}

5

（A卷）第 6 页 共 8 页

得分

评卷人 五、分析简答题（第一题10分，第二题6分，共16分）

1．假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成。它们在电文中出现的频度分别为{7,19,2,6,32,3,21,10}。要求： （1）请为这8个字母设计哈夫曼编码，并画出对应的哈夫曼树；（8分） （2）计算该哈夫曼树的最小加权路径长度WPL（2分）。

6

（A卷）第 7 页 共 8 页

2. 已知一棵二叉树的中序序列和后序序列分别为GLDHBEIACJFK和LGHDIEBJKFCA，请画出此二叉树。（6分）

7

（A卷）第 8 页 共 8 页

得分 评卷人 六、 算法设计题（14分）

1.设计在链式存储结构上交换二叉树中所有结点左右子树的算法。（14分）

8

本文来源：https://www.bwwdw.com/article/97iv.html