计算机专业基础综合数据结构(排序)-试卷2

数据结构试卷带答案数据结构试卷（一）一、选择题（20分）1．组成数据的基本单位是（ 1.C ）。

(A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（ C ）。

(A) 线性结构(B) 树型结构(C) 图型结构(D) 集合3．数组的逻辑结构不同于下列（D）的逻辑结构。

(A) 线性表(B) 栈(C) 队列(D) 树4．二叉树中第i(i≥1)层上的结点数最多有（C）个。

(A) 2i (B) 2i(C) 2i-1(D) 2i-15．设指针变量p指向单链表结点A，则删除结点A的后继结点B 需要的操作为（.A ）。

(A) p->next=p->next->next (B) p=p->next(C) p=p->next->next (D) p->next=p6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（.C ）。

(A) 6 (B) 4 (C) 3 (D) 27．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（C ）。

(A) 100 (B) 40 (C) 55 (D) 808．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（8.B(A) 3 (B) 4 (C) 5 (D) 19．根据二叉树的定义可知二叉树共有（B）种不同的形态。

(A) 4 (B) 5 (C) 6 (D) 710.设有以下四种排序方法，则（B ）的空间复杂度最大。

(A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序二、填空题(30分)1.设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =____________;。

计算机专业基础综合数据结构（排序）模拟试卷2(题后含答案及解析)题型有：1. 单项选择题 2. 综合应用题单项选择题1-40小题，每小题2分，共80分。

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

1．采用简单选择排序，比较次数与移动次数分别为( )。

A．O(n)，O(log2n)B．O(log2n)，O(n2)C．O(n2)，O(n)D．O(nlog2n)，O(n)正确答案：C解析：简单选择排序的关键字比较次数KCN与对象的初始排列无关。

第i 趟选择具有最小关键字对象所需的比较次数总是n—i—1次(此处假定整个待排序对象序列有n个对象)。

因此，总的关键字比较次数为：最坏情况是每一趟都要进行交换，总的对象移动次数为RMN=3(n一1)。

知识模块：数据结构2．就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是( )。

A．堆排序＜快速排序＜归并排序B．堆排序＜归并排序＜快速排序C．堆排序＞归并排序＞快速排序D．堆排序＞快速排序＞归并排序正确答案：A解析：此题考查的知识点为排序的空间复杂性。

堆排序辅助空间为O(1)，快速排序为O(log2n)，归并排序为O(n)。

应选A。

知识模块：数据结构3．一组记录的关键码为(25，48，16，35，79，82，23，40，36，72)，其中，含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为( )。

A．16，25，35，48，23，40，79，82，36，72B．16，25，35，48，79，82，23，36，40，72C．16，25，48，35，79，82，23，36，40，72D．16，25，35，48，79，23，36，40，72，82正确答案：A解析：对于(25，48，16，35，79，82，23，40，36，72)，(25，48)和(16，35)归并的结果为(16，25，35，48)。

(79，82)和(23，40)归并后的结果为(23，40，79，82)，余下的两个记录不归并，所以一趟归并后的结果为(16，25，35，48，23，40，79，82，36，72)，本题答案为A。

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

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

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

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

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

计算机学科专业基础综合数据结构-图(二)(总分100,考试时间90分钟)一、单项选择题(下列每题给出的4个选项中，只有一个最符合试题要求)1. 具有6个顶点的无向图至少应有______条边才能确保是一个连通图。

A.5 B.6 C.7 D.82. 设G是一个非连通无向图，有15条边，则该图至少有______个顶点。

A.5 B.6 C.7 D.83. 下列关于无向连通图特性的叙述中，正确的是______。

①所有顶点的度之和为偶数②边数大于顶点个数减1③至少有一个顶点的度为1A.只有① B.只有② C.①和② D.①和③4. 对于具有n(n＞1)个顶点的强连通图，其有向边的条数至少是______。

A.n+1B.nC.n-1D.n-25. 下列有关图的说法中正确的是______。

A.在图结构中，顶点不可以没有任何前驱和后继 B.具有n个顶点的无向图最多有n(n-1)条边，最少有n-1条边 C.在无向图中，边的条数是结点度数之和 D.在有向图中，各顶点的入度之和等于各顶点的出度之和6. 对于一个具有n个顶点和e条边的无向图，若采用邻接矩阵表示，则该矩阵大小是______，矩阵中非零元素的个数是2e。

A.n B.(n-1)2 C.n-1 D.n27. 无向图的邻接矩阵是一个______。

A.对称矩阵 B.零矩阵 C.上三角矩阵 D.对角矩阵8. 从邻接矩阵可知，该图共有______个顶点。

如果是有向图，该图共有4条有向边；如果是无向图，则共有2条边。

A.9 B.3 C.6 D.1 E.5 F.4 G.2 H.09. 下列说法中正确的是______。

A.一个图的邻接矩阵表示是唯一的，邻接表表示也唯一 B.一个图的邻接矩阵表示是唯一的，邻接表表示不唯一 C.一个图的邻接矩阵表示不唯一，邻接表表示唯一 D.一个图的邻接矩阵表示不唯一，邻接表表示也不唯一10. 用邻接表存储图所用的空间大小______。

A.与图的顶点数和边数都有关 B.只与图的边数有关 C.只与图的顶点数有关 D.与边数的二次方有关11. 采用邻接表存储的图的深度优先搜索算法类似于二叉树的______，广度优先搜索算法类似于二叉树的层次序遍历。

数据结构试卷试1一、解释下列术语（每小题4分，共20分）1. 头指针2. 二叉排序树的定义3. 头结点4. 数据的逻辑结构5. 排序方法的稳定性二、选择填空（每小题2分，共20分）（在每小题的4 个备选答案中，选出一个正确的答案，多选少选均不得分）1. 在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时顺向后移动( ) 个元素A.n-iB. n-i+1C. n-i-1D.i2. 某个栈的输入序列为1，2，3，4，下面的四个序列中( )不可能是它的输出序列A.1,2,3,4B.2,3,4,1C. 4,3,2,1D.3,4, 1,23. 对二叉排序进行( )遍历可以得到结点的排序序列A.前序B.中序C. 后序D.按层次4．有64个结点的完全二叉树的深度为（）。

A 8B 7C 6D 55．折半查找法的时间复杂度是( )A.(n2)B.O(n)C. O(n㏒n)D. O(㏒n)6．A(1:5,1:6)的每个元素占5个单元，将其按行优先次序储存在起始地址为1000的连续的内存单元中，则元素A[5，5]的地址为（）。

A 1140B 1145C 1120D 11257. 有n个叶子结点的哈夫曼树的结点总数为（）。

A 不确定B 2nC 2n+1D 2n-18. 已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac, 则它的前遍历序列是（）。

A acbedB decabC deabcD cedba9．若循环队列用数组A(0:m-1)存放其元素值，已知其头、尾指针分别是f和r,则当前队列中的元素个数是（）。

A (r-f+m)mod mB r-f+1C r-f-1D r-f10. 一个二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树（树中结点个数大于1）。

A 空或只有一个结点B 高度等于其结点数C 任一结点无左孩子 D任一结点无右孩子三，判断题（每小题2分，对的打√，错的打×，共10分）1．若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条（其中n为G的顶点数）。

[考研类试卷]计算机专业基础综合数据结构（排序）历年真题试卷汇编9一、综合题1 如果只要找出一个具有n个元素的集合的第k(1≤k≤n)个最小元素，你所学过的排序方法中哪种最适合?给出实现的思想。

【北方交通大学1998六(10分)】2 设结点个数为n，请问采用堆排序法进行排序，其时间复杂性是多少?请以大O 形式给出，并给出证明。

【上海交通大学2004四(10分)】2 已知待排序的序列为(503，87，512，6l，908，170，897，275，653，462)，试完成下列各题。

3 根据以上序列建立一个堆(画出第一步和最后堆的结果图)，希望先输出最小值。

4 输出最小值后，如何得到次小值(并画出相应结果图)。

【同济大学2001二(10分)】4 试将关键字序列(56，塾，55，67，46，58，18，88)5 调整成一个初始大顶堆，用二叉树形式说明调整过程；6 简要说明如何从初始大顶堆开始进行排序。

【华中科技大学2007四、24(10分)】7 一组记录的关键字为(50，79，8，56，32，41，85)，给出利用重建堆方法建立的初始堆(堆顶最大)，并给出堆排序的过程。

【吉林大学2007二、5(4分)】8 已知序列{503，87，512，61，908，170，897，275，653，462)将其调整为堆(大堆顶，即K i≥K2i，K i≥K2i+1)。

【中国海洋大学2006一、4(8分)】9 给定关键字序列(20，18，9，86，72，12，27，40)。

试将该序列建成小根堆。

10 判断下面的每个结点序列是否表示一个堆，如果不是堆，请把它调整成堆。

①100，90，80，60，85，75，20，25，10，70，65，50②100，70，50，20，90，75，60，25，10，85，65，80【复旦大学1997二(8分)】11 全国有10000人参加物理竞赛，只录取成绩优异的前10名，并将他们从高分到低分输出。

课程名称： 数据结构 考试时间：姓名： 班级： 学号：一、选择题（每题2分，共20分）（ ）1、 链表适用于_______查找A) 顺序 B) 二分法 C) 顺序，也能二分法 D) 随机（ ）2、试利用Dijkstra 算法求图中从顶点a 到其他各顶点间的最短路径A) a,c,f,e,d,g,bB) a,c,e,f,d,g,bC) a,c,f,d,e,g,bD) a,c,f,d,e,b,g(有问题)（ ）3、栈中元素的进出原则是A ）先进先出B ）后进先出C ）栈空则进D ）栈满则出 （ ）4、已知图的邻接矩阵如下，根据算法思想，则从顶点0出发按广度优先遍历的结点序列是_______。

