云南省2004年普通高校“专升本”招生考试真题
数据结构试卷
|
题号 |
一 |
二 |
三 |
四 |
五 |
总 分 |
累分人 |
累 分 复查人 |
|
分数 |
|
|
|
|
|
|
|
|
|
评 卷 复查人 |
|
|
|
|
|
|
|
|
本试卷共9页，考生作答前应检查是否有缺页、白页，以防漏答。满分150分。考试时间150分钟。
（注：因为这套试卷属于重新在电脑上排版，所以不一定是9页的页码。但是题目一致，同学们可以参考借鉴。）
|
得分 |
评卷人 |
|
|
|
一、单项选择题：（在每小题的四个备选答案中，只有一个选项是正确的，将正确选项前的字母填入题干后括号内。本大题共15个小题，每小题3分，共45分。）
n
1．下列时间复杂度中最坏的是：（ ）
2
A．0（1） B．0（n） C．0（n ） D．0（㏒2 ）
2．在一个单链表中，右P所指节点不是最后节点，删除P之后的节点，则执行（ ）
3．在一个向图中，所有顶点的入度之和等于所有顶点的出度之和的：（ ）
A．1/2倍 B．1倍 C．2倍 D．4倍
4．若一组记录的关键码为（62，45，78，21，88），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为：（ ）
A．45，62，21，78，88 B．21，45，62，78，88
C．45，21，62，78，88 D．21，45，62，88，78
5．在有n个结点的有序表中，等概率插入一个结点所需的结点移动平均次数（ ）
A．n B．n/
6．深度为6的二叉树其结点个数至多有：（ ）
A．31 B．
7．用二分法查找有序表｛2，11，16，24，38，56，72，88，96｝中的数据56时，需进行的比较次数为：（ ）
A．2 B．
8．设数组data〔n〕作为循环队列queue的存储空间，front为队头指针；rear为队尾指针，则执行出队操作后，其头指针front的值为：（ ）
A．front=front+1 B．front=(front+1)%(n－1) C．front=(front－1)%n D．front=(front+1)%n
9．非线性结构的逻辑特征是一个节点可能有：（ ）
A．一个直接前趋和一个直接后继 B．多个直接前趋和一个直接后继
C．一个直接前趋和多个直接后继 D．多个直接前趋和多个直接后继
10．n叉树中，度为0的节点，称为：（ ）
A．根 B．叶 C．祖先 D．子孙
11．下列说法中正确的是：（ ）
A．有向图的邻接矩阵一定是非对称矩阵 B．无向图的邻接矩阵一定是对称矩阵
C．若图G的邻接矩阵是对称的则G一定是无向图 D．有向图的邻接矩阵一定是下三角矩阵
12．在一颗完全二叉树中，右编号为j的结点有左孩子，则其左孩子的编号为：（ ）
A．2j B．2j+
13．把长度为m的单链表接在长度为n的单链表之后的算法时间复杂度为：（ ）
A．0(m) B．0(n) C．0(m+n) D．0(1)
14．将整数1，2，3，4，5依次进栈，最后都出栈，出栈可以在任何时刻（只要栈不空）进行，则出栈序列不可能的是：（ ）
A．23415 B．
15．某二叉树的后序遍历为DABEC，中序遍历序列为DEBAC，则前序遍历序列为：（ ）
A．ABCDE B．DECAB C．DEABC D．CEDBA
|
得分 |
评卷人 |
|
|
|
二、填空题：（把答案填在题中横线上。本题共10个小题，每小题2分，共20分。）
1．数据结构主要研究三方面的问题，分别是数据的逻辑结构、 、 、 。
2．数据的逻辑结构分为两大类：它们分别是线性结构和 。
3．队列的插队操作在 进行，删除操作在 进行，而堆栈的插入操作在 进行，删除操作在 进行。
4．二叉排序树左子树上所有结点的值均 于根结点的值。
5． 称为网。
6．如果结点A有2个兄弟，分别是C和D，而B为C的父亲，则B的度为 。
7．有n个结点的无向图中，其边数最多为 。
8．在一个长度为n的顺序表中，第 i个元素（1≤i≤n）之前插入一个元素时，需向后移动
个元素。
9．设线性表L是顺序存储，若起始地址L（a1）=1000，每个元素占4个存储单元，
则L（a6）= 。
10．假定一组记录的排序码为（46，79，56，38，40，80），对其进行一趟昌泡排序的结果为：
。
|
得分 |
评卷人 |
|
|
|
三、解答题：（本大题共4个小题，1，2题每题8分，3，4题每题9分，共34分）
1．哈希表是数据结构中的一个重要理论，简述它的算法思想。
2．给于给定的一组权值W=｛1，20，4，9，8，16｝，建立哈夫曼树，并计算带权路径长度wpl。（要求左子树根结点的权值均小于等于右子树根结点的权值，否则不给分。）
3．按二叉树线索算法，在下面填上标记和线索，使其成为后序线索二叉村。（注：标记Ltag，Rtag若其对应指针指向子树则其值为0，其对应指针为线索则其值为1。）
Ltag Rtag
|
|
|
A |
|
|
|
|
|
B |
|
|
|
|
|
C |
|
|
|
|
|
D |
|
|
|
|
|
E |
|
|
|
|
|
F |
|
|
符号太多，由于网络不支持，更多内容请到办公室查询！
