计算机专业数据结构综合测试2
数据结构测试（长春理工大学精品课）
综合测试二
一、选择
1.链表不具有的特点是（）查看答案
A 可随机访问任一元素
B 插入删除不需要移动元素
C 不必事先估计存储空间
D 所需空间与线性表的长度成正比
正确答案为A
解释：单链表不能随机访问某个元素，这种存储结构必须采用顺序访问的方式，根据头指针依此才能找到后继元素的地址，以便访问。收起
2.非空的循环单链表head的尾结点p满足（）查看答案
A p->next==NULL
B p==NULL
C p->next==head
D p==head
正确答案为C
解释：循环链表的尾结点的后继应是头结点。收起
3.对稀疏矩阵进行压缩存储是为了（）。查看答案
A 便于进行矩阵运算
B 便于输入和输出
C 节省存储空间
D 降低运算的时间复杂度
解释：矩阵采用压缩存储，相同的元素存一次，零元素不存，主要目的是为了节约内存空间，在很多时候为了找到相应元素，需要找到元素和存储位置的对应关系，反而增大了时间复杂度。收起
4.具有15个结点的二叉树的最小深度是（）。查看答案
A 4
B 5
C 3
D 6
正确答案为A
解释：n个结点的二叉树最小深度应是完全二叉树的深度logn+1，因此n=15时，最小深度是4。收起
5.在有n个叶子结点的哈夫曼树中，其结点总数为（）查看答案
A 不确定
B 2n
C 2n+1
D 2n-1
正确答案为D
解释：赫夫曼树只有度为0和度为2的结点，叶子结点有n个，那么度为2的结点有n-1个，即总结点个数为2n-1个。收起
6.不带权的无向图的邻接矩阵（）。查看答案
A 不一定是对称矩阵
B 是对角线元素非零的对称矩阵
C 是上三角矩阵
D 是对角线元素为零的对称矩阵
正确答案为D
解释：无向图的邻接矩阵为对称矩阵，又因图中各顶点不包含到自身的关系，因此对角线上元素为0。收起
7.下列排序算法中，（）算法可能会出现下面情况：初始数据有序，化费时间反而最多.
查看答案
A 堆排序
B 冒泡排序
C 快速排序
D Ｓhell排序
正确答案为C
解释：对于快速排序每次找到枢轴的位置基本将待排集合对分是最好的情况，如果待排集合基本有序，快速排序算法就退化了，时间复杂度可达到O（n*n）。收起
8.对关键码集合K={53,30,37,12,45,24,96},从一棵二而叉树开始逐个插入关键码，建立二叉排序树，若希望的到的二叉排序树的高度最小，应选用下列输入序列（）。查看答案
A 45，24，53，12，37，96，30
B 37，24，12，30，53，45，96
C 12，24，30，37，45，53，96
D 30，24，12，37，45，96，53
正确答案为B
解释：构造的二叉排序树的形态和查找关键字的顺序有关，要想构造的二叉排序树的高度最小，应建立成和完全二叉树一样的高度，关键字是7个，因此最终建立的是一棵满二叉树，又根据排序树的特点，左子树结点比根结点小，根结点比右子树小，根结点应当是37，依此得出答案为B。收起
9.用折半查找法查找表（a1,a2,…,a11）,需要比较4次才能找到的元素是（）。
查看答案
A a1和a8
B a4和a7
C a2和a8
D a4和a10
正确答案为C
解释：根据折半查找建立折半查找判定树，查找表区间为1-11，第1层树根为a6，第二层为a3，a9，第三层为a1，a4，a7，a10，第四层为a2，a5，a8，a11。收起
10. 对一棵m阶B-树，下列选项错误的是（）。查看答案
A 每个结点最多有m个子女
B 除根结点和叶结点外，每个结点
至少有[m/2]个子女
C 有k个子女的结点必有k个
D 根结点至少有两个子女
关键码（k<=m）
正确答案为C
解释：根据B-树的定义，只有C不满足定义，有k个子女的结点应有k-1个关键字。收起
二、填空题
1.下面程序段的时间复杂度是( )。查看答案
for( i=1;i for ( j=1;j<(2*n);j++) x=x+1;} 正确答案为O(n*n) 解释：外层循环循环体执行n-1次，内层循环循环体执行2n-1次，因此算法的时间复杂度为O(n*n) 。收起 2. 用链表表示线性表,表中元素之间的逻辑关系是通过链表中结点的( )来实现的。 查看答案 正确答案为指针 解释：链式存储结构中线性表中元素的逻辑关系通过后继指针指出。收起 3.设循环队列用数组A[m]表示,队头、队尾指针分别是front和rear,则判定队满的条件为 ( ) 查看答案 正确答案为(rear+1)% M==front收起 4.已知完全二叉树有200个结点,则整个二叉树有 ( )个度为1的结点。查看答案 正确答案为1 解释：假设二叉树中度为0的结点个数为n0个，二叉树中度为1的结点个数为n1个，二叉树中度为2的结点个数为n2个，根据完全二叉树的特点，完全二叉树中n1只能是0个或1个，再结合二叉树的性质n0+n1+n2=200，n2=n0-1，得2n0+n1=201，因此n1只能取1。收起 5.在有向图的邻接矩阵表示中，第j列元素之和等于第j个顶点的 ( ) 查看答案 解释：有向图的邻接矩阵表示法中，第i行非0元素个数之和表示第i个 顶点的出度，第i列非0元素个数之和表示第i个顶点的入度。收起 6.对用邻接表表示的连通图进行深度或广度优先遍历时的时间复杂度为 ( ) 查看答案 正确答案为O(n+e 收起 7.对于关键字序列（１２,１３,１１,１８,６０,１５,７,１８,２５,１００），用筛选法建堆，必须从关键字为 ( )的结点开始．查看答案 正确答案为60 解释：初始建堆应从第n/2的位置开始建堆。收起 8.对n个元素的序列进行冒泡排序时 ( )情况下比较次数最少. 查看答案 正确答案为初始有序 解释：冒泡排序若关键字初始有序，则第一个关键字和第二个关键字比较，无交换，第二个关键字和第三个关键字比较，无交换，依此类推，第n-1个和第n个关键字比较，无交换，共比较n-1次，这种情况是关键字比较次数最少的，算法时间复杂度也降低为O(n)。收起 9.长度为11的有序表进行折半查找时，在等查找概率情况下查找成功的平均查找长度为 ( ) 正确答案为3 解释：根据折半查找算法建立折半查找判定树，查找表的长度为11，第一层有一个结点，第二层有两个结点，第三层有四个结点，第四层有四个结点，因此平均查找长度为（1+2*2+3*4+4*4）/11=3。收起 10.哈希查找是通过 ( )来确定记录的存储地址的。查看答案 正确答案为计算哈希函数值 解释：哈希查找就是通过哈希函数值确定记录的存储位置，建立起关键字和存储位置之间的关系。收起 三、应用题 1.假设一棵树的先根序列为ABCEFIJHGKD，后根序列为JIKHGFEDCBA。请画出该树。 查看答案 解： （1）因为树的先根和后根遍历序列分别与其转换后对应的二叉树的先根和中根遍历序列相同，所以可先得到的对应的二叉树如下图所示： （2）根据树与二叉树的转换规则，可得到树如下图所示： 收起 2.请用克鲁斯卡尔算法构造下图所示网络的最小生成树。查看答案 解：最小生成树如下图所示： 收起 (1)插入n; (2)删除e 查看答案 解： 下列是一棵五阶B-树,依次执行以下两步操作,画出每一步执行后所得到的B-树形。 (1)插入n: (2)删除e: 收起 4.给出一组关键字K={14,28,17,9,7,21,13,4,11},写出用下列方法排序时,第一趟结束时关键字的排列状态。 (1)快速排序 (2)希尔排序(d1=4) (3)归并排序。查看答案 (1)快速排序：{11,4,13,9,7}14{21,17,28} (2)希尔排序(d1=4) ： {7,21,13,4,11,28,17,9,14} (3)归并排序：[11，28 ] [9，17 ] [7，21 ] [4，13 ] [11 ]收起 四、算法设计题 1.编写算法，将非空单链表hb插入到单链表ha的第i(0 int algo1(LNode *ha, LNode *hb,int i){ for(p=hb;p->next; p=p->next); for(j=1,q=ha;j p->next=q->next; q->next=hb->next; free(hb); } 收起 2.已知一棵具有n个结点的完全二叉树被顺序存储在一维数组中，编写算法打印出编号为k的结点的双亲和孩子结点。查看答案 int algo2(char bt[],int n,int k){ if (k<1||k>n) return 0; if( k==1) printf(“ %c is a root\n”, bt[1]); else printf(“ %c’s parent is %c\n”, bt[k], bt[k/2]); if(2*k<=n) printf(“ %c’s lchild is %c\n”, bt[k],bt[2*k]); else printf(“ %c is not lchild\n”, bt[k])); else printf(“ %c is not rchild\n”, bt[k])); return 1; }收起 2010-2011 学年第2 学期课号BT11107 课程名称数据结构（B卷; 闭卷）适用班级（或年级、专业）08011103、104、105 一、填空题（每小题2分，共20分） (1) 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的 （）和运算等的学科。 (2)在一个长度为n的顺序表中第i个元素（1 ≤i ≤n）之前插入一个元素时，需向后 移动（）个元素。 (3）假设以S和X分别表示进栈和退栈操作，则对输入序列a，b，c，d，e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为（）。 （4）数据的逻辑结构在计算机存储器内的表示，称为数据的（）。 （5）在具有n个单元的循环队列中，队满时共有____个元素。 （6）二叉树有（）种基本形态。 （7）在具有n个结点的完全二叉树中，若结点i有左孩子，则结点i的左孩子编号为（）。（8）若用二叉树表示具有n个结点的二叉树，则有（）个空链域。 （9）深度为k（k>0）的二叉树，至多有（）个结点，第i层上之多有（）结点。 (10) 一个有n个顶点的无向图最多有____条边。 二、选择题（每小题2分，共20分） 1.研究数据结构就是研究（）。 (A) 数据的逻辑结构 (B) 数据的存储结构 (C) 数据的逻辑结构和存储结构 (D) 数据的逻辑结构、存储结构及其数据的运算 2.下列算法的时间复杂度是（） s=0; for (i=0;i 数据结构例题（及答案） 项目一习题(答案) 一选择题 1. 算法的计算量的大小称为计算的(B )。 A( 效率 B. 复杂性 C. 现实性 D. 难度 2.算法的时间复杂度取决于(C ) A(问题的规模 B. 待处理数据的初态 C. A和B 3(从逻辑上可以把数据结构分为(C )两大类。 A(动态结构、静态结构 B(顺序结构、链式结构 C(线性结构、非线性结构 D(初等结构、构造型结构 4(连续存储设计时，存储单元的地址(A )。 A(一定连续 B(一定不连续 C(不一定连续 D(部分连续，部分不连续 5. 以下属于逻辑结构的是(C )。 A(顺序表 B. 哈希表 C.有序表 D. 单链表 二、判断题 1. 数据元素是数据的最小单位。(×) 2. 记录是数据处理的最小单位。(×) 3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系;(×) 4(程序一定是算法。(×) 5. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。(×) 6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(×) 7. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。(?) 8. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. (×) 三、填空 1(数据的物理结构包括数据元素的表示和数据元素间关系的表示。 2. 对于给定的n个元素,可以构造出的逻辑结构有集合，线性结构，树形 结构，图状结构或网状结构四种。 3(数据的逻辑结构是指数据的组织形式，即数据元素之间逻辑关系的总体。而 逻辑关系是指数据元素之间的关联方式或称“邻接关系”。 4(一个数据结构在计算机中表示(又称映像) 称为存储结构。 5(抽象数据类型的定义仅取决于它的一组逻辑特性，而与在计算机内部如何表 示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响 其外部使用。 6(数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度。 7. 数据结构是研讨数据的逻辑结构和物理结构，以及它们之间的相互 关系，并对与这种结构定义相应的操作(运算)，设计出相应的算法。 ( 一个算法具有5个特性: 有穷性、确定性、可行性，有零个或多个输入、 有一个或多个输8 出。 四、应用题 1. 1. 数据结构是一门研究什么内容的学科, 答:数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象 及对象间的关系和施加于对象的操作等的学科 2. 2. 数据元素之间的关系在计算机中有几种表示方法,各有什么特点, 答:四 种表示方法 中国矿业大学2011-2012学年 《数据结构》试卷（A卷）（考试时间：100分钟） 一. 填空（每空2分，共40分） 1. 数据结构式具有相同性质的数据元素的（1）。 2. 通常程序在调用另一个程序时，都需要使用一个（2）来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。 3. 有6行8列的二维数组A，每个元素用相邻的6个字节存储，存储器按字节编址，已知A的起始存储地址（基址）为1000，在行优先存储和列优先存贮情况下A[5,5]的存储地址分别为__（3）_____,_____(4)____。 4. 完全二叉树第4 个节点的父节点是第 (5) 节点，左孩子是第 (6) 个节点。如果该二叉树有10层，则共有 (7) 个节点。 5. 请描述在循环队列Q中，队头和队尾指针分别由front和rear表示，该队列有10个存储空间，判断队空和队满的条件分别分：_____(8)________,_______(9)_________。 6. 字符串t=”child”，s=”cake”，请写出下列函数的结果：StrLength(t) =（10）__;Concat(SubString(s,3,1)，SubString(t,2,2))=____（11）___。 7. 一棵二叉树为 则后序序列为（12），中序序列为（13），先序序列为__（14）____。 8. 请用数据序列{53，17，12，66，58，70，87，25，56，60 }构造一棵二叉排序树_(15）_。 9.。一个栈输入的序列式1,2,3，则可能的且以2为开头的输出序列是 (16) ，不可能的序列是____（17）____。 10. 有n个结点的无向完全图的边数分别为_______(18)_______。 11. 要从数据：2，3，4，8，9，11，13查找11，若采用折半查找法，则在（19）次比较后，才找到该数据。 12. 在直接插入排序、希尔排序、冒泡排序和快速排序中，平均情况下（20）_____最快。 二简答题： 1给定{15,3,14,2,6,9,16,17}，试为这8个数设计哈夫曼编码，并计算其带权路径长度。 2请对下图的无向带权图按克鲁斯卡尔算法求其最小生成树。（要求使用图画出每一步过程）。 C G E D F B H A 数据结构试题及答案 一、单项选择题 (1)一个算法应该就是（)。 A)程序???B）问题求解步骤得描述 C）要满足五个基本属性??D) A与C (2)算法指得就是（)。 A）计算机程序???B）解决问题得计算方法 C)排序算法???D）解决问题得有限运算序列。 (3)与数据元素本身得形式、内容、相对位置、个数无关得就是数据得(）。 A) 存储结构B) 逻辑结构C）算法D)操作 (4)从逻辑上可以把数据结构分为( ）两大类。 A）动态结构、静态结构??B) 顺序结构、链式结构 C）线性结构、非线性结构???D）初等结构、构造型结构 (5)下列叙述中正确得就是(）。 A)一个逻辑数据结构只能有一种存储结构 B）数据得逻辑结构属于线性结构,存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理得效率 D）一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理得效率 (6)数据得基本单位就是（） ?A) 数据项??B) 数据类型C)数据元素??D)数据变量 (7)下列程序得时间复杂度为（) i=０；s＝０; wｈｉlｅ(s 计算机专业基础综合（数据结构）模拟试卷1 (总分：72.00，做题时间：90分钟) 一、单项选择题(总题数：21，分数：42.00) 1.单项选择题1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数： 2.00）__________________________________________________________________________________________ 解析： 2.若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则下面最节省运算时间的存储方式是( )。 （分数：2.00） A.单链表 B.带有头指针的单循环链表 C.双链表 D.带有尾指针的单循环链表√ 解析：解析：在链表中的最后一个结点之后插入一个结点要知道终端结点的地址，所以，单链表、带有头指针的单循环链表、双链表都不合适。考虑在带有尾指针的单循环链表中删除第一个结点，其时间性能是O(1)，所以答案是D。 3.已知两个长度分别为l和s的降序链表，若将它们合并为一个长度为l+s的升序链表，则最坏情况下的时间复杂度是( )。 （分数：2.00） A.O(l) B.O(ls) C.O(min(l，s)) D.O(max(l，s)) √ 解析：解析：在合并过程中，最坏的情况是两个链表中的元素依次进行比较，比较的次数最少是m和n中的最大值。 4.线性表中存放的主要是( )。 （分数：2.00） A.整型常量 B.字符 C.数据元素√ D.信息元素 解析：解析：线性表中主要存放的是数据元素，而数据元素可以是整型也可以是字符型，但对于一个线性表来说，所有的数据元素的类型必须相同。 5.下面的叙述中正确的是( )。 I．线性表在链式存储时，查找第i个元素的时间同i的值成正比Ⅱ．线性表在链式存储时，查找第i个元素的时间同i的值无关Ⅲ．线性表在顺序存储时，查找第i个元素的时间同i的值成正比 （分数：2.00） A.仅I √ B.仅Ⅱ C.仅Ⅲ D.I、Ⅱ、Ⅲ 解析：解析：在线性表链式存储结构中，查找第i个元素的时间与i的位置成正比。而在顺序存储结构中查找第i个元素的时间与i的位置无关。 6.对于某线性表来说，主要的操作是存取任一指定序号的元素和在最后进行插入运算，那么应该选择( )存储方式最节省时间。 （分数：2.00） A.顺序表√ 栈和队列的共同特点是__________________________ .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中，增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是 __________________________ 13.树是结点的集合，它的根结点数目是_____________________ 14.在深度为5的满二叉树中，叶子结点的个数为_______________ 15.具有3个结点的二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是 ____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中，算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________ 数据结构试卷1 一、单项选择题：(每小题2分，共20分) 1. 在一个长度为n的顺序表中顺序搜索一个值为x的元素时，在等概率的情况下，搜索成功时的数据平均比较次数为________。 A. n B. n/2 C.(n+1)/2 D.(n-1)/2 2. 不带头结点的单链表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==rear B. front!=NULL C. rear!=NULL D. front==NULL 5. 设有一个广义表A ( (x, (a, b) ), (x, (a, b), y) )，运算Head (Head (Tail (A) ) ) 的执行结果为________。 A．y B．(a, b) C．(x,(a,b)) D．x 6. 在一棵具有n个结点的二叉树中，所有结点的空子树个数等于_________。 A. n B. n-1 C. n+1 D. 2*n 7. 利用n个值作为叶结点的权重，生成的霍夫曼树中共包含有_________个结点。 A. n B. n+1 C. 2*n D. 2*n-1 8. 设无向图的顶点个数为n，则该图最多有________条边。 A. n-1 B. n(n-1)/2 C. n(n+1)/2 D. n(n-1) 9. 任何一个无向连通图的最小生成树_________。 A．只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在 10. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为_______排序法。 A．选择B.二路归并C.交换 D.插入 二、填空题（每空1分，共20分） 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的____________以及它们之间的___________和运算等的学科。 2. 顺序表中逻辑上相邻的元素的物理位置________相邻。单链表中逻辑上相邻的元素的物理位置__________相邻。 3. 在单链表中，除了首元结点外，任一结点的存储位置由___________________ 指示。 4. ________ 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性 《数据结构》题库及答案 一、选择题 1．线性表的顺序存储结构是一种 的存储结构，线性表的链式存储结构是一种 的存储结构。 a. 随机存储； b.顺序存储； c. 索引存取； d. HASH 存取 2．一个栈的入栈序列是a,b,c,d,e ，则栈的不可能的输出序列是 。 a. edcba; b. decba; c. dceab; d.abcde 3．一个队列的入队序列是1，2，3，4，则队列的输出序列是 。 a. 4,3,2,1; b. 1,2,3,4; c. 1,4,3,2; d.3,2,4,1 4．在一个单链表中，已知p 结点是q 结点的直接前驱结点，若在p 和q 之间插入结点s ，则执行的操作是 。 a. s->nxet=p->next; p->next=s; b. p->next=s->next; s->next=p; c. q->next=s; s->next=p; d. p->next=s; s->next=q; 5．设有两个串p,q ，求q 在p 中首次出现的位置的运算称作 。 a.联接 b.模式匹配 c.求子串 d.求串长 6．二维数组M 的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i 的范围从0到8，列下标j 的范围从1到10，则存放M 至少需要 个字节。 a. 90 b.180 c.240 d.540 7．在线索二叉树中，结点p 没有左子树的充要条件是 。 a. p->lch==NULL b. p->ltag==1 c. p->ltag==1且p->lch=NULL d. 以上都不对 8．在栈操作中，输入序列为（A ，B ，C ，D ），不可能得到的输出序列为：______ A 、（A ， B ， C ， D ） B 、（D ，C ，B ，A ） C 、（A ，C ，D ，B ） D 、（C ，A ，B ，D ） 9．已知某二叉树的后序序列是dabec ，中序序列是debac ，则它的先序序列是 。 A 、acbed B 、decab C 、deabc D 、cedba 10．设矩阵A 是一个对称矩阵，为了节省存储空间，将其下三角部分（见下图）按行序存放在一维数组B[1..n(n-1)/2]中，对任一上三角部分元素)(j i a ij ，在一维数组B 的存放位置是 。 2018计算机考研：计算机数据结构测试题(四) 2018考研，计算机专业课考试科目为：计算机组成原理、数据结构、操作系统以及计算机网络等，需要大家记忆的知识点有很多，但是不能死机硬背，还是要理解为主的，融会贯通才能把题做好，拿到高分，小编就为大家分享计算机数据结构测试题及参考答案，希望计算机考研的考生在复习之余能够认真做题，巩固知识。 计算机数据结构测试题(四) 一、选择题(30分) 1.设某无向图有n个顶点，则该无向图的邻接表中有( )个表头结点。 (A) 2n (B) n (C) n/2 (D) n(n-1) 2.设无向图G中有n个顶点，则该无向图的最小生成树上有( )条边。 (A) n (B) n-1 (C) 2n (D) 2n-1 3.设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字45为基准而得到的一趟快速排序结果是( )。 (A) 40，42，60，55，80，85 (B) 42，45，55，60，85，80 (C) 42，40，55，60，80，85 (D) 42，40，60，85，55，80 4.( )二叉排序树可以得到一个从小到大的有序序列。 (A) 先序遍历(B) 中序遍历(C) 后序遍历(D) 层次遍历 5.设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为( )。 (A) 2i+1 (B) 2i (C) i/2 (D) 2i-1 6.程序段s=i=0;do {i=i+1; s=s+i;}while(i<=n);的时间复杂度为( )。 (A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(n3/2) 7.设带有头结点的单向循环链表的头指针变量为head，则其判空条件是( )。 (A) head==0 (B) head->next==0 (C) head->next==head (D) head!=0 8.设某棵二叉树的高度为10，则该二叉树上叶子结点最多有( )。 (A) 20 (B) 256 (C) 512 (D) 1024 9.设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为( )。 (A) 1 (B) 2 (C) 3 (D) 4 10.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为( )。 (A) top=top+1; (B) top=top-1; (C) top->next=top; (D) top=top->next; 二、判断题(20分) 1.不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。( ) 2.当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。( ) 3.设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为O(log2n)。( ) 一、选择题(20分) 1．下面关于线性表的叙述错误的是（D ）。 (A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现 (D) 线性表采用顺序存储便于插入和删除操作的实现 2．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（A ）。 (A) BADC (B) BCDA (C) CDAB (D) CBDA 3．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（C ）。 (A) 9 (B) 10 (C) 11 (D) 12 4．设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（B ）。 (A) O(1) (B) O(log2n) (C) (D) O(n2) 5．设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（B ）方法可以达到此目的。 (A) 快速排序(B) 堆排序(C) 归并排序(D) 插入排序 第9小题分析：9快速排序、归并排序和插入排序必须等到整个排序结束后才能够求出最小的10个数，而堆排序只需要在初始堆的基础上再进行10次筛选即可，每次筛选的时间复杂度为O(log2n)。 6.下列四种排序中（D ）的空间复杂度最大。 (A) 插入排序(B) 冒泡排序(C) 堆排序(D) 归并排序 7．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（C ）。 (A) O(n) (B) O(nlog2n) (C) O(1) (D) O(n2) 8．设一棵二叉树的深度为k，则该二叉树中最多有（D ）个结点。 (A) 2k-1 (B) 2k(C) 2k-1(D) 2k-1 9．在二叉排序树中插入一个结点的时间复杂度为（B ）。 (A) O(1) (B) O(n) (C) O(log2n) (D) O(n2) 10．设用链表作为栈的存储结构则退栈操作（B ）。 (A) 必须判别栈是否为满(B) 必须判别栈是否为空 (C) 判别栈元素的类型(D) 对栈不作任何判别 11．下列四种排序中（A ）的空间复杂度最大。 (A) 快速排序(B) 冒泡排序(C) 希尔排序(D) 堆 12．设某二叉树中度数为0的结点数为N0，度数为1的结点数为N l，度数为2的结点数为N2，则下列等式成立的是（C ）。 (A) N0=N1+1 (B) N0=N l+N2(C) N0=N2+1 (D) N0=2N1+l 13.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不 超过（A ）。 (A) log2n+1 (B) log2n-1 (C) log2n (D) log2(n+1) 14．数据的最小单位是（A ）。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 15．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（D ）。 (A) O(log2n) (B) O(1) (C) O(n2) (D) O(n) .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中，增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是__________________________ 13.树是结点的集合，它的根结点数目是_____________________ 14.在深度为5的满二叉树中，叶子结点的个数为_______________ 15.具有3个结点的二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中，算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________ 单选题(每题2分，共20分) 1. 1. 对一个算法的评价，不包括如下(B )方面的内容。 A .健壮性和可读性 B .并行性 C .正确性 D .时空复杂度 2.2. 在带有头结点的单链表HL 中，要向表头插入一个由指针 p 指向 的结点，则执行(A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; 都具有相同的(A )。 A.行号 B .列号 C .元素值 D .非零元素个数 9. 快速排序在最坏情况下的时间复杂度为(D )。 A. O(log 2n) B . O(nlog 2n) C . 0(n) D 10.10. 从二叉搜索树中查找一个元素时，其时间复杂度大致 为 A. O(n) B. O(1) C. O(log 2 n) D. O(n 二、 运算题(每题6分，共24分) 1. 1. 数据结构是指数据及其相互之间的 _________________ 。当结点之 间存在M 对N (M N)的联系时，称这种结构为 __________________________ 。 2. 2. 队列的插入操作是在队列的_ _尾 ________ 行，删除操作是在队 列的 ____ 首 _____ 行。 3. 3. 当用长度为N 的数组顺序存储一个栈时，假定用top==N 表示栈 C. p->next=HL; p=HL; 3. 3. A. C. D. HL=p; p-> next=HL; 对线性表，在下列哪种情况下应当采用链表表示? 经常需要随机地存取元素 B. 表中元素需要占据一片连续的存储空间 一个栈的输入序列为1 2 3， 4. 4. 列的是(C ) A. 2 3 1 C. 3 1 2 AOV 网 是一种(D ) 有向 图 B .无向图 (B ) 经常需要进行插入和删除操作 D.表中元素的个数不变 则下列序列中不可能是栈的输出序 B. 3 2 1 5. 5. 6. .无向无环图 D .有向无环图 采用 开放定址法处理散列表的冲突时，其平均查找长度( B. 高于链接法处理冲突 D .高于二分查找 7. 8. 6. A.低于链接法处理冲突 .与链接法处理冲突相同 7. 参数。 A.值 8. B)。 若需要利用形参直接访问实参时，应将形参变量说明为( B .函数 C .指针 D .引用 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点 9. .0(n 2) (C )。 2 ) [考研类试卷]计算机专业基础综合数据结构（概论）历年真题试卷汇编 2 一、单项选择题 1 以下哪个数据结构不是多型数据类型?( )【中山大学1999一、3(1分)】 （A）栈 （B）广义表 （C）有向图 （D）字符串 2 以下数据结构中，( )是非线性数据结构【中山大学1999一、4】 （A）树 （B）字符串 （C）队 （D）栈 3 下列数据中，( )是非线性数据结构。【北京理工大学2001六、1(2分)】（A）栈 （B）队列 （C）完全二叉树 （D）堆 4 连续存储设计时，存储单元的地址( )。【中山大学1999一、1(1分)】 （A）一定连续 （B）一定不连续 （C）不一定连续 （D）部分连续，部分不连续 5 以下属于逻辑结构的是( )。【西安电子科技大学应用2001一、1】 （A）顺序表 （B）哈希表 （C）有序表 （D）单链表 6 算法的计算量的大小称为计算的( )。【北京邮电大学2000二、3(20／8分)】（A）效率 （B）复杂性 （C）现实性 （D）难度 7 算法的时间复杂度取决于( )。【中科院计算所1998二、1(2分)】 （A）问题的规模 （B）待处理数据的初态 （C）A和B 7 计算机算法指的是(1)，它必须具备(2)这三个特陛。【南京理工大学1999一、 1(2分)】 8 (1) （A）计算方法 （B）排序方法 （C）解决问题的步骤序列 （D）调度方法 9 (2) （A）可执行性、可移植性、可扩充性 （B）可执行性、确定性、有穷性 （C）确定性、有穷性、稳定性 （D）易读性、稳定性、安全性 10 一个算法应该是( )。【中山大学1998二、1(2分)】 （A）程序 （B）问题求解步骤的描述 （C）要满足五个基本特性 （D）A和C 11 下面说法错误的是( )。【南京理工大学2000一、2(1．5分)】 (1)算法原地工作的含义是指不需要任何额外的辅助空间 (2)在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(22)的算法 (3)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 (4)同一个算法，实现语言的级别越高，执行效率就越低 数据结构经典例题 1.设计一个算法将L拆分成两个带头节点的单链表L1和L2。 void split(LinkList *&L,LinkList *&L1,LinkList *&L2) { LinkList *p=L->next,*q,*r1; //p指向第1个数据节点 L1=L; //L1利用原来L的头节点 r1=L1; //r1始终指向L1的尾节点 L2=(LinkList *)malloc(sizeof(LinkList));//创建L2的头节点 L2->next=NULL; //置L2的指针域为NULL while (p!=NULL) { r1->next=p; //采用尾插法将*p(data值为ai)插入L1中 r1=p; p=p->next; //p移向下一个节点(data值为bi) q=p->next; //由于头插法修改p的next域,故用q保存*p的后继节点 p->next=L2->next; //采用头插法将*p插入L2中 L2->next=p; p=q; //p重新指向ai+1的节点 } r1->next=NULL; //尾节点next置空 } 2.查找链表中倒数第k个位置上的节点（k为正整数）。若查找成功，算法输出该节点的data域的值，并返回1；否则，只返回0。 typedef struct LNode {int data; struct LNode *link; } *LinkList; int Searchk(LinkList list,int k) { LinkList p,q; int count=0; p=q=list->link; while (p!=NULL) { if (count 一、单项选择题 1 某算法的时间复杂度是O(n 2 ) ，表明该算法（）。 A 问题规模是n2 B 问题规模与n2成正比 C 执行时间等于n2 D 执行时间与n2成正比 2、关于数据结构的描述，不正确的是（）。 A数据结构相同，对应的存储结构也相同。 B数据结构涉及数据的逻辑结构、存储结构和施加其上的操作等三个方面。 C数据结构操作的实现与存储结构有关。 D定义逻辑结构时可不考虑存储结构。 3、按排序策略分来，起泡排序属于（）。 A插入排序B选择排序C交换排序D归并排序 4、利用双向链表作线性表的存储结构的优点是（）。 A便于进行插入和删除的操作 B 提高按关系查找数据元素的速度 C节省空间D便于销毁结构释放空间 5、一个队列的进队顺序为1,2,3,4，则该队列可能的输出序列是（）。 A 1,2,3,4 B 1,3,2,4 C 1,4,2,3 D 4,3,2,1 6、 Dijkstra算法是按（）方法求出图中从某顶点到其余顶点最短路径的。 A按长度递减的顺序求出图的某顶点到其余顶点的最短路径 B按长度递增的顺序求出图的某顶点到其余顶点的最短路径 C通过深度优先遍历求出图中从某顶点到其余顶点的所有路径 D通过广度优先遍历求出图的某顶点到其余顶点的最短路径 7、字符串可定义为n（ n≥ 0）个字符的有限（）。其中，n是字符串的长度，表明字符串中字符的个数。 A集合B数列C序列D聚合 8、在二维数组A[9][10]中，每个数组元素占用 3 个存储单元，从首地址SA 开始按行连续存放。在这种情况下，元素A[8][5]的起始地址为（）。 A SA+141 B SA+144 C SA+222 D SA+255 9、已知广义表为L(A(u,v,(x,y),z),C(m,(),(k,l,n),(())),((())),(e,(f,g),h))，则它的长度是（）。 A2B3C4D5 10.对于具有n(n>1)个顶点的强连通图，其有向边条数至少有_____。 A. n+1 B. n C. n-1 D. n-2 11.一个递归算法必须包括 __________ 。 A. 递归部分 B . 结束条件和递归部分 C. 迭代部分 D. 结束条件和迭代部分 12.从逻辑上看可以把数据结构分为__________两大类。 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 13、若在长度为n 的顺序表的表尾插入一个新元素的渐进时间复杂度为（）。 A O(n) B O(1) C O(n 2) D O(log 2n) 14.采用顺序搜素方式搜索长度为 n 的线性表时，在等概率情况下，搜索成功时的平均搜索 长度为 __________。 A. n B. n/2 C . (n+1)/2 D. (n-1)/2 15、非空的循环单链表first的链尾结点（由p 所指向）满足（）。 A p->link==NULL; B P==NULL; 计算机专业基础综合数据结构（概论）历年真题试卷汇编3 (总分：70.00，做题时间：90分钟) 一、单项选择题(总题数：15，分数：30.00) 1.设n是描述问题规模的非负整数，下面程序片段的时间复杂度是( )。【2011年全国硕士研究生入学计算机学科专业基础综合试题】简称【201 1年全国试题1(2分)】 x=2； while(x *x； （分数：2.00） A.O(log 2 n) √ B.O(n) C.O(nlog 2 n) D.O(n 2 ) 解析： 2.求整数n(n≥0)阶乘的算法如下，其时间复杂度是( )。【2012年全国试题1(2分)】int fact(int n){if(n<=i) return i；return n*fact(n一1)； （分数：2.00） A.O(log 2 n) B.O(n) √ C.O(nlog 2 n) D.O(n 2 ) 解析： 3.已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是( )。【2013年全国试题1(2)分】 （分数：2.00） A.O(n) B.O(m×n) C.O(min(m，n)) D.O(max(m，n)) √ 解析： 4.下列程序段的时间复杂度是( )。【2014年全国试题1(2分)】count=0;for(k=1；k<=n；k*=2)for(j=1；j<=n；j++)count++； （分数：2.00） A.O(log 2 n) B.O(n) C.O(nlog 2 n) √ D.O(n 2 ) 解析： 5.在数据结构中，数据的最小单位是( )。【北京理工大学2006九、1(1分)】 （分数：2.00） A.数据元素 B.字节 C.数据项√ D.结点 解析： 6.在数据结构中，数据的基本单位是( )。【北京理工大学2004五、1(1分)】 （分数：2.00） A.数据项 B.数据类型 C.数据元素√ 基本概念典型例题 一、单项选择题 [例6-1]数据结构用集合的观点可以表示为一个二元组DS＝(D，R)。其中，D是( ①)的有穷集合，R是D上( ②)的有限集合。 ①A.算法B. 数据元素C. 数据操作D. 逻辑结构 ②A. 操作B. 映像C. 存储D．关系 解析：由数据结构的集合形式化定义可知，本题答案为：①B；②D。 [例6-2]数据的常用存储结构中不包括( )。 A．顺序存储结构B．线性结构C．索引存储结构D．散列存储结构 解析：数据通常有四种基本的存储方法，即顺序存储方法、链式存储方法、索引存储 方法和散列存储方法。由此可知，本题答案为：B。 [例6-3] 算法指的是( ①)，它必须具备( ②)这三个特性。 ①A．计算方法B．排序方法C．解决问题的步骤序列D．调度方法 ②A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性 C．确定性、有穷性、稳定性D．易读性、稳定性、安全性 解析：算法是对特定问题求解步骤的一种描述，是由若于条指令组成的有限序列。它 必须满足以下性质：输人性、输出性、有穷性、确定性、无二义性和可行性。由此可知，本 题答案为：①㈠②B。 [例6-4] 在下面的程序段中，对x的赋值语句的执行频度为( )。 for(i=0；i B 卷 一、单项选择题 1、若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( )。 A. 顺序存储结构 B. 链式存储结构 C. 索引存储结构 D. 散列存储结构 2、在长度为n的顺序表的第i(1≤i≤n+1)位置上插入一个元素，元素的移动次数( )。 A. n-i+1 B. n-I C. i D. i-1 3、对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )。 A. 顺序表 B.用头指针表示的单循环链表 C. 用尾指针表示的单循环链表 D. 单链表 4、若进栈序列为a,b,c,则通过入出栈操作可能得到的a,b,c的不同排列个数为( )。 A. 4 B. 5 C. 6 D. 7 5、为查找某一特定单词在文本中的出现的位置，可应用的串运算是( )。 A. 插入 B. 删除 C. 串联接 D. 子串定位 6、已知函数sub(s,i,j)的功能功能是返回串s中的从第i个字符起长度为j的子串，函数scopy(s,1)的功能为复制串t到s。若字符串S=”SCIENCESTUDY“，则调用函数scopy(P,sub(S,1,7)))后得到 A. P=”SCIENCE” B. P=“STUDY” C. S=”SCIENGE” D. S=”STUDY” 7、三维数组A[4][5][6]按行优先存储在内存中，若每个元素占2个存储 单元，且数组中第一个元素的存储地址为120，则元素A[3][4][5]的存储地址为( )。 A. 356 B. 358 C. 360 D. 362 8、如右图所示广义表是一种（）。 A. 线性表 B. 纯表 C. 结点共享表 D. 递归表 9、下列陈述中正确的是( )。 A. 二叉树是度为2的有序树 B. 二叉树中结点只有一个孩子时无左右之分 C. 二叉树中必有度为2的结点 D. 二叉树中最多只有两棵子树，并且有若右之分 10、n个顶点的有向完全图中含有有有向边的数目最多为 ( ) A. n-1 B. n C. n(n-1)/2 D. n(n-1) 11、已知一个有向图如下所示，则从顶点a出发进行深度优先遍历，不可能得到的DFS序列为( )。 A. a d b e f c B. a d c e f b C. a d c b f e D. a d e f c b 12、在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是( )。 A. 快速排序 B. 堆排序 C. 归并排序 D. 基数排序 13、不可能生成右图所示二叉排序树的关键字的序列是( )。 1．假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。【北京大学1998 三、1 （5分）】 LinkedList Union(LinkedList la,lb) { pa=la->next; pb=lb->next; la->next=null; while(pa!=null && pb!=null) ∥当两链表均不为空时作 if(pa->data<=pb->data) { r=pa->next; pa->next=la->next; ∥将pa结点链于结果表中，同时逆置。 la->next=pa; pa=r; } else {r=pb->next; pb->next=la->next; ∥将pb结点链于结果表中，同时逆置。 la->next=pb; pb=r; } while(pa!=null) ∥将la表的剩余部分链入结果表，并逆置。 {r=pa->next; pa->next=la->next; la->next=pa; pa=r; } while(pb!=null) {r=pb->next; pb->next=la->next; la->next=pb; pb=r; } } 1）设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中ha表中已有的数据若hb中也有,则hb中的数据不归并到ha中,hb的链表在算法中不允许破坏。【南京理工大学1997 四、3（15分）】 LinkedList Union(LinkedList ha, hb)∥ha和hb是两个无头结点的数据域值递增有序的单链 ｛LinkedList 表，本算法将hb中并不出现在ha中的数据合并到ha中，合并中不能破坏hb链表。 la; la=(LinkedList)malloc(sizeof(LNode)); la->next=ha; pa=ha; pb=hb; pre=la; while(pa&&pb) if(pa->data数据结构试题B及参考答案(计算机专业)
数据结构经典例题
数据结构-数据结构历年考题及答案2
数据结构试题库答案
计算机专业基础综合(数据结构)模拟试卷1
经典数据结构面试题(含答案)
数据结构试卷及答案2套
《数据结构》题库及答案
2018计算机考研：计算机数据结构测试题(四)
大数据结构经典复习题(仅供参考)
经典数据结构面试题(含答案)
数据结构试题及答案(10套最新)
[考研类试卷]计算机专业基础综合数据结构(概论)历年真题试卷汇编2.doc
数据结构经典例题
算法与数据结构题库与答案
计算机专业基础综合数据结构(概论)历年真题试卷汇编3
数据结构典型例题
数据结构期末试题2及答案
数据结构经典算法试题
- 计算机专业基础综合数据结构(概论)历年真题试卷汇编3
- 数据结构试卷_计算机系
- 计算机专业数据结构试题
- 计算机专业基础综合数据结构(图)历年真题试卷汇编3
- 计算机系《数据结构》平时测试试题二
- 数据结构试题B及参考答案(计算机专业)
- 计算机专业基础综合数据结构(集合)历年真题试卷汇编8
- 广州大学插本数据结构试题
- 计算机专业数据结构模拟试题
- 完整word版四川大学计算机学院数据结构与算法分析期末试题2013级A
- 计算机系《数据结构》试题20036
- [考研类试卷]计算机专业基础综合数据结构(概论)历年真题试卷汇编2.doc
- 计算机考研数据结构试卷十一(练习题含答案)
- 2008年华南理工大学831计算机专业综合(数据结构、操作系统)考研试题
- 武汉大学计算机学院数据结构06级试题(A)含答案
- 计算机专业基础综合(数据结构)模拟试卷5
- 计算机专业基础综合数据结构(集合)历年真题试卷汇编3
- 聊城大学计算机学院数据结构A答案
- 计算机专业基础综合数据结构(排序)历年真题试卷汇编5
- 武汉大学计算机学院数据结构06级试题(A)含标准答案