（有问题）A) 0 2 4 3 6 5 1 B)0 1 2 3 4 5 6 C) 0 4 2 3 1 5 6 D) 0 1 3 4 2 5 6（ ）5、用5个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman ）树的带权路径长度是。

A ）32B ）33C ）34D ）15（ ）6、给定二叉树的两种遍历序列，分别是：先序遍历序列：D ，A ，C ，E ，B ，H ，F ，G ，I ； 中序遍历序列：D ，C ，B ，E ，H ，A ，G ，I ，F ，其后序遍历序 列为：A) BHECGIFAD B) BHECIGADFC) BHECIGFAD D) CHEBIGADF（ ）7、有8个结点的无向图最多有 条边。

A ）14B ）28C ）56D ）112⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡0100011101100001011010110011001000110010011011110（）8、折半查找有序表（4，6，10，12，20，30，50，70，88，100）。

若查找表中元素58，则它将依次与表中比较大小，查找结果是失败。

A）20，70，30，50 B）30，88，70，50C）20，50 D）30，88，50（）9、一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为A）38, 40, 46, 56, 79, 84 B）40, 38, 46 , 79, 56, 84C）40, 38，46, 56, 79, 84 D）40, 38, 46, 84, 56, 79（）10、排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为A）希尔排序B）归并排序C）插入排序D）选择排序二、填空题（每空2分，共20分）1、在树形结构中，树根结点没有结点，其余每个结点有且只有个前驱结点；叶子结点没有结点，其余每个结点的后续结点数可以有。

