第七章图
一．选择题
1．n个顶点，e条边的有向图的邻接矩阵中非零元素有个。
A.n
B.2e
C.e
D.n+e
2．用邻接表存储图所用的空间大小（）
A．与图的顶点数和边数都有关
B．只与图的边数有关
C．只与图的顶点数有关
D．与边数的平方有关
3．有n 条边的无向图的邻接表存储法中，链边中结点的个数是（）个。
A．n B．2n C．n/2 D．n*n
4．一个带权无向连通图的最小生成树（）。
A．有一棵或多棵. B．只有一棵C．一定有多棵D．可能不存在
5．若一个图中包含有k个连通分量，若要按照深度优先搜索的方法访问所有顶点，则必须调用( )次深度优先搜索遍历的算法。
A．k B．1 C．k-1 D．k+1
二．如下所示有向图：
1．请给出每个顶点的度，入度和出度。
2．请画出其邻接矩阵、邻接表、逆邻接表、十字链表。
三．试对下图所示的AOE网络，解答下列问题。
1．求每个事件的最早发生时间ve [i]和最迟发生时间vl[i]。
2．求每个活动的最早开始时间ee(s)和最迟开始时间el(s)。
3．指出哪些活动加速可使整个工程提前完成。
四．写出下图所示的AOV网的所有拓扑有序序列。
第八章查找
一．填空题
1．采用二分法进行查找的查找表，应选择____________________方式的存储结构
2．设在有序表A[0……9]中进行二分查找，比较一次查找成功的结点数为_____，比较二次查找成功的结点数为______，比较三次查找成功的结点数为_____，比较四次查找成功的结点数为_____，比较五次查找成功的结点数为_____，平均查找长度为______。
二．选择题
1．对线性表进行二分查找时，要求线性表必须（）
A．键值有序的链接表B．键值有序的顺序表
C．链接表但键值不一定有序D．顺序但键值不一定有序
2．有一个有序表{1，4，6，10，18，35，42，53，67，71，78，84，92，99},当用二分查找法查找键值为84的结点时，经（）比较后查找成功。
A．2 B．3 C．4 D．12
3．顺序检索一个具有n个数据元素的线性表，其时间复杂度为（），二分检索一个具有n 个数据元素的线性表，其时间复杂度为（）
A．O(n) B．O(log2n) C．O(n2) D．O(nlog2n)
4．在一棵平衡二叉排序树中，每个结点的平衡因子的取值范围是()。
A. -1~1
B. -2~2
C. 1~2
D. 0~1
5．设散列表长度为m，散列函数为H（key）=key%p，为了减少发生冲突的可能性，p应取（）
A．小于m的最大奇数B．小于m的最大素数
C．小于m的最大偶数D．小于m的最大合数
6．若根据查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K%13计算哈希地址，则元素64的哈希地址为()。
A. 4
B. 8
C. 12
D. 13
三．解答题
1．给定表{19,14,22,01,66,21,83,27,56,13,10}
①试按元素在表中的顺序构造一棵二叉排序树；
②判断该二叉排序树是否平衡，若不平衡，调整其为平衡二叉树。
2．设一组关键字为（7，15，20，31，48，53，64，76，82，99），Hash函数H（key）= key % 11，Hash表表长m=11，用线性探测法解决冲突，试构造Hash表，并分别计算查找成功和查找失败情况下的平均查找长度。
第九章排序
一．填空题
1．排序是将一组任意排列的数据元素按的值从小到大或从大到小重新排列成有序的序列。
2．在排序前，关键字值相等的不同记录间的前后相对位置保持的排序方法称为稳定的排序方法。
3．在排序前，关键字值相等的不同记录间的前后相对位置的排序方法称为不稳定的排序方法。
4．外部排序是指在排序前被排序的全部数据都存储在计算机的_____________储器中。5．下列程序是按关键字的值从大到小进行直接选择排序的算法，将算法补充完整。Select(list r,int n)
{for(i=1;______________;i++)
{ k=i；
for(j=i+1;_______________;j++)
if(r[k].key if(_____________________) swap(r[k],r[i]); /*r[k]与r[i]交换*/ } } 6．将下列按关键字值从小到大进行冒泡排序的算法补充完整。 Bubblesort(int n,list r) { flag=_____________________; m=n-1; while(m>0 && flag) {flag=0; for(i=1;i<=m;i++) if(r[i].key____________r[i+1].key) {flag=_________________; swap(r[i],r[i+1]); } m--; }} 7．若快速排序算法中完成一趟快速排序的算法是Quickpass(SqList &r,int low,int high)，将完整的快速排序递归算法补充完整。 Quicksort(SqList &r,int s,int t) {if(s { i=Quickpass(L,s,t); Quicksort(r,______ ,______); Quicksort(r,____________); } 二．选择题 1．直接插入排序的方法是从第（）个元素开始，插入前边适当位置的排序方法。 A．1 B．2 C．3 D．n 2．冒泡排序的方法（）的排序方法。 A．稳定B．不稳定C．外部D．选择 3．假定对元素序列（7, 3, 5, 9, 1, 12, 8, 15）进行快速排序，则进行第一次划分后，得到的左区间中元素的个数为（）。 A．2 B．3 C．4 D．5 4．假定对元素序列（7, 3, 5, 9, 1, 12）进行堆排序，并且采用小根堆，则由初始数据构成的初始堆为（）。 A．1, 3, 5, 7, 9, 12 B．1, 3, 5, 9, 7, 12 C．1, 5, 3, 7, 9, 12 D．1, 5, 3, 9, 12, 7 5．若一个元素序列基本有序，则选用（）方法较快。 A．直接插入排序B．简单选择排序 C．堆排序D．快速排序 6．若要从1000个元素中得到10个最小值元素，最好采用（）方法。 A．直接插入排序B．简单选择排序 C．堆排序D．快速排序 栈和队列的共同特点是__________________________ .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 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. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位10. 下列图示的顺序存储结构表示的二叉树是( ) 练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 1 6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位 10. 下列图示的顺序存储结构表示的二叉树是( ) 2 数据结构上机实验题目 实验一线性表的顺序存储结构 实验学时 2学时 背景知识:顺序表的插入、删除及应用。 目的要求： 1．掌握顺序存储结构的特点。 2．掌握顺序存储结构的常见算法。 实验容 1．输入一组整型元素序列，建立顺序表。 2．实现该顺序表的遍历。 3．在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。4．判断该顺序表中元素是否对称,对称返回1,否则返回0。 5．实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。 6．输入整型元素序列利用有序表插入算法建立一个有序表。 7．利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。 8. 利用该顺序结构实现循环队列的入队、出队操作。 8．编写一个主函数,调试上述算法。 #include #define OVERFLOW 0 #define MAXSIZE 100 typedef int ElemType; typedef struct list {ElemType elem[MAXSIZE]; int length; }Sqlist; void Creatlist(Sqlist &L) {int i; printf("请输入顺序表的长度："); //输入一组整型元素序列，建立一个顺序表。 scanf("%d",&L.length); for(i=0;i 《数据结构》课程设计题目 (程序实现采用C语言) 题目1：猴子选王（学时：3） 一堆猴子都有编号，编号是1，2，3 ...m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 要求：m及n要求从键盘输入，存储方式采用向量及链表两种方式实现该问题求解。 //链表 #include { pCurr = (RingNodePtr)malloc(sizeof(RingNode)); i++; pCurr->pos = i; pPrev->next = pCurr; pPrev = pCurr; } pCurr->next = pHead; // 构成环状链表 } void KickFromRing(RingNodePtr pHead, int n) { RingNodePtr pCurr, pPrev; int i = 1; // 计数 pCurr = pPrev = pHead; while(pCurr != NULL) { if (i == n) { // 踢出环 printf("\n%d", pCurr->pos); // 显示出圈循序 pPrev->next = pCurr->next; free(pCurr); pCurr = pPrev->next; i = 1; } pPrev = pCurr; 数据结构经典例题 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 基本概念典型例题 一、单项选择题 [例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 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 第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 典型题目分类 §1 概述 ［全真模拟试卷３选择题３］数据结构中，与计算机无关的是数据的 Ａ存储结构Ｂ物理结构Ｃ逻辑结构Ｄ物理和存储结构 答案：Ｃ ［全真模拟试卷５选择题１］数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及Ａ数据的存储结构Ｂ计算方法Ｃ数据映象Ｄ逻辑存储 答案：Ａ ［全真模拟试卷５选择题３］在计算机中，算法是指 Ａ加工方法Ｂ解决方案的准确而完整的描述 Ｃ排序方法Ｄ查询方法 答案：Ｂ ［全真模拟试卷１填空题１］算法的基本特征是可行性、确定性、和拥有足够的情报。 答案：有穷性 ［全真模拟试卷６选择题２］算法分析的目的是 Ａ找出数据结构的合理性Ｂ找出算法中输入和输出之间的关系Ｃ分析算法的易懂性和可靠性Ｄ分析算法的效率以求改进 答案：Ｄ ［全真模拟试卷６填空题１］在算法正确的前提下，评价一个算法的两个标准是。答案：时间复杂度和空间复杂度［专家预测试卷３填空题１］算法的工作量大小和实现算法所需的存储单元多少分别称为算法的。 答案：时间复杂度和空间复杂度 ［全真模拟试卷３选择题１］算法的空间复杂度是指 Ａ算法程序的长度Ｂ算法程序中的指令条数 Ｃ算法程序所占的存储空间Ｄ执行过程中所需要的存储空间答案：Ｄ §2 线性表 ［全真模拟试卷６选择题３］线性表Ｌ＝（a1,a2,……,a i,……,a n），下列说法正确的是 Ａ每个元素都有一个直接前件和直接后件 Ｂ线性表中至少要有一个元素 Ｃ表中诸元素的排列顺序必须是由小到大或由大到小 Ｄ除第一个元素和最后一个元素外，其余每个元素都有且只有一个直接前件和一个直接后件 答案：Ｄ ［全真模拟试卷７选择题１］下列叙述正确的是 Ａ线性表是线性结构Ｂ栈和队列是非线性结构 Ｃ线性链表是非线性结构Ｄ二叉树是线性结构 答案：Ａ ［专家预测试卷３选择题１］根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成 Ａ动态结构和静态结构Ｂ紧凑结构和非紧凑结构 Ｃ线性结构和非线性结构Ｄ内部结构和外部结构 答案：Ｃ ［全真模拟试卷３填空题１］数据的逻辑结构有线性结构和两大类。 答案：非线性结构 ［专家预测试卷１选择题３］线性表的顺序存储结构和线性表的链式存储结构分别是 Ａ顺序存取的存储结构，顺序存取的存储结构 Ｂ随机存取的存储结构，顺序存取的存储结构 Ｃ随机存取的存储结构，随机存取的存储结构 Ｄ任意存取的存储结构，任意存取的存储结构 答案：Ｂ ［全真模拟试卷５填空题１］长度为ｎ的顺序存储线性表中，当在任何位置上插入一个元素概率都相等时，插入一个元素所需移动元素的平均个数为。 答案：ｎ/2 §3 栈和队列 ［全真模拟试卷１选择题１］栈和队列的共同特点是 Ａ都是先进先出Ｂ都是后进先出 Ｃ只允许在端点处插入和删除元素Ｄ没有共同点 答案：Ｃ ［全真模拟试卷２选择题３］如果进栈序列为e1,e2,e3,e4，则可 一、选择题(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) 1.把二元查找树转变成排序的双向链表 题目： 输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点，只调整指针的指向。 10 / \ 6 14 / \ / \ 4 8 12 16 转换成双向链表 4=6=8=10=12=14=16。 首先我们定义的二元查找树节点的数据结构如下： struct BSTreeNode { int m_nValue; // value of node BSTreeNode *m_pLeft; // left child of node BSTreeNode *m_pRight; // right child of node }; 2.设计包含min函数的栈。 定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。 3.求子数组的最大和 题目： 输入一个整形数组，数组里有正数也有负数。 数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2， 因此输出为该子数组的和18。 4.在二元树中找出和为某一值的所有路径 题目：输入一个整数和一棵二元树。 从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。 打印出和与输入整数相等的所有路径。 例如输入整数22和如下二元树 10 / \ 5 12 / \ 4 7 则打印出两条路径：10, 12和10, 5, 7。 二元树节点的数据结构定义为： struct BinaryTreeNode // a node in the binary tree { int m_nValue; // value of node BinaryTreeNode *m_pLeft; // left child of node BinaryTreeNode *m_pRight; // right child of node }; 5.查找最小的k个元素 题目：输入n个整数，输出其中最小的k个。 例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。 数据结构 1. 在一个单链表中p 所指结点之前插入一个s(值为e)所指结点时，可执行如下操作： q=head; while(q->next!=p) q=q->next; s= new Node; s->data=e; q->next= ; //填空 s->next= ; //填空 2.线性表的顺序存储结构是一种 C 的存储结构，而链式存储结构是一种_A__的存储结构。 A．随机存取B．索引存取C．顺序存取D．散列存取 3.线性表若采用链式存储结构时，要求内存中可用存储单元的地址_D__。 A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续或不连续都可以 4.在一个单链表中，已知q 所指结点是p 所指结点的前驱结点，若在q 和p 之间插入s 结点，则执行__C__。 A. s->next=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 所指结点不是最后结点，在p 之后插入s 所指结点，则执行 _B___。 A. s->next=p; p->next=s; B. s->next=p->next; p->next=s; C. s->next=p->next; p=s; C. p->next=s; s->next=p; 6.在一个单链表中，若删除p 所指结点的后续结点，则执行__A__。 A. p->next= p->next->next； B. p= p->next; p->next= p->next->next； C. p->next= p->next; D. p= p->next->next； 7.链表不具备的特点是_A___。 A 可随机访问任何一个元素C 无需事先估计存储空间大小 B 插入、删除操作不需要移动元素 D 所需存储空间与线性表长度成正比 8.以下关于线性表的说法不正确的是 C 。 A 线性表中的数据元素可以是数字、字符、记录等不同类型。 B 线性表中包含的数据元素个数不是任意的。 C 线性表中的每个结点都有且只有一个直接前趋和直接后继。D 存在这样的线性表：表中各结点都没有直接前趋和直接后继。 9.在一个长度为n 的顺序表中删除第i个元素，要移动个元素。如果要在第i 个元素前插入一个元素，要后移()个元素。N-I N-I+1 答案1.q->next=s; s->next=p; 2.A/C（这题是考察对概念的理解，可参考第7 题，“顺序表才能随即存取，而链表不可以”） 3.D 4.C 5.B 6.A 7.A(此题绝对选A，因为链表只能根据他的前一个结点才能找到下一个结点，不具备随即访问元素的功能) 8.C 9.n-i; n-i+1 第一章数据结构与算法 第2章线性表 典型例题解析 一、选择题 1．线性表是具有n个（n≥0）的有限序列。 A．表元素B．字符C．数据元素D．数据项 【分析】线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列，通常记为(a1,a2,…,a n)，其中n为表长，n=0时称为空表。 【答案】C 2．顺序存储结构的优点是。 A．存储密度大B．插入运算方便 C．删除运算方便D．可方便地用于各种逻辑结构的存储表示【分析】顺序存储结构是采用一组地址连续的存储单元来依次存放数据元素，数据元素的逻辑顺序和物理次序一致。因此，其存储密度大。 【答案】A 3．带头结点的单链表head为空的判断条件是。 A．head==NULL B．head->next==NULL C．head->next==head D．head!=NULL 【分析】链表为空时，头结点的指针域为空。 【答案】B 4．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用存储方式最节省运算时间。 A．单链表B．仅有头指针的单循环链表 C．双链表D．仅有尾指针的单循环链表 【分析】根据题意要求，该线性表的存储应能够很方便地找到线性表的第一个元素和最后一个元素，A和B都能很方便地通过头指针找到线性表的第一个元素，却要经过所有元素才能找到最后一个元素；选项C双链表若存为双向循环链表，则能很方便地找到线性表的第一个元素和最后一个元素，但存储效率要低些，插入和删除操作也略微复杂；选项D可通过尾指针直接找到线性表的最后一个元素，通过线性表的最后一个元素的循环指针就能很方便地找到第一个元素。 【答案】D 5．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用存储方式最节省时间。 A．顺序表B．双链表 C．带头结点的双循环链表D．单循环链表 【分析】某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运 第七章图 一、名词解释 1.图 2.无向完全图 3.有向完全图 4.子图 5.连通分量 6.图的遍历 7.图的最小生成树 一、填空题 1.设x,y是图G中的两顶点，则（x,y）与（y,x）被认为________边，但 1.栈和队列的共同特点是（只允许在端点处插入和删除元素） 4.栈通常采用的两种存储结构是（线性存储结构和链表存储结构） 5.下列关于栈的叙述正确的是（D） A.栈是非线性结构 B.栈是一种树状结构 C.栈具有先进先出的特征 D.栈有后进先出的特征 6.链表不具有的特点是（B）A.不必事先估计存储空间 B.可随机访问任一元素 C.插入删除不需要移动元素 D.所需空间与线性表长度成正比 7.用链表表示线性表的优点是（便于插入和删除操作） 8.在单链表中，增加头结点的目的是（方便运算的实现） 9.循环链表的主要优点是（从表中任一结点出发都能访问到整个链表） 10.线性表L＝（a1,a2,a3,……ai,……an），下列说法正确的是（D） A.每个元素都有一个直接前件和直接后件 B.线性表中至少要有一个元素 C.表中诸元素的排列顺序必须是由小到大或由大到小 D.除第一个和最后一个元素外，其余每个元素都有一个且只有一个直接前件和直接后件 11.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（D） A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续不连续都可以 12.线性表的顺序存储结构和线性表的链式存储结构分别是（随机存取的存储结构、顺序存取的存储结构） 13.树是结点的集合，它的根结点数目是（有且只有1） 14.在深度为5的满二叉树中，叶子结点的个数为（31） 15.具有3个结点的二叉树有（5种形态） 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为（13） 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（cedba） 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为（DGEBHFCA） 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是（gdbehfca） 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 1. 在计算机中，算法是指（解题方案的准确而完整的描述） 2.在下列选项中，哪个不是一个算法一般应该具有的基本特征（无穷性） 说明：算法的四个基本特征是：可行性、确定性、有穷性和拥有足够的情报。 3. 算法一般都可以用哪几种控制结构组合而成（顺序、选择、循环） 4.算法的时间复杂度是指（算法执行过程中所需要的基本运算次数） 5. 算法的空间复杂度是指（执行过程中所需要的存储空间） 6. 算法分析的目的是（分析算法的效率以求改进） 7. 下列叙述正确的是（C） A．算法的执行效率与数据的存储结构无关 B．算法的空间复杂度是指算法程序中指令（或语句）的条数 C．算法的有穷性是指算法必须能在执行有限个步骤之后终止 D．算法的时间复杂度是指执行算法程序所需要的时间 8.数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的 习题六树和二叉树 一、单项选择题 1．以下说法错误的是( A ) A．树形结构的特点是一个结点可以有多个直接前趋 B．线性结构中的一个结点至多只有一个直接后继 C．树形结构可以表达(组织)更复杂的数据 D．树(及一切树形结构)是一种"分支层次"结构 E．任何只含一个结点的集合是一棵树 2．下列说法中正确的是( D ) A．任何一棵二叉树中至少有一个结点的度为2 B．任何一棵二叉树中每个结点的度都为2 C．任何一棵二叉树中的度肯定等于2 D．任何一棵二叉树中的度可以小于2 3．讨论树、森林和二叉树的关系，目的是为了（A ） A．借助二叉树上的运算方法去实现对树的一些运算 B．将树、森林按二叉树的存储方式进行存储 C．将树、森林转换成二叉树 D．体现一种技巧，没有什么实际意义 4．树最适合用来表示( C ) A．有序数据元素B．无序数据元素 C．元素之间具有分支层次关系的数据D．元素之间无联系的数据5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B ）A．9 B．11 C．15 D．不确定 6．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ D ）。 A．M1 B．M1+M2 C．M3 D．M2+M3 7．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ E ）A．250 B．500 C．254 D．505 E．以上答案都不对 8．二叉树的第I层上最多含有结点数为（ C ） A．2I B．2I-1-1 C．2I-1D．2I -1 10．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( B )结点A．2h B．2h-1 C．2h+1 D．h+1 11. 利用二叉链表存储树，则根结点的右指针是（B ）。 A．指向最左孩子B．指向最右孩子C．空D．非空12．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（A ）。 A．CBEFDA B．FEDCBA C．CBEDFA D．不定 13．已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（ D ）。 A．acbed B．decab C．deabc D．cedba 14．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（ B ）A．都不相同B．完全相同 《数据结构与算法》复习题 选择题 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构 B．数据结构 C．数据的逻辑结构 D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑 B．存储 C．逻辑和存储 D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。A．数据的处理方法 B．数据元素的类型 C．数据元素之间的关系 D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何 B．结点个数的多少 C．对数据有哪些运算 D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。 （1）A．找出数据结构的合理性 B．研究算法中的输入和输出的关系C．分析算法的效率以求改进 C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度 B．正确性和简明性 C．可读性和文档性 D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是 O(n2) 。 s =0; for( I =0; i经典数据结构面试题(含答案)
数据结构模拟卷(含答案)经典习题培训讲学
数据结构模拟卷(含答案)经典习题
经典数据结构上机题_答案解析
数据结构经典题目c语言代码
数据结构经典例题
数据结构典型例题
数据结构经典算法试题
数据结构课后习题详解(超完整,超经典)
[IT认证]全国计算机等级考试《数据结构》典型试题
数据结构经典复习题(仅供参考)
Java数据结构经典题
典型数据结构面试题
数据结构第2章典型例题解析
数据结构 图的习题
很好的数据结构面试题(含答案)
数据结构树的测试题(二)
数据结构(C语言)【经典试题库】附含答案解析
相关主题
文本预览