1、数据结构习题集2009年全国硕士研究生入学统一考试 计算机科学与技术学科联考 计算机学科专业基础综合考试大纲 教育部考试中心 中国学位与研究生教育学会工科工作委员会目 录I. 考查目标 II. 考试形式和试卷结构考查范围 III. 考查范围数据结构 计算机组成原理 操作系统 计算机网络IV. 试题示例.考查目标计算机学科专业基础综合考试涵盖数据机构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。要求考生比较系统地掌握上述专业基础课程的概念、基本原理和方法，能够运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。.考试形式和试卷结构一、试卷满分及考试时间 本试卷满分为1
2、50分，考试时间为180分钟二、答题方式 答题方式为闭卷、笔试三、试卷内容结构 数据结构 45分 计算机组成原理 45分 操作系统 35分 计算机网络 25分四、试卷题型结构 单项选择题 80分（40小题，每小题2分） 综合应用题 70分.考查范围数据结构【考查目标】1.理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。2.掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。3.能够选择合适的数据结构和方法进行问题求解。一、线性表（一）线性表的定义和基本操作（二）线性表的实现1.顺序存储结构2.链式存储结构3.线性表的应用二、栈、队列和数组（一）
3、栈和队列的基本概念（二）栈和队列的顺序存储结构（三）栈和队列的链式存储结构（四）栈和队列的应用（五）特殊矩阵的压缩存储三、树与二叉树（一）树的概念（二）二叉树1.二叉树的定义及其主要特征2.二叉树的顺序存储结构和链式存储结构3.二叉树的遍历4.线索二叉树的基本概念和构造5.二叉排序树6.平衡二叉树（三）树、森林1.书的存储结构2.森林与二叉树的转换3.树和森林的遍历（四）树的应用1.等价类问题2.哈夫曼（Huffman）树和哈夫曼编码四、 图（一）图的概念（二）图的存储及基本操作1.邻接矩阵法2.邻接表法（三）图的遍历1.深度优先搜索2.广度优先搜索（四）图的基本应用及其复杂度分析1.最小（代
4、价）生成树2.最短路径3.拓扑排序4.关键路径五、查找（一）查找的基本概念（二）顺序查找法（三）折半查找法（四）B-树（五）散列（Hash）表及其查找（六）查找算法的分析及应用六、内部排序（一）排序的基本概念（二）插入排序1.直接插入排序2.折半插入排序（三）气泡排序（bubble sort）（四）简单选择排序（五）希尔排序（shell sort）（六）快速排序（七）堆排序（八）二路归并排序（merge sort）（九）基数排序（十）各种内部排序算法的比较（十一）内部排序算法的应用试题示例一、单项选择题：140小题，每小题2分，共80分。在每小题给出的四个选项中，请选出一项最符合题目要求的。试
5、题示例：1、 下列排序算法中，时间复杂度为O（nlog2n）且占用额外空间最少的是堆排序 起泡排序 C快速排序 D希尔排序2、 下列序列中，满足堆定义的是A（100，86，48，73，35，39，42，57，66，21） B（12，70，33，65，24，56，48，92，86，33）C（103，97，56，38，66，23，42，12，30，52，6，26） D（5，56，20，23，40，38，29，61，35，76，28，100）二、综合应用题：4147小题，共70分。试题示例：41（10分）设无向图G=（V，E），其中V=1，2，3，4，5，E=（1，2，4），（2，5，5），（1，3
6、，2），（2，4，4），（3，4，1），（4，5，3），（1，5，8），每条边由一个三元组表示，三元组中前两个元素为与该边关联的顶点，第三个元素为该边的权。请写出图G中从顶点1到其余各点的了短路径的求解过程。要求列出最短路径上的顶点，并计算路径长度.42.(15分)已知一棵二叉树采用二叉链表存储,结点构造为:LeftChild Data RightChild ,root指向根结点。现定义二叉树中结点X0 的根路径为从根结点到X0 结点的一条路径，请编写算法输出该二叉树中最长的根路径（多条最长根路径中只输出一条即可。算法可使用C或C + +或JAVA语言实现）。第 1 章 绪论一、单选题1、在数
7、据结构中，从逻辑上可以把数据结构分成A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构2、算法分析的两个主要方面是A、空间复杂性和时间复杂性 B、正确性和简明性 C、可读性和文档性 D、数据复杂性和程序复杂性3、数据的不可分割的最小单位是A、结点 B、数据元素 C、数据项 D、数据对象4、在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为A、规则 B、集合 C、结构 D、运算5、与程序运行时间有关的因素主要有以下四方面，其中与算法关系密切的是A、问题的规模 B、机器代码质量的优劣 C、机器执行速度
8、 D、语句的执行次数二、判断题1、数据结构是带有结构的数据元素的集合。 ( )2、程序越短，运行的时间就越少。( )3、处理同一问题的算法是唯一的。( )4、一个完整算法可以没有输入，但必须有输出。( )三、填空题1、_是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。2、_结构的数据元素之间存在一对多的关系。3、数据结构的形式化定义为 (D，S)，其中 D 是_的有限集，S 是 D 上关系的有限集。4、数据结构在计算机中的_称为存储结构。5、数据元素之间的关系在计算机中有两种不同的表示方法：顺序映象和非顺序映象，由此得到两种不同的存储结构是_存储结构和_存储结构。6、一个算法具
9、有五个特性：_、_、_、有零个或多个输入、有一个或多个输出。7、评价一个算法的好坏应该从算法的正确性、可读性、_和_等几方面进行。四、解答题1、设n为正整数。试确定下列各程序段中前置以记号的语句的频度： i=1；k=0；while (i=n-1) k+=10*i； i+； i=1；k=0；do k+=10*i； i+； while (i=n-1)； i=1；k=0；while (i=n-1) i+； k+=10*i； k=0；for (i=1；i=n；i+) for (j=i；j=n；j+) k+；2、阅读以下算法：void fun(int n)int i，j，k，s，x； for (s=0，
10、i=0；in；i+) for (j=i；jn；j+) s+； i=1；j=n；x=0；while (irlink=p;q-llink=p-llink;p-llink=q;p-llink-rlink=q (B) p-llink=q;q-rlink=p；p-llink-rlink=q;q-llink=p-llink(C) q-llink=p-rlink;q-rlink=p;p-link-rlink=q;p-llink=q(D) 以上都不对8. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是： （A）110 （B）108 （C）100 （D）120 9. 在n个结点的
11、顺序表中，算法的时间复杂度是O（1）的操作是( ) （A） 访问第i个结点（1in）和求第i个结点的直接前驱（2in） （B） 在第i个结点后插入一个新结点（1in） （C） 删除第i个结点（1in） （D） 将n个结点从小到大排序 10. 链式存储结构所占存储空间（ ） （A） 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 （B） 只有一部分，存放结点值 （C） 只有一部分，存储表示结点间关系的指针 （D） 分两部分，一部分存放结点值，另一部分存放结点所占单元数 11. 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时
12、间。(A) 单链表 (B) 仅有头指针的单循环链表 (C) 双链表 (D) 仅有尾指针的单循环链表12. 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（ ） （A）n （B）2n-1 （C）2n （D）n-1 13 线性表L在以下哪种情况下适用于使用链式结构实现（ ） （A）需经常修改L中的结点值 （B）需不断对L进行删除插入 （C）L中含有大量的结点 （D）L中结点结构复杂 14在一个单链表L中，若要删除由指针q所指向结点的后继结点，则执行（ ）。（A） p=q-next; p-next=q-next （B） p=q-next; q-next=p（C） p=q-next;
13、q-next; q-next=q（D） q-next=q=-next-next; q-next=q;15 在非空双向循环链表中，在由q所指的结点后面插入一个由p所指的结点的过程是依次执行：p-Llink=q,p-Rlink=q-Rlink,q-Rlink=p，（ ）。(括号中应该填上一条赋值语句) （A） q-Llink=p （B） q-Rlink-Llink=p （C） p-Rlink-Llink=p （D） p-Llink-Llink=p二、判断题1线性表的逻辑顺序与存储顺序总是一致的。( )2顺序存储的线性表可以按序号随机存取。( )3顺序表的插入和删除操作不需要付出很大的时间代价，因为
14、每次操作平均只有近一半的元素需要移动。( ) 4在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。( )5在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。( )6线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。( )7在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。( )8. 如果没有提供指针类型的语言，就无法构造链式结构。( ) 9. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各个单元向前移动。( ) 10. 线性表的每个结点只能是一个简单类型，而链表的每个结点
15、可以是一个复杂类型。( ) 11. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。( )12. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( )13. 在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点。( )14. 一个循环链表可以由所给定的头指针或者尾指针唯一确定。( )三、填空题1线性结构的基本特征是:若至少含有一个结点，则除起始结点没有直接_外，其他结点有且仅有一个直接_;除终端结点没有直接_外，其它结点有且仅有一个直接_.2线性表的顺序存储结构通过_来直接反映数据元素之间的逻辑关系，而链式存储结构则通过_间接反映数据元素之间的逻辑关系。3线性表的常
16、见链式存储结构有_、_和_。4对于长度为n的非空线性表，插入或者删除一个数据元素的操作的时间复杂度为_。5在一个单链表中指针p所指结点之后插入一个由指针s所指结点，应执行s-next=_;和p-next=_的操作。6在一个单链表中删除指针p所指结点（若存在），则需要修改指针的操作是_。7对于一个长度为n的非空顺序表，删除它的第i个数据元素时，需要移动_个其他数据元素。8在以H为头指针的带表头结点的单循环链表中，链表为空的条件为 。9.在单链表中，每个结点包含有两个域，一个叫 域，另一个叫 域。10.在下面数组a中存储着一个静态链表，表头指针为a0.next，则该线性表为 。a012345678
17、data605642387425next437620111一元多项式f(x) =9x10-3x7+6x-5的单链表表示是_。四、解答题1何时选用顺序表、何时选用链表作为线性表的存储结构为宜?2简述带头结点和不带头结点的单链表的区别。3说明在顺序表中实现插入操作和删除操作时为什么必须移动数据元素，以及插入操作和删除操作各自移动数据元素的方向？4在单链表和双向链表中，能否从当前结点出发访问到任一结点？5. 设有多项式 A(x)=7+3x+9x8+5x17 B(x)=8x+22x7-9x8(1) 用单链表给出A(x)的存储表示。（画出单链表示意图）(2) 用单链表给出B(x)的存储表示。（画出单链表
18、示意图）(3) 以上述两个单链表为基础，通过插入和删除等运算得出A(x)+B(x)的存储表示，使其存储空间覆盖A(x)和B(x)的存储空间。（画出单链表示意图）五、算法设计题1长度为n的递增有序顺序表，请写一的算法，将x插入到顺序表的中，并保持该表的有序性。2试写实现顺序表的就地逆置的算法，即利用原表的存储空间将线性表（a1,a2,an）逆置成（an,an-1,a1）3对单链表实现就地逆置。4试写一个高效算法，删除单链表中所有大于min且小于max的元素（若表中存在这样的元素）同时释放被删除结点的空间，并分析你的算法的时间复杂度（min和max是给定的两个参变量，它们的值可以和表中的元素相同，
19、也可以不同）5. 已知数组A1.n的元素类型为整型。设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为o(n)。6. 有两个按数据元素值递增有序排列的线性表A和B。编写算法将A表和B表归并成一个按元素值递增有序（即非递减有序，允许值相同）排列的线性表C，并要求利用原表(即A表和B表的)结点空间存放表C。（请分A，B均以顺序表作存储结构和A，B均以单链表作存储结构，这两种情况写算法）。7. 假设有两个按数据元素值递增有序排列的线性表A和B，均以单链表作存储结构。编写算法将A表和B表归并成一个按元素值递减有序（相同值元素只保留一个）排列的线性表C，并要求
20、利用原表(即A表和B表的)结点空间存放表C。8. 已知一单链表中的数据元素含有三个字符(即:字母字符、数字字符和其它字符)。试编写算法，构造三个循环链表，使每个循环链表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间(头结点可另辟空间)。9. 已知两个单链表A和B分别表示两个集合，其元素递增排列，编写一个函数求出A和B的交集C，要求C同样以元素递增的单链表形式存储。第 3 章 栈、队列和数组一、单选题1. 栈中元素的进出原则是( )。 (A) 先进先出 (B)后进先出 (C)栈空则进 (D)栈满则出 2. 栈的插入与删除操作在( )进行。 (A) 栈顶 (B) 栈底 (C) 任
21、意位置 (D) 指定位置3 .若让元素1，2，3依次进栈，则出栈次序不可能出现（ ）种情况。 （A） 3，2，1 （B） 2，1，3 （C） 3，1，2 （D） 1，3，24. 若用一个大小为6 的数组来实现循环队列，且当rear和front的值分别为O和3。当从队列中删除一个元素，再加入两个元素后，rear 和front 的值分别为（ ）（A） l和5 （B） 2和4 （C） 4和2 （D） 5和l 5一般情况下，将递归算法转换成等价的非递增归算法应该设置( )。（A）堆栈 （B）队列 （C）堆栈或队列 （D）数组6链栈与顺序栈相比，有一个比较明显的优点即 （ ）（A）插入操作更方便 （B）
22、通常不会出现栈满的情况 （C）不会出现栈空的情况 （D）删除操作更方便 7设C语言数组Datam+1作为循环队列SQ的存储空间， front为队头指针，rear为队为指针，则执行出队操作的语句为（ ）(A) front=front+1 (B) front=（front+1）%m (C) rear=(rear+1)%m (D) front=(front+1)%(m+1)8. 若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若p1=n，则pi为 （A）i （B）n=i （C）n-i+1 （D）不确定 9. 设有一顺序栈T，元素s1,s2,s3,s4,s5,s6依次进栈，
23、如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是（ ） （A）2 （B）3 （C） 5 （D）610数组n用来表示一个循环队列，f为当前队列头元素的前一位置，r为队尾元素的位置，假定队列中元素的个数小于n，计算队列中元素的公式为 （A）rf （B）（nfr）% n （C）nrf （D）（nrf）% n 11中缀表达式A-(B+C/D)*E的后缀形式是（ ）(A) AB-C+D/E* (B) ABC+D/-E* (C) ABCD/E*+- (D) ABCD/+E*-12一个算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( )。
24、 (A) -A+B*C/DE (B) A+B*CD/E (C) -*ABC/DE (D) -A*BC/DE13.循环队列A0.m-1存放其元素，用front和rear分别表示队头和队尾，则循环队列满的条件是（ ）。（A）（Q.rear+1）%m=Q.front (B) Q.rear=Q.front+1 (C) Q.rear+1=Q.front (D) Q.rear=Q.front14.解决计算机主机和打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区应该是一个（ ）结构（A）栈 （B）队列 （C）线性表 （D）
25、数组15.假设顺序栈的定义为：typedef struct selemtype *base; /* 栈底指针*/ selemtype *top; /* 栈顶指针*/ int stacksize; /* 当前已分配的存储空间,以元素为单位*/ sqstack; 变量st的类型为sqstack，则栈st为空的判断条件为（ ）。 （A）st.base = NULL （B） st.top = st.stacksize （C） st.top-st.base= st.stacksize （D） st.top = st.base16对于以行序为主序的存储结构来说，在数组Ac1d1，c2d2中，c1和d1分别
26、为数组A的第一个下标的上、下界，c2d2分别为第二个下标的上、下界，每个数据元素占K个存储单元，二维数组中任一元素Ai,j的存储位置可由( )式确定.(A) Loci,j=( d2-c2+1)(i- c1)+(j- c2)*k (B) Loci,j=locc1, c2+( d2- c2+1)(i- c1)+(j- c2)*k(C) Loci,j=Ac1, c2+( d2- c2+1)(i- c1)+(j- c2)*k (D) Loci,j=loc0,0+( d2- c2+1)(i- c1)=(j- c2)*k17对于基于三元组的稀疏矩阵转置的处埋方法以下说法正确的是 ( )(A)按照矩阵A的列序来进行转置，算法的时间复杂度为0(nu+tu) (B)按照A的三元组a.data的次序进