计算机专业基础综合数据结构（树与二叉树）模拟试卷2(题后含答案及解析)题型有：1. 单项选择题 2. 综合应用题单项选择题1-40小题，每小题2分，共80分。

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

1．设树T的度为4，其中度为1、2、3和4的结点个数分别为4、1、1、1，则T中的叶子数为( )。

A．10B．11C．9D．7正确答案：D解析：根据题中条件可知，1×4+2×1+3+4+1=4+1+1+1+n0，由此可以得出：n0=1×4+2×1+3+4+1一(4+1+1+1)=14—7=7. 知识模块：数据结构2．用下列元素序列(22，8，62，35，48)构造平衡二叉树，当插入( )时，会出现不平衡的现象。

A．22B．35C．48D．62正确答案：C解析：由题中所给的结点序列构造二叉排序树的过程如下图：当插入48后，首次出现不平衡子树，虚线框内即为最小不平衡子树。

知识模块：数据结构3．下面的算法实现了将二叉树中每一个结点的左右子树互换。

addQ(Q，bt)为进队的函数，delQ(Q)为出队的函数，empty(Q)为判别队列是否为空的函数，空白处应填的内容是( )。

typedef struct node{ int data；struct node*lchild，*rchild；}btnode；void exchange(btnode*bt){ btnode*p，*q；if(bt){ addQ(Q，bt)；while(!EMPTY(Q)){ p=delQ(Q)；q=p-＞rchild；p一＞rchild=p一＞lchild；( (1) )=q；if(p-&gt;lchild) ( (2) )；if(p-＞rchild)addQ(Q，p-＞rchild)；} }} A．p-＞lchild，delQ(Q，p一＞lchild)B．p-＞rchild，delQ(Q，p-＞lchild)C．p-＞lchild，addQ(Q，p-＞lchild)D．p-＞rchild，addQ(Q，p-＞lchild)正确答案：C 涉及知识点：数据结构4．已知有一棵二叉树，其高度为n，并且有且只有n个结点，那么二叉树的树形有( )种。

计算机专业基础综合（数据结构）模拟试卷2(总分：70.00，做题时间：90分钟)一、单项选择题(总题数：21，分数：42.00)1.单项选择题1-40小题。

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

（分数：2.00）__________________________________________________________________________________________ 解析：2.栈和队列的主要区别在于( )。

