2018年浙江理工大学991数据结构考研真题试题试卷

2018年全国硕士研究生入学统一考试计算机学科专业基础综合试卷一、单项选择题：140小题，每小题2分，共80分。

下列每题给出的四个选项中，只有一个选项符合题目要求。

请在答题卡上将所选项的字母涂黑。

b5E2RGbCAP 1．已知程序如下：ints(int n>{ return (n<=0> ? 0 : s(n-1> +n。

}void main(>{ cout<< s(1>。

}程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息一次对应的是A．main(>->S(1>->S(0> B．S(0>->S(1>->main(>p1EanqFDPwC．main(>->S(0>->S(1> D．S(1>->S(0>->main(>DXDiTa9E3d【参考答案】 D【考查知识点】栈的基本概念和函数调用的原理。

2．先序序列为a,b,c,d的不同二叉树的个数是A．13B．14C．15D．16【参考答案】 C【考查知识点】二叉树的基本概念。

3．下列选项给出的是从根分别到达两个叶节点路径上的权值序列，能属于同一棵哈夫曼树的是A．24，10，5和 24，10，7B．24，10，5和24，12，7C．24，10，10和 24，14，11 D．24，10，5和 24，14，6【参考答案】 C【考查知识点】哈夫曼树的原理。

4．现在有一颗无重复关键字的平衡二叉树<AVL树）,对其进行中序遍历可得到一个降序序列。

下列关于该平衡二叉树的叙述中，正确的是RTCrpUDGiTA．根节点的度一定为2B．树中最小元素一定是叶节点C．最后插入的元素一定是叶节点D．树中最大元素一定是无左子树【参考答案】 B【考查知识点】树的中序遍历和AVL树的基本概念。

5．设有向图G=(V,E>，顶点集V={V0,V1,V2,V3}，边集E={<v0,v1>,<v0,v2>,<v0,v3>，<v1,v3>},若从顶点V0 开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是5PCzVD7HxAA．2 B．3 C．4 D．5【参考答案】 D【考查知识点】图的深度优先遍历。

浙江理工大学二O一二年‎硕士学位研‎究生招生入‎学考试试题‎考试科目：数据结构代码：991 （请考生在答‎题纸上答题‎，在此试题纸‎上答题无效‎）一、单选题(每题2分，共20分)1. 不带头结点‎的单链表s‎i mple‎L ist为‎空的判定条‎件是。

A. simpl‎e List‎== nullB. simpl‎e List‎->next == nullC. simpl‎e List‎->next = simpl‎e List‎D. simpl‎e List‎! = null2. 某线性表最‎常用的操作‎是在最后一‎个结点之后‎插入一个结‎点或删除第‎一个结点，故采用__‎_____‎_____‎___存储‎方式最节省‎运算时间。

A. 单链表B. 仅有头结点‎的单循环链‎表C. 双链表D. 仅有尾指针‎的单循环链‎表3. 向一个栈顶‎指针为to‎p的链栈中‎插入一个S‎所指结点时‎，则执行__‎_____‎_____‎_____‎_____‎_。

A. top->next = S;B. S->next = top->next; top->next = S;C. S->next = top; top = S;D. S->next = top; top = top->next;4. 一维数组和‎线性表的区‎别是___‎_____‎_____‎。

A. 前者长度固‎定，后者长度可‎变B. 后者长度固‎定，前者长度可‎变C. 两者长度均‎固定D. 两者长度均‎可变5. 设矩阵A是‎一个对称矩‎阵，为了节省存‎储，将其下三角‎部分按行序‎存放在一维‎数),在一组数组‎B的下标位‎置组B[1, n(n-1)/2]中，对任一下三‎角部分中任‎一元素ai‎j(i jK的值是‎_____‎_。

A. i(i-1)/2+j-1B. i(i-1)/2+jC. i(i+1)/2+j-1D. i(i+1)/2+j6.在线索化二‎叉树中，P所指的结‎点没有左子‎树的充要条‎件是___‎_____‎_____‎_____‎_____‎。

浙江省2018年1月高等教育自学考试数据结构试题课程代码：02331一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内。

每小题2分，共38分)1.某二叉树的先序序列和后序序列正好相同，则该二叉树一定是( )的二叉树。

A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子2.下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(log2n)的是( )A.堆排序B.冒泡排序C.直接选择排序D.快速排序3.下列排序算法中，( )算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。

A.堆排序B.冒泡排序C.快速排序D.SHELL排序4.一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是( )A. 2 3 4 1 5B. 5 4 1 3 2C. 2 3 1 4 5D. 1 5 4 3 25.设循环队列中数组的下标范围是1～n，其头尾指针分别为f和r，则其元素个数为( )A. r-fB. r-f+1C. (r-f) mod n+1D. (r-f+n) mod n6.若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用( )存储方式最节省时间。

A.单链表B.双链表C.带头结点的双循环链表D.单循环链表7.在有n个结点的二叉链表中，值为非空的链域的个数为( )A. n-1B. 2n-1C. n+1D. 2n+18.一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为( )A. 0B. 1C. 2D.不确定9.数组A［５］［６］的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A［５，５］的地址为( )A. 1140B. 1145C. 1120D. 112510.求最短路径的DIJKSTRA算法的时间复杂度为( )A. O(n)B. O(n+e)C. O(n2)D. O(n×e)11.对有18个元素的有序表作二分查找，则查找A［3］的比较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，312.快速排序算法在最好情况下的时间复杂度为( )A. O(n)B. O(nlog2n)C. O(n2)D. O(log2n)13.下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是( )A.堆排序B.冒泡排序C.快速排序D.直接插入排序14.二叉树在线索化后，仍不能有效求解的问题是( )A.先序线索二叉树中求先序后继B.中序线索二叉树中求中序后继C.中序线索二叉树中求中序前趋D.后序线索二叉树中求后序后继15.DFS算法的时间复杂度为( )A. O(n)B. O(n3)C. O(n2)D. O(n+e)16.队列操作的原则是( )A.先进先出B.后进先出C.只能进行插入D.只能进行删除17.有64个结点的完全二叉树的深度为( )(根的层次为1)。

数据结构试卷 1一、单选题1. 栈和队列的共同特点是 ()。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时 ( ).A.仅修改头指针B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中哪一个是非线性结构？ ( )A. 队列B. 栈C. 线性表D. 二叉树4.设有一个二维数组 A[m][ n]，假设 A[0][0] 存放位置在644(10)，A[2][2] 存放位置在 676(10)，每个元素占一个空间，问A[3][3] (10)存放在什么位置？脚注 (10)表示用10进制表示。

A．688B． 678C．692D．6965.树最适合用来表示 () 。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第 k 层的结点数最多为 ( ).A．2k-1B.2K+1 C.2K-1 D. 2 k-17. 若有 18 个元素的有序表存放在一维数组A[19] 中，第一个元素放 A[1] 中，现进行二分查找，则查找 A ［3］的比较序列的下标依次为 ()A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对 n 个记录的文件进行快速排序，所需要的辅助存储空间大致为A. O（1）B. O （n）C. O（1og2n）D. O（n2）9.对于线性表（ 7，34， 55，25，64， 46，20，10）进行散列存储时，若选用 H（K）=K %9作为散列函数，则散列地址为 1 的元素有（）个，A．1B．2C．3D．410.设有 6个结点的无向图，该图至少应有 ()条边才能确保是一个连通图。

A.5B.6C.7D.8二、填空题1.通常从四个方面评价算法的质量：_________、 _________、 _________和_________。

2.一个算法的时间复杂度为 (n3+n2log2n+14n)/n2，其数量级表示为 ________。

浙江理工大学数据结构与算法期末样卷(1)模拟试卷二一、单选题（每题2分，共20分）1．在一个具有额外字段结点的单链表中hl中，若要向字段填入一个由指针p指向的结点，则继续执行()a.hl=p;p->next=hl;b.p->next=hl->next;hl->next=p;c.p->next=hl;p=hl;d.p->next=hl;hl=p;2．若顺序存储的循环队列的queuemaxsize=n,则该队列最多可以存储（）个元素a.nb.n-1c.n+1d.不确定3．下列哪一条就是顺序存储方式的优点？（）a.存储密度大b.插入和删除运算方便c.获取符合某种条件的元素方便d.查找运算速度快4．建有一个二维数组a[m][n]，假设a[0][0]放置边线在600(10)，a[3][3]放置边线在678(10)，每个元素占到一个空间，问a[2][3](10)存放在什么边线？(注释(10)则表示用10十进制则表示,m>3)a.658b.648c.633d.6535．下列关于二叉树遍历的叙述中，正确的是()a.若一个树叶就是某二叉树的中序结点的最后一个结点，则它必就是该二叉树的前序结点最后一个结点b.若一个点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点c.若一个结点就是某二叉树的中序结点的最后一个结点，则它必就是该二叉树的前序最后一个结点d.若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点6．k层二叉树的结点总数最多为()a.2k-1b.2k+1c.2k-1d.2k-17．对线性表展开二分法搜寻，其前提条件就是()a.线性表以链接方式存储，并且按关键码值排好序b.线性表以顺序方式存储，并且按关键码值的检索频率排好序c.线性表以顺序方式存储，并且按关键码值排好序d.线性表以链接方式存储，并且按关键码值的检索频率排好序8．对n个记录进行堆排序，所需要的辅助存储空间为()a.o（1og2n）b.o（n）c.o（1）d.o（n2）9．对于线性表（7，34，77，25，64，49，20，14）展开杂凑存储时，若采用h（k）=k%7做为杂凑函数，则杂凑地址为0的元素存有（）个，a.1b.2c.3d.410．以下关于数据结构的描述中，恰当的就是()a.数组就是相同类型值的子集b.递归算法的程序结构比迭代算法的程序结构更为精炼c.树是一种线性结构d.用一维数组存储一棵全然二叉树就是有效率的存储方法二、填空题（每空1分，共26分）1．数据的逻辑结构被分成_________、________、__________和___________四种。

数据结构期末考试题库及答案2018目录第1章绪论 (1)第2章线性表 (4)第3章栈和队列 (8)第4章串、数组和广义表 (12)第5章树和二叉树 (16)第6章图 (20)第7章查找 (22)第8章排序 (28)第1章绪论1．选择题（1）数据结构是指（1. A ）。

A.数据元素的组织形式B.数据类型C.数据存储结构D.数据定义（2）计算机内部数据处理的基本单位是（10. B ）。

A.数据B.数据元素C.数据项D.数据库（3）数据结构中，与所使用的计算机无关的是数据的 C 结构.A) 存储 B) 物理 C) 逻辑 D) 物理和存储【解析】[解析] 数据结构概念一般包括数据的逻辑结构、存储结构及数据上的运算集合等。

数据的逻辑结构只抽象地反映数据元素之间的逻辑关系，而不管它在计算机中的存储形式。

（4）算法分析的目的是____C________A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性（5）计算机算法必须具备输入、输出和 B 等5个特性。

A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性（6）在数据结构中，从逻辑上可以把数据结构分成（）。

A．动态结构和静态结构 B．紧凑结构和非紧凑结构C．线性结构和非线性结构 D．内部结构和外部结构答案：C（7）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。

A．存储结构 B．存储实现C．逻辑结构 D．运算实现答案：C（8）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。

A．数据具有同一特点B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C．每个数据元素都一样D．数据元素所包含的数据项的个数要相等答案：B（9）以下说法正确的是（）。

A．数据元素是数据的最小单位B．数据项是数据的基本单位C．数据结构是带有结构的各数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构答案：D解释：数据元素是数据的基本单位，数据项是数据的最小单位，数据结构是带有结构的各数据元素的集合。