（分数：2.00）A.它们的逻辑结构不一样B.它们的存储结构不一样C.所包含的运算不一样D.插入和删除运算的限定不一样√解析：解析：栈和队列的逻辑结构都是线性的，都有顺序存储和链式存储，有可能包含的运算不一样，但不是其主要区别。

任何数据结构在针对具体问题时所包含的运算都可能不同。

所以正确答案是D。

3.若循环队列以数组Q[0．．m-1]作为其存储结构，变量rear。

表示循环队列中的队尾元素的实际位置，其移动按rear=(rear+1)MOD m进行，变量length表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是( )。

（分数：2.00）A.rear-lengthB.(rear—length+m)MOD mC.(rear—length+1+m)MOD m √D.m-length解析：解析：按照循环队列的定义，因为元素移动按照rect=(rear+1)MOD m进行，则当数组Q[m—1]存放了元素之后，下一个入队的元素将存放到Q[0]中，因此队列的首元素的实际位置是(rear—length+1+m)MOD m。

4.一个以向量V[n]存储的栈，其初始栈顶指针top为n+1，则对于x，其正确的进栈操作是( )。

（分数：2.00）A.top=top+1；V[top]=xB.V[top]=x；top=top+1C.top=top-1；V[top]=x √D.V[top]=x；top=top-1解析：解析：此题考查的知识点是入栈的具体操作。

计算机学科专业基础综合数据结构-排序(二)(总分：100.00，做题时间：90分钟)一、单项选择题(总题数：30，分数：31.00)1.下面给出的4种排序方法中，______排序法是不稳定性排序法。

（分数：1.00）A.插入B.冒泡C.二路归并D..堆√解析：此题考查的知识点是排序算法的稳定性问题。

如果待排序的文件中，存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序是稳定的排序；反之，若具有相同关键字的记录之间的相对次序发生变化，则称这种排序是不稳定的排序。

是否稳定与算法有关，相邻数据比较的算法是稳定的，不相邻数据比较会出现不稳定。

选项A、B、C都是相邻元素比较，是稳定的。

所以选D。

2.下列内部排序算法中，其比较次数(或交换次数)与序列初态无关的算法是______。

（分数：1.00）A.快速排序B.直接插入排序C.二路归并排序√D.冒泡排序解析：此题考查的知识点是各类排序算法的思想。

冒泡排序方法就是自底向上检查这个序列，若两个相邻的元素的顺序不对，则交换。

直到所有元素处理完为止。

与序列初态有关，D错。

直接插入排序思想是假设待排序的记录存放在数组R[n+1]中，排序过程中的某一时刻，R被分成两个子区间[R[1]，R[i-1]]和[R[i]，R[n]]，其中，前一个子区间是已排好序的有序区；后一个子区间是当前未排序的无序区。

直接插入排序的基本操作是将当前无序区的第i个记录R[i]插入到有序区中的适当位置，使得R[1]到R[i]变为新的有序区。

首先比较R[i]和R[i-1]，如果R[i-1]≤R[i]，则R[1..i]已排好序，第i遍处理就结束了；否则交换R[i]与R[i-1]的位置，继续比较R[i-1]和R[i-2]，直到找到某一个位置j(1≤j≤i-1)使得R[j]≤R[j+1]时为止。

与序列初态有关，B错。

快速排序是通过基准元素v把表(文件，数据集合)划分成左、右两部分，使得左边的各记录的关键字都小于v：右边的各记录的关键字都大于等于v；重复该过程直到排好序。

数据结构考试试题及答案一、选择题（每题2分，共20分）1. 在数据结构中，线性表的顺序存储结构通常使用什么类型的数据结构来实现？A. 栈B. 队列C. 数组D. 链表答案：C2. 下列选项中，哪一个不是二叉树的性质？A. 任意节点的左子树和右子树的深度可能不同B. 任意节点的左子树和右子树的深度相同C. 任意节点的左子树和右子树的节点数可能不同D. 任意节点的左子树和右子树的节点数相同答案：B3. 哈希表的冲突解决方法不包括以下哪种？A. 开放定址法B. 链地址法C. 线性探测法D. 排序法答案：D4. 以下哪种排序算法的时间复杂度最低？A. 冒泡排序B. 快速排序C. 插入排序D. 归并排序答案：B5. 在图的遍历算法中，深度优先搜索（DFS）使用的栈是：A. 系统栈B. 显式栈C. 隐式栈D. 以上都不是答案：B6. 以下哪种数据结构可以有效地实现稀疏矩阵的存储？A. 顺序存储B. 链表C. 散列D. 邻接矩阵答案：C7. 在二叉搜索树中，插入一个新节点后，树的平衡因子可能为：A. -2B. 0C. 2D. 3答案：A8. 堆数据结构中，父节点的值总是大于其子节点的值，这种堆被称为：A. 最小堆B. 最大堆C. 完全二叉树D. 满二叉树答案：B9. 以下哪个算法不是动态查找表的算法？A. 直接查找B. 二分查找C. 斐波那契查找D. 哈希查找答案：A10. 在图的遍历算法中，广度优先搜索（BFS）使用的栈是：A. 系统栈B. 显式栈C. 隐式栈D. 以上都不是答案：C二、填空题（每题2分，共20分）1. 在数据结构中，栈是一种______结构，遵循后进先出（LIFO）的原则。

答案：线性2. 一个具有n个顶点的无向图的边数最多为______。

答案：n*(n-1)/23. 快速排序算法的时间复杂度在最坏情况下为______。

答案：O(n^2)4. 在哈希表中，如果一个关键字的哈希地址已经被占用，则需要进行______。

年第 学期《数据结构》期末考试试卷答案年级：05级 专业：计算机科学与技术 班级： 学号： 姓名： 题号 一 二 三 四 五 六 总分 签名 得分注：1、共100分，考试时间120分钟。

2、此试卷适用于 本科专业。

一得 分 阅卷教师一、填空题（本题共10小题，每个空2分，共20分）1．根据数据元素之间的关系的不同特性，通常有下列4类基本结构：集合、线性结构、____树形结构__和图状结构。

2．数据结构中评价算法的两个重要指标是_时间复杂度 和 空间复杂度。

3. 在双链表中，存储一个结点有三个域，一个是数据域；另两个是指针域，分别指向 前驱 和后继 ．4. 一个栈的输入序列是a 、b 、c ，则不可能的栈输出序列是_c a b__。

5．在串 S = "structure"中，以 t 为首字符的子串有__12_____个。

6．广义表C ＝ ( ( ( ( a ) , b ) ) ,( ( ( ) , y ) ) )，则tail( head( tail( C ) ) )＝___（）___。

7．已知一棵完全二叉树共有768个结点，则该树中有__384__个叶子结点。

8．用Prim 算法求具有n 个顶点e 条边的图的最小生成树的时间复杂度为 O( n 2 ) 。

9．在堆排列和快速排列中，若初始记录基本无序，则最好选用 快速排序 。

10．对于长度为n 的线性表，若进行顺序查找，则时间复杂度为 O （n ） 。

二得 分 阅卷教师二、选择题（本题共10小题，每个空2分，共24分）1．线性表采用链式存储时，结点的存储地址 （ D ）A ．必须是不连续的B ．和头结点的存储地址相连续C ．必须是连续的D ．连续与否均可2．在表长为n 的顺序表上做插入运算，平均要移动的结点数为 ( C ) A ．n B ．n/3 C ．n/2 D ．n/43．递归算法转换成对应的非递归算法时，通常需要使用 （ B ） A ．队列 B ．栈 C ．链表 D ．树4．串是一种特殊的线性表，其特殊体现在 （ A ） A ．数据元素是一个字符 B ．可以顺序存储C ．可以链接存储D ．数据元素可以是多个字符5．二维数组A[8][9]采用列优先存储方法，若每个元素各占2个存储单元，而且A[0][0]的地址为1000，则A[5][7]的地址为 （ A ） A ．1122 B ．1234 C ．1212 D ．11206．有ｍ个叶结点的哈夫曼树所具有的结点数为 （ B ）Ａ．ｍ Ｂ．２ｍ－１ Ｃ．２ｍ Ｄ．ｍ＋１——————————————装————————————————订————————————————线———————————————————7．若一棵二叉树有10个叶子结点，则该二叉树中度为2的结点个数是（C ）A．11 B．10 C．9 D．不确定8．在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（d ）A．e B．2e C．n2－e D．n2－2e9．任何一个无向连通图的最小生成树有（ A ）。

数据结构样卷一．判断题（15分）1．（0 ）线性表的各种基本操作在顺序存储结构上的实现均比在链式存储结构上的实现效率要低。

2．（0 ）一个有向图的邻接表和逆邻接表中表结点的个数一定相等。

3．（1 ）先序遍历森林和先序遍历与该森林相对应的二叉树，其结果不同。

4．（1 ）不使用递归，也可实现二叉树的先序、中序和后序遍历。

5．（1 ）散列法存储的基本思想是由关键字的值决定数据的存储地址。

6．（1 ）采用折半查找法对有序表进行查找总是比采用顺序查找法对其进行查找要快。

7．（0 ）在任何情况下，快速排序方法的时间性能总是最优的。

8. （ 0 ）二维数组是其数据元素为线性表的线性表。

9.（0 ）拓扑排序是一种内部排序方法。

10．（0 ）数据的物理结构是指数据在计算机内实际的存储形式。

二．单选题（每个选择项2分，共20分）1. 单循环链表的主要优点是( D )。

A.不再需要头指针B.已知某个结点的位置后，能够容易找到它的直接前趋C.在进行插入，删除运算时，能更好地保证链表不断开D.从表中任一结点出发都能扫描到整个链表2. 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用( D )存储方式最节省时间。

A．顺序表B．单链表C．双链表D．单循环链表3. 在Hash函数H (k) = k MOD m 中，一般来讲，m应取( C )。

A．奇数B．偶数C．素数D．充分大的数4. 图的深度优先遍历算法类似于二叉树的( A )，广度优先遍历算法类似于二叉树的( D )。

A．先序遍历B．中序遍历C．后序遍历D．层次遍历5. 对树而言，不合适的遍历方法是( D )。

A．先序遍历B．中序遍历C．后序遍历D．层次遍历6. 若广义表A满足Head(A)==Tail(A)，则A为( B )。

A. ( )B. (( ))C. (( ),( ))D. (( ),( ),( ))7. 下列二叉树中，( A )可用于实现符号的不等长高效编码。

计算机专业基础综合数据结构（概论）历年真题试卷汇编2(总分：88.00，做题时间：90分钟)一、单项选择题(总题数：11，分数：22.00)1.数据元素之间的关系称为( )。

【北京理工大学2006九、2(1分)】（分数：2.00）A.操作B.结构√C.数据对象D.数据集合解析：2.(多选)一个算法具有( )等特点。

【华中科技大学2007二、17(2分)】（分数：2.00）A.有0个或多个输入量B.健壮性√C.正确性D.可行性解析：3.下面程序的时间复杂性为( )。

【南京理工大学2004一、4(1分)】for(int i=0；i（分数：2.00）A.O(n 2 )B.O(m*n) √C.O(m 2 )D.O(m+n)解析：4.在下列算法中，“x=x*2”的执行次数是( )。

【华中科技大学2006一、16(2分)】int suanfa]．(int n){int i，j，x=1;for(i=0；i（分数：2.00）A.m(n+1)／2 √B.Nlog 2 nC.n 2D.n(n一1)／2解析：5.执行下列算法suanfa2(1000)，输出结果是( )。

【华中科技大学2006一、17(2分)】void suanfa2(int n){int i=i;while(i<=n)i*=2；printf(“％d”，i);}（分数：2.00）A.2000B.512C.1024 √D.2 1000解析：6.当n足够大时下述函数中渐近时间最小的是( )。

【哈尔滨工业大学2005二、4(1分)】（分数：2.00）A.T(n)=nlog 2 n=1000log 2 nB.T(n)=nlog 2 3=1 000log 2 n √C.T(n)=n 2 =1000log 2 nD.T(n)=2nlog 2 n=1 000log 2 n解析：7.下面算法时间复杂度是( )。

【华中科技大学2006一、18(2分)】int suanfa3(int n){int i=i，s=l；while(s（分数：2.00）A.O(n) √B.O(2 2 )C.O(log 2 n)解析：8.下列函数中渐进时间复杂度最小的是( )。

《数据结构》试卷一一、填空题：（共２０分）1、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用存储结构。

2、队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是。

3、在一棵二叉树中，度为０的结点个数为n0，度为２的个数为n2，则n0= 。

4、二叉树的前序遍历序列等同于该二叉树所对应森林的遍历序列5、对一棵二叉排序树，若以遍历该树，将得到一个以关键字递增顺序排列的有序序列。

6、三个结点a,b,c组成二叉树，共有种不同的结构。

7、在AVL树中，由于在Ａ结点的右孩子的右子树上插入结点，使Ａ结点的平衡因子由-1变为-2，使其失去平衡，应采用型平衡旋转。

8、图的遍历有两种,它们是。

9、堆排序的时间复杂度为。

10、在含有N个结点的二叉链表中有空链域，通常用这些空链域存储线索，从而得另一种链式存储结构----线索链表。

二、单项选择题（共２０分）１、若进栈序列为１，２，３，４，假定进栈和出栈可以穿插进行，则可能的出栈序列是（）（A）２，４，１，３（B）３，１，４，２（C）３，４，１，２（D）１，２，３，４２、有一棵非空的二叉树，（第０层为根结点），其第i层上最多有多少个结点？（）（A）２i（B）２1-i（C）２1+i（D） i３、设电文中出现的字母为A，B，C，D，E，每个字母在电文中出现的次数分别为９，２７，３，５，１１，按huffman编码，则字母A编码为（）（A）１０（B）１１０（C）１１１０（D）１１１１４、下面关于数据结构的叙述中，正确的叙述是（）（A）顺序存储方式的优点是存储密度大，且插、删除运算效率高（B）链表中每个结点都恰好包含一个指针（C）包含n个结点的二叉排序树的最大检索长度为logn2（D）将一棵树转为二叉树后，根结点无右子树５、程序段：y:＝0while n>=(y+1)*(y+1) doy:=y+1enddo的时间复杂度为（）（A）O(n) （B）O(n2) （C）O(n2/1) （D）O(1)6、排序方法中,关键码比较的次数与记录的初始排列无关的是( )(A) shell排序 (B) 归并排序 (C) 直接插入排序 (D) 直接选择排序7、数组q[0..n-1]作为一个环行队列,f 为当前队头元素的前一位置,r为队尾元素的位置,假定队列中元素的个数总小于n,则队列中元素个数为( )(A) r-f (B) n+f-r (C) n+r-f (D) (n+r-f) mod n8、为了有效的利用散列查找技术,需要解决的问题是:( )Ⅰ:找一个好的散列函数Ⅱ:设计有效的解决冲突的方法Ⅲ:用整数表示关键码值(A) Ⅰ和Ⅲ (B) Ⅰ和Ⅱ (C) Ⅱ和Ⅲ (D) Ⅰ,Ⅱ和Ⅲ9、引入线索二叉树的目的是（）(A) 加快查找结点的前驱或后继的速度(B) 为了能在二叉树中方便的进行插入与删除(C) :为了能方便的找到双亲(D) 使二叉树的遍历结果唯一10、用二分（折半）查找表的元素的速度比用顺序法（）(A) 必然快(B) 必然慢(C): 相等(D): 不能确定三、简答题：（共40分）１、已知某二叉树按中序遍历序列为BFDAEGC，按前序遍历序列为ABDFCEG,试画出该二叉树形状，并写出它的后序遍历序列。

数据结构试卷1一、单项选择题：(每小题2分，共20分)1. 在一个长度为n的顺序表中顺序搜索一个值为x的元素时，在等概率的情况下，搜索成功时的数据平均比较次数为________。

A. nB. n/2C.(n+1)/2D.(n-1)/22. 不带头结点的单链表first为空的判定条件是_________。

A. first->next == NULL;B. first == NULL;C. first->next == first;D. first != NULL;3. 栈的插入和删除操作在__________进行。

A. 栈顶B. 栈底C. 任意位置D. 指定位置4. 假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为__________。

A. front==rearB. front!=NULLC. rear!=NULLD. front==NULL5. 设有一个广义表A ( (x, (a, b) ), (x, (a, b), y) )，运算Head (Head (Tail (A) ) ) 的执行结果为________。

A．y B．(a, b) C．(x,(a,b)) D．x6. 在一棵具有n个结点的二叉树中，所有结点的空子树个数等于_________。

A. nB. n-1C. n+1D. 2*n7. 利用n个值作为叶结点的权重，生成的霍夫曼树中共包含有_________个结点。

A. nB. n+1C. 2*nD. 2*n-18. 设无向图的顶点个数为n，则该图最多有________条边。

A. n-1B. n(n-1)/2C. n(n+1)/2D. n(n-1)9. 任何一个无向连通图的最小生成树_________。

A．只有一棵 B. 一棵或多棵C. 一定有多棵D. 可能不存在10. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为_______排序法。

计算机专业基础综合（排序）-试卷2(总分：68.00，做题时间：90分钟)一、单项选择题(总题数：16，分数：32.00)1.单项选择题1-40小题。

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

（分数：2.00）__________________________________________________________________________________________解析：2.采用简单选择排序，比较次数与移动次数分别为( )。

（分数：2.00）A.O(n)，O(log 2 n)B.O(log 2 n)，O(n 2 )C.O(n 2 )，O(n) √D.O(nlog 2 n，)，O(n)解析：解析：简单选择排序的关键字比较次数KCN与对象的初始排列无关。

第i趟选择具有最小关键字对象所需的比较次数总是n—i—1次(此处假定整个待排序对象序列有n个对象)。

因此，总的关键字比较次最坏情况是每一趟都要进行交换，总的对象移动次数为RMN=3(n—1)。

3.就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是( )。

（分数：2.00）A.堆排序<快速排序<归并排序√B.堆排序<归并排序<快速排序C.堆排序>归并排序>快速排序D.堆排序>快速排序>归并排序解析：解析：此题考查的知识点为排序的空间复杂性。

堆排序辅助空间为O(1)，快速排序为O(log 2 n)，归并排序为O(n)。

应选A。

4.一组记录的关键码为(25，48，16，35，79，82，23，40，36，72)，其中，含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为( )。

（分数：2.00）A.16，25，35，48，23，40，79，82，36，72 √B.16，25，35，48，79，82，23，36，40，72C.16，25，48，35，79，82，23，36，40，72D.16，25，35，48，79，23，36，40，72，82解析：解析：对于(25，48，16，35，79，82，23，40，36，72)，(25，48)和(16，35)归并的结果为(16，25，35，48)。

农村信用社招聘-计算机专业-数据结构与算法-综合练习题二[单选题]1.AOV网是一种（）。

A.有向图B.无向无环图C.无向图D.有向无环图[单选题]2.二叉树的第k层的节点数最多为（）。

（江南博哥）A.B.C.D.2[单选题]3.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X 的最多比较次数不超过（）。

A.B.C.D.[单选题]4.顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（）。

A.O（n-1）B.O（n）C.O（n+1）D.[单选题]5.将长度为n的单链表链接在长度为m的单链表之后的算法，其时间复杂度为（）。

A.O（m）B.O（m+n）C.O（1）D.O（n）[单选题]6.设一组初始记录关键字序列（5，2，6，3，8），以第一个记录关键字5为基准进行一趟快速排序的结果为（）。

A.3，2，5，8，6B.2，3，5，8，6C.3，2，5，6，8D.2，3，6，5，8[单选题]7.设某哈夫曼树中有199个节点，则该哈夫曼树中有（）个叶子节点。

A.101B.100C.99D.102[单选题]8.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644（10），A[2][2]存放位置在676（10），每个元素占一个空间，问A[3][3]存放在什么位置？脚注（10）表示用10进制表示。

（）A.678B.688C.692D.696[单选题]9.若允许表达式内多种括号混合嵌套，则为检查表达式中括号是否正确配对的算法，通常选用的辅助结构是（）。

A.栈B.线性表C.队列D.二叉排序树[单选题]10.设有广义表D（a，b，D），其长度为3，深度为（）A.∞B.3C.2D.5[单选题]11.设指针q指向单链表中节点A，指针p指向单链表中节点A的后继节点B，指针s指向被插入的节点X，则在节点A和节点B插入节点X的操作序列为（）。

A.p-＞next=s；s-＞next=q；B.q-＞next=s；s-＞next=p；C.p-＞next=s-＞next；s-＞next=p；D.s-＞next=p-＞next；p-＞next=-s；[单选题]12.在一棵度为3的树中，度为3的节点个数为2，度为2的节点个数为1，则度为0的节点个数为（）。

计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编2(总分：64.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：30.00)1.某表达式的前缀形式为：+-*ABCD／E／F+GH，它的中缀形式为( )。

【中国科学技术大学1992八、7(1分)】A.A B *C-D+E／F／G+HC.A B* C-D+E／(F／(G+H)) √D.A B*(C-D) +E/(G+H)2.表达式a * (b+c)一d的后缀表达式是( )。

【南京理工大学2001一、2(1．5分)】A.abcd * +一B.abc+ * d- √C.abc * +d-D.-+ * abcd3.与中缀表达式a * b+c／d-e等价的前缀表达式是( )。

【华中科技大学2006一、5(2分)】A.一+*ab／cde √B.*+／-abcdeC.abcde*+／一D.+*ab-／cde4.利用栈求表达式的值时，设立操作数栈OPND，设OPND只有两个存储单元，在下列表达式中，不发生上溢的是( )。

【四川大学2005】A.A-B*(C-D)B.(A-B)*C-D √C.(-B*C)一DD.(A一B)*(C-D)5.有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列?( )【北方交通大学2001一、3(2分)】A.5 4 3 6 12B.4 5 3 1 2 6C.3 4 6 5 2 1 √D.2 3 4 1 5 66.设栈的输入序列是1，2，3，4，则( )不可能是其出栈序列。

【中科院计算所2000一、10(2分)】【烟台大学2007一、4(2分)】A.1，2，4，3B.2，1，3，4C.1，4，3，2D.4，3，1，2 √E.3，2，1，47.四个元素1，2，3，4依次进栈，出栈次序不可能出现( )种情况。

【北京邮电大学2005一、1(2分)】A.1，2，3，4B.4，1，3，2 √C.1，4，3，2D.4，3，2，18.如进栈序列1，2，3，4，